Method and apparatus for generating arbitrary projections of three-dimensional voxel-based data

• US 5,101,475 A
• Filed: 04/17/1989
• Issued: 03/31/1992
• Est. Priority Date: 04/17/1989
• Status: Expired due to Fees

• Current Assignee: The Research Foundation of State University of New York
• Original Assignee: The Research Foundation for The State University of New York (State University of New York)
• Inventors: Shimony, Solomon E., Kaufman, Arie E.
• Primary Examiner(s): Harkcom, Gary V.
• Assistant Examiner(s): Zimmerman, Mark K.
• Application Number:
  US07/339,438
• Time in Patent Office: 1,079 Days
• Field of Search: 364/522, 364/521, 364/413.19, 364/413.22
• US Class Current: 345/424
• CPC Class Codes: G06T 17/00 Three dimensional [3D] modelling, e.g. data description of 3D objects

Abstract

A device for generating parallel and perspective projections of 3-D voxel-based images, viewed along arbitrary viewing directions. The method involves using retrieval parameters to retrieve voxels of the 3-D voxel-based image from discrete 3-D voxel space. Then, the 3-D voxel-based image is viewed along an arbitrary viewing direction specified by viewing parameters in a manner independent of the retrieval parameters. Apparatus is also provided using a 3-D voxel-based image viewed along an arbitrary viewing direction specified by viewing parameters in a manner independent of the retrieval parameters. Apparatus is also provided utilizing a 3-D memory storage device organized in accordance with a 3-D skewed memory storage scheme, and providing for conflict-free retrieval of voxel-based retrieval rays along a retrieval direction of the memory storage device.

Claims

1. A method for viewing a 3-D voxel-based image represented in discrete 3-D voxel space, said method comprising the steps of:

(a) retrieving the voxels of said 3-D voxel-based image along at least one retrievel direction using retrieval parameters; and

(b) along any arbitrary viewing direction specificable by viewing parameters, viewing said 3D voxel-based image in said discrete 3-D voxel space, independent of said retrieval parameters; and

(c) storing said 3-D voxel image is said discrete 3-D voxel space according to a first skewed memory storage scheme which provides for said simultaneous accessing of said plurality of voxels along at least one said retrieval direction so as to form a plurality of voxel based retrieval rays, said first skewed memory storage scheme involving mapping the voxels of said 3-D voxel-based image in said discrete 3-D voxel space into a first skewed memory storage space.

2. The method of claim 1, wherein said 3-D voxel space is specified in terms of coordinate directions, and wherein step (a) comprises, for each said voxel-based retrieval ray,

(i) accessing from said first skewed memory storage space, said voxels of said voxel-based retrieval ray, and

(ii) demapping said voxel-based retrieval ray along at least one of said coordinate directions, said demapping being based upon said skewed memory storage scheme, and

(iii) storing each said demapped retrieval ray in a second memory storage space according to a 2-D skewed memory storage scheme, said second skewed memory storage space providing for simultaneous access to the voxels of a plurality of voxel-based fetching rays along a plurality of fetching directions extending through said second skewed memory storage space, and

wherein step (b) comprises, for each said voxel-based fetching ray in said second skewed memory storage space,

(i) accessing from said second skewed memory storage space, said voxels of said voxel-based fetching ray,

(ii) demapping said voxel-based fetching ray along another said coordinate direction, said demapping being based upon said 2-D skewed memory storage scheme, and

(iii) storing each said demapped fetching ray in said discrete 3-D space,

whereby a plurality of voxel-based viewing rays is formed on the basis of said plurality of retrieval rays, wherefrom said 3-D voxel-based image can be viewed along said arbitrary viewing direction independent of said retrieval directions.

3. The method of claim 2, wherein step (b) further comprises,

for each viewing ray,

analyzing said viewing ray so as to determine the first non-transparent voxel along said viewing ray which is closest to an observer viewing said 3-D voxel-based image.

10. The method of claim 1, which further comprises

storing said 3-D voxel-based image in said discrete 3-D voxel space according to a first skewed memory storage scheme, which provides for said simultaneous accessing of said plurality of voxels along at least one said retrieval direction, sand first skewed memory storage scheme involving mapping the voxels of said 3-D voxel-based image in said discrete 3-D voxel space, into a first skewed memory storage space.

11. The method of claim 10, wherein step (a) comprises

retrieiving said plurality of voxels along at least one of said retrieval directions in said 3-D voxel space by demapping said voxels from said first skewed memory storage space, into said 3-D voxel space.

12. The method of claim 10, wherein said 3-D voxel space is specified in terms of coordinate directions, and wherein step (a) comprises, for each said voxel-based retrieval ray,

(i) accessing from said first skewed memory storage space, said voxels of said voxel-based retrieval ray, and

(ii) demapping said voxel-based retrieval ray along at least one of said coordinate directions, said demapping being based upon said skewed memory storage scheme, and

(iii) storing each said demapped retrieval ray in a second memory storage space according to a 2-D skewed memory storage scheme, said second skewed memory storage space providing for simultaneous access to the voxels of a plurality of voxel-based fetching rays along a plurality of fetching directions extending through said second skewed memory storage space, and

wherein step (b) comprises, for each said voxel-based fetching ray in said second skewed memory storage space,

(i) accessing from said second skewed memory storage space, said voxels of said voxel-based fetching ray,

(ii) demapping said voxel-based fetching ray along another coordinate direction, said demapping being based upon said 2-D skewed memory storage scheme, and

(iii) storing each said demapped fetching ray in said discrete 3-D space,

whereby a plurality of voxel-based projection rays is formed on the basis of said plurality of retrieval rays.

4. A method of generating an arbitrary projection of a 3-D voxel-based image represented in discrete 3-D voxel space, said 3-D voxel space providing for access to the voxels along a plurality of retrieval directions extending through said 3-D voxel space, said method comprising the steps:

(a) retrieving a plurality of voxels along at least one said retrievel direction;

(b) (i) forming a plurality of projection ray planes on the basis of said plurality of retrieved voxels,

(ii) forming said plurality of voxel-based projection rays on the basis of said plurality of projection ray planes formed in substep (b) (i); and

(c) generating said arbitrary projection of said 3-D voxel based image on the basis of said plurality of voxel-based projection rays.

5. A method for generating an arbitrary projection of a 3D voxel-based image represented in discrete 3-D voxel space, said 3-D voxel space providing for access to the voxels along a plurality of retrieval directions extending through said 3-D voxel space, said method comprising the steps:

(a) retrieving a plurality of voxels along at least one said retrieval direction;

(b) (i) forming a plurality of voxel-based retrieval rays on the basis of said plurality of retrieved voxels;

(ii) forming a plurality of voxel-based projection rays on the basis of said plurality of voxel-based retrieval rays; and

(c) generating said arbitrary projection of said 3-D voxel-based image on the basis of said plurality of voxel-based projection rays.

6. The method of claim 5, wherein substep (b)(i) comprises

forming a plurality of projection ray arrangements on the basis of said plurality of voxel-based retrieval rays, and

substep (b)(ii) comprises

forming a plurality of voxel-based projection rays on the basis of said plurality of projection ray arrangements formed in step (b)(i).

7. The method of claim 5, wherein substep (b)(i) comprises

(A) forming a plurality of projection ray planes on the basis of said plurality of voxel-based retrieval rays, and

substep (b)(ii) comprises

(B) forming a plurality of voxel-based projection rays on the basis of said plurality of projection ray planes formed in step (b)(ii).

8. The method of claim 7, wherein step (c) comprises,

for each said projection ray in said projection ray plane,

analyzing said projection ray so as to determine the first non-transparent voxel along said projection ray which is closest to an observer viewing said 3-D voxel-based image, thereby generating said arbitrary projection thereof.

9. The method of claim 8, wherein step (a) comprises

simultaneously accessing said plurality of voxels along at least one said retrieval direction, so as to form said plurality of voxel-based retrieval rays.

13. A method for generating an arbitrary projection of a 3-D voxel-based image represented in discrete 3-D voxel space, said 3-D voxel space providing for access to the voxels along a plurality of retrieval directions extending through said discrete 3-D voxel space, said method comprising the steps of:

(a) specifying a plurality of voxel-based projection ray planes extending through said discrete 3-D voxel space;

(b) for each said voxel-based projection ray plane,

(i) retrieving a plurality of voxels along at least one said retrieval direction,

(ii) forming a plurality of voxel-based projection rays on the basis of said plurality of retrieved voxels in step (i), and

(iii) generating an arbitrary projection of said voxel-based projection ray plane, on the basis of said plurality of voxel-based projection rays; and

(c) on the basis of said arbitrary projections of said voxel-based projection ray planes, forming said arbitrary projection of said 3-D voxel-based image.

14. The method of claim 13, wherein step (b)(iii) comprises,

for each said projection ray in said projection ray plane,

analyzing said projection ray so as to determine the first non-transparent voxel along said projection ray which is closest to an observer viewing said 3-D voxel-based image, thereby generating said arbitrary projection of said projection ray plane.

15. The method of claim 14, wherein step (b)(i) comprises

simultaneously accessing said plurality of voxels along at least one said retrieval direction, so as to form said plurality of voxel-based retrieval rays.

16. The method of claim 15, which further comprises

storing said 3-D voxel-based image in said discrete 3-D voxel space according to a 3-D skewed memory storage scheme, which provides for said simultaneous accessing of said plurality of voxels along at least one said retrieval direction, said 3-D skewed memory storage scheme involving mapping the voxels of said voxel-based image in said discrete 3-D voxel space, into a 3-D skewed memory storage space.

17. The method of claim 16, wherein substep (b)(i) comprises

retrieving said plurality of voxels along at least one of said retrieval directions in said 3-D voxel space by demapping said voxels from said 3-D skewed memory storage space, into said 2-D voxel space.

18. The method of claim 16, wherein said 3-D voxel space is specified in terms of coordinate directions, and wherein substep (b)(i) comprises, for each said voxel-based projection plane,

(i) accessing from said 3-D skewed memory storage space, said voxels of said voxel-based retrieval ray, and

(ii) demapping said voxel-based retrieval ray along at least one of said coordinate directions, said demapping being based upon said 3-D skewed memory storage scheme, and

(iii) storing each said demapped retrieval ray in a 2-D memory storage space according to a 2-D skewed memory storage scheme, said 2-D skewed memory storage space providing for simultaneous access to the voxels of a plurality of voxel-based fetching rays along a plurality of fetching directions extending through said 2-D skewed memory storage space, and

wherein substep (b)(ii) comprises, for each said voxel-based fetching ray in said 2-D skewed memory storage space,

(i) accessing from said 2-D skewed memory storage space, said voxels of said voxel-based fetching ray,

(ii) demapping said voxel-based fetching ray along another coordinate direction, said demapping being based upon said 2-D skewed memory storage scheme, and

(iii) storing each said demapped fetching ray in said discrete 2-D voxel space,

whereby a plurality of voxel-based projection rays is formed on the basis of said plurality of retrieved voxels.

19. Apparatus for generating an arbitrary projection of a 3-D voxel-based image represented in discrete 3-D voxel space, said arbitrary projection being characterized by a plurality of projection rays passing through said 3-D voxel space, said apparatus comprising:

retrieving means for retrieving the voxels of a plurality of voxel-based retrieval rays extending through said 3-D voxel space;

formation means for forming a plurality of voxel-based projection rays on the basis of said plurality of retrieval rays;

generating means for generating said arbitrary projection of said 3-D voxel-based image on the basis of said plurality of voxel-based projection rays; and

memory storage and accessing means for storing according to a 3-D skewed memory storage scheme, said 3-D voxel-based image represented in said discrete 3-D voxel space, and for providing simultaneous access to said plurality of voxels disposed along at least one retrieved direction in said discrete 3-D voxel space, said 3-D skewed memory storage scheme involving mapping of the voxels of the said 3-D voxel-based image in said discrete 3-D voxel space, into a first skewed memory storage space.

20. Apparatus for generating an arbitrary projection of a 3-D voxel-based image represented in discrete 3-D voxel space, said arbitrary projection being characterized by a plurality of projection rays passing through said 3-D voxel space, said apparatus comprising:

specification means for specifying a plurality of voxel-based projection ray planes extending through said discrete 3-D voxel space;

retrieving means for retrieving from each said voxel-based projection, ray planes a plurality of voxel-based retrieval rays extending along at least one such retrieval direction;

projection ray formation means for forming a plurality of voxel-based projection rays on the basis of said plurality of retrieval rays;

generating means for generating said arbitrary projection of said 3-D voxel-based image, on the basis of said plurality of voxel-based projection rays; and

projection plane formation means for forming said arbitrary projection of said 3-D voxel-based image on the basis of said generated arbitrary projections of said voxel-based projection planes.

21. The apparatus of claim 20, wherein said retrieving means comprises:

conflict-free retrieving means for simultaneously retrieving along at least one conflict-free retrieval direction, the voxels of said voxel-based retrieval rays extending through said discrete 3-D voxel space.

22. The apparatus of claim 20, which further comprises

memory storage and accessing means for storing according to a 3-D memory storage scheme, said 3-D voxel-based image represented in said discrete 3-D voxel space, and for providing simultaneous access to said plurality of voxels disposed along at least one retrieval direction in said discrete 3-D voxel space, said 3-D skewed memory storage scheme involving mapping of the voxels of said 3-D voxel-based image in said discrete 3-D voxel space, into a first skewed memory storage space.

23. The apparatus of claim 22, wherein said 3-D voxel space is specified in terms of coordinate directions, and wherein said retrieving means comprises

first accessing means for simultaneously accessing from said first skewed memory storage space, said voxels of each said voxel-based retrieval ray,

first demapping means for demapping each said voxel-based retrieval ray along at least one of said coordinate directions, said demapping being based upon said 3-D skewed memory storage scheme, and

first storage means for storing each said demapped retrieval ray in a second memory storage space according to a 2-D skewed memory storage scheme, said second skewed memory storage space providing for simultaneous access to the voxels of a plurality of voxel-based fetching rays along a plurality of fetching directions extending through said second skewed memory storage space, and

wherein said formation means comprises

second accessing means for simultaneously accessing from said second skewed memory storage space, said voxels of each said voxel-based fetching ray,

second demapping means for said voxel-based fetching ray along another coordinate direction, said demapping being based upon said 2-D skewed memory storage scheme, and

second storage means for storing each said demapped fetching ray in said discrete 3-D space,

whereby a plurality of voxel-based projection rays is formed on the basis of said plurality of retrieval rays.

24. The apparatus of claim 23, wherein said generating means comprises

analyzer means for analyzing each said projection ray so as to determine the first non-transparent voxel along said projection ray which is closest to an observer viewing said 3-D voxel-based image, and

projection formation means for forming said arbitrary projection of said 3-D voxel image on the basis of said first non-transparent voxels determined by said analyzer means.