Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
1997-08-20
2001-08-21
Zimmerman, Mark (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
C345S440000
Reexamination Certificate
active
06278459
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to computer image generation and more particularly to methods for generating two-dimensional displays of an image based on three-dimensional image data.
Many imaging systems produce data representing physical entities or properties in three-dimensional space. Examples include CAT scans, MRI scans, ultrasound images and seismic test images. The process of converting the three-dimensional arrays of data into two dimensional image displays is referred to as volume-rendering. The term voxel processing is also used, because the 3-D space is ordinarily broken down into small volumes, referred to as voxels. Each voxel has optical properties, ordinarily expressed in terms of opacity (or its inverse, transparency) and color (or grey-scale in black and white imaging systems). These properties contribute to the overall image when it is to be computed by mathematical projection and sampling and converted into pixels to be displayed on a two dimensional display surface.
Volume rendering employs a class of algorithms for visualizing or representing three-dimensional grids of data. Such algorithms are based on the physics of light interaction with modeled particles in a volume. The beginnings of a particle model for graphics rendering were developed by Blinn (Bli82) and extended by Kajiya et al. (KH84) to nonhomogeneous densities of particles. The common algebraic technique for combining ray samples is compositing, derived separately by Blinn (Bli82) and Porter et al. (PD84). Modem direct volume rendering algorithms are largely based on Levoy (Lev88), Drebin et al. (DCHB88), Sabella (Sab88), and Upson et al. (UK88). Up-to-date surveys may be found in Max (Max95) and Kaufman (Kau91).
Levoy in (Lev88) proposed a volume rendering pipeline that classifies and shades voxels before interpolation. This approach can lead to two computational advantages compared to classifying sample points interpolated from voxel data. First, classification can be treated as a preprocess and need not be repeated per view. Second, the number of voxels in a data set can be significantly less than the number of sample points when computing a view, resulting in lower classification cost. Commonly-assigned U.S. Pat. No. 5,557,711 discloses a multiprocessor and parallel method for volume rendering by preprocessing transparency and luminescence signals in subsets or regions of an object space and then compositing the signals from such regions for the object space as a whole. Unfortunately, classification first followed by interpolation as described in (Lev88, Lev89, Lev90) erroneously interpolates shaded color values independently from opacity.
The wide use of volume rendering software from the seminal Levoy references, and the inherent complexity of the underlying model, have meant that implementations of volume rendering can include shading artifacts due to improper classification, shading, and interpolation. Drebin et al. (DCH88) specify opacity weighting of the colors. Others have noted the difficulties associated with opacity and color, notably Wilhelms (WG91) and Blinn (Bli94), but not as it relates to resampling of shaded color values in volume ray tracing. Wilhelms notes that different answers will result if one interpolates colors versus data, but the former may be faster. Blinn discusses the issues in filtering an image that has opacities at each pixel. He shows an example of overlaying and downsampling, and the different answer that results if downsampling is done first without opacity weighting the colors. He calls the opacity weighted colors “associated colors.” Wilhelms, Van Gelder et al. (Wil91,VGK96) discuss the issues in interpolating colors instead of materials, and resulting artifacts, but do not clarify that additional artifacts result if opacity weighted colors are not properly interpolated.
Accordingly, a need remains for a better way to process voxel data to interpolate color values in proper relation to opacity values, so as to avoid introducing artifacts.
SUMMARY OF THE INVENTION
In order to solve the need for an accurate two-dimensional representation of a three-dimensional image, the invention provides an improved method and apparatus for processing voxel data which avoids the problem of color artifacts coming from zero opacity regions.
Particularly, according to the invention, a computer system has a processing subsystem, a memory and a display for displaying an image in a two-dimensional array of pixels. The three-dimensional image is stored in the computer memory as a three-dimensional data array comprising object data values associated with a plurality of sample points in a three-dimensional space. A method for generating a pixel color value to be displayed in a subset of the array of pixels as a part of the two-dimensional representation comprises the steps of, first, processing the object data values to determine voxel colors C and voxel opacities &agr; for the plurality of sample points. Second, the voxel colors are opacity weighted to produce a set of opacity weighted colors
{tilde over (C)}
. Third, the voxel opacities &agr; and the opacity weighted colors
{tilde over (C)}
from each sample point are composited to form the two-dimensional view. In this manner, artifacts resulting from zero opacity areas contributing to the overall color are eliminated because of the opacity weighting performed prior to compositing.
An apparatus for mathematically calculating and visually displaying a two-dimensional view of a three-dimensional image is also provided. In this apparatus, a two-dimensional array of pixels for representing the three-dimensional image is created by generating a pixel color value to be displayed in a subset of the array of pixels. The apparatus comprises a memory for storing the three-dimensional image as a three-dimensional data array comprising object data values associated with a plurality of sample points in a three-dimensional space. A central processing unit (CPU) is provided for processing the object data values to determine voxel colors C and voxel opacities a for the plurality of sample points. The processing unit must also be capable of mathematically calculating a set of opacity weighted colors
{tilde over (C)}
by opacity weighting the voxel colors. A compositor composites the voxel opacities &agr; and the opacity weighted colors
{tilde over (C)}
from each sample point to form the two-dimensional view, and a display unit visually displays the two-dimensional view.
The foregoing and other objects, features and advantages of the invention will become more readily apparent from the following detailed description of a preferred embodiment of the invention which proceeds with reference to the accompanying drawings.
REFERENCES:
patent: 5339386 (1994-08-01), Sodenberg et al.
patent: 5457482 (1995-10-01), Rhoden et al.
patent: 5745665 (1998-04-01), Pasco
patent: 5847711 (1998-12-01), Kaufman et al.
“Interactive Computer Graphics: A top-down Approach with OpenGL” —Edward Angel, Section 10.8.2, 1997.*
Hanspeter Pfister and Arie Kaufman, “Cube 4—A Scalable Architecture for Real-Time Volume Rendering”, Symposium on Volume Visualization, pp. 47-54, ACM, Oct. 1996.
Marc Levoy, “Display of Surfaces from Volume Data”, IEEE Computer Graphics and Applications, pp. 29-37, May 1988.
Marc Levoy, “Efficient Ray Tracing of Volume Data”, ACM Transactions on Graphics, vol. 9, No. 3, pp. 245-261, Jul. 1990.
Philippe Lacroute and Marc Levoy, “Fast Volume Rendering Using a Shear-Warp Factorization of the Viewing Transformation”, SIGGRAPH '94, Computer Graphics Proceedings, ACM SIGGraph, pp. 451-458, Jul. 1994.
Graphics and Visualization Lab, Army High Performance Computing Research Center, Minneasota Supercomputer Center, “All About Bob”, http://www.arc.umn.edu/GVL/Software/bob.html.
Todd Kulick, “Building and OpenGL volume Renderer”, http://reality.sgi.com/kulick-engr/devnews/volren/article.htm.
William H. Press, Saul A. Teukolsky, William T. Vetterling, Brian P. Flannery, “Numerical Recipes in C: The Art of Scientific Co
Goss Michael E.
Malzbender Thomas
Hewlett--Packard Company
Padmanabhan Manlo
Zimmerman Mark
LandOfFree
Opacity-weighted color interpolation for volume sampling does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Opacity-weighted color interpolation for volume sampling, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Opacity-weighted color interpolation for volume sampling will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2522697