Defining a neighborhood of vertices in a 3D surface mesh

Details Defining a neighborhood of vertices in a 3D surface mesh Defining a neighborhood of vertices in a 3D surface mesh

1999-10-29

2003-08-12

Jones, Hugh (Department: 2123)

Data processing: structural design, modeling, simulation, and em

Structural design

C703S002000, C345S419000, C345S420000

Reexamination Certificate

active

06606584

ABSTRACT:

TECHNOLOGICAL FIELD
This application relates to creating and rendering
3
D surfaces in a computer system.
BACKGROUND
Many computer graphics applications render complex three-dimensional (3D) surface geometries by iteratively refining simple, coarse 3D geometries, known as “base meshes.” In general, each base mesh is a collection of triangle faces, in which trios of adjacent points, or vertices, are connected to form an approximation of a 3D surface. This approximation represents a coarse approximation of a more complex, ideal 3D surface, known as a “limit subdivision surface,” or “limit surface.”
A computer creates an initial “subdivision surface” from a base mesh by applying a computational kernel, known as a “subdivision kernel,” to the triangles and vertices in the base mesh. Repeated and recursive application of the subdivision kernel yields increasingly smooth meshes that converge at the limit surface as the number of iterations approaches infinity.
Producing a subdivision surface typically involves computing a weighted midpoint between each pair of vertices in each triangle (i.e., along each edge in the mesh) and then connecting the midpoints, or “tessellating” the triangle, to create four smaller triangles. The time required to subdivide a 3D surface mesh depends upon the technique used in tessellating the triangles in the mesh. More efficient tessellation techniques reduce processing time and therefore improve rendering speed.
In rendering 3D surfaces, computers must often calculate surface normal vectors to ensure realistic light shading of the surfaces. Simple lighting models use the angle between a surface normal vector and a vector in the direction of the light source to calculate how much light strikes the surface at a corresponding vertex. In general, the computer must compute a surface normal vector for each new vertex produced in the subdivision surface computations. As with tessellation, more efficient surface normal calculation reduces processing time and therefore improves rendering speed.
SUMMARY
In one aspect, the invention features using a computer to create a digital model of a 3D surface to be rendered. The computer obtains an initial digital model of the 3D surface and identifies first and second base triangles in the initial model. The first base triangle is subdivided into a plurality of subdivision triangles including a first subdivision triangle. Likewise, the second base triangle is subdivided into a plurality of subdivision triangles including a second subdivision triangle. The first and second subdivision triangles share an edge.
The computer assigns first and second identifying labels to the first and second subdivision triangles to indicate their positions in the first and second base triangles. Thereafter, the computer further subdivides the digital model. One technique for further subdividing the digital model includes applying a computer-implemented test to the first identifying label to derive the second identifying label automatically, using the first and second identifying labels to retrieve information about the first and second subdivision triangles, and then using this information to subdivide the first subdivision triangle into smaller triangles.
Other embodiments and advantages will become apparent from the following description and from the claims.


REFERENCES:
patent: 5602979 (1997-02-01), Loop
patent: 6266062 (2001-07-01), Rivara
patent: 6356263 (2002-03-01), Migdal et al.
Lee et al., “Navigating through Triangle Meshes Implemented as Linear Quadtrees”, ACM Transaction on Graphics, vol. 19, Issue 2, Apr. 2000, pp. 79-121.*
Floriani et al., “Hierarchical Triangulation for Multiresolution Surface Description”, ACM Transaction on Graphics, vol. 14, No. 4, Oct. 1995, pp. 363-411.

Affiliated with

Also associated with

Rating

Defining a neighborhood of vertices in a 3D surface mesh does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Defining a neighborhood of vertices in a 3D surface mesh, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Defining a neighborhood of vertices in a 3D surface mesh will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3119876