Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
1996-02-26
2003-05-06
Zimmerman, Mark (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
C345S424000, C345S427000, C345S505000
Reexamination Certificate
active
06559843
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to computer systems, and more particularly, to rendering volumetric data to produce a two-dimensional image.
BACKGROUND OF THE INVENTION
Many physical objects can be represented spatially and temporally by computerized models. Scaler and vector volumetric data representing the structures or features of such objects can be generated empirically by using medical scanners, seismic survey, sonar, radar, and the like. Volumetric data can also be synthetically generated by computerized models. Objects represented can include the internal structure of atoms, the distribution of background radiation in the universe, or even imaginary objects.
Computer generated images produced with the volumetric data find utility in computer-aided design, and in scientific and medical visualization fields. A two-dimensional (2D) image perceived as a three-dimensional (3D) presentation can convey large amounts of information in a more comprehensible form than is possible using other traditional techniques such as statistical tables or voluminous prose. Translucent volume rendering or images representing a selected plane or slice through an object are especially helpful for studying internal structures, and for visually relating the interior of objects to their external forms.
Images presented in an animated sequence can take advantage of motion parallax for better morphological understanding of the object represented by the volumetric data. Currently, on most computer systems, the time required to generate 2D images from volumetric data is too long to support real-time generation rates and manipulation. If the images are generated too slowly, the viewer's attention lapses, thought processes are disrupted, and the significance of differences between successive frames of the image is lost.
In volume rendering, a volume element or “voxel” is the 3D equivalent of a 2D pixel, or picture element. Voxels are usually organized into a parallelpiped arrangement relative to some Cartesian coordinate system. Each voxel represents a quantum data unit of the volume. The voxel can have associated scaler or vector values symbolizing some property of the portion of the object in the immediate vicinity of the corresponding voxel.
To view an object represented by volumetric data, the values are mapped into pixels in the image plane. For the purpose of viewing, the data of the voxel data are usually expressed abstractly in terms of color and opacity. Color may be used to differentiate a particular object property, such as density or heat distribution, and the opacity of the color may indicate the relative intensity of the differentiation. For a given orientation of the object, the Cartesian grid of the volume data may not always align perfectly with the Cartesian grid of the image plane. Various techniques are known for deriving the value of the 3D space between adjacent voxels, for example, tri-linear interpolation.
The techniques of volume rendering can be categorized as either geometric iso-surface rendering, or direct volume rendering. Geometric iso-surface rendering converts the 3D data into geometry, usually polygons which can be displayed using traditional imaging techniques. However, other than for simple objects, substantial processing is usually required to extract the iso-surfaces.
Direct volume rendering, on the other hand, utilizes the entire original generated volumetric data in the final rendering of the image, and thus any part, including the interior of the object can be viewed by mapping the 3D voxels onto the 2D pixels. Two mapping techniques, forward and backward mapping, are commonly used for direct volume rendering.
In forward, or object space mapping, the 3D voxels are projected onto the 2D pixels of the image plane. Backward, or image space mapping places an imaginary viewer and an imaginary image plane in the three-dimensional environment of the object. The composition of the scene on the image plane is determined by casting imaginary rays through the pixels of image plane to traverse the volumetric data. The color and opacity of the volumetric data encountered approximately along the trajectory or path of the ray are interpolated, and integrated, usually at regularly spaced intervals to determine the colors and opacities of the pixels.
In general, ray-casting is well suited for manipulation by computer systems having massively parallel architectures. Massively parallel computers have a plurality of processor elements (PEs), each PE having access to an associated memory. Massively parallel computers are categorized as either Multi-Instruction Multiple-Data (MIMD), or Single-Instruction Multiple-Data (SIMD).
One of the main differences between MIMD and SIMD architectures is that the instruction stream is the same for each PE of a SIMD computer, whereas the instructions for the PEs of a MIMD computer can be different. In other words, MIMD computers can be considered extensions of uni-processors with each PE working on some portion of the total work-load. Typically, jobs are parceled out serially to the PEs as they become idle, with minimal attention paid to synchronizing the PEs.
On the other hand, in a SIMD computer, each PE is manipulating different data while constrained to execute the same instruction in a lock-step manner. Processes used by SIMD computers are sometimes called “data-parallel processes” since the parallelism is on the data, and not the executed instructions. As an advantage, SIMD computers can be provided with a substantially larger number of processor elements than comparably priced MIMD computers. For example, SIMD computers having thousands of PEs are readily available, while MIMD computers of a similar price typically include less than a hundred PEs.
Keeping many thousands of PEs busy, as will be discussed herein, is a non-trivial problem. Unless the work load is carefully balanced among the processors, the efficiencies gained by the high degree of parallelism are quickly lost. Since the SIMD architecture requires that all active processors, at any one time, execute the same instruction, inactive processors remain stalled until active processors have completed a current set of instructions. Therefore, while implementing applications for SIMD computers, the data structures and processes which manipulate the data must be especially designed in order to maximize processing parallelism.
In one known data-parallel implementations, the volumetric data are oriented so a particular processor element can find all of the data for determining color and opacity values of a particular ray within its associated memory. In more detail, the volumetric data are first distributed among the local memories of each PE according to each ray cast. The goal is to have each PE cast a complete ray through the volumetric data stored in its associated memory, from start to finish. The required accumulation of pixel values, e.g., color and opacity, for a single ray are all performed within a single PE. Obviously, for a stationary viewing angle this technique is fairly efficient.
However, difficulties arise if the viewer desires to manipulate the represented object to view multiple orientations. To accomplish this in the prior art, the volumetric data are routed from PE to PE by a series of shears to align the data with a particular viewing angle. In addition to taking a considerable amount of time, multiple sheers tend to introduce progressively more observable artifacts into the final image as a result interpolation errors after shearing to reconstruct the Cartesian grid of the voxels.
Another data parallel volume rendering technique is based on object parallelism. That is, for a given set of data stored in a single processor, only the values of the intersecting rays are computed. Here, the volumetric data are only reoriented if the angle of rotation is greater than 45 degrees with respect to a Cartesian axes of the volumetric data. Once the volumetric data are in place, for any given viewing orientation that does not exceed 45 degree
Compaq Computer Corporation
Oppenheimer Wolff & Donnelly LLP
Sherry Leah
Zimmerman Mark
LandOfFree
Segmented ray casting data parallel 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 Segmented ray casting data parallel volume rendering, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Segmented ray casting data parallel volume rendering will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3015536