Sunday, August 17, 2014

Homemade 3D rendering engine (VIII)

While the binary space partitioning algorithm is conceptually simple, the implementation of it is fairly complicated because a lot of details are missing from the previous discussion. For example, how is the model represented? How do we choose the plane to split? How to split the model? Apparently, to implement the algorithm, all these questions has to be answered.

In my implementation, a model is a collection of triangles, with vertexes represented in world’s coordinates. We just pick one triangle (which then implies a plane) to split, the tricky part are the triangles that cross the plane need to split, and the computation of that splitting can be fairly complicated as shown below.

First, a plane can be represented by a point and its normal, crossing the two vectors of the triangle gives the normal. Determine which half-space contains the camera is straightforward.

Second, if a triangle’s vertexes are all on the same side of the half-space (the plane inclusive), we are lucky and just group that triangle in one of the left or right sub-trees.

Third, if a triangle’s vertexes are on both sides, there must be one on one side and two on other side. Determine the lonely one, find the two intersection point on the plane, that forms a triangle, the rest is a trapezoid which can easily split into two triangles as well.


In fact, there is a fourth case, that one on one size, one on the plane, and one on the other side, in that case we should split into two triangles. The case was missing in my code and some triangles mysteriously disappear … L

No comments :

Post a Comment