Graphics Reference
In-Depth Information
c
c
1
c
2
n
n
±
e
(a)
(b)
Figure 12.13
(a) The normal
n
hits cell
c
(dashed) on the top face of the cube inscribed in
the unit sphere. (b) The perturbed normal
n
±
e
hits cells
c
1
and
c
2
. The contents of these
cells must be tested for co-planarity with the polygon having the normal
n
.
Each polygon normal can be seen as describing a position of the surface of the
unit sphere. Let a cube be inscribed in the unit sphere, each cube face divided into a
number of cells of a fixed uniform size. Each polygon normal will intersect some cube
face cell (Figure 12.13a). Let polygons be associated with the face cell their normals
intersect.
Near co-planar polygons will now largely map to the same cell, allowing them to
be further processed after their co-planarity has been verified. However, due to the
arbitrary discretization into cells, two plane normals arbitrarily close may still end up
in different cells. A simple solution to this problem is to test all eight neighboring
face cells of the cell the polygon normal intersected. Some care must be taken near
the cube edges to make sure the correct cells are visited.
To cut down on the number of neighboring cells to test, the polygon normal
n
can
be perturbed slightly in the plane of the intersected face, giving a rectangular region
in the face, describing the area for which normals would be considered coplanar to
n
. All cells overlapped by the rectangular region would then be tested, similar to
before (Figure 12.13b). Typically, the number of cells overlapped by this region would
be smaller than eight. Again, care must be taken to visit the correct cells when the
rectangular region extends over a cube edge.
The presented method has an expected complexity of
O
(
n
). An alternative but
less efficient
O
(
n
log
n
) tree-based sorting method is given in [Salesin92]. Alterna-
tive solutions to the problem of merging (near) co-planar faces are presented in
[Hinker93] and [Kalvin96].
12.4.1
Testing Co-planarity of Two Polygons
One approach to testing if two polygons are co-planar is to compute the angle
between their plane normals. If the angle is less than some given tolerance, the
