Sabrina Kilian <"ykgp at vtSPAM.edu"> wrote:
> I like K-D trees
> because they are just binary trees with a fancy insert and delete.

  Kd-trees are quite useful for many purposes. They are, for example,
sometimes used in real-time rendering because it can be used to speed
up certain operations. For example:

  Assume that you have a very large amount of semi-transparent polygons
which you need to render. The problem with semi-transparent polygons is
that they must be rendered in back-to-front order. Rendering them in a
random order will result in an erroneous image.

  Sorting the polygons to a back-to-front order with respect to the
current camera location at each frame is too inefficient because the
triangles would first need to be transformed according to the camera
parameters and then their distance to the camera would need to be
determined somehow (which is not always something unambiguous) and
then a O(nlogn) sorting algorithm would need to be applied.

  However, this can be done much more efficiently. As a pre-processing
step all the triangles are stored in a Kd-tree. After that, each time
a new frame needs to be rendered, the Kd-tree can be relatively easily
traversed in an order which results in all the triangles being rendered
in a back-to-front order with respect to the location of the camera.
This traversal is O(n) regardless of the camera location, and it always
results in a perfect ordering of the triangles. No distances need to
be calculated and nothing needs to be sorted.

-- 
                                                          - Warp

Post a reply to this message