Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1998-10-15
2001-03-27
Alam, Hosain T. (Department: 2172)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C707S793000, C704S226000, C704S227000, C382S124000
Reexamination Certificate
active
06208997
ABSTRACT:
REFERENCE TO A MICROFICHE APPENDIX
A microfiche appendix is filed herewith having 4 sheets with 387 frames. The program listing set out in the microfiche contains material that is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure, as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever.
FIELD OF THE INVENTION
The present invention relates generally to multiresolution representations of very large spatial databases, and, more particularly, to reduced resolution approximations of very large databases, where the approximations are computable at rates that facilitate real-time (e.g., interactive) viewing and controllable to meet specific constraints on the error in the approximations or the time required to render a view of them.
BACKGROUND OF THE INVENTION
Many databases have already or will soon have grown to the point where the production of useful views of the entire database at real-time (interactive) rates is impossible. In many cases (for example, high resolution spatial databases), it would be acceptable to work with a reduced-resolution representation that approximates the original database and that is small enough to be manipulated and viewed in real time. The representation should do the best job of approximating the original database at some given size for the representation. In other words, the representation should be optimal. Furthermore, the representation, in general, will need to be tailored to the particular views that are to be generated. This implies that the representation itself must be produced in real time. Finally, since the size of databases will only continue to grow, the methods for producing reduced-resolution representations should not impose any inherent limits on the size of the databases that can be approximated.
The invention described here, dubbed ROAM for Real-time Optimally Adapting Meshes, is a general method for producing optimal-quality, reduced-resolution approximate representations of arbitrarily large databases in real time. For example, in an exemplary embodiment discussed below for terrain rendering, the ROAM method is used to produce a reduced-resolution representation of a large terrain database that is optimized for viewing from a given location with a given direction and field of view. The representation can be produced at a rate of 30 frames per second (or faster) making the process appropriate for interactive fly-over of the terrain. In comparison with other methods of approximating a terrain for interactive viewing, ROAM produces approximate representations of much higher quality resulting in a dramatic reduction in visual artifacts as compared with other methods of approximating a terrain for interactive viewing.
In addition to requiring a reduced-resolution representation to be optimal, there will often be cases in which certain features need to be represented exactly, that is, as they would be if no reduction in resolution had taken place. ROAM includes a very general mechanism for guaranteeing that distinguished features of the database are exact in the representations that it produces. In many cases, this can be done with negligible effect on the quality of other features (which are still being approximated) or the speed with which the representation is produced. For example, in the exemplary embodiment for terrain rendering, ROAM can guarantee that lines of sight from the eye to distinguished targets are exact (that is, clear or occluded as they would be if the exact terrain were used) in the terrain representation that it produces for interactive viewing. ROAM can make this guarantee for dozens to hundreds of distinguished lines of sight with negligible effect on either performance or the overall quality of the approximated terrain. The ability to guarantee exact lines of sight in scenes generated in real time is obviously important in, for example, simulations for training of military pilots.
ROAM's ability to produce approximate representation in which essentially arbitrary features are exactly represented is a major advance in solving the difficult problem of maintaining consistency between real-time simulations, which must be able to interact while remaining free to choose their own approximations for terrain and other databases in order to fit their individual computational capabilities, and needs for accuracy. In such situations, ROAM maintains consistency by allowing each simulation system to construct its own representation subject to the condition that the features that must be consistent are represented exactly.
Terrain remains one of the most challenging types of large spatial databases for visualization because it is not naturally decomposed into parts whose complexity can be adjusted independently, and because the qualities required of a triangulation are view dependent. Classic geometry level-of-detail (LOD) optimization algorithms are not immediately applicable to terrain because they require independently adjustable parts. Traditional triangulation optimizations do not apply directly to terrain visualization because they do not admit flexible view-dependent error objectives, and they are much too slow to be used for each frame.
Known existing algorithms that can interactively perform view-dependent, locally-adaptive terrain meshing, including the process of the present invention, rely on a pre-defined multiresolution terrain representation that is used to build the adaptive triangle mesh for a frame. Typically, neighborhoods that are flat or distant are triangulated more coarsely than close or rough neighborhoods that require finer details. See, e.g., Mark C. Miller, “Multiscale Compression of Digital Terrain Data to Meet Real time Rendering rate Constraints,” University of California-Davis, graduate thesis (1995), incorporated herein by reference.
On current graphics hardware and software, the problem remains to maintain dynamic, view-dependent triangle meshes and texture maps that produce good images at the required frame rate. Using ROAM, meshes are constructed that optimize flexible view-dependent error metrics, produce guaranteed error bounds, achieve specified triangle counts directly, and use frame-to-frame coherence to operate at high frame rates for thousands of triangles per frame.
Various objects, advantages and novel features of ROAM will be set forth in part in the description which follows, and in part will become apparent to those skilled in the art upon examination of the following or may be learned by practice of the invention. The objects and advantages of the invention may be realized and attained by means of the instrumentalities and combinations particularly pointed out in the appended claims.
SUMMARY OF THE INVENTION
To achieve the foregoing and other objects, and in accordance with the purposes of the present invention, as embodied and broadly described herein, the process of this invention comprises a computer-implemented process for producing view space representation data in real time from a world space database representing terrain features. The world space database is first preprocessed. A database is formed having one element for each spatial region corresponding to a finest selected level of detail. A multiresolution database is then formed by merging elements at the finest level of detail and subsequent intermediate levels of detail to define a hierarchy of element resolutions until a coarsest selected resolution is obtained. A strict error metric is computed for each element at each level of detail that is independent of parameters defining the view space and that is approximately monotonic to associate with the elements forming the multiresolution database. The multiresolution database and associated error metrics are then stored.
The multiresolution database and associated strict error metrics are then processed in real time for real time frame representations. View parameters for a view vo
Aldrich Charles
Duchaineau Mark
Miller Mark C.
Mineev-Weinstein Mark B.
Sigeti David E.
Alam Hosain T.
Alam Shahid
The Regents of the University of California
Wilson Ray G.
LandOfFree
Rapid production of optimal-quality reduced-resolution... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Rapid production of optimal-quality reduced-resolution..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Rapid production of optimal-quality reduced-resolution... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2504362