March 30, 2004
BibTeX references.
Fausto Bernardini, Chandrajit L. Bajaj,
Jindong Chen & Daniel R. Schikore
International Journal of Computational Geometry and Applications (IJCGA),
v.9, n.4&5, Aug.-Oct. 1999, pp.327-370.
On-line files.
NB: Outcome of Fausto's PhD thesis at the Department of Computer Sciences, Purdue University, December 1996.
Main Contributions:
Not done (yet):
[O'Rourke81]: Convex hull shrunk iterartively to yield a polyhedra of minimal surface area. Not guaranteed to converge onto the true minimal surface. Restricted to genus 0 object.
[Boissonnat84]: Local method (surface) based on iterative k-nearest neighbors search. Global method (volumetric) based on the Delaunay tetrahedralization, followed by "sculpturing" (iterative removal of tetrehedron). The sequence used in sculpturing is not robust: different sequences may lead to different end-results. Several geometric measures can be used to decide if a tetrahedron is to be removed. Boissonnat suggests: max distance between tet faces and associated circumsphere.
[Choi88]: Start with a triangle from a point with total visibility (all other surface points are "visible" or in a cone of light rays) and incrementally build the triangulation. Edge swapping is then used a posteriori to smooth the resulting mesh.
[Veltkamp92]: Introduces the gamma-graph wich encompasses many well-known graphs such as the Euclidean minimum spanning tree, the Delaunay triangulation, the convex hul and the Gabriel graph. Start with convex hull and constrict (tets having boundary faces are removed), until the boundary of the gamma-graph is a closed surface passing through all given points.
[Hoppe92-96]: Fits tangent planes to data using k-nearest neighbors. Connect points (using a minimum spanning tree) which have nearly parallel planes. Compute a signed distance map. Use marching cube. Optimize the mesh a posteriori.
[Levoy94-96]: Combine separate 3D scans: co-resgister these; build a triangle mesh for each; compute the contribution to a global signed-distance map (function of the view direction of the sensor, weighted by the angle with the surface normal); followed by marching cube. Holes need to filled-in; computationally expensive.
[Edelsbrunner83-94]: Alpha-shapes. Consider a ball of radius alpha and use it to erase simplices if it can go through these: i.e., small enough simplices "escape" the eraser and represent the alpha-shape. Vary alpha from infinity (convex hull) to zero (cloud of points). An alpha-shape is in general a non-connected, non-regular polytope. Weights can be assigned to points to capture levels of details (in the sampling).
[Bajaj95]: Use alpha-shapes to define an approximate signed distance function, followed by a piecewise algebraic surface fitting.
[Schmitt86]: Input points organized on a rectangular grid are adaptively fitted using Bernstein-Bezier parametric bi-cubic patches to form a G^1 continuous surface (differentiable w/r to arc length but not necessarily w/r to their actual parametrization)
[Moore91]: Fit algebraic surfaces to scattered dense data. Use least-squares and "auxiliary data" (approximation of signed distance; to avoid extraneous parts).
[Hoppe94]: Minimize an energy function trading off conciseness and accuracy of fit, starting from a triangular mesh. Capable of representing sharp features (creases and corners).
[Eck96]: Tensor-product B-spline patches, starting from [Hoppe92-96] (above).
[Bajaj95]: Fit C^1 smooth implicit algebraic patches starting from an initial piecewise-linear approximation.
[Besl95]: Builds polynomial surfaces based on region growing..
[Terzopoulos88]: snakes.
[Pentland91]: Finite element.
Power distance (see [Boehm94]).
Any polynomial of degree n can be expressed as a BB-form over a tetrahedron.
A class of piecewise implicit surface with weights such that singularities and multiple sheets are avoided.
Two problems needs to resolved with A-patches:
[ TOP ]
Gerald Farin,
Josef Hoschek & Myung-Soo Kim editors
848 pages, Elsevier Science (North Holland)
ISBN: 0444511040
Chapter 1: A History of Curves and Surfaces in CAGD (G. Farin).
Chapter 2: Geometric Fundamentals (W. Boehm, H.
Prautzsch). 
Chapter 3: Geometries for CAGD (H. Pottmann, S. Leopoldseder).
Chapter 4: Bezier Techniques (D. Hansford).
Chapter 5: Rational Techniques (H.J. Wolters).
Chapter 6: Spline Basics (C. de Boor).
Chapter 7: Curve and Surface Constructions (D. Hansford, G. Farin).
Chapter 8: Geometric Continuity (J. Peters).
Chapter 9: Splines on Surfaces (M. Neamtu).
Chapter 10: Box Splines (H.
Prautzsch, W. Boehm).
Chapter 11: Finite Element Approximation with Splines (K. Hoellig).
Chapter 12: Subdivision Surfaces (M. Sabin).
Chapter 13: Interrogation of Subdivision Surfaces (M. Sabin).
Chapter 14: Multiresolution Techniques (L. Kobbelt).
Chapter 15: Algebraic Methods for Computer Aided Geometric Design (T.W. Sederberg, J. Zheng).
Chapter 16: Scattered Data Interpolation: Radial Basis and Other Methods (S.K. Lodha, R. Franke).
Chapter 17: Pythagorean-Hodograph Curves (R.T. Farouki),
pp. 405-427. 
Chapter 18: Voronoi Diagrams (K. Sugihara).
Chapter 19: The Medial Axis Transform (H. I. Choi, C. Y. Han).
Chapter 20: Solid Modeling (V. Shapiro).
Chapter 21: Parametric Modeling (C. M. Hoffmann, R. Joan-Arinyo).
Chapter 22: Sculptured Surface NC Machining (B. K. Choi, B. H. Kim, R. B. Jerard).
Chapter 23: Cyclides (W. Degen).
Chapter 24: Geometry Processing (T. A. Grandine).
Chapter 25: Intersection Problems (N. M. Patrikalakis, T. Maekawa), pp. 623-650.
Chapter 26: Reverse Engineering (T. Varady, R. Martin).
Chapter 27: Vector and Tensor Field Visualization (G. Scheuermann, H. Hagen).
Chapter 28: Splines over Triangulations (H-P Seidel, F. Zeilfelder).
Chapter 29: Kinematics and Animation (B. Juettler, M. G. Wagner).
Chapter 30: Direct Rendering of Freeform Surfaces (G. Elber).
Chapter 31: Modeling and Processing with Quadric Surfaces (W. Wang).
by Gerald Farin
5th edition, 2002.
4th edition, 1997.
Published by Academic Press Ltd., 1997.
Web link (C programs, ToC, Errata)
[ TOP ]
Christoph M Hoffmann and Robert Joan-Arinyo
Computer-aided Design, Vol. 30 (5), pp. 321-332,
April 1998.
Feature-based design is becoming one of the fundamental design paradigms of CAD systems. In this paradigm, the basic unit is a feature and parts are constructed by a sequence of feature attachment operations. The type and number of possible features involved depend upon product type, the application reasoning process and the level of abstraction. Therefore to provide CAD systems with a basic mechanism to define features that fit the end-user needs seems more appropriate than trying to provide a large repertoire of features covering every possible application.
A procedural mechanism is proposed for generating and deploying user-defined features in a feature-based design paradigm. The usefulness of the mechanism relies on two functional capabilities. First the shape and size of the user-defined features are instantiated according to parameter values given by the end-user. Second the end-user positions and orients the feature in the part being designed by means of geometric gestures on geometric references.
Keyword(s): computer-aided design; feature-based design; user-defined features; parametric design.
Christoph M. Hoffmann and Jaroslaw R. Rossignac
IEEE Transactions on Visualization
and Computer Graphics , Vol. 2, No. 1, March 1996
C. Hoffmann is with the Computer Science Department, at Purdue University, West Lafayette, IN 47907. E-mail: cmh@cs.purdue.edu.
The objective of solid modeling is to represent, manipulate, and reason about, the three-dimensional shape of solid physical objects, by computer. Such representations should be unambiguous.
Solid modeling is an application-oriented field that began in earnest in the early 1970s. Major application areas include design, manufacturing, computer vision, graphics, and virtual reality. Technically, the field draws on diverse sources including numerical analysis, symbolic algebraic computation, approximation theory, applied mathematics, point set topology, algebraic geometry, computational geometry, and data bases.
In this road map article, we begin with some mathematical foundations of the field. We review next the major representation schemata of solids. Then, major layers of abstraction in a typical solid modeling system are characterized: The lowest level of abstraction comprises a substratum of basic service algorithms. At an intermediate level of abstraction there are algorithms for larger, more conceptual operations. Finally, a yet higher level of abstraction presents to the user a functional view that is typically targeted towards solid design. Here, we will look at some applications and at user interaction concepts.
The classical design paradigms of Solid Modeling concentrated on obtaining one specific final shape. Those paradigms are becoming supplanted by feature-based, constraint-based design paradigms that are oriented more toward the design process and define classes of shape instances. These new paradigms venture into territory that has yet to be explored systematically. Concurrent with this paradigm shift, there is also a shift in the system architecture towards modularized confederations of plug-compatible functional components. We explore these trends lightly in the last section.
Index Terms : Solid modeling, solid representations, conversion between solid representations, feature-based design, constraint-based design.
[ TOP ]
Christoph M. Hoffmann and
Jorg Peters
in Mathematical Methods for Curves and Surfaces, M.Daehken, T.Lyche
& L.L.Schumaker ed.,
Vanderbilt University Press, pp. 237-253, 1995.
To enrich the shape vocabulary of mechanical CAD systems, we develop techniques that allow defining free-form curves from geometric constraints. An important aspect of this approach is the ability to obtain all possible instances of curve segments satisfying the constraints of a dimensioned sketch. We illustrate the approach by treating constraints on Tschirnhausen cubics in some detail.
June 4 -- 9, 1995, Oberwolfach, Germany.
The mathematical research institute in Oberwolfach, a small town in Southern Germany, is renowned world-wide for high-quality international research meetings. The meetings typically run for a week and the participants live together on the premises in an isolated valley in the Schwarzwald. Traditionally, there is no fixed program, and the next day's talks are scheduled the evening before.
The conference brought together some 60 researchers in CAGD (Computer-Aided Geometric Design) from around the world. It was organized by R. Barnhill (Arizona State University), J. Hoschek (Technical University of Darmstadt, Germany) and W. Boehm (Technical University of Braunschweig, Germany). The talks presented a cross-section of major research trends in CAGD and previewed emerging research directions. Instead of summarizing the 42 talks given during the week, I will characterize the major themes they articulated. Those themes were:
In addition to the research presentations, two talks commemorated the work of the late John Gregory (Brunel University, UK).
One objective of CAGD is to design pleasing shapes. When approximating or interpolating scattered data, a ``fair'' curve or surface is to be found. What constitutes fairness is in part a mathematical notion and in part an aesthetic concept whose particulars would depend on the application. For instance, in ship building, fairness of the hull surface may depend primarily on flow characteristics. In automotive applications, on the other hand, fairness of the car body would also emphasize visual and aesthetic aspects that may relate to the way lines of light are reflected.
Of the many algorithms in the literature dealing with fairness of shape, the energy-based variational approach is currently receiving much attention. Roughly speaking, an integral of the curve or surface is to be minimized. The integral might constitute an approximate measure of the bending energy inherent in the shape. Fairing algorithms using this approach solve a variational mathematical problem, for example using the finite element method. One of the benefits of the approach is the ability to express functional constraints such as drag in a viscous fluid, or geometric constraints such as conforming, at specific localities, to a given sculptured surface.
Wavelets have emerged as an important tool in image compression. Conceptually, a function over a domain (e.g., the image pixel values of the screen grid) is approximated by a hierarchy of function spaces. Each function space successively refines the previous one, and concurrently a refinement of discrete domains takes place. The refinement is subject to technical conditions. In turn, this permits a graded representation of an image ranging from a very coarse image representation to a very detailed one. Because of the refinement notion, a transmitted image comes up fast and coarse. As the transmission continues, more and more detail appears until the fully detailed image is displayed.
Emerging applications in CAGD include radiosity computations, a very sophisticated rendering technique, and hierarchical shape approximation and detailing. The second application is still not understood very well and presents foundational mathematical problems that remain to be worked out. Note that this application would also impact data reduction and conversion, a practical issue arising when transmitting design data between CAD systems using different spline representations of curved surfaces.
A polygonal curve can be made ``smoother'' by systematically cutting all corners. For example, subdivide the segments adjacent to a corner and replace the corner by the segment connecting the two subdivision points nearest to the old corner. Iterating this process results in the limit in a curve, and this research asks what curves are so obtained. Similar cutting processes can be devised for polyhedra in space, yielding curved surfaces in the limit.
By its nature, corner cutting is a process that could yield fractal objects in the limit. The main research questions, therefore, include: Does a particular subdivision scheme yield a smooth curve or surface? If so, how smooth is the result (i.e., how many times is the curve or surface continuously differentiable)? What classes of subdivision schemata have a desired smoothness behavior? In current CAGD research, corner cutting is used to fill irregular holes in quilts of sculptured surfaces subject to continuity requirements at the boundaries. Other uses attempt to devise blending algorithms for solids with sculptured surfaces.
A parametric curve or surface has the Pythagorean hodograph (ph) property if its offsets are again parametric curves or surfaces. Usually, parametric curves and surfaces do not have the ph property. Trivial examples of ph curves and surfaces include straight lines and planes, and circles and spheres.
The rediscovery of several interesting, nontrivial ph curves and surfaces has stimulated this research in recent years. Current problems worked on include devising interpolation algorithms that use only piecewise ph curves, designing ph curves from geometric constraints, and designing with ph curves and surfaces. This research elegantly extends classical geometry work on cyclographic maps and Laguerre transforms that reformulate the problem of finding such curves and surfaces as an equivalent, simpler problem in a higher dimensional curved space. Research is coming close to finding practical interpolation and design algorithms for ph curves, but the corresponding problems for surfaces are largely open at this time. A property of practical interest is that the arc length of ph curves can be computed exactly, and this may impact NC path generation.
These diverse subjects are related by the fact that they employ techniques from symbolic algebraic computation and algebraic geometry. Geometric constraint solving is about solving systems of algebraic equations. By judiciously restricting the problem and exploiting the geometric nature of the objects manipulated, very efficient algorithms can be obtained that have a strong impact on engineering design and analysis.
Implicitization of parametric curves and surfaces is a test case for symbolic algebraic computations. Current research seeks to generalize some techniques originally developed at the beginning of this century. The technology is sophisticated, but its impact on practice appears to be limited.
The geometry of implicit algebraic surfaces is investigated in the hope of finding a rich class of such surfaces that can be used in free-form design. Currently, free-form design is done almost exclusively with parametric curves and surfaces. Implicit surfaces are advocated by some researcher as an alternative.
When approximating or interpolating data points with a piecewise parametric curve or surface, the data points are assigned specific parametric coordinates. This is done to convert the problem from a nonlinear problem to a linear one, and is a crucial first step to achieve fast and practical algorithms. However, the assignment of parametric coordinates affects the shape of the approximation or interpolation, and so a variety of heuristics have been proposed in the literature to make good coordinate assignments in a variety of situations.
Reparameterization makes the process iterative: First, assign parametric coordinate and compute a surface. Then, based on the geometry of the surface and the relative location of the data points, assign new parametric coordinates to the points and repeat. For example, a natural requirement would be to have parametric coordinates such that a data point with parametric coordinates u,v is on a line perpendicular to the approximating surface C at the corresponding point C(u,v). Current research explores this and other techniques to change the parametric coordinates of data points.
[ TOP ]
Morgan-Kaufmann, San Mateo, CA, 1989. 338 pages.
[ TOP ]
Tamás Várady, Ralph R Martin & Jordan Cox
Computer-Aided
Design, Vol. 29 (4) pp. 255-268, April 1997.
In many areas of industry, it is desirable to create geometric models of existing objects for which no such model is available. This paper reviews the process of reverse engineering of shapes. After identifying the purpose of reverse engineering and the main application areas, the most important algorithmic steps are outlined and various reconstruction strategies are presented. Pros and cons of various data acquisition techniques are described with related problems of boundary representation model construction. Specific issues addressed include characterization of geometric models and related surface representations, segmentation and surface fitting for simple and free-form shapes, multiple view combination and creating consistent and accurate B-rep models. The limitations of currently known solutions are also described, and we point out areas in which further work is required before reverse engineering of shape becomes a practical, widely-available engineering tool.
Keywords : CAD; geometric modelling; reverse engineering; scanning; segmentation; surface fitting; boundary models.
The shape model representation is fundamental as it determines the computational algorithms applied to the data sets.
[ TOP ]
Atul Sudhalkar, Levent Gürsöz & Friedrich
Prinz
Computer-Aided
Design, Vol. 28 (6-7) pp. 507-517, June 1996.
The Medial Axis Transform (MAT) was defined by Blum in the 1960s as an alternate description of the shape of an object. Since then, its potential applicability in a wide range of engineering domains has been acknowledged. However, this potential has never quite been realized, except recently in two dimensions. One reason is the difficulty in defining algorithms for finding the MAT, especially in three dimensions. Another reason is the lack of incentive for modelling designs directly in MATs. Given this impasse, some lateral thinking appears to be in order. Perhaps the MAT per se is not the only skeleton which can be used. Are there other, more easily derived skeletons, which share those properties of the MAT which are of interest in engineering design?In this work, we identify a set of properties of the MAT which, we argue, are of primary interest. Briefly, these properties are dimensional reduction (in the sense of having no interior), homotopic equivalence, and invertibility. For the restricted class of discrete objects, we define an algorithm for identifying a point set, called a skeleton, which shares these properties with the MAT. Furthermore, this skeleton is to the box-norm (L_inf norm) what the MAT is to the Euclidean norm, and hence the deviation of this skeleton from the MAT is bounded.The algorithm will be developed for both 2D and 3D cases. Proofs of correctness of the algorithm shall be indicated. The use of this skeleton in automated numerical analysis of injection moulded parts shall be demonstrated on industrialized parts. The use of the 3D skeleton in aiding automatic mesh generation for finite element analysis is also of interest, and shall be discussed.
Keywords: Medical Axis Transform; skeletons; image-processing; shape abstraction; feature recognition; digital thinking
A skeleton representation of an object is very useful in:
Mohsen Rezayat
Computer-Aided
Design, Vol. 28 (11), pp. 905-915, November 1996.
An integral part of parallel product and process design is simulation through numerical analysis. This so-called simulation-driven design process often requires abstraction (from the solid model) of an analysis model with appropriate dimension reduction and detail removal. Unfortunately, current CAD systems do not provide the means for automatic abstraction of the optimum analysis model. In this paper we present the algorithms for a new approach, based on midsurface abstraction, which holds significant promise in simplifying simulation-driven design. The method is user-friendly because very little interaction is required to guide the software in its automatic creation of the desired analysis model. It is also robust because it handles parts with complex and interacting features. Examples of abstracted analysis models in finite-element structural analysis and injection-moulding simulation demonstrate the effectiveness and efficiency of the process. In this paper, we will also explore the feasibility of extending the use of midsurface algorithms for feature modelling. It is argued that a successful feature recognition/abstraction scheme must combine topologic and geometric data. Midsurface algorithms cast these data in a nice format and add vital information to it for recognition of certain types of features.
Keywords:
4 main steps:
Page created & maintained by Frederic Leymarie,
1999-2004.
Comments, suggestions, etc., mail to: leymarie@lems.brown.edu