Apparatus and method for parallel and perspective real-time volume visualization

• US 5,847,711 A
• Filed: 08/01/1997
• Issued: 12/08/1998
• Est. Priority Date: 09/06/1994
• Status: Expired due to Term

• 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: Bitter, Ingmar, Kaufman, Arie E.
• Primary Examiner(s): Zimmerman, Mark K.
• Application Number:
  US08/910,575
• Time in Patent Office: 494 Days
• Field of Search: 345/424, 345/427
• US Class Current: 345/424
• CPC Class Codes: G06T 1/20 Processor architectures; Processor configuration, e.g. pipelining
• CPC Class Codes: G06T 15/005 General purpose rendering architectures
• CPC Class Codes: G06T 15/08 Volume rendering
• CPC Class Codes: G06T 15/10 Geometric effects

Abstract

An apparatus and method for parallel and perspective real-time volume visualization. The method employs ray-slice-sweeping and includes the steps of selecting viewing and processing parameters; initializing a compositing buffer; sampling voxel values from a three dimensional memory buffer onto a current slice of sample points; combining the sample point values with pixels of the compositing buffer along a plurality of interstice ray segments which extend only between the current slice and an adjacent slice associated with the compositing buffer; and repeating the sampling and combining steps by subsequentially sweeping through subsequent slices of sample points parallel to the first processing slice until the last processing slice is reached. Each of the subsequent slices in turn becomes the current slice. The apparatus includes a three dimensional buffer; a pixel bus; a plurality of rendering pipelines; and a control unit. The plurality of rendering pipelines each include a first slice unit; a compositing unit; a two dimensional slice compositing buffer; and a first (preferably bilinear) interpolation unit. Sample point values are combined with pixels of the compositing buffer in the compositing unit along the plurality of interslice ray segments which extend only between a current slice contained in the slice unit and a slice contained in the two-dimensional slice compositing buffer. In the apparatus and method of the present invention, gradients are computed at voxel positions, improving accuracy and allowing for a more compact implementation with less control overhead than prior methods and apparatuses.

Claims

1. A ray-slice-sweeping method for generating a three-dimensional (3-D) volume projection image having a plurality of pixels, said image being generated from a view point, said method utilizing discrete voxels stored in a 3-D buffer, each of said voxels having a location and at least one voxel value associated therewith, said method comprising the steps of:

(a) selecting viewing and processing parameters which define;

said view point;

at least one base plane of said 3-D buffer which is employed for projection purposes; and

first and last processing slices of said 3-D buffer;

(b) initializing a compositing buffer having a plurality of pixels, each of said pixels having at least color, transparency and position associated therewith;

(c) sampling voxel values from said 3-D buffer onto a current slice of sample points parallel to said first processing slice to provide sample point values, said current slice being said first processing slice during a first execution of step(c);

(d) combining said sample point values with said pixels of said compositing buffer along a plurality of interslice ray segments, said segments extending only between said current slice and an adjacent slice associated with said compositing buffer; and

(e) repeating steps (c) and (d) by sequentially sweeping through subsequent slices of sample points parallel to said first processing slice until said last processing slice is reached, each of said subsequent slices in turn becoming said current slice.

2. The ray-slice-sweeping method of claim 1, wherein:

step (c) includes sampling said voxel values from said 3-D buffer directly onto grid points of said current slice of sample points, said sample points coinciding with said grid points;

step (d) includes the sub-step of casting a plurality of sight rays from said view point through said grid points of said current slice of sample points, said interslice ray segments extending along said sight rays from said sample points of said current slice to said adjacent slice associated with said compositing buffer, said interslice ray segments intersecting said adjacent slice at a plurality of intersection points; and

step (e) includes re-casting said sight rays as each of said subsequent slices becomes said current slice;

said method further comprising the additional step of;

(f) performing one of;

zero order interpolation;

first order interpolation;

second order interpolation;

third order interpolation;

higher order interpolation; and

adaptive combinations thereof,

said interpolation being performed among pixels of said compositing buffer adjacent said intersection points in order to provide interpolated pixel values for combination with said sample points of said current slice.

3. The ray-slice-sweeping method of claim 2, wherein step (f) includes performing bilinear interpolation among said pixels adjacent said intersection points.

4. The ray-slice-sweeping method of claim 3, wherein:

said view point is in front of said 3-D buffer;

said first processing slice is in front of said 3-D buffer;

said last processing slice is in back of said 3-D buffer; and

in step (d), said combining is performed from front to back with respect to said view point.

5. The ray-slice-sweeping method of claim 3, wherein:

said view point is in front of said 3-D buffer;

said first processing slice is in back of said 3-D buffer;

said last processing slice is in front of said 3-D buffer; and

step (d), said combining is performed from back to front with respect to said view point.

6. The ray-slice-sweeping method of claim 3, wherein:

said view point is in back of said 3-D buffer;

said first processing slice is in front of said 3-D buffer;

said last processing slice is in back of said 3-D buffer; and

in step (d), said combining is performed from back to front with respect to said view point.

7. The ray-slice-sweeping method of claim 3, wherein:

said view point is in back of said 3-D buffer;

said first processing slice is in back of said 3-D buffer;

said last processing slice is in front of said 3-D buffer; and

in step (d), said combining is performed from front to back with respect to said view point.

8. The ray-slice-sweeping method of claim 1, wherein:

step (d) includes the sub-step of casting a plurality of sight rays from said view point through locations in said adjacent slice associated with said compositing buffer, said locations corresponding to grid point locations of said pixels within said compositing buffer, said sight rays intersecting said current slice at a plurality of intersection points;

step (c) includes sampling said voxel values from said 3-D buffer onto said plurality of intersection points by performing one of;

zero order interpolation;

first order interpolation;

second order interpolation;

third order interpolation;

higher order interpolation; and

adaptive combinations thereof, said interpolation being performed among voxel values associated with voxel locations adjacent said plurality of intersection points; and

step (e) includes re-casting said sight rays as each of said subsequent slices becomes said current slice.

9. The ray-slice-sweeping method of claim 8, wherein step (c) includes performing bilinear interpolation among said voxel values associated with said voxel locations adjacent said plurality of intersection points.

10. The ray-slice-sweeping method of claim 9, wherein:

said view point is in front of said 3-D buffer;

said first processing slice is in front of said 3-D buffer;

said last processing slice is in back of said 3-D buffer; and

in step (d), said combining is performed from front to back with respect to said view point.

11. The ray-slice-sweeping method of claim 9, wherein:

said view point is in front of said 3-D buffer;

said first processing slice is in back of said 3-D buffer;

said last processing slice is in front of said 3-D buffer; and

in step (d), said combining is performed from back to front with respect to said view point.

12. The ray-slice-sweeping method of claim 9, wherein:

said view point is in back of said 3-D buffer;

said first processing slice is in front of said 3-D buffer;

said last processing slice is in back of said 3-D buffer; and

in step (d), said combining is performed from back to front with respect to said view point.

13. The ray-slice-sweeping method of claim 9, wherein:

said view point is in back of said 3-D buffer;

said first processing slice is in back of said 3-D buffer;

said last processing slice is in front of said 3-D buffer; and

in step (d), said combining is performed from front to back with respect to said view point.

14. The ray-slice-sweeping method of claim 1, wherein:

step(c) includes sampling said voxel values from said 3-D buffer directly onto grid points of said current slice of sample points, said sample points coinciding with said grid points; and

a first execution of step (d) includes the sub-step of casting a plurality of sight rays from said view point through said grid points of said current slice of sample points, said interslice ray segments extending from said sample points of said current slice to intersections of said sight rays with said compositing buffer;

said method further comprising the additional steps of;

(f) performing one of;

zero order interpolation;

first order interpolation;

second order interpolation;

third order interpolation;

higher order interpolation; and

adaptive combinations thereof,

said interpolation being performed among pixels of said compositing buffer adjacent said intersection points in order to provide interpolated pixel values for combination with said sample points of said current slice, results of said interpolation and said combination of step (d) being stored, with an accumulated offset, in grid point locations of those of said pixels in said compositing buffer which are closest to said intersections of said sight rays with said compositing buffer;

(g) performing one of;

(i) merging of two or more of said interslice ray segments when two or more of said results of said interpolation and said combination are attempted to be stored at an identical grid point location; and

(ii) splitting of at least one of said interstice ray segments when adjacent interstice ray segments diverge beyond a divergence threshold;

(h) maintaining said sight rays formed in said first execution of step (d) throughout said sequential sweeping through said subsequent slices, except when one of said merging and said splitting is performed;

(i) generating a new sight ray from said view point to a preselected location in the neighborhood of said identical grid point location when said merging is performed;

(j) generating two new sight rays from said view point to corresponding preselected locations in said current slice when said splitting is performed; and

(k) storing said results of said interpolation and said combination of step (d) in an adjacent one of said grid point locations when said accumulated offset exceeds a predetermined value, said storing being done together with a new accumulated offset value.

15. The ray-slice-sweeping method of claim 14, wherein:

step (g) comprises said merging of said two or more of said interslice ray segments; and

in step (d), said combining is performed from back to front with respect to said view point.

16. The ray-slice-sweeping method of claim 15, wherein step (f) comprises performing bilinear interpolation among said pixels of said compositing buffer adjacent said intersection points.

17. The ray-slice-sweeping method of claim 14, wherein:

step (g) comprises said splitting of said at least one of said interstice ray segments; and

in step (d), said combining is performed from front to back with respect to said view point.

18. The ray-slice-sweeping method of claim 17, wherein step (f) comprises performing bilinear interpolation among said pixels of said compositing buffer adjacent said intersection points.

19. The ray-slice-sweeping method of claim 14, further comprising the additional step of:

(1) dividing said 3-D buffer into a plurality of zones separated by zone boundaries, said merging and splitting being confined to said zones and not occurring across said zone boundaries, said zones and zone boundaries being selected for enhancing image sharpness and accuracy.

20. The ray-slice-sweeping method of claim 19, wherein said zone boundaries are determined by forming generalized 3-D pyramids extending from said view point through boundaries of pixels associated with said base plane into said 3-D buffer, further comprising the additional step of:

(m) labeling those voxels that belong to a given one of said zones.

21. The ray-slice-sweeping method of claim 1, wherein:

a first execution of step (d) includes the sub-step of casting a plurality of sight rays from said view point through locations in said adjacent slice associated with said compositing buffer, said locations corresponding to grid point locations of said pixels within said compositing buffer, said sight rays intersecting said current slice at a plurality of intersection points, said interslice ray segments extending from said grid point locations of said pixels within said compositing buffer to said intersection points; and

step (c) includes sampling said voxel values from said 3-D buffer onto said plurality of intersection points by performing one of;

zero order interpolation;

first order interpolation;

second order interpolation;

third order interpolation;

higher order interpolation; and

adaptive combinations thereof,

said interpolation being performed among voxel values associated with voxel locations adjacent said plurality of intersection points;

said method further comprising the additional steps of;

(f) storing results of said interpolation and said combination of step (d), with an accumulated offset, in said grid point locations of said pixels within said compositing buffer;

(g) performing one of;

(i) merging of two or more of said interslice ray segments when two or more of said results of said interpolation and said combination are attempted to be stored at an identical grid point location; and

(ii) splitting of at least one of said interslice ray segments when adjacent interslice ray segments diverge beyond a divergence threshold;

(h) maintaining said sight rays formed in said first execution of step (d) throughout said sequential sweeping through said subsequent slices, except when one of said merging and said splitting is performed;

(i) generating a new sight ray from said view point to a preselected location in the neighborhood of said identical grid point location when said merging is performed;

(j) generating two new sight rays from said view point to corresponding preselected locations in said compositing buffer when said splitting is performed; and

(k) storing said results of said interpolation and said combination of step (d) in an adjacent one of said grid point locations when said accumulated offset exceeds a predetermined value, said storing being done together with a new accumulated offset value.

22. The ray-slice-sweeping method of claim 21, wherein:

step (g) comprises said merging of said two or more of said interslice ray segments; and

in step (d), said combining is performed from back to front with respect to said view point.

23. The ray-slice-sweeping method of claim 22, wherein step (f) comprises performing bilinear interpolation among said voxel values associated with said voxel locations adjacent said plurality of intersection points.

24. The ray-slice-sweeping method of claim 21, wherein:

step (g) comprises said splitting of said at least one of said interslice ray segments; and

in step (d), said combining is performed from front to back with respect to said view point.

25. The ray-slice-sweeping method of claim 24, wherein step (f) comprises performing bilinear interpolation among said voxel values associated with said voxel locations adjacent said plurality of intersection points.

26. The ray-slice-sweeping method of claim 21, further comprising the additional step of:

(1) dividing said 3-D buffer into a plurality of zones separated by zone boundaries, said merging and splitting being confined to individual zones and adjacent zones only and not occurring, for a given zone, across more than one of said zone boundaries on each side of said given zone, said zones and zone boundaries being selected for enhancing image sharpness and accuracy and for reduction of aliasing.

27. The ray-slice-sweeping method of claim 26, wherein said zone boundaries are determined by forming generalized 3-D pyramids extending from said view point through boundaries of pixels associated with said base plane into said 3-D buffer, further comprising the additional step of:

(m) labeling those voxels that belong to a given one of said zones.

28. An apparatus for parallel and perspective real-time volume visualization via ray-slice-sweeping, said apparatus being responsive to viewing and processing parameters which define a view point, said apparatus generating a three-dimensional (3-D) volume projection image from said view point, said image having a plurality of pixels, said apparatus comprising:

(a) a three-dimensional (3-D) buffer which stores a plurality of discrete voxels, each of said voxels having a location and at least one voxel value associated therewith, said three-dimensional buffer including a plurality of memory units, said viewing and processing parameters defining at least one base plane of said 3-D buffer and first and last processing slices of said 3-D buffer;

(b) a pixel bus which provides global horizontal communication;

(c) a plurality of rendering pipelines, each of said rendering pipelines being vertically coupled to both a corresponding one of said plurality of memory units and said pixel bus, each of said rendering pipelines having horizontal communication with at most its two nearest neighbors, each of said rendering pipelines in turn comprising;

(i) at least a first slice unit having an input coupled to said corresponding one of said plurality of memory units and having an output, said slice unit including a current slice of sample points parallel to said first processing slice, said slice unit receiving voxel values from said 3-D buffer onto said sample points to provide sample point values;

(ii) a compositing unit having an input which is coupled to said output of said slice unit and having an output which is coupled to said pixel bus;

(iii) a two-dimensional slice compositing buffer having a plurality of pixels, each of said pixels having at least color, transparency and position associated therewith, said compositing buffer having an input coupled to said output of said compositing unit and having an output coupled to said input of said compositing unit; and

(iv) a first bilinear interpolation unit having an input coupled to one of;

said output of said compositing buffer; and

said corresponding one of said plurality of memory units;

said bilinear interpolation unit having an output which is coupled to;

said input of said compositing unit when said input of said bilinear interpolation unit is coupled to said output of said compositing buffer; and

said input of said at least first slice unit when said input of said bilinear interpolation unit is coupled to said corresponding one of said plurality of memory units; and

(d) a control unit which initially designates said first processing slice as said current slice and which controls sweeping through subsequent slices of said 3-D buffer as current slices, until said last processing slice is reached;

wherein said sample point values are combined with said pixels of said compositing buffer in said compositing unit, said combination occurring along a plurality of interslice ray segments extending only between said current slice in said slice unit and a slice contained in said 2-D slice compositing buffer.

29. The apparatus of claim 28, wherein:

said slice unit receives said voxel values from said 3-D buffer directly onto grid points of said current slice of sample points, said sample points coinciding with said grid points;

said interslice ray segments extend along a plurality of sight rays cast from said view point through said grid points of said current slice of sample points, said interslice ray segments extending from said sample points of said current slice in said slice unit to said slice contained in said 2-D slice compositing buffer, said interslice ray segments intersecting said slice contained in said 2-D slice compositing buffer at a plurality of intersection points;

said bilinear interpolation unit has its input coupled to said output of said compositing buffer and its output coupled to said input of said compositing unit, said bilinear interpolation unit receiving signals associated with pixels of said 2-D slice compositing buffer which are adjacent said intersection points and providing interpolated pixel values for combination with said sample points of said current slice in said compositing unit; and

said control unit recasts said sight rays as each of said subsequent slices becomes said current slice.

30. The apparatus of claim 29, wherein each of said plurality of rendering pipelines further comprises:

(v) a second slice unit having an input coupled to said output of said first slice unit and having an output;

(vi) a gradient computation unit having an input coupled to said output of said second slice unit and having an output; and

(vii) a shading unit having an input coupled to said output of said gradient computation unit and having an output coupled to said input of said compositing unit;

wherein said second slice unit is used for gradient estimation in conjunction with said gradient computation unit.

31. The apparatus of claim 28, wherein:

said first bilinear interpolation unit has its input coupled to said 3-D buffer and its output coupled to said input of said slice unit;

said interslice ray segments extend along a plurality of sight rays cast from said view point through locations in said slice contained in said 2-D slice compositing buffer, said locations corresponding to grid point locations of said pixels within said compositing buffer, said sight rays intersecting said current slice at a plurality of intersection points;

said first bilinear interpolation unit receives voxel values associated with voxel locations adjacent said plurality of intersection points and interpolates among said voxel values to provide interpolated voxel values associated with said plurality of intersection points; and

said control unit recasts said sight rays as each of said subsequent slices becomes said current slice.

32. The apparatus of claim 31, wherein each of said plurality of rendering pipelines further comprises:

(v) a second slice unit having an input coupled to said output of said first slice unit and having an output;

(vi) a gradient computation unit having an input coupled to said output of said second slice unit and having an output;

(vii) a shading unit having an input coupled to said output of said gradient computation unit and having an output coupled to said input of said compositing unit; and

(viii) a second bilinear interpolation unit having an input coupled to said output of said compositing buffer and having an output coupled to said input of said compositing unit;

wherein said second slice unit is used for gradient estimation in conjunction with said gradient computation unit.

33. The apparatus of claim 28, wherein:

said slice unit receives said voxel values from said 3-D buffer directly onto grid points of said current slice of sample points, said sample points coinciding with said grid points;

said interslice ray segments extend along a plurality of sight rays cast from said view point through said grid points of said current slice of sample points, said interslice ray segments extending from said sample points of said current slice in said slice unit to said slice contained in said 2-D slice compositing buffer, said interslice ray segments intersecting said slice contained in said 2-D slice compositing buffer at a plurality of intersection points;

said first bilinear interpolation unit has its input coupled to said output of said compositing buffer and its output coupled to said input of said compositing unit, said bilinear interpolation unit receiving signals associated with pixels of said 2-D slice compositing buffer which are adjacent said intersection points and providing interpolated pixel values for combination with said sample points of said current slice in said compositing unit, results of said combination of said interpolated pixel values and said sample points of said current slice being stored, with an accumulated offset, in grid point locations of those of said pixels in said compositing buffer which are closest to said intersection of said sight rays with said compositing buffer; and

said control unit;

enables one of;

(i) merging of two or more of said interslice ray segments when two or more of said results of said interpolation and said combination are attempted to be stored at an identical grid point location; and

(ii) splitting of at least one of said interslice ray segments when adjacent interslice ray segments diverge beyond a divergence threshold;

maintains said sight rays throughout said sequential sweeping through said subsequent slices, except when one of said merging and said splitting is performed;

generates a new sight ray from said view point to a preselected location in the neighborhood of said identical grid point location when said merging is performed;

generates two new sight rays from said view point to corresponding preselected locations in said current slice when said splitting is performed; and

stores said results of said interpolation and said combination in an adjacent one of said grid point locations when said accumulated offset exceeds a predetermined value, said storing being done together with a new accumulated offset value.

34. The apparatus of claim 33, wherein said control unit divides said 3-D buffer into a plurality of zones separated by zone boundaries, said merging and splitting being confined to said zones and not occurring across said zone boundaries, said zones and said zone boundaries being selected for enhancing image sharpness and accuracy.

35. The apparatus of claim 28, wherein:

said first bilinear interpolation unit has its input coupled to said 3-D buffer and its output coupled to said input of said slice unit;

said interslice ray segments extend along a plurality of sight rays cast from said view point through locations in said slice contained in said 2-D slice compositing buffer, said locations corresponding to grid point locations of said pixels within said compositing buffer, said sight rays intersecting said current slice at a plurality of intersection points;

said first bilinear interpolation unit receives voxel values associated with voxel locations adjacent said plurality of intersection points and interpolates among said voxel values to provide interpolated voxel values associated with said plurality of intersection points for combination with said pixels of said compositing buffer, results of said combination being stored, with an accumulated offset, in said grid point locations of said pixels within said compositing buffer; and

said control unit;

enables one of;

(i) merging of two or more of said interslice ray segments when two or more of said results of said interpolation and said combination are attempted to be stored at an identical grid point location; and

(ii) splitting of at least one of said interslice ray segments when adjacent interslice ray segments diverge beyond a divergence threshold;

maintains said sight rays throughout said sequential sweeping through said subsequent slices, except when one of said merging and said splitting is performed;

generates a new sight ray from said view point to a preselected location in the neighborhood of said identical grid point location when said merging is performed;

generates two new sight rays from said view point to corresponding preselected locations in said compositing buffer when said splitting is performed; and

said results of said interpolation and said combination in an adjacent one of said grid point locations when said accumulated offset exceeds a predetermined value, said storing being done together with a new accumulated offset value.

36. The apparatus of claim 35, wherein said control unit divides said 3-D buffer into a plurality of zones separated by zone boundaries, said merging and splitting being confined to individual zones and adjacent zones only and not occurring, for a given zone, across more than one of said zone boundaries on each side of said given zone, said zones and zone boundaries being selected for enhancing image sharpness and accuracy and for reduction of aliasing.

37. The apparatus of claim 28, further comprising:

(e) a global feedback connection between said pixel bus and said 3-D buffer, said global feedback connection forming a global feedback loop, said global feedback loop being configured for feedback from said pixel bus to said 3-D buffer, and subsequently to any intermediate stage in said plurality of rendering pipelines.