HOME    »    PROGRAMS/ACTIVITIES    »    Annual Thematic Program
Talk Abstracts
Geometric Design

Material from Talks

Nira Dyn (School of Mathematical Sciences, Tel Aviv University, Israel)  niradyn@post.tau.ac.il

Spline Subdivision Schemes for Compact Sets

Motivated by the problem of the reconstruction of 3D objects from their 2D cross sections, we consider spline subdivision schemes operating on data consisting of compact sets. A spline subdivision scheme generates from such initial data a sequence of set-valued functions, with compact sets as images, which converges to a limit set-valued function. In the case of 2D sets, the limit set valued function, with 2D sets as images, describes a 3D object.

For the case of data consisting of convex sets, we replace addition by Minkowski sums of sets. Then the spline subdivision schemes generate limit set-valued functions which can be expressed as linear combinations of integer shifts of a B-spline, with the initial sets as coefficients. The subdivision techniques are used to conclude that these limit "set-valued spline functions" have shape preserving properties similar to those of scalar spline functions. We obtain O(h2) rate of approximation by the limit function, under mild smoothness assumptions on the set-valued function, from which the initial data is sampled.

For the case of non-convex sets we show that the limit of the spline subdivision schemes, using the Minkowski sums, is too large to be a good approximation.

To define spline subdivision schemes for general compact sets, we use the representation of spline subdivision schemes in terms of repeated averages, and replace the usual average by a binary operation between two compact sets, termed the "metric average". These schemes are shown to converge in the Hausdorff metric, and provide O(h) rate of approximation.

The results presented here, were obtained in collaboration with E. Farkhi.

Guenther Greiner (MMD IX,Computer Graphics, Computer Science, Universität Erlangen)

Parameterizing Meshes with Applications

When processing surfaces, at the very beginning one usually starts with a mesh in 3D-space. In order to process it and to do analysis on the surface, (e.g. smoothing, editing, building hierarchies, compressing) one usually has to parameterize the mesh in an appropriate way. Often the result of the analysis will depend on the parameterization and it is important to look for `good' parameterizations.

In the talk, we review several methods for parameterizing meshes, compare their performance and present several applications, e.g. texture mapping, surface fitting, remeshing, hierarchical representations.

Stefanie Hahmann (Laboratoire de Modelisation et Calcul, University of Grenoble, France)  Stefanie.Hahmann@imag.fr

Smooth Surfaces Over Arbitrary Meshes

Triangular Bezier patches are an important tool for defining smooth surfaces over arbitrary triangular meshes. The previously introduced 4-split method interpolates the vertices of a 2-manifold triangle mesh by a set of tangent plane continuous triangular Bezier patches of degree five. The resulting surface has an explicit closed form representation and is defined locally. In this talk, we introduce a new method for visually smooth interpolation of arbitrary triangle meshes based on a regular 4-split of the domain triangles. The tangent directions of the boundary curves at the mesh vertices are now completely free and the degree of the patch boundary curves is elevated to degree five. The importance of these two features is twice. First, irregular triangulations can be handled better in the sense that unwanted undulations due to flat triangles in the mesh are significantly reduced. Second, the interpolation scheme is locally refinable. We explain why the original 4-split method doesn't possess this important property.

The results presented here, were obtained in collaboration with G.-P. Bonneau.

Bernd Hamann (Co-Director and Professor, Center for Image Processing and Integrated Computing and Department of Computer Science, University of California, Davis)  hamann@cs.ucdavis.edu

Hierarchical Approaches for the Visualization of Massive Scientific Data

One of the most challenging and important problems that the science and engineering communities are facing today --- and even more so in the future --- are representing, visualizing, and interpreting very large data sets. Such data sets commonly result from computer simulations of complex physical phenomena (e.g., computational physics, climate modeling, ocean modeling) or from high-resolution imaging (e.g., satellite imaging, medical imaging). The technology currently used to represent massive data sets is inappropriate for interactive and efficient data analysis and visualization. It is impossible for a user of a visualization system to ``navigate'' through a data set consisting of several million (or billion) data points and analyze the data set entirely. In this talk, I will present various ideas that seem to be promising in the context of overcoming some of the problems associated with the visualization of very large data sets. I will emphasize the necessity to bring together approaches from approximation theory; geometric modeling (splines) and grid generation; computational geometry (tesselations); optimization (simulated annealing); and other appropriate fields. I will point out various avenues for representing massive data sets using hierarchical approaches that facilitate massive data set visualization and exploration.

Christoph M. Hoffmann (Computer Science Department, Purdue University)

Elementary Constructions in Spatial Constraint Solving

In geometric constraint solving, a useful approach is to decompose the problem into smaller subproblems, possibly recursively, and then to construct the solution from the solved subproblems. Problem decomposition is understood and some good algorithms exist that are general and effective. Moreover, for planar constraint solving, the subproblems are often quite simple.

In the case of spatial constraint solving, however, the elementary subproblems can be fairly complex, especially when they involve lines in addition to points and planes. The simplest class of such problems are the sequential constructions, in which a single geometric element is determined from constraints on known elements. We will consider such problems and discuss approaches to formulate and solve the associated equation systems.

Ravi Janardan (Department of Computer Science & Engineering University of Minnesota, Twin Cities)  janardan@cs.umn.edu http://www.cs.umn.edu/~janardan

Geometric Algorithms for Layered Manufacturing

Layered Manufacturing (LM) is an emerging technology which enables complex 3-dimensional parts to be built directly from their computer models, using a "3-dimensional printer" attached to a personal computer. In essence, the process involves orienting the model suitably, slicing it into parallel layers, and ``printing'' each layer on top of the previous one. LM is becoming increasingly important in computer-aided design and manufacturing because it provides the designer with an additional level of physical verification of the model, thereby allowing the detection and correction of flaws that may have otherwise gone unnoticed. LM is used extensively in the automotive, aerospace, and medical industries.

LM poses a number of interesting geometric problems whose efficient solution would enhance further the speed, accuracy, and utility of the process. These problems include choosing a suitable orientation of the model so as to optimize certain design criteria, generation of efficient tool-paths for printing the layers, efficient computation and location of so-called support structures, and model decomposition to minimize support requirements. In this talk, we will discuss some of these problems, describe efficient geometric algorithms for their solution, and discuss directions for further work.

(The material presented in this talk is the result of several joint research efforts with various subsets of the following group of individuals: P. Gupta, M. Hon, I. Ilinkin, E. Johnson, J. Majhi, J. Schwerdt, and M. Smid.)

Ognyan Kounchev (University of Wisconsin-Madison)

Application of Piecewise Polyharmonic Splines (Polysplines) to CAGD

The polysplines are piecewise solutions of elliptic equations, in particular they may be polyharmonic functions. Each two pieces of the polyspline match on some interface (break--surface) in a sufficiently smooth way. Even more, on the break--surface we suppose that some data--function is given, and it is proved that "interpolation polysplines" exist for a very general class of data--functions, see O. Kounchev "Multivariate Polysplines: Applications to Numerical and Wavelet Analysis", Academic Press, May 2001. This makes the polysplines a very flexible tool for CAGD since the geometry of the "control curves" may be rather general and the data may be interpolated. We assume that the data points are given on some control curves, then we join these points using one--dimensional methods, and this produces the data--functions on the interfaces which are finally interpolated by the polysplines.

Jorg Peters (Computer & Information Sciences & Engineering, University of Florida)   jorg@cise.ufl.edu

Curvature Continuous Free-Form Surfaces

A new technique for creating curvature continuous free-form surfaces of unrestricted patch layout employs patches of degree 3 by 3 (bicubics) and some patches of degree 4 by (d+2), d>0. The surfaces have the flexibility at extraordinary points of C2 splines of degree d. The construction is explained, in particular, of curvature continuous free-formsplines of degree at most 3 by 5.

Jorg Peters (Computer & Information Sciences & Engineering, University of Florida)   jorg@cise.ufl.edu

Surface Envelopes

Surface envelopes are tight, two-sided enclosures of composite spline surfaces. This talk hows how to construct the two hulls of the enclosure so that matched triangle pairs sandwich a given nonlinear, curved surface consisting of tensor-product Bézier patches. The envelope of a surface may be viewed as a low cost approximate piecewise linear implicitization with a precise and easily computed error bound.

Hartmut Prautzsch (Institut fur Betriebs-und Dialogsysteme, Universität Karlsruhe)  prau@ira.uka.de

Multi Meshes

In CAGD free form surfaces are usually represented by tangent plane or curvature continuous spline surfaces. In Computer Graphics and in applications, where speed is more a concern than accuracy, free form surfaces are often represented by triangular nets, i.e. continuous pw linear spline surfaces. In this talk we propose to use point sets only with local connectivity to reconstruct, represent and modify free form surfaces. Most operations and ideas that have been developed for triangular nets can also be used (after appropriate modifications) with our reduced representation. The quality of our results is the same as for triangular nets and moreover, our algorithms are faster and simpler.

Bahram Ravani (University of California Davis)  

Computational Line Geometry in Design and Manufacturing

This presentation develops a computational framework for designing surfaces and sculptured shapes using line geometry. Classical line geometry is reviewed and recent results in developing Bezier and B-spline type line constructs are presented. It is shown that curve type algorithms can be developed for designing surfaces with line geometry. Methods are presented that are based on both the Study representation as well as the Klein model of the line space. A De Casteljau type algorithm and a Lie Group representation are used to provide the computational framework for designing with line geometry. Applications of computational line geometry in Mesh Generation, Robotics, Numerical Control Machining, and Electric Discharge Machining are also presented.

Thomas Sederberg (Department of Computer Science, Brigham Young University)

NURCCS, Syzygy Modules, and Morph-based Compression

Since the purpose of this workshop is to discuss "the most recent research," this presentation will overview three works in progress. Non-uniform Rational Catmull-Clark Surfaces (NURCCS) generalize both cubic NURBS and Catmull-Clark surfaces. While NURCCS have non-stationary refinement rules, they nonetheless hold some economic appeal in allowing legacy NURBS models to be incorporated into a subdivision surface modeling system. A syzygy module is the set of all n-tuples of polynomials whose dot products with all elements of some other set of n-tuples of polynomials all vanish. Syzygy modules hold promise in providing a more simple algorithm for implicitization. The ability to automatically create a morph of two images can lead to an efficient way to transmit animations via the internet. We have written such a morph algorithm, and are now exploring applications to video compression.

Hans-Peter Seidel (Max-Planck-Institut for Computer Science, Saarbrücken, Germany)   hpseidel@mpi-sb.mpg.de

Efficient Processing of Large 3D Meshes

Due to their simplicity triangle meshes are often used to represent geometric surfaces. Their main drawback is the large number of triangles that are required to represent a smooth surface. This problem has been addressed by a large number of mesh simplification algorithms which reduce the number of triangles and approximate the initial mesh. Hierarchical triangle mesh representations provide access to a triangle mesh at a desired resolution, without omitting any information.

In this talk we present an infrastructure for discrete geometry processing, including algorithms for 3D reconstruction, curvature computation, mesh reduction, geometric mesh smoothing, and multiresolution editing of arbitrary unstructured tringle meshes.

In particular, we will demonstrate how mesh reduction and geometric mesh smoothing can be combined to provide a powerful and numerically efficient multiresolution smoothing and editing paradigm.

T.C. Sun (Wayne State University)

Application of The GCV method to B-spline Surface Design

This paper applies the General Cross Validation (GCV) method, used commonly in statistics, to the problem of reconstructing a free-form surface from measurement data. The GCV method is used to estimate, from the given data, the optimal smoothing parameter which is an important factor in the energy constrained least square approximation. Detailed algorithms are presented which calculate the optimal approximation surface to a prescribed error tolerance. Examples are given to show the advantages of using the GCV methods over the traditional experimental least square method with energy constraints. The GCV method is shown to be better than the experimental least square approximation in several aspects: it is optimal, it is reliable, and it is faster.

Joint work with Y. Huang.


Tamas Varady (Geometric Modeling Laboratory, Computer and Automation Research Institute, Hungarian Academy of Sciences, varady@sztaki.hu http://www.sztaki.hu/~varady   http://www.sztaki.hu/gml

Detecting Smooth Edges in Reverse Engineering

Joint work with Pal Benko.

Reverse engineering is the process of converting 3D, multiple view, measured data into an evaluated boundary representation model, which can directly be used in commercial CAD/CAM systems through standard data exchange interfaces. In this talk we concentrate on topologically complex solid models bounded by simple analytic surfaces, such as planes, cylinders, cones, spheres, tori and blending surfaces. The bounding surfaces must be accurate, their surface type and the related parameters must be reliably estimated including complex linear extrusion surfaces and surfaces of revolution as well. Smooth edges are essential in reverse engineering, these must be explicitly detected and reconstructed, otherwise not only imperfect models are generated, but the reconstruction process may crash at the intersection of nearly tangential surfaces. The so-called constrained fitting technique is based on a set of curves and surfaces, and segmented data points to be approximated. Each entity is characterized by a hypothetical curve or surface type and unknown parameters. There is a given a set of constraints (specified by the user or derived by the reverse engineering system itself), what we want to satisfy, i.e. we would like approximate simultaneously several surface elements, while the constraints are also satisfied. A new method is presented, which is computationally efficient and capable of resolving conflicts between constraints. Computational considerations of applying so-called auxiliary elements, and speeding up the computation by separating the terms holding the point data and the surface parameters will also be discussed. Constrained fitting is also suitable for enforcing a wider range of engineering constraints, such as parallelism, perpendicularity, tangency, concentricity, or symmetry amongst various geometric entities.

Joe Warren (Department of Computer Science, Rice University)  jwarren@cs.rice.edu

A Subdivision Scheme for Surfaces of Revolution

This talk will describe a new non-stationary variant of Catmull-Clark subdivision that is capable of reproducing surfaces of revolution.

Denis Zorin (Department of Computer Science, Courant Institute of Mathematical Science-NYU)  dzorin@mrl.nyu.edu

Approximate Boolean Operations on Solids Represented by Surfaces

We describe a method for computing approximate results of boolean operations (union, intersection, difference) applied to free-form solids represented by multiresolution subdivision surfaces. We present algorithms for generating a control mesh for a multiresolution surface approximating the result, optimizing the parameterization of the new surface with respect to the original surfaces and for fitting the surface defined on the new mesh to the geometry of the original surfaces.

Our algorithms aim to minimize the size and optimize the quality of the new control mesh. For approximate computations, all algorithms are quite fast as they modify the control meshes only in a neighborhood of the intersection. High accuracy approximations are also possible at additional computational expense.


Material from Talks

Geometric Design

2000-2001 Program: Mathematics in Multimedia

Connect With Us: