Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
1998-04-13
2001-11-06
Vo, Cliff N. (Department: 2772)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
C345S427000
Reexamination Certificate
active
06313841
ABSTRACT:
BACKGROUND OF THE INVENTION
This invention relates to volume rendering systems and more particularly to a volume rendering system capable of rendering volumetric datasets for perspective visual projection using parallel pipeline processing.
Given a set of viewing parameters, a typical volume rendering system renders a volumetric dataset or simply a volume to produce a two-dimensional image by casting parallel rays into the dataset, computing color values at sample points along the rays, and accumulating them to determine the final pixel values. Popular volumetric datasets include medical datasets, such as CT and MRI data, and scientific datasets generated by computer simulation. A volume described by the dataset consists of elements called voxels, each representing some property of the dataset. Voxels are usually defined at intersections of a three-dimensional regular grid and stored in a three-dimensional memory array indexed by voxel position.
One of the major problems with rendering such a volume is the expensive computing cost due to the large number of voxels to process. A typical rendering process for raycasting computes, in software, the color values of samples along each ray by using some form of interpolation with surrounding voxels and accumulates these values to determine the final color of the ray. The rendering cost is in direct proportion to the total number of voxels. An exemplary dataset may be described as an N×N×N matrix, with each three-dimensional coordinate having an associated voxel. Letting N=256 in a first example, there are 256
3
, or 16 million, voxels. Since rays are projected in relatively close proximity to provide sufficient detail in the rendered image, each voxel will be utilized k times on average in the calculation of ray samples, for a total of 16k million times.
Conventional volume rendering systems implemented by software suffer from a performance problem, and are thus unable to perform realtime rendering, because of the large number of operations to perform. There are some methods used to reduce the computing cost. Early ray termination is one example, which terminates a ray when additional samples along the ray are not expected to contribute much to the final color of the ray. Coherency encoding is another example, which encodes spatial coherency in the dataset to avoid processing voxels in empty regions. The performance enhancement obtained by these methods, however, depends on the dataset. It is very difficult for a software-based volume rendering system to achieve the realtime rendering performance independent of the voxel values in the datasets. Some software rendering systems are designed to run on high-performance computers. However, their still suffer from the performance problem, because the number of operations per voxel is not large enough to statistically justify the expensive memory access per voxel.
Some special-purpose hardware systems have been developed to achieve realtime performance by accelerating the volume rendering process. Several pipelines are used, each for rendering operations for one ray. The pipelines generate images for parallel projection, in which the rays are cast into the volume from a point at infinity and therefore all parallel. With this form of parallel ray projection, rendering operations are regular and amenable to parallel pipeline processing in hardware; since the rays are parallel, the distance between the sample locations of two neighboring rays at the same distance from some reference plane is constant, and the offset for each sample location from a respective reference voxel location is also constant. This allows the hardware pipelines, each responsible for a ray, to perform the same sampling and rendering operations, albeit on different combinations of voxels, because the offsets of the sample locations determine the weights for interpolation in sampling operations, and these offsets are the same for each ray and therefore for each pipeline.
Perspective projection is another type of projection, in which rays are cast into a volume from a point, called the center of projection (“COP”), at some finite distance from the volume. With this type of projection, volumes closer to the center of projection appear larger in the images than those far from the center of projection. Because of this property, the generated images are more natural to human eyes than those generated by parallel projection. Since the rays are not parallel in perspective projection, rendering operations are not regular and thus not amenable to parallel pipeline processing in hardware. Specifically, the distance between the sample locations of two neighboring rays changes as the distance from the sample locations to a reference plane changes; the offsets of the sample locations from the respective reference voxel locations also change. This requires unique sampling and rendering operations at each hardware pipeline responsible for a different ray.
For instance, in one prior art configuration for perspective rays, hardware pipelines are organized to compute different rays such that each pipeline, responsible for a first ray, computes all the samples along the ray to determine its final color. When a pipeline finishes the first ray, it processes another ray using similar operations. The major problem in this configuration is that one voxel is typically accessed by multiple pipelines, increasing the total number of memory accesses and memory contentions. To alleviate this problem, the hardware pipelines can be organized such that they read a voxel once and retain it until all the samples requiring that voxel are computed. In this organization each pipeline interleaves the computation of samples for different rays. A first pipeline transfers a voxel to a neighboring pipeline after using it for sample interpolation at one pipeline clock. At the next pipeline clock, the first pipeline receives a different voxel from a neighboring pipeline for the similar sample interpolation for the same ray or a different ray, depending on the operation type. Examples of such an organization of hardware pipelines can be found in Hanspeter Pfister, “Architectures for Real-Time Volume Rendering,” Ph.D. Thesis, Department of Computer Science, State University of New York at Stony Brook, December 1996.
The above-mentioned perspective projection problem is especially serious for this type of hardware pipeline organization, because the pipelines are organized to compute different samples for different rays with a regular sequence of voxels from memory. In particular, some pipelines may not have samples to compute using a given voxel because of the increasing distance between the samples of the neighboring rays. This irregularity in applying parallel pipeline processing techniques to perspective projections has not been addressed in conventional hardware pipeline systems.
BRIEF SUMMARY OF THE INVENTION
In order to overcome the disadvantages of conventional volume rendering systems, the present invention comprises a volume rendering system and method with a resampling module which includes a set of resampling units to resample voxels to generate samples along perspective rays cast from the center of projection, and a rendering module which includes rendering units to generate pixels for the baseplane image. The resampling units thus regularize the calculations required for perspective projections by parallizing perspective rays, thus enabling the realtime processing capabilities of parallel-pipeline processing formerly only available with parallel projections.
The volume rendering system is provided having an enhanced capability for producing a realtime image of a volume on a display screen. Voxels describing the volume are read from a voxel memory and are re-sampled in the generation of samples along perspective rays cast from a center of projection. A level of detail value is utilized in determining a number of voxels to be utilized in calculating the sample. Weights are assigned to each voxel contribution as part of this calculation. Co
Lauer Hugh C.
Ogata Masato
Ohkami Takahide
Brinkman Dirk
Terarecon, Inc.
Vo Cliff N.
LandOfFree
Parallel volume rendering system with a resampling module... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Parallel volume rendering system with a resampling module..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Parallel volume rendering system with a resampling module... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2610845