Page 15 - Geometric Modeling and Algebraic Geometry

1 The GAIA Project 9
However, if the faces are sculptured surfaces, e.g., bicubic NURBS - NonUniform
Rational B-splines, the edges will in general be free form space curves with no sim-
ple closed mathematical description. As the tradition (and standard) within CAD is
to represent such curves as NURBS curves, approximation of edge geometry with
NURBS curves is necessary. For more information on the challenges of CAD-type
intersections consult [54].
When designing within a CAD-system, point equality tolerances are defined that
determine when two points should be regarded as the same. A typical value for such
tolerances is 10 −3 mm, however, some systems use tolerances as small as 10 −6 mm.
The smaller this tolerance is, the higher the quality of the CAD-model will be. Ap-
proximating the edge geometry with e.g., cubic spline interpolation that has fourth
order convergence using a tolerance of 10 −6 instead 10 −3 will typically increase the
amount of data necessary for representing the edge approximation by a factor be-
tween 5 and 6. Often the spatial extent of the CAD-models is around 1 meter. Using
an approximation tolerance of 10 −3 mm is thus an error of 10 −6 relative to the spatial
extent of the model.
The intersection functionality of a CAD-system must be able to recognise the
topology of a model in the system. This implies that intersections between two faces
that are limited by the same edge must be found. The complexity of finding an inter-
section depends on relative behaviour of the surfaces intersected along the intersec-
tion curve:

• Transversal intersections are intersection curves where the normals of the two
surfaces intersected are well separated along the intersection curve. It is fairly
simple to identify and localise the branches of the intersection when we only
have transversal intersection.
• Singular and near singular intersections take place when the normals of the
two surfaces intersected are parallel or near parallel in single points or along in-
tervals of an intersection curve. In these cases the identification of the intersection
branches is a major challenge.

Figures 1.1 and 1.2 respectively show transversal and near-singular intersection
situations. In Figure 1.1 there is one unique intersection curve. The two surfaces in
Figure 1.2 do not really intersect, there is a distance of 10 −7 between the surfaces,
but they are expected to be regarded as intersecting. To be able to find this curve,
the point equality tolerance of the CAD-system must be considered. The intersection
problem then becomes: Given two sculptured surface f(u, v) and g(s, t), find all
points where |f(u, v) − g(s, t)| <ε where ε is the point equality tolerance.

1.4.1 The algebraic complexity of intersections

The simplest example of an intersection of two curves in IR is the intersection of
2
two straight lines. Let two straight lines be given:
• A straight line represented as a parametric curve