Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
1998-05-08
2002-01-01
Zimmerman, Mark (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
C345S423000
Reexamination Certificate
active
06335732
ABSTRACT:
BACKGROUND OF THE INVENTION
a) Field of the Invention
The present invention relates to a method and associated computer software for improved visualization and interaction with three dimensional graphics, whereby the system renders only what the user sees and does not waste time rendering hidden components.
b) Description of Related Art
Recent modeling simplification efforts, using Computer Aided Design (CAD) systems, focus on reducing the number of polygons in a visual model. Surfaces in CAD model are tessellated to generate polygons. The collection of polygons is then used as a visual model. The current method relying on the polygon based “Level of Details” (LOD) approach is unwieldy. It requires loading all the information about the entire mechanical model. Such a data set far exceeds the capability of present-day graphics hardware to interactively render the model, no matter the polygon count. Today, modeling applications demand an instantaneous, interactive display of models.
Heckbert in “Ten Unsolved Problems in Rendering, Workshop on Rendering Algorithms and Systems” provided a list of ten unsolved problems in simplifying models for rendering. Among them is the problem of how to more fully automate the levels of details and hierarchical bounding boxes. Heckbert noted that setting up a level of details database is burdensome and causes uneven transitions when switching levels. For simulation work, this is quite unacceptable.
Researchers have investigated and pursued numerous simplification approaches. Among them are the octree, wavelet and the favored multi-resolution technique. Srihari in “Multi-resolution 3-d Image Processing and Graphics” showed how octree models can be used for displaying voxel-based images at different levels of detail. In an octree, each level of the tree increases the resolution by a factor of eight. This allows one to view an object as a gradual process proceeding from a father node to its sons. Gortler, et al in “Hierarchial and Variational Geometric Modeling with Wavelengths” used the hierarchical nature of wavelet basis functions to obtain multi-resolution control point and ]east squares control. A wavelet basis represents a solution hierarchically. In wavelet based schemes, the user chooses the resolution level 1, and then only the quantities of basis function on level 1 are altered. However, multi-resolution models are the models of choice for simplifying renderings and simulations. A few researchers such as Harten (“Multiresolution Representation and Numerical Algorithms”) and Gauch (“Multiresolution Image Shape Description”) have developed multiresolution techniques.
In 1994, Heckert et al. presented “Multiresolution Modeling For Fast Rendering” which surveyed multi-resolution techniques for accelerated rendering and found that a polyhedral simplification method was the most appropriate for accelerated rendering and simulation. Subsequently, commercial packages that used the multi-resolution technique became available. Among them are: the 3D Accelerator (see Rossignac et al., “Multi-resolution 3D approximations for rendering complex scenes”), a polyhedral simplification method, and Deneb Robotics optional package called HIFI, which is a polygonal simplification method.
However, the multi-resolution modeling technique has limitations. Multi-resolution models are scene dependent. They require the preparation of a level of details database for each scene. This is a lengthy process that requires input from the user for each scene and each model. All objects (external and internal) must be prepared, stored in the database, and rendered whether or not the objects are visible during the simulation.
Decomposing a CAD model into polygons before rendering it for visualization typically produces thousands of polygons. The software algorithms that underlie the modeled object, generate an eveN smaller set of polygons that are visually similar to the original object. By creating multiple levels of detail (fore, mid and background) at varying resolutions, the work of a graphics engine is reduced. However, important visible features are lost in such simplification processes. Moreover, the polygonal simplification methods still cannot deliver the requisite display speed for large mechanical models.
A mechanical environment consists of whole mechanical parts and assemblies. A person recognizes a piece of equipment not by taking it apart and investigating its internals, but by simply looking at its external surfaces, its “container.” No one needs to take apart an automobile to recognize what it is, even though the interior parts are hidden from the viewer. The polygon based LOD technique loads all the information, both interior and external, and does not take advantage of the physical reality of a mechanical environment.
SUMMARY OF THE PRESENT INVENTION
The present invention seeks to overcome the drawbacks inherent in the prior art by providing a method for taking advantage of external recognition to thereby render only what is visibly displayed to the user. Internal components and hidden components are omitted from the rendered image.
The invention set forth herein is considerably more efficient because it is scene independent. It processes the CAD models, and prepares a simplified visual container database off-line. It guarantees that only visual objects of an assembly are loaded and rendered for simulation. Internal objects are loaded and rendered as needed. All the processing is done off-line. Simulation time decreases because there are few surfaces to display. This method makes it a powerful tool for faster rendering and simulation.
Taking advantage of this external recognition makes it possible to display CAD models much faster than is currently possible. Significant computational efficiencies are produced by decoupling the internal and external components of a visual assembly. The external container is displayed and manipulated without loading all the visual geometry information. Internal component information is loaded into the display engine only as it is needed.
A key concept underlying the container approach of this invention is the use of a mechanical component (MC) object. This object is a CAD model (solid or 3D surface) of a mechanical component. An MC object is comprised of either the 3D surfaces or the primitive solids and not the tesselated polygons. In a given assembly an MC object may contain, be contained within, penetrated in, abut, or be similar to another MC object.
A generational paradigm helps define the relationship between the MC objects of an assembly. Object positions can be identified through a “relationship tree.” An MC object that contains one or more objects is a ‘parent’ object. The objects within the parent object are its ‘children.’ Two penetrating objects are ‘spouses’, whereas objects sharing a common boundary are ‘siblings.’ Two identical objects are ‘twins.’ A cluster of related objects comprise the ‘assembly.’ Using the concept of containers and the concept of MC objects, the present invention proposes software to significantly reduce the level of detail required for visualization.
To create improved visualization speed, the proposed invention: 1) extracts from existing CAD models an assembly's combinatorial (topological) structure and metric (geometric) information; 2) separately identifies the external, visible features from the interior ones; 3) display only the assembly's visual geometry; and 4) link the original CAD model components within an assembly to its visually displayed “container” geometry.
The present invention sets forth an Automatic Container Simplification (ACS) system which can meet the aforementioned requirements and include the following features:
(1) a visual container database that is based on the surfaces that are visible to the viewer;
(2) a container database that is compatible with multiresolution modeling schemes as well as display systems;
(3) a database that is comprised of surfaces and, therefore, can be directly rendered;
(4) simplified models that retain all important vi
Cao Huedung X.
Liniak Berenato Longacre & White
Zimmerman Mark
LandOfFree
External recognition and rendering method does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with External recognition and rendering method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and External recognition and rendering method will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2866354