Computer graphics processing and selective visual display system – Computer graphics processing – Adjusting level of detail
Reexamination Certificate
2002-05-14
2003-08-26
Nguyen, Phu K. (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Adjusting level of detail
Reexamination Certificate
active
06611267
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to computer systems for three-dimensional (“3D”) modeling of real-world objects, terrains and other surfaces. In particular, this invention relates to computer systems which create optimized mesh models of objects and surfaces and have the capability to change dynamically the construction of the model to represent the object or surface in varying levels of detail.
BACKGROUND OF THE INVENTION
There is great interest in the development of computer systems which enable users to generate quickly accurate displays and reproductions of real world objects, terrains and other 3D surfaces. A graphic display and manipulation system generates a mesh model of the object, terrain or surface, uses that mesh model as a basis to create the display or reproduction and allows the user to manipulate the model to create other displays such as “morphs,” fantasy displays or special effects. A mesh model represents an object, terrain or other surface as a series of interconnected planar shapes, such as sets of triangles, quadrangles or more complex polygons. More advanced graphic display systems provide rapid zoom and “walk around” capabilities (allowing the viewer to make his or her perceived vantage point appear to move closer to, farther from or about an object or surface). The mesh modeling of these systems must be flexible and provide dynamic resolution capabilities as well as display a high quality reproduction of the object.
A set of data points that describes the object or surface provides basic data for the mesh. The data points represent actual, measured points on the object, surface or terrain. Their values come from a number of sources. A user can input data points based on measurement or planned architecture or they can be generated through scanning and other measuring systems. A scanning system uses a light source such as a laser stripe to scan and a camera to collect images of the scanning light as it reflects from the object. A scanning system processes the information captured in the images to determine a set of measured 3D point values that describe the object, surface or terrain in question. Scanning systems can easily gather the raw data of several hundred thousand 3D coordinates. The data points come to the mesh modeling system as a group of randomly distributed points. Other data concerning the object, terrain or surface, such as a texture map, ambient light data or color or luminosity information, can be associated or used in conjunction with the geometric shapes of the mesh.
Typical mesh modeling systems use data points either indirectly (in gridded network models) or directly (in irregular network models) to create meshes. U.S. Pat. No. 4,888,713 to Falk and U.S. Pat. No. 5,257,346 to Hanson describe ways of creating gridded mesh representations. Gridded network models superimpose a grid structure as the basic framework for the model surface. The grid point vertices form the interconnected geometric faces which model the surface. The computer connects the grid points to form evenly distributed, geometric shapes such as triangles or squares, that fit within the overall grid structure. While gridded models provide regular, predictable structures, they are not well suited for mesh construction based on an irregular, random set of data points, such as those generated through laser scanning (as mentioned above). To fit the irregular data points of a laser scan into a rigid grid structure, the data point values must be interpolated to approximate points at the grid point locations. The need to interpolate increases computation time and decreases the overall accuracy of the model.
Compared to a gridded model, an irregular mesh model provides a better framework for using irregular data points, because the irregularly-spaced data points themselves can be used as the vertices in the framework, without the need to interpolate their values to preset grid point locations. A typical irregular network meshing system builds a mesh by constructing edge lines between data points to create the set of geometric faces that approximate the surface of the object or terrain. There has been widespread interest in building irregular mesh models having planar faces of triangular shapes, as only three points are needed to determine a planar face.
While irregular triangular meshes offer the possibility of more accurate displays, the systems to implement them are more complex compared to gridded network models. The limitations of the computer hardware and the complexity inherent in the data structures needed for implementation of irregular mesh building systems has prevented their widespread use. U.S. Pat. No. 5,440,674 to Park and U.S. Pat. No. 5,214,752 to Meshkat et al. describe meshing systems used for finite element analysis, i.e., the partitioning of CAD diagrams into a series of mesh faces for structural analysis, not the creation of a mesh from a series of raw data points. Further, these systems do not permit dynamic variable resolution. To alter the resolution of the meshes in these systems, the operator must reinitiate and recreate the entire mesh. As such, the systems do not appear suitable for the dynamic mesh generation requirements of applications such as computer animation and special effects.
For computer mesh applications involving the hundreds of thousands of 3D data points typically used in computer animation, there is a need for the creation of a mesh system which can generate a mesh with substantial speed and rapidly vary its resolution. Speed and data storage requirements are also important factors in graphic display applications on communication systems such as the Internet. Currently, Internet graphic displays are typically communicated as massive 2D pixel streams. Each and every pixel displayed in a 2D image must have a pixel assignment. All of those pixel assignments must be transmitted via the communications system. Such a transmission requires large amounts of communication time. Further, if movement is depicted in the display, information must be continuously sent over the communications system to refresh the image or, in the alternative, one large chunk of pixel data must be downloaded to the receiving terminal before the display can begin. Replacing the 2D image display system with a 3D modeling system substantially reduces the amount of data needed to be transmitted across the communication system, because with a 3D modeling system only representative 3D data points need be sent—not a full set of assignments for every pixel displayed. A mesh generating system located at the receiver terminal could generate a full display of the object upon receiving relatively few 3D data points. Currently available meshing systems do not provide this capability.
The demands of computer animation and graphic display also call for improvement in the quality of the mesh. In the case of an irregular triangulated mesh, for example, when the angles of one triangle's corners vary widely from the angles of another triangle or the triangles differ wildly in shape and size, the mesh tends to be difficult to process for functions such as “gluing” (joining a mesh describing one part of an object to a mesh describing an adjacent part). Such a mesh will also display badly. For example, a non-optimized triangulated mesh might show a jagged appearance in the display of what are supposed to be smooth curving surfaces like the sides of a person's face. Generally, an underlying mesh model constructed from small, regularly angled triangles that tend towards being equilateral is preferable.
The procedure of B. Delaunay known as “Delaunay Triangulation” is one optimization theory which researchers have attempted to implement for the construction of a high quality, irregular meshes with homogeneous triangular structure Delaunay's theories for the creation of irregular mesh lattices derive from the teachings of M. G. Voronoi and the studies he made of “Voronoi polygons”. Voronoi determined that, for a set of data points in space, a proximity region co
Lebedev Alexei
Migdal Alexander
Nguyen Phu K.
Viewpoint Corporation
LandOfFree
System and method for computer modeling of 3D objects or... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for computer modeling of 3D objects or..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for computer modeling of 3D objects or... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3102497