Method and apparatus for storing, accessing, and processing voxel-based data

• US 4,985,856 A
• Filed: 11/10/1988
• Issued: 01/15/1991
• Est. Priority Date: 11/10/1988
• 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: Bakalash, Reuven, Kaufman, Arie E.
• Primary Examiner(s): Harkcom, Gary V.
• Assistant Examiner(s): Zimmerman, Mark K.
• Application Number:
  US07/269,567
• Time in Patent Office: 796 Days
• Field of Search: 364/522, 340/729, 378/901
• US Class Current: 345/424
• CPC Class Codes: G06T 1/60 Memory management

Abstract

A method and apparatus for storing to and accessing from a memory device, one or more voxels of a beam disposed along one or more of a plurality of storage/retrieval directions of a 3-D matrix array in 3-D discrete voxel space. Voxels are stored into memory space by mapping the voxels along one of the plurality of storage/retrieval directions, into a plurality of independently addressable memory modules in memory storage space. Each memory module is indexed by a memory module index and has internal memory cell addresses. The mapping is carried out in accordance with a linear skewing function which expressed in terms of x, y, and z coordinate directions and integer n. The voxels can be retrieved along one or more of a plurality of storage/retrieval directions by de-mapping one or more of the voxels from the memory storage space into 3-D voxel space using spacial parameters and integer n. The demapping operations of the present method are also used in order to determine the voxel depth measures of voxels along one of the storage/retrieval directions.

Claims

1. A method of storing and retrieving one or more voxels of a beam disposed along one or more of a plurality of storage/retrieval directions of a 3 -D matrix array in 3-D discrete voxel space, said 3 - D discrete voxel space being specified in terms of x, y and z coordinate directions, said method comprising the steps of:

(a) storing said voxels into memory storage space, by mapping said voxels along one of said plurality of storage/retrieval directions, into a plurality of n independently accessible memory modules in said memory storage space, each said memory module being indexed with memory module indices k=0, 1 . . . n-1 and each said k-th memory module having n² internal memory cell addresses, said n being an integer and each said memory cell provided with internal module indices, i and j, said mapping being carried out in accordance with a linear skewing function of the general form

space="preserve" listing-type="equation">k=(ax+by+cz) mod n

where x, y and z are the coordinate values of each said voxel in said 3 -D discrete voxel space, where i=x and j=y, and where a, b and c are integer coefficients and n is a prime relative to said integer coefficients a, b and c, and linear combinations of said integer coefficients a, b and c the number of storage/retrieval directions in said n³ matrix array in said 3- D discrete voxel space being based upon the values of said integers a, b, c and n; and

(b) retrieving said voxels along one of said plurality of storage/retrieval directions in said 3-D voxel space, by demapping said one or more voxels along said beam by

(i) determining each voxel depth measure representative of the depth of each said voxel in said n³ matrix array in aid 3- D discrete voxel space, said determination of said voxel depth measure being determined based on one or more of said x, y and z coordinate values of said voxel, said integer coefficients a, b and c, and said module index k of said memory module into which said voxel has been mapped in step (a).

(ii) for each voxel along said beam parallel to said storage/retrieval direction, determining said memory cell indices i and j on the basis of said voxel depth measure and said x, y and z coordinate values corresponding to each said voxel, and

(iii) identifying each voxel along a specified storage/retrieval direction using said memory cell indices i and j resulting from step b (ii) and said module index k resulting from step a.

2. The method according to claim 1, wherein each said integer coefficients a, b and c equals 1, so as to provide six storage/retrieval directions corresponding to the principal axes ±

x, ±

y, ±

z of said n³ matrix array.

3. The method according to claim 2, wherein step (a) (i) comprises determining for each said voxel, said voxel depth measures d₃₀ x and d_-x for said voxels along said beams parallel to the x principal axis, said voxel depth measure d_+y and d_-y for said voxels along said beams parallel to the y principal axis, and said voxel depth measure d_+z and d_-z for said voxels along said beams parallel to said z principal axis, being determined, respectively, according to the functions

d_+x =(k-(y+z)) mod n

d_-x =n-d_+x -1

d_+y =(k-(x+z)) mod n

d_-y =n-d_+y -1

d_+z =(k-(x+y)) mod n

d_-z =n-d_+z -1

4. The method according to claim 1, wherein said integer coefficient a equals 5, said integer coefficient b equals 2, and said integer coefficient c equals 1, so as to provide twenty-six storage/retrieval directions of said n³ matrix array in said 3-D discrete voxel space.

5. A method of determining which voxel in a plurality of voxels along a beam parallel to a storage/retrieval direction of an n³ matrix array in 3-D discrete voxel space, is closest to an observer viewing along said beam, said 3-D discrete voxel space being specified in terms of x, y and z coordinate directions, said method comprising the sequence of steps of:

(a) mapping said voxels along said beam parallel to said storage/retrieval direction into a plurality of n independently accessible memory modules being indexed with module indices k=0, 1, . . . , n-1, each said k-th memory module containing n² memory cells, each said memory cell being specified by internal module indices i and j, said mapping being carried out in accordance with a linear skewing function of the general form

space="preserve" listing-type="equation">k=(ax+by+cz) mod n

where x, y and z are the coordinate values of each said voxel in said 3-D discrete voxel space, where i=x and j=y, and where a, b and c are integer coefficients, the number of storage/retrieval directions in said n³ matrix array in said 3-D discrete voxel space being based upon the values of said integers a, b, c and n;

(b) for each said voxel in said string of voxels along said beam parallel to said storage/retrieval direction, determining a voxel depth measure representative of the depth of each said voxel in said n³ matrix array in said 3-D discrete voxel space, said determination of said voxel depth measure being determined for each said voxel on the basis of one or more of said x, y and z coordinate values of said voxel, said integer coefficients a, b, and c, and said module index of said memory module into which said voxel has been mapped in step (a); and

(c) comparing said voxel depth measures determined in step (b), so as to determine which voxel depth measure a predetermined extreme value, and thereby representative of the corresponding voxel being closest to said observer viewing along said beam parallel to said storage/retrieval direction.

6. The method of claim 5, wherein said voxel is further specified by a transparency parameter which is either a transparent or a non-transparent voxel value, and wherein said method further comprises prior to step (c),

determining said voxels having a non-transparent voxel value, and wherein step (c) comprises

comparing only said voxel depth ,measures determined in step (b) which correspond to said voxels determined above as having a non-transparent value, so as to determine which voxel having a non-transparent voxel value, has a predetermined extreme voxel depth measure value, and thereby representative of said voxel being closest to said observer viewing along said beam parallel to said storage/retrieval direction.

7. The method of claim 6, wherein said method comprises, prior to step (c),

determining said non-transparent voxels along said beam, which have corresponding voxel depth measures within at least one predetermined depth measure range

wherein step (c) comprises

comparing only said voxel depth measures determined in step (b) which correspond to said non-transparent voxels determined above as having corresponding voxel depth measures within said predetermined depth measure range, so as to determine which voxel within said predetermined depth measure range, has a predetermined extreme voxel depth measure, and thereby representative of said voxel being closest to said observer viewing along said beam parallel to said storage/retrieval direction.

8. The method of claim 5 wherein each said voxel depth measure is represented by a plurality of binary digits, and wherein said comparison of voxel depth measures comprises

(i) comparing the most significant binary digit of each said voxel depth measure,

(ii) determining which voxels have the predetermined extreme voxel depth measure, on the basis of comparing said most significant binary digits,

(iii) forming a group of voxels from the determination performed in step (ii),

(iv) comparing the next consecutive most significant binary digits of voxel depth measures of said voxels in said voxel group formed in step (iii),

(v) determining which voxels in said voxel group have the predetermined extreme voxel depth measure, on the basis of comparing said next consecutive largest significant binary digits, and

(vi) repeatedly performing said comparing, determining and group formation steps on the basis of consecutive significant binary digits, until only one surviving voxel depth measure remains in said group, said surviving voxel depth measure corresponding to said voxel being the closest to said observer viewing along said storage/retrieval direction.

9. The method of claim 8, which further comprises, for a plurality of beams parallel to said storage/retrieval direction, each said beam having a plurality of voxels therealong,

(1) mapping said plurality of voxels along each said beam, into said plurality of n independently accessible memory modules according to said linear skewing function,

(2) determining a voxel depth measure for each said non-transparent voxel along each said beam,

(3) for each said voxel along each said beam, comparing said voxel depth measures corresponding to said non-transparent voxels, so as to determine which voxel depth measure is a predetermined extreme value, and thereby representative of the corresponding non-transparent voxel being closest to said observer viewing along said beam parallel to said storage/retrieval direction, and

(4) forming a two-dimensional image from said plurality of non-transparent voxel values determined in step (3) above.

10. A method of mapping the voxels of an n³ matrix array in 3-D discrete voxel space, into a plurality of n independently accessible memory modules, said 3-D discrete voxel space being specified in terms of x, y and z coordinate directions,

said method comprising:

(a) defining a plurality of 3-D voxel subspaces sequentially numbered module n, for K=0, 1, . . . n-1, and grouping together each said K-th 3-D voxel subspace, each said K-th 3-D voxel subspace containing a set of voxels having x, y and z coordinate values;

(b) providing a plurality of independently accessible nxn memory modules indexed K=0, 1, . . . n-1, each said K-th memory module containing n² memory cells, each memory cell being specified by internal module indices, i, j;

(c) assigning each grouping of said K-th 3-D voxel subspaces to said K-th memory module; and

(d) for each said voxel having said x, y and z coordinates, mapping from said 3-D voxel space, into said K-th memory module according to

space="preserve" listing-type="equation">K=(5x+2y+z) mod n

and into the (i, j)-th memory cell according to x=i and y=j.

11. Apparatus for simultaneously storing and retrieving a beam of voxels disposed parallel to a storage/retrieval direction of an n³ matrix array in 3-D discrete voxel space, said 3-D discrete voxel space being specified in terms of x, y and z coordinate directions, said apparatus comprising:

storing means for storing said voxels into memory storage space, by mapping said voxels along one of said plurality of storage/retrieval directions, into a plurality of n independently accessible memory modules in said memory storage space, each said memory module being indexed by a memory module index and having internal memory cell addresses, said n being an integer, said mapping being carried out in accordance with a skewing function expressed in terms of said x, y and z coordinate directions and said integer n; and

retrieving means for retrieving said voxels along one of said plurality of storage/retrieval directions in said 3-D voxel space, by demapping said one or more voxels from said memory storage space into said 3-D voxel space using spatial parameters and said integer n, said retrieving means comprising;

(i) a plurality of n modules being indexed with module indices K=0, 1, . . . n-1, each said k-th module including a k-th memory module, a k-th local address unit for independently accessing said k-th memory module, each said memory cell of each said k-th memory module being specified by internal module indices i and j, each said k-th local address unit including a local voxel depth computation unit for computing a voxel depth measure of each voxel residing in said k-th memory module, said voxel depth measure of each voxel being representative of the depth of said voxel in said n³ matrix array, and being determined on the basis of one or more of said x, y and z coordinate values of said voxel, said integer coefficients a, b and c, and said module index k of said memory module into which said voxel is mapped, said local addressing unit further including means for determining for each said voxel, said memory cell indices i and j on the basis of said voxel depth measure and said x, y and z coordinate values corresponding to each said voxel, and memory cell index selection means for selecting memory cell indices i and j from global memory cell indices i" and j" and said voxel depth measures along said storage/retrieval directions,

(ii) a central control unit including a central addressing unit for generating module indices k"=0, 1, . . . n-1, and global memory cell indices i" and j", said central addressing unit further including means for carrying out the mapping of said voxels along said beams parallel to said storage/retrieval direction, into said plurality of n independently accessible memory modules, said mapping being carried out in accordance with a linear skewing function of the general form

space="preserve" listing-type="equation">k=(ax+by+cz) mod n

where x, y and z are the coordinate values of each said voxel in said 3-D discrete voxel space, where i=x and j=y, and where a, b and c are integer coefficients and n is a prime relative to said integer coefficients a, b and c, or to linear combinations of said integer coefficients a, b, and c of the number of storage/retrieval directions in said n³ matrix array being based upon the values of said integers a, b, c and n,

(iii) means for transferring global memory cell indices i" and j" from said central addressing unit to said plurality of n local address units, and

(iv) means for transferring said beam of voxels, into or from said n memory modules.

12. The apparatus of claim 11, wherein each said k-th module further comprises

a voxel multiple write processing unit for processing voxels accessed from said k-th memory module,

a k-th voxel value storage register for storing the k-th voxel value of the k-th voxel along said beam parallel to said storage/retrieval direction,

a k-th voxel depth measure register for storing said voxel depth measure of said k-th voxel along said beam parallel to said storage/retrieval direction,

a k-th voxel depth competition unit for locally comparing the value of said voxel depth measure of said k-th voxel with all other voxels of said beam parallel to said storage/retrieval direction, and determining which said voxel depth measure has a predetermined extreme value and generating a voxel pass control signal corresponding to said voxel depth measure having said predetermined extreme value, and

writing means for writing into a two-dimensional frame buffer, said voxel value stored in said k-th voxel value storage register corresponding to said voxel pass control signal.

13. Apparatus of claim 12, which further includes means for providing transparency control parameters to said voxel multiple write processing units, each said k-th voxel multiple write processing unit further including

a k-th voxel transparency control unit for receiving said transparency control parameters and for controlling the local comparison of said voxel depth measures within said k-th voxel depth competition unit, said voxel depth competition control being carried out on the basis of said voxel value in said k-th voxel value register and said transparency control parameters.

14. Apparatus of claim 12, wherein each said voxel depth measure is represented by a plurality of binary bits, and wherein said local voxel depth competition unit comprises means for

(i) comparing the most significant binary bits of each said voxel depth measure,

(ii) determining which voxels have a predetermined extreme voxel depth measure, on the basis of comparing said most significant binary bits,

(iii) forming a group of voxels from the determination performed in step (ii),

(iv) comparing the next consecutive most significant binary bits of voxel depth measures of said voxels in said voxel group formed in step (iii),

(v) determining which voxels in said voxel group have the predetermined extreme voxel depth measure, on the basis of comparing said next consecutive most significant binary bits.

15. The apparatus of claim 12, which further includes intermodule voxel value moving means for moving voxel values stored in said k-th voxel value storage registers, to other voxel value storage registers.

16. The apparatus of claim 11, wherein each said k-th local address unit includes a local comparison means for comparing the voxel depth measure of each said voxel with at least one preselected voxel depth measure range, and controlling the local comparison of said voxel depth measures within said k-th voxel depth competition unit, said voxel depth competition control being carried out on the basis of said voxel being within said preselected voxel depth measure range.

17. A 3-D voxel-based graphics system comprising:

a memory and addressing system for storing and retrieving 3-D voxel based images along a plurality of storage/retrieval directions in 3-D discrete voxel space, said memory and addressing system including a plurality of modules each said module having a memory module, and a local address unit, for independently addressing said memory module;

a central addressing unit for simultaneously transmitting to each said module, broadcasted addresses and control parameters;

means for transferring said broadcasted addresses and control parameters to each said module; and

means for transferring said voxel-based images into or from said n memory modules.

18. The 3-D voxel-based graphics system of claim 17, wherein said system further comprises

at least one voxel-based processor for accessing said n memory modules.

19. The 3-D voxel-based graphics system of claim 18 wherein said voxel-based processor is selected from the group consisting of a 3-D geometry processor, a 3-D frame buffer processor, and 3-D viewing processor.