Resample and composite engine for real-time volume rendering

Abstract

The present invention is a digital electronic system for rendering a volume image in real time. The system accelerators the processing of voxels through early ray termination and space leaping techniques in the projection guided ray casting of the voxels. Predictable and regular voxel access from high-speed internal memory further accelerates the volume rendering. Through the acceleration techniques and devices of the present invention real-time rendering of parallel and perspective views, including those for stereoscopic viewing, are achieved.

1. A digital electronic system for real-time volume rendering of a 3D volume dataset comprising:
 a data-processing accelerator for reducing a number of voxels for rendering an image in real-time by selecting image-forming voxels that are non-transparent and non-occluded from a projection and by rejecting non-image-forming voxels that are transparent or occluded from the projection, wherein the voxels are a volume dataset of the image to be rendered contained in memory external to the system; 
 a control unit for forward projecting the 3D volume dataset at regularly spaced voxel positions to determine number of rays to be casted wherein said 3D volume dataset is divided into a plurality of voxel access blocks having a cubic array of voxel; 
 a processor for ray casting the rays of the image-forming voxels in a front-to-back order to form 2D representation of image planes; 
 a hardware engine for accelerating the real-time volume rendering by having the image-forming voxels available for processing without having to refetch a substantial number of the voxels from the external memory; 
 wherein the real-time image is rendered from the image-planes formed from the selected voxels. 
 
     
     
       2. The system of  claim 1  wherein the projection is a parallel projection. 
     
     
       3. The system of  claim 1  wherein the projection is a perspective projection. 
     
     
       4. The system of  claim 1  wherein the projection is a stereoscopic projection. 
     
     
       5. The system of  claim 1  wherein the ray casting includes early-ray termination and space leaping for selecting the image-forming voxels, wherein the image-forming voxels are non-occluded voxels and early-ray termination substantially avoids oversampling of the occluded voxels. 
     
     
       6. The system of  claim 1  wherein ray casting includes space leaping for selecting the image-forming voxels, wherein the image-forming voxels are non-transparent voxels and space leaping substantially avoids overprocessing of transparent voxels. 
     
     
       7. The system of  claim 1  wherein the hardware engine further comprises volume memory for storing a local copy of a small subset of the data volume defining the voxels, a rendering unit for implementing the ray casting of the stored data volume and pixel memory for storing output ray data from the rendering unit from which the real time image is to be rendered. 
     
     
       8. The system of  claim 1  wherein the hardware engine includes at least two processors and a controller synchronizes the processors. 
     
     
       9. The system of  claim 8  wherein the data volume of neighboring voxels is distributed between the at least two processors. 
     
     
       10. The system of  claim 9  wherein data volume from one processor is distributed in a circular fashion to the other processor for interpolating image-cast rays. 
     
     
       11. The system of  claim 10  wherein the volume memory is a high-speed internal static or dynamic random access memory and each processor has a dedicated connection the high-speed internal static or dynamic random access memory. 
     
     
       12. The system of  claim 11  wherein the image can be rendered from the hardware engine faster than all of the voxels in the volume dataset can be read from the external memory. 
     
     
       13. The system of  claim 1  further comprising a personal computer containing the external memory. 
     
     
       14. The system of  claim 1  further comprising a screen for viewing the rendered real-time image. 
     
     
       15. A method for rendering a real-time image comprising:
 retrieving a volume dataset from external memory; 
 subdividing the volume dataset into a plurality of voxel access blocks, wherein said voxel access blocks are a cubic array of voxels; 
 storing the voxel access blocks in high-speed internal memory; 
 forward projecting the voxels located at the corners of the block to determine number of rays to be casted, wherein said corner voxels correspond to a position of said block; 
 ray casting the rays in a front-to-back order to form a two-dimensional representation therefrom; 
 reducing a number of the voxels for rendering an image in real-time by selecting non-transparent voxels and non-occluded voxels and by rejecting transparent voxels or occluded voxels wherein the voxels are the volume dataset of the image to be rendered contained in said external memory; 
 processing the selected voxels to form pixels in a plurality of processors having interleaved memories for processing and distributing the voxels thereamong without having to refetch the voxels from the external memory; and 
 rendering a real-time image therefrom. 
 
     
     
       16. The method of  claim 5  further including wherein the step of reducing the number of voxels further includes early-ray termination for selecting the non-occluded voxels to substantially avoid oversampling of occluded rays. 
     
     
       17. The method of  claim 16  wherein the step of reducing the number of voxels further includes space-leaping to substantially avoid the overprocessing of the transparent voxels. 
     
     
       18. The method of  claim 16  further including processing the pixels and the voxels in high-speed internal random access memory to render the image therefrom faster than the step of retrieving the volume data set from the external memory. 
     
     
       19. A method for rendering a real-time image comprising:
 retrieving a volume dataset from external memory; 
 forward projecting the volume dataset at regularly spaced voxel positions to compute number of rays/pixels to be casted, wherein the dataset is divided into plurality of voxel access blocks having cubic array of voxels; 
 ray casting the rays/pixels in front-to-back order visiting all voxel access blocks except for transparent or occluded blocks without having to refetch the voxels from the external memory to form a 2D representation of image planes, wherein said image planes is a calculation of color, opacity and position of the rays/pixels. 
 
     
     
       20. A method for rendering a real-time image comprising:
 retrieving a volume dataset from external memory;   subdividing the volume dataset into a plurality of voxel access blocks;   storing the voxel access blocks in high-speed internal memory;   forward projecting the voxels located at the corners of the block to determine number of rays to be casted, wherein said corner voxels correspond to a position of said block;   ray casting the rays in a front-to-back order to form a two-dimensional representation therefrom;   reducing a number of the voxels for rendering an image in real-time by selecting non-transparent voxels and non-occluded voxels and by rejecting transparent voxels or occluded voxels wherein the voxels are the volume dataset of the image to be rendered contained in said external memory;   processing the selected voxels to form pixels in a plurality of processors having interleaved memories for processing and distributing the voxels thereamong without having to refetch the voxels from the external memory; and   rendering a real-time image therefrom.   
     
     
       21. A system for rendering a volume dataset, wherein the volume dataset includes a plurality of voxel blocks, wherein each of said voxel blocks includes two or more voxels, the system comprising:
 one or more rendering units;   a first memory configured to store said plurality of voxel blocks;   a control unit, wherein, for each of said plurality of voxel blocks, said control unit is configured to:
 identify, by performing a forward projection, a portion of a frame buffer corresponding to the voxel block; 
 determine whether the voxel block is selected for transfer from said first memory to said one or more rendering units, wherein said determination is based upon whether said voxel block is transparent and whether said voxel block is occluded relative to a current viewing position; and 
 transfer the voxel block from the first memory to said one or more rendering units in response to said determination indicating that the voxel block is selected for transfer; 
   wherein, for each voxel block, said one or more rendering units are configured to process, in front-to-back order, a set of rays passing through the corresponding portion of the frame buffer, and wherein said one or more rendering units are configured to terminate processing of rays determined to be occluded.   
     
     
       22. The system of claim 21, wherein the control unit is configured to perform said identification according to a front to back ordering of the voxel blocks. 
     
     
       23. The system of claim 21, wherein said performing the forward projection is based on a parallel projection, a perspective projection, or a stereoscopic projection. 
     
     
       24. The system of claim 21, wherein a first of the one or more rendering units is configured to determine whether a ray is occluded by comparing an opacity value of the ray to an opacity threshold. 
     
     
       25. The system of claim 21, wherein a first of the one or more rendering units is configured to perform space leaping on at least one of the rays of the set of rays in response to an indication that a current one of the voxel blocks and voxel blocks neighboring the current voxel block are transparent. 
     
     
       26. The system of claim 21, wherein the first memory comprises one or more volume memories coupled respectively to the one or more rendering units, wherein the plurality of voxels are partitioned among the one or more volume memories. 
     
     
       27. The system of claim 26, wherein each of the voxel blocks is partitioned among the one or more volume memories. 
     
     
       28. The system of claim 27, wherein each of the one or more rendering units is configured for circular distribution of voxels among the one or more rendering units. 
     
     
       29. The system of claim 21, wherein the frame buffer is partitioned among one or more pixel memories coupled respectively to the one or more rendering units. 
     
     
       30. The system of claim 29, wherein the control unit is further configured to transfer blocks of rays between the frame buffer and the one or more rendering units. 
     
     
       31. The system of claim 30, wherein the rays of each block of rays is distributed among the one or more pixel memories so that each of the one or more rendering units processes a corresponding portion of the rays in each block of rays. 
     
     
       32. The system of claim 21, wherein the one or more rendering units are configured to interpolate samples along the rays of said set of rays based on voxels of the transferred voxel block. 
     
     
       33. The system of claim 21, wherein a first of the one or more rendering units is configured to compute gradients from voxels of the transferred voxel block. 
     
     
       34. The system of claim 21 further comprising a personal computer containing the first memory. 
     
     
       35. The system of claim 21 further comprising a screen for viewing an image stored in the frame buffer. 
     
     
       36. The system of claim 21, where the frame buffer represents a rendered image of the volume dataset. 
     
     
       37. The system of claim 21, wherein, for each of the voxel blocks, the control unit is configured to issue blocks of rays to the one or more rendering units starting from a center of said portion of the frame buffer. 
     
     
       38. The system of claim 21, wherein a first of the one or more rendering units includes a ray caster unit, wherein the ray caster unit is configured to operate on rays by performing calculations including one or more of the following types of calculations: reconstruction, classification, shading, composition. 
     
     
       39. The system of claim 38, wherein the ray caster unit is configured to perform composition calculations, and wherein the first rendering unit further includes a ray interleave unit configured to interleave rays of said set of rays in order to prevent feedback in said composition calculations performed in the ray caster unit. 
     
     
       40. The system of claim 21, wherein the volume dataset is a computed tomography (CT) dataset or a magnetic resonance imaging (MRI) dataset. 
     
     
       41. The system of claim 21, wherein the volume dataset represents geophysical information. 
     
     
       42. The system of claim 21, wherein the volume dataset describes one or more properties of a fluid or of a chemical system. 
     
     
       43. The system of claim 21, wherein the system is a 3D graphics system. 
     
     
       44. The system of claim 21, wherein the system is a computer aided design (CAD) system. 
     
     
       45. The system of claim 21, wherein said determination includes determining that the voxel block is not selected for transfer based on information indicating that the voxel block is occluded relative to the current viewing position. 
     
     
       46. The system of claim 21, wherein said determination includes determining that the voxel block is selected for transfer based on information indicating that the voxel block is not occluded relative to the current viewing position and information indicating that the voxel block is not transparent. 
     
     
       47. The system of claim 21, wherein said determination includes determining that the voxel block is selected for transfer based on information indicating that said voxel block is transparent, information indicating that the voxel block is not occluded relative to a current viewing position, and information indicating that neighboring voxel blocks of said voxel block are transparent. 
     
     
       48. A system for rendering a volume dataset, wherein the volume dataset includes a plurality of voxel blocks, wherein each of said voxel blocks includes two or more voxels, the system comprising:
 one or more rendering means for performing rendering computations;   a first means for storing said plurality of voxel blocks;   a control means for:
 identifying, by performing a forward projection, a portion of a frame buffer corresponding to each of the voxel blocks; 
 determining whether the voxel block is selected for transfer from said first means to said one or more rendering means, wherein said determination is based upon whether said voxel block is transparent and whether said voxel block is occluded relative to a current viewing position; and 
 transferring the voxel block from the first means to said one or more rendering means in response to said determination indicating that the voxel block is selected for transfer; 
   wherein said one or more rendering means comprise means for:
 processing, in a front-to-back order, a set of rays passing through the portion of the frame buffer, and 
   
       terminating the processing of rays determined to be occluded. 
     
     
       49. The system of claim 48, wherein a first of said one or more rendering means includes a first buffer for buffering two slices of voxels. 
     
     
       50. The system of claim 49, wherein the first rendering means includes a second buffer for buffering one slice of gradient data. 
     
     
       51. The system of claim 48, where the frame buffer is configured to store data representing a two-dimensional array of pixels, wherein each pixel defines a corresponding ray relative to the viewing position, wherein the stored data for each pixel includes a color, an opacity and a position. 
     
     
       52. The system of claim 51, wherein the stored data for each pixel also includes an increment vector. 
     
     
       53. The system of claim 48, wherein said determination includes determining that the voxel block is not selected for transfer based on information indicating that the voxel block is occluded relative to the current viewing position. 
     
     
       54. The system of claim 48, wherein said determination includes determining that the voxel block is selected for transfer based on information indicating that the voxel block is not occluded relative to the current viewing position and information indicating that the voxel block is not transparent. 
     
     
       55. The system of claim 48, wherein said determination includes determining that the voxel block is selected for transfer based on: information indicating that said voxel block is transparent, information indicating that the voxel block is not occluded relative to a current viewing position, and information indicating that neighboring voxel blocks of said voxel block are transparent. 
     
     
       56. A method for rendering a volume dataset, wherein the volume dataset includes a plurality of voxel blocks, wherein each of said voxel blocks includes two or more voxels, the method comprising:
 a computer system storing the plurality of voxels in a first memory;   for each of the voxel blocks:
 the computer system identifying, by performing a forward projection, a portion of a frame buffer corresponding to the voxel block; 
 the computer system determining whether the voxel block is selected for retrieval from said first memory, wherein said determining is based upon whether said voxel block is transparent and whether said voxel block is occluded relative to a current viewing position; and 
 the computer system retrieving the voxel block from the first memory in response to said determination indicating that the voxel block is selected for retrieval; 
 processing, in front-to-back order, a set of rays passing through the corresponding portion of the frame buffer; and 
   
       the computer system terminating processing of rays determined to be occluded. 
     
     
       57. The method of claim 56, wherein each of the voxel blocks is retrieved from the first memory at most once per frame. 
     
     
       58. The method of claim 56, wherein said identifying the portion of a frame buffer corresponding to each of said voxel blocks is performed according to a front-to-back ordering of the voxel blocks. 
     
     
       59. The method of claim 56 further comprising:
 displaying an image from the frame buffer.   
     
     
       60. The method of claim 56 further comprising:
 determining that a ray is occluded by comparing an opacity value of the ray to an opacity threshold.   
     
     
       61. The method of claim 56 further comprising:
 performing space leaping on at least one of the rays of said set of rays in response to a determination that the voxel block and a plurality of neighboring voxel blocks are transparent.   
     
     
       62. The method of claim 56, wherein said determining includes determining that the voxel block is not selected for retrieval based on information indicating that the voxel block is occluded relative to the current viewing position. 
     
     
       63. The method of claim 56, wherein said determining includes determining that the voxel block is selected for retrieval based on information indicating that the voxel block is not occluded relative to the current viewing position and information indicating that the voxel block is not transparent. 
     
     
       64. The method of claim 56, wherein said determining includes determining that the voxel block is selected for retrieval based on information indicating that said voxel block is transparent, information indicating that the voxel block is not occluded relative to a current viewing position, and information indicating that neighboring voxel blocks of said voxel block are transparent. 
     
     
       65. A volume rendering controller configured to:
 access stored information to determine whether a block of voxels is selected for retrieval from a memory, wherein said stored information includes at least information specifying whether said block is transparent and information specifying whether said block is occluded relative to a current viewing position;   determine, by performing a forward projection, a portion of a frame buffer corresponding to the block;   output a clipping region of the block;   control a transfer of the block from the memory onto a first bus in response to a determination that the block is selected for retrieval.   
     
     
       66. The volume rendering controller of claim 65 further configured to:
 control a transfer of pixel tiles in the corresponding portion of the frame buffer onto a second bus.   
     
     
       67. The volume rendering controller of claim 65 further configured to:
 generate a space-leap flag for the block based on an examination of said information, wherein the space-leap flag indicates whether space-leaping is to be performed on one or more rays associated with said portion of the frame buffer; and   output the space leaping flag for the block.   
     
     
       68. The volume rendering controller of claim 65, wherein the volume rendering controller is further configured to determine that the block is not selected for retrieval based on the information indicating that the block is occluded relative to the current viewing position. 
     
     
       69. The volume rendering controller of claim 65, wherein the volume rendering controller is further configured to determine that the block is selected for retrieval based on the information indicating that the block is not occluded relative to the current viewing position and the information indicating that the block is not transparent. 
     
     
       70. The volume rendering controller of claim 65, wherein the volume rendering controller is further configured to determine that the block is selected for retrieval based on: the information indicating that said block is transparent, the information indicating that the block is not occluded relative to a current viewing position, and additional information indicating that blocks of voxels neighboring said block are transparent. 
     
     
       71. A method comprising:
 accessing stored information to determine whether a block of voxels is selected for retrieval from a memory, wherein said stored information includes at least information specifying whether said block is transparent and information specifying whether said block is occluded relative to a current viewing position;   determining, by performing a forward projection, a portion of a frame buffer corresponding to the block;   outputting a clipping region of the block;   controlling a transfer of the block from the memory onto a first bus in response to a determination that the block is selected for retrieval.   
     
     
       72. The method of claim 71 further comprising:
 controlling a transfer of pixel tiles in the corresponding portion of the frame buffer onto a second bus.   
     
     
       73. The method of claim 71 further comprising:
 generating a space-leap flag for the block based on an examination of said information, wherein the space-leap flag indicates whether space-leaping is to be performed on one or more rays associated with said portion of the frame buffer; and   outputting the space leaping flag for the block.   
     
     
       74. The method of claim 71 further comprising:
 determining that the block is not selected for retrieval based on the information indicating that the block is occluded relative to the current viewing position.   
     
     
       75. The method of claim 71 further comprising:
 determining that the block is selected for retrieval based on the information indicating that the block is not occluded relative to the current viewing position and the information indicating that the block is not transparent.   
     
     
       76. The method of claim 71 further comprising:
 determining that the block is selected for retrieval based on: the information indicating that said block is transparent, the information indicating that the block is not occluded relative to a current viewing position, and additional information indicating that blocks of voxels neighboring said block are transparent.   
     
     
       77. A medical imaging system for rendering a volume dataset, wherein the volume dataset includes a plurality of voxel blocks, wherein each of said voxel blocks includes two or more voxels, the system comprising:
 one or more rendering units;   a first memory configured to store said plurality of voxel blocks;   a control unit, wherein, for each of said plurality of voxel blocks, said control unit is configured to:
 identify, by performing a forward projection, a portion of a frame buffer corresponding to the voxel block; 
 determine whether the voxel block is selected for transfer from said first memory to the one or more rendering units, wherein said determination is based upon whether said voxel block is transparent and whether said voxel block is occluded relative to a current viewing position; and 
 transfer the voxel block from the first memory to said one or more rendering units in response to said determination indicating that the voxel block is selected for transfer; 
   
       wherein, for each voxel block, said one or more rendering units are configured to process, in front-to-back order, a set of rays passing through the corresponding portion of the frame buffer, and wherein the one or more rendering units are configured to terminate processing of rays determined to be occluded. 
     
     
       78. The medical imaging system of claim 77, wherein the volume dataset is a medical information dataset. 
     
     
       79. The medical imaging system of claim 77, wherein said determination includes determining that the voxel block is not selected for transfer based on information indicating that the voxel block is occluded relative to the current viewing position. 
     
     
       80. The medical imaging system of claim 77, wherein said determination includes determining that the voxel block is selected for transfer based on information indicating that the voxel block is not occluded relative to the current viewing position and information indicating that the voxel block is not transparent. 
     
     
       81. The medical imaging system of claim 77, wherein said determination includes determining that the voxel block is selected for transfer based on: information indicating that said voxel block is transparent, information indicating that the voxel block is not occluded relative to a current viewing position, and information indicating that neighboring voxel blocks of said voxel block are transparent. 
     
     
       82. A system for rendering a volume dataset, wherein the volume dataset includes a plurality of voxel blocks, wherein each of said voxel blocks includes an array of voxels, the system comprising:
 a plurality of rendering units;   a first memory configured to store said plurality of voxel blocks;   a control unit, wherein, for each of said plurality of voxel blocks, said control unit is configured to:
 identify, by performing a forward projection, a portion of a frame buffer corresponding to the voxel block; 
 determine whether the voxel block is selected for transfer from said first memory to at least one of the plurality of rendering units, wherein said determination is based upon information regarding whether said voxel block is transparent and information regarding whether said voxel block is occluded relative to a current viewing position; and 
 transfer the voxel block from the first memory to said at least one rendering unit in response to said determination indicating that the voxel block is selected for transfer; 
   
       wherein, for each voxel block, said at least one rendering unit is configured to process, in front-to-back order, a set of rays passing through the corresponding portion of the frame buffer, and wherein said at least one rendering unit is configured to perform early ray termination on rays determined to be occluded. 
     
     
       83. The system of claim 82, wherein the control unit is configured to perform said identification of the portion of the frame buffer corresponding to each of said voxel blocks according to a front-to-back ordering of the voxel blocks. 
     
     
       84. The system of claim 82, wherein the at least one rendering unit is configured to determine that a ray is occluded by comparing an opacity value of the ray to an opacity threshold. 
     
     
       85. The system of claim 82, wherein the at least one rendering unit is configured to perform space leaping on at least one of the rays of the set of rays in response to an indication that a current one of the voxel blocks is transparent. 
     
     
       86. The system of claim 82, wherein the at least one rendering unit is configured to interpolate samples along one or more of the rays of said set of rays based on voxels of the transferred voxel block. 
     
     
       87. The system of claim 82, wherein the array of voxels is a rectangular array. 
     
     
       88. The system of claim 82, wherein the array of voxels is a cubic array. 
     
     
       89. The system of claim 82, wherein said determination includes determining that the voxel block is not selected for transfer based on information indicating that the voxel block is occluded relative to the current viewing position. 
     
     
       90. The system of claim 82, wherein said determination includes determining that the voxel block is selected for transfer based on information indicating that the voxel block is not occluded relative to the current viewing position and information indicating that the voxel block is not transparent. 
     
     
       91. The system of claim 82, wherein said determination includes determining that the voxel block is selected for transfer based on: information indicating that said voxel block is transparent, information indicating that the voxel block is not occluded relative to a current viewing position, and information indicating that neighboring voxel blocks of said voxel block are transparent.