Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
2000-11-17
2004-01-20
Vo, Cliff N. (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
C345S419000
Reexamination Certificate
active
06680735
ABSTRACT:
FIELD OF THE INVENTION
The present invention is related to the field of computer graphics, and in particular to rendering volumetric data sets using a parallel pipelined hardware rendering engine.
BACKGROUND OF THE INVENTION
Volume rendering is often used in computer graphics applications where three-dimensional data need to be visualized. The volume data can be scans of physical or medical objects, or atmospheric, geophysical, or other scientific models where visualization of the data facilitates an understanding of the underlying real-world structures represented by the data.
With volume rendering, the internal structure, as well as the external surface features of physical objects and models are visualized. Voxels are usually the fundamental data items used in volume rendering. A voxel is data that represent a particular three-dimensional portion of the object or model. The coordinates (x, y, z) of each voxel map the voxels to positions within the represented object or model.
A voxel represents one or more values related to a particular location in the object or model. For a given prior art volume, the values contained in a voxel can be a specific one of a number of different parameters, such as density, tissue type, elasticity, or velocity. During rendering, the voxel values are converted to color and opacity (RGB&agr;) values, according to the voxel intensity values, which can be projected onto a two-dimensional image plane for viewing.
One frequently used technique during rendering is ray-casting. There, a set of imaginary rays are cast through the voxels. The rays originate from some view point or image plane. The voxels are sampled at points along the rays, and various techniques are known to convert the sampled values to pixel values. In either case, processing of the volume may proceed in a back-to-front, or front-to-back order.
One traditional technique of ray-casting for volume rendering is based on a shear-warp algorithm of Lecroute and Levoy, see Lacroute and Levoy, “
Fast Volume Rendering Using a Shear
-
Warp Factorization of the Viewing Transformation
,” Computer Graphics, 28(4), 451-458, August 1994.
That technique has the advantage of stepping through a volume data set in an order closely related to the order in which the voxels are stored. This order is called “object order.” Object order has two advantages. It allows volume memory to be accessed in an optimal way, and it requires only three multiplications by interpolation weights to determine a sample value. As a result, volume data can be fetched and processed at a maximum rate. It was this ray casting technique that first made real-time, interactive volume rendering possible.
The shear-warp technique achieves its performance by casting rays according to a grid defined by the voxels on a “base plane” of the volume data set. The base plane is a plane parallel to a face or surface of the volume most nearly parallel to the image plane. In the shear-warp technique, rays cast through the volume are positioned on a grid of rows and columns parallel to the rows and columns of voxels in the volume itself. This orderly row-and-column arrangement is what makes object order rendering efficient, particularly for memory accesses and interpolating sample values.
However, the resulting image is aligned to the base plane, and not to the image plane. Moreover, except in special cases, the resulting base plane aligned image is distorted from the desired, final image of the volume object. Therefore, the shear-warp technique is really a two-stage technique, the first stage, called the “shear” stage”, renders the image to the base plane while the second stage, called the “warp” stage, undistorts the base plane image and positions it correctly onto the image plane.
The warp stage is, in effect, a resampling of the base plane image to produce the final image on the image plane. As a result, there is, in any practical implementation, a degradation of image quality from what could be obtainable.
The warp stage is not difficult, and it can easily be accomplished using, for example, the texture map functions of a conventional 3D polygon graphics system such as OpenGL™. However, not all application environments are designed for systems that include such graphics capability. In those cases, the need to perform the warp stage requires a cumbersome addition to the system design or an extra software module with challenging performance requirements. Either way, complexity of the system is increased.
An alternate method of ray-casting is known as “image order.” In this method, rays are cast through the volume data set from pixels on the final image plane. This produces a correct image directly, without distortion and without the warp stage. The resulting image is typically of a higher quality than can be obtained from the shear-warp technique. The reason that image order rendering produces higher image quality is that each pixel on the final image plane is generated directly from the single ray that passes through it. In object order, by contrast, each pixel in the final image plane is synthesized from a number of nearby pixels on the base plane image. Hence, in object order there are two instances of resampling to degrade the quality of the image.
However, image order rendering comes with a penalty. Volume data cannot be fetched as efficiently from memory as with the shear-warp technique. Also, interpolating sample values takes seven multiplications by interpolation weights, instead of the three multiplications required in object order. Therefore, image order methods are significantly slower than object order techniques, so much so, that the real-time interactive volume rendering is not possible but for the smallest volume data sets. Practical interactive applications, such as real-time medical imaging, are very difficult, if not impossible, with prior art image order techniques.
Another issue in rendering concerns embedded images of polygon objects and other objects. With the image order rendering method, embedding such objects and images is straightforward. The objects are simply drawn with a traditional 3D graphics system onto the image plane at the same pixel resolution as the final volume rendered image. There is no resampling of the embedded polygons or images, and therefore, no loss of image quality as a result of the embedding.
In contrast, because the object order volume rendering technique (shear-warp) generates a distorted image on a base plane, the embedded objects must also be drawn with an equivalent distortion on the base plane. The rendered image with the embedded polygons is then warped during the warp stage to the final image. This warp stage seriously deteriorates the image quality of the drawn polygons, especially when the embedded geometry includes sharp edges.
It would be desirable to obtain the superior quality of image order volume rendering while enjoying the superior performance of object order rendering.
SUMMARY OF THE INVENTION
The invention provides a system and method for rendering a volume data set composed of voxels onto an image plane composed of pixels by casting a ray through each pixel of the image plane. A surface of the volume data set is selected as a base plane. Sample points are defined along each ray so that the sample points lie in planes parallel to the base plane. Voxels are fetched from volume memory in slices parallel to the base plane to enhance performance. Voxels adjacent to each sample point are interpolated to determine a sample value for each sample point, and the sample values of each ray are combined to determine a pixel value for each pixel.
REFERENCES:
patent: 6072496 (2000-06-01), Guenter et al.
patent: 6208347 (2001-03-01), Migdal et al.
patent: 6236405 (2001-05-01), Schilling et al.
patent: 6256603 (2001-07-01), Celniker
Bhatia Vishal C.
Lauer Hugh C.
Lussier Jeffrey
Seiler Larry D.
Wu Yin
Blakely , Sokoloff, Taylor & Zafman LLP
TeraRecon, Inc.
Vo Cliff N.
LandOfFree
Method for correcting gradients of irregular spaced graphic... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for correcting gradients of irregular spaced graphic..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for correcting gradients of irregular spaced graphic... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3231235