Graphics Reference
In-Depth Information
of two steps. First, a
generation
step is performed in which the object is fully covered
by a large number of spheres. Then, in a second
pruning
step any and all redundant
spheres are removed. Redundant here means that if the spheres were removed the
object would still be fully covered by the remaining spheres.
The generation part is controlled by two parameters. The first parameter,
overshoot
,
controls how far beyond the surface of the object a sphere is allowed to extend.
The second parameter,
spacing
, specifies the minimum allowable distance between
any two sphere centers. The algorithm proceeds by creating a tight uniform 3D grid
around the object. The grid cell side is set to the spacing parameter. All cells are
labeled
interior
,
exterior
,or
surface
, depending on whether they are fully inside the
object, fully outside the object, or neither. Each cell is also assigned a value, initially
zero. A sphere is then centered at every grid cell not marked exterior. Sphere radii
are set so that spheres do not extend outside object boundaries by more than the
overshoot parameter.
In the pruning step, spheres can be redundant either by being fully enclosed within
a single (larger) sphere or by being enclosed by the union of a set of two or more
spheres. In the first case, each sphere is simply compared to all other spheres to see if
it is redundant, in which case it is removed. This process requires
O
(
n
2
) sphere-sphere
comparisons. To handle the second case, the remaining set of spheres is iterated over
and for each cell fully contained within the sphere its associated value is incremented
by one. After this is done, each grid cell labeled
surface
having a value of 1 must be
contained in a single sphere. For the object to be fully enclosed, all such spheres
must be included in the final set. These spheres are identified, removed, and added to
the final set. The cell is labeled
processed
, indicating that it should not be considered
henceforth.
When all such spheres have been added to the final set, and no more cells with a
value of 1 exist, all remaining surface cells must be covered by two or more spheres.
Conversely, each remaining sphere must be fully enclosed by two or more spheres.
Thus, any sphere can be deleted from the candidate set while still maintaining full
object coverage. As the sphere is deleted, the grid cells contained by it are decremented
by one. Whenever this results in a grid cell with value 1, the corresponding sphere is
added to the final set in the same way as before. Processing stops when no candidate
spheres are remaining or, if desired, simply when all surface cells have been marked
processed. Even though their algorithm does not proceed to build a hierarchy from
the final sphere set, any of the previously described hierarchy construction methods
could now be applied with the spheres as the input set to produce a sphere tree, if
needed.
6.4.6
k
-DOP Trees
In [Klosowski98]
k
-DOP trees were used for detection collisions between a flying
object and a large static environment. Using top-down construction, they bound
the input set of triangles in a
k
-DOP and then partition the input set in two parts,
recursing over the parts. The recursion is stopped when the nodes contain a preset
