Orientation-based Pruning for Collision Detection

Warning: This pages are still under construction.

Introduction

Among the various strategies devised for aleviating the burden of computing interference between two polyhedral object models, orientation-based pruning has not been exploited to its full potential. Instead of using the information concerning the spatial localisation of the model's features, these approaches consider their orientations to eliminate candidates that cannot take part in a collision. The most intuitive of such approaches is back-face culling, a well-known concept in Computer Graphics adapted to collision detection. Here, the faces that are culled off are those whose normals do not project on the "interior" of the relative motion direction.

Each time the direction of relative motion changes, the set of candidate faces for intersection has to be updated. This is equivalent to the updating of volumetric hierarchies when the object's features attain new positions in space due to translations or rotations. In some cases, for example if the models are convex, such updating can be done in an incremental fashion. In the volumetric approaches, this is done exploiting spatial and temporal coherence: for small time increments, the features that realize the minimum distance (and are therefore good candidates for inminent collisions) are the same as in the previous time frame or in their neighborhood. Similarly, if the relative direction of movement changes smoothly, new faces to cull off appear (and others disappear) in the limit between previously culled and not culled ones.

As will become clear in what follows, orientation-based pruning constitutes an alternative to the more popular volumetrical focusing procedures. Furthermore, both approaches can be used together in a hibrid strategy.

Applicability constraints

Direction of motion gives an important on-line clue for restricting the faces to be considered for collision, attending to their orientation. However, it is strongly dependent on the actual relative velocities. Furthermore, these velocities have to be known or computed a priori. A velocity-independent orientation-based preprocessing of polyhedra, for enhancement of further collision checking, would be the construction of a hierarchical representation that partitions subsets of polyhedral features attending to their orientation. More on this will be considered later. Between both extremes, strategies can be devised that reduce the search space for a specific range of situations, like the present approach: here, the elimination of candidates exploits the fact that for a given relative orientation of polyhedra, only certain contacts between their boundary features can take place. Such contacts can be determined through the so-called applicability constraints (Donald, 87) .

Any contact between two polyhedra can be expressed in terms of two basic contacts:

Vertex-face contact
Edge-edge contact

When the polyhedra are convex, the applicability constraints express necessary and sufficient conditions for such basic contacts. In the case where the polyhedra exhibit concave edges, applicability is still a necessary, but no more a sufficient condition for contact. Thus, a strategy based on applicability constraints is conservative in the nonconvex case, as possible candidates are taken into account that will never contact. However, despite patological cases, a lot of pruning can be done in general.

Pruning of edge - face candidates based on applicability constraints

It is obvious that if two polyhedra collide, the first edge - face pairs that are going to intersect are associated to applicable contacts. The choice of the edge - face candidate pair, for each applicable contact, depends on the type of contact:

Vertex - face contact: the candidate pair is formed by one of the adjacent edges to the vertex and the face.
Edge - edge contact: the candidates are one of the edges and one of the adjacent faces to the other edge.

The Spherical Face Orientation Graph (SFOG, for short...)

Polyhedral features can be mapped on the spherical surface in a straightforward manner:

Faces are represented as nodes. The spherical surface is the location of all possible orientations in 3D space, and a given node corresponds to the orientation of the represented face (i.e., the outward normal of the supporting plane).
Edges are represented as arcs. A given edge is shared by two faces: correspondingly, the arc that represents it joins the nodes that stand for these two adjacent faces. These arcs lie on great circles of the sphere. Clearly, two nodes delimit two arcs on a great circle, a minor and a mayor arc. Minor arcs correspond to convex edges, mayor arcs to concave edges.
Vertices are represented by regions enclosed by a cycle of convex arcs and nodes, that correspond to adjacent edges and faces. Such regions are well defined when the vertices are convex, i.e., when all the adjacent edges are convex. Nonconvex vertices have at least one adjacent concave edge. There exists a subclass of nonconvex vertices where a pyramid can be locally defined by a subset of adjacent convex edges, such that all other edges are contained inside. This pyramid is the local convex hull of the pseudo-vertex, and the corresponding arcs define a convex subregion on the sphere.

Pairing of applicable features by means of the SFOG

By superposition of the SFOG of one polyhedron on the central symmetric image of the SFOG of the other polyhedron, a compact representation of all applicable vertex-face and edge-edge contacts is obtained:

Vertex-face:

Convex case: A given region contains a given node if and only if the corresponding vertex-face contact is applicable.
Non-convex case: A given convex subregion contains a given node if and only if the corresponding verte-face contact is locally applicable.

Edge-edge: Two arcs intersect if and only if the represented edges are applicable.

The problem of finding applicable features is reduced to that of obtaining node-region and arc-arc intersections efficiently.

The algorithms

Convex case

The amount of pruning that can be done becomes particularly evident in the convex case. Therefore, a simple algorithm has been developed and implemented for the situations where the polyhedra are known to be convex. This algorithm considers nodes of one SFOG and regions of the other one, and performs the node-in-region inclusion and the arc crossings tests. The data structures used in the algorithm are:
- input graphs:
  - the SFOGs
  - a Cycle Graph (where nodes correspond to vertices of one polyhedron)
- output vectors:
  - FACE_APP[node] recording the face-vertex applicability relationships
  - EDGE_APP[arc] recording the edge-edge applicability relationships
- processing lists:
  - OPEN_NODES
  - OPEN_ARCS
The procedure ordered_intersection (node, &EDGE_APP) finds every intersection of arcs stemming from node with the arcs of the cycle in which node lies, and appends these intersections to EGDE_APP. The arc_intersection(arc, cycle, edge) function finds the intersection between arc and the arcs of cycle different from edge, which is known to have been crossed by arc in entering cycle. The function Succ_Arcs(node) returns the arcs that ``point out of" node, in the sense that although we are exploring an undirected graph, certain directions of the arcs are implicitly imposed as some nodes are explored before others and we want to avoid exploring a given arc in both directions. The function succ_node(arc) returns the unexplored extreme node of arc, and succ_cycle(edge, arc) returns the cycle that cobounds edge and where arc is ``pointing to" (in the sense that the other cobounding cycle will either contain the node such that arc belongs to Succ_Arcs(node) or will already have an arc intersected by arc). Finally, the function last(EDGE_APP[arc]) returns the last arc intersected by arc. The algorithm starts at a given point, which can be considered without loss of generality as a ``North Pole", and travels over the sphere towards the ``South" in a spiral-like fashion. Thus, it can be considered a greedy or breadth-first algorithm \cite{Pea84}.

SFOG SEARCH ALGORITHM (convex polyhedra)}}

Choose North-pole;

Find North-region containing North-pole;

FACE_APP[North-pole]:= North-region;

North-pole -> OPEN_NODES;

while (OPEN_NODES <> Ø) or (OPEN_ARCS <> Ø)
while (OPEN_NODES <> Ø)
node <- OPEN_NODES; ordered_intersection(node, &EDGE_APP); for every a in Succ_Arcs(node)
if EDGE_APP[a] = Ø then
if FACE_APP[succ_node(a)]= Ø then
FACE_APP[succ_node(a)]:=
FACE_APP[node];
succ_node(a) -> OPEN_NODES;
endif
else
a -> OPEN_ARCS;
endif
endfor
endwhile
while (OPEN_ARCS <> Ø)
arc <- OPEN_ARCS; edge := last(EDGE_APP[arc]); cycle := succ_cycle(edge, arc); s := arc_intersection(arc, cycle, edge); if s=Ø then
if FACE_APP[succ_node(arc)] = Ø then
FACE_APP[succ_node(arc)] := cycle; succ_node(arc) -> OPEN_NODES;
endif
else
EDGE_APP[arc] <- s; arc -> OPEN_ARCS;
endif
endwhile
endwhile }

Complexity of this algorithm is linear in the output. A worst case can be found were the size of this output is quadratic, due to edge-edge applicability relationships (when the number of edges bounding a face of polyhedron P is O(n_P) and the number of edges applicable to each of them is O(n_Q)), but it is attached to a very specific geometry, where a large number of vertices are coplanar. If vertices are in general position, the number of edges applicable to the boundary of a face is bounded by a constant, and the output complexity becomes linear in the input.
Nonconvex case

Naïve algorithm

It is straightforward to adapt the plane sweep principle to the sphere: the vertical sweep-line is replaced by a sweep-meridian, the sweep begins at an arbitrary point (as we cannot speak of a ``leftmost'' point), and proceeds eastwards (as the plane sweep from left to right). As in the planar case of line segment intersection detection, two arcs will intersect at most at one point (recall that arcs larger than 180^o have been removed, since they correspond to concave edges), and monotonicity is ensured: one arc cannot intersect the sweep-meridian at more than one point simultaneously.

Each time the sweep-meridian arrives at the western endpoint of an arc a[i], this arc is tested for intersection with all the active arcs (i.e., arcs currently intersected by the sweep-meridian) of opposite colour L_c'[i]}$, and included in the list of active arcs L_c[i] (c[i] denotes the colour of a[i]). As soon as the eastern endpoint of an arc is reached, that arc is deleted from the active list. In this way, every purple intersection will be detected exactly once. A pseudo-code transcription of this simple algorithm is presented:

NAÏVE SFOG SEARCH ALGORITHM
Preprocessing: Order the 2n endpoints e[i] by increasing meridian value. Let a[i] be the arc with endpoint e[i] and c[i] its colour.
L_red = Ø,
L_blue = Ø
for (i = 1 .. 2n) do
if (e[i] is a western endpoint) then
for (all a' in L_c'[i]) do
if (a[i] intersects a') then
report purple intersection
endif
endfor
insert(a[i], L_c[i])
else
delete(a[i], L_c[i])
endif
endfor

Snapshots of this algorithm, and how the node-in-region inclusions are performed during the same sweep can be found here

Red-blue blocks algorithm

A more sophisticated approach is based on the observation that, at a given instant, red and blue arcs along the sweep line are grouped into blocks of varying size. Purple intersections can only take place between the arcs at the limits of these monochromatic groups, e.g., the lowest arc of a blue block and the highest arc of the red block immediately beneath. In other words, "interior" arcs in each block do not have to be cared for. However, these delimiting arcs change as the sweep progresses, due to the insertion of new arcs, the deletion of existing arcs, purple intersections, and also crossings between arcs of the same colour. All these events have to be taken into account for updating conveniently the blocks. BEGIN and END events are basic to the sweep process, and PURPLE events are the desired output, but the monochromatic intersections are not interesting by themselves. As their number can even outgrow that of the PURPLE events, a healthy strategy will be that of computing only those monochromatic intersections that are necessary to keep the information about the frontier arcs updated. This purpose is pursued in the HeapSweep algorithm due to Basch and Guibas (Basch et al., 96) . This algorithm has been adapted to the sweep on a spherical surface.

Pseudocode of the algorithm is given below. The overall efficiency of the algorithm depends largely on the data structures used:
- Sweep line status (active segments)
  - Kinetic queues store the arcs contained in each monochromatic block. This data structure allows quick access to the block's top and bottom arcs and efficient updating when new arcs are inserted or old ones are deleted. Kinetic queues are stored as heaters.
  - A balanced search tree T stores the top and bottom element of each block.
- Event point schedule
For clarity in the pseudocode, we highlight the node-region intersection part by using a different font color.

RED-BLUE BLOCKS ALGORITHM
Preprocessing: Order the 2n endpoints by increasing meridian value. Insert them in a priority search queue e_p_s as BEGIN and END events.
first_after_complete_turn = FALSE
while (e_p_s <> Ø)

if current meridian >= 360° and first_after_complete_turn = FALSE then
first_after_complete_turn <- TRUE;
for all active blocks do
build up list of regions
endfor
endif
Extract next event from e_p_s
case event.type of

BEGIN :
Search T to determine where s=event.arc has to be inserted.
if s is beyond the limits of T then
if the adjacent block has the same color than s then
insert s in this block,
update T

else
create new block with element s,
update T,
if current meridian >= 360° then
construct list of regions associated to this new block:
take the list of regions of the nearest same colored block,
delete from this list those regions closed by arcs in the block inbetween and
include the pole regions delimited by arcs in the block inbetween.
include event.node in these regions
endif
endif
test for PURPLE scheduling
else
if both neighbors of s in T have distinct colors then
insert s in the same colored block,
update T
test for PURPLE scheduling
if current meridian >= 360° then
include event.node in the regions associated to this same colored block
endif
else
if the neighbors' color is the same than s.color then
insert s in the block,
if current meridian >= 360° then
include event.node in the regions associated to this block
endif
else
split the existing block,
create new block with unique element s
update T
test for PURPLE scheduling
if current meridian >= 360° then
construct list of regions associated to this new block:
take the list of regions of the same colored block above,
delete from this list those regions closed by the arcs above in the splitted block
take the list of regions of the same colored block below,
delete from this list those regions closed by the arcs below in the splitted block
include the regions delimited by arcs above and below in the splitted block.
include event.node in these regions
endif
endif
endif
endif
END :
Delete s=event.arc from the corresponding block
if s was the unique element in its block then
merge the two neighbor blocks (one of them possibly NULL)
endif
else
if s was an extreme of its block then
update T
test for PURPLE scheduling with new limit
endif
endif
if current meridian >= 360° and no arc begins at event.node then
include event.node in the regions associated to the block where s belonged to.
endif

INTERNAL :
(assume that a₀ is below a₁)
rotate arc a₀ and a₁ in the block
if a₀ was the lower extreme of its block then
if a₁ was the upper extreme of its block then
update T by interchanging the two blockends
test for PURPLE scheduling with lower and upper blocks
else
update T by deleting a₀ and introducing a₁ as the new lower blockend
test for PURPLE scheduling with lower block
endif
else

if a₁ was the upper extreme of its block then
update T by deleting a₁ and introducing a₀ as the new upper blockend
test for PURPLE scheduling with upper block
endif
endif

PURPLE :
(Let the intersecting arcs be a_r and a_b)
Assign a₀ to the lower arc from both before the intersection, and a₁ to the upper one
Let regions(B₀) be the regions list associated to the block of size sz₀ containing a₀ (regions(B₁) defined analogously)
if any one of the arcs' endpoints is still in the first sweep then
Store a_r and a_b for output
endif
if sz₁ = 1 then
if sz₀ = 1 then
if T_above = NULL then
if T_below = NULL then
update T by interchanging the two (unique) blockends
if current meridian >= 360° then
Delete from regions(B₀) the region under a₁ and insert the region above (these are "polar" regions).
Delete from regions(B₁) the region above a₀ and insert the region below (these are also "polar" regions).

endif
else

insert a₁ in the block below
update T by deleting T_below and interchanging the intersecting arcs in T
if current meridian >= 360° then
Delete from regions(B₀) the region under a₁ and insert the region above (the latter is a "north pole" region).

endif
endif
else

if T_below = NULL then
insert a₀ in the block above
update T by deleting T_above and interchanging the intersecting arcs in T
if current meridian >= 360° then
Delete from regions(B₁) the region above a₀ and insert the region below (the latter is a "south pole" region).

endif
else

insert a₀ in the block above
insert a₁ in the block below
update T by deleting T_above if the size of the block above was previously greater than 1, and T_below if the size of the block below was previously greater than 1, and interchanging the intersecting arcs in T
endif

else /* sz₀ > 1 */

if T_above = NULL then
if T_below <> NULL then
delete a₀ from the block below
create new block containing a₀ (call it B₀*)
update T by interchanging the intersecting arcs in T and inserting below a₁ the arc from the block below that was previously underneath a₀ (this arc may coincide with T_below)
if current meridian >= 360° then
Create regions(B₀*) by inserting the region above a₁ plus regions(B₀) minus the region bounded above by a₁.
Delete from regions(B₁) the region above a₀ and insert the region below.

endif
endif
else

if T_below <> NULL then
delete a₀ from the block below

update T by interchanging the intersecting arcs in T, deleting T_above if the size of the block above was previously greater than 1, and inserting below a₁ the arc from the block below that was previously underneath a₀ (this arc may coincide with T_below)

if current meridian >= 360° then
Delete from regions(B₁) the region above a₀ and insert the region below.

endif
endif
endif
else /* sz₁ > 1 */
if sz₀ = 1 then
if T_above <> NULL then
if T_below = NULL then
delete a₁ from the block above
create a new block containing a₁ (call it B₁*)

update T by interchanging the intersecting arcs in T and inserting above a₀ the arc from the block above that was previously over a₁ (this arc may coincide with T_above)
if current meridian >= 360° then
Create regions(B₁*) by inserting the region underneath a₀ plus regions(B₁) minus the region bounded below by a₀.
Delete from regions(B₀) the region below a₁ and insert the region above.

endif
else

delete a₁ from the block above
insert a₁ in the block below

update T by interchanging the intersecting arcs in T, deleting T_below if the size of the block below was previously greater than 1, and inserting above a₀ the arc from the block above that was previously over a₁ (this arc may coincide with T_above)

if current meridian >= 360° then
Delete from regions(B₀) the region below a₁ and insert the region above.

endif
endif
endif
endif
else

(T_above and T_below cannot be NULL)
delete a₁ from the block above
create a new block containing a₁ (B₁*)
delete a₀ from the block below
create a new block containing a₀ (B₀*)

update T by interchanging the intersecting arcs in T, and inserting above a₀ the arc from the block above that was previously over a₁ (this arc may coincide with T_above), as well as inserting below a₁ the arc from the block below that was previously underneath a₀ (this arc may coincide with T_below)

if current meridian >= 360° then
Create regions(B₀*) by inserting the region above a₁ plus regions(B₀) minus the region bounded above by a₁.
Create regions(B₁*) by inserting the region underneath a₀ plus regions(B₁) minus the region bounded below by a₀.

endif
endif

end case

Last modified on monday, 15 April, 2002