Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
2001-04-20
2004-05-18
Zimmerman, Mark (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
C345S420000
Reexamination Certificate
active
06738062
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to computer graphics, and more particularly to displacement mapping.
BACKGROUND OF THE INVENTION
Highly detailed surface models are becoming commonplace in the area of computer graphics, in part due to three-dimensional scanning technologies. Typically, these models are represented as dense triangle meshes. However, the irregularity and huge size of such meshes present challenges in manipulation, animation, rendering, transmission, and storage.
FIG. 1
illustrates a surface
100
represented as dense triangle meshes.
Such surface
100
is an expensive representation because it stores:
(1) the irregular connectivity of faces,
(2) the (x,y,z) coordinates of the vertices,
(3) possibly several sets of texture parameterization coordinates (u,v) at the vertices, and
(4) texture images referenced by these parameterizations, such as color images and bump maps.
Examples of alternative representations will now be set forth that allow one to express a detailed surface as a displacement from a simpler, smooth domain surface.
A simple example of a displaced surface is terrain data expressed as a height field over a plane. The case of functions over the sphere has been considered in the past. See: Schröder, P., and Sweldens, W. Spherical wavelets: efficiently representing functions on the sphere. Proceedings of SIGGRAPH 95, Computer Graphics, Annual Conference Series, pp. 161-172. Another example is a three-dimensional scan of a human head expressed as a radial function over a cylinder. However, even for this simple case of a head, artifacts are usually detectable at the ear lobes, where the surface is not a single-valued function over the cylindrical domain.
It has been shown that a detailed model can be represented as a displacement map over a network of B-spline patches. See: Krishnamurthy, V., and Levoy, M. Fitting smooth surfaces to dense polygon meshes. Proceedings of SIGGRAPH 96, Computer Graphics, Annual Conference Series, pp. 313-324. However, such B-spline patches resort to a vector-valued displacement map because the detailed model is not always an offset of their B-spline surface. Also, avoiding surface artifacts during animation requires that the domain surface be tangent-plane (C
1
) continuous, which involves constraints on the B-spline control points.
Many techniques have been developed in the past for modeling purposes. Such techniques involve subdivision surfaces, displacement maps, bump maps, and multiresolution subdivision.
Subdivision Surfaces
Subdivision schemes defining smooth surfaces have been introduced in much documentation. By way of example, reference may be made to:
1) Catmull, E., and Clark, J. Recursively generated B-spline surfaces on arbitrary topological meshes. Computer Aided Design 10, pp. 350-355 (1978);
2) Doo, D., and Sabin, M. Behavior of recursive division surfaces near extraordinary points. Computer Aided Design 10, pp. 356-360 (1978); and
3) Loop, C. Smooth subdivision surfaces based on triangles. Master's thesis, University of Utah, Department of Mathematics, 1987.
More recently, these schemes have been extended to allow surfaces with sharp features and fractionally sharp features. See:
1) DeRose, T., Kass, M., and Truong, T. Subdivision surfaces in character animation. Proceedings of SIGGRAPH 98, Computer Graphics, Annual Conference Series, pp. 85-94; and
2) Hoppe, H., DeRose, T., Duchamp, T., Halstead, M., Jin, H., McDonald, J., Schweitzer, J., and Stuetzle, W. Piecewise smooth surface reconstruction. Proceedings of SIGGRAPH 94, Computer Graphics, Annual Conference Series, pp. 295-302.
DeRose et al. define scalar fields over subdivision surfaces using subdivision masks. Hoppe et al. describe a method for approximating an original mesh with a much simpler subdivision surface. Such method does not, however, consider whether the approximation residual is expressible as a scalar displacement map.
Displacement Maps
The idea of displacing a surface by a function is set forth in Cook, R. Shade trees. Computer Graphics (Proceedings of SIGGRAPH 84), 18(3), pp. 223-231. Displacement maps have become popular commercially as procedural displacement shaders. The simplest displacement shaders interpolate values within an image, perhaps using standard bicubic filters. Though displacements may be in an arbitrary direction, they are almost always along the surface normal. See: Apodaca, A. and Gritz, L. Advanced RenderMan—Creating CGI for Motion Pictures, Morgan Kaufmann, San Francisco, Calif., 1999.
Typically, normals on the displaced surface are computed numerically using a dense tessellation. While simple, this approach requires adjacency information that may be unavailable or impractical with low-level APIs and in memory-constrained environments (e.g. game consoles). Strictly local evaluation requires that normals be computed from a continuous analytic surface representation. However, it is difficult to piece together multiple displacement maps while maintaining smoothness. One encounters the same vertex enclosure problem as in the stitching of B-spline surfaces. While there are well-documented solutions to this problem, they require constructions with many more coefficients (9×in the best case), and may involve solving a global system of equations. For more information on the vertex enclosure problem set forth hereinabove, reference may be made to: Peters, J. Local smooth surface interpolation: a classification. Computer Aided Geometric Design, 7(1990), pp. 191-195.
A scheme has also been developed for approximating an arbitrary mesh using a B-spline patch network together with a vector-valued displacement map. In such scheme, the patch network is constructed manually by drawing patch boundaries on the mesh. Additional work has been done on surface pasting using the idea of adding a vector-valued displacement map to a spline surface. For more information on such concepts, reference may be made to:
1) Chan, K., Mann, S., and Bartels, R. World space surface pasting. Graphics Interface '97, pp. 146-154;
2) Krishnamurthy, V., and Levoy, M. Fitting smooth surfaces to dense polygon meshes. Proceedings of SIGGRAPH 96, Computer Graphics, Annual Conference Series, pp. 313-324; and
3) Mann, S. and Yeung, T. Cylindrical surface pasting. Technical Report, Computer Science Dept., University of Waterloo (June 1999).
Hardware architecture has also been developed for rendering scalar-valued displacement maps over planar triangles. To avoid cracks between adjacent triangles of a mesh, the vertex normals may be interpolated across the triangle face, and the interpolated normal may be used to displace the surface. Such scheme permits adaptive tessellation in screen space. The importance of proper filtering when constructing mipmap levels in a displacement map should be recognized. The domain surface associated with the present technique is not smooth since it is a polyhedron. As such, animating a displaced surface using a polyhedral domain surface results in many surface artifacts. For more information on such hardware architecture, reference may be made to: Gumhold, S., and Hüttner, T. Multiresolution rendering with displacement mapping. SIGGRAPH workshop on Graphics hardware, Aug. 8-9, 1999.
An additional similar framework has been developed to express the geometry of one mesh as a displacement from another mesh, for the purpose of multiresolution shape deformation. For more information regarding such framework, reference may be made to: Kobbelt, L., Bareuther, T., and Seidel, H. P. Multi-resolution shape deformations for meshes with dynamic vertex connectivity. Proceedings of EUROGRAPHICS 2000.
With respect to displacement maps, there is a need for subdivision-based displacements that are inherently smooth. There is a further need for a surface representation that is more compact such that displaced surface normals may be computed more efficiently. Moreover, there is a need for unifying the representation around subdivision in order to simplify implementation and make operations such as magnification mo
NVIDIA Corporation
Sealey Lance W.
Silicon Valley IP Group PC
Zilka Kevin J.
Zimmerman Mark
LandOfFree
Displaced subdivision surface representation does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Displaced subdivision surface representation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Displaced subdivision surface representation will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3241584