IST-1999-29010

Key Action/Action line: FET-Open, IST VI.1.1

http://www.math.sintef.no/gaia/

Web-page of full FET-project following GAIA

Conference presentations of GAIA results

• Presentation at ECITTT in Cambridge UK, 29 March - 1 April 2001 of "Approximate Implicitization"

• Presentation at SNSC'01 in Linz Austria, 12 September - 14 September 2001 of "Approximate Implicitization and self-intersection"

• Executive summery of GAIA final report

Surface with singularity/collapse resulting from filleting

The recent introduction of approximate algebraic methods is a possible bridge between classical algebraic geometry, and the needs for better intersection algorithms within Computer Aided Geometric Design (CAGD). Parametric and algebraic descriptions are easy to combine and give good computational efficiency for conic sections, cylinders, spheres and cones. For surfaces of total degree higher than two the relationship between parametric and algebraic representations is more complex. Thus in CAGD parametric representations are normally chosen and NURBS (NonUniform Rational B-Spines) dominate. The process of finding an exact algebraic description for NURBS surfaces is computationally expensive, results in algebraic surfaces of high degree (for a bi-cubic NURBS surface the algebraic degree is 18) and requires exact arithmetic. Thus exact implicitization is not used in CAGD. However, the algebraic representation of a surface is well suited for classifying artifacts in surface behavior such as self-intersections and singularities. Classification of artifacts based on classical algebraic geometry with an investigation into the degree needed to reveal such artifacts is essential to assess the feasibility of approximate algebraic methods in CAGD.

The project will evaluate to what extent approximate algebraic methods can improve intersection algorithms and detection of artifacts such as singularities and self-intersections in surfaces.

• Document and disseminate the characteristics of approximate implicitization:

• Use of floating point arithmetic.
• Use of algebraic surfaces with low degree (degree 3, 4 or 5).
• Approximate implicitization of piecewise polynomials.
• High convergence rates.

• Combine several mathematical domains that can be seen as complementary in the assessment: Algebraic geometry; Approximation theory; Geometric modeling (CAGD).
• Perform case studies on intersections and self-intersections of curves and surfaces. We will compare approximate algebraic methods with sampling based methods.
• If the GAIA results are promising for industrial use, we plan to submit a FET RTD-project proposal based on GAIA.

Self-intersection as result of making an offset surface

The project will focus on intersection and self-intersection of surfaces using approximative algebraic techniques. Most surfaces in CAGD are built from curves. In surface intersection algorithms curves are often extracted from surfaces. Thus intersection of curves and self-intersection of curves will also to be addressed.

We will develop a prototype toolbox with methods based on approximate implicitization, in addition a sampling based reference method will be implemented. The methods are to be tested on industrial examples, and they should treat the following cases:

1. Ordinary intersections. The objective is to decide whether two geometrical objects intersect within a given tolerance or not. The problem is as follows: given two parametric surfaces, we will detect possible intersections by approximating one of them by an implicit surface, and combine this with the parametric description of the other surface.
2. "Near-intersections". Methods to detect cases when two objects intersect clearly in one point, but there are ambiguities in the surrounding area (tangency or higher order contact).
3. Self-intersections and singularities. We will investigate how singularities in surfaces are reproduced in the approximate algebraic surface. If singularities are reproduced then classification of singularities can be based on results from classical algebraic geometry. However, if singularities are not properly reproduced then the difference in behavior between the parametric and approximate algebraic surface is a tool for singularity detection.

The main work of GAIA is:

Classification of singularities in algebraic curves and surfaces

Approximate implicitization based intersection and selfintersection software components

Development of sampling based reference method

Validation of numerical algorithms, and extensive testing on industrial examples