Effective Computational Geometry for Curves and Surfaces

Shared-cost RTD (FET Open) Project No IST-2000-26473

Results

This project is focused on effectively handling curved objects.

Objectives

Description of work

Geometric algorithms for curves and surfaces. We intend to revisit the field of Computational Geometry in order to understand how structures that are well-known for linear objects behave when defined on curves and surfaces.

Algebraic issues. Several operations on nonlinear geometric objects, often lying at the algorithm's bottleneck, are equivalent to manipulating polynomials. A fundamental question is the solution of algebraic systems, ubiquitous in the construction of new objects, such as intersections. Another crucial goal is the implementation of primitives with Boolean or discrete output, such as an object is contained in some bounding object.

Robustness issues. Geometric programs are notorious for their non-robustness: algorithms are designed for a model of computation where real numbers are dealt with exactly and geometric algorithms are frequently only formulated for inputs in general position. This is not simply an academic problem. It is easy to crash any commercial CAD-system. Progress has been made only in recent years. A significant part of the progress was made by the proposers and centers around the so-called exact computation paradigm. We will extend this paradigm to curved objects.

Approximating curves and surfaces. Since algorithms for curves and surfaces are more involved, more difficult to make robust and typically several orders of magnitude slower than their linear counterparts, there is a need for approximate representations. Our objective is to provide robust and quality guaranteed approximations of curves and surfaces.

Milestones and expected results

Participating sites

Support

Total cost: 1 595 600 EUR Community funding: 1 029 000 EUR Project start: May 1st 2001 Duration: 36 months

IST home FET Home

Coordinator contact details