Page 11 - Geometric Modeling and Algebraic Geometry

1

The GAIA Project on Intersection and Implicitization

Tor Dokken

SINTEF ICT, Department of Mathematics
tor.dokken@sintef.no

Summary. In the GAIA-project we have combined knowledge from Computer Aided Geo-
metric Design (CAGD), classical algebraic geometry and real symbolic computing to improve
intersection algorithms for Computer Aided Design (CAD) systems. The focus has been on:
• Singular and near singular intersections of surfaces, where the surfaces are parallel or near
parallel along segments of the intersection curves.
• Self-intersection of surfaces to facilitate trimming of self-intersecting surfaces.
The project has published more than 50 papers. Software toolkits from the project are available
for downloading under the GNU GPL license.

1.1 Introduction

In the GAIA project we have combined knowledge from Computer Aided Geomet-
ric Design (CAGD), classical algebraic geometry and real symbolic computing to
improve intersection algorithms for CAD-type systems. The calculation of the inter-
section between curves or surfaces can seem mathematically simple. This is true for
the intersection of e.g. two straight lines when they intersect transversally and closed
expressions for finding the intersection are used. However, if floating point arithmetic
is used, care has to be taken to properly handle situations when the lines are parallel
or near parallel. The intersection of two bi-cubic parametric surfaces can be reduced
to finding the real zero set of a polynomial equation f(s, t)=0 of bi-degree (54,54),
which by itself is a challenging problem. In industrial systems floating point arith-
metic is used, thus introducing rounding errors. In CAD system there are tolerances
defining when two points are to be regarded as the same point. This has also to be
taken into consideration in CAD-related intersection algorithms. The consequence
of low quality intersection algorithms in CAD-systems is low quality CAD-models.
Low quality CAD-models impose high costs on the product creation processes in
industry.
The objectives of the GAIA project were related both to the scientific and tech-
nological aspects: