Effective computing with low-degree curved objects

Curved geometric objects, such as real algebraic curves and surfaces, are important in geometric computing as they arise naturally in many problems in computer sciences, mathematics, physics and chemistry. We work on the design and implementation of exact and efficient algorithms for manipulating such primitives.

Intersections of quadrics

The Voronoi Diagram of Three Lines

Arrangements of quadrics

Boundary evaluation of quadric-based solids

Topology of real algebraic plane curves

Algebraic tools for geometric computing

Algebraic invariants

Shape approximation by lower-degree objects

Parameterization of intersections of quadrics: theory, algorithms and implementation

We present the first exact, robust, practical and efficient algorithm, and its implementation, for computing a parametric form of the intersection of two arbitrary quadrics (degree-two algebraic surfaces, e.g., ellipsoids, paraboloids, hyperboloids, etc.) with rational coefficients. Our method is similar in spirit to the general method introduced by J. Levin in 1976 for computing an explicit representation of the intersection of two quadrics, but extends it in several directions. Combining results from the theory of quadratic forms, linear algebra and number theory, we show how to obtain parametric intersection curves that are both `simple' (the size of the coefficients is small) and `as rational as possible'. Our contributions are mainly three-fold:
  1. we present the first classification of pairs of quadrics based on the type of their intersection in real projective space, thus refining over the reals the classification in complex space by Segre in 1883;
  2. based on this classification, we present the first practical algorithm that correctly identifies and parameterizes the intersection in all cases;
  3. the parameterization is essentially as simple as possible. We also produced a C++ implementation of this algorithm, QI, which is, up to our knowledge, the only existing solution for computing exactly a parameterization of the intersection of two quadrics.

More on the subject
Online C++ implementation

The Voronoi Diagram of Three Lines

The faces of Voronoi diagrams or medial axes of polyhedra in 3D consist of quadric patches, and the edges of quadric intersection arcs. For computing such structures efficiently, we first need to understand their properties in particular, for the case of lines. We have obtained some fundamental results in that direction, proving, in particular, that the topology of the Voronoi diagram of three lines in general position is invariant. The proof relies on the characterization of real pencils of quadrics of (Lien vers la page) and introduces a new proof technique which relies upon modern tools of computer algebra (for computing Groebner bases). We also obtained the first complete characterization of the Voronoi diagram of three lines in arbitrary positions. We proved that the trisector consists of arcs that are always monotonic in a particular direction. These results also yield a new algorithm, fundamental for handling robustness issues, for sorting points (candidate vertices) along the arcs of Voronoi diagrams of lines using only rational linear tests (for lines with rational coefficients).

Arrangements of quadrics and Boundary evaluation of quadric-based solids

Arrangements of quadrics
Towards the computation of the 3D arrangement we achieved a major milestone, namely the computation of the edge-adjacency graph, that is, we compute all vertices of the arrangement and their connectivity. As input we can deal with arbitrary rational quadrics, that is, quadrics defined by polynomials in Q[x,y,z]. The implementation is complete in the sense that it can handle all cases, in particular, it can handle configurations that involve tangential or singular intersections.
Boundary evaluation of quadric-based solids
Few approaches have been proposed for exactly computing the boundary representation (BRep) of a solid defined as unions and intersections of elementary solids (CSG) delimited by quadrics. Furthermore, all of them assume that the objects considered are in generic position, therefore bypassing the all-important issue of degeneracies. Using our algorithm for parameterizing the intersections of two projective quadrics as a building block, we have presented an algorithm for exactly and robustly extracting the surface patches appearing on the BRep and giving an explicit representation of their borders.
This problem has many applications other than the boundary evaluation of quadric-based solids. For instance, problems such as computing the convex hull of a set of quadric patches or computing one cell of the Voronoi diagram of polyhedra can be solved by computing the boundary of a quadric-based solid.

Topology of real algebraic plane curves: Isotop

We address the problem of computing the topology and geometry of a real algebraic plane curve. The topology is of prime interest but geometric information, such as the position of singular and critical points, is also relevant. This problem is important as it permits to plot such curves in a certified way, that is without missing branches or missing self-intersections. It is also mandatory for computing arrangements of such curves. Previous methods based on the cylindrical algebraic decomposition use sub-resultant sequences and computations with polynomials with algebraic coefficients. A novelty of our approach is to replace these tools by Groebner basis computations and isolation with rational univariate representations. This has the advantage of avoiding computations with polynomials with algebraic coefficients, even in non-generic positions, and avoiding costly back-and-force shearing of the coordinate system in non-generic configurations. We also present an analysis of the complexity of our algorithm. An implementation of our algorithm, called Isotop (for isotopy), demonstrates its efficiency, in particular on high-degree non-generic curves.

Algebraic tools for geometric computing

In computational geometry, many problems lead to standard, though difficult, algebraic questions such as computing the real roots of a system of equations, computing the sign of a polynomial at the roots of a system, or determining the dimension of a set of solutions. This work goes toward making state-of-the-art algebraic software more accessible to the computational geometry community, in particular, through the computational geometric library CGAL. We proposed a model of the Univariate Algebraic Kernel concept for algebraic computations.

Constant-complexity geometric problems and algebraic invariants

We have revisited some standard constant-complexity geometric problems having in view to better understand the design of the underlying geometric predicates. For that, we mostly rely on classical tools, in particular algebraic invariant theory, which was perceived as a bridge between geometry and algebra by the mathematicians of the 19th century (culminating with Klein's Erlangen Program, and the view of geometry as the study of the properties of a space invariant under the action of a group of transformations). In 2008, we studied the relative position of two plane projective conics and showed that it can be characterized by predicates of bidegree at most (6,6) in the coefficients of the input conics, improving upon previous results. By relative position we mean the morphology of the intersection, the rigid isotopy class and which conic is inside the other when applicable. Analyzing the algebraic invariant theory of pencils of conics, we constructed a special conic -- called a combinant -- invariantly attached to a given pencil and showed how the projective type of this combinant, encoded by its inertia, is characteristic of the intersection type of the two conics in most cases. However, the problem was treated purely algebraically and the results have no obvious geometric meaning: why such inertia is characteristic of such intersection pattern is obscure. In 2009, we reproved essentially the same results, but using an entirely new approach which has the benefit of making perfectly clear the geometric meaning of the inertia of the combinant conic and overall bringing substantial geometric insight to the problem. The key intermediate tool we use that illuminates this interpretation is the Bezoutian. We are working on extending these results to other primitives. We also approached the design of predicates with a different view, through a formulation as an arrangement of hypersurfaces.

Shape approximation by lower-degree objects

We also worked on the problem of approximating complex shapes by lower-degree objects, with the idea that a simple intermediate representation has great potential for dealing with curved objects. We studied the approximation of smooth curves by tangent continuous conic splines, giving tight bounds on the complexity of the approximation by a conic spline with respect to the Hausdorff metric; this work was published in 2007 in the journal Mathematics in Computer Science. In 2010, we have started working on extensions of this result with a view to better grasp the complexity of the approximation, study the complexity of approximation by other types of primitives (conic biarcs for instance) and bound the time complexity of algorithms computing optimal approximants.