Defining surface normals in a 3D surface mesh

Details Defining surface normals in a 3D surface mesh Defining surface normals in a 3D surface mesh

1999-10-29

2003-11-18

Zimmerman, Mark (Department: 2671)

Computer graphics processing and selective visual display system

Computer graphics processing

Three-dimension

C345S428000, C345S427000, C345S441000, C345S582000, C345S619000

Reexamination Certificate

active

06650324

ABSTRACT:

TECHNOLOGICAL FIELD
This application relates to creating and rendering 3D 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 rendering an image of a 3D surface, a computer system obtains a digital model that includes data points defining vertices for triangles that represent 2D faces of the 3D surface. The computer also obtains a plurality of vectors, each defining a surface normal for the 3D surface at a corresponding one of the vertices. The computer applies an algorithm, such as a Butterfly Subdivision Scheme, to the data points to create new data points defining new vertices that subdivide the triangles into smaller triangles. The computer applies the same algorithm to the vectors to calculate new vectors, each defining a surface normal at a corresponding one of the new vertices.
Other embodiments and advantages will become apparent from the following description and from the claims.


REFERENCES:
patent: 4600919 (1986-07-01), Stern
patent: 5124914 (1992-06-01), Grangeat
patent: 5163126 (1992-11-01), Einkauf et al.
patent: 5731819 (1998-03-01), Gagne et al.
patent: 6057859 (2000-05-01), Handelman et al.
patent: 6208347 (2001-03-01), Migdal et al.
patent: 6337880 (2002-01-01), Cornog et al.
patent: 6388670 (2002-05-01), Naka et al.
Foley et al., “Computer graphics: principal and practice” Addison-Wesley Publishing Company, 1060-1064, Reading, MA 1996.
Hoppe, “Progressive Meshes” Microsoft Research, 99-108, http://www.research.microsoft.com/research/graphics/hoppe/.
Popovic “Progressive Simplicial Complexes” Microsoft Research, http://www.research.microsft.com/~hoppe/.
Hoppe “Efficient Implementation of progressive meshes” Coput. & Graphics vol. 22, No. 1, pp. 27-36, 1998.
Taubin et al., “Progressive Forest Spilt Compression” IBM T.J. Watson Research Center, Yorktown Heights, NY.
Cohen-Or et al., “Progressive Compression of Arbitrary Triangular Meshes” Computer Science Department, School of Mathematical Sciences, Tel Aviv, Israel.
Bajaj et al., “Progressive Compression and Transmission of Arbitrary Triangular Meshes” Department of Computer Sciences, University of Texas at Austin, Austin, TX.
Pajarola et al., “Compressed Progressive Meshes” Graphics, Visualization & Usability Center, College of Computing, Georgia Institute of Technology, Jan. 1999.
Alliez et al., “Progressive Compression for Lossless Transmission of Triangle Meshes” University of Southern California, Los Angeles, CA, 195-202.
Chow “Optimized Geometry Compression for Real-time Rendering” Massachusetts Institute of Technology, Proceedings Visualization 1997, Oct. 19-24, 1997, Phoenix, AZ, 347-354.
Markosian “Real-Time Nonphotorealistic Rendering” Brown University site of the NSF Science and Technology Center for Computing Graphics and Scientific Visualization, Providence, RI.
Elber Line Art Rendering via a Coverage of Isoperimetric Curves, IEEE Transactions on Visualization and Computer Graphics, vol. 1, Department of Computer Science, Technion, Israel Institute of Technology, Haifa, Israel, Sep. 1995.
Zeleznik et al., “SKETCH: An Interface for Sketching 3D Scenes” Brown University site of the NSF Science and Technology Center for Computer Graphics and Scientific Visualization, 1996.
Landsdown et al., “Expressive Rendering: A Review of Nonphotorealistic Techniques” IEEE Computer graphics and Application, 29-37, 1995.
Raskar “Image Precision Silhouette Edges” University of North Carolina at Chapel Hill, Microsoft Research, 1999 Symposium on Interactive 3D Graphics Atlanta, GA, 135-231, 1999.
Ma et al., “Extracting Feature Lines for 3D Unstructured Grids” Institute for Computer Applications in Science and Engineering (ICASE), NASA Langley Research Center, Hampton, VA, IEEE, 1997.
Lewis “Pose Space Deformation: A Unified Approach to Shape Interpolation and Skeleton-Driven Deformation” Centropolis, New Orleans, LA, 165-172.
Lasseter “Principles of Traditional Animation Applied to 3D Computer Animation” Pixar, San Rafael, California, 1987.
Thomas (Contributor) et al., “The Illusion of Life: Disney Animation” 47-51.

Affiliated with

Also associated with

Rating

Defining surface normals 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 surface normals in a 3D surface mesh, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Defining surface normals in a 3D surface mesh will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3163343