Kd-trees are indeed quite handy. They are eg. used in 3D games in
certain situations where triangles need to be rendered in a certain order.

  For example semi-transparent polygons have to be rendered from
farthest-from-the-camera to closest. This is because if you render them
in the wrong order, the result would not look correct (the blending of
overlapping polygons would be in the wrong order and thus the result
incorrect). Also the Z-buffer cannot be used for semi-transparent polygons.
(If you used the Z-buffer and you render the polygons in the wrong order,
some of the polygons would not be rendered at all, even though they should.)

  So assume that you have, for example 10000 blades of grass, each one with
a semi-transparent texture, and thus you need to render then from farthest
to closest, regardless of where the camera is. How to do this?

  You could, of course, try to sort the triangles at each frame. However,
not only would this be inefficient (after all, you only have about 16 ms
to do *everything* that is needed to render the next frame, and sorting
these polygons would certainly not be the only thing you have to do), but
there's a huge problem with trying to sort the triangles by depth: The
comparison function is far from trivial to implement. Determining which
of two triangles is in front of the other is a surprisingly complicated
task.

  In fact, there is no comparison function to sort triangles by depth in
the general case. This might sound like a surprising result, but it indeed
is so. Three triangles may occlude cyclically each other, in which case
they don't have a well-defined order by depth. In other words, triangle A
may partially occlude triangle B, which partially occludes triangle C,
which partially occludes triangle A. In terms of comparison, you basically
have the situation where A < B and B < C and C < A, in which case these
three elements have no well-defined order.

  With opaque triangles cyclical occlusion is not a problem because the
Z-buffer takes care of hidden surface removal on a per-pixel basis. However,
with semi-transparent triangles you can't use the Z-buffer (and get a
correct result).

  The only way to render correctly cyclically-occluding triangles is
to split at least one of the triangles into two parts and render these
two parts separately (in the proper order compared to the other triangles).
However, you really don't want to start splitting triangles on the fly in
a real-time rendering engine.

  It is possible to split triangles as a preprocessing step (even at the
level design stage) so that they can be ordered unambiguously. However,
using a sorting algorithm to sort the triangles at each frame is not
really something you want to do. Even if the triangles could be sorted
unambiguously by depth, the comparison is complicated and heavy, as well
as the entire sorting algorithm, which would be O(n log n).

  Step in the kd-tree.

  If you add all the semi-transparent triangles into a kd-tree, you will
be able to render the triangles from farthest to closest with a simple
O(n) traversal of the tree, regardless of where the camera is
with respect to the triangles. The comparison to be made at each node
is much simpler than the comparison which would need to be done for a
sorting algorithm.

  And that's not all. When adding triangles to the kd-tree, it's trivial
to detect cyclical occlusion situations, and perform the necessary triangle
splitting, as a preprocessing step. After this has been done, no more splits
are ever necessary, and everything can be rendered in a depth order
regardless of where the camera is (using a simple linear traversal of the
kd-tree).

  (Of course which triangles to split is not unambiguous, and algorithms
can be developed to minimize the number of triangles which need to be
split, but this is only related to the preprocessing. The rendering stays
the same.)

-- 
                                                          - Warp

Post a reply to this message