Graphics Reference
In-Depth Information
sliver polygons and T-junctions. Clipping also generates extra vertices, and thus not
clipping saves memory as well. The drawback of not clipping is that it may now be
important to make sure the intersection with a polygon takes place inside the volume
of the leaf and not with the part of the polygon that lies outside the leaf volume.
Without this test, a near-to-far traversal of the BSP tree could not be guaranteed to
find the nearest point of intersection for a ray intersection test.
Most BSP tree presentations and resources on polygon clipping do not cover the
use of thick planes for robustness. A notable exception is [Chin92], in discussion on
robust polygon clipping.
8.3.5
More on Polygon Splitting Robustness
Although the previous section presented a thorough description of how to split a
single polygon in a robust manner, there is one remaining issue that arises when
clipping a shared edge of two neighboring polygons. Consider the two triangles
ABC
and
CBD
of Figure 8.15a, both with their vertices given in counterclockwise order.
Splitting these triangles against the plane clips the shared edge
BC
twice: once for
each triangle. There is a subtle yet crucial point here: the edge is defined as
BC
for
triangle
ABC
and as
CB
for triangle
CBD
. Due to the differences between floating-
point arithmetic and real arithmetic, intersecting
BC
against a plane
P
does not, in
general, result in the same intersection point as intersecting
CB
with the same plane.
Naive clipping code, which moves around the boundaries of the two triangles and
clips the edges as they are encountered, will therefore introduce cracks between the
two neighboring triangles (as the computed intersection points differ subtly).
Figure 8.15b illustrates the problem case. For triangle
ABC
, edges
BC
and
CA
are
clipped against the plane.
BC
intersects the plane at
F
BC
. For triangle
CBD
, edges
A
A
A
E
E
F
BC
C
C
C
B
B
B
F
CB
F
BC
G
G
D
D
D
(a)
(b)
(c)
Figure 8.15
(a) Original geometry of two triangles intersecting a plane. (b) Inconsistent han-
dling of the shared edge results in two different intersection points, which introduces cracking.
(c) The correct result when the shared edge is handled consistently.
