Parallel computing system for volumetric modeling, data processing and visualization

• US 5,361,385 A
• Filed: 08/26/1992
• Issued: 11/01/1994
• Est. Priority Date: 08/26/1992
• Status: Expired due to Term

• Current Assignee: Yanicklo Technology LLC (Intellectual Ventures LLC)
• Original Assignee: Terra Computer, Ltd.
• Inventors: Bakalash, Reuven
• Primary Examiner(s): Herndon, Heather R.
• Assistant Examiner(s): SMITH, MICHAEL
• Application Number:
  US07/936,178
• Time in Patent Office: 797 Days
• Field of Search: 395/124, 395/127, 345/31, 345/33
• US Class Current: 345/424
• CPC Class Codes: G06F 15/8015 One dimensional arrays, e.g. rings, linear arrays, buses
• CPC Class Codes: G06T 1/20 Processor architectures; Processor configuration, e.g. pipelining
• CPC Class Codes: G06T 15/005 General purpose rendering architectures

Abstract

A parallel computing system producing, storing, and processing voxel data elements in parallel within a three-dimensional memory storage array, and producing and buffering pixel data elements in parallel for use in volume visualization of the stored voxel data elements. The parallel computing system includes a system bus for transferring parameters and local programs. A plurality of local computing units are connected to the system bus. Each local computing unit has a local program storage memory for storing one or more local programs, and RISC processor for executing the local programs. A local memory storage module is connected to each local computing unit. Each local memory storage module has a set of memory storage elements, each of which is capable of storing one or more voxel data elements. A plurality of the memory storage elements in the local memory storage modules are indexed so as to represent the three-dimensional memory storage array in 3-D space characterized by three coordinate directions. A local bus is connected to each local computing unit and one local memory storage module, for transferring voxel data elements therebetween. A control computing unit is connected to the plurality of local computing units by way of the system bus, for coordinating (i.e., synchronizing) parallel execution of the local programs by the plurality of local computing units. A voxel data element transfer means mechanism transfers voxel data elements among the local computing units. A pixel data element buffer memory is connected to the buses, and is controlled by the control computing unit. These pixel data elements are transferrable over the system bus to a user interface/display computing unit, for use in visualization of voxel data elements stored in the three-dimensional memory storage array.

Claims

1. A parallel computing system for producing, storing, and processing voxel data elements in parallel within a three-dimensional memory storage array, and producing and buffering pixel data elements in parallel for use in visualization of voxel data elements stored within said three-dimensional memory storage array, said parallel computing system comprising:

a system bus for transferring parameters and local programs;

a plurality of local computing units indexable as k=0,1,2, . . . , N-1, each said local computing unit being connected to said system bus and having

means for storing one or more local programs capable of producing, storing and processing voxel data elements within said three dimensional memory storage array, and

means for executing said one or more local programs using said parameters so as to locally produce, store and process voxel data elements within said three-dimensional memory storage array, and produce one or more pixel data elements from one or more voxel data elements stored within said three-dimensional memory storage array;

a plurality of local memory storage modules indexable as k=0,1,2, . . . , N-1, each said local memory storage module having a set of memory storage elements and each said memory storage element being capable of storing one or more voxel data elements, wherein a plurality of said memory storage elements in said plurality of local memory storage modules are indexed so as to represent said three-dimensional memory storage array in 3-D space characterized by three coordinate directions;

a plurality of local buses indexable as k=0,1,2, . . . N-1, each said local bus being operably connected to one said local computing unit and one said local memory storage module, for transferring voxel data elements therebetween;

a control computing unit, operably connected to said plurality of local computing units by way of said system bus, for coordinating parallel execution of said one or more local programs by said plurality of local computing units;

voxel data element transfer means operably connected to said plurality of local buses, for transferring voxel data elements between each said k-th local computing unit and said (k+Δ

k)th local computing unit, where Δ

k equals a module distance defined between said local memory storage modules in memory space; and

pixel data element buffering means, operably connected to said plurality of local buses and said system bus and controlled by said control computing unit, for buffering pixel data elements produced from said plurality of local computing units and transferred over said plurality of local buses, wherein pixel data elements buffered in said pixel data element buffering means are transferable over said system bus to a user interface computing unit operably connected to said system bus, for use in visualization of voxel data elements stored within said three-dimensional memory storage array.

2. The parallel computing system of claim 1, wherein said control computing unit further comprises

means for storing a control routine,

means for executing said control routine, and producing coordination data, and

means for transferring said coordination data to said plurality of local computing units, for use during the execution of said one or more local programs in a parallel manner by said plurality of local computing units.

3. The parallel computing system of claim 2,

wherein said parameters specify a voxel data filtering function to be performed on said 3-D voxel based object;

wherein said one or more local programs at each said local computing unit comprise a local filtering program which instructs said local computing unit to process voxel data elements in accordance with said voxel data filtering function, and

wherein voxel data elements are processed in parallel by said plurality of local computing units to provide a complete voxel-based representation of said 3-D geometric object filtered in accordance with said voxel data filtering function.

4. The parallel computing system of claim 3,

wherein, for each rectilinear sequence of memory storage elements in said three-dimensional memory storage array accessed by said plurality of local computing units, said control computing unit

transmits Cartesian coordinates to said local computing units in order to specify the rectilinear sequence of storage elements,

transmits said module distance Δ

k to said voxel data element transfer means in order to specify parallel transferal of voxel data elements among said plurality of local computing units, and

controls the operation of said voxel data element transfer means.

5. The parallel computing system of claim 4, wherein the parameters specifying said voxel data filtering function are produced by said user interface computing unit.

6. The parallel computing system of claim 1, which further includes

said user interface computing unit operably connected to said system bus for producing and transferring said parameters to said control computing unit by way of said system bus, wherein said user interface computing unit comprises:

means for inputing and storing user-input data;

means for storing a user interface program;

means for executing said user interface program so as to process said user-input data, produce said parameters, and transfer said parameters over said system bus to said control computing unit; and

means for visually displaying an image of a 3-D voxel-based object represented in said three-dimensional memory storage array,

wherein said image is viewable along a viewing direction specified by said user and formed from a two-dimensional array of said pixel data elements obtained from said pixel data element buffering means.

7. The parallel computing system of claim 6,

wherein said user-input data specifies a 3-D geometric object for conversion into said 3-D voxel based-object, and said parameters specify an implicit representation of said 3-D geometric object;

wherein said control computing unit transmits said parameters to said local computing units;

wherein said one or more local programs at each said local computing unit comprise a local voxelization program which instructs said local computing unit to process said parameters, produce voxel data elements representative of a portion of said 3-D geometric object in said 3-D space, and store said produced voxel data elements in said operably connected local memory storage module, and

whereby, the voxel data elements produced by said plurality of local computing units collectively provide, in parallel, a complete voxel-based representation of said 3-D geometric object in said 3-D space.

8. The parallel computing system of claim 7,

wherein said user-input data further specifies a viewing direction in 3-D space along which a plurality of projected viewing rays represented therein extend through said 3-D voxel-based object and said parameters further specify a geometric representation of said projected viewing rays;

wherein said local computing units use said parameters to produce pixel data elements which each said projected viewing ray contributes to the image of said 3-D voxel-based object viewed along said specified viewing direction.

9. The parallel computing system of claim 8, wherein each projected viewing ray extends parallel to each and every other projected viewing ray, represented in said 3-D space, and through said 3-D voxel-based object.

10. The parallel computing system of claim 8, wherein each projected viewing ray extends from said user and through said 3-D voxel-based object.

11. The parallel computing system of claim 1, which further comprises

a data input/output unit, through which a plurality of voxel data elements can be selectively transferred from an external data storage device to a specified sequence of memory storage elements in said three-dimensional memory storage array, and through which said plurality of voxel data elements can be selectively transferred from said specified sequence of memory storage elements in said three-dimensional memory storage array to said external storage device.

12. The parallel computing system of claim 1, wherein said control computing unit includes means for coordinating the operation of said plurality of local computing units so as to orchestrate access to a rectilinear sequence of memory storage elements parallel to any one of said coordinate axes in said three-dimensional memory storage array.

13. The parallel computing system of claim 1, wherein said three-dimensional memory storage array has three principal planes, and wherein said control computing unit includes means for coordinating the operation of said plurality of local computing means so as to orchestrate access to a sequence of memory storage elements arranged within a plane parallel to one of the principal planes in said three-dimensional memory storage array.

14. The parallel computing system of claim 1, wherein said control computing unit includes means for coordinating the operation of said plurality of local computing units so as to orchestrate access to a sequence of memory storage elements arbitrarily arranged across said three-dimensional memory storage array.

15. The parallel computing system of claim 1,

wherein the location of each said memory storage element in said three-dimensional memory storage array is specified by Cartesian coordinates selected from the group consisting of x, y and z;

wherein said control computing unit executes said one or more local programs produces a set of Cartesian coordinates which specify a sequence of memory storage elements in said three-dimensional array, and transmits said set of Cartesian Coordinates over said system bus to said plurality of local computing units; and

wherein said plurality of local computing units process said set of Cartesian coordinates in accordance with said one or more local programs so as to generate physical memory addresses for accessing said sequence of memory storage elements specified by said set of Cartesian coordinates.

16. The parallel computing system of claim 1, wherein said pixel data element buffer memory comprises

a plurality of dual-port data storage buffers indexable as k=0,1, . . . , N-1, each said dual-port data storage buffer being operably connected to one said local computing unit by one said local bus, and said plurality of dual-port data storage buffers being accessible in parallel by said plurality of local computing units by way of said plurality of local buses, and being sequentially accessible by said control computing unit or said user interface computing unit by way of said system bus.

21. The parallel computing system of claim 16, wherein said voxel data element transfer means comprises:

a first voxel data element transfer means including a plurality of local control means, each being operably associated with and controlled by said k-th local bus, for selectively controlling the transfer of voxel data elements between each said k-th local computing unit and said (k-Δ

k)th local computing unit, and between each said k-th local computing unit and said (k+Δ

k)th local computing unit, where said module distance Δ

k is selected from the group consisting of (-1, -2, -3, +1, +2, +3); and

a second voxel data element transfer means including a plurality of data element transfer subunits, each being operably connected between an adjacent set of said local buses in said memory space and controlled by said control computing unit, and said plurality of data element transfer subunits being operable to transfer in parallel, a plurality of voxel data elements between each said k-th local computing unit and said (k+Δ

k)th local computing unit.

22. The parallel computing system of claim 16, wherein said voxel data element transfer means comprises a plurality of local control means, each being operably associated with and controlled by said k-th local bus, for selectively controlling the transfer of voxel data elements between each said k-th local computing unit and said (k-Δ

k)th local computing unit, and between each said k-th local computing unit and said (k+Δ

k)th local computing unit, where said module distance Δ

k is selected from the group consisting of (-1, -2, -3, +1, +2, +3).

23. The parallel computing system of claim 22, wherein each k-th local bus is controlled by said k-th local computing unit.

24. The parallel computing system of claim 23, wherein said module distance Δ

k is selected from the group consisting of (-1, -2, -3, +1, +2, +3).

28. The parallel computing system of claim 1, wherein said voxel data element transfer comprises a plurality of local control means, each being operably associated with and controlled by said k-th local bus, for selectively controlling the transfer of voxel data elements between each said k-th local computing unit and said (k-Δ

k)th local computing unit, and between each said k-th local computing unit and said (k+Δ

k)th local computing unit, where said memory distance Δ

k is selected from the group consisting of (-1, -2, -3, +1, +2, +3).

29. The parallel computing system of claim 28, wherein each k-th local bus is controlled by said k-th local computing unit.

30. The parallel computing system of claim 1, wherein each said memory storage element comprises a plurality of memory storage subelements, each memory storage subelement capable of storing one or more data elements.

31. The parallel computing system of claim 1, wherein each said local computing unit and said control computing unit comprises a microcomputer chip.

32. The parallel computing system of claim 31, wherein each said microcomputer chip is a RISC type microcomputer chip.

33. The parallel computing system of claim 31, wherein each said local memory storage module comprises a random access memory storage device.

17. The parallel computing system of 16, wherein said module distance Δ

k is determined by said control computing unit.

18. The parallel computing system of claim 17, wherein said voxel data element transfer means comprises means for transferring, in parallel, a voxel data element placed on each said k-th local bus to said (k+Δ

k) local bus.

19. The parallel computing system of claim 18, wherein said voxel data element transfer means comprises a plurality of data element transfer subunits, each being operably connected between an adjacent set of said local buses in physical memory space and controlled by said control computing unit, and said plurality of data element transfer subunits being operable to transfer in parallel, a plurality of voxel data elements between each said k-th local computing unit and said (k+Δ

k)th local computing unit.

20. The parallel computing system of claim 19, wherein said module distance Δ

k is selected from the group consisting of (-1, -2, -3, +1, +2, +3).

25. The parallel computing system of 1, wherein said module distance Δ

k is determined by said control computing unit.

26. The parallel computing system of claim 25, wherein said voxel data element transfer means comprises means for transferring a voxel data element placed on each said k-th local bus to said (k+Δ

k) local bus.

27. The parallel computing system of claim 26, wherein said voxel data element transfer means comprises a plurality of data element transfer subunits, each being operably connected between an adjacent set of said local buses in said memory space and controlled by said control computing unit, and said plurality of data element transfer subunits being operable to transfer in parallel, a plurality of voxel data elements between each said k-th local computing unit and said (k+Δ

k)th local computing unit.

34. A volume visualization workstation for producing, storing, and processing voxel data elements in parallel within a three-dimensional memory storage array, and producing and buffering pixel data elements in parallel for use in visualization of voxel data elements stored in said three-dimensional memory storage array, said parallel computing workstation comprising:

a system bus for transferring parameters and local programs;

a plurality of local computing units indexable as k=0,1,2, . . . N-1, each said local computing unit being connected to said system bus and having

means for storing one or more local programs capable of producing, storing and processing voxel data elements within said three dimensional memory storage array, and

means for executing said one or more local programs using said parameters so as to locally produce, store and process voxel data elements within said three-dimensional memory storage array, and produce one or more pixel data elements from one or more voxel data elements stored within said three-dimensional memory storage array;

a plurality of local memory storage modules indexable as k=0,1,2, . . . , N-1, each said local memory storage module having a set of memory storage elements and each said memory storage element being capable of storing one or more voxel data elements, wherein a plurality of said memory storage elements in said plurality of local memory storage modules are indexed so as to represent said three-dimensional memory storage array in 3-D space characterized by three coordinate directions;

a plurality of local buses indexable as k=0,1,2, . . . N-1, each said local bus being operably connected to one said local computing unit and one said local memory storage module, for transferring voxel data elements therebetween;

a control computing unit, operably connected to said plurality of local computing units by way of said system bus, for coordinating parallel execution of said one or more local programs by said plurality of local computing units;

voxel data element transfer means operably connected to said plurality of local buses, for transferring voxel data elements between each said k-th local computing unit and said (k+Δ

k)th local computing unit, where Δ

k equals a memory distance defined between said local memory storage modules in memory space;

pixel data element buffering means, operably connected to said plurality of local buses and said system bus, and controlled by said control computing unit, for buffering pixel data elements produced from said plurality of local computing units and transferred over said plurality of local buses to said pixel data element buffering means; and

a user interface computing unit operably connected to said system bus for producing and transferring said parameters to said control computing unit by way of said system bus, and for receiving pixel data elements transferred from said pixel data element buffering means over said system bus to said user interface computing unit, for use in visualization of voxel data elements stored within said three-dimensional memory storage array.

35. The volume visualization workstation of claim 34, wherein said control computing unit comprises

means for storing a control routine,

means for executing said control routine, and producing coordination data, and

means for transferring said coordination data to said plurality of local computing units, for use during the execution of said one or more local programs a parallel manner by said local computing units.

36. The volume visualization workstation of claim 35, wherein said parameters specify a voxel data filtering function to be performed on said 3-D voxel based object;

wherein said one or more local programs at each said local computing unit comprise a local filtering program which instructs said local computing unit to process voxel data elements in accordance with said voxel data filtering function, and

wherein voxel data elements are processed in parallel by said plurality of local computing units to provide a complete voxel-based representation of said 3-D geometric object filtered in accordance with said voxel data filtering function.

37. The volume visualization workstation of claim 36,

wherein, for each rectilinear sequence of memory storage elements in said three-dimensional memory storage array accessed by said plurality of local computing units, said control computing unit

transmits Cartesian coordinates to said local computing units in order to specify the rectilinear sequence of memory storage elements,

transmits said module distance Δ

k to said voxel data element transfer means in order to specify parallel transferal of voxel data elements among said plurality of local computing units, and

controls the operation of said voxel data element transfer means.

38. The volume visualization workstation system of claim 37, wherein the parameters specifying said voxel data filtering function are produced by said user interface computing unit.

39. The volume visualization workstation of claim 35, which further comprises

a data input/output unit, through which a plurality of voxel data elements can be selectively transferred from an external data storage device to a specified sequence of memory storage elements in said three-dimensional memory storage array, and through which said plurality of voxel data elements can be selectively transferred from said specified sequence of memory storage elements in said three-dimensional memory storage array to said external storage device.

40. The volume visualization workstation of claim 35, wherein said control computing unit includes means for coordinating the operation of said plurality of local computing units so as to orchestrate access to a rectilinear sequence of memory storage elements parallel to any one of said coordinate axes in said three-dimensional memory storage array.

41. The volume visualization workstation of claim 35, wherein said three-dimensional memory storage array has three principal planes, and wherein said control computing unit includes means for coordinating the operation of said plurality of local computing means so as to orchestrate access to a sequence of memory storage elements arranged within a plane parallel to one of the principal planes in said three-dimensional memory storage array.

42. The volume visualization workstation of claim 35, wherein said control computing unit includes means for coordinating the operation of said plurality of local computing units so as to orchestrate access to a sequence of memory storage elements arbitrarily arranged across said three-dimensional memory storage array.

43. The volume visualization workstation of claim 35, wherein the location of each said memory storage element in said three-dimensional memory storage array is specified by Cartesian coordinates selected from the group consisting of x, y and z;

wherein said control computing unit produces a set of Cartesian coordinates which specify a sequence of memory storage elements in said three-dimensional array, and transmits said set of Cartesian Coordinates over said system bus to said plurality of local computing units; and

wherein said plurality of local computing units process said set of Cartesian coordinates in accordance with said one or more local programs so as to generate physical memory addresses for accessing said sequence of memory storage elements specified by said set of Cartesian coordinates.

44. The volume visualization workstation of claim 34, wherein said user interface computing unit comprises:

means for inputting and storing user-input data;

means for storing a user interface program;

means for executing said user interface program so as to process said user-input data, produce said parameters, and transfer said parameters to said control computing unit; and

means for visually displaying an image of a 3-D voxel-based object represented in said three-dimensional memory storage array; and

wherein said image is viewed along a viewing direction specified by said user and formed from a two-dimensional array of said pixel data elements obtained from said pixel data element buffering means.

45. The volume visualization workstation of claim 44,

wherein said user-input data specifies a 3-D geometric object for conversion into said 3-D voxel based-object, and said parameters specify an implicit representation of said 3-D geometric object;

wherein said control computing unit transmits said parameters to said local computing units; and

wherein said one or more local programs at each said local computing unit comprise a local voxelization program which instructs said local computing unit to process said parameters, produce, in parallel, voxel data elements representative of a portion of said 3-D geometric object in said 3-D space, and store said produced voxel data elements in said operably connected local memory storage module,

whereby, the voxel data elements produced by said plurality of local computing units collectively provide a complete voxel-based representation of said 3-D geometric object in said 3-D space.

46. The volume visualization workstation of claim 45,

wherein said user-input data further specifies a viewing direction in 3-D space along which a plurality of projected viewing rays represented therein, extend through said 3-D voxel-based object and said parameters further specify a geometric representation of said projected viewing rays;

wherein said local computing units use said parameters to produce, in parallel, pixel data elements which each said projected viewing ray contributes to the image of said 3-D voxel-based object viewed along said specified viewing direction.

47. The volume visualization workstation of claim 46, wherein each projected viewing ray represented in said 3-D space extends parallel to each and every other projected viewing ray, and through said 3-D voxel-based object.

48. The volume visualization workstation of claim 46, wherein each projected viewing ray represented in 3-D space extends from said user and through said 3-D voxel-based object.

49. The volume visualization workstation of claim 34, wherein said pixel data element buffer memory comprises

a plurality of dual-port data storage buffers indexable as k=0,1, . . . , N-1, each said dual-port data storage buffer being operably connected to one said local computing unit by one said local bus, and said plurality of dual-port data storage buffers being accessible in parallel by said plurality of local computing units by way of said plurality of local buses, and being sequentially accessible by said control computing unit or said user interface computing unit by way of said system bus.

54. The volume visualization workstation of claim 49, wherein said voxel data element transfer means comprises a plurality of local control means, each being operably associated with and controlled by said k-th local bus, for selectively controlling the transfer of data elements between each said k-th local computing unit and said (k-Δ

k)th local computing unit, and between each said k-th local computing unit and said (k+Δ

k)th local computing unit, where said module distance Δ

k is selected from the group consisting of (-1, -2, -3, +1, +2, +3).

55. The volume visualization workstation of claim 54, wherein each k-th local bus is controlled by said k-th local computing unit.

60. The volume visualization workstation of claim 34, wherein said voxel data element transfer comprises a plurality of local control means, each being operably associated with and controlled by said k-th local bus, for selectively controlling the parallel transfer of voxel data elements between each said k-th local computing unit and said (k-Δ

k)th local computing unit, and between each said k-th local computing unit and said (k+Δ

k)th local computing unit, where said module distance Δ

k is selected from the group consisting of (-1, -2, -3, +1, +2, +3).

61. The volume visualization workstation of claim 60, wherein each k-th local bus is controlled by said k-th local computing unit.

62. The volume visualization workstation of claim 34, wherein said voxel data element transfer means comprises:

a first voxel data element transfer means including a plurality of local control means, each being operably associated with and controlled by said k-th local bus, for selectively controlling the transfer of voxel data elements between each said k-th local computing unit and said (k-Δ

k)th local computing unit, and between each said k-th local computing unit and said (k+Δ

k)th local computing unit, where said module distance Δ

k is selected from the group consisting of (-1, -2, -3, +1, +2, +3); and

a second voxel data element transfer means including a plurality of data element transfer subunits, each being operably connected between an adjacent set of said local buses in physical memory space and controlled by said control computing unit, and said plurality of data element transfer subunits being operable to transfer in parallel, a plurality of voxel data elements between each said k-th local computing unit and said (k+Δ

k)th local computing unit.

63. The volume visualization workstation of claim 34, wherein each said memory storage element comprises a plurality of memory storage subelements, each memory storage subelement capable of storing one or more data elements.

64. The volume visualization workstation of claim 34, wherein each said local computing unit, said control computing unit, and said user interface computing unit comprises a microcomputer chip.

65. The volume visualization workstation of claim 64, wherein each said microcomputer chip is a RISC type microcomputer chip.

66. The volume visualization workstation of claim 65, wherein each said local memory storage module comprises a random access memory storage device.

50. The volume visualization workstation of 49, wherein said module distance Δ

k is determined by said control computing unit.

51. The volume visualization workstation of claim 50, wherein said voxel data element transfer means comprises means for transferring a voxel data element placed on each said k-th local bus to said (k+Δ

k) local bus.

52. The volume visualization workstation of claim 50, wherein said voxel data element transfer means comprises a plurality of data element transfer subunits, each being operably connected between an adjacent set of said local buses in physical memory space and controlled by said control computing unit, and said plurality of data element transfer subunits being operable to transfer in parallel, a plurality of voxel data elements between each said k-th local computing unit and said (k+Δ

k)th local computing unit.

53. The volume visualization workstation of claim 52, wherein said module distance Δ

k is selected from the group consisting of (-1, -2, -3, +1, +2, +3).

56. The volume visualization workstation of 34, wherein said module distance Δ

k is determined by said control computing unit.

57. The volume visualization workstation of claim 56, wherein said voxel data element transfer means comprises means for transferring a voxel data element placed on each said k-th local bus to said (k+Δ

k) local bus.

58. The volume visualization workstation of claim 57, wherein said voxel data element transfer means comprises a plurality of data element transfer subunits, each being operably connected between an adjacent set of said local buses in physical memory space and controlled by said control computing unit, and said plurality of data element transfer subunits being operable to transfer in parallel, a plurality of voxel data elements between each said k-th local computing unit and said (k+Δ

k)th local computing unit.

59. The volume visualization workstation of claim 58, wherein said module distance Δ

k is selected from the group consisting of (-1, -2, -3, +1, +2, +3).