Computer graphics processing and selective visual display system – Computer graphics processing – Shape generating
Reexamination Certificate
1998-08-14
2002-05-07
Zimmerman, Mark (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Shape generating
C345S420000, C345S423000, C345S427000, C345S442000, C345S443000, C345S581000
Reexamination Certificate
active
06384826
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention is directed toward the problem of surface reconstruction, and more particularly toward reconstructing a surface from sample points, a problem arising in many fields including the fields of computer graphics, data visualization, automated cartography, and medical imaging.
2. Art Background
In general, surface reconstruction algorithms approximate an unknown surface from an input that does not explicitly describe that surface. As a first example, in the field of computer graphics, a three-dimensional model may be scanned by a laser range finder to generate sample points that are input to a computer. A surface reconstruction algorithm is then executed to reconstruct a polygonal surface for subsequent manipulation and rendering. As a second example, a scientist studying a dynamical system may reconstruct a surface over a set of data points to ascertain whether the points lie on a smooth surface such as a low-degree polynomial.
Prior art surface reconstruction algorithms fall into two broad categories: those based on triangulation (such as the current invention) and those based on level sets. The most well-known triangulation-based algorithm is the alpha complex construction of Edelsbrunner, et al. at the University of Illinois. (See H. Edelsbrunner and E. Mücke, “Three-Dimensional Alpha Shapes”, ACM Trans. Graphics, 13 (1994) pp. 43-72) Others who have used triangulation-based algorithms include Boissonat (see S. D. Boissonat, “Geometric Structures for Three-Dimensional Shape Reconstruction,” ACM Trans. on Graphics 3 (1984) 266-286), Bajaj, et al. at Purdue (see C. L. Bajaj, F. Bernardini, and G. Xu, “Automatic Reconstruction of Surfaces and Scaler Fields from 3D Scans”, Computer Graphics (Proc. SIGGRAPH), 1995, pp. 109-118), and Attali in Prance (See D. Attali R-Regular, “Shape Reconstruction from Unorganized Points”, Proceedings of the ACM Symposium on Computational Geometry, 1997, pp. 248-253). The weakness of the alpha complex is that it assumes a global size parameter, alpha, and hence does not work very well for adaptively sampled surfaces. A more general weakness of all triangulation-based algorithms up until the present invention is spurious holes appearing in the surface where four sample points happen to be cocircular.
Level-set algorithms have been devised by a number of research groups, most notably at the University of Washington (See H. Hoppe, T. DeRose, T. Duchamp, J. McDonald, and W. Stuetzle, “Surface Reconstruction from Unorganized Points”, Computer Graphics (Proc. SIGGRAPH), 1992, pp. 71-78) and at Stanford University. (See B. Curless and M. Levoy, “A Volumetric Method for Building Complex Models From Range Images”, Computer Graphics (Proc. SIGGRAPH), 1996 and G. Turk and M. Levoy, “Zippered Polygon Meshes from Range Images”, Computer Graphics (Proc. SIGGRAPH), 1994, pp. 311-318) Level-set algorithms work quite well in practice, and are currently preferred over triangulation-based methods for inexact applications such as computer graphics. Two characteristics of level-set algorithms become liabilities for more exact applications such as scientific visualization: first, level-set algorithms approximate (pass nearby) rather than interpolate (pass through) the sample points; and second, level-set algorithms strongly prefer closed surfaces over surfaces with boundaries.
The surface reconstruction algorithm of the present invention is triangulation-based with provably reliable performance for both inexact and exact applications. Unlike other triangulation-based algorithms, the present invention assumes no global size parameter and avoids spurious holes. Unlike level-set algorithms, the invention gives a polygonal surface whose vertex set is exactly the set of sample points, and the invention will leave a boundary, for example a “window” into the surface, when the polygons that would fill in the boundary are not adequately supported by the data.
SUMMARY OF THE INVENTION
The surface reconstruction algorithm generates a d-dimensional surface from a set of sample points. In the typical case, the surface reconstruction algorithm reconstructs a two-dimensional surface embedded in three-dimensional space from the set of sample points. The surface reconstruction algorithm first generates the Voronoi diagram of the sample points. The Voronoi diagram represents a division of space into Voronoi cells, one Voronoi cell for each sample point, such that each sample point's Voronoi cell consists of that part of space closer to it than to any other sample point. The surface reconstruction system uses the sample points and the shapes of their Voronoi cells to determine which surface elements (triangles in the case of a two-dimensional surface in three dimensions) to include in the reconstructed surface. In one embodiment, Voronoi cell shape information includes locations of vertices, angles at vertices and edges, aspect ratio of the cell, and directions and lengths of principal axes of the cell.
For the two-dimensional surface in three dimensions embodiment, the Voronoi cell shape information is the location of one or two specially selected vertices, called “poles”, from each Voronoi cell. The first pole, p+, of sample point v, is the vertex of v's Voronoi cell farthest from v. If v lies on the convex hull of the sample points, then its Voronoi cell is unbounded, and p+ is any point so that vector vp+ points in a direction in which the Voronoi cell is unbounded. In either case, the second pole p− is the vertex of v's Voronoi cell farthest from v such that vp− has negative dot product with vp+.
After the selection of poles, the surface reconstruction algorithm computes the Delaunay triangulation of the sample points and the poles and retains only those triangles in which all three vertices are sample points. In two last optional steps, the algorithm performs some further triangle filtering. Triangles may be removed based on the angle between the vector to the pole at a vertex and the normal to the triangle. Finally the algorithm extracts a two-dimensional manifold from the set of retained triangles. This manifold extraction step removes each triangle with a sharp dihedral (for example, an edge not adjacent to another triangle), and then takes the inside or outside of the union of triangles.
REFERENCES:
patent: 5850229 (1998-12-01), Edelsbrunner et al.
patent: 5886702 (1999-03-01), Migdal et al.
patent: 6133921 (2000-10-01), Turkiyyah et al.
Chen et al., “Shortest Paths on a Polyhedron”, Department of Computer Science University of Kentucky, 1990 ACM, pp. 360-369.*
Guha, “An Optical Mesh Computer Algorithm for Constrained Delaunay Triangulation”, Electrical Engineering & Computer Science University of Wisconsin Milwaukee, IEEE 6/94, pp. 102-109.*
Amenta, N. and Bern, M., “The Crust and the &bgr;-Skeleton: Combinatorial Curve Reconstruction,”Graphical Models and Image Processing,vol. 60/2, No. 2, Mar. 1998, pp. 125-135.
Amenta, N., Bern, M. and Kamvysselis, M., “A New Voronoi-Based Surface Reconstruction Algorithm,”Proc. SIGGRAPH,1998, pp. 415-421.
Amenta, N. and Bern, M., “Surface Reconstruction by Voronoi Filtering,”Proceedings of the Annual Symposium on Computational Geometry,(ACM), 1998, pp. 39-48.
Attali, D., “r-Regular Shape Reconstruction from Unorganized Points,”Proceedings of the ACM Symposium on Computational Geometry,1997, pp. 248-253.
Bajaj, C.L., Bernardini, F. and Xu, G., “Automatic Reconstruction of Surfaces and Scalar Fields from 3D Scans,”Computer Graphics(Proc. SIGGRAPH), 1995, pp. 109-118.
Boissonnat-J.-D., “Geometric Structures for Three-Dimensional Shape Representation,”ACM Transactions on Graphics,vol. 3, No. 4, Oct. 1984, pp. 266-286.
Clarkson, K.L., Mehlhorn, K. and Seidel, R., “Four Results on Randomized Incremental Constructions,”Computational Geometry: Theory and Applications,1993, 29 pp.
Clarkson, K., “A Program for Convex Hulls,” http://cm.bell-labs.com
etlib/voronoi/hull.html.
Curless, B. and Levoy, M., “A Volumetric Method for Buil
Amenta Annamaria B.
Bern Marshall Wayne
Flieslier, Dubb, Meyer & Lovejoy LLP
Nguyen Kimbinh T.
Xerox Corporation
Zimmerman Mark
LandOfFree
Method, apparatus and computer medium for surface... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method, apparatus and computer medium for surface..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method, apparatus and computer medium for surface... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2865572