Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
2002-04-29
2004-12-07
Lee, Wilson (Department: 2821)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
Reexamination Certificate
active
06828966
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to the fields of mesh representations of object surfaces and volumetric representations of object volumes, and, more specifically, to deriving a mesh representation of a surface from a volumetric representation of an object.
RELATED ART
Volumetric representations of objects are generated in many applications, such as medical imaging and laser scanning. In these applications, a volume of a three dimensional object is typically represented by data in the form of volume elements (‘voxels’), each associated with a point in space and a value known as an iso-value representative of a characteristic or quality of the object at the point in space. For example, in magnetic resonance imaging, a volumetric representation of at least a portion of the human body is formed, comprising a plurality of voxels, in which the iso-value associated with each voxel is the intensity of the image at the point in space corresponding to the image.
It is often desirable to be able to extract from the volumetric representation a representation of a particular surface within the volume represented by the volumetric representation. For example, in the field of magnetic resonance imaging, a physician may want to extract and display a surface representation of a selected organ, such as the brain or the heart, from a volumetric representation of the upper torso and head of a human body. Moreover, a mesh representation, i.e., a representation in which an object surface is represented by a plurality of tessellated polygons such as triangles, is often a convenient form for representing object surfaces because it can be easily refined to more detailed levels of resolution in a hierarchical fashion depending on the application involved. The hierarchical arrangement facilitates applications involving progressive resolution, such as Web applications in which it is desired to rapidly display a coarse representation of object which is the progressively filled in at higher levels of resolution.
A so-called ‘Marching Cubes’ algorithm, described in W. E. Lorenson and H. E. Cline, “Marching Cubes: A High Resolution 3D Surface Construction Algorithm,”
Computer Graphics
(
Proceedings SIGGRAPH
'87), 21(4), 163-169, July 1987, is presently available for extracting a meshed triangle representation from a volumetric representation. However, the triangular representation formed by this method often represents an object surface with an excessive number of triangles, and also with triangles with bad aspect ratios, i.e., aspect ratios which are likely to lead to loss of precision. Mesh representations utilizing an excessive number of triangles lead to inefficiency because they require more time to display and more resources to store. Moreover, mesh representations utilizing triangles with bad aspect ratios are disfavored because they can cause instability problems in down stream applications such as finite element simulation.
SUMMARY
The invention provides a method of extracting a mesh representation of a surface from a volumetric representation of at least a portion of an object. A surface is derived from the volumetric representation. Then, a seed point on the surface is selected and, subject to any applicable constraints, the neighborhood of the point is grown to cover a portion of the surface. If any constraints are applicable and encountered during this process, the growth is halted, and the size of the neighborhood reduced by a specified amount. If any portions of the surface remain uncovered, the process iterates by selecting additional seed points, and growing additional neighborhoods in like manner to the process described, until the surface is substantially completely covered. Polygons are then formed by selectively connecting seed points with connectors. These polygons form a mesh representation of the surface. In one implementation, the polygons are formed using a surface Delaunay triangulation algorithm.
Other systems, methods, data structures, features and advantages of the invention will be or will become apparent to one with skill in the art upon examination of the following figures and detailed description. It is intended that all such additional systems, methods, features and advantages be included within this description, be within the scope of the invention, and be protected by the accompanying claims.
REFERENCES:
patent: 5760779 (1998-06-01), Yamashita et al.
patent: 5901247 (1999-05-01), Osbourn et al.
patent: 6133921 (2000-10-01), Turkiyyah et al.
patent: 6246784 (2001-06-01), Summers et al.
patent: 6345112 (2002-02-01), Summers et al.
patent: 6384826 (2002-05-01), Bern et al.
patent: 6476803 (2002-11-01), Zhang et al.
patent: 6556696 (2003-04-01), Summers et al.
Gavriliu, et al.Fast Extraction of Adaptive Multiresolution Meshes With Guaranteed Properties From Volumetric Data, Proceedings of IEEE Visualization 2001, Oct., 2001 pp. 295-302.
Lorensen. W.E. and Cline, H.E.,Marching Cubes : A High Resolution 3D Surface Reconstruction Algorithm, Computer Graphics, vol. 21, No. 4, pp. 163-169, 1987 (reprinted, pp. 347-353).
De Berg, M. et al.,Computational Geometry: Algorithms and Applications, Chapter 7, 2nd Edition, Springer-Verlag 2000, pp. 147-163.
Barr Alan H.
Breen David E.
Carranza Joel
Gavriliu Marcel
California Institute of Technology
Cao Huedung X.
Howrey Simon Arnold & White , LLP
Lee Wilson
LandOfFree
Method of deriving mesh surface representation from volume... 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 of deriving mesh surface representation from volume..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of deriving mesh surface representation from volume... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3310465