Implicit Polynomial Surface Fitting and Tessellation

The extraction of information from 3D data is often difficult as it involves processing huge volumes of data. A generic model fitted to data sets can dramatically ease the required processing and simplify several 3D problems. In computer vision, objects in 3D images are mostly described by their surfaces; ellipsoids, quadric surfaces, and super-quadrics are used as surface models. In essence, these surfaces are special forms of the more generic implicit algebraic surfaces. In this project, 3D object representation based on implicit algebraic surfaces is investigated. Fundamental to the usefulness of this representation is the intelligent fitting of algebraic surfaces to 3D data sets, which is a challenge solved by extending the 3L fitting algorithm for 2D curves to 3D. Our goal is to show that implicit algebraic surfaces become a viable 3D shape representation alternative with the new efficient 3D fitting technique.

In applications beyond object recognition, the 3D shape representation methodology developed appears to be ideally suited to object representation for computer graphics purposes. To this end, we combine the developed fitting algorithm with an adaptive surface-following triangulation technique. This combination is particularly effective for modeling both unorganized point sets and freeform (organic) surfaces. The breadth-first tessellation algorithm requires the evaluation of the implicit algebraic function itself and the gradient, and performs these operations only locally near the surface. The resultis a flexible method of visualizing a given surface, both bounded and unbounded, using a single global representation or several piecewise-continuous surface patches.

Last updated: June 3, 1998

Back to research topics.