Computer graphics processing and selective visual display system – Computer graphics processing – Adjusting level of detail
Reexamination Certificate
1999-01-12
2002-04-16
Zimmerman, Mark (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Adjusting level of detail
C345S420000, C345S423000, C345S427000
Reexamination Certificate
active
06373489
ABSTRACT:
FIELD OF THE INVENTION
This application relates generally to the fields of interactive three dimensional computer graphics and geometry modeling. More particularly, this invention relates to scalable visualization for interactive geometry modeling. Even more particularly, this invention relates to scalable visualization for interactive geometry modeling in geoscience.
BACKGROUND OF THE INVENTION
Geologists, geophysicists and petroleum engineers use models, including computerized models, of the earth's crust to plan exploration and production of hydrocarbons and, to a lesser extent, other minerals. As hydrocarbons become more scarce, the accuracy of the computerized models becomes increasingly important to limiting the cost of locating and producing hydrocarbons and the associated cost of hydrocarbon products, such as gasoline and heating oil.
Interactivity is essential to geoscience modeling and visualization applications. Interactive applications must react quickly to user commands, allowing the user to easily control how a model is built and visualized. However, as models grow larger, applications typically become slower. At some point, response time exceeds interactive criteria. Although using a faster processor and graphics hardware might recoup lost interactivity, users can quickly create models requiring more computing power than available.
Adaptive visualization has been an area of significant research in recent years in the visualization community concerned with large model visualizations. Recently, adaptive visualization has appeared in some products such as, for example, the Active Surface Definition feature in IRIS Performer 2.2 from Silicon Graphics® Inc. In these works existing geometry models are visualized, as shown in FIG.
1
. Typically, the data
2
is used to create a surface representation for geometry modeling
4
, such as NURBS. The geometry model
6
is constructed from the surface representation for geometry modeling. To interactively visualize a large model, the surface representation of the model
4
is converted to the representation of the selected graphics package
8
, which is then visualized
10
. For interactive geometry modeling, this approach not only takes more memory space, but also takes time to reconstruct the adaptive visualization representation if the underlying geometry model has been changed.
SUMMARY OF THE INVENTION
In general, in one aspect, the invention features a method for visualizing a model comprising a first surface. The method is implemented in a programmed computer comprising a processor, a data storage system, at least one input device and at least one output device. The method and the model are stored on a computer-readable media. The method comprises determining, as the model is being built, the rendering resolution of a portion of the first surface based on a view frustum from which the first surface is to be viewed and rendering the portion of the first surface on the output device using the rendering resolution.
Implementations of the invention may include one or more of the following. The first surface may comprise one or more vertices and one or more edges. Determining may comprise selecting, based on the view frustum, the vertices to be rendered from among the one or more vertices and the edges to be rendered from among the one or more edges. The vertices to be rendered and the edges to be rendered may be tessellated. The method may further comprise partitioning the surface into n
i
nodes at resolution level-i using a level-i set of boundaries; partitioning the surface into n
1+1
nodes at resolution level-i+1 using a level-i+1 set of boundaries, resolution level-i+1 having greater resolution than resolution level-i. The method may further comprise associating each level-i+1 node with a unique level-i node; associating with each level-i node the level-i+1 nodes associated to the node; and each node having associated with it a bounding object, each bounding object spatially bounding its associated node.
Selecting the vertices to be rendered may comprise selecting a node front from among the nodes and collecting the vertices from the node front. Selecting the node front may comprise culling the nodes that are outside a view frustum, the view frustum being determined by the view frustum from which the surface is to be viewed. Selecting the node front may comprise selecting nodes from among those nodes having bounding objects that intersect the view frustum. Selecting may comprise projecting a level-i node to a screen. The projection of the level-i node to the screen may have an area. Selecting may further comprise adding the level-i node to the node front if the area of the projection is smaller than a predefined minimum resolution; adding the level-i node to the node front if there are no level-i+1 nodes associated with the level-i node; and considering the level-i+1 nodes associated with the level-i node for inclusion in the node front if the area of the projection of the level-i node is larger than a predefined minimum resolution.
The bounding object of a level-i node may be a sphere. The level-i node may be added to the node front if the following equation is satisfied:
R
(sphere)≦
K×D
wherein
K is a constant computed for the view frustum; and
D is the distance from the center of the level-i node's bounding object to a view point associated with the view frustum.
The projection may be onto a projection plane, the projection plane having a minimum side length, and the projection being viewed from the view point through a viewport, the viewport having a side length corresponding to the minimum side length of the projection region, wherein
K
=
L
×
R
min
(
screen
)
d
wherein
L is the ratio of the minimum side length of the projection region on the projection plane to the corresponding side length of the viewport;
R
min
(screen) is the predetermined radius of minimum projection area on the screen; and
d is the distance from the view point to the projection plane.
The level-i node may comprise one or more simplices, each simplex comprising a surface normal, wherein
the bounding object of a level-i node is a sphere;
the level-i node is added to the node front if the following equation is satisfied:
R
(sphere)≦
f
(&thgr;,&Dgr;&thgr;)×
K×D
where
f(&thgr;,&Dgr;&thgr;) is a scaling function of the average normal &thgr; and the deviation &Dgr;&thgr; of the surface normals of the level-i node's simplices
K is a constant computed for the view frustum; and
D is the distance from the center of the level-i node's bounding object to a viewpoint associated with the view frustum.
f(&thgr;,&Dgr;&thgr;) may be precomputed and stored in a lookup table.
The method may further comprise removing no-longer-to-be-rendered vertices from the list of vertices to be rendered and adding vertices to the list of vertices to be rendered when the view frustum is changed. Removing the tessellation from a no-longer-to-be-rendered portion of the surface including the no-longer-to-be-rendered vertices may be accomplished using decremental tessellation. Tessellating an added portion of the surface including the added vertices may be accomplished using incremental tessellation.
The surface may comprise one or more cells and a 2D map, the 2D map comprising all of the vertices in the surface, the 2D map having a domain and a range. Tessellating may comprise tessellating a subset of the vertices in the domain of the 2D map; and creating a triangle mesh using the range values of the subset of vertices and the tessellation of the domain. Tessellation of the subset of vertices in the domain of the 2D map may include a chosen collection of edges.
The surface may comprise one or more 2-cells, one or more 1-cells that form the boundaries of the 2-cells, and one or more 0-cells that form the boundaries of the 1-cells. Rendering may comprise decimating the 1-cells; identifying the decimated 1-cells that form the boundary of a 2-cell; detecting an intersection betwe
Hammersley Richard P.
Lu Hong-Qian
Jansson Pehr B.
Nguyen Kimbinh T.
Schlumberger Technology Corporation
Speight Howard L.
LandOfFree
Scalable visualization for interactive geometry modeling does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Scalable visualization for interactive geometry modeling, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Scalable visualization for interactive geometry modeling will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2927175