Graphics Reference
In-Depth Information
C
K
BL
J
D
A
G
FH
E
I
(a)
A,G
D
1
D
2
J
1
B,C,D
1
,J
1
,K,L
G
A
J
2
D
2
,E,F,H,I,J
2
(b)
A,G
B
B
H
C,D
1
J
1
,K,L
D
2
,E,F
I,J
2
H
I
(c)
Figure 8.3
(a) The original 12-polygon input geometry. (b) The initial dividing plane is selected
to pass through face
A
(and face
G
). (c) For the next ply of the tree dividing planes are selected
to pass through faces
B
and
H
.
suffer from having to test unnecessary polygons when traversing a dividing plane.
Collision queries on leaf-storing trees perform tests on all polygons contained in the
leaves overlapped by the query object. Tests on the tree may exit early if a collision is
detected.
The dividing planes of leaf-storing trees can be either general or autopartitioning.
Regardless of which, any eventual faces coplanar with the selected dividing plane are
not stored in the node but sent down either the front or back side child tree. When
autopartitioning, all faces coplanar with a selected dividing plane should be marked
so as to exclude them from consideration when selecting future dividing planes. If
they are not excluded, theoretically a dividing plane could be reselected further down
the tree, which does not make sense.
The construction of a leaf-storing tree is shown in Figure 8.4. Using arbi-
trary partitioning, the initially selected dividing plane divides the input set in half.
