Graphics Reference
In-Depth Information
threshold
t
of triangles. For the static hierarchy they used
t
=
1, and for the flying
40. Query traversal was such that the environment was fully descended
into before the object was descended.
Four different partitioning strategies were compared for the construction of the
k
-DOP trees. The choice of axis was limited to one of the
x
,
y
,or
z
coordinate axes
based on the criteria of minimizing the sum of volumes, minimizing the maximum
volume, using the axis with the largest variance, and splitting along the longest axis of
the parent volume. The mean and the median of the axis-projected triangle centroid
coordinates were both used to determine the splitting point.
Their results showed that splitting at the mean always produced a hierarchy with
a smaller total volume than splitting at the median. The “minimize sum” strategy
consistently produced the smallest total volume hierarchy, with“minimize maximum,”
“largest variance,” and “longest axis” producing results roughly 7%, 10%, and 33%
worse, respectively. They also examined using more than the three coordinate axes,
specifically all
k
/2 defining directions for the
k
-DOPs, reporting it not really providing
an improvement. Preprocessing time increased by about 30% on average, however.
To tumble the
k
-DOPs during updating, they used the more expensive hill-climbing
method for the root node, as it and nearby nodes are most frequently visited. The
approximate DOP-of-DOP method was used for all other nodes because of the
(much) lower overhead.
Also working with
k
-DOPs, [Konecný98] instead uses the axis of largest variance
among the set of
k
/2 fixed-direction axes for the
k
-DOPs (measured over the projected
centroids). He then partitions the primitives in two sets of equal size.
[Klosowski98] compared 6-, 14-, 18-, and 26-DOPs and found 18-DOPs perform-
ing the best. As a contrast, [Zachmann98] compared 6-, 8-, and 14-DOPs, finding
6-DOPs (that is, AABBs) performing better than the other two. In a later work, using
the nonstandard
k
-DOPs described in Chapter 4, Zachmann reports examining the
full range
k
object
t
=
24 performed
best overall [Zachmann00]. As these tests were performed under varying conditions,
it is difficult to compare the results directly.
Using doubles (8 bytes) for vertex components and 4-byte integers for triangle
vector indices, Klosowski et al. report they require (16
k
=[
6
...
32
]
. Although no
k
was optimal in all tests,
k
=
108)
n
bytes to store all
n
triangles of the environment, including the hierarchy itself. For
k
+
6, 14, 18, and
26 this becomes 204, 332, 396, and 524 bytes per input triangle, respectively. This
should be compared to the 412 bytes per input triangle claimed for the OBB-based
collision detection package RAPID (also using doubles). What is worse, for a data set
of 169,944 triangles they report a 26-DOP hierarchy being an obscene 69 MB in size!
=
6.5
Merging Bounding Volumes
When hierarchies are created top-down or incrementally, bounding volumes
are typically created from scratch using the dimensions of the contained data.
