Page 21 - Geometric Modeling and Algebraic Geometry

1 The GAIA Project 15
Approach Comment Addressed in GAIA II
Triangulation Will both miss branches and pro- See section 1.7.1 on the Reference
duce false branches Method
Lattice Will miss branches Used in many CAD-systems.
evaluation Not addressed in GAIA II
Recursive Guarantees topology within speci- See section 1.7.2 addressing the com-
fied tolerances bination of recursion and approximate
implicitization
Exact Guarantees topology however will The AXEL library see Section 1.7.3
not always work
Combined Guarantees topology however will Uses Sturm Harbicht sequences for
exact & not always work, faster than the ex- topology of algebraic curves, see Sec-
numeric act methods tion 1.7.4
Table 1.1. Different CAD-intersection methods and their properties.

1.6.2 Approximate implicitization of rational parametric surfaces

Two main approaches have been pursued in the project.
• Approximate implicitization by factorization is a numerically stable method
that reformulates implicitization to finding the smaller singular values of a ma-
trix of real numbers. See one of [17, 21] for an introduction. The approach can
be used as an exact implicitization method if the proper degree is chosen for the
unknown implicit and exact arithmetic is used. The approach has high conver-
gence rates and is numerical stable. Strategies for selecting solutions with a de-
sired gradient behavior are supplied, either for encouraging vanishing gradients
or avoiding vanishing gradients. The approach works both for rational paramet-
ric curves and surfaces, and for procedural surfaces. Experiments with piecewise
algebraic curves and surfaces have produced implicit curves and surfaces that
have more vanishing gradients than is desirable. We have experienced that esti-
mating gradients will improve this situation. We have established a connection
between the original approach to approximate implicitization, and a numerical
integration based method that can also be used for procedural surfaces, and a
sampling/interpolation based approach [22].
• Approximate implicitization by point sampling and normal estimates is con-
structive in nature as it estimates gradients of the implicit representation to ensure
that gradients do not vanish when not desired [1, 2, 3, 11, 13, 36, 37, 38, 40, 50,
51, 52]. The approach produce good implicit curves and surfaces and the problem
of vanish gradients in not desired regions is minimal. The method works well for
approximation by piecewise implicit curves and surfaces.
The work within GAIA has illustrated the feasibility of approximate implicitiza-
tion, established both new methods on approximate implicitization with respect to
theory and practical use of approximate implicitization. It has also been important to
compare the different approaches to approximate implicitization [59].