Data processing: generic control systems or specific application – Specific application – apparatus or process – Product assembly or manufacturing
Reexamination Certificate
1999-02-11
2002-04-23
Grant, William (Department: 2121)
Data processing: generic control systems or specific application
Specific application, apparatus or process
Product assembly or manufacturing
C703S002000, C345S419000
Reexamination Certificate
active
06377865
ABSTRACT:
FIELD OF THE INVENTION
This invention is a method for the automatic conversion of a physical object into a 3D digital model. Combined with 3D scanning technologies it can reverse engineer mechanical, organic, and other shapes.
BACKGROUND OF THE INVENTION
The reconstruction of 3D physical objects has applications in various commercial markets and has been practiced in the Arts and in Engineering disciplines. The computational problem of converting physical measurements into a full-fledged digital model has been studied in computer graphics and in computer-aided geometric design, both of which are disciplines within the Computer Sciences.
This invention concerns the automatic conversion of a 3-dimensional physical object into a digital model of exactly the same shape. The method is illustrated in FIG.
1
and the logical steps are depicted in FIG.
2
. It starts with measurements taken with a 3D scanner. The measurements are points on the surface, which are automatically converted into a surface description using triangles connected to each other along shared edges. The surface description can either be used to produce a physical copy of the object using a 3D printing machine, and it can be further processed with animation or geometric design software.
The prior art uses a variety of systems to make 3D models of objects including manual and semi-manual solutions. The most frequently used method in the animation industry, where looks are more important than accuracy, is to use patches of spline surfaces which can be fit manually over clouds or sets of measured points. Semi-manual methods are common in the mechanical computer-aided design (CAD) industry where parameterized patches are fit over subsets of the measurements identified in a user-guided process. The commercial software CopyCAD by Delcam, Strim by Matra and Surfacer by Imageware are examples of this strategy.
Assuming the points are already connected to a surface by edges and triangles, there is a variety of methods available for replacing the piecewise linear description by a collection of curved spline patches. Charles Loop Smooth Spline Surfaces over Irregular Meshes (1994) and Jorg Peters, C
1
-Surface Splines (1995) decompose the triangles into smaller pieces and then replace each piece by a spline patches so the entire surface is continuous and differentiable. Both methods results in a large number of patches, which defeats the main purpose of introducing splines. Venkat Krishnamurthy and Marc Levoy, Fitting Smooth Surfaces to Dense Polygon Meshes (1996) address this shortcoming by manually decomposing the surface into regions and automatically fitting the corresponding spline patches using spring meshes. Matthias Eck and Hugues Hoppe, Automatic Reconstruction of B-Spline Surfaces or Arbitrary Topological Type (1996) automate the entire patch fitting process by first decimating the triangulated surface and then fitting parametrized patches using regression methods. Similarly, Chandrajit L. Bajaj, Jindon Chen and Guoliang Xu, Modeling with Cubic A-Patches (1995) use regression to fit implicit patches over pieces of a triangulated surface. While the latter two methods are automatic in fitting patches, they do not automate the task of shape reconstruction, which is needed to produce the triangulated surface and is a prerequisite of the patch fitting methods.
Among the automatic solutions, three approaches are distinguished: reconstruction from slices, reconstruction from dense measurement, and reconstruction from 3D complexes. The first two approaches are limited to shapes that can be described by a closed surface.
The reconstruction of a surface is considerably easier than in the general case if the measured points represent a sequence of parallel slices. Henry Fuchs, Zvi M. Kedem and Sam P. Uselton, Optional Surface Reconstruction from Planar Contours (1977) show how to connect two polygons in parallel planes with a cylindrical surface of minimum area. The problem is more difficult if there are more than one polygon per slice. Various heuristics for determining which polygons to connect and how to connect them have been investigated. For example, David Meyers, Shelly Skinner and Kenneth Sloan, Surfaces from Contours (1992) use the minimum set of edges that connect all points, known as a spanning tree of the measurements to guide the matching process for the polygons. Jean-Daniel Boissonnat, Shape Reconstruction from Planar Cross Sections (1988) uses the 3D Delaunay complex for both purposes: to decide which polygons to connect and also how to connect them. In spite of the effort reflected in a large body of literature, no algorithm appears to produce surfaces from sliced data in a generally satisfactory manner to produce a 3D model. Nevertheless, the reconstruction from slices is a fast and effective method for simple organic forms, such as eggs, bones, etc. They are part of commercially available systems such as the Cyberware scanners and medical imaging hardware and software.
A method for surface reconstruction that has become popular in the computer graphics community uses the measurements to construct a continuous function defined over the entire three-dimensional space. The surface is reconstructed as the set where the function assumes a constant value. This is the 2-dimensional analogue of the 1-dimensional contour or isoline in geographic maps that traces out a curve along which a possibly mountainous landscape assumes a constant height. The 2-dimensional analogue of an isoline is an isosurface and can be constructed with the marching cube algorithm. Hugues Hoppe, Tony DeRose, Tom Duchamp, John McDonaLD, Werner Stuezle, Surface Reconstruction from Unorganized Points (1992) construct this function so it approximates the signed Euclidean distance from the measured surface. A necessary assumption in their work is that measurement are uniformly dense over the entire surface and that the density exceeds the smallest feature size of the shape. Brian Curless and Marc Levoy, A Volumetric Method for Building Complex Models from Range Images (1996) use information about rays available from some types of scanners to extrapolated the function over gaps in the measured data. A fundamental requirement of this approach is that the signed distance function is differentiable in the normal direction along the entire surface, which is not possible unless the surface is a closed manifold. In other words, the surface is restricted to form the boundary of a solid volume in space. Examples of surfaces that do not satisfy this property are thin sheets or the common case where only a portion of the volume's surface is accessible to measurement.
A 3D complex decomposes a 3-dimensional volume into cells. An example is the Delaunay complex of a point set, which connects the points with edges and triangles and this way decomposes the convex hull of the given points into tetrahedra. Except for Remco Veltkamp, Closed Object Boundaries from Scattered Points (1994) all work on shape reconstruction via 3D complexes is based on the Delaunay complex A representation of the shape is extracted from the complex by selecting an appropriate set of triangles, edges, and vertices. The various approaches differ in their selection process.
Jean-Daniel Boissonnat, Geometric Structures for Three-Dimensional Shape Representation (1984) describes this approach in general terms and gives some heuristics that sculpt a shape by removing tetrahedra from outside in. The weakness of the method is the lack of an effective rule for deciding which tetrahedra to remove and in what sequence. Herbert Edelsbrunner and Ernst Mucke, Three-Dimensional Alpha Shapes (1994) extend the concept of alpha shapes from 2D to 3D and define them as subcomplexes of the Delaunay complex. They give a rule when a tetrahedron, triangle, edge, vertex belongs to the alpha shape. This rule is exclusively expressed in terms of distance relationship, and it succeeds in reconstructing a shape provided the measured data points are uniformly distributed over its surface and possibly its in
Edelsbrunner Herbert
Fu Ping
Cabrera Zoila
Grant William
Myers Bigel & Sibley & Sajovec
Raindrop Geomagic, Inc.
LandOfFree
Methods of generating three-dimensional digital models of... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Methods of generating three-dimensional digital models of..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods of generating three-dimensional digital models of... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2851600