Graphics Reference
In-Depth Information
B
D
B
n
n
C
A
D
C
A
(a)
(b)
Figure 12.26
(a) The edge
AB
is convex, as
n
· (
D
−
A
) < 0. (b) The edge
AB
is concave, as
n
· (
D
−
A
)>0.
To determine if an edge is concave, the following approach can be used. Let
F
1
and
F
2
be the two faces meeting at an edge
E
. Then, the edge
E
is concave if some vertex
of
F
2
not on
E
lies in front of the plane through
F
1
. Specifically, for the two triangles
ABC
and
ADB
given in Figure 12.26 the edge
AB
is concave if
n
·
(
D
−
A
)
>
0, where
n
A
).
An algorithm for convex decomposition is given in [Belov02]. Cutting is dis-
cussed in [Yong00] and [Ribelles01]. The latter paper also covers hole filling. Convex
decomposition using BSP trees is discussed in [Joshi03].
=
(
B
−
A
)
×
(
C
−
12.5.4
Dealing with “Nondecomposable” Concave Geometry
As mentioned at the start of the previous section, not all concave geometry can be
feasibly decomposed into convex pieces. Consider a hemispherical bowl, modeled
with polygons. Because the inside of the bowl is concave everywhere, decomposing
the bowl into convex pieces would require cutting apart all faces of the inside the
bowl. One solution, then, is to treat the bowl geometry as a polygon soup and collide
against its boundary geometry as a collection of individual faces. This allows almost
any of the collision methods described to this point to be applied to the problem.
Unfortunately, a drawback of this solution is that volume information is lost. This
means it is no longer possible to (easily) detect if an object is positioned fully inside
the bowl geometry itself.
Another solution is to model the bowl as a CSG object. For example, a simple
CSG representation of a bowl,
D
, is the intersection of an AABB
A
and the difference
between two spheres
B
and
C
,
D
C
), as illustrated in Figure 12.27.
The collision status of an object
M
with the bowl can then be determined by the
logical code expression
=
A
∩
(
B
−
bool collides = PartiallyInside(A,M) && PartiallyInside(B,M) && PartiallyOutside(C,M);
where
PartiallyInside(X,Y)
is true if some part of
Y
lies inside
X
and
Partially
Outside(X,Y)
is true if some part of
Y
lies outside
X
. The
PartiallyInside()
