Method and apparatus for rapidly rendering computer generated images of complex structures

• US 6,023,279 A
• Filed: 01/09/1997
• Issued: 02/08/2000
• Est. Priority Date: 01/09/1997
• Status: Expired due to Term

• Current Assignee: The Boeing Co.
• Original Assignee: The Boeing Co.
• Inventors: Sowizral, Henry A., Zikan, Karel
• Primary Examiner(s): Zimmerman, Mark K.
• Application Number:
  US08/781,104
• Time in Patent Office: 1,125 Days
• Field of Search: 345/421, 345/422, 345/502, 345/505, 345/1, 345/506
• US Class Current: 345/421
• CPC Class Codes: G06T 15/06 Ray-tracing
• CPC Class Codes: G06T 15/40 Hidden part removal

Abstract

The image rendering system (20) of the present invention rapidly renders graphical image of complex structures. A complex structure is represented by a plurality of objects that can be organized into an object hierarchy. The image rendering system (20) projects a plurality of rays (55) from a given vision coordinate. For each projected ray, the image rendering system (20) determines with which objects in the object hierarchy are intersected by the ray (55). The image rendering system (20) then determines which object among those intersected by the ray (55) is closest to the given vision coordinate and adds that object to a set of visible objects. As objects are added to the set of visible objects, each object is rendered on the display in accordance with a current vision coordinate. Since the process of adding objects to the set of visible objects is decoupled and run asynchronously from the process of rendering visible objects on the display, the image rendering system (20) is capable of rendering objects at real-time frame rates.

Claims

1. A method for generating on a display a graphical image of a complex structure represented by a plurality of objects, the method comprising:

(a) projecting a plurality of rays from a given vision coordinate, and for each projected ray,

(i) determining which objects in the plurality of objects are intersected by the ray;

(ii) determining which object, among the objects intersected by the ray, is closest to the given vision coordinate; and

(iii) adding the closest object to a set of visible objects; and

(b) as objects are added to the set of visible objects, for each object in the set of visible objects,

(i) reading the object from the set of visible objects as objects are added to the set of visible objects;

(ii) if the object is visible from the current vision coordinate, drawing the object on the display; and

(iii) if the object is not visible from the current vision coordinate, discarding the object from the set of visible objects.

2. The method of claim 1, wherein determining which object among the objects intersected by the ray is the closest object to the given vision coordinate comprises:

(a) determining a distance between each object intersected by the ray and the given vision coordinate; and

(b) determining which object intersected by the ray has the smallest distance to the given vision coordinate.

3. The method of claim 2, further comprising organizing the plurality of objects into an object hierarchy, from a root volume bounding the complex structure, to a plurality of subvolumes wherein each subvolume bounds each of the plurality of objects, to a plurality of shrunken subvolumes wherein each shrunken subvolume bounds a portion of each object.

4. The method of claim 3, wherein determining the distance between each object intersected by the ray and the given vision coordinate comprises:

(a) searching the object hierarchy to determine with which shrunken subvolumes the ray intersects; and

(b) for each shrunken subvolume with which the ray intersects,

(i) determining a distance between the shrunken subvolume and the given vision coordinate; and

(ii) determining which shrunken subvolume has the smallest distance to the given vision coordinate.

5. The method of claim 1, wherein (a) and (b) are repeated for successive vision coordinates.

6. The method of claim 1, wherein a computer readable medium is encoded to perform (a) and (b).

7. The method of claim 1, wherein (a) is performed in parallel by a plurality of ray casting processors, while (b) is performed in parallel by a plurality of separate object rendering processors such that objects are concurrently added to the set of visible objects by each of the plurality of ray casting processors while objects are asynchronously rendered on a set of displays by each of the object rendering processors.

8. An image rendering system for rendering a graphical image of a complex structure on a display, wherein the complex structure is represented by a plurality of objects, the image rendering system comprising:

(a) a storage medium for storing the plurality of objects organized into an object hierarchy and for storing a set of visible objects;

(b) at least one processing unit coupled to the storage medium for adding those objects in the object hierarchy that are visible from a given viewpoint to the set of visible objects stored in the storage medium and for discarding those objects in the object hierarchy that are not visible from the given viewpoint; and

(c) at least one processing unit coupled to the storage medium for rendering each visible object in the set of visible objects on the display in accordance with a current viewpoint while the other at least one processing unit is adding visible objects to the set of visible objects.

9. The image rendering system of claim 8, wherein the at least one processing unit for adding visible objects to the set of visible objects, adds visible objects to the set of visible objects by:

(a) projecting a plurality of rays from the given viewpoint; and

(b) for each projected ray,

(i) determining with which objects in the object hierarchy the ray intersects;

(ii) determining which object, among the objects with which the ray intersects, is closest to the given viewpoint; and

(iii) adding the closest object to a set of visible objects while another visible object is being rendered by the processing unit for rendering each visible object.

10. The image rendering system of claim 9, wherein the at least one processing unit determines which object among the objects with which the ray intersects is the closest object to the given vision coordinate by:

(a) determining a distance between each object intersected by the ray and the given viewpoint; and

(b) determining which object intersected by the ray has the smallest distance to the given viewpoint.

11. The image rendering system of claim 10, wherein the at least one processing unit for rendering each visible object in the set of visible objects, renders each visible object by:

(a) reading the object from the set of visible objects as objects are added to the set of visible objects by the other at least one processing unit; and

(b) if the object is visible from the current viewpoint, drawing the object on the display.

12. The image rendering system of claim 8, wherein a plurality of processing units are coupled to the storage medium for adding those objects in the object hierarchy that are visible from a given viewpoint to the set of visible objects stored in the storage medium.

13. The image rendering system of claim 12, wherein a plurality of processing units are coupled to the storage medium for rendering each visible object in the set visible objects in accordance with a current viewpoint, while the other processing units are adding visible objects to the set of visible objects.

14. The image rendering system of claim 13, wherein each of the plurality of processing units for rendering each visible object in the set of visible objects renders each visible object on a separate display.

15. A method for generating a graphical image of a complex structure on a set of displays, wherein the complex structure is represented by a plurality of objects, the method comprising:

(a) implementing a ray casting routine that (i) casts a plurality of rays from a given vision coordinate; and

(ii) for each casted ray, adds the object intersected by the casted ray that is the closest to the given vision coordinate to a set of visible objects; and

(b) implementing an object rendering routine that renders each object in the set of visible objects on a display in accordance with a current vision coordinate, as objects are added to the set of visible objects, and that further discards any object from the set of visible objects if the object is determined to no longer be visible from the current vision coordinate.

16. The method of claim 15, wherein a plurality of ray casting routines are implemented in parallel such that each ray casting routines adds objects to the set of visible objects.

17. The method of claim 16, wherein a plurality of object rendering routines are implemented in parallel such that each object rendering routine renders each object in the set of visible objects on a display in accordance with the current vision coordinate while each ray casting routine adds objects to the set of visible objects.

18. The method of claim 17, wherein each ray casting routine adds objects to the set of visible objects by:

for each ray cast by the ray casting routine,

(a) determining which objects are intersected by the casted ray;

(b) determining which object, among the objects intersected by the casted ray, is closest to the given viewpoint; and

(c) adding the closest object to the set of visible objects.

19. The method of claim 18, wherein each ray casting routine determines which object among the objects with which the ray intersects is the closest object to the given vision coordinate by:

(a) determining a distance between each object intersected by the casted ray and the given vision coordinate; and

(b) determining which object intersected by the casted ray has the smallest distance to the given vision coordinate.

20. The method of claim 19, wherein each object rendering routine renders each visible object in the set visible objects by:

(a) reading the object from the set of visible objects as objects are added to the set of visible objects by each of the ray casting routines; and

(b) if the object is visible from the current viewpoint, drawing the object on the display.

21. The method of claim 18, wherein the plurality of objects representing the complex structure are organized into an object hierarchy from a root volume bounding the complex structure, to subvolumes bounding each of the plurality of objects, to shrunken subvolumes bounding portions of each object.

22. The method of claim 21, wherein each ray casting routine determines which object is closest to the given vision coordinate by:

(a) searching the object hierarchy to locate shrunken subvolumes that are intersected by the casted ray; and

(b) for each shrunken subvolume intersected by the ray, determining which shrunken subvolume has the smallest distance to the given vision coordinate; and

(c) storing the object associated with the shrunken subvolume in the set of visible objects.