Graphics Reference
In-Depth Information
Three types of BSP trees were described: node-storing, leaf-storing, and solid-leaf
BSP trees. Recursive top-down construction of these trees was discussed, along with
how to select and score dividing planes to form good trees.
For BSP trees (and similar structures), it is important to consider the robustness of
inserting primitives and performing queries on the tree, to ensure that both primitives
and queries end up in all nodes they overlap. It was shown how thick planes help in
this respect, and both classification and clipping of polygons to a thick plane were
described.
Point and ray queries were used to illustrate the basic recursive approach to per-
forming BSP tree queries. Last, it was shown how polytope queries can be facilitated
on BSP trees through the process of adding beveling planes and offsetting the divid-
ing planes at query time to form an expanded tree. The expanded tree effectively
forms the Minkowski sum of the polytope and the original BSP tree and therefore
enables a simple ray query on the tree to substitute as the polytope query.
