Proposed WP2 projects:

• Algebraic spline geometry
• Procedural surfaces and point represented surfaces
• Algebraic tools for geometric constructions

Geometric modelling usually involves piecewise algebraic representations of shapes. Their effective treatment leads to the resolution of polynomial systems of equations, which requires the use of stable and efficient tools. A major challenge in this direction is to combine accuracy, robustness and efficiency.  Very recent improvements of the so-called elimination techniques in computational algebraic geometry (mainly computation of resultants, generalized normal forms and subdivision techniques) open a new window of applications of Algebraic Geometry to CAD.

Resultants provide a very compact way for characterizing when a polynomial system of equations has a solution and, in many cases, for describing the solutions if they are finite. They are based on matrix formulations, which allow for instance to project a problem in high dimensions onto a univariate problem. Systems that are relevant to CAD applications are studied, such as multi-homogeneous systems, so as to exploit their structure and obtain compact matrices. New ideas around the use of moving curves and surfaces, and residual resultants open up a wider applicability of these algebraic techniques in practice.

Computer Algebra proposes to exploit the properties of the quotient algebra modulo the equations to be solved, in order to compute the roots. Classical approaches such as Gröbner bases, which are not stable, can be replaced by the very recently developed generalized normal form methods.

Subdivision solvers form a third family of algebraic tools, which are very interesting in geometric computing. They provide methods to localize roots in a bounded domain, and have witnessed important progress lately, both on the algorithmic and the implementation level.  They can be used as filters in many geometric operations, such as for instance detecting characteristic points on a shape, also providing certified approximations of the solutions of polynomial systems. Exploiting the properties of the Bernstein basis representation, they lead to efficient solvers. Analyzing and optimizing their performances in terms of the characteristics of the input systems is a current research activity, requiring the investigation of new criteria to detect isolated or multiple roots.

Results of the GAIA II project show that all these new algebraic techniques, properly specialized to solve geometric problems (such as computing singular points, self-intersections or intersection points on curves or surfaces) can seriously improve accuracy, robustness and efficiency. The real applicability and impact in practice of these improvements is still under study since, as it has already been mentioned above, the exact implicit equation of a curve or surface may not be usable in practice. Still it provides, through its resultant formulation or by using the generalized normal forms, a way of reducing any intersection problem for such a geometric object to a purely numerical linear algebra problem involving the computation of eigenvalues, generalized eigenvalues or singular values. This constitutes one concrete example of what is called an Algebraic Solver, where the right combination of algebraic and geometrical tools, together with numerical linear algebra techniques, provides more robust, efficient and accurate algorithms for polynomial system solving coming from CAD.

The libraries SYNAPS and the algebraic-geometric modeller AXEL provide a first (and complete) framework to check the potential of this approach on problems arising from real-world situations in CAD.

All the current approximations to CAD from algebraic geometry rely on mathematical foundations based on the use of complex numbers and projective geometry while, in practice, all the considered practical questions are presented over the real numbers and in an affine setting. This obvious remark implies the need of analyzing, from the point of view of Real Algebraic Geometry, the consideration of curves, surfaces and volumes as semialgebraic sets (i.e. sets defined by means of polynomial equalities and inequalities), together with their manipulation techniques such as quantifier elimination algorithms. The role of semialgebraic sets as a way of detecting and eliminating geometric extraneous components in implicitization has already been described and quantifier elimination has been used to generate closed form formulae for solving the interference problem for conics and quadrics.

A related problem concerns the Voronoi diagram of curved objects, which is central in space partitioning and collision detection. Using the above results on the interference problem for conics, the case of ellipses has been studied from the algebraic viewpoint. For efficiency, the latter is combined with an iterative scheme that uses numerical, though certified, computation and solves, at any desired accuracy, the problem for arbitrary smooth closed curves.