System and method employing pipelined parallel circuit architecture for displaying surface structures of the interior region of a solid body

• US 4,985,834 A
• Filed: 11/22/1988
• Issued: 01/15/1991
• Est. Priority Date: 11/22/1988
• Status: Expired due to Term

• Current Assignee: General Electric Company
• Original Assignee: General Electric Company
• Inventors: Cline, Harvey E., Ludke, Siegwalt, Hartley, Richard I., Noujaim, Sharbel E.
• Primary Examiner(s): Fleming, Michael R.
• Assistant Examiner(s): Hayes, Gail O.
• Application Number:
  US07/275,154
• Time in Patent Office: 784 Days
• Field of Search: 364/413.13-413.26, 364/413, 364/22, 364/413.19
• US Class Current: 345/424
• CPC Class Codes: G06T 17/00 Three dimensional [3D] modelling, e.g. data description of 3D objects

Abstract

Arbitrary interior surfaces of a three-dimensional body are displayed from a regular array of values of at least one physical property in the interior of the body. The physical property measurements may be made with systems such as computerized tomographic x-ray, or magnetic resonance imaging. Highly parallel circuits and a highly parallel architecture permit generation of surface views in real time, i.e., sufficiently fast to support ongoing procedures such as surgical operations. These parallel circuits, realizable on large scale integrated circuit chips, perform surface normal calculations, linear interpolations and signal comparisons in simultaneously operating circuit paths which are asynchronously enabled when input data appear.

Claims

1. A system for displaying two-dimensional images of internal surfaces of three-dimensional solid bodies, comprising:

means for storing three-dimensional signal patterns representing the value of at least one physical property associated with a three-dimensional body at regularly spaced grid locations defining volume voxel elements within said body;

means for selectively accessing an entire voxel of values, represented by said signal patterns, from said storing means at one time;

parallel circuit means for testing said voxel values, as defined by vertex values, for intersections of said voxel with a preselected internal surface of said three-dimensional body;

parallel circuit means for subdividing only intersected voxels into sub-voxels;

parallel circuit means for testing values of each of said sub-voxels for intersections of said each sub-voxel with said preselected surface;

parallel circuit means for determining sub-voxel normal values only for those sub-voxels intersected by said preselected surface; and

display processor means for receiving sub-voxel coordinates and sub-voxel normal values, and for displaying said normal values on a screen, said displayed values representing an image of said preselected surface.

2. The system according to claim 1 further comprising:

means for simultaneously accessing a plurality of neighborhood voxel values for those voxels having a common face with the accessed entire voxel; and

parallel circuit means, utilizing said neighborhood voxel values, for determining surface normal vectors by central differences.

3. The system according to claim 1 wherein said parallel circuit means for testing said voxel values comprises:

means for simultaneously comparing all of said vertex values to a constant value representing said preselected surface; and

means for detecting when said constant value lies between a maximum and a minimum of said vertex values.

4. The system according to claim 1 wherein said parallel circuit means for subdividing only intersected voxels into sub-voxels comprises:

parallel circuit means utilizing voxel scaling factors to generate sub-voxel fractional addresses within a voxel,

said scaling factors being different for each dimension of said regularly spaced grid.

5. The system according to claim 4 wherein at least one of said scaling factors is given by 2ⁿ, where n is an integer.

6. The system according to claim 1 wherein said parallel circuit means for subdividing only intersected voxels into sub-voxels comprises:

parallel circuit means utilizing voxel scaling factors to generate sub-voxel fractional addresses within a voxel,

said scaling factors being the same for at least two dimensions of said regularly spaced grid.

7. The system according to claim 6 wherein at least one of said scaling factors is given by 2ⁿ, where n is an integer.

8. The system according to claim 1 wherein said display processor means comprises:

means for comparing said sub-voxel normal values to a viewing angle to produce a pixel value for said image of said preselected surface;

means for transforming the coordinates of said normal values into coordinates on a viewing plane for said image of said preselected surface;

means for limiting the coordinates included in said image of said preselected surface; and

means for resolving ambiguities between display surface pixels occupying the same pixel locations.

9. The system according to claim 8 wherein said means for limiting the coordinates included in said image of said preselected surface comprises:

means for decimating said sub-voxel normal values in the space of said signal patterns.

10. The system according to claim 8 wherein said means for limiting the coordinates included in said image of said preselected surface comprises:

means for decimating said sub-voxel normal values in the space of said viewing plane.

11. A method for displaying two-dimensional images of internal surfaces of three-dimensional solid bodies, comprising:

storing three-dimensional signal patterns representing the value of at least one physical property associated with a three-dimensional body at regularly spaced grid locations defining volume voxel elements within said body;

selectively accessing an entire voxel of said values, represented by signal patterns, from said storing means at one time;

testing a plurality of said voxel values, as defined by said vertex values, in parallel for intersections of said voxel with a preselected internal surface of said three-dimensional body;

subdividing only intersected ones of said voxels into a plurality of sub-voxels in parallel;

testing values of each of said sub-voxels, simultaneously and in parallel, for intersections of said each sub-voxel with said preselected surface;

determining sub-voxel normal values in parallel only for those sub-voxels intersected by said preselected surface; and

displaying said normal values such that said values being displayed represent an image of said preselected surface.

12. The method according to claim 11 further comprising:

simultaneously accessing a plurality of neighborhood voxel values for those voxels having a common face with the accessed entire voxel; and

utilizing said neighborhood voxel values to determine, in parallel, all of the voxel vertex surface normal vectors by central differences.

13. The method according to claim 11 wherein the step of testing comprises:

simultaneously comparing all of said vertex values to a constant value representing said preselected surface; and

detecting when said constant value lies between a maximum and a minimum of said vertex values.

14. The method according to claim 11 wherein the step of subdividing comprises:

utilizing voxel scaling factors to generate in parallel a plurality of sub-voxel fractional addresses within a voxel,

said scaling factors being different for each dimension of said regularly spaced grid.

15. The method according to claim 14 wherein at least one of said scaling factors is given by 2ⁿ, where n is an integer.

16. The method according to claim 11 wherein the step of subdividing comprises:

utilizing voxel scaling factors to generate in parallel a plurality of sub-voxel fractional addresses within a voxel,

said scaling factors being the same for at least two dimensions of said regularly spaced grid.

17. The method according to claim 16 wherein at least one of said scaling factors is given by 2ⁿ, where n is an integer.

18. The method according to claim 11 wherein the step of displaying further comprises:

comparing said sub-voxel normal values to a viewing direction to produce a pixel value for said image of said preselected surface;

transforming the coordinates of said surface points into coordinates on a viewing plane for said image of said preselected surface;

limiting the coordinates included in said image of said preselected surface; and

resolving ambiguities between display surface pixels occupying the same pixel locations.

19. The method according to claim 18 wherein the step of limiting further comprises:

decimating said sub-voxel normal values in the space of said signal patterns.

20. The method according to claim 18 wherein the step of limiting comprises:

decimating said sub-voxel normal values in the space of said viewing plane.

21. A processing system of pipeline circuit architecture for rapidly displaying a two-dimensional image of a three-dimensional data array comprising:

a first circuit of pipeline configuration responsive to data values in said array, for simultaneously locating the position of a plurality of points on a surface of interest in said data array; and

a second circuit of pipeline configuration in parallel with said first circuit of pipeline configuration, also responsive to said data values, for simultaneously establishing intensity of the displayed image at said plurality of points.

22. The processing system according to claim 21 wherein said first and second pipeline circuit means comprise large scale integrated circuit chips.