Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
1999-05-20
2002-06-18
Vo, Cliff N. (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
Reexamination Certificate
active
06407737
ABSTRACT:
FIELD OF INVENTION
The present invention is related to the field of volume graphics, and in particularly to rendering an image of a shear-warped volume data set.
BACKGROUND OF THE INVENTION
A volume data set is defined as an array of voxels. The voxels have values representative of some real or imaginary object. Therefore, the voxels are typically arranged in a memory according to object coordinates. Rendering of the volume produces pixels arranged according to image coordinates.
Sometimes, the size of the volume data set is either too large or too complex to be processed in a single rendering pass by a single rendering engine. In other words, the numbers of voxels to be processed exceed memory or processing limitations. In this case, it become necessary to partition the volume into sets of voxels. These sets can then be rendered independently, either sequentially or in parallel. Finally, the results of the independent renderings can be combined into a final image that is the same as the image that would have been generated in a single pass rendering.
There are many methods in the prior art that use partitioning of volume data in conjunction with direct volume rendering. They can be roughly divided into image partitioning and object partitioning methods. In image partitioning, each rendering task computes a specific portion of the image. Sets of pixels are computed by moving the volume data to one or more rendering engines as the viewing transformation changes. In object partitioning, each rendering engine is assigned a specific subset of the volume data to render. The partial results from each rendering must then be combined together to form the image.
In “Real-Time Volume Rendering on Shared Memory Multiprocessors Using the Shear Warp Factorization,” Parallel Rendering Symposium, pp. 15-22, 1995, Lacroute presents a parallel shear-warp rendering method that requires a shared-memory architecture for efficient operation. There, an image partitioning of the base-plane is used in conjunction with an object partitioning of the volume. The volume is partitioned into sets of voxels that are on slices aligned perpendicular to viewing rays. The alignment of the partitioned sets of voxels is performed by shearing the slices according to viewing parameters, and subsequently warped the intermediate results to a final image.
As a disadvantage, Lacroute's method requires that each rendering engine have access to the entire volume data set because many of the rays pass through all of the slices. This either increases the amount of storage required, or else, requires specialized hardware, such as a shared-memory computer. In addition, the partitioning and shearing need to be done for every different viewing angle.
Amim et al., in “Fast Volume Rendering Using an Efficient, Scalable Parallel Formulation of the Shear Warp Algorithm, Parallel Rendering Symposium, pp. 7-14, 1995, describes an extension of Lacroute's shear-warp method. Here, the volume is object partitioned according to slices that are parallel to the viewing rays. This view point dependency leads to a need to communicate voxels among rendering engines, which is more inefficient than Lacroute's image partitioning method. Although Amim's method allows a partitioning of the volume according to the number of rendering engines, it still suffers, like Lacroute, in being view point dependent.
Therefore, it is desired to render a volume by distributing volume partitions over multiple rendering engines and their associated memories in such a way that any viewing angle can be handled without a repartitioning of the data. In addition, the rendering must meet the following requirements.
The quality of the final image must be comparable to that which would have been generated in a single-pass rendering of the volume. There should be no visually disturbing artifacts due to the combining of partial results from multiple rendering passes. The rendering engine should transparently handle the rendering of partitioned volumes, including special effect rendering requirements such as cropping, cut-planes, and cursors that may extend or operate across partition boundaries. It should also be possible to obtain the intermediate results of the independent renderings.
SUMMARY OF THE INVENTION
The invention provides a method and apparatus for shear-warp rendering a volume data set that is partitioned into smaller parts. The smaller parts can then be processed independently, either in parallel or serially, to overcome spatial or temporal constraints.
The volume data set is stored in a memory as an arrangement of voxels using object coordinate system. The voxels of the volume data set are object partitioned, relative to the object coordinate system, into a plurality of axis aligned sets of voxels. The axis aligned sets of voxels can have arbitrary dimensions.
Selected ones of the axis aligned sets of voxels are independently rendered as pixels in intermediate baseplanes. There is one intermediate baseplane for each selected set of axis aligned voxels. The intermediate baseplanes are then combined and warped to an image.
As an advantage of the invention, an arbitrary viewing direction can be selected without repartitioning the image or object. In another aspect, the combining and warping is performed either after all of the intermediate baseplanes have been rendered, or incrementally after each individual intermediate baseplane has been rendered.
To support view independence, duplication of rendering samples is avoided at the edge of volume partitions.
REFERENCES:
patent: 6243098 (2001-06-01), Lauer et al.
patent: 6262740 (2001-07-01), Lauer et al.
patent: 6310620 (2001-10-01), Lauer et al.
patent: 6313841 (2001-11-01), Ogata et al.
Amin et al.; “Fast Volume Rendering Using an Efficient, Scalable Parallel Formulation of the Shear-Warp Algorithm”; 1995 Parallel Rendering Symposium; Oct. 30-31, 1995; pp. 7-14.
Philippe Lacroute; “Real-Time Volume Rendering on Shared Memory Multiprocessors Using the Shear-Warp Factorization”; 1995 Parallel Rendering Symposium; Oct. 30-31, 1995; pp. 15-22.
Bhatia Vishal C.
Hardenbergh Jan C.
Knittel James M.
Lauer Hugh C.
Pfister Hanspeter
Brinkman Dirk
Terarecon, Inc.
Vo Cliff N.
LandOfFree
Rendering a shear-warped partitioned volume data set does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Rendering a shear-warped partitioned volume data set, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Rendering a shear-warped partitioned volume data set will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2977531