Sunday, August 17, 2014

Homemade 3D rendering engine (VII)

The projection model we discussed above is good enough to produce wire frame models, where models are lines and are projected to the screen from rendering. In particular, we do not care about drawing lines that should appear behind some other lines.

But for my purpose, I need to produce a cube with surface painted with colors, I need to differentiate if the plane is in front of behind, and not draw anything behind.

While the Painter’s algorithm is the most popular algorithm around, it requires too much memory for my application and I cannot use hardware acceleration, so I opted not to use that, instead, I have learnt and used the binary space partitioning tree algorithm.

Let’s start with defining half-space, a half-space is simply the region of the space that is above/below a plane. So given a plane, the space is divided into two half-spaces.

So given a plane, we can divide the model into three parts, one that is in the half space where it contains the camera. One that is exactly on the plane, and one that is in the other half-space.

Now it comes a simple divide and conquer strategy. We start with the complex model, finding a plane to split the model, build a node in the tree with that plane to represent the split, and three children as the split models. Recursively do it until it is just one plane, then we stop.


The resulting tree is the binary space partitioning tree, given a binary space partitioning tree, we know that a model appearing in the half-space containing the camera will always appear in front of the model on the plane, which is on turn appear in front of the model in the other half-space, so by doing a tree-traversal, we can render the items from back to front, effectively hiding the items that should appear on the back.

No comments :

Post a Comment