Apparatus and method for volume processing and rendering

• US 20040125103A1
• Filed: 01/09/2003
• Published: 07/01/2004
• Est. Priority Date: 02/25/2000
• Status: Active Grant

• Current Assignee: The Research Foundation for The State University of New York (State University of New York)
• Original Assignee: The Research Foundation for The State University of New York (State University of New York)
• Inventors: Chen, Baoquan, Kreeger, Kevin, Bitter, Ingmar, Kaufman, Arie E., Dachille, Frank
• Granted Patent: US 7,133,041 B2
• Time in Patent Office: Days
• US Class Current: 345/419
• CPC Class Codes: G06T 15/06 Ray-tracing
• CPC Class Codes: G06T 15/08 Volume rendering
• CPC Class Codes: G06T 15/40 Hidden part removal

Abstract

An apparatus and method for real-time volume processing and universal three-dimensional rendering. The apparatus includes a plurality of three-dimensional (3D) memory units; at least one pixel bus for providing global horizontal communication; a plurality of rendering pipelines; at least one geometry bus; and a control unit. The apparatus includes a block processor having a circular ray integration pipeline for processing voxel data and ray data. Rays are generally processed in image order thus permitting great flexibility (e.g., perspective projection, global illumination). The block processor includes a splatting unit and a scattering unit. A method for casting shadows and performing global illumination in relation to light sources includes sweeping a two dimensional array of rays through the volume can also be implemented with the apparatus. A method for approximating a perspective projection includes using parallel projection.

Claims

1. A method for performing approximate perspective volumetric ray casting of a three-dimensional (3D) volume dataset, the volume dataset comprising a plurality of discrete voxels stored in a distributed fashion in a plurality of three-dimensional (3D) memory units, each of the voxels having a location lying on a gridpoint in the volume dataset and having voxel data associated therewith, the method comprising the steps of:

(a) selecting viewing and processing parameters which define;

a viewpoint; and

a view direction;

(b) calculating a length of the volume dataset between the location of the nearest voxel to the viewpoint and the farthest voxel from the viewpoint, the length being measured along one of;

(i) a line parallel to the view direction; and

(ii) an axis of the three-dimensional volume dataset that is most parallel to the view direction;

(c) dividing the volume dataset along the measured length into a plurality of slabs, each of the plurality of slabs having an orientation that is perpendicular to the measured length and defines a plane having a position with respect to the viewpoint in three dimensional space;

(d) generating a perspective projection;

(e) rendering each of the plurality of slabs by parallel projection onto a plurality of separate baseplane images;

(f) texturing each of the plurality of images through the perspective projection onto their respective plane; and

(g) blending the plurality of textured images together to form the final image

2. A method for performing approximate perspective volumetric ray casting of a three-dimensional (3D) volume dataset as defined by claim 1, further comprising performing the following step prior to step (a):

culling the volume dataset.

3. A method for performing approximate perspective volumetric ray casting of a three-dimensional (3D) volume dataset as defined by claim 1, wherein steps (e) through (g) are performed sequentially for each of the plurality of slabs.

4. A method for performing approximate perspective volumetric ray casting of a three-dimensional (3D) volume dataset as defined by claim 3, wherein steps (d) through (g) are performed starting with one of the plurality of slabs having the farthest voxel from the viewpoint and ending with one of the plurality of slabs having the nearest voxel.

5. A method for performing approximate perspective volumetric ray casting of a three-dimensional (3D) volume dataset as defined by claim 3, wherein steps (d) through (g) are performed starting with one of the plurality of slabs having the nearest voxel from the viewpoint and ending with one of the plurality of slabs having the farthest voxel.

6. A method for performing approximate perspective volumetric ray casting of a three-dimensional (3D) volume dataset as defined by claim 1, wherein each of the plurality of slabs have an equal thickness.

7. A method for performing approximate perspective volumetric ray casting of a three-dimensional (3D) volume dataset as defined by claim 1, wherein the position of each respective plane of each of the plurality of slabs is situated at exponentially increasing distances from the viewpoint along measured length.

8. A method for performing approximate perspective volumetric ray casting of a three-dimensional (3D) volume dataset as defined by claim 7, wherein each successive slab after the slab having the nearest voxel has a thickness along the measured length that is twice the thickness of a preceding adjacent slab.

9. A method for performing approximate perspective volumetric ray casting of a three-dimensional (3D) volume dataset as defined by claim 1, wherein step (e) is completed for all of the plurality of slabs prior to performing steps (f) and (g).

10. A method for performing approximate perspective volumetric ray casting of a three-dimensional (3D) volume dataset as defined by claim 9, wherein steps (f) and (g) are performed starting with one of the plurality of slabs having the farthest voxel from the viewpoint and ending with one of the plurality of slabs having the nearest voxel.

11. A method for performing approximate perspective volumetric ray casting of a three-dimensional (3D) volume dataset as defined by claim 9, wherein steps (f) and (g) are performed starting with one of the plurality of slabs having the nearest voxel from the viewpoint and ending with one of the plurality of slabs having the farthest voxel.

12. An apparatus for performing approximate perspective volumetric ray casting of a three-dimensional (3D) volume dataset, the volume dataset comprising a plurality of discrete voxels stored in a distributed fashion in a plurality of three-dimensional (3D) memory units, each of the voxels having a location lying on a gridpoint in the volume dataset and having voxel data associated therewith, the apparatus comprising:

an approximating unit, the approximating unit being configured to;

(a) select viewing and processing parameters which define;

a viewpoint; and

a view direction;

(b) calculate a length of the volume dataset between the location of the nearest voxel to the viewpoint and the farthest voxel from the viewpoint, the length being measured along one of;

(i) a line parallel to the view direction; and

(ii) an axis of the three-dimensional volume dataset that is most parallel to the view direction;

(c) divide the volume dataset along the measured length into a plurality of slabs, each of the plurality of slabs having an orientation that is perpendicular to the measured length and defines a plane having a position with respect to the viewpoint in three dimensional space;

(d) generate a perspective projection;

(e) render each of the plurality of slabs by parallel projection onto a plurality of separate baseplane images;

(f) texture each of the plurality of images through the perspective projection onto their respective plane; and

(g) blend the plurality of textured images together to form the final image.

13. An article of manufacture for performing approximate perspective volumetric ray casting of a three-dimensional (3D) volume dataset, the volume dataset comprising a plurality of discrete voxels stored in a distributed fashion in a plurality of three-dimensional (3D) memory units, each of the voxels having a location lying on a gridpoint in the volume dataset and having voxel data associated therewith, the article comprising:

a machine readable medium containing one or more programs which when executed implement the steps of;

(a) selecting viewing and processing parameters which define;

a viewpoint; and

a view direction;

(b) calculating a length of the volume dataset between the location of the nearest voxel to the viewpoint and the farthest voxel from the viewpoint, the length being measured along one of;

(i) a line parallel to the view direction; and

(ii) an axis of the three-dimensional volume dataset that is most parallel to the view direction;

(c) dividing the volume dataset along the measured length into a plurality of slabs, each of the plurality of slabs having an orientation that is perpendicular to the measured length and defines a plane having a position with respect to the viewpoint in three dimensional space;

(d) generating a perspective projection;

(e) rendering each of the plurality of slabs by parallel projection onto a plurality of separate baseplane images;

(f) texturing each of the plurality of images through the perspective projection onto their respective plane; and

(g) blending the plurality of textured images together to form the final image.

14. A method of mapping a three dimensional volume dataset in a linear memory array, said volume dataset comprising a plurality of discrete voxels associated with a three dimensional grid point position P_xyz=(x;

y;

z), said linear memory array having a plurality of indices O_xyz, the method comprising the steps of;

(a) converting integer coordinates (x;

y;

z) of the grid point position of one of the plurality of discrete voxels into a first bit pattern ( . . . ,x₃, x₂, x₁, x₀;

. . . , y₃, y₂, y₁, y₀;

. . . , z₃, z₂, z₁, z₀);

(b) determining an integer offset for the one of the plurality of discrete voxels of step (a) from a second bit pattern ( . . . ,z₃, y₃, x₃, z₂,y₂,x₂,z₁,y₁,x₁,z₀,y₀,x₀); and

(c) mapping the one of the plurality of discrete voxels of step (a) onto the linear array at the integer offset; and

(d) repeating steps (a) through (c) for each of the plurality of discrete voxels.

15. A method of mapping a three dimensional volume dataset as defined by claim 14, wherein steps (a) through (c) are processed in linear storage order.

16. A recursive blocking apparatus for a real-time volume rendering system having a linear memory array for the mapping of a three dimensional volume dataset, said volume dataset comprising a plurality of discrete voxels associated with a three dimensional grid point position P_xyz=(x;

y;

z), the linear memory array having a plurality of indices O_xyz, the recursive blocking apparatus comprising;

an addressing unit, the addressing unit being configured to;

(a) convert integer coordinates (x;

y;

z) of the grid point position of one of the plurality of discrete voxels into a first bit pattern ( . . . ,x₃, x₂, x₁, x₀;

. . . , y₃, y₂, y₁, y₀;

z₃, z₂, z₁, z₀);

(b) determine an integer offset for the one of the plurality of discrete voxels of step (a) from a second bit pattern ( . . . , z₃, y₃, x₃, z₂, y₂, x₂, z₁, y₁, x₁, z₀y₀, x₀); and

(c) map the one of the plurality of discrete voxels of step (a) onto the linear array at the integer offset; and

(d) repeat steps (a) through (c) for each of the plurality of discrete voxels.

17. An article of manufacture for mapping a three dimensional volume dataset in a linear memory array, said volume dataset comprising a plurality of discrete voxels associated with a three dimensional grid point position P_xyz=(x;

y;

z), said linear memory array having a plurality of indices O_xyz, the article comprising;

a machine readable medium containing one or more programs which when executed implement the steps of;

(a) converting integer coordinates (x;

y;

z) of the grid point position of one of the plurality of discrete voxels into a first bit pattern ( . . . ,x₃, x₂, x₁, x₀;

. . . y₃, y₂, y₁, y₀;

. . . z₃, z₂, z₁, z₀);

(b) determining an integer offset for the one of the plurality of discrete voxels of step (a) from a second bit pattern ( . . . , z₃, y₃, x₃, z₂, y₂, x₂, z₁, y₁, x₁, z₀, y₀, x₀); and

(c) mapping the one of the plurality of discrete voxels of step (a) onto the linear array at the integer offset; and

(d) repeating steps (a) through (c) for each of the plurality of discrete voxels.

18. An apparatus for splatting at least one ray passing through a three-dimensional (3D) volume dataset, the volume dataset having a plurality of discrete voxels, each of the voxels having voxel data associated therewith, the at least one ray having ray data associated therewith and a position in the volume dataset with respect to time associated with one or more voxels, the apparatus comprising:

a splatting unit configured to;

receive the voxel data and the ray data associated with the position of the ray;

copy the voxel data and the ray data;

update the voxel data based upon the copy of the ray data; and

update the ray data based upon the copy of the voxel data.

19. A method of splatting at least one ray passing through a three-dimensional (3D) volume dataset, the volume dataset having a plurality of discrete voxels, each of the voxels having voxel data associated therewith, the at least one ray having ray data associated therewith and a position in the volume dataset with respect to time associated with one or more voxels, the method comprising the steps of:

(a) receiving the voxel data and the ray data associated with the position of the ray;

(b) copying the voxel data and the ray data;

(c) updating the voxel data based upon the copy of the ray data; and

(d) updating the ray data based upon the copy of the voxel data.

20. A queue sorter for determining a processing order of a plurality of ray queues for a volume processing system during processing, each of the plurality of ray queues being assigned a dataset including a queue number and a scalar importance, the queue sorter comprising:

a pipelined insertion sorter having;

a comparison buffer having a first linear storage arrangement for storing at least one dataset of one of said plurality of ray queues; and

a selected buffer having a second linear storage arrangement for storing the dataset for each of said plurality of ray queues,

the pipelined insertion sorter being configured to;

(a) receive a first dataset of one of said plurality of ray queues at a rank of the first storage arrangement of the comparison buffer;

(b) compare the scalar importance of the first dataset with the scalar importance of a second dataset in the selected buffer having the same rank to determine the dataset having the higher scalar importance and the lower scalar importance;

(c) assign the dataset having the higher scalar importance to the second dataset;

(d) move the dataset having the lower scalar importance to the first dataset on the first linear storage arrangement at a position located one below the rank of the second dataset; and

(e) repeat (a) through (d) during processing with the scalar importance of the active queue being set higher than the scalar importance of the remaining plurality of ray queues and removing an old dataset from the selected buffer when the first dataset has the same queue number as the old dataset.

21. A queue sorter as defined in claim 20, wherein the pipelined insertion sorter performs (b) through (d) for a plurality of datasets simultaneously.

22. A method of determining a processing order of a plurality of ray queues for a volume processing system during processing, each of the plurality of ray queues being assigned a dataset including a queue number and a scalar importance, the method comprising the steps of:

(a) providing an insertion sorter having;

a comparison buffer having a first linear storage arrangement for storing at least one dataset of one of said plurality of ray queues; and

a selected buffer having a second linear storage arrangement for storing the dataset for each of said plurality of ray queues;

(b) receiving a first dataset of one of said plurality of ray queues at a rank of the first storage arrangement of the comparison buffer;

(c) comparing the scalar importance of the first dataset with the scalar importance of a second dataset in the selected buffer having the same rank to determine the dataset having the higher scalar importance and the lower scalar importance;

(d) assigning the dataset having the higher scalar importance to the second dataset;

(e) moving the dataset having the lower scalar importance to the first dataset on the first linear storage arrangement at a position located one below the rank of the second dataset; and

(f) repeating steps (b) through (e) during processing with the scalar importance of the active queue being set higher than the scalar importance of the remaining plurality of ray queues and removing an old dataset from the selected buffer when the first dataset has the same queue number as the old dataset.

23. A block processor for interfacing a ray bus and a plurality of three-dimensional (3D) memory units in a volume processing unit, the volume processing unit generating a plurality of rays for processing a volume dataset having a plurality of discrete voxels stored in a distributed fashion in the plurality of three-dimensional (3D) memory units, each of the voxels having a location lying on a gridpoint in the volume dataset and having voxel data associated therewith, each of the plurality of rays having a path and being a data structure having ray data associated therewith and a sample location in the volume dataset with respect to time associated with one or more voxels, the block processor comprising;

a circular ray integration pipeline for processing the voxel data and the ray data to represent an exchange of energy between the volume dataset and the ray data along the path of each ray, the plurality of rays being processed simultaneously in a round-robin fashion.

24. A block processor as defined in claim 23, wherein the circular ray integration pipeline comprises:

a queue sorter for interfacing the plurality of rays over the ray bus, the queue sorter separating the plurality of rays into a plurality of ray queues and assigning a scalar importance to each of the plurality of rays queues for maintaining a sorted rank of importance for each of the plurality of rays queues;

at least one ray queue being connected to the queue sorter for receiving the plurality of sorted rays, the at least one ray queue controlling the processing of each of the plurality of sorted rays one at a time;

a prefetch and memory controller being connected to the at least one ray queue having the highest scalar importance for receiving the plurality of sorted rays and prefetching voxels to hide latency, the prefetch and memory controller interfacing the memory units;

an interleaved volume cache being connected to the prefetch and memory controller for receiving the plurality of sorted rays and prefetched voxels a resampling unit being connected to the interleaved volume cache for receiving the plurality of sorted rays and accepting one sample location along a ray and a plurality of voxels that are nearest the sample location, the resampling unit trilinearly interpolating density, tag, gradient and irradiance for the sample location to generate sample data;

a segmentation unit being connected to the resampling unit for receiving the plurality of sorted rays and the sample data and classifying the material type including color, opacity, and shading coefficients for the sample data

a compositing unit being connected to the segmentation unit for receiving the plurality of sorted rays and the sample data and updating the opacity and color of the ray based upon the sample data;

a shading unit being connected to the compositing unit for receiving the plurality of sorted rays and the sample data;

a scattering unit for receiving the plurality of sorted rays and the sample data and redirecting the ray direction based upon the sample data and the material type of the data; and

a splatting unit being connected to the scattering unit and receiving the plurality of sorted rays and the sample data for updating the voxel data and the ray data associated with the sample location,

wherein one of the scattering unit and splatting unit is directly connected to the shading unit and the other is connected to the queue sorter.

25. A block processor as defined in claim 23, wherein the scattering unit is connected to the shading unit.

26. A block processor as defined in claim 23, wherein the splatting unit is connected to the shading unit.

27. A block processor as defined in claim 23, wherein the splatting unit is configured to:

receive the ray data and the voxel data associated with the sample location of the ray;

copy the voxel data and the ray data;

update the voxel data based upon the copy of the ray data; and

update the ray data based upon the copy of the voxel data.

28. A block processor as defined in claim 23, wherein the shading unit has a reflectance map for performing shading.

29. A block processor as defined in claim 23, wherein the queue sorter is configured to interface at least one other block processor.

30. A method for scattering at least one ray passing through a three-dimensional (3D) volume dataset, the volume dataset having a plurality of discrete voxels and an estimated gradient, each of the voxels having voxel data associated therewith, the at least one ray having a direction, ray data associated therewith, and a sample location in the volume dataset with respect to time associated with at least one voxel, the voxel data associated with the sample location including a reflectivity in a range between 0 and 1, a refractivity in a range between 0 and 1, a glossiness in a range between 0 and 90, the method comprising the steps of:

(a) receiving and copying the ray data and voxel data associated with the sample location;

(b) selecting a first random number in a range between 0 and 1

(c) reflecting the ray direction about the estimated gradient in the volume dataset at the sample location when the first random number is less than the reflectivity at the sample location;

(d) selecting a second random number in a range between 0 and 1

(e) refracting the ray direction based upon the refractivity of the voxel data associated with the sample location and the estimated gradient in the volume dataset at the sample location when the second random number is less than the refractivity at the sample location;

(f) selecting a random direction and a gaussian distributed random angle, the random angle being defined by the glossiness of the voxel data multiplied by a third range between 0 and 1; and

(g) rotating the ray direction in the random direction by the random angle based on the glossiness at the sample location.

31. An apparatus for scattering at least one ray passing through a three-dimensional (3D) volume dataset, the volume dataset having a plurality of discrete voxels and an estimated gradient, each of the voxels having voxel data associated therewith, the at least one ray having a direction, ray data associated therewith, and a sample location in the volume dataset with respect to time associated with at least one voxel, the voxel data associated with the sample location including a reflectivity in a range between 0 and 1, a refractivity in a range between 0 and 1, a glossiness in a range between 0 and 90, the apparatus comprising:

a scattering unit configured to;

(a) receive and copy the ray data and voxel data associated with the sample location;

(b) select a first random number in a range between 0 and 1

(c) reflect the ray direction about the estimated gradient in the volume dataset at the sample location when the first random number is less than the reflectivity at the sample location;

(d) select a second random number in a range between 0 and 1

(e) refract the ray direction based upon the refractivity of the voxel data associated with the sample location and the estimated gradient in the volume dataset at the sample location when the second random number is less than the refractivity at the sample location;

(f) select a random direction and a gaussian distributed random angle, the random angle being defined by the glossiness of the voxel data multiplied by a third range between 0 and 1; and

(g) rotate the ray direction in the random direction by the random angle based on the glossiness at the sample location.

32. A method for casting shadows of a volume dataset in relation to point light sources located both inside and outside, distant light sources located outside the volume dataset, and area light sources inside the volume dataset, the volume dataset comprising a plurality of discrete voxels stored in a distributed fashion in a plurality of three-dimensional (3D) memory units, each of the voxels having a location lying on a gridpoint in the volume dataset and having voxel data associated therewith, the method comprising the steps of:

(a) computing sum of the optical path length to all the point light sources for all of the voxels in the volume data set;

(b) storing the sums of the optical path length values in both a radiosity array and an unshot radiosity array;

(c) selecting a projection direction and a face of the volume dataset which is most perpendicular to the projection direction;

(d) dividing the volume dataset along the projection direction into a plurality of slices which are parallel to the face, the plurality of slices having a first slice, the first slice having at least one voxel associated with the face;

(e) initializing a two dimensional (2D) array of rays on the selected face with any distant light source energy, each of the rays having a path parallel to the projection direction and ray data associated therewith;

(f) assigning the first slice as a current slice

(g) integrating and distributing light energy to voxels along each path of each ray within the current slice; and

(h) repeating step (g) by sequentially sweeping along the projection direction through each subsequent slice until each of the plurality of slices is processed, each subsequent slice in turn becoming the current slice.

33. A method for casting shadows as defined in claim 32, wherein step (e) comprises the sub-steps of:

(a) making a copy of all the ray data and all voxel data on the current slice, the voxel data including the reflectivity, opacity, radiosity, and unshot radiosity, the ray data representing light energy;

(b) selecting a current voxel;

(c) determining an appropriate neighborhood of rays for the current voxel;

(d) resampling the ray data at the current voxel;

(e) modulating the ray data by a factor zeta to distribute the energy;

(f) updating the current voxel data based on the resampled ray data;

(g) updating the data of the neighboring rays based on the current voxel data;

(h) repeating steps (b) through (g) for each voxel in the current slice;

(i) storing the ray data back into the neighboring rays; and

(j) storing the voxel data back into the volume dataset.

34. A method for performing global illumination of a volume dataset in relation to point light sources located both inside and outside, distant light sources located outside the volume dataset, and area light sources inside the volume dataset, the volume dataset comprising a plurality of discrete voxels stored in a distributed fashion in a plurality of three-dimensional (3D) memory units, each of the voxels having a location lying on a gridpoint in the volume dataset and having voxel data associated therewith, the method comprising the steps of:

(a) computing sum of the optical path length to all the point light sources for all of the voxels in the volume data set;

(b) storing the sums of the optical path length values in both a radiosity array and an unshot radiosity array;

(c) selecting a projection direction and a face of the volume dataset which is most perpendicular to the projection direction;

(d) dividing the volume dataset along the projection direction into a plurality of slices which are parallel to the face, the plurality of slices having a first slice, the first slice having at least one voxel associated with the face;

(e) initializing a two dimensional (2D) array of rays on the selected face with any distant light source energy, each of the rays having a path parallel to the projection direction and ray data associated therewith;

(f) assigning the first slice as a current slice

(g) integrating and distributing light energy to voxels along each path of each ray within the current slice;

(h) repeating step (g) by sequentially sweeping along the projection direction through each subsequent slice until each of the plurality of slices is processed, each subsequent slice in turn becoming the current slice; and

(i) repeating steps (c) through (h) continuously during global illumination.

35. A method for performing global illumination as defined in claim 34, wherein step (e) comprises the sub-steps of:

(a) making a copy of all the ray data and all voxel data on the current slice, the voxel data including the reflectivity, opacity, radiosity, and unshot radiosity, the ray data representing light energy;

(b) selecting a current voxel;

(c) determining an appropriate neighborhood of rays for the current voxel;

(d) resampling the ray data at the current voxel;

(e) modulating the ray data by a factor zeta to distribute the energy;

(f) updating the current voxel data based on the resampled ray data;

(g) updating the data of the neighboring rays based on the current voxel data;

(h) repeating steps (b) through (g) for each voxel in the current slice;

(i) storing the ray data back into the neighboring rays; and

(j) storing the voxel data back into the volume dataset.

36. A programmable processing element for controlling the storage location of volume data and polygon data distributed among blocks of a scheduling grid and being stored in a memory hierarchy having a first tier, a second tier, and a third tier, the scheduling grid having a plurality of rays casted there through and stored in ray queues, the programmable processing element comprising:

a dispatcher for controlling the volume data and the polygon data movement through the memory hierarchy, the dispatcher being operatively coupled to the first, second and third tiers;

a scheduler for determining the block processing order based upon the scheduling grid and the plurality of ray queues; and

a buffer connected between the dispatcher and the scheduler for facilitating communication between the dispatcher and the scheduler.

37. The programmable processing element as defined in claim 36, wherein the scheduler has a heuristic metric for determining the block processing order.