Apparatus and method for associating voxel information with display positions

Abstract

An apparatus and method of associating display positions on a display with display information associated with voxels in a voxel block where the voxels are mappable to a display coordinate system defined by a view plane. The method and apparatus involve scanning voxel positions in the voxel block, according to a scan order in which column positions in respective planes through the voxel block which are progressively farther from a base point in the voxel block are addressed in order of those which map to foreground positions in the view plane before those which map to more background positions in the view plane to produce position specifiers identifying renderable voxel positions in the voxel block, determining respective display positions for each position specifier according to a display position mapping and associating respective display positions with corresponding position specifiers such that position specifiers which map to display positions which already associated with position specifiers identify more foreground positions on the display are not associated with display positions.

What is claimed is:  
     
         1 . A method of associating display positions on a display, with display information associated with voxels in a voxel block, said voxels being mappable to a display coordinate system defined by a view plane, in said display coordinate system, the method comprising: 
 scanning voxel positions in said voxel block, according to a scan order in which column positions, in respective planes through said voxel block which are progressively farther from a base point of said voxel block are addressed in order of those which map to foreground positions in said view plane before those which map to more background positions in said view plane, to produce position specifiers identifying renderable voxel positions in said voxel block;    determining respective display positions for each position specifier according to a display position mapping; and    associating respective display positions with corresponding position specifiers such that position specifiers which map to display positions which are already associated with position specifiers identifying more foreground positions on said display are not associated with display positions.    
     
     
         2 . The method of  claim 1  wherein associating comprises assigning references associated with respective said position specifiers to respective display positions, said references identifying display attributes of voxels at said respective position specifiers.  
     
     
         3 . The method of  claim 2  further comprising providing said respective display positions and their associated references to a rendering routine.  
     
     
         4 . The method of  claim 1  further comprising identifying said renderable voxel positions.  
     
     
         5 . The method of  claim 4  wherein identifying said renderable voxel positions comprises identifying columns within a renderable column range.  
     
     
         6 . The method of  claim 5  wherein identifying columns comprises addressing a plane and producing column addresses of columns progressively farther from an edge of said voxel block, in said plane.  
     
     
         7 . The method of  claim 6  further comprising producing a position specifier for each voxel associated with a column address, when said column address is within said renderable column range.  
     
     
         8 . The method of  claim 7  wherein identifying renderable voxels comprises identifying columns which have active voxels.  
     
     
         9 . The method of  claim 8  wherein identifying columns, which have active voxels, comprises producing a column address and using said column address to locate active voxels in the column identified by said column address.  
     
     
         10 . The method of  claim 5  wherein producing said column address comprises addressing a plane and producing column addresses of columns progressively farther from an edge of said voxel block, in said plane.  
     
     
         11 . The method of  claim 1  further comprising determining a plane axis along which each plane in said succession of planes is defined.  
     
     
         12 . The method of  claim 11  further comprising determining a column axis and producing column addresses specifying columns progressively farther from said plane axis in a plane in said succession of planes until a column address of a column within a renderable column range and having active voxels is located.  
     
     
         13 . The method of  claim 12  wherein producing column addresses comprises producing a plane coordinate along said plane axis to specify a plane orthogonal to said plane axis and producing a column coordinate along said column axis to specify a column in said plane specified by said plane coordinate.  
     
     
         14 . The method of  claim 13  wherein producing said position specifier comprises producing a set of coordinates specifying a column of voxels in an x-z plane of said voxel block and specifying a voxel in said column of voxels, said plane coordinate and said column coordinate specifying said column in said x-z-plane and a y-coordinate of said voxel block specifying said voxel in said column specified by said plane and column coordinates.  
     
     
         15 . The method of  claim 1  further comprising storing an indication of whether or not a position specifier has been associated with a given display position.  
     
     
         16 . The method of  claim 15  further comprising reading said indication when said given display position is computed for a given position specifier and outputting said reference to said given position specifier when said indication indicates that a position specifier has not already been associated with said given display position.  
     
     
         17 . The method of  claim 1  further comprising executing an initialization routine prior to producing said set of position identifiers.  
     
     
         18 . The method of  claim 17  wherein executing said initialization routine comprises determining said scan order and establishing a mapping between coordinates in said voxel block and said display positions.  
     
     
         19 . The method of  claim 17  wherein computing said scan order comprises determining said base point and determining plane and column axes of said voxel block.  
     
     
         20 . The method of  claim 19  wherein determining said base point comprises mapping corners of said voxel block, to said display coordinate system and producing normalized corner vectors for each mapped corner of said voxel block.  
     
     
         21 . The method of  claim 20  further comprising finding a base corner vector from the origin in said display coordinate system to a mapped corner point of said voxel block, wherein said base corner vector forms a larger angle than all other corner vectors with a display orientation vector representing an orientation of said view plane.  
     
     
         22 . The method of  claim 21  further comprising determining said display orientation vector.  
     
     
         23 . The method of  claim 22  wherein determining said display orientation vector comprises finding which of two orthogonal vectors and their corresponding parity reverse counterparts, along display axes in the display coordinate system, is most parallel to a vector in the display coordinate system representing a mapping of a y-axis of the voxel block.  
     
     
         24 . The method of  claim 19  wherein determining a plane axis comprises determining an edge of said voxel block, that contains said base point and that appears to extend in a direction progressing most rapidly away from said view plane when mapped to said display coordinate system and defining said plane axis as a line in said voxel coordinate system, coincident with said edge.  
     
     
         25 . The method of  claim 24  wherein determining a column axis comprises defining as said column axis a line in said coordinate system which is coincident with said base point and which intersects said plane axis and which is at an angle to a y-axis of said voxel block.  
     
     
         26 . The method of  claim 18  further comprising computing a parallel projection mapping for mapping points in said voxel block to points in said display coordinate system.  
     
     
         27 . The method of  claim 18  further comprising producing a clipping table and using said clipping table to determine whether a voxel is renderable.  
     
     
         28 . The method of  claim 27  wherein producing a clipping table comprises producing a table having fields associated with corresponding columns in said voxel block.  
     
     
         29 . The method of  claim 28  further comprising populating said fields with indicators indicating whether or nor a set of position indicators is to be produced for corresponding columns.  
     
     
         30 . The method of  claim 28  further comprising populating said fields with a range indicator indicating a range of voxels within a corresponding column, for which a set of position indicators is to be produced.  
     
     
         31 . The method of  claim 18  further comprising initializing a priority completion buffer.  
     
     
         32 . The method of  claim 31  further comprising storing in said priority completion buffer an indication of whether or not a given display position has been associated with a reference to a position specifier.  
     
     
         33 . The method of  claim 32  further comprising reading said indication when said given display position is computed for a given position specifier and outputting said reference to said given position specifier when said indication indicates that a position specifier has not already been associated with said given display position.  
     
     
         34 . A method of associating display positions on a display, with display information associated with voxels in a voxel block, said voxels being mappable to a display coordinate system defined by a view plane, in said display coordinate system, the method comprising: 
 for each plane in a succession of planes comprised of voxel columns in said voxel block, where said planes are progressively farther from said view plane and progressively farther from a base point in said voxel block, producing a set of position specifiers for renderable voxels in each column of said each plane;    computing a display position for each position specifier in said set; and    producing a reference to one of said position specifiers if a reference to said one of said position specifiers has not already been produced for said display position.    
     
     
         35 . A method of associating display positions on a display, with display information associated with voxels in a voxel block, said voxels being mappable to a display coordinate system defined by a view plane, in said display coordinate system, the method comprising: 
 establishing a mapping between coordinates in said voxel block and display positions of said display;    computing a scan order for scanning positions of said voxel block;    scanning positions in said voxel block in said scan order and producing position specifier for positions which are to be considered for rendering; and    using said mapping to produce a display position for each position specifier, and producing a reference to said position specifier if a reference to said position specifier has not already been produced for said display position.    
     
     
         36 . A method of associating display positions on a display, with display information associated with voxels in a voxel block, said voxels being mappable to a display coordinate system defined by a view plane, said voxel block having a base point in a voxel coordinate system, which maps to a point closest to said view plane, in said display coordinate system, the method comprising: 
 determining from said voxel block and said view plane a parallel projection mapping for mapping points in said voxel block coordinate system to points in said display coordinate system;    employing said parallel projection mapping to determine which corner of said voxel block appears closest to the view plane and to determine which edge of said voxel block appears to extend in a direction progressing most rapidly away from said view plane;    defining a plane axis as an axis which is coincident with said edge which appears to extend in a direction progressing most rapidly away from said view plane and defining a column axis as a line which intersects said plane axis and which is at an angle to a y-axis of said voxel block;    producing voxel position specifiers, each comprising a coordinate on said plane axis, a coordinate on said column axis and a coordinate on said y-axis, of voxels in columns, parallel to the column axis for successive positions along the plane axis which are progressively farther from said view plane; and    computing a display position for each position specifier; and    producing a reference to said position specifier if a reference to said position specifier has not already been produced for said display position.    
     
     
         37 . An apparatus for associating display positions on a display, with display information associated with voxels in a voxel block, said voxels being mappable to a display coordinate system defined by a view plane, in said display coordinate system, the apparatus comprising: 
 scanning means for scanning voxel positions in said voxel block, according to a scan order in which column positions, in respective planes through said voxel block which are progressively farther from a base point in said voxel block are addressed in order of those which map to foreground positions in said view plane before those which map to more background positions in said view plane, to produce position specifiers identifying renderable voxel positions in said voxel block;    mapping means for determining respective display positions for each position specifier according to a display position mapping; and    associating means for associating respective display positions with corresponding position specifiers such that position specifiers which map to display positions which are already associated with position specifiers identifying more foreground positions on said display are not associated with display positions    
     
     
         38 . A computer readable medium for providing computer-readable instructions for directing a processor circuit to associate display positions on a display, with display information associated with voxels in a voxel block, said voxels being mappable to a display coordinate system defined by a view plane, in said display coordinate system, the instructions comprising: 
 a first code segment for directing the processor circuit to scan voxel positions in said voxel block, according to a scan order in which column positions, in respective planes through said voxel block which are progressively farther from a base point in said voxel block are addressed in order of those which map to foreground positions in said view plane before those which map to more background positions in said view plane, to produce position specifiers identifying renderable voxel positions in said voxel block;    a second code segment for directing the processor to determine respective display positions for each position specifier according to a display position mapping; and    a third code segment for directing the processor circuit to associate respective display positions with corresponding position specifiers such that position specifiers which map to display positions which are already associated with position specifiers identifying more foreground positions on said display are not associated with display positions.    
     
     
         39 . A signal comprising code segments for directing a processor circuit to associate display positions on a display, with display information associated with voxels in a voxel block, said voxels being mappable to a display coordinate system defined by a view plane, in said display coordinate system, the code segments comprising: 
 a first code segment for directing the processor circuit to scan voxel positions in said voxel block, according to a scan order in which column positions, in respective planes through said voxel block which are progressively farther from a base point in said voxel block are addressed in order of those which map to foreground positions in said view plane before those which map to more background positions in said view plane, to produce position specifiers identifying renderable voxel positions in said voxel block;    a second code segment for directing the processor to determine respective display positions for each position specifier according to a display position mapping; and    a third code segment for directing the processor circuit to associate respective display positions with corresponding position specifiers such that position specifiers which map to display positions which are already associated with position specifiers identifying more foreground positions on said display are not associated with display positions.    
     
     
         40 . An apparatus for associating display positions on a display, with display information associated with voxels in a voxel block, said voxels being mappable to a display coordinate system defined by a view plane, in said display coordinate system, the apparatus comprising: 
 a scanner for scanning voxel positions in said voxel block, according to a scan order in which column positions, in respective planes through said voxel block which are progressively farther from a base point in said voxel block are addressed in order of those which map to foreground positions in said view plane before those which map to more background positions in said view plane, to produce position specifiers identifying renderable voxel positions in said voxel block;    a mapper for determining respective display positions for each position specifier according to a display position mapping; and    an associator which associates respective display positions with corresponding position specifiers such that position specifiers which map to display positions which are already associated with position specifiers identifying more foreground positions on said display are not associated with display positions.    
     
     
         41 . The apparatus of  claim 40  wherein said associator is operable to assign references associated with respective said position specifiers to respective display positions, said references identifying display attributes of voxels at said respective position specifiers.  
     
     
         42 . The apparatus of  claim 41  further comprising an output for providing said respective display positions and their associated references to a rendering routine.  
     
     
         43 . The apparatus of  claim 40  further comprising an identifier for identifying said renderable voxel positions.  
     
     
         44 . The apparatus of  claim 43  wherein said identifier is operable to identify columns within a renderable column range.  
     
     
         45 . The apparatus of  claim 44  wherein said identifier is operable to address a plane in said succession of planes and produce column addresses of columns progressively farther from an edge of said voxel block, in said plane.  
     
     
         46 . The apparatus of  claim 45  wherein said identifier is operable to produce a position specifier for each voxel associated with a column address, when said column address is within said renderable column range.  
     
     
         47 . The apparatus of  claim 46  wherein said identifier is operable to identify renderable voxels comprises identifying columns which have active voxels.  
     
     
         48 . The apparatus of  claim 47  wherein said identifier is operable to produce a column address and use said column address to locate active voxels in the column identified by said column address.  
     
     
         49 . The apparatus of  claim 44  wherein said identifier is operable to address a plane in said succession of planes and to produce column addresses of columns progressively farther from an edge of said voxel block, in said plane.  
     
     
         50 . The apparatus of  claim 40  wherein said scanner is operable to determine a plane axis along which each plane in said succession of planes is defined.  
     
     
         51 . The apparatus of  claim 50  wherein said scanner is operable to determine a column axis and produce column addresses specifying columns progressively farther from said plane axis in a plane in said succession of planes until a column address of a column within a renderable column range and having active voxels is located.  
     
     
         52 . The apparatus of  claim 51  wherein said scanner is operable to produce a plane coordinate along said plane axis to specify a plane orthogonal to said plane axis and produce a column coordinate along said column axis to specify a column in said plane specified by said plane coordinate.  
     
     
         53 . The apparatus of  claim 52  wherein said scanner is operable to produce a set of coordinates specifying a column of voxels in an x-z plane of said voxel block and specify a voxel in said column of voxels, said plane coordinate and said column coordinate specifying said column in said x-z-plane and a y-coordinate of said voxel block specifying said voxel in said column specified by said plane and column coordinates.  
     
     
         54 . The apparatus of  claim 40  further comprising a processor circuit for storing an indication of whether or not a position specifier has been associated with a given display position.  
     
     
         55 . The apparatus of  claim 54  further comprising a processor circuit for reading said indication when said given display position is computed for a given position specifier and for outputting said reference to said given position specifier when said indication indicates that a position specifier has not already been associated with said given display position.  
     
     
         56 . The apparatus of  claim 40  further comprising a processor circuit for executing an initialization routine prior to producing said set of position identifiers.  
     
     
         57 . The apparatus of  claim 56  wherein said processor circuit is operable to determine said scan order and establish a mapping between coordinates in said voxel block and said display positions.  
     
     
         58 . The apparatus of  claim 57  wherein said processor circuit is operable to determine said base point and determine plane and column axes of said voxel block.  
     
     
         59 . The apparatus of  claim 58  wherein said processor circuit is operable to map corners of said voxel block, to said display coordinate system and produce normalized corner vectors for each mapped corner of said voxel block.  
     
     
         60 . The apparatus of  claim 59  wherein said processor circuit is operable to find a corner vector, from the origin in said display coordinate system, to a mapped corner point of said voxel block, wherein said base corner vector forms a larger angle than all other corner vectors with a display orientation vector representing an orientation of said view plane.  
     
     
         61 . The apparatus of  claim 60  wherein said processor circuit is operable to determine said display orientation vector.  
     
     
         62 . The apparatus of  claim 61  wherein said processor circuit is operable to find which of two orthogonal vectors and their corresponding parity reverse counterparts, along display axes in the display coordinate system, is most parallel to a vector in the display coordinate system representing a mapping of a y-axis of the voxel block.  
     
     
         63 . The apparatus of  claim 58  wherein said processor circuit is operable to determine an edge of said voxel block, that contains said base point and that appears to extend in a direction progressing most rapidly away from said view plane when mapped to said display coordinate system and to define said plane axis as a line in said voxel coordinate system, coincident with said edge.  
     
     
         64 . The apparatus of  claim 63  wherein said processor circuit is operable to define as said column axis a line in said coordinate system which is coincident with said base point and which intersects said plane axis and which is at an angle to a y-axis of said voxel block.  
     
     
         65 . The apparatus of  claim 57  wherein said processor circuit is operable to compute a parallel projection mapping for mapping points in said voxel block to points in said display coordinate system.  
     
     
         66 . The apparatus of  claim 57  wherein said processor circuit circuit is operable to produce a clipping table and using said clipping table to determine whether a voxel is renderable.  
     
     
         67 . The apparatus of  claim 66  wherein said processor circuit is operable to produce a table having fields associated with corresponding columns in said voxel block.  
     
     
         68 . The apparatus of  claim 67  wherein said processor circuit is operable to populate said fields with indicators indicating whether or nor a set of position indicators is to be produced for corresponding columns.  
     
     
         69 . The apparatus of  claim 67  wherein said processor circuit is operable to populate said fields with a range indicator indicating a range of voxels within a corresponding column, for which a set of position indicators is to be produced.  
     
     
         70 . The apparatus of  claim 57  further comprising a priority completion buffer.  
     
     
         71 . The apparatus of  claim 70  wherein said processor circuit is operable to store in said priority completion buffer an indication of whether or not a given display position has been associated with a reference to a position specifier.  
     
     
         72 . The apparatus of  claim 71  wherein said processor circuit is operable to read said indication when said given display position is computed for a given position specifier and to output said reference to said given position specifier when said indication indicates that a position specifier has not already been associated with said given display position.