Method of hierarchical static scene simplification

Details Method of hierarchical static scene simplification Method of hierarchical static scene simplification

1999-03-03

2001-10-23

Zimmerman, Mark (Department: 2671)

Computer graphics processing and selective visual display system

Computer graphics processing

Adjusting level of detail

C345S423000

Reexamination Certificate

active

06307558

ABSTRACT:

BACKGROUND
1. Field
The present invention relates generally to computer graphics and, more specifically, to polygonal surface simplification of three dimensional objects in a scene.
2. Description
Computer-generated visual simulations are used in many application areas, such as flight simulation, building walkthroughs, computational fluid dynamics, and video games, for example, with the purposes of training, evaluation, education, and entertainment. Since recent general purpose graphics workstations and personal computers (PCs) allow the interactive display of thousands of polygons making up representations of three dimensional (3D) objects, these simulations have become more common and accessible to a variety of users, such as scientists, educators, and game players. However, as graphics performance increases and its cost decreases, a new generation of users will demand even more complex and more realistic animations. Such animations will require real-time performance at approximately constant frame rates so that the user has the feeling of actual immersion in a virtual world.
In response, content authors are creating more complicated simulations. A simulation may include many different scenes, each with many objects. An object is typically represented as a polygonal mesh. A complicated object may be represented by a mesh containing hundreds or thousands of polygons. When more polygons are present in the mesh, the quality of the image shown on the display is better (that is, it is more detailed), but the time required to display the object is higher. When less polygons are present in the mesh, the quality of the image is poorer, but the time required to display the object is lower. In some cases, a graphics subsystem cannot render a scene having many complicated objects in real-time. A graphics subsystem may attempt to simplify some or all of the objects so that the scene can be displayed more quickly. For example, if an object is initially represented by a mesh having 10,000 polygons, it may be simplified by methods known in the art to a representation of the object having only 1,000 polygons. The object may be simplified further, for example, into a representation having only 100 polygons. These different representations are called levels of detail (LOD). Such LODs are commonly represented in a multi-resolution mesh (MRM). Depending on the desired image quality and system bandwidth, different instances of a multi-resolution mesh representing an object may be used.
Various scene management techniques are used by 3D graphics packages to increase the performance of displaying the scene on a display. For example, some objects in a scene may be simplified by utilizing one or more of several known methods. These methods are known as polygonal surface simplification techniques or mesh simplification techniques. In some cases, objects appearing farther away from a user may be simplified into meshes having fewer polygons (and thus be lower quality images) while objects appearing closer to a user may be only slightly simplified or not simplified at all.
A drawback of polygonal surface simplification techniques known to date is that they operate only on individual objects at a time. Hence, these techniques are inefficient and inadequate for handling complex scenes having large numbers of complex objects. Therefore, a technique that automatically simplifies all of the objects in a scene according to predetermined criteria and that balances image quality and system performance would be a significant advance in the computer graphics art.
SUMMARY
An embodiment of the present invention is a method of scene simplification. The method includes concurrently simplifying a plurality of objects in a scene represented by a hierarchical scene graph.


REFERENCES:
patent: 5317689 (1994-05-01), Nack et al.
patent: 5990910 (1999-11-01), Laksono et al.
patent: 6111582 (2000-08-01), Jenkins
patent: 6137492 (2000-10-01), Hoppe
patent: 6195105 (2001-02-01), Dilliplane et al.
Foley et al. “Computer Graphics; Principles and Practice” second edition ISBN 0-201-12110-7, reprinted 11/192 and 193, pp. 873-882, Nov. 1992.*
Bishop et al., “Designing a PC Game Engine,” IEEE Computer Graphics and Application, Jan./Feb. 1998, pp. 46-53.
Hoppe et al., “Surface Reconstruction from Unorganized Points,” University of Washington White Paper, 8 pages.
Belblidia et al., “Generating Various Levels of Detail of Architectural Objects for Image-Quality and Frame-Rate Control Rendering,” White Paper, 6 pages.
Cohen et al., “Simplification Envelopes,” Computer Graphics (SIGGRAPH '95 Proceedings) (1996), 10 pages.
Hoppe, Hugues, “Progressive Meshes,” Microsoft Research White Paper, 10 pages.
Hoppe et al., “Mesh Optimization,” Computer Graphics (SIGGRAPH '93 Proceedings) (1993), 8 pages.
Luebke, David, “Hierarchical Structures For Dynamic Polygonal Simplification,” TR 96-006, Department of Computer Science, University of North Carolina at Chapel Hill, 7 pages.
Krus et al., “Levels of Detail & Polygonal Simplification,” Crossroads, The ACM's First Electronic Publication, 15 pages.
Hoppe, Hugues, Efficient Implementation of Progressive Meshes, Technical Report MSR-TR-98-02, Microsoft Research, Jan. 1998, 10 pages.

Affiliated with

Also associated with

Rating

Method of hierarchical static scene simplification does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Method of hierarchical static scene simplification, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of hierarchical static scene simplification will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2610612