Graphics Reference
In-Depth Information
Aa
A
a
Ba
Ca
B
C
b
c
Bb
Bc
Cb
Cc
g
D
E
F
G
d
e
f
Db
Eb
Dc
Ec
Fb
Gb
Fc
Gc
(a)
(b)
(c)
Figure 6.9
(a) The hierarchy for one object. (b) The hierarchy for another object. (c) The
collision tree formed by an alternating traversal. The shaded area indicates a front in which
the objects are (hypothetically) found noncolliding.
Following Li and Chen [Li98], assume the front contains
n
leaf nodes and that
the collision tree is binary (implying that, for instance,“descend larger”is used as the
descent rule). In a binary tree of
n
leaves, it is easy to show the number of internal
nodes is
n
1. When a front is maintained, if the front moves down these internal
nodes correspond to the work saved in using the front as a starting point as opposed
to testing from the root.
If no front nodes move, which only happens when their parent nodes remain in
collision, at least the
n
/2 parent nodes have to be checked for collision. The total
number of nodes tested starting from the front is
n
−
3
n
/2. Again, this results
in a saving over the 2
n
nodes tested in traversing from the root.
When the front nodes move up, the number of nodes examined depends on how
many levels they move. If they move just one level, the total number of nodes
tested is therefore
n
+
n
/2
=
7
n
/4. However, in this case traversing from
the root is significantly cheaper, as only an order of
n
nodes is tested, or exactly
n
/2
+
n
/2
+
n
/4
=
1.
Given the probabilities
p
D
,
p
S
, and
p
U
— for a node to move down, stay the same,
or move up — the expected number of nodes saved by maintaining a separation
list is
+
(
n
/2
−
1)
=
n
−
s
=
p
D
n
+
p
S
(2
n
−
3
n
/2)
+
p
U
(
n
−
7
n
/4)
=
p
D
n
+
p
S
n
/2
−
p
U
3
n
/4.
Assume it is equally likely for a front node to move up, stay the same, or move down,
that is
p
D
=
p
S
=
p
U
=
1/3. The saved number of nodes is then just
s
=
n
/4, which is
not quite as effective as one might first think.
Clearly, the majority of the cost in updating the front lies in checking whether a
node is staying put or moving up in the collision tree. In addition, to be able to test
parent nodes for overlap parent pointers would have to be maintained in the data
structure holding the front.
Here Li and Chen suggest a clever alternative approach. They simply examine the
size of the front (measured in number of nodes) from one query to the next. If the
