The dual parametric and implicit representations are central in algorithms for low degree (typically 1 or 2) algebraic surfaces. Although available in the theory, exact implicit representations of sculptured CAD-type surfaces are not useful, as they are computationally too expensive. This is due to the high degrees and the exploding number of coefficients. Since the advent of approximate implicitization, new methods are within reach. The FET assessment project verified that self-intersection algorithms work with approximate implicits of total degree as low as 4. Intersection algorithms are the most complex part of 3D CAD kernels, and the source of many problems in advanced CAD-model exchange and use. Approximate implicitization opened a bridge to algebraic geometry. By combining results from different branches of mathematics we plan to investigate the use of approximate algebraic geometry in surface intersection algorithms.

Objectives

The project combines knowledge from Computer Aided Geometric Design (CAGD) and classical algebraic geometry to improve intersection algorithms for Computer Aided Design (CAD) types system.

The focus within the project is on:

·         Exact and approximate implicitization

·         Classification and identification of singularities

·         Recursive subdivision based intersection algorithms

·         Industrial testing

 

We want to improve intersection algorithms in CAD by integrating approximate algebraic geometry and state-of-the art approaches, and further, to understand better approximate implicitization with respect to limitations and possibilities of different polynomial degrees, choice of polynomial bases and other aspects. To improve the use the algebraic surfaces our aim is to integrate knowledge from real & classical algebraic geometry into the CAD-domain. We intend to find better methods for approximating intersection tracks, investigate other uses for algebraic geometry, and combine knowledge from CAD, approximation theory and classical algebraic geometry. Our project will span the whole chain from basic research to industrial prototyping.

Description of work

• Singularities: Classification, detection and localization. The partners believe that Computer Aided Geometric Design will benefit from algebraic geometry. We will address both real and classical algebraic geometry for better understanding of intersection problems and identifying results that can improve intersection algorithms.
• Representation: Different methods for finding algebraic representations exist. We will look in more detail into the resultant type, further investigate approximate m ethods and address piecewise algebraic methods. Topics of special interest are approximation with parameterizable implicit curves/ surfaces and classes of algebraic surfaces governed by a small numbers of parameters.
• Intersection: As the main objective is intersection algorithms, we will address how the approximate algebraic approach complements state-of-the-art methods, and develop a prototype integration. More accurate methods and compact representations for intersection tracks will also be in focus. The results will be demonstrated in an industrial prototype.
• Applications: The assessment project resulted in a number of open issues that will be addressed. Some applications have already been identified, such as detection of loops on curves and ray tracing for graphics; others are foreseen. We feel that when a complex geometric constellation arises, a local approximate algebraic geometry is a tool to get more insight and sort out the solution.

As the project will benefit from industrial feedback from a larger industrial audience, the GAIA users club will invite industrial companies interested in influencing new CAD-type technology.

Milestones and expected results

• July 2002: Kick-off.
• December 2004: (Midterm): Established improved fundament for surface intersection and document a number of technological improvements in 3D technology outside CAD. Documented use of substantial knowledge from real and classical algebraic geometry. 10 papers published and two patents under work.
• September 2005 (End): Demonstrated and verified feasibility of results from Month 18. 10 additional papers published and two additional patents under work.

GAIA II - Project Information and Partners

Full title: Intersection algorithms for geometry based IT-applications using approximate algebraic methods.

Project Acronym: GAIA II

Contract number: IST-2001-35512

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

Coordinator: Tor Dokken, SINTEF ICT, Department of Applied Mathematics SINTEF. e-mail tor.dokken "at" sintef.no

Project partners:

• SINTEF ICT, Department of Applied Mathematics, Norway
• Johannes Kepler University, Austria
• University of Nice Sophia Antipolis, France
• University of Cantabria, Spain
• think3 SPA, Italy and France
• University of Oslo, Norway