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