Go up to Top
Go forward to Progress Reports

Introduction and Motivation

 

ntroduction

Computer Aided Geometric Design (CAGD) and Visualization are concerned with the approximation and representation of curves and surfaces that arise when these objects have to be processed by computer. They play an important role not only in the construction of such varied products as car bodies, ship hulls, airplane fuselages and wings, propeller blades, shoe insole, bottles, etc., but also in the description of geological, physical and even medical phenomena (see [18],[20],[21],[22], [23]).

A practical implementation has to balance two conflicting goals: efficiency and reliability. Roughly speaking, the algorithms must not be subject to failure and must find all the parts of the algebraic set. On the other hand, algorithms must be efficient enough so that interaction between a CAGD user and a CAGD system can be achieved. Typically, a numerical algorithm is efficient, but it is not reliable and may fail in certain cases, especially in areas near the singularities. On the other hand, algorithms based on exact arithmetic are reliable, but are normally slow and require a lot of memory space.

In spite of much effort, no present algorithm satisfies all those two main goals (see [22],[24],[25], [26]). Perhaps the goals of efficiency and reliability cannot be met simultaneously without some compromises. We propose to negotiate those compromises judiciously. That means that, we will tackle the problems by a hybrid symbolic-numerical approach and develop algorithms which should fit those three main goals.

We restrict attention to algebraic curves and surfaces. This restriction is reasonable in the sense that the class is very rich and includes most of the curves and surfaces used in, for instance, engineering design. In particular, this class includes all the major parametric surfaces used in geometric modeling, including Bezier surfaces, nonuniform rational B-spline (NURBS), and so on (see [22],[15],[19],[14], [17],[16],[13]). It does not include all space curves and surfaces, however. For example, the helix is not an algebraic space curve. In previous projects we have developed the system CASA for pure Symbolic Computation on algebraic curves and surfaces (see [28],[27]).

To support our goals, we would like to use new techniques, for example: combination of symbolic-numerical methods, parallel computation, multi-precision floating point arithmetic, multivariate resultants, Gröbner Basis with respect to the product term ordering, etc., in our research. Such techniques are not ready-to-use in any suitable system.

Therefore, together with the theoretical research, we also propose a project work which is directed towards designing software. The software - called HySaX (Hybrid Software for Algebraic Geometry in X-windows environment) - will aim at the implementation of hybrid symbolic-numerical algorithms for approximation and representation of algebraic sets in two and three dimensions. The software will be built as an enhancement of the traditional and widely used computer algebra system Maple. Therefore it can be benefited from a large number of already known algorithms which has been implemented in the library/share-library of Maple. Especially, it will succeed the CASA system, a computer algebra system for constructive algebraic geometry, which has been developed by the Computer Algebra group of RISC-Linz.

 

otivation

The three main goals of efficiency, robustness, and accuracy for algorithms in CAGD have not been attained. There is an agreement that the problem is serious, but what strategy has the best chance of solving it is not agree on. The difficulty seems to be rooted in the intersection of approximate numerical and exact symbolic data.
alggeo@risc.uni-linz.ac.at

Up Next