High-speed image generation of complex solid objects using octree encoding
First Claim
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.
4 Assignments
0 Petitions
Accused Products
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.
148 Citations
110 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. - View Dependent Claims (2)
-
-
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. - View Dependent Claims (4, 5, 6)
-
-
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). - View Dependent Claims (9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41)
-
-
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. - View Dependent Claims (43, 44)
-
-
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. - View Dependent Claims (46, 47, 48)
-
-
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 functionsproject 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. - View Dependent Claims (50)
-
-
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. - View Dependent Claims (53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90)
-
-
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. - View Dependent Claims (92, 93)
-
-
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. - View Dependent Claims (95, 96)
-
-
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. - View Dependent Claims (100, 101, 102, 103, 104, 105, 106, 107, 108)
-
-
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.
-
Specification