Proposed WP1 projects:

• Sparse approximate implicitization
• Approximate and exact parameterization
• Interpolation of curves by surfaces

These research problems are related to methods for the conversion between the two main representations of curves and surfaces, the implicit and the parametric form. While parametric representations are interesting to generate points, implicit representations encompass a larger class of shapes and are more powerful for geometric queries. The exact conversion procedures, implicitization and parameterization, have been studied in classical algebraic geometry and in symbolic computation, but their practical application in CAD is rather limited, due to the feasibility reasons outlined earlier. Approximate techniques have emerged recently, and their practical value has been demonstrated in the GAIA II project.

The discussion of these techniques from a theoretical point of view has just begun, and it can be expected to lead to a better theoretical understanding of the possibilities and the limitations of the new methods. The singular value decomposition used in approximate implicitization is linked to a certain condition number, which may help to study the numerical robustness of the implicitization process. It is one of the aims to continue the theoretical analysis of these methods, both for parameterization and implicitization.  

Another important issue, which should be addressed, is the improvement of the existing algorithms for approximate implicitization. On one hand, improved algorithms should allow for an adaptive control of the number of degrees of freedom, similar to the concept of multiresolution. Such techniques have been explored in a previous research training network MINGLE (Multiresolution in Geometric Modelling, 2000 – 2004), which was also coordinated by SINTEF. As a challenging problem, we plan to look into wavelet-type techniques for implicitly defined curves and surfaces in order to combine the multiresolution approach with approximate algebraic geometry.

This work can be coupled with methods for predicting the support of the implicit equation, by exploiting, at the same time, the structure and the sparseness of the parametric expressions.

We also plan to investigate other applications of the powerful techniques for approximate implicitization, which have emerged recently. We will study problems such as 3D object reconstruction, registration of 3D objects, robust footpoint computation, fast high-quality rendering, and many others.

Computational techniques for approximate parameterization have not received much attention so far, and should be studied in more detail. Both conversion processes also need special methods for dealing with singularities. For instance, singularities may occur during the process of detecting self-intersections, and their reproduction by approximate implicitization techniques is therefore highly desirable.

As a more theoretical question, we plan to look into so-called universal parameterizations. These are rational mappings, which allow generating rational patches on certain special classes of algebraic surfaces. They are related to representation formulas of the solutions to the corresponding equation in unique factorization domains. Recently similar formulas, which are valid in the subclass of principal ideal domains, have emerged. We will analyze these results from a geometric point of view and discuss related applications.