Section: Overall Objectives

Introduction

The main scientific objective of the VEGAS research team is to contribute to the development of an effective geometric computing dedicated to non-trivial geometric objects. Included among its main tasks are the study and development of new algorithms for the manipulation of geometric objects, the experimentation of algorithms, the production of high-quality software, and the application of such algorithms and implementations to research domains that deal with a large amount of geometric data, notably solid modeling and computer graphics.

Computational geometry has traditionally treated linear objects like line segments and polygons in the plane, and point sets and polytopes in three-dimensional space, occasionally (and more recently) venturing into the world of non-linear curves such as circles and ellipses. The methodological experience and the know-how accumulated over the last thirty years have been enormous.

For many applications, particularly in the fields of computer graphics and solid modeling, it is necessary to manipulate more general objects such as curves and surfaces given in either implicit or parametric form. Typically such objects are handled by approximating them by simple objects such as triangles. This approach is extremely important and it has been used in almost all of the usable software existing in industry today. It does, however, have some disadvantages. Using a tessellated form in place of its exact geometry may introduce spurious numerical errors (the famous gap between the wing and the body of the aircraft), not to mention that thousands if not hundreds of thousands of triangles could be needed to adequately represent the object. Moreover, the curved objects that we consider are not necessarily everyday three-dimensional objects, but also abstract mathematical objects that are not linear, that may live in high-dimensional space, and whose geometry we do not control. For example, the set of lines in 3D (at the core of visibility issues) that are tangent to three polyhedra span a piecewise ruled quadratic surface, and the lines tangent to a sphere correspond, in projective five-dimensional space, to the intersection of two quadratic hypersurfaces.

Effectiveness is a key word of our research project. By requiring our algorithms to be effective, we imply that the algorithms should be robust, efficient, and versatile. By robust we mean algorithms that do not crash on degenerate inputs and always output topologically consistent data. By efficient we mean algorithms that run reasonably quickly on realistic data where performance is ascertained both experimentally and theoretically. Finally, by versatile we mean algorithms that work for classes of objects that are general enough to cover realistic situations and that account for the exact geometry of the objects, in particular when they are curved.