Computer graphics processing and selective visual display system – Computer graphics processing – Graphic manipulation
Reexamination Certificate
2001-11-29
2004-10-05
Razavi, Michael (Department: 2672)
Computer graphics processing and selective visual display system
Computer graphics processing
Graphic manipulation
C345S641000
Reexamination Certificate
active
06801215
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to the field of computer graphics and in particular to a method for iteratively extracting layers from a current set of primitives in order to render the primitives in an order, which can be front-to-back or back-to-front.
BACKGROUND OF THE INVENTION
One of the earliest, if not the earliest, solutions to computing a visibility-order, which is the basis for several recent techniques starts with a rough ordering in z (depth) of the primitives. Then for each primitive, the algorithm fine tunes the ordering by checking whether other primitives actually precede it in the ordering.
The BSP-tree, which is a data structure that represents a hierarchical convex decomposition of a given space, was then developed. Each node v of a BSP-tree T corresponds to a convex polyhedral region, P(v)
R
3
; the root node corresponds to all of R
3
. Each non-leaf node v also corresponds to a plane, h(v), which partitions P(v) into two subregions, P(v+)=h+(v)#P(v) and P(v−)=h−(v)∩P(v), corresponding to the two children, v+ and v− of v. Here, h+(v) (respectively, h−(v)) is the half-space of points above (respectively, below) plane h(v). It was demonstrated that BSP-trees can be used for obtaining a visibility ordering of a set of objects (or, more precisely, an ordering of the fragments into which the objects are cut by the partitioning planes). The key observation is that the structure of the BSP-tree permits a simple recursive algorithm for “painting” the object fragments from back to front: If the viewpoint lies in, say, the positive half-space h+(v), then (recursively) the fragments stored in the leaves of the sub-tree rooted at v− are painted first, then the object fragments S(v)
h(v), and then (recursively) the fragments stored in the leaves of the sub-tree rooted at v+.
It is important to note that the BSP-tree does not actually generate a visibility order for the original primitives, but for fragments of them. It has been shown how to recover the visibility order from the sorted fragments. There are a few issues in using BSP-trees for visibility-ordering. Building a BSP-tree is a computationally intensive process. Thus, handling dynamic geometry is a challenge. Using techniques from the field of “kinetic”data structures, an efficient extension of BSP-trees for handling moving primitives was developed. At this time, this technique requires á priori (actual analytical) knowledge of the motion of the geometry to efficiently perform local changes on the BSP-tree as the primitives move.
Another technique for visibility order, wherein a well-chosen (small) set of ray shooting queries are performed, is known. The ray shooting queries compute for each primitive (at least) its successor and predecessor in the visibility ordering. By running a topological sort on these pair-wise relations, it is possible to recover a visibility order. One of the shortcomings of this technique is that it might actually obtain a larger portion of the visibility graph than necessary to compute the ordering. Since the ray shooting queries are relatively expensive both in time and memory, this can be inefficient.
An incremental visibility sorting: algorithm has also been presented, similar in some respects to the algorithm using a rough ordering in z (depth) and then fine tuning the ordering. This algorithm, despite having a worst case running time of O(n
4
), is shown to be quite fast in practice. In order to cull the number of visibility relations that need to be maintained, several optimizations, such as the use of kd-trees (hierarchical data decomposition trees) and the tracking of overlaps of the convex hulls of the geometric primitives are performed. Their algorithm is able to explore temporal coherency and, in fact, is optimized for dynamic geometry. This algorithm also proposes a technique for correct rendering in the presence of cycles.
Another related technique is known, which uses a multi-pass rendering technique with a “moving” depth buffer to render transparent objects.
Building complicated data structures to solve the visibility-ordering problem is a fairly difficult task. Given that interactivity is of utmost importance in most applications, it would be prudent to try and solve this problem in hardware at some pre-specified resolution. As other researchers have found exploiting the ever-faster graphics hardware available in workstations and PCs, can lead to simpler, and more efficient solutions to rendering problems. The present invention is motivated by this trend.
SUMMARY OF THE INVENTION
The initial motivation for the present invention comes from volume rendering, but the present invention has other applications, which include image-based rendering acceleration, animations with selective display, efficient rendering with transparency. The main contribution of the present invention is a method for computing a visibility ordering of a set of (acyclic) primitives by using features of the graphics hardware.
The present invention is, therefore, a hardware-assisted visibility ordering algorithm. From a given viewpoint, a (back-to-front) visibility ordering of a set of objects is a partial order on the objects such that if object A obstructs object B, then B precedes A in the ordering. Note, however, if the visibility ordering is front-to-back then if object A obstructs B, then B precedes A in the ordering and B<p A. Such orderings are useful because they are the building blocks of other rendering algorithms such as direct volume rendering of unstructured grids. The conventional way to compute the visibility order is to build a set of visibility relations (e.g., B<p A), and then run a topological sort on the set of relations to actually get the partial ordering. The present invention instead works by assigning a layer number to each primitive, which directly determines the visibility ordering. Objects that have the same layer number are independent, and have no obstruction between each other. A method, which exploits a combination of the z− and stencil buffers to compute the layer number of each primitive, is used. One application of the method of the present invention is to obtain a fast unstructured volume rendering algorithm. In an exemplary embodiment the present invention is implemented in OpenGL as well as described in terms of pseudo code.
Most conventional visibility ordering algorithms first build a sufficient set of pair-wise visibility relations (e.g., B<
p
A), and then in a second phase, a topological sort is needed on the set of relations to actually obtain the ordering. Sufficiency for the present invention is in the sense that it is possible to extend such pair-wise relations into a valid partial order. The technique of the present invention instead works by assigning a layer number to each primitive, which directly determines the visibility ordering. To compute the layer number of each primitive, extensive use is made of the graphics hardware. In particular, a combination of the z− and stencil buffers is exploited.
It is, therefore, an object of the present invention to iteratively extract layers from a set of primitives using programmable hardware in order to render the primitives.
It is a further object of the present invention to use a subdivision scheme to avoid unnecessary reading and scanning of the data.
REFERENCES:
patent: 5617114 (1997-04-01), Bier et al.
patent: 5720020 (1998-02-01), Tannenbaum et al.
patent: 5831615 (1998-11-01), Drews et al.
patent: 6151030 (2000-11-01), DeLeeuw et al.
A. Mammen, “Transparency and Antialiasing Algorithms Implemented with the Virtual Pixel Maps Technique”, IEEE Computer Graphics & Applications, pp. 43-55, Jul. 1989.*
P.L. Williams, “Visibility Ordering Meshed Polyhedra”, ACM Transactions on Graphics, 11(2): 103-126, Apr. 1992.
Silva Claudio T.
Wei Bin
AT&T Corp.
Havan Thu-Thao
Razavi Michael
LandOfFree
Hardware-assisted visibility-ordering algorithm does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Hardware-assisted visibility-ordering algorithm, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hardware-assisted visibility-ordering algorithm will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3284122