Adaptive subdivision of mesh models

Details Adaptive subdivision of mesh models Adaptive subdivision of mesh models

1999-01-27

2002-03-12

Vo, Cliff N. (Department: 2671)

Computer graphics processing and selective visual display system

Computer graphics processing

Three-dimension

C345S421000, C345S442000, C345S581000

Reexamination Certificate

active

06356263

ABSTRACT:

FIELD OF THE INVENTION
This invention relates to three-dimensional (“3D”) modeling of real-world objects, terrains and other surfaces by computer. In particular, the present invention relates to a system and method for smooth surface interpolation for arbitrary meshes.
COPYRIGHT NOTICE
Portions of the disclosure of this patent document contain material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or patent disclosure as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever.
BACKGROUND INFORMATION
There is great interest in the development of computer systems which enable users to generate accurate displays and reproductions of real world and fantasy 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. A mesh model represents an object, terrain or other surface as a series of interconnected planar shapes, such as triangles, quadrangles or more complex polygons. More advanced graphic display systems provide rapid zoom and “walk around” capabilities (allowing the user to make his or her perceived vantage point appear to move closer to, farther from or about an object or surface).
A set of data points that describes the object or surface provides basic data for the mesh. The data points, in many cases, represent actual, measured points on the object, surface or terrain. Values for such measured data points may 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.
Typical mesh modeling systems use data points (such as measured data points) to create meshes of the object, surface or terrain. When modeling a complex object, the meshes often have sharp changes of surface contour in localized areas of detail. For example, when modeling a human face, the area of the mesh model for the nose or the eyes will usually have more changes of contour than the surface area of the cheek. In some circumstances the model designers will sometimes wish to heighten or further refine the contours in these areas to provide a model of the object which is more realistic in appearance or which has a special focus.
Traditional tools of 3D modeling include the use of Bezier splines, Non-Uniform Rational B-Splines (NURBS) and other types of patch based surface modeling. These tools are efficient for simple shapes such as boxes, spheres and cylinders, but quickly become awkward for constructing and providing a sufficient level of detail resolution for surfaces that are more irregularly shaped, such as organic shapes resulting from 3D scanning. As the terrain of a complex object changes rapidly, and in a random fashion, a global function calculation, such as a B-Spline, requires a significant portion of the computer's resources and may not provide a model that has sufficient detail in the areas of interest. Thus, for mesh models of irregularly shaped surfaces, such as real-world or fantasy objects, surfaces or terrains, there is a need for the development of new computer tools for permitting refinement to such complex surfaces. In mathematical terms, one problem to be solved can be stated as follows: Given a base mesh, such as a triangulated surface, how can the mesh be refined to produce a smooth surface that passes through all of the initial vertices orthogonal to the initial normal vectors at each of the vertices.
Over the last decade, developers have made attempts to create algorithms for refining the detail of complex, irregular surfaces. One generally known approach, is the so-called “subdivision of surfaces” technique. As applied to the smoothing of 3D triangulated meshes, this technique seeks to recursively subdivide all of the triangles of the mesh into four-sub triangles, until the desired level of detail is reached.
FIG. 1
shows an example of this subdivision of a single triangle
1
into a triangulated mesh having original vertices
11
,
12
, and
13
. The edges
2
,
3
,
4
of triangle
1
are subdivided by adding new vertices
21
,
22
, and
23
at the midpoints of each edge
2
,
3
,
4
of triangle
1
. These new vertices can be determined or extruded based on an extrusion algorithm and four new triangles
31
,
32
,
33
and
34
can be rendered. Each of these smaller triangles
31
-
34
may also be subdivided and extruded in a similar manner to further refine the mesh.
However, there are drawbacks to the subdivision of surfaces technique, including a likelihood of overwhelming a computer's resources. In certain implementations, each global subdivision using this technique quadruples the used memory. For example, a mesh having 10,000 triangles would have 40,000 triangles after the first iteration of a subdivision. Such subdivision could quickly overwhelm the memory resources of the computer, causing it to be unable to render and animate such a surface after a small number of subdivisions. In addition, this type of recursive subdividing produces a uniform surface geometry when each triangle is always subdivided in the same manner. These subdivisions may not create a surface which passes through the orthogonals of the initial vertices in an efficient manner. Accordingly, there is a need for new techniques to subdivide a mesh model in a way which would provide greater accuracy and efficiency in terms of subdivisions which create a surface that best passes through all of the initial vertices orthogonal to the initial normals and which also uses the available computing resources in the most efficient manner. In the search for better mesh modeling systems, it is important to look at criteria such as:
how to avoid doing unnecessary subdivisions at smooth areas;
how to determine or extrude the middle points of the edges;
how to guarantee numerical stability and robustness; and
how to achieve real-time performance using commonly available computer equipment.
One goal is to prevent unnecessary subdivisions with a algorithm that is adaptive so that it permits the making of an efficient subdivision at any level of recursion. The second issue pertains to the mathematical accuracy of the subdivision. The extrusion technique should provide a certain smoothness of the surface in the limit of infinite subdivision. Additionally, normal vectors to this limiting surface have to interpolate those at the base mesh vertices, which requirement gives another restriction on the extrusion algorithm.
The third issue pertains to practical implementation. “Bad” areas, such as high peaks may produce instabilities at each level of subdivision, which may go to infinity in the limit of infinite level. The last issue has to do with computational complexity. The algorithm should take linear time. Moreover, very few operations should be performed in every triangle, so that speeds of, for example 10 frames/sec, can be achieved by using available computer hardware, such as an Intel Pentium II™ processor.
With problems such as these solved, adaptive subdivision may become a basic tool of 3D graphics, like Gourand shading. Hardware acceleration may lead to speeds of 30 frames/sec or more, after which a new level of realism in 3D graphics can be achieved. However, to date there are no tools which can produce a smooth mesh model with the desired efficiency, detail and accuracy.
SUMMARY OF THE INVENTION
The present invention provides a computer-based system and method for the adaptive subdivision of mesh model of a three-dimensional (3D) object or surface that r

Affiliated with

Also associated with

Rating

Adaptive subdivision of mesh models does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Adaptive subdivision of mesh models, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Adaptive subdivision of mesh models will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2826337