Warp wrote:
>   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.

Ah yes, the "painter's algorithm".

Incidentally, while playing CSS the game engine appears to very 
occasionally get this wrong. (I.e., distant objects appear *in front* of 
nearer ones - typically textures for things like explosions, window 
glass, etc.) The result looks very weird.

>   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).

Presumably if the triangles are allowed to move around you can't 
precompute the splits?

Post a reply to this message