Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
1998-09-29
2001-11-06
Zimmerman, Mark (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
C345S428000
Reexamination Certificate
active
06313837
ABSTRACT:
BACKGROUND OF THE INVENTION
This application relates to representing computer models and more particularly to representing a geometry model at more than one level of resolution.
The accurate representation of subsurface topology can have a profound effect on the interpretation of a geoscience model. This is mainly due to the presence of material properties such as, for example, oil. For a more detailed introduction on the importance of topology, see U.S. patent application Ser. No. 08/772,082, entitled MODELING GEOLOGICAL STRUCTURES AND PROPERTIES.
Imagine, for example, the situation of two compartments
10
a
,
10
b
separated by a sealed fault
12
(a sealed fault is an impermeable membrane that does not permit fluids to pass), as shown in FIG.
1
. Due to the sealed fault there can be no flow of fluid from compartment
10
a
to compartment
10
b.
If both compartments were to contain oil it would be necessary to drill into both compartments to recover the oil.
Now suppose the sealed fault
12
is punctured, as shown in FIG.
2
. There is now a free flow of fluid between compartment
10
a
and compartment
10
b
so it would be possible to drill just into one of the compartments to extract the oil.
Thus, having the correct topology in the geoscience model can have a profound effect on the finances of an oil-field development.
Another important concept in interpreting geoscience models presented graphically on a computer screen is the concept of multiresolution analysis, whereby an analyst can view an area of interest in the geoscience model at different resolution levels. There are many techniques that have been developed for multiresolution analysis of surfaces. The work falls into two principal categories. The first is to use wavelets. The second is to use edge contraction and edge flipping, which is sometimes called “topological editing”.
Wavelets have found wide acceptance in image processing and recently have found application in surface representations. Typically, wavelets are used in a subdivision fashion. A typical subdivision scheme uses quaternary subdivision. For example, as shown in
FIG. 3
, a triangle
14
may be subdivided into four triangles
16
a-d.
In the example shown in
FIG. 3
, the retessellation conforms to the subdivision scheme. That is, the retessellation of the triangle into four triangles conforms with the quaternary subdivision scheme. It can be imagined, however, that if a different local retessellation of the triangle is performed, it may not be clear how to rebuild the subdivision scheme, since the refinement may not conform to the subdivision scheme. For example, if the triangle
14
is retessellated as in
FIG. 3
b
into triangles
17
a
and
17
b
, the retessellation does not conform to the quaternary subdivision scheme. There has been no work on the integration of wavelets and boundary representations.
Topological editing, or editing a mesh using the topological operations of vertex removal, edge contraction and edge flipping, can be used to build multiresolution surfaces. Some mesh building techniques build a history of topological operations which permits progressive and partial loading of the surface, but it is not clear how this history is modified if a triangle is refined. There has been no work on the integration of topological editing and boundary representations.
SUMMARY OF THE INVENTION
In general, in one aspect, the invention features a method, computer system and computer program for representing a first surface at multiple levels of resolution. The first surface comprises zero or more zero-cells, zero or more one-cells and one or more two cells. The method is implemented in a programmed computer comprising a processor, a memory, a persistent storage system, at least one input device, and at least one output device. The method and a model are stored on a computer-readable media and the method represents the model on one of the output devices. The method comprises partitioning the first surface with one or more boundaries, each level of resolution having a subset of the boundaries.
Implementations of the invention may include one or more of the following. The first surface may be partitioned into n
i
nodes at resolution level-i using the level-i subset of boundaries. Each level-i+1 node may be associated with a unique level-i node. Each level-i node may be associated with the level-i+1 nodes associated to the node. Each level-i node may be associated with a subset of vertices that are critical at resolution level i. Assuming level d is the deepest level of resolution and the first surface is divided into simplices, each node at resolution level d may be designated a leaf node, each simplex may be associated to a unique leaf node, and each leaf node may have associated with it the simplices associated to that leaf node.
A level-i node may have associated with it the list of simplices which is the union of all simplices associated with the level-i+1 nodes associated to the level-i node. The subset of boundaries for each node may be assigned to be the boundary of the union of the simplices associated with that node. The nodes may form an original tree and each node may be assigned a unique key. Each vertex in a leaf node may be assigned the key corresponding to that leaf node.
The representation of a second surface may be stored in the computer-readable media, the second surface having nodes, leaf nodes, vertices, critical vertices and simplices. It may be determined which leaf nodes of the first surface intersect the leaf nodes of the second surface and the intersecting simplices from the first and second surfaces from the simplices associated to the intersecting leaf nodes.
Each node except the leaf nodes may have a subtree, and the original tree may be split into new trees and each new tree may be associated with a new cell. The subtrees of the original tree which have no intersecting leaf nodes may be identified with one of the new cells. The simplices of the first surface may be split along the intersection curve. New simplices may be formed by tessellating the split simplices to respect the macro-topology of one-cells and zero-cells passing through the original simplices. A new tree may be built for each new cell and each new simplex may be assigned to the leaf node of the tree created for the new cell to which the new simplex belongs. For each leaf node of each new tree, each simplex in the original tree which is connected to a new simplex in the new tree leaf node and which lies in the same tree leaf node as the new simplex may be migrated. The neighbors of a tree node may be determined by finding all the keys of all the critical vertices in the node. The coarsest level node which is an ancestor of a key from the critical vertices in the migrated tree nodes and has not been split or migrated may be determined and that node may be migrated to the new tree.
A complete node front of the tree of the first surface and a collection of vertices on a boundary of the first surface may be defined. A list of critical vertices from the tree nodes of the complete node front may be built. Those vertices identified to one- or zero-cell vertices may be removed from the list and all zero-cell vertices from the model which lie in the first surface and the defined collection of one-cell vertices may be added to the list. The collection of one-cell edges may be recorded. The surface may be tessellated to respect the list of vertices and the recorded one-cell edges.
The subset of vertices on the boundary of the first surface which are also on the boundary of the second surface may be required to be the same as the subset of vertices on the boundary of the second surface which are also on the boundary of the first surface.
A geometrical representation of the first surface may be maintained in a persistent storage.
A bounding box for each node may be stored on a persistent storage device, and for each node a list of critical vertices associated with that node may be stored on the persistent storage device. Storing the list of crit
Assa Steven Brent
Hammersley Richard Paul
Lu Hong-Qian
Jansson Pehr B.
Maseles Danita J. M.
Santiago Enrique L
Schlumberger Technology Corporation
Speight Howard L.
LandOfFree
Modeling at more than one level of 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 Modeling at more than one level of resolution, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Modeling at more than one level of resolution will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2591657