Graphics Reference
In-Depth Information
lines. A second problem is that some loops may be missed entirely if the grid is not
fine enough. This problem often occurs near critical points of z(u,v), such as saddle
points, or other singularities because the data may not have a unique interpretation.
In Figure 13.9(b) there are three possible intersection curves that give rise to the same
labeling of grid vertices with the sign of their z
ij
values.
[Faro87] describes an algebraic geometry approach to finding sections of bicubic
patches. See also [ChaK87]. Another surface section algorithm is a special case of the
general surface intersection algorithm described in [GraK97].
The problem of finding sections has a converse, namely to describe a surface
given a collection of sections for it. This is
skinning
problem and will be discussed
in Section 14.7.
13.5
Surface-Surface Intersections
General surface intersection algorithms are particularly important in geometric
modeling, such as in the boundary evaluation algorithm of CSG and NC cutter path
generation. Unfortunately, finding such intersections is a very difficult problem and
no algorithm that is both efficient
and
correct is known at the moment. Efficient algo-
rithms have problems near singularities or almost-singularities because computers
only have finite precision. Accurate and robust algorithms are currently too slow.
Some are based on algebraic geometry methods that do not apply to nonalgebraic sur-
faces. Others try to use interval arithmetic ([HMPY97]). Pratt and Geisow ([PraG86])
give a good survey of some older known intersection algorithms. [Fari92b] contains
a list of references on the topic of intersection algorithms.
First of all, finding the intersection of two faceted surfaces reduces to finding the
intersection of two facets in 3-space. This in turn reduces to finding the intersection
of a convex polygon with a plane and then finding the intersection of a segment with
a convex polygon. The mathematics behind doing this was discussed in Section 6.5.
If only one of the surfaces is faceted and the other is smooth, one can reduce this
problem to finding sections of the smooth surface and finding the intersection of two
curves in these sections. This leaves the problem of finding the intersection of two
smooth surfaces.
Like in the curve case, one approach to finding intersections of smooth surfaces
that one might think of almost immediately is to approximate them by faceted sur-
faces and then use methods for intersecting those types of surfaces. The usual problem
is deciding when an approximation is good enough. [Grif75] and [Grif78] used this
approach to display parametric surfaces. [HaAG83] starts off with coarse faceted
approximations whose intersecting facets are then subdivided further appropriately.
[RosR86] used meshes of isoparametric curves. [Turn88] used a two-surface bound-
ing volume that generalized his curve intersection approach described earlier in
Section 13.3.2. After finding points close to the intersection, a Newton-Raphson
method was used to actually find points on it.
Rather than solving the smooth surface intersection problem by reducing it to the
faceted case it is better to deal with it directly. The special case of quadric surface
intersections has been studied extensively. See, for example, [FaNO89] and [Pieg92]
