Graphics Reference
In-Depth Information
(5,8)
3
x
- 2
y
≥
-1
4
x
+ 2
y
≤
36
(1,2)
(9,0)
x
+ 4
y
≥
9
Figure 3.16
A convex polygon can be described as the intersection of a set of (closed) half-
spaces. Here, the triangle (1, 2), (9, 0), (5, 8) is defined as the intersection of the halfspaces
x
+ 4
y
≥ 9, 4
x
+ 2
y
≤ 36, and 3
x
− 2
y
≥−1.
3.7.1
Testing Polygonal Convexity
Most intersection tests and other operations performed on polygons in a collision
detection system are faster when applied to convex rather than concave polygons, in
that simplifying assumptions can be made in the former case. Triangles are nice in
this respect, as they are the only type of polygon guaranteed to be convex. However, it
may be more efficient to perform an intersection against a single convex
n
-gon rather
than against multiple triangles covering the same area. To guarantee no concave faces
are present in the collision geometry database — which would not work with a faster
test, specially written for convex faces — all faces should be verified as convex, either
at tool time or during runtime (perhaps in a debug build).
Frequently, quadrilaterals (or
quads
, for short) are the only primitives supported
in addition to triangles. In such situations, rather than applying a generic convexity
test for arbitrary polygons, a simpler convexity test that applies specifically to quads
can be used. Assuming all vertices of the quad
ABCD
lie in the same plane, the quad
is convex if and only if its two diagonals lie fully in the interior of the quad (Figure
3.17a through c). This test is equivalent to testing if the two line segments
AC
and
BD
,
corresponding to the diagonals, intersect each other. If they do, the quad is convex.
If they do not, the quad is concave or self-intersecting. If the segments are parallel
