Early ray termination in a parallel pipelined volume...

Details Early ray termination in a parallel pipelined volume... Early ray termination in a parallel pipelined volume...

1999-10-01

2003-11-25

Nguyen, Phu K. (Department: 2671)

Computer graphics processing and selective visual display system

Computer graphics processing

Three-dimension

Reexamination Certificate

active

06654012

ABSTRACT:

FIELD OF THE INVENTION
This invention relates generally to rendering volume data sets, and more particularly, the invention relates to early termination of rays cast through volume data sets.
BACKGROUND OF THE INVENTION
Volume graphics is the subfield of computer graphics that deals with visualizing objects or models represented as sampled data in three or more dimensions, i.e., a volume data set. These data are called volume elements, or “voxels.” The voxels store digital information representing physical characteristics of the objects or models being studied. For example, voxel values for a particular object or model 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 that object or model.
Volume rendering is that part of volume graphics concerned with the projection of the volume data set as two-dimensional images for purposes of printing, display on computer terminals, and other forms of visualization. By assigning color and transparency values to particular voxel data values, different views of the exterior and interior of an object or model can be rendered.
For example, a surgeon needing to examine 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. The resulting image then reveals the condition of the ligaments, tendons, bones, etc. which are hidden from view prior to surgery, thereby allowing for better surgical planning, shorter surgical operations, less surgical exploration and faster recoveries. In another example, a mechanic using a tomographic scan of a turbine blade or welded joint 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 otherwise is hidden from the human eye.
Real-time volume rendering is the projection and display of the volume data set as a series of images in rapid succession, typically at thirty frames per second or faster. This makes it possible to create the appearance of moving pictures of the object, model, or system of interest. It also enables a human operator to interactively control the parameters of the projection and to manipulate the image, while providing to the user immediate visual feedback. Projecting hundreds of millions of voxel values to an image requires enormous amounts of computing power. Doing so in real time requires substantially more computational power.
Further background on volume rendering is included in a Doctoral Dissertation entitled “Architectures for Real-Time Volume Rendering” submitted by Hanspeter Pfister to the Department of Computer Science at the State University of New York at Stony Brook in December 1996, and in U.S. Pat. No. 5,594,842, “Apparatus and Method for Real-time Volume Visualization.” Additional background on volume rendering is presented in a book entitled “Introduction to Volume Rendering” by Barthold Lichtenbelt, Randy Crane, and Shaz Naqvi, published in 1998 by Prentice Hall PTR of Upper Saddle River, N.J.
PRIOR ART VOLUME RENDERING PIPELINES
In one prior art volume rendering system, the rendering pipelines are configured as a single integrated chip, U.S. patent application Ser. No. 09/315,742 “Volume Rendering Integrated Circuit.”
In a method called “ray-casting,” rays are cast through the volume data set, and sample points are calculated along each ray. Red, green, and blue color values, and an opacity value (also called alpha value) is determined for each sample point by interpolating voxels near the sample points. Collectively, the color and opacity values are called RGBA values. These RGBA values are typically composited along each ray to form a final pixel value, and the pixel values for all of the rays form a two-dimensional image of the three-dimensional object or model.
In some systems based on the ray-casting method, one ray is cast through the volume array for each pixel in the image plane. In other systems, rays are cast according to a different spacing, then the final image is resampled to the pixel resolution of the image plane. In particular, the prior art systems cited above uses the well-known Shear-Warp algorithm of Lecroute et al. as described in “Fast Volume Rendering Using Shear-Warp Factorization of the Viewing Transform,” Computer Graphics Proceedings of SIGGRAPH, pp. 451-457, 1994. There, rays are cast from uniformly spaced points on a plane parallel to one of the faces of the volume array. This plane is called the base plane, and the points are aligned with axes of the base plane.
FIG. 1
depicts a typical volume rendering pipeline
100
of the prior art, such as described in U.S. patent application Ser. No. 09/353,679 “Configurable Volume Rendering Pipeline.” Voxels are read from a volume memory
110
and passed through a gradient estimation stage
120
in order to estimate gradient vectors. The voxels and gradients are then passed through interpolation stages
130
in order to derive their values at sample points along rays, and through classification stages
140
in order to assign RGBA color and opacity values. The resulting RGBA values and interpolated gradients are then passed to illumination stages
150
, where highlights and shadows are added. The values are then clipped and filtered in stages
160
in order to remove portions of the volume or otherwise modulate the image of the volume. Finally, the values are composited in stages
170
to accumulate all of the RGBA values for each ray into final pixel values for writing to a pixel memory
180
.
It should be noted that the gradient estimation stages
120
, interpolation stages
130
, and classification stages
140
can be connected in any order, depending upon the requirements of the application. This architecture is particularly suited to parallel implementation in a single integrated circuit, as described in the above referenced Patent Applications.
As an alternative to compositing a two-dimensional image, RGBA values can be written out as a three-dimensional array, thereby creating a new volume data set, which can be rendered with different transfer functions. In other words, the final images is the result of progressive rendering cycles on an evolving volume data set.
Partition Into Sections
One of the challenges in designing a volume rendering engine as a single semiconductor integrated circuit is to minimize the amount of on-chip memory required to support the functions of the volume rendering pipelines.
As shown in
FIG. 2
for the shear-warp algorithm implemented of the prior art, the amount of on-chip memory is directly proportional to an area of a face
210
of a volume data set
200
that is most nearly perpendicular to a view direction
220
, that is the xy-face as illustrated in FIG.
2
. In the prior art, this memory was reduced by partitioning the volume into sections, and by rendering the volume a section at a time.
FIG. 2
illustrates the partition of the volume into sections
230
in both the x-and y-directions. Each section is defined by an area on the xy-face of the volume array and projects through the entire array in the z-direction. These sections are known as “axis-aligned sections” because they are parallel to the z-axis of the array. This partition reduces the requirement for on-chip memory to an amount proportional to the area of the face of the section in the xy-plane rather than to that of the entire volume. It also makes it possible to design a circuit capable of rendering arbitrarily large volume data sets with a fixed amount of on-chip memory.
One consequence of partitioning the volume data set into axis-aligned sections is that when rays traverse the volume at arbitrary angles, the rays cross from one section to another. For example, a ray
240
parallel to view direction
220
enters into section
231
, crosses section
232
, and then exits from

Affiliated with

Also associated with

Rating

Early ray termination in a parallel pipelined volume... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Early ray termination in a parallel pipelined volume..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Early ray termination in a parallel pipelined volume... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3143293