Method and System for Adaptive Maximum Intensity Projection Ray Casting

Abstract

The adaptive MIP ray casting system first fragments a 3-D dataset into multiple sub-volumes and constructs an octree data structure with each sub-volume being associated with one node of the octree data structure. The system then establishes a 2-D image plane and selectively launches a plurality of rays towards the 3-D dataset, each ray adaptively interacting with a subset of the sub-volumes and identifies the maximum data value along the ray path. The maximum data value is then converted into a pixel value on the 2-D image plane. Finally, the system interpolates pixel values at those locations where no pixel value is generated by ray casting and thereby generates a 2-D image of the 3-D dataset.

1 . A method of adaptive maximum intensity projection ray casting, comprising:
 fragmenting a sampled 3-D dataset of a scalar field into a plurality of sub-volumes of different sizes, each sub-volume associated with a set of data value parameters characterizing the data value distribution of the scalar field within the sub-volume;   defining a screen transfer function that is dependent upon data values of the scalar field;   selectively casting a plurality of rays towards the sampled dataset, each ray having an initial data value record wherein the step of selectively casting is performed on a computer processor and comprises, for each ray,
 adaptively selecting a subset of the plurality of sub-volumes of different sizes that are located along a path of the ray based on the data value distribution of the scalar field within the sub-volumes that are located along the path of the ray; 
 identifying a maximum data value on the ray path that is within the selected subset; and 
 converting the maximum data value into a pixel value in a 2-D image plane according to the screen transfer function; and 
   wherein the step of selectively casting a plurality of rays towards the sampled dataset further comprises:
 subdividing the 2-D image plane into a plurality of mini-planes; and for each of the plurality of mini-planes, 
 estimating four pixel values at four corners of the mini-plane; and 
 recursively subdividing the mini-plane into multiple sub-planes, and estimating pixel values at other locations in the sub-planes by casting rays towards the sampled dataset until a maximum pixel value differential of each sub-plane is below a predefined imaging error threshold; and 
 using the pixel values determined for the cast rays to estimate other pixel values at other locations in the 2-D image plane. 
   
     
     
         2 . The method of  claim 1 , wherein the step of fragmenting a sampled 3-D dataset includes:
 fragmenting the sampled dataset into eight sub-volumes; and   for each sub-volume, recursively fragmenting it into eight smaller sub-volumes until the size of the smallest sub-volumes reaches a predefined size limit.   
     
     
         3 . The method of  claim 2 , wherein the predefined size limit is a sub-volume comprising 2×2×2 3-D cells, a data value of the scalar field being associated with each corner of each cell. 
     
     
         4 . The method of  claim 3 , wherein each cell has eight corners and the data value at a location within the cell is tri-linearly interpolated using the data values at the eight corners of the cell. 
     
     
         5 . The method of  claim 1  wherein the set of data value parameters associated with a sub-volume include a maximum, an average, and a minimum data value of the scalar field within the sub-volume. 
     
     
         6 . The method of  claim 1 , further comprising:
 constructing an octree data structure having a root node, a plurality of intermediate nodes and a plurality of leaf nodes;   associating the root node with the sampled 3-D dataset;   associating each of the plurality of leaf nodes with one of the smallest sub-volumes; and   associating each of the plurality of intermediate nodes with one of the sub-volumes that is larger than the smallest sub-volume.   
     
     
         7 . (canceled) 
     
     
         8 . The method of  claim 1 , wherein the maximum pixel value differential of a sub-plane is defined as the maximum deviation of pixel values at the four corners of the sub-plane from the average pixel value of the sub-plane. 
     
     
         9 . The method of  claim 1 , wherein the predefined imaging error threshold is adjusted by an image rendering speed provided by a user, a distance to an edge of an object embedded in the 3-D dataset, and a difference between a pixel value estimated from an adaptive MIP ray casting and a pixel value estimated from a bi-linear interpolation. 
     
     
         10 . The method of  claim 1  wherein the step of selecting a subset of the plurality of sub-volumes that are located along the ray path includes:
 identifying a largest sub-volume that encounters the ray along the ray path and its associated set of data value parameters; 
 estimating a maximum screen value differential of the sub-volume using the ray's current data value record and the sub-volume's associated set of data value parameters; and 
 recursively selecting a smaller sub-volume contained in the sub-volume until the estimated maximum screen value differential of the smaller sub-volume is below a predefined threshold. 
 
     
     
         11 . (canceled) 
     
     
         12 . The method of  claim 1 , wherein the step of identifying the maximum data value on the ray path that is within the selected subset of the plurality of sub-volumes includes
 estimating a data value at a predefined position of a sub-volume;   updating the ray's current data value record if the estimated data value is higher than the current data value record; and   repeating said estimating and updating steps against every remaining sub-volume of the subset until the ray exits the sampled dataset.   
     
     
         13 . The method of  claim 12 , wherein the sub-volume is a smallest sub-volume comprising 2×2×2 cells, or a cell or a sub-cell whose dimension is at least above the crosssection of the ray. 
     
     
         14 . The method of  claim 1 , wherein the step of using the pixel values determined for the cast rays to estimate other pixel values at other locations includes for each of the other locations,
 selecting four pixel values surrounding the location and associated with four cast rays; and   bi-linearly interpolating a pixel value at the location using the four pixel values.   
     
     
         15 . An adaptive maximum intensity projection (MIP) ray casting system, comprising:
 one or more central processing units for executing programs;   a user interface for receiving a plurality of MIP ray casting parameters; and   an adaptive MIP ray casting engine module executable by the one or more central processing units, the module comprising:
 instructions for fragmenting a sampled 3-D dataset of a scalar field into a plurality of sub-volumes of different sizes, each sub-volume associated with a set of data value parameters characterizing the data value distribution of the scalar field within the subvolume; 
 instructions for defining a screen transfer function that is dependent upon data values of the scalar field; 
 instructions for selectively casting a plurality of rays towards the sampled dataset, each ray having an initial current data value record; 
 instructions for adaptively selecting a subset of the plurality of sub-volumes of different sizes that are located on a ray path based on the data value distribution of the scalar field within the sub-volumes that are located along the path of the ray; 
 instructions for identifying a maximum data value on the ray path that is within the selected subset; 
 instructions for converting the maximum data value into a pixel value in a 2-D image plane according to the screen transfer function; and 
 wherein the instructions for selectively casting a plurality of rays towards the sampled dataset further comprise instructions for: 
 subdividing the 2-D image plane into a plurality of mini-planes; and for each of the plurality of mini-planes, 
 estimating four pixel values at four corners of the mini-planes; and 
 recursively subdividing the mini-plane into multiple sub-planes, and 
 estimating pixel values at other locations in the sub-planes by casting rays towards the sampled dataset until a maximum pixel value differential of each sub-plane is below a predefined imaging threshold; and 
 instructions for using the pixel values determined for the cast rays to estimate other pixel values at other locations in the 2-D image plane. 
   
     
     
         16 . The system of  claim 15 , wherein the instructions for fragmenting a sampled 3-D dataset include:
 fragmenting the 3-D dataset into eight sub-volumes; and   for each sub-volume, recursively fragmenting it into eight smaller sub- volumes until the size of the smallest sub-volumes reaches a predefined size limit.   
     
     
         17 . The system of  claim 16 , wherein the predefined size limit is a sub-volume comprising 2×2×2 3-D cells, a data value of the scalar field being associated with each corner of each cell. 
     
     
         18 . The system of  claim 17 , wherein each cell has eight corners and the data value at any location within the cell is tri-linearly interpolated using the data values at the eight corners of the cell. 
     
     
         19 . The system of  claim 15 , wherein the set of data value parameters include a maximum, an average, and a minimum data value of the scalar field within the sub-volume. 
     
     
         20 . The system of  claim 15 , further comprises:
 instructions for constructing an octree data structure comprising a root node, a plurality of intermediate nodes and a plurality of leaf nodes;   instructions for associating the root node with the 3-D dataset;   instructions for associating each of the plurality of leaf nodes with a smallest sub-volume from the plurality of sub-volumes; and   instructions for associating each of the plurality of intermediate nodes with a sub-volume from the plurality of sub-volumes that is larger than the smallest sub-volume.   
     
     
         21 - 53 . (canceled)