Main navigation | Main content
HOME » PROGRAMS/ACTIVITIES » Annual Thematic Program
Geometric Design
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.frSmooth 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.eduHierarchical 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/~janardanGeometric 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.
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.
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.
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.
A
Subdivision Scheme for Surfaces of Revolution 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.
|
|
|
|
|