Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
1999-05-25
2001-07-17
Vo, Cliff N. (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
Reexamination Certificate
active
06262740
ABSTRACT:
FIELD OF INVENTION
This invention relates to volume graphics and more particularly to a method and apparatus for processing voxel-based data in real time and for creating visual images of objects represented by the data.
BACKGROUND OF THE INVENTION
Volume graphics is the subfield of computer graphics that deals with the visualization of objects or phenomena represented as sampled data in three or more dimensions. These samples are called volume elements, or “voxels,” and contain digital information representing physical characteristics of the objects or phenomena being studied. For example, voxel data for a particular object may represent density, type of material, temperature, velocity, or some other property at discrete points in space throughout the interior and in the vicinity of the object.
Voxel-based representations of objects occur in many situations and applications. For example, tomographic scans and nuclear magnetic resonance scans of a human body or industrial assembly produce three dimensional arrays of data representing the density and type of the material comprising the body or object. Likewise, seismic data collected from earthquakes and controlled explosions is processed into three dimensional arrays of data representing the types of soil and rock beneath the surface of the earth. In pre-natal health care, ultrasound scans of a human fetus in the womb produce 3-D sampled data for non-invasive examination and diagnostic purposes. Still another example is the modeling of the flow of air over an aircraft wing or through a jet engine, which also results in discrete samples of data at points in three dimensional space that can be used for design and analysis of the aircraft or engine.
It is natural to want to see images of objects represented by voxels. In the past, two methods have been available for this purpose. One method is to construct a series of parallel two-dimensional image slices, each representing a slightly different cross section of the object being viewed. This is the method typically used by radiologists when viewing computed tomography scans or nuclear magnetic resonance scans of the human body. Radiologists are trained to construct three-dimensional mental pictures of the internal organs of the body from these series of two-dimensional images. The slices are, in general, parallel to one of the primary dimensions or axes of the body, so that they represent the “sagittal,” “axial,” and “coronal” views that are familiar to radiologists. This method of visualizing voxel-based data is difficult, requires years of training, and is prone to uncertainty, even by the most expert practitioners.
Another method is to convert voxel data into representations suitable for computer graphics systems to display. Most computer graphic systems today are designed to display surfaces of objects by subdividing those surfaces into small triangles or polygons. These triangles are assigned colors and levels of transparency or opacity, then converted into pixels, that is picture elements, and projected onto the computer screen. Triangles corresponding to surfaces in the foreground obscure those corresponding to surfaces in the background. Triangles can also be colored or painted with textures and other patterns to make them look more realistic. Additional realism is made possible by simulating the position and effects of lights, so that highlights and shadows appear on the resulting image. The art and science of this kind of graphics system is well-developed and described by a large body of literature such as the textbook “Computer Graphics: Principles and Practice,” 2
nd
edition, by J. Foley, A. vanDam, S. Feiner, and J. Hughes, published by Addison-Wesley of Reading, Mass., in 1990.
This kind of polygon-based graphics system is especially suitable for displaying images of objects that are represented as computer models of their surfaces, such as architectural or mechanical drawings. However, it is less appropriate for visualizing objects represented by 3-D sampled data or voxels, because the process of converting the samples to triangles or polygons is itself computationally expensive. Many algorithms exist for performing the conversion from voxels to polygons, including the famous Marching Cubes algorithm described by W. E. Lorensen and H. E. Cline in a paper entitled “Marching Cubes: A high-resolution 3D surface construction algorithm,” presented in
Computer Graphics
, the Proceedings of the 1987 SIGGRAPH Conference, pages 163-169. All of these algorithms suffer the problem of losing detail of the surface, something that would be intolerable in applications such as medical imaging and others.
In recent years, an alternative method has emerged called volume rendering. This method is a form of digital signal processing in which the individual voxels of a voxel-based representation are assigned colors and levels of transparency or opacity. They are then projected on a two-dimensional viewing surface such as a computer screen, with opaque voxels in the foreground obscuring other voxels in the background. This accumulation of projected voxels results in a visual image of the object. Lighting calculations can be done on the individual voxels to create the appearance of highlights and shadows in a similar manner to that of conventional computer graphics.
By changing the assignment of colors and transparency to particular voxel data values, different views of the exterior and interior of an object can be seen. For example, a surgeon needing to examine the ligaments, tendons, and bones of a human knee in preparation for surgery can utilize a tomographic scan of the knee and cause voxel data values corresponding to blood, skin, and muscle to appear to be completely transparent. In another example, a mechanic using a tomographic scan of a turbine blade or weld in a jet engine can cause voxel data values representing solid metal to appear to be transparent while causing those representing air to be opaque. This allows the viewing of internal flaws in the metal that would otherwise be hidden from the human eye.
The process of creating a viewable image from computer data is called “rendering,” and the process of creating a viewable image from voxel data is called “volume rendering.” The mechanism for mapping the data values of individual voxels to colors and transparencies is called a “transfer function.”
a) Projection of Voxel Data
There are a number of techniques to take the data points or voxels representing an object and project them onto a flat viewing surface such as a computer screen. In each of these techniques, an object to be viewed is positioned relative to the viewing surface by translating the three dimensional sampled data representing that object to the spatial coordinates of the space in front of or behind the viewing surface. The techniques are different methods of computing the color and intensity of the light at discrete points or “pixels” on that viewing surface.
One technique is to compute a series of fast Fourier transforms of the voxel data, combine them, then compute the inverse Fourier transform to obtain the resulting two-dimensional image. This is described by T. Malzbender in U.S. Pat. No. 5,414,803 entitled “Method Utilizing Frequency Domain Representation for Generating Two-Dimensional Views of Three-Dimensional Objects.”
A second technique called “splatting” was described by L. A. Westover in a Doctoral Dissertation entitled “Splatting: A Parallel, Feed-Forward Volume Rendering Algorithm” presented to and published by the Department of Computer Science of the University of North Carolina in July 1991, Technical Report number TR91-029. In the splatting technique, each individual voxel of a set of three-dimensional sampled data is projected in the direction of the eye of the viewer. The colors and transparency of the projected voxel are mathematically combined with the pixels of the viewing surface in the immediate region surrounding the point where that projection intersects that computer screen. When all voxels are thus accumulated, the resulting ima
Lauer Hugh C.
Osborne Randy B.
Pfister Hanspeter
Brinkman Dirk
Terarecon, Inc.
Vo Cliff N.
LandOfFree
Method for rendering sections of a 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 Method for rendering sections of a volume data set, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for rendering sections of a volume data set will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2550348