Computer graphics processing and selective visual display system – Computer graphic processing system – Plural graphics processors
Reexamination Certificate
1999-05-20
2003-03-11
Chauhan, Ulka J. (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphic processing system
Plural graphics processors
C345S424000, C345S426000
Reexamination Certificate
active
06532017
ABSTRACT:
FIELD OF THE INVENTION
The present invention is related to the field of computer graphics, and in particular to a volume rendering pipeline.
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 values for a particular object or system 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 system.
Volume rendering is the part of volume graphics concerned with the projection of volume data as two-dimensional images for purposes of printing, display on computer terminals, and other forms of visualization. By assigning colors and transparency to particular voxel data values, different view of the exterior and interior of an object or system can be displayed. 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. 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 would otherwise be hidden from the human eye.
Real-time volume rendering in the projection and display of volume data as a series of images in rapid succession, typically at 30 frames per second or faster. This makes it possible to create the appearance of moving pictures of the object, phenomenon, or system of interest. It also enables a human operator to interactively control the parameters of the projection and to manipulate the image, thus providing the user with immediate visual feedback. It will be appreciated that projecting tens of millions or 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.
Additional general 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, New Jersey. Further background on volume rendering architectures is found in a paper entitled “Towards a Scalable Architecture for Real-time Volume Rendering” presented by H. Pfister, A. Kaufman, and T. Wessels at the 10th Eurographics Workshop on Graphics Hardware at Masstricht, The Netherlands, on Aug. 28 and 29, 1995. This paper describes an architecture now known as “Cube4.” The Cube 4 is also described 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 Dec. 1996, and in U.S. Pat. No. 5,594,842, “Apparatus and Method for Real-time Volume Visualization.”
Cube 4 and other architectures achieve real-time volume rendering using the technique of parallel processing. A plurality of processing elements are deployed to concurrently perform volume rendering operations on different portions of a volume data set, so that the overall time required to render the volume is reduced in substantial proportion to the number of processing elements. In addition to requiring a plurality of processing elements, parallel processing of volume data requires a high-speed interface between the processing elements and a memory storing and volume data, so that the voxels can be retrieved from the memory and supplied to the processing elements at a sufficiently high data rate to enable the real-time rendering to be achieved.
Volume rendering as performed by Cube 4 is an example of a technique known as “ray-casting.” A large number of rays are passed through a volume in parallel and processed by evaluating the volume data a slice at a time, where a “slice” is a planar set of voxels parallel to a face of the volume data set. Using fast slice-processing technique in specialized hardware, as opposed to software, frame processing rates can be increased to be higher than two frames per second.
The essence of the Cube—4 system is that the three dimensional sampled data representing the object is distributed across the memory modules by a technique called “skewing,” so that adjacent voxels in each dimension are stored in adjacent memory modules independent of view direction. Each memory module is dedicated to its own processing pipeline. Moreover, voxels are organized in the memory modules so that if there are a total of P pipelines and P memory modules, then P adjacent voxels can be fetched in parallel within a single clock cycle of a computer memory system, independent of the view direction. This reduces the total time to fetch voxels from memory by a factor of P. For example, if the data set has 256
3
voxels and P has the value of four, then only 256
3
/4 or approximately four million memory cycles are needed to fetch the data in order to render an image.
An additional characteristic of the Cube—4 system is that the computational processing required for volume rendering is organized into pipelines with specialized functions for this purpose. Each pipeline is capable of starting the processing of a new voxel in each cycle. Thus, in the first cycle, the pipeline fetches a voxel from its associated memory module and performs the first step of processing. Then in the second cycle, the pipeline performs the second step of processing of this first voxel, while at the same time fetching the second voxel and performing the first step of processing this voxel. Likewise, in the third cycle, the pipeline performs the third processing step of the first voxel, the second processing step of the second voxel, and the first processing step of the third voxel. In this manner, voxels from each memory module progress through its corresponding pipeline in lock-step fashion, one after the another, until all voxels are fully processed. Thus, instead of requiring 10 and 100 software instructions per voxel, a new voxel can be processed in every clock cycle.
Skewing can disperse adjacent voxels over any of the pipelines, and since the pipelines are dedicated to memory modules, the Cube—4 system must communicate voxel data with four other pipelines, i.e., the two neighboring pipelines on either side. Such communication is required, for example, to transmit voxel values from one pipeline to another for purposes such as estimating gradients or normal vectors so that lighting and shadow effects can be calculated. Pipeline interconnects are used to communicate the values of rays as they pass through the volume accumulating visual characteristics of the voxels in the vicinities of the areas through which they pass. Having, a large number of interconnects among the pipelines increase the complexity of the system.
In the Cube—4 system, volume rendering proceeds as follows. Data are organized as a cube or other parallelepiped data structure. Considering first the face of this cube or solid that is most nearly perpendicular to the view direction, a partial beam of P voxels at the top corner is fetched from P memory modules concurrently, in one memory cycle, and inserted into the first stage of the P processing pipelines. In the second cycle these voxels are moved to the second stage of their respective pipelines. At the same time, the next P voxe
Burgess Stephen R.
Hardenbergh Jan C.
Kappler Christopher J.
Knittel James M.
Lauer Hugh C.
Brinkman Dirk
Chauhan Ulka J.
TeraRecon, Inc.
LandOfFree
Volume rendering pipeline does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Volume rendering pipeline, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Volume rendering pipeline will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3010298