This project is based on a theory by Eli Savransky. This theory is introduced in the following paper

It is recommended to first read the paper. I will assume that you familiar with the basic theory.

The process of rendering:

Because, impossible images are possible only when watching the model from a specific point of view, the software first must calculate the specific point of view (transformation) that will give the desirable effect. I will call this process, solving the scene graph. First, a viewing transformation is assigned to each graph node. This is done by starting with an arbitrary node and scanning the graph until all the nodes are visited using BFS variant. The transformation is spreading in the graph by multiplying the current node transformation with the edge transformation. If the graph doesn’t contain loops, it means that this is an ordinary, possible, scene it is trivial to render. If, while scanning the graph, we reached a node that was visited before (loop), we have to find the right viewing transformation, V, such that T1•E•V•P = T2•V•P where P is the canonic orthographic projection.

Since T1•E and T2 differ only by translation, it is easy to find the desirable V. If the graph has more than one loop, when the second loop is reached, we try to use the same V that was found before. If it satisfies the equation, the graph is solvable, otherwise the graph is not solvable and the scene is impossible to render.

The viewing transformation for each node is N = T•V.

After we assigned a viewing transformation for each node, we can start rendering the scene. A simple pseudo code is demonstrating the basics of the rendering algorithm, which is based on the OpenGL library:

EnableBuffer(Depth) //Enable the Zbuffer

EnableBuffer(Color) //Enable the Color buffer

for(int obj = 0; obj < NUM_OF_NODES; obj++){

clearBuffer(Depth) // Clear the Zbuffer
nodeMatrix = getNodeTransformation(obj)
render(obj, nodeMatrix) //render object number obj with nodeMatrix transformation
}

for(int obj = 0; obj < NUM_OF_NODES; obj++){
clearBuffer(Depth) // Clear the Zbuffer
DisableBuffer(Color) //Disable the Color buffer

for(int neighbor = 0; neighbor < NUM_OF_NEIGHBORS; neighbor++){
edgeMatrix = getEdgeTransformation(obj, neighbor)
nodeMatrix = getNodeTransformation(obj)

viewMatrix = edgeMatrix*nodeMatrix
render(neighbor, viewMatrix); //render object number neighbor with viewMatrix transformation
}
EnableBuffer(Color) //Enable the Color buffer
render(obj, nodeMatrix);
}

Note that when a transformation between 2 objects is not defined, the algorithm chooses arbitrarily and sometimes-visual artifacts arise.

The reduction algorithm:

This input for this algorithm is a graph and the output is another graph usually smaller, with less nodes and less edges but with the same geometric data.

There are 2 main reasons for reducing the graph. First, since the speed of the rendering process depends on the number of nodes in the graph, a smaller graph results in faster rendering. Second, since visual artifacts arise where there is a lack of transformation between 2 nodes, smaller graph demand less edges, hence less transformation. For example, in a scene with 7 objects we will need more than 20 transformations in order to avoid visual artifacts. Since it requires too much work, the software can try to reduce the graph and than if for example it will result in a new reduced graph with 3 nodes, it will require only 3 transformation.

Pseudo code:

The aim of this function is to reduce as much nodes as possible.

for(int s = 0; s < NUM_OF_NODES; s++){

for(int t = 0; t < NUM_OF_NODES; t++){

reduceNode(t, s);

}

}

The aim of this function is to reduce the son node into the father node and remove the son node.

bool reduceNode(int son, int father)

{

if(!isReductionPossible(son, father)){ //if the reduction is not possible, return false.

return false;

}

//go over all the neighbors of the son node.

for(int neighbor = 0; neighbor < NUM_OF_NODES; neighbor++){

Matrix44 fatherToNeighbor = getTransformation(son, neighbor)*getTransformation(father, son)

removeEdge(son, neighbor)

}

Matrix44 fatherToSon = getTransformation(father, son)

removeEdge(son, father))

removeNode(son)

return true;

}

The aim of this function is check if it is possible to reduce the son node into the father node.

bool isReductionPossible(int son, int father)

{

//go over all the neighbors of the son node.

for(int neighbor = 0; neighbor < NUM_OF_NODES; neighbor++){

if(isEdgeExist(neighbor, father)){ //if the neighbor and the father are connected.

//they are connected, and it's causing a contradiction

if(getTransformation(father, neighbor)!= getTransformation (son, neighbor) * getTransformation(father, son)

return false;

}

}

}

return true;

}

This simple algorithm is designed for fixing modeling errors. Because some objects like bars are symmetric, it is hard sometimes to differ one side of the objects from the other. Whenever the user insert a transformation that causes the scene graph to be impossible to solve, the software, automatically, tries to solve the graph with other transformations such as the same transformation combined with a rotation around the X, Y or Z axis.

Animations:

There are few kinds of animations. The simplest one is based only on the following transformation: translation in X, Y, Z axis, rotation in Z axis and scaling. Those transformations are not breaking the impossible effect and can be applied to any scene. The “Small Tri-Bar” animation is an example for this kind of animation.

At first look, it seems that other animations will not be possible for impossible objects since impossible objects can be viewed only from a certain point of view. The idea behind those animations is that the object itself is changing. Each frame of the animation actually present different object, hence it is possible to look at it from another point of view. Impossible object consist of scene graph and 3D objects. Sometimes, a different object means that the 3D objects are the same but the scene graph is different (e.g. the transformations between the objects is different) The “Rib Cube” animation is an example for this kind of animation. Sometimes, the 3D objects are different too, but this animation is more difficult to construct. The “Tri-Bar” animation is an example for this kind of animation. Note that the bars are changing their sizes during the animation.

Another animation method is to build an impossible scene in which some transformations are missing. In this case, the renderer chooses arbitrarily the missing transformation and sometimes interesting effects arises. The “Chess Cuboid” and the “Wood Cuboid” are examples for this kind of animations.

The Fat Tri-Bar effect:

The Fat Tri-Bar effect is a visual artifact that arises when at a certain area of the impossible image, there are more than 2 objects that want to contribute their color and there is no logical order between them. For example, if we got 3 bars A, B, C and at some area of the image, A is above B, B is above C and C is above A it is impossible to render such area.

You can see that the pixels at the center of this Tri-Bar are missing. No mater which object will contribute his color to the area at the center of this fat Tri-bar, it will not make any sense.