High-speed image generation of complex solid objects using octree encoding

• US 4,694,404 A
• Filed: 01/12/1984
• Issued: 09/15/1987
• Est. Priority Date: 01/12/1984
• Status: Expired due to Term

• Current Assignee: Octree Corporation
• Original Assignee: KeyBank National Association (KeyCorp)
• Inventors: Meagher, Donald J. R.
• Primary Examiner(s): Krass, Errol A.
• Assistant Examiner(s): Dixon, Joseph L.
• Application Number:
  US06/570,287
• Time in Patent Office: 1,342 Days
• Field of Search: 340/728, 340/729, 340/747, 364/518, 364/521, 364/519, 364/520, 364/522
• US Class Current: 345/421
• CPC Class Codes: G06T 15/06 Ray-tracing
• CPC Class Codes: G06T 15/40 Hidden part removal
• CPC Class Codes: G06T 17/005 Tree description, e.g. octree, quadtree
• CPC Class Codes: G06T 9/40 Tree coding, e.g. quadtree, octree

Abstract

To generate two-dimensional images of three-dimensional solid objects at high speed, an object is defined within a three-dimensional universe hierarchically subdivided into a plurality of discrete volumes of uniform size and similar orientation. The three-dimensional universe is represented by an octree structure having a plurality of nodes, one for every volume in the three-dimensional universe which is at least partially occupied by the object. An arbitrary point of view is selected. Nodes in the tree structure representing the three-dimensional universe are visited in a sequence determined by the selected point of view so that nodes corresponding to volumes which are unobstructed by other volumes are visited first. Each visited node contained by the object is projected onto a subdivided view plane organized into a hierarchy of discrete areas. Areas of the view plane enclosed by the projection are painted onto a display screen. View plane areas which intersect but are not enclosed by the projection are further subdivided. To create sectional views, a user may define a region of the three-dimensional universe, and volumes outside of that region are not projected. Real time image generation wherein calculations necessary to create the image are performed by hard-wired digital logic elements to increase speed performance is possible.

Claims

1. A method for interactively generating a two-dimensional image of a three-dimensional scene including at least one object, said method comprising the steps of:

(a) providing input data volumetrically defining said object within a three-dimensional universe;

(a1) selecting a random viewing direction;

(a2) determining a sequence in response to said selected viewing direction;

(b) progressively subdividing the volume of said three-dimensional universe into volumetric subdivisions;

(c) projecting said volumetric subdivisions which are contained by said object onto a view plane in the order of said sequence and in a direction determined by said selected viewing direction;

(d) progressively subdividing the area of said view plane into subdivisions;

(e) determining which of the subdivisions of said view plane are enclosed by the projections of said volumetric subdivisions of said three-dimensional universe; and

(f) painting areas of a display screen corresponding to said view plane subdivisions determined by said determining step (e) to be enclosed by said projections and not enclosed by projections earlier in said sequence.

2. A method as in claim 1 wherein:

said method further includes the step of scaling at least one dimension of said three-dimensional universe by a scaling factor which is independent of any dimension of said view plane area; and

said subdividing step (b) includes the step of subdividing said volume into subdivisions having a dimension proportional to said scaling factor.

3. A method for generating a two-dimensional image of a three-dimensional scene including at least one object, said method comprising:

(a) providing input data volumetrically defining said object within a three-dimensional universe;

(a1) selecting a random viewing direction;

(a2) determining a sequence in response to said selected viewing direction;

(b) progressively subdividing the volume of said three-dimensional universe into subdivisions;

(c) projecting said volumetric subdivisions which are contained by said object onto a view plane in the order of said sequence wherein volumetric subdivisions containing said object visually obstructing other volumetric subdivisions containing said object are projected before said other subdivisions;

(d) progressively subdividing the area of said view plane into subdivisions;

(e) determining, for each of said projections, which of the subdivisions of said view plane are enclosed by said projection; and

(f) painting areas of a display screen corresponding to said subdivisions of said view plane determined by said determining step (e) to be enclosed by at least one of said projections, including the step of painting said display screen areas only in response to the first projection in said sequence determined by said determining step (e) to enclose said view plane subdivisions to which said display screen areas correspond.

4. A method as in claim 3 wherein said painting step includes the step of determining, in response to said selected viewing direction, which volumetric subdivisions of said universe visually obstruct other ones of said volumetric subdivisions.

5. A method as in claim 3 wherein at least one of said progressively subdividing step (b) and said determining step (e) is performed by hard-wired digital logic elements.

6. A method as in claim 3 wherein said progressively subdividing step (b) and said projecting step (c) are performed recursively for smaller and smaller subdivisions of said three-dimensional universe until a predetermined resolution limit is reached, and said progressively subdividing step (d), said determining step (e) and said painting step (f) are performed recursively for smaller and smaller subdivisions of said view plane until a predetermined resolution limit is reached.

7. A method for generating a two-dimensional image of a three-dimensional scene including at least one object, said method comprising:

(a) providing input data volumetrically defining said object within a three-dimensional universe;

(b) progressively subdividing the volume of said three-dimensional universe into volumetric subdivisions;

(c) defining a subset of the volume of said three-dimensional universe to be displayed;

(d) projecting said volumetric subdivisions which are contained by said object and which lie within said subset onto a view plane;

(e) progressively subdividing the area of said view plane into subdivisions;

(f) determining which of the view plane subdivisions are enclosed by said projections of said volumetric subdivisions; and

(g) painting areas of a display screen corresponding to said view plane subdivisions determined by said determining step (f) to be enclosed by said projections.

8. A method for generating a two-dimensional image of a three-dimensional scene including at least one object, said method comprising the steps of:

(a) providing input data volumetrically defining an object within a three-dimensional universe;

(b) subdividing said three-dimensional universe into a hierarchy of a plurality of levels of subdivided volumes, each level comprising at least one discrete volume, said volumes being characterized by the degree to which they are occupied by said object, a volume in any level being a subdivision of a volume in the level above said any level in said hierarchy;

(c) selecting a point of view for viewing said object;

(c1) determining a sequence for visiting said volumes in said hierarchy in response to said selected point of view;

(d) establishing a two-dimensional view plane;

(e) visiting the volumes in said hierarchy in the order of said sequence until a volume occupied by said object to a predetermined degree which is not visually obstructed from said selected point of view by any other volume in said hierarchy occupied by said object to said predetermined degree is encountered;

(f) projecting said unobstructed volume onto said view plane at a location and orientation determined by said selected point of view and by the location of said volume in said three-dimensional universe;

(g) subdividing said view plane into a plurality of discrete areas;

(h) determining which of said view plane areas are enclosed by said projection projected by said projecting step (f) and which of said areas intersect said projection but are not enclosed by said projection;

(i) painting said view plane areas determined by said determining step (h) to be enclosed by said projection;

(j) further subdividing said view plane areas determined to intersect but not to be enclosed by said projection and repeating said determining step (h) and said painting step (i) for said further subdivided view plane areas;

(k) repeating said visiting step (e) to visit the next volume in said sequence occupied by said object to said predetermined degree which is not visually obstructed from said selected point of view by any volume in said hierarchy occupied by said object to said predetermined degree and also not projected onto said view plane earlier in said sequence by said projecting step (f), repeating said projecting step (f) and said subdividing step (g) for said next volume, and performing said determining step (h), painting step (i) and further subdividing step (j) on the projection of said next volume for previously unpainted ones of said view plane areas, until all of the volumes in said hierarchy occupied by said object to said predetermined degree and not visually obstructed from said selected point of view by any volume in said hierarchy occupied by said object to said predetermined degree and also not projected onto said view plane earlier in said sequence by said projecting step (f) have been visited; and

(l) displaying the view plane areas painted by said painting step (i).

9. A method as in claim 8 wherein at least one of said visiting step (e), projecting step (f), subdividing step (g), determining step (h), painting step (i), further subdividing step (j) and repeating step (k) are performed by processing electrical signals with hard-wired digital logic elements.

10. A method as in claim 8 wherein said subdividing step (b) subdivides each of said volumes occupied but not to a predetermined degree into 8 volumes of identical size, shape and orientation.

11. A method as in claim 10 wherein:

said three-dimensional universe is defined by a parallelepiped; and

said subdividing step (b) subdivides said universe into parallelepiped-shaped volumes.

12. A method as in claim 8 wherein:

said three-dimensional universe is defined by a parallelepiped; and

said subdividing step (b) subdivides said universe into parallelepipeds.

13. A method as in claim 12 wherein:

said determining step (h) includes the step of determining which of said areas are enclosed by the projection of one of three faces, said three faces corresponding to the three visible faces of the six-sided projection of said volume along the axis of said selected point of view onto said view plane;

said painting step (i) paints each of said view plane areas determined to be enclosed by the projection of one said faces one of three shades depending upon which face projection encloses said area; and

said further subdividing step (j) is performed on view plane areas which intersect said volume projection but which are not enclosed by the projection of one of said faces

14. A method as in claim 8 wherein:

said subdividing step (b) includes the step of creating a representation of said hierarchically-subdivided three-dimensional universe, said representation having a plurality of entries, each of said entries representing one of said volumes, each of said entries comprising at least one field containing indicia of the occupation by said object of the volume which said each entry represents; and

said visiting step (e) includes the step of processing said plurality of entries.

15. A method as in claim 14 wherein said creating step of said subdividing step (b) includes the step of arranging said representation in a tree structure.

16. A method as in claim 15 wherein said entry-processing step of said visiting step (e) encounters said unobstructed volume by a depth-first traversal of said tree structure.

17. A method as in claim 16 wherein:

said establishing step (d) includes the step of clearing every entry in an hierarchical representation of said view plane, said representation of said view plane comprising a plurality of levels, each of said levels comprising a plurality of entries representing and corresponding to said discrete view plane areas;

said painting step (i) includes the step of marking the entries in said representation representing said painted view plane areas; and

said repeating step (k) includes the step of determining if an entry of said hierarchical representation of said view plane has been marked in order to determine whether a view plane area represented by said entry has been previously painted.

18. A method as in claim 15 wherein said subdividing step (b) subdivides each of said volumes occupied but not to a predetermined degree into 8 volumes of identical size, shape and orientation.

19. A method as in claim 15 wherein only entries representing subdivisions of volumes occupied by said object but not occupied by said object to said predetermined degree are included in said tree structure.

20. A method as in claim 19 wherein said visiting step (e) includes the step of adding an offset stored in each of said entries in said tree structure to the storage address where said entry is stored in a storage device to obtain the storage addresses in said storage device of entries representing subdivisions of the volume which said entry represents.

21. A method as in claim 8 wherein:

said establishing step (d) includes the step of clearing every entry in an hierarchical representation of said view plane, said view plane representation comprising a plurality of levels, each of said levels representing a plurality of discrete areas of said subdivided view plane, each of said levels comprising a plurality of entries representing and corresponding to said discrete areas;

said painting step (i) includes the step of marking the entries in said representation representing said view plane areas which are painted; and

said repeating step (k) includes the step of determining if entries of said hierarchical representation of said view plane representing said view plane areas have been previously painted.

22. A method as in claim 21 wherein said representation of said view plane is arranged in a tree structure.

23. A method as in claim 22 wherein:

said view plane is rectangular;

said subdividing step (g) subdivides said view plane into at least four rectangular areas of equal size and orientation; and

said further subdividing step (j) subdivides each of said areas into four rectangles of equal size and orientation.

24. A method as in claim 22 wherein said previously-painted determining step of said repeating step (k) includes the step of accessing the entries in said representation of said view plane representing said areas by addressing an interleaved memory.

25. A method as in claim 8 wherein said painting step (i) includes the step of uniformly painting each of said areas one of a plurality of different shades.

26. A method as in claim 8 wherein said painting step (i) includes the step of painting each of said areas of said view plane a shade which is dependent upon the orientation, with respect to said view point, of the surface of said volume the projection of which encloses said area.

27. A method as in claim 8 wherein said displaying step (1) is performed by modifying the intensity of pixels on an electronic display, each of said pixels corresponding to said subdivided area of said view plane at said predetermined degree of resolution.

28. A method as in claim 8 wherein said painting step (i) includes the step of painting said areas of said view plane at said predetermined degree of resolution which are significantly enclosed by said projection.

29. A method as in claim 8 wherein:

said subdividing step (g) includes the step of selecting an overlay comprising a predetermined number of contiguous ones of said view plane areas which together enclose a projection projected by said projecting step (f);

said determining step (h) is performed only on said areas comprising said overlay; and

said further subdividing step (j) further subdivides only said areas comprising said overlay.

30. A method as in claim 29 wherein the size of each of said areas of said view plane in said subdividing step (g) is larger than the size of said projection.

31. A method as in claim 29 wherein four of said contiguous areas are selected by said subdividing step (g).

32. A method as in claim 31 wherein the size of each of said areas of said view plane in said subdividing step (g) is larger than the size of said projection.

33. A method as in claim 8 wherein the size of each of said areas of said view plane in said subdividing step (g) is larger than the size of said projection.

34. A method as in claim 8 wherein said determining step (h) includes the preliminary step of testing said areas for intersection with a bounding box comprising a polygon of predetermined shape and orientation which is just large enough to enclose said projection.

35. A method as in claim 34 wherein said bounding box is rectangular.

36. A method as in claim 35 wherein:

said view plane is rectangular;

said subdividing step (g) subdivides said view plane into at least four rectangular areas of equal size and orientation; and

said further subdividing step (j) subdivides each of said areas into four rectangles of equal size and orientation.

37. A method as in claim 36 wherein said bounding box and said view plane areas have the same orientation.

38. A method as n claim 8 wherein said projecting step (f) includes the step of processing retained data defining the size and orientation of projections of larger-sized volumes in said three-dimensional universe by hard-wired digital logic elements to obtain the size and orientation of projections of smaller-sized volumes in said three-dimensional universe.

39. A method as in claim 8 further including the step of defining a region of said three-dimensional universe and wherein said visiting step (e) only visits volumes contained within said region.

40. A method as in claim 39 wherein said region of said region-defining step is defined by at least one surface having a location and orientation which is selected by a user.

41. A method as in claim 40 wherein said region of said region-defining step is defined by at least one pair of parallel planes.

42. A method for generating a two-dimensional image of a three-dimensional object, said method comprising the steps of:

(a) providing input data volumetrically defining an object within a three-dimensional universe;

(b) subdividing said three-dimensional universe into a hierarchy of a plurality of smaller, subdivided discrete volumes, said volumes arranged in levels, comprising a plurality of discrete volumes of said volumes being characterized by the degree to which they are occupied by said object, a volume in any level being a subdivision of a volume in a level above said any level;

(c) selecting a point of view for viewing said object;

(c1) determining a traversal sequence in response to said selected point of view;

(d) selecting a region of said three-dimensional universe to be displayed;

(e) establishing a two-dimensional view plane;

(f) visiting the volumes in said hierarchy which are contained within said region in the order of said traversal sequence until a volume occupied by said object to a predetermined degree which is not visually obstructed from said selected point of view by any other volume in said hierarchy which is contained within said region and is occupied by said object to said predetermined degree is encountered;

(g) projecting said unobstructed volume onto said view plane at a location and orientation determined by said selected point of view and by the location of said volume in said three-dimensional universe;

(h) subdividing said view plane into a plurality of discrete areas;

(i) determining which of said view plane areas are enclosed by said projection and which of said view plane areas intersect but are not enclosed by said projection;

(j) painting said view plane areas determined to be enclosed by said projection;

(k) further subdividing said view plane areas determined to intersect but not to be enclosed by said projection and repeating said determining and said painting steps for said further subdivided areas;

(l) repeating said visiting step to obtain the next volume in said sequence contained within said region occupied by said object to said predetermined degree which is not visually obstructed from said selected point of view by any volume in said hierarchy which is contained within said region, occupied by said object to said predetermined degree and also not projected onto said view plane earlier in said sequence, repeating said projecting step (g) and said subdividing step (h) for said next volume, and performing said determining, painting and further subdividing steps on the projection of said next volume for previously unpainted ones of said view plane areas until all of the volumes in said hierarchy contained within said region and occupied by said object to said predetermined degree and not visually obstructed from said selected point of view by any volume in said hierarchy contained within said region, occupied by said object to said predetermined degree and also not projected onto said view plane earlier in said sequence have been visited; and

(m) displaying the painted view plane areas.

43. A method as in claim 42 wherein said region selecting step (d) includes the step of defining at least one surface having a location and orientation which is selected by a user, said surface being used to at least partially define said region.

44. A method as in claim 43 wherein said surface-defining step of said region selecting step (d) includes the step of defining at least one pair of parallel planes.

45. A system for generating a two-dimensional image of a three-demensional scene including at least one object, comprising:

means, connected to receive an externally generated viewing direction signal specifying a random desired viewing direction, for determining a sequence in response to said selected viewing direction signal, and

data acquisition means for acquiring input data volumetrically defining an object to be displayed;

data conversion means, connected to receive said input data for defining said object within a three-dimensional universe the volume of which is subdivided into a plurality of volumetric subdivisions;

image processing means, operatively connected to said data conversion means and said sequence selected viewing direction determining means and also connected to receive said signal, for;

projecting said volumetric subdivisions of said three-dimensional universe which are contained by said object onto a view plane in the order of said sequence and in a direction determined by said selected viewing direction signal;

progressively subdividing the area of said view plane into subdivisions;

determining which of the view plane subdivisions are enclosed by the projections of said volumetric subdivisions of said three-dimensional universe; and

painting areas of a display screen corresponding to said view plane subdivisions determined to be enclosed by said projections.

46. A system as in claim 45 wherein said image processing means consists of a plurality of hardwired digital logic elements.

47. A system as in claim 45 wherein said image processing means consists of a hard-wired finite-state sequential digital logic circuit.

48. A system as in claim 45 wherein:

said system further includes means operatively connected to said image processing means for scaling at least one dimension of said three-dimensional universe by a scaling factor which is independent of any dimension of said view plane area; and

said projections have a dimension proportional to said scaling factor.

49. A system for generating a two-dimensional image of a three-dimensional scene including at least one object, comprising:

data acquisition means for acquiring information volumetrically defining an object to be displayed;

data conversion means, connected to receive said information acquired by said data acquisition means, for representing said object within a three-dimensional universe subdivided into a plurality of volumetric subdivisions;

display means for displaying an image; and

a digital signal processor connected to said data coversion means and said display means and preprogrammed to perform the following functions

project said volumetric subdivisions of said three-dimensional universe which are contained by said object onto a view plane in a predetermined sequence wherein volumetric subdivisions containing said object not visually obstructed by other volumetric subdivisions containing said object are projected before said other subdivisions;

progressively subdivide the area of said view plane into subdivisions;

determine, for each of said projections, which of the view plane subdivisions are enclosed by said projection; and

set the intensity of portions of said display means corresponding to said view plane subdivisions determined to be enclosed by at least one projection and not determined to be enclosed by the projection of a volumetric subdivision projected earlier in said sequence.

50. A system as in claim 49 wherein said data acquisition means includes user interactive means for analytically defining said object to be displayed.

51. A system for generating a two-dimensional image of a three-dimensional object, comprising:

data acquisition means for acquiring information volumetrically defining an object to be displayed;

data conversion means connected to receive said information acquired by said data acquiring means for representing said object within a three-dimensional universe the volume of which is subdivided into a plurality of volumetric subdivisions;

interactive means for defining a subset of the volume of said three-dimensional universe to be displayed in response to user interaction;

display means for displaying an image; and

a digital signal processing means connected to said data conversion means, interactive means and display means, for performing the following functions;

(1) project said volumetric subdivisions of said three-dimensional universe which are contained by said object and which lie within said subset onto a view plane,

(2) progressively subdivide the area of said view plane into subdivisions,

(3) determine which of the view plane subdivisions are enclosed by said projections of said volumetric subdivisions of said three-dimensional universe; and

(4) select the intensity of areas of said display means corresponding to said view plane subdivisions determined to be enclosed by said projections.

52. A system for generating a two-dimensional image of a three-dimensional scene including at least one object, said system comprising:

data acquisition means for acquiring input data volumetrically defining an object to be displayed;

data conversion means, responsive to said input data acquired by said data acquisition means, for generating electrical signals defining said object within a three-dimensional universe subdivided into a hierarchy of a plurality of levels of subdivided volumes, each of said levels comprising at least one discrete volume, said volumes being characterized by the degree to which they are occupied by said object, any subdivided volume in said universe being a subdivision of a volume in the level above said any volume;

interactive means for selecting a point of view for viewing said object in response to interaction therewith by a user and for producing signals indicating said selected point of view;

image processing means, connected to said data conversion means and said interactive means, for generating electrical signals specifying an image of said object as viewed from said selected view point, including;

(1) image window processing means for establishing a two-dimesional view plane, including means for subdividing said view plane into a plurality of discrete areas;

(2) object node processing means, responsive to said electrical signals produced said conversion means and also connected to receive said selected point of view signals for determining a traversal sequence in response to said selected point of view signals and for visiting the volumes of said three-dimensional universe in said hierarchy in the order of said sequence until a volume occupied by said object to a predetermined degree which is not visually obstructed from said selected point of view by any other volume in said hierarchy occupied said object to said predetermined degree is encountered, and for so visiting, in the order of said sequence, each of the volumes of said universe occupied by said object to object to said predetermined degree and not visually obstructed from said selected point of view by any volume in said hierarchy occupied by said object to said predetermined degree and also not projected onto said view plane earlier in said sequence until all of the volumes in said hierarchy occupied by said object to said predetermined degree and not visually obstructed from said selected point of view by any other volume in said hierarchy occupied by said object to said predetermined degree have been visited;

(3) geometric processing and projecting means, connected to receive said point of view signal and operatively coupled to said object node processing means, for projecting each of said unobstructed volumes onto said view plane at a location and orientation determined by said selected point of view and the location of said volumes in said three-dimensional universe;

(4) geometric comparing means, operatively coupled to said image window processing means and said geometric processing and projecting means, for determining, for each of said projections, which of said discrete view plane areas are enclosed by said projections and which of said view plane areas intersect but are not enclosed by said projections, said view plane subdividing means including recursive means for further subdividing view plane areas determined by said geometric comparing means to intersect but not to be enclosed by said projections; and

(5) window writer means, connected to said geometric comparing means for painting said areas of said view plane determined to be both enclosed by a projection and not already painted because of enclosure by the projection of a volume visited earlier in said sequence; and

image display means, connected to said window writer means, for displaying the painted view plane areas.

53. A system as in claim 52 wherein said data acquisition means includes a computed tomography scanner.

54. A system as in claim 52 wherein:

said data conversion means includes object storage means for storing a representation of said hierarchically-subdivided three-dimensional universe, said object storage means including a plurality of storage locations corresponding to and associated with said volumes, each of said storage locations having at least one field containing said characterization of the volume corresponding therewith; and

said object node processing means includes means for reading the contents of the storage locations of said object storage means corresponding to said visited volumes.

55. A system as in claim 54 wherein said object storage means stores said representation in a tree structure.

56. A system as in claim 54 wherein:

said data conversion means subdivides each of said volumes in each of said levels into 8 volumes of identical size, shape and orientation; and

said object storage means stores said representation in an octree structure.

57. A system as in claim 56 wherein said object storage means stores the subdivisions only of volumes occupied by said object but not to said predetermined degree.

58. A system as in claim 56 wherein at least one of the plurality of storage locations of said object storing means includes a linking field for specifying storage locations to be read by said object node processing means later in said traversal sequence.

59. A system as in claim 58 wherein:

said object storage means includes means for storing an offset associated with each of said storage locations, said offset locating the address of storage locations representing the subdivisions of the volume corresponding to the storage location associated with the offset relative to the address of said storage location associated with the offset; and

said object node processing means includes addressing means for addressing storage locations corresponding to the subdivisions of a volume corresponding to a given storage location by adding said offset associated with said given storage location to the address of said given storage location.

60. A system as in claim 52 wherein said interactive means includes a trackball.

61. A system as in claim 52 wherein said image processing means includes a plurality of hard-wired digital logic elements.

62. A system as in claim 52 wherein said image processing means consists of a hard-wired finite-state sequential digital logic circuit.

63. A system as in claim 52 wherein:

said image processing means further includes;

window storage means, operatively connected to said image window processing means and to said view plane subdividing means, for storing a hierarchical representation of said view plane, said representation of said view plane comprising a plurality of levels, each of said levels representing a plurality of subdivided view plane areas, said window storage means including a plurlaity of storage locations, each of said storage locations corresponding to and associated with one of said view plane areas; and

window storage accesss means, coupled to said window storage means, for marking the storage locations of said window storage means corresponding to said view plane areas which are painted; and

said geometric comparing means determines whether a view plane area has been previously painted by testing whether the storage location of said window storage means corresponding to said view plane area has been marked.

64. A system as in claim 63 wherein said window storage means stores said representation of said view plane in a tree structure.

65. A system as in claim 63 wherein said window storage means comprises an interleaved memory.

66. A system as in claim 52 wherein:

said three-dimensional universe is parallelepiped in shape;

each of said volumes subdividing said three-dimensional universe is parallelepiped in shape;

said geometric comparing means includes means for determining which of said areas are enclosed by the projection of one of three faces of said unobstructed volume, each of said three faces corresponding to one of the visible faces of the six-sided projection of said volume along the axis of said selected point of view onto said view plane;

said window writer means paints each of said view plane areas determined to be enclosed by the projection of one of said faces one of three shades depending upon which face encloses said view plane areas; and

said recursive means of said view plane subdividing means further subdivides only those view plane areas which intersect said projection but which are not enclosed by the projection of one of said faces.

67. A system as in claim 52 wherein:

said view plane is rectangular; and

said view plane subdividing means subdivides said view plane into a plurality of rectangles of equal size and orientation.

68. A system as in claim 52 wherein said window writer means includes means for uniformly painting each of said areas one of a plurality of different shades.

69. A system as in claim 52 wherein said window writer means includes means for painting each of said areas of said view plane a shade which is dependent upon the orientation, with respect to said view point, of the surface of said volume the projection of which encloses said area.

70. A system as in claim 52 wherein said recursive means of said view plane subdividing means paints said subdivided areas at said predetermined degree of resolution which are significantly enclosed by said projection.

71. A system as in claim 52 wherein:

said view plane subdividing means includes means for selecting an overlay comprising a predetermined number of contiguous ones of said areas which together enclose said projection; and

said geometric comparing means performs said determination only on said areas comprising said overlay.

72. A system as in claim 71 wherein four of said contiguous areas are selected by said overlay-selecting means.

73. A system as in claim 72 wherein said view plane subdividing means subdivides said view plane into areas each of which is larger than the size of said projection.

74. A system as in claim 71 wherein said view plane subdividing means subdivides said view plane into areas each of which is larger than the size of said projection.

75. A system as in claim 52 wherein each of said plurality of discrete areas into which said view plane subdividing means subdivides said view plane is larger than the size of said projection.

76. A system as in claim 52 wherein said geometric comparing means includes means for testing said areas for intersection with a bounding box comprising a polygon of predetermined shape and orientation which is just large enough to enclose said projection.

77. A system as in claim 76 wherein said bounding box is rectangular.

78. A system as in claim 77 wherein:

said view plane is rectangular;

said view plane subdividing means subdivides said view plane into a plurality of rectangles of equal size and orientation; and

said recursive means further subdivides each of said areas into four rectangles of equal size and orientation.

79. A system as in claim 78 wherein said bounding box and said view plane areas have the same orientation.

80. A system as in claim 79 wherein:

said view plane subdividing means includes means for selecting an overlay comprising a predetermined number of contiguous ones of said areas which together enclose said projection; and

said geometric comparing means performs said test and said determination only on said areas comprising said overlay.

81. A system as in claim 80 wherein four of said contiguous areas are selected by said overlay-selecting means.

82. A system as in claim 81 wherein said view plane subdividing means subdivides said view plane into areas each of which is larger than the size of said projection.

83. A method as in claim 52 wherein said geometric processing and projecting means includes:

means for retaining data defining the size and orientation of said projection of larger-sized volumes in said three-dimensional universe; and

means for processing said retained data to obtain the size and orientation of the projection of smaller-sized volumes in said three-dimensional universe.

84. A system as in claim 83 wherein said means for processing said retained data comprises:

shift registers;

arithmetic adders; and

digital logic gates.

85. A system as in claim 83 wherein said means for retaining data comprises a stack.

86. A system as in claim 52 further including means for defining a region of said three-dimensional universe and wherein said object node processing means only visits volumes contained within said region.

87. A system as in claim 86 wherein said region-defining means includes means for defining at least one surface having a location and orientation which is selected by a user.

88. A system as in claim 86 wherein said said region-defining means includes means for defining at least one pair of parallel planes.

89. A system as in claim 52 wherein said display means includes:

an electronic display; and

means for modifying the intensity of pixels on said electronic display, each of said pixels corresponding to said subdivided area of said view plane at said predetermined degree of resolution.

90. A system as in claim 89 wherein said intensity-modifying means includes frame buffer means for storing said modified intensity of each of said pixels.

91. A system for generating a two-dimensional image of a three-dimensional object volumetrically defined within a three-dimensional universe the volume of which has been subdivided into a plurality of volumetric subdivisions, said system comprising:

memory means for storing signals representing said volumetric subdivisions;

node processing means, coupled to said memory means and connected to receive an externally-generated signal representing a random selected viewing direction, for projecting said subdivisions of said three-dimensional universe which are contained by said object onto a two-dimensional, mathematically-defined view plane and an order and in a direction responsive to said selected viewing direction;

window geometry processing means for progressively subdividing the area of said view plane into subdivisions of discrete areas;

geometric comparing means coupled to said window geometry processing means and said node processing means for determining which of the view plane area subdivisions are enclosed by said projections of said volumetric subdivisions of said three-dimensional universe;

view plane memory means coupled to said geometric comparing means and said window geometry processing means for storing data representing the view plane subdivisions determined by said geometric comparing means to be enclosed by said projections; and

means coupled to said view plane memory means for displaying said painted view plane areas.

92. A system as in claim 91 wherein said node processing means, window geometry processing means and geometric comparing means each consist of a plurality of hard-wired digital logic elements.

93. A system as in claim 91 wherein said, node processing means, window processing means and geometric comparing means together form a hard-wired finite-state sequential digital logic circuit.

94. A system for generating on a display a two-dimensional image of a three-dimensional scene including at least one object volumetrically defined within a three-dimensional universe the volume of which is subdivided into a plurality of volumetric subdivisions, said system comprising:

means for projecting said volumetric subdivisions of said three-dimensional universe which are contained by said object onto a view plane in a predetermined order wherein volumetric subdivisions not visually obstructed from a predetermined view point by other volumetric subdivisions containing said object are projected before said other volumetric subdivisions;

means for progressively subdividing the area of a view plane into subdivisions;

means operatively connected to said projecting means and said progressively subdividing means for determining, for each of said projections, which of the view plane areas are enclosed by the projections; and

image forming means operatively connected to said determining means for setting the intensity of areas of a display corresponding to said view plane subdivisions determined by said determining means to be enclosed by projections, the intensity of each of said display areas being set only once.

95. A system as in claim 94 wherein said projecting means, progressively subdividing means, determining means and image forming means each comprise a plurality of hard-wired digital logic elements.

96. A system as in claim 94 wherein said projecting means, progressively subdividing means, determining means and image forming means together comprise a hard-wired finite-state sequential digital logic circuit.

97. A system for generating a two-dimensional image display of a three-dimensional scene comprising at least one object volumetrically defined within a three-dimensional universe, the volume of said universe being subdivided into a plurality of volumetric subdivisions, said system comprising:

interactive means for defining a subset of the volume of said three-dimensional universe in response to user interaction;

node processing means coupled to said interactive means for projecting volumetric subdivisions of said three-dimensional universe which are contained by said object and which lie within said subset onto a view plane,

window geometry processing means for progressively subdividing the area of said view plane into subdivisions,

geometric comparing means connected to said node processing means and said window geometry processing means for determining which of the view plane subdivisions are enclosed by said projections of said volumetric subdivisions; and

window writer and displaying means operatively coupled to said geometric comparing means for displaying areas corresponding to said view plane subdivisions determined to be enclosed by said projections.

98. A system for generating indicia of a two-dimensional image of a three-dimensional object volumetrically defined within a three-dimensional universe, said universe subdivided into a hierarchy of levels, each of said levels comprising a plurality of discrete volumes, each of said volumes being characterized by the degree to which it is occupied by said object, different levels subdividing said universe into volumes of different sizes, said system including:

interactive means for selecting a point of view for viewing said object in response to user interaction;

image window processing means for establishing a two-dimensional view plane, including means for subdividing said view plane into discrete areas;

object node processing means operatively connected to said image window processing means and said interactive means, for determining a traversal sequence in response to said selected point of view, for visiting the volumes of said three-dimensional universe in said hierarchy in the order of said traversal sequence until a volume occupied by said object to a predetermined degree which is not visually obstructed from said selected point of view by any other volume in said hierarchy occupied by said object to said predetermined degree is encountered, and for subsequently visiting, in the order of said sequence, each of the volumes occupied by said object to said predetermined degree and not visually obstructed from said selected point of view by any volume in said hierarchy occupied by said object to said predetermined degree and also not earlier visited;

geometric processing and projecting means operatively coupled to said object node processing means and said interactive means for projecting each of said unobstructed volumes onto said view plane at locations and orientations determined by said selected point of view and the location of said volumes in said three-dimensional universe;

geometric comparing means operatively coupled to said image window processing means and said object node processing means for determining, for each of said projections, which of said discrete view plane areas are enclosed by said projection and which of said areas intersect but are not enclosed by said projection, and for controlling said image window processing means to recursively subdivide view plane areas determined to intersect but not to be enclosed by said projection; and

window writer means operatively coupled to said geometric comparing means for producing and outputting signals representing said view plane areas determined to be both enclosed by a projection and not enclosed by the projection of a volume visited earlier in said sequence.

99. An image display processor (a) connected to receive information representing a solid object, and (b) outputting signals representing an image of said solid object, said processor comprising:

object node processing means, connected to receive said object-representing information, for progressively subdividing a three-dimensional object universe containing said object into volumetric subdivisions and for producing node property signals indicating the degree to which said volumetric subdivisions are occupied by said object;

node select logic mean, connected to receive an externally-generated signal representing a selected arbitrary point of view and also connected to receive said node property signals, for successively selecting said volumetric subdivisions in order of a sequence corresponding to said selected point of view and for producing selection signals representing said selected volumetric subdivisions;

object node geometry processing means, connected to receive said selection signals and said point of view representing signal, for generating node geometry signals representing at least one of the dimensions, the location and the orientation of said volumetric subdivisions selected by said node delect logic means as projected onto a predetermined two-dimensional view plane in accordance with said selected point of view;

image window logic means, connected to receive said selection signals, for progressively subdividing said two-dimensional view plane into area subdivisions, for selecting area subdivisions having a predetermined relationship to said projected selected volumetric subdivisions, and for generating window geometry signals representing at least one of the dimensions and the locations of said selected area subdivisions;

cycle results means, connected to receive said node geometry signals and said window geometry signals, for producing results indicating whether said selected area subdivisions are enclosed by the projections of said selected volumetric subdivisions;

window writer means, connected to receive said results and said window geometry signals, for composing an image in response to the area subdivisions determined to be enclosed by projections, and for generating and outputting signals representing said image; and

sequence control means, connected to receive said results, for controlling said object node processing means, node select logic means, object node geometry processing means and image window logic means to recursively subdivide said view plane and said object universe until all volumetric subdivisions of a predetermined volume which contain a portion of said object, are not filled by said object and are not hidden from said selected point of view by other volumetric subdivisions earlier in the order of said sequence have been projected and the area subdivisions enclosed by the resulting projections have been determined.

100. A processor as in claim 99 wherein said image window logic means includes:

window overlay select logic means, connected to receive said node geometry signals, for selecting view plane area subdivisions large enough to completely enclose and corresponding in locations with the projections of said selected volumetric subdivisions and for producing window designation signals designating said selected view plane area subdivisions; and

image window geometry processing means connected to receive said window designation signals for generating window geometry signals representing the dimensions and locations of said selected view plane area subdivisions.

101. A processor as in claim 100 wherein said image window logic means further includes:

image window memory means for storing a quadtree data structure representing said view plane area subdivisions; and

image window packet processing means, cooperating with said window memory means and connected to receive said results and said window designation signals, for updating said quadtree data structure stored in said window memory means in response to said results and for producing data, in response to data stored in said window memory means, representing said selected area subdivisions and/or further subdivisions thereof.

102. A processor as in claim 101 wherein:

said image memory means comprises an interleaved memory addressable to produce data representing a selected 2×

2 array of contiguous view plane area subdivisions of equal size; and

said window overlay select logic means is also connected to receive said node geometry signals and includes;

means for subdividing each area subdivision of a 2×

2 array of contiguous view plane area subdivisions of equal size into a 2×

2 array of contiguous view plane area subdivisions of equal size to thereby generate a 4×

4 array of view plane area subdivisions, and

means for selecting one of the sixteen possible 2×

2 arrays of contiguous view plane area subdivisions within said 4×

4 array in response to said node geometry signals.

103. A processor as in claim 99 wherein said cycle results means includes:

bounding box arithmetic logic means for comparing the locations of the smallest rectangles of predetermined orientation completely containing projections of said selected volumetric subdivisions with the locations of said selected view plane area subdivisions; and

enclosure and intersections arithmetic logic means for comparing the locations of the projections of said selected volumetric subdivisions with the locations of said selected view plane area subdivisions.

104. A processor as in claim 99 wherein:

said processor further includes cut plane processing means, connected to receive an externally applied signal specifying a region of said object universe and also connected to receive said node select logic means selection signals, for producing a cut plane status signal indicating whether said selected volumetric subdivisions are within said region; and

wherein said cycle results means is also connected to receive said status signal and conditions said results on said status signal.

105. A processor as in claim 99 further including at least one stack means for retaining information representing larger volumetric and/or area subdivisions when said sequence control means controls said object node packet processing means, node select logic means, object node geometry processing means and image window logic means to recursively subdivide said view plane and/or said object universe into smaller volumetric and area subdivisions, respectively.

106. A processor as in claim 99 further including:

object memory means for storing an octree data structure representing said subdivided object universe, said memory means including plural storage locations, each storage location containing data specifying the degree of occupancy by said object of eight contiguous parallelepipeds of similar size, shape and orientation, each storage location also containing a pointer pointing to memory storage locations containing data specifying the degree of occupancy of subdivisions of said parallelepiped; and

memory address pointing means, connected between said object node processing means and said object memory means, for addressing storage locations of said object memory means representing said volumetric subdivisions, for reading the data contained in said addressed locations, and for providing said read data to said object node processing means.

107. A processor as claim 99 wheren:

said desired point of view specified by said externally-generated signal is arbitrary; and

said object node geometry processing means includes;

node bounding box geometry means, connected to receive said point of view representing signal, for generating parameters specifying the locations of said volumetric subdivisions selected by said node select logic means as projected along the axis of said selected point of view onto said view plane with respect to coordinate axes of said plane, and

node polygon geometry means, connected to receive said point of view representing signal, for producing parameters specifying the orientations of three of the six sides of projections of said volumetric subdivisions with respect to said view plane axes.

108. A processor as in claim 99 wherein said image window logic means is also connected to receive said results, and includes:

means for storing data representing the degree to which said area subdivisions are enclosed by said projections; and

means for determining, in response to said data representing the degree of enclosure of a given area subdivision, the degree to which subdivisions of said given subdivision are enclosed by said projections.

109. A method for generating a two-dimensional image of a three-dimensional object, said method comprising:

(a) providing input data volumetrically defining said object within a three-dimensional universe;

(b) selecting a random viewing direction;

(c) determining a sequence in response to said selected viewing direction;

(d) progressively subdividing the volume of said three-dimensional universe into volumetric subdivisions;

(e) projecting said volumetric subdivisions which are contained by said object onto a view plane in the order of said sequence wherein volumetric subdivisions visually obstructing, in said selected viewing direction, other subdivisions containing said object are projected after said other subdivisions; and

(f) painting areas of a display screen corresponding to said projections.

110. A system for generating a two-dimensional image of a three-dimensional object, comprising:

means for providing data volumetrically defining an object within a three-dimensional universe;

means for selecting a random viewing direction;

display means for displaying an image; and

a digital signal processor connected to said data providing means, selecting means and display means and preprogrammed to perform the following functions;

determine a sequence in response to said selected viewing direction;

progressively subdivide said three-dimensional universe into volumetric subdivisions;

project said volumetric subdivisions of said three-dimensional universe which are contained by said object onto a view plane in the order of said sequence wherein volumetric subdivisions continuing said object not visually obstructed, in said selected viewing direction, by other volumetric subdivisions containing said object are projected after said other subdivisions; and

vary the intensity of portions of said display means corresponding to said projections.