Graphics Reference
In-Depth Information
Given a set of objects, it is now straightforward to implement a collision-filtering
algorithm in terms of a number of repeated tests to see if an object from the set is
fully visible with respect to the other objects. If so, this object is discarded as not
intersecting any objects. Tests are repeated until no more objects can be discarded
in this manner. Upon exit, the remaining set of objects — the
potentially colliding set
(PCS) — contains the objects that may be in collision. At this point, further pairwise
tests can determine which exact objects of the set are intersecting, if desired.
Let
S
be a set of
n
objects. Testing whether object
O
i
is fully
visible with respect to the rest of the objects,
O
1
,
O
2
,
...
,
O
i
−
1
,
O
i
+
1
,
...
,
O
n
, can be
performed for all objects at once, using a simple two-pass approach in which objects
are rendered and simultaneously tested for full visibility. In the first pass the objects
are rendered and tested one by one in the order
O
1
,
O
2
,
...
,
O
n
. The fully visible status
of each object is recorded. In the second pass, the objects are rendered and tested in
the reverse order,
O
n
,
O
n
−
1
,
...
,
O
1
, and their status is again recorded. Now, for each
object
O
i
if
O
i
is found fully visible with respect to
O
1
,
O
2
,
...
,
O
i
−
1
on the first pass
and fully visible with respect to
O
n
,
O
n
−
1
,
...
,
O
i
+
1
on the second pass
O
i
is fully visible
with respect to all other objects and therefore cannot be in collision. Thus, any object
that was marked fully visible in both passes can be safely removed from the PCS.
Additionally, if all of the last
r
rendered objects,
O
r
,
O
r
+
1
,
...
,
O
n
, have been marked
fully visible during the first pass (or all of the last
s
rendered objects,
O
s
,
O
s
−
1
,
...
,
O
1
,
during the second pass), they too can be removed from the PCS. The “fully visible”
test for object
O
i
during each pass can be implemented in terms of an occlusion query
as follows.
={
O
1
,
O
2
,
...
,
O
n
}
1. Disable depth buffer writes.
2. Enable depth testing, with pixels passing if their depth is greater than current
value.
3. Perform an occlusion query on object
O
i
.
4. Enable depth buffer writes.
5. Set depth test to less-than or equal.
6. Render object
O
i
.
7. Get the result from the occlusion query. If no pixels passed the test, flag object
O
i
as fully visible during this pass.
These steps are repeated for all
n
objects. The test assumes the depth buffer is
initially set to
Z
-far.
In a scene with
n
nonintersecting objects stacked
n
deep, the two-pass filtering
algorithm is able to mark only the frontmost object as fully visible, leaving the remain-
ing
n
1 objects in the PCS. It thus takes
n
repetitions to mark all objects as fully
visible and to reduce the PCS to empty. The overall algorithm performance is there-
fore linearly dependent on the depth complexity of the scene. Because scenes rarely
−
