Extended Convex Differences Tree
Saturday, July 20, 2002

Introduction

Back in 2000 I hit upon an idea for reducing the complexity of collision detection. The idea was based on a few observations:

The smoother a concavity is, the more convex polyhedra will be required to represent it in a convex decomposition

By treating concavities as inverse convexities and creating a CSG tree we can reduce the number of convex polyhedra required to decompose a concave object. Ray-tracers have used CSG trees to optimize for years, but I'm not aware of anyone CSG trees for collision detection. As it turns out, this method has been described in the literature already [1], but I think it's been given a short shrift.

Observations

Figure 1 illustrates a taxonomy of objects with various "indentations" which make them concave. Objects 1 and 2 have only convex indentations, and thus their negative spaces don't need to be decomposed into convex partitions. Object 3, however, has a concave indentation which must be decomposed into convex parts. Notice how the positive objects require more partitions to decompose them than the negative parts in objects 1 and 2. The opposite is true for object 3. Thus, the more concave an object is, the more complex its decomposition, and the simpler the decomposition of its corresponding negative object. We can exploit this symmetry by introducing the CSG "difference" operator into our representation of the decomposition.

Figure 1: 1-3.(a) original object, (b) convex decomposition of positive space, (c) convex decomposition of negative space. Object 4 illustrates the necessity of partitioning concave edges

From studying these diagrams, we can begin to formulate a theory about the relationship between the convexity and concavity of the positive and negative spaces.

There's another interesting observation that may be helpful as a heuristic: when doing convex decomposition of a concave object, we'll need to generate a convex object for every edge segment along each concave edge of the object. Why is this the case? (Examine object 4 in figure 1). Proof by contradiction: assume we use a concave edge of the object as part of a component in its decomposition. But then we can draw a line between two points in the object such that the line intersects the boundary of the figure, meaning that the object isn't convex. Thus, we must always "partition" each concave edge along its segments such that the resulting partitions are no longer concave.

Connections to Skeletonization

I haven't studied it in any great detail, but I've got an intuition that the more complex the set of (simplified approximate) medial axes of a polyhedron, the more complex its convex decomposition. I'll report any results I obtain after boning up on medial axes and skeletonization later.

Applications to Collision Detection

We regularly do interference tests using the convex hull before testing against the polyhedra of the convex decomposition. Using the structure described above, the convex hull test is an integral part of the entire collision detection phase, which yields even greater efficiency due to the two-for-one savings this implies.

References