Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
2000-12-20
2003-12-16
Jankus, Almis R. (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
Reexamination Certificate
active
06664961
ABSTRACT:
FIELD OF THE INVENTION
The present invention is a system for providing three-dimensional computer graphics. More particularly, the present invention is a system that accelerates the processing of volume data for real-time ray casting of a three-dimensional image and a method thereof.
BACKGROUND OF THE INVENTION
Volume rendering projects a volume dataset onto a two-dimensional (2D) image plane or frame-buffer. Volume rendering can be used to view and analyze three-dimensional (3D) data from various disciplines, such as biomedicine, geo-physics, computational fluid dynamics, finite element models and computerized chemistry. Volume rendering is also useful in the application of 3D graphics, such as Virtual Reality (VR), Computer Aided Design (CAD), computer games, computer graphics special effects and the like. The various applications, however, may use a variety of terms, such as 3D datasets, 3D images, volume images, stacks of 2D images and the like, to describe volume datasets.
As schematically depicted in
FIG. 1
, a volume dataset is typically organized as a 3D array of samples which are often referred to as volume elements or voxels. The volume dataset can vary in size, for example from 128
3
to 1024
3
samples, and may also be non-symmetric, i.e., 512×512×128. The samples or voxels can also vary in size. For example, a voxel can be any useful number of bits, for instance 8 bits, 16 bits, 24 bits, 32 bits or larger, and the like.
The volume dataset can be thought of as planes of voxels or slices. Each slice is composed of rows or columns of voxels or beams. As depicted in
FIG. 1
, the voxels are uniform in size and regularly spaced on a rectilinear grid. Volume datasets can also be classified into non-rectilinear grids, for example curvilinear grids. These other types of grids can be mapped onto regular grids.
Voxels may also represent various physical characteristics, such as density, temperature, velocity, pressure and color. Measurements, such as area and volume, can be extracted from the volume datasets. A volume dataset may often contain more than a hundred million voxels thereby requiring a large amount of storage. Because of the vast amount of information contained in a dataset, interactive volume rendering or real-time volume rendering defined below requires a large amount of memory bandwidth and computational throughput. These requirements often exceed the performance provided by typical modern workstations and personal computers.
Volume rendering techniques include direct and indirect volume rendering. Direct volume rendering projects the entire dataset onto an image-plane or frame buffer. Indirect volume rendering extracts surfaces from the dataset in an intermediate step, and these projected surfaces are approximated by triangles and rendered using the conventional graphics hardware. Indirect volume rendering, however, only allows a viewer to observe a limited number of values in the dataset (typically 1-2) as compared to or all of the data values contained therein for direct volume rendering.
Direct volume rendering that is implemented in software, however, is typically very slow because of the vast amount of data to be processed. Moreover, real-time direct (interactive) volume rendering (RTDVR) involves rendering the entire dataset at over 10 Hz, however, 30 Hz or higher is desirable. Recently, RTDVR architectures have become available for the personal computer, such as VolumePro, which is commercially available from RTVIZ, a subsidiary of Mitsubishi Electronic Research Laboratory. VIZARD II and VG-Engine are two other RTDVR accelerators that are anticipated to be commercially available. These accelerators may lower the cost of interactive RTDVR and increase performance over previous non-custom solutions. Moreover, they are designed for use in personal computers. Previous solutions for real-time volume rendering used multi-processor, massively parallel computers or texture mapping hardware. These solutions are typically expensive and not widely available due to, for instance, the requirement for parallel computers. Alternatively, these solutions generate lower quality images by using texture-mapping techniques.
Although accelerators have increased the availability and performance of volume rendering, a truly general-purpose RTDVR accelerator has yet to emerge. Current accelerators generally support parallel projections and have little or no support for perspective projections and stereoscopic rendering. These different projections are illustrated in FIG.
2
. Stereoscopic rendering is a special case where two images, generally two perspective images, are generated to approximate the view from each eye of an observer. Stereoscopic rendering typically doubles the amount of data to be processed to render a stereoscopic image. Moreover, current accelerators also require high memory bandwidths that can often exceed 1 Gbyte per second for a 256
3
dataset.
Furthermore, these current accelerators are typically either image-order or object-order architectures. An image-order architecture is characterized by a regular stepping through image space and the object-order architecture is characterized by a regular stepping through object space. Image-order ray casting architectures may support algorithmic speed-ups, such as space leaping and early ray termination, and perspective projections. Object-order architectures tend to provide more hardware acceleration and increased scalability. Object-order architectures, however, have not generally provided algorithmic acceleration. The trade-off between these various limitations are typically either (i) good parallel rendering performance and no support for perspective projections or (ii) good algorithmic acceleration and little hardware acceleration and vice versa.
The voxel-to-pipeline topologies of typical image-order and object-order accelerators are shown schematically in
FIGS. 3 and 4
, respectively. Image-order architectures must access several voxels from a volume memory per processor. This typically causes a bottleneck in achievable hardware acceleration and thereby limits the number of useful processors. For example, as illustrated in
FIG. 3
, a typical image-order architecture has an 8-to-1 bottleneck for each image-order pipeline. Although algorithmic acceleration for the reconstruction, classification, shading and the composition of the voxels can often increase performance, such an increase in performance is often outweighed by the voxel bottleneck in the memory system, thereby limiting the overall acceleration.
As depicted in
FIG. 4
, object-order pipelines generally require only one voxel access per processor thereby providing greater hardware acceleration due to the lack of a voxel or a memory bottleneck. Object-order reconstruction of the dataset, however, makes it difficult, if not impossible, to implement algorithmic acceleration or support perspective projections.
Neither image-order nor object-order architectures are general-purpose techniques because of their limitations. For example, image-order architectures only deliver interactive performance for certain types of datasets by relying heavily on algorithmic acceleration. Performance can be extremely sensitive to viewing parameters (and dataset characteristics) potentially causing large fluctuations in performance. On the other hand, object-order architectures yield more consistent performance but typically do not support perspective projections. As a result, these architectures cannot be used for applications that require stereoscopic rendering, virtual reality, computer graphics, computer games and fly-throughs.
Thus, there is a need for a device capable of general-purpose volume rendering performance that supports interactive rendering for both parallel and perspective projections. Furthermore, there is a need for a general-purpose device that supports interactive rendering for stereoscopic displays.
SUMMARY OF THE INVENTION
The present invention is a general-purpose device that supports interactive rendering for parallel and perspect
Ray Harvey
Silver Deborah
Hoffman & Baron LLP
Jankus Almis R.
Rutgers, The State University of NJ
LandOfFree
Resample and composite engine for real-time volume rendering does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Resample and composite engine for real-time volume rendering, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Resample and composite engine for real-time volume rendering will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3121449