Volume Body Renderer

Abstract

Irregular volumes within one or more three-dimensional volume datasets are identified and extracted in response to criteria. The processing involves automatically finding a seed voxel or seed cell that meets the criteria and thus belongs to an irregular volume of interest, and then identifying cells related to the seed cell by one or more predetermined relationships that are therefore also to be grouped into that irregular volume. Information, which can be of any suitable type, identifying each such cell as being related to other cells and belonging to an irregular volume is stored in a suitable data structure. The location or similar neighborhood information and other data describing properties or attributes of the identified cell are also stored. Because the irregular volumes are extracted and pre-processed in this manner, operations including rendering them on a display and performing Boolean and arithmetic operations on them can readily be performed.

1 . A computer-implemented method for identifying irregular volumes represented within volumetric input data, comprising the steps of:
 inputting one or more volume datasets comprising a multiplicity of three-dimensional cells;   establishing criteria describing properties of an irregular volume of interest;   processing each volume dataset, the processing comprising the steps of:
 traversing from cell to cell of the volume dataset until a seed cell is identified having properties matching the criteria, the identified seed cell thereby belonging to an identified irregular volume; 
 identifying cells related to the seed cell by a predetermined relationship as belonging to the identified irregular volume; 
 storing in a data structure associated with each identified cell belonging to the identified irregular volume, attribute data describing properties of the identified cell, the attribute data including an indication of the location of the identified cell with respect to a predetermined frame of reference and including an identifier uniquely identifying the identified cell as belonging to the identified irregular volume; and 
   rendering at least a portion of the one or more volume datasets representing at least a portion of the identified irregular volume, the irregular volume portion comprising at least one internal cell and at least one boundary cell.   
     
     
         2 . The method claimed in  claim 1 , wherein the predetermined relationship is adjacency of cells within the volume dataset. 
     
     
         3 . The method claimed in  claim 1 , wherein the predetermined relationship is cells within the volume dataset meeting predetermined wavelet characteristics. 
     
     
         4 . The method claimed in  claim 1 , wherein the predetermined relationship is cells within a predetermined neighborhood distance of the seed cell. 
     
     
         5 . The method claimed in  claim 1 , wherein the predetermined relationship is cells belonging to an irregular volume within a predetermined size range. 
     
     
         6 . The method claimed in  claim 1 , wherein the predetermined relationship is cells belonging to another irregular volume previously processed, whereby the previously processed irregular volume defines a template. 
     
     
         7 . The method claimed in  claim 1 , wherein the predetermined relationship is cells having a gradient value within a predetermined range. 
     
     
         8 . The method claimed in  claim 1 , wherein the predetermined relationship is cells having a transparence attribute with a value within a predetermined range. 
     
     
         9 . The method claimed in  claim 1 , wherein the predetermined relationship is cells having a selected attribute with a value within a predetermined range. 
     
     
         10 . The method claimed in  claim 1 , wherein the predetermined relationship is cells located in a selected region with respect to a predetermined user-provided geometric surface or geometric shape. 
     
     
         11 . The method claimed in  claim 1 , wherein the step of identifying cells related to the seed cell by a predetermined relationship as belonging to the identified irregular volume is performed by a recursive computer process traversing from each identified cell to an adjacent cell. 
     
     
         12 . The method claimed in  claim 1 , wherein the attribute data include a data-collection attribute from the one or more volume datasets and at least one value of the data-collection attribute of the identified cell. 
     
     
         13 . The method claimed in  claim 1 , wherein the attribute data further include an indication of whether the identified cell is a boundary cell or whether the identified cell is an internal cell. 
     
     
         14 . The method claimed in  claim 1 , wherein the attribute data further include information describing neighboring cells. 
     
     
         15 . The method claimed in  claim 1 , wherein the step of traversing from cell to cell of the volume dataset until a seed cell is identified includes storing information identifying the identified seed cell in a seed cell table. 
     
     
         16 . The method claimed in  claim 1 , further comprising:
 establishing a division of at least one of the volume datasets into a plurality of portions; and   wherein the step of processing each volume dataset comprises processing at least one selected portion of the plurality of portions until each irregular volume in the selected portion is processed.   
     
     
         17 . The method claimed in  claim 16 , wherein irregular volumes in one portion are processed by a separate computer process from irregular volumes in another portion. 
     
     
         18 . The method claimed in  claim 16 , wherein:
 the step of establishing a division of at least one of the volume datasets into a plurality of portions comprises establishing a division of each of a plurality of volume datasets into a plurality of portions; and   wherein irregular volumes in one portion are processed by a separate computer process from irregular volumes in another portion.   
     
     
         19 . The method claimed in  claim 1 , wherein:
 the inputting step comprises inputting a plurality of volume datasets, each comprising a multiplicity of three-dimensional voxels or cells; and   the processing step comprises processing each of the plurality of volume datasets, whereby irregular volumes identified in each volume dataset are stored in a data structure of the same type as the data structure in which irregular volumes identified in all other volume datasets are stored; and   the attribute data further include an irregular volume identifier uniquely identifying an irregular volume from all other irregular volumes.   
     
     
         20 . The method claimed in  claim 1 , further comprising the steps of:
 selecting an identified seed cell belonging to an identified irregular volume;   identifying cells belonging to the same irregular volume as the identified seed cell by retrieving identifiers from the data structures and comparing the identifiers; and   retrieving from the data structures, indications of the locations of the cells identified as belonging to the same irregular volume as the identified seed cell.   
     
     
         21 . The method claimed in  claim 20 , further comprising the step of rendering a graphical depiction of at least a portion of the identified irregular volume by rendering a graphical depiction of cells identified as belonging to the same irregular volume as the identified seed cell. 
     
     
         22 . The method claimed in  claim 21 , further comprising the step of:
 retrieving from the data structures, attributes indicating whether cells identified as belonging to the same irregular volume as the identified seed cell are boundary cells; and   wherein the step of rendering a graphical depiction of at least a portion of the identified irregular volume comprises rendering a graphical depiction of each boundary cell identified as belonging to the same irregular volume as the identified seed cell, whereby the boundary cells are shaded to represent an irregular volume surface.   
     
     
         23 . The method claimed in  claim 1 , further comprising the steps of:
 retrieving from the data structures stored, volume attribute data describing a property of each identified cell belonging to a first identified irregular volume;   retrieving from the data structures stored, volume attribute data describing a property of each identified cell belonging to a second identified irregular volume; and   performing an operation between volume attribute data describing a property of each identified cell belonging to the first identified irregular volume and volume attribute data describing a property of each identified cell belonging to the second identified irregular volume.   
     
     
         24 . The method claimed in  claim 23 , wherein the operation is a Boolean operation. 
     
     
         25 . The method claimed in  claim 23 , wherein the operation is an arithmetic operation. 
     
     
         26 . The method claimed in  claim 23 , wherein the operation is an algorithmic operation performed upon the second identified irregular volume using the first identified irregular volume as a template. 
     
     
         27 . The method claimed in  claim 23 , wherein the operation is a merge operation combining the first identified irregular volume with the second identified irregular volume. 
     
     
         28 . A computer program product for identifying irregular volumes represented within volumetric input data, comprising a computer-usable medium carrying thereon a:
 means for inputting one or more volume datasets comprising a multiplicity of three-dimensional cells;   means for establishing criteria describing properties of an irregular volume of interest;   means for processing each volume dataset, the means for processing comprising a:
 means for traversing from cell to cell of the volume dataset until a seed cell is identified having properties matching the criteria, the identified seed cell thereby belonging to an identified irregular volume; 
 means for identifying cells related to the seed cell by a predetermined relationship as belonging to the identified irregular volume; 
 means for storing in a data structure associated with each identified cell belonging to the identified irregular volume, attribute data describing properties of the identified cell, the attribute data including an indication of the location of the identified cell with respect to a predetermined frame of reference and including an identifier uniquely identifying the identified cell as belonging to the identified irregular volume; and 
   means for rendering at least a portion of the one or more volume datasets representing at least a portion of the identified irregular volume, the irregular volume portion comprising at least one internal cell and at least one boundary cell.   
     
     
         29 . The computer program product claimed in  claim 28 , wherein the predetermined relationship is adjacency of cells within the volume dataset. 
     
     
         30 . The computer program product claimed in  claim 28 , wherein the predetermined relationship is cells within the volume dataset meeting predetermined wavelet characteristics. 
     
     
         31 . The computer program product claimed in  claim 28 , wherein the predetermined relationship is cells within a predetermined neighborhood distance of the seed cell. 
     
     
         32 . The computer program product claimed in  claim 28 , wherein the predetermined relationship is cells belonging to an irregular volume within a predetermined size range. 
     
     
         33 . The computer program product claimed in  claim 28 , wherein the predetermined relationship is cells belonging to another irregular volume previously processed, whereby the previously processed irregular volume defines a template. 
     
     
         34 . The computer program product claimed in  claim 28 , wherein the predetermined relationship is cells having a gradient value within a predetermined range. 
     
     
         35 . The computer program product claimed in  claim 28 , wherein the predetermined relationship is cells having a transparence attribute with a value within a predetermined range. 
     
     
         36 . The computer program product claimed in  claim 28 , wherein the predetermined relationship is cells having a selected attribute with a value within a predetermined range. 
     
     
         37 . The computer program product claimed in  claim 28 , wherein the predetermined relationship is cells located in a selected region with respect to a predetermined user-provided geometric surface or geometric shape. 
     
     
         38 . The computer program product claimed in  claim 28 , wherein identifying cells related to the seed cell by a predetermined relationship as belonging to the identified irregular volume is performed by a recursive computer process traversing from each identified cell to an adjacent cell. 
     
     
         39 . The computer program product claimed in  claim 28 , wherein the attribute data include a data-collection attribute from the one or more volume datasets and at least one value of the data-collection attribute of the identified cell. 
     
     
         40 . The computer program product claimed in  claim 28 , wherein the attribute data further include an indication of whether the identified cell is a boundary cell or whether the identified cell is an internal cell. 
     
     
         41 . The computer program product claimed in  claim 28 , wherein the attribute data further include information describing neighboring cells. 
     
     
         42 . The computer program product claimed in  claim 28 , wherein traversing from cell to cell of the volume dataset until a seed cell is identified includes storing information identifying the identified seed cell in a seed cell table. 
     
     
         43 . The computer program product claimed in  claim 28 , further comprising a:
 means for establishing a division of at least one of the volume datasets into a plurality of portions; and   wherein processing each volume dataset comprises processing at least one selected portion of the plurality of portions until each irregular volume in the selected portion is processed.   
     
     
         44 . The computer program product claimed in  claim 43 , wherein irregular volumes in one portion are processed by a separate computer process from irregular volumes in another portion. 
     
     
         45 . The computer program product claimed in  claim 43 , wherein:
 the means for establishing a division of at least one of the volume datasets into a plurality of portions comprises a means for establishing a division of each of a plurality of volume datasets into a plurality of portions; and   wherein irregular volumes in one portion are processed by a separate computer process from irregular volumes in another portion.   
     
     
         46 . The computer program product claimed in  claim 28 , wherein:
 the means for inputting comprises a means for inputting a plurality of volume datasets, each comprising a multiplicity of three-dimensional voxels or cells;   the means for processing comprises means for processing each of the plurality of volume datasets, whereby irregular volumes identified in each volume dataset are stored in a data structure of the same type as the data structure in which irregular volumes identified in all other volume datasets are stored; and   the attribute data further include an irregular volume identifier uniquely identifying an irregular volume from all other irregular volumes.   
     
     
         47 . The computer program product claimed in  claim 28 , further comprising a:
 means for selecting an identified seed cell belonging to an identified irregular volume;   means for identifying cells belonging to the same irregular volume as the identified seed cell by retrieving identifiers from the data structures and comparing the identifiers; and   means for retrieving from the data structures, indications of the locations of the cells identified as belonging to the same irregular volume as the identified seed cell.   
     
     
         48 . The computer program product claimed in  claim 47 , further comprising a means for rendering a graphical depiction of at least a portion of the identified irregular volume by rendering a graphical depiction of cells identified as belonging to the same irregular volume as the identified seed cell. 
     
     
         49 . The computer program product claimed in  claim 48 , further comprising a:
 means for retrieving from the data structures, attributes indicating whether cells identified as belonging to the same irregular volume as the identified seed cell are boundary cells; and   wherein the means for rendering a graphical depiction of at least a portion of the identified irregular volume comprises a means for rendering a graphical depiction of each boundary cell identified as belonging to the same irregular volume as the identified seed cell, whereby the boundary cells are shaded to represent an irregular volume surface.   
     
     
         50 . The computer program product claimed in  claim 28 , further comprising a:
 means for retrieving from the data structures stored, volume attribute data describing a property of each identified cell belonging to a first identified irregular volume;   means for retrieving from the data structures stored, volume attribute data describing a property of each identified cell belonging to a second identified irregular volume; and   means for performing an operation between volume attribute data describing a property of each identified cell belonging to the first identified irregular volume and volume attribute data describing a property of each identified cell belonging to the second identified irregular volume.   
     
     
         51 . The computer program product claimed in  claim 50 , wherein the operation is a Boolean operation. 
     
     
         52 . The computer program product claimed in  claim 50 , wherein the operation is an arithmetic operation. 
     
     
         53 . The computer program product claimed in  claim 50 , wherein the operation is an algorithmic operation performed upon the second identified irregular volume using the first identified irregular volume as a template. 
     
     
         54 . The computer program product claimed in  claim 50 , wherein the operation is a merge operation combining the first identified irregular volume with the second identified irregular volume.