Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
1999-04-15
2002-03-12
Zimmerman, Mark (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
C345S619000
Reexamination Certificate
active
06356262
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to rendering three dimensional objects and/or volumes on a graphics computer. More specifically, the invention relates to ordering polyhedral cells of volumes in a visibility order for efficient visualization.
BACKGROUND OF THE INVENTION
A visibility ordering of a set of objects, from a given viewpoint, is a total order on the objects such that if object A obstructs object B, then B precedes A in the ordering. Such orderings are extremely useful in computer graphics. Since the late 1960s, several algorithms have been proposed for computing visibility ordering of objects. The classic article by Sutherland, Sproull and Schumacker (“A Characterization of Ten Hidden-Surface Algorithms”, ACM Computing Surveys, 1974), summarizes the early work in the area. At that point, the focus of the visibility ordering work was performing hidden-surface removal. With the advent of the z-buffer, computing visibility orderings was not so important anymore, since such computations were expensive, and the z-buffer provided a simple and effective (hardware) solution to the hidden-surface removal problem.
In the late 1980s, volume rendering, and other graphics techniques were developed, which again required solutions to the visibility ordering problem. In these techniques, it did not suffice to simply flag whether a particular surface (or piece thereof) was visible, but it was necessary to actually compute a global ordering, which then could be used to paint them on the screen in the right order. In Max, Hanranhan, Crawfis (“Area and Volume Coherence for Efficient Visualization of 3D Scalar Functions”, pp 27-33, Computer Graphics (San Diego Workshop on Volume Visualization, 1990)), a technique is proposed which can be used to compute visibility ordering of a special kind of mesh, namely a Delaunay triangulation. In Peter Williams (“Visibility Ordering Meshed Polyhedra”, ACM Transactions on Graphics, 1992), a more general technique was proposed, which still only worked correctly for special kind of meshes, in particular, meshes composed of convex cells, which have no holes, and where the boundary of the whole set of cells was convex. In this work, some heuristics for general datasets were proposed.
The first published solution to an efficient technique for computing the “exact” (that is, correct) visibility ordering of a set of polyhedral cells was proposed in Stein, Becker, and Max (“Sorting and hardware assisted rendering for volume visualization”, Symposium on Volume Visualization, 1994). There, an extension of the previous work of Newell, Newell and Sancha (“Solution to the hidden surface problem”, Proc ACM National Conference, 1972) was proposed. Later, in Williams, Max, and Stein (“A high accuracy volume renderer for unstructured data”, IEEE Transactions on Visualization and Computer Graphics, 1998), a faster variation of the technique is described. A technique similar to Stein et al, is also described in Karasick, Lieber, Nackman, and Rajan (“Visualization of three-dimensional Delaunay meshes”, Algorithmica 1997).
PROBLEMS WITH THE PRIOR ART
Prior art can be roughly divided into three classes: (I) exact visibility-ordering techniques which are general (that is, work for all types of meshes); (II) exact visibility-ordering techniques which have limited applicability (that is, only work correctly for certain types of meshes); (III) and heuristic techniques, which only approximate the visibility ordering of polyhedral cells.
Class I algorithms have quadratic complexity, and have shown to be very slow in practice, and not suitable for use in any kind of interactive application.
Class II algorithms, although fast and suitable for use, have limited scope, and can only be applied for certain types of meshes.
Class III algorithms are not suited for use in interactive applications, mainly because they usually lead to errors in the computed images, which in general might lead to undesirable results. Using Class III algorithms compromises not only the quality of the visualization, but ultimately it can lead to incorrect conclusions. For instance, a medical doctor can not rely on results obtained by using such techniques.
OBJECTS OF THE INVENTION
An object of this invention is an improved method for computing visibility ordering of polyhedral cells.
An object of this invention is an improved system and method for rendering three dimensional volumes.
An object of this invention is an improved system and method for quickly and efficiently rendering three dimensional volumes represented by large data sets.
An object of this invention is an improved system and method for quickly and efficiently rendering three dimensional volumes represented by unstructured (non convex) and large data sets where the volumes are sorted in a visibility order.
SUMMARY OF THE INVENTION
We propose a system and method for efficiently computing the visibility ordering of polyhedral cells.
In order to compute such orderings, our invention builds an ordering graph, composed of oriented edges between two cells. Each edge (A,B) corresponds to the fact that cell A has to be projected, or rendered, before B.
Our invention comprises a set of ordering relations and rules that can be shown to generate, if one exists, a global ordering of the polyhedral cell complex. Our invention uses three different types of edges to accomplish this: Meshed Polyhedra Visibility Ordering (MPVO), Binary Space Partition (BSP) and Partially Projected Cell (PPC) edges, where MPVO edges are prior art described in “Visibility Ordering Meshed Polyhedra” by Peter Williams, and BSP and PPC edges are new for our invention.
MPVO edges exist between two cells that share a face.
BSP edges: In order to define the BSP edges, we must first compute a BSP-tree of the boundary faces of the cell complex. During this construction, some of the boundary faces of the cells will be ‘cut’ by the BSP-tree ‘extended’ faces, into multiple pieces. If we say C is the boundary cell, and c′, c″, and so on, are the pieces of its boundary faces, we define BSP_edge (c′, C) to mean that cell C can only be projected after c′ has been projected by the BSP.
PPC edges: We say a cell C is in the PPC if one of the pieces that compose it, say c′, has been projected by the BSP, but there exist other pieces of cell C that have not been projected. In this case, our system needs to perform additional checks to ensure cells are not being projected out of order. This is accomplished by performing ‘ray shooting’ queries, which we call XMPVO queries.
REFERENCES:
patent: 5459822 (1995-10-01), Izawa et al.
patent: 5555352 (1996-09-01), Lucas
patent: 5742293 (1998-04-01), Koyamada et al.
patent: 5914721 (1999-06-01), Lim
patent: 6172679 (2001-01-01), Lim
C.Silva et al, An Exact Interactive Time Visibility Ordering Algorithm for Polyhedral Cell Complexes.
ACM Symposium on Volume Visualization, 10/98, pp. 87-94.
J. Comba et al, Fast Polyhedral Cell Sorting for Interactive Rendering of Unstructured Grids.
Eurographics '99/P. Brunet and R. Scopigno, vol. 18 (1999), No. 3.
Comba Joao Luiz Dihl
Klosowski James Thomas
Mitchell Joseph Shannon Baird
Silva Claudio T.
Taubin Gabriel
Cao Huedung X.
Ohlandt Greeley Ruggiero & Perle LLP
Percello Louis J.
Zimmerman Mark
LandOfFree
System and method for fast polyhedral cell sorting does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for fast polyhedral cell sorting, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for fast polyhedral cell sorting will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2890308