Computer graphics processing and selective visual display system – Computer graphics processing – Graph generating
Reexamination Certificate
1998-07-15
2001-05-08
Zimmerman, Mark (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Graph generating
Reexamination Certificate
active
06229549
ABSTRACT:
BACKGROUND OF THE INVENTION
Computer graphics applications often involve display of three-dimensional objects in a “world space” on a two-dimensional display device such as a Cathode Ray Tube (CRT). In addition to non-real-time applications such as computer-aided-drafting of mechanical structures, interactive computer graphics applications include time-based three-dimensional simulations such as those used for flight training, architectural visualization and other forms of “virtual reality.” These simulations may be based on factual data, as in some flight simulations or architectural visualizations, or imaginary data, as in many video games. For these simulation applications, a major challenge is rapid and accurate representation of complex, irregular three-dimensional surfaces that are moving with respect to an observer. For example, in a flight simulation it may be desirable to show terrain translating and rotating with respect to a virtual pilot in a virtual cockpit.
Conventional techniques for mapping a three-dimensional surface for representation on a two-dimensional display generally break down along two lines, each motivated by different needs. For precision applications such as measurement, computer-guided machining and the like, a designer may attempt to build a near-exact representation of surface detail. In these types of applications, faithful reproduction of surface detail may be essential to produce an accurate end product, e.g., a precise wing contour, a precise measurement of interference between parts, and the like. These precision results are often obtained at a high cost because of the size of the database which must be maintained and the multiple, complex computations which may be involved in describing and displaying surfaces.
In contrast, many graphics applications are less concerned with accurate representation of surface details than with providing an appearance of surface structure to lend greater realism to a display without burdensome computational overhead. For instance, a graphics designer wishing to faithfully reproduce an orange is more concerned that the simulated orange appear pebbled than with maintaining the exact location of each pebble on the orange's skin as it is rotated and translated with respect to the observer. For these types of applications, mapping techniques such as texture, bump and displacement mapping may be more appropriate. These techniques usually entail much less data storage and computational overhead, since each location on the three-dimensional surface need be transformed in world space and stored.
Conventional techniques for detailed surface modeling include polygon mesh and parametric and quadric surface approximation, as described in the textbook entitled
Computer Graphics Principles and Practice, Second Edition
by J. Foley et al., Addison-Wesley Publishing Company, Inc., 1990, pages 471-529.
A polygon mesh approximates a surface by modeling it as a combination of polygons connected at their various edges. An explicit representation of a polygon represents the polygon as a list of its vertex coordinates in world space. To avoid redundant storage and repetitive transformation and scan conversion, polygon meshes are often defined using vertex and edge pointers. Lists of vertices and edges are maintained, with each polygon pointing to the edges or vertices which define it. This representational technique tends to cut down on storage requirements and redundant clipping, transformation and scan conversion computations because the constituent polygons of the mesh are manipulated and displayed using their common edges instead of the individual polygons. However, complex polygon meshes represented in this fashion still may present demanding storage and computational burdens.
Parametric and quadric surface modeling techniques model three-dimensional surfaces in much the same way as polygon mesh techniques, modeling the surface as a combination of segments or subsurfaces. Instead of using the simple piecewise-linear approximation used in a polygon mesh, however, these techniques use higher order piecewise-polynomial curves and surfaces. For many applications these techniques provide more accurate surface detail while diminishing the number of points which must be stored to represent the surface. This increased accuracy is often at the cost of complex third or higher-order parametric computations, however.
Conventional techniques for geometrical transformation of the three-dimensional surfaces represented by any of these surface modeling techniques typically apply the transformation to each of the polygon vertices or parametric curve endpoints generated for the model. Many multiplies and trigonometric calculations thus may be required for each point. Even with redundancy-reducing techniques such as vertex and edge pointers, this process is computationally intensive for all but simple surfaces which can be represented by a relatively coarse mesh. Complex surfaces such as terrain generally require a finer distribution of data points to achieve a realistic appearance. Display of a three-dimensional surface represented by a detailed surface model may be equally demanding, as a large number of subsurfaces may have to be projected onto a viewing plane and scan-converted to produce an image. Even with fine detail, additional processing may be required to minimize visual separation effects such as Mach bending caused by using a polygon mesh or similar technique. High-speed interactive transformation and display of these models thus may require processing capabilities beyond those available on general purpose processors such as those used in personal computers.
For these reasons, detailed three-dimensional surface modeling generally has been limited to precision applications such as CAD/CAM or to complex military or commercial training simulations carried out using special-purpose graphics processing hardware or high-powered supercomputers. Many other interactive simulation applications do not employ detailed surface modeling because the computational and data storage overhead involved may preclude updating the display quickly enough to represent movements in real time. Realistic motion representation may require image update rates in excess of 15 Hz, placing heavy demands on a processor performing object translation, projection or scan conversion.
As an alternative to detailed surface modeling, texture, bump and displacement mapping techniques may efficiently provide the appearance of three-dimensional surface detail with less computational and storage overhead. Several of these techniques are described in Foley et al.,
Computer Graphics Principles and Practice, Second Edition
, pages 741-45. These techniques model an object in world space using a coarse representation, typically polygonal. The coarse representation normally contains a smaller number of data points than would be contained in a detailed surface model, and thus translations and rotations of the object in world space may be more easily and quickly computed. Surface detail may then be mapped on the subsurfaces of the coarse representation.
In two-dimensional texture mapping, texture elements are mapped onto the surfaces of the polygons to provide color cues which suggest a surface structure. In bump-mapping, the appearance of surface detail is achieved without detailed surface modeling by perturbing the surface normal of the illumination model used to display the underlying surfaces of the coarse model, giving a “bumpy” surface appearance. In displacement mapping, the actual surface is displaced to provide a similar appearance. Each of these approaches may provide realistic representations of three-dimensional surfaces without detailed surface modeling and the associated overhead.
However, many interactive graphics applications require accurate representation of three-dimensional surface detail throughout translation and rotation of the represented objects. For instance, in a flight simulation application it is generally desirable to maintain spatial relationships
Haynes and Boone LLP
Sealey Lance W.
Virtus Entertainment, Inc.
Zimmerman Mark
LandOfFree
High-speed three-dimensional texture mapping systems and... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with High-speed three-dimensional texture mapping systems and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and High-speed three-dimensional texture mapping systems and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2479142