Image generator and method for resolving non-binary cyclic occlusions with image compositing operations

• US 6,215,503 B1
• Filed: 05/29/1998
• Issued: 04/10/2001
• Est. Priority Date: 05/29/1998
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Snyder, John, Blinn, James F., Lengyel, Jerome E.
• Primary Examiner(s): Vo, Cliff N.
• Application Number:
  US09/086,966
• Time in Patent Office: 1,047 Days
• Field of Search: 345/435, 345/418, 345/419, 345/430, 345/431, 345/432, 345/433
• US Class Current: 345/629
• CPC Class Codes: G06T 15/40 Hidden part removal

Abstract

An image generator takes graphical objects and an occlusion relationship for the objects and resolves non-binary occlusion cycles with image compositing operations to produce an output image of the objects. The image generator takes an occlusion relationship for objects in a scene and a set of antialiased image layers with transparency of the objects and produces an antialiased image of the objects with hidden surfaces eliminated. One implementation operates on subsets of the objects in a scene that form non-binary cycles. This implementation uses a chain of atop operators to combine occluding objects with a selected object from a subset, and then combines this result with other objects in the cycle using over image operations. Another implementation computes a chain of out image operations for each object to combine the image layers of the occluding objects with the image layer of the object. The results of each chain of out image operations are summed to produce an output image.

Claims

1. A method for generating an image given a list of objects that form an occlusion cycle without binary occlusions and image layers representing renderings of the objects, the method comprising:

selecting one of the objects in the list of objects that form an occlusion cycle;

finding a first subset of the objects that occlude the selected object and a second subset formed by removing the selected object from the list of objects that form an occlusion cycle;

generating a first image by using an atop image operation to combine the image layers of the one or more objects in the first subset of the objects that occlude the selected object with the image layer of the selected object; and

combining the first image with the image layers of the objects in the second subset formed by removing the selected object from the list using an over image operation to compute an image representing the objects in the occlusion cycle.

3. The method of claim 1 wherein generating the first image includes applying nested combinations of the atop and over image operations to combine the image layers of the objects in the first subset with the image layer of the selected object.

4. The method of claim 1 further including:

applying a nested combination of over and atop image operations on the image layers of the objects in the second subset.

5. The method of claim 1 wherein the generating and combining comprise:

generating the image representing the objects in the occlusion cycle by computing a sum of in and out image operations.

6. The method of claim 1 wherein the image representing the objects in the occlusion cycle is computed using only two image buffers, a first buffer for accumulating results of the in and out image operations, and a second buffer for accumulating a sum of an intermediate image in the first buffer and another intermediate image in the second buffer.

7. The method of claim 5 further including:

computing a visibility sort of objects in a graphics scene, including grouping the objects in the graphics scene that form an occlusion cycle together; and

combining images representing the objects in the scene and the image representing the objects in the occlusion cycle with over image operations, where the over image operations comprise a sum of out image operations.

8. The method of claim 1 wherein the atop image operation comprises a sum of in and out image operations.

9. The method of claim 8 wherein computing a sum of in and out image operations comprises:

accumulating a first intermediate image resulting from in and out image operations in a first buffer; and

accumulating a second intermediate image in a second buffer resulting from a summing operation that adds the first intermediate image from the first buffer with an image in the second buffer.

10. The method of claim 9 further including:

accumulating a third intermediate image in a third buffer resulting from an over image operation that combines the second intermediate image from the second buffer with an image in the third buffer.

2. A computer readable medium having instructions for performing the following to generate an image given a list of objects that form an occlusion cycle without binary occlusions and image layers representing renderings of the objects:

selecting one of the objects in the occlusion cycle;

finding a first subset of the objects that occlude the selected object and a second subset formed by removing the selected object from the list;

generating a first image by using an atop image operation to combine the image layers of the one or more objects in the first subset with the image layer of the selected object; and

combining the first image with the image layers of the objects in the second subset using an over image operation to compute an image representing the objects in the occlusion cycle.

11. A method for generating an image given a set of objects and image layers representing renderings of the objects:

for each object in a set of objects in a scene, determining which objects in the set occlude the object to find a subset of occluding objects for each object;

computing an intermediate image by combining image layers of objects in a subset with out image operations;

repeating the computing for each of the subsets; and

summing the intermediate images to compute an image representing the objects in the set with hidden surfaces of the objects removed.

12. The method of claim 11 including:

accumulating the intermediate image resulting from combining image layers of objects in a subset using out image operations in a first buffer; and

accumulating a sum of one or more intermediate images from the first buffer in a second buffer.

13. The method of claim 12 wherein the set of objects comprise substantially all of the objects in a graphics scene, including at least one group of objects that form an occlusion cycle, and wherein only two buffers are used to generate an output image representing all of the objects in the scene.

14. The method of claim 12 wherein the objects in the set form an occlusion cycle and only two buffers are used to generate the image representing the objects in the set.

15. The method of claim 12 wherein the set represents a group of objects that form an occlusion cycle in a graphics scene and the group is only a portion of objects in a graphics scene, the method further including:

performing a visibility sort of the objects in the graphics scene, including placing the objects that form an occlusion cycle into the group; and

using a chain of over image operations to combine the image representing the objects in the occlusion cycle with other objects in the graphics scene such that the chain of over image operations results in an image of the graphics scene with hidden surfaces removed.

16. A computer readable medium having instructions for performing the following to generate an image given a set of objects and image layers representing renderings of the objects:

for each object in a set of objects in a scene, determining which objects in the set occlude the object to find a subset of occluding objects for each object;

computing an intermediate image by combining image layers of objects in a subset with out image operations;

repeating the computing for each of the subsets; and

summing the intermediate images to compute an image representing the objects in the set with hidden surfaces of the objects removed.

17. An image generator for generating an image given a set of objects that form an occlusion cycle without binary occlusions and image layers representing renderings of the objects, the image generator comprising:

a display controller for combining image layers of a first subset of the objects that occlude a selected object in the cycle with an atop image operation, and for combining the results of the atop image operation with image layers of a second subset of the objects formed by removing the selected object from the list with an over image operation;

a first buffer for accumulating the results of the atop image operation; and

an over accumulator buffer for accumulating the results of the over image operation.

18. The image generator of claim 17 wherein the display controller is operable to combine the image layers of the first subset using a sum of in and out image operations.

19. The image generator of claim 18 further including:

a first buffer for accumulating results of in and out image operations; and

a second buffer for accumulating results of summing outputs of the in and out image operations.

20. A method for generating an image comprising:

computing occlusion relationships for graphical objects in a graphics scene, including detecting whether objects in the scene form an occlusion cycle; and

evaluating the occlusion relationships for the objects in the scene to determine image compositing operations on image layers of the objects that produce an image of objects in a non-binary cycle with hidden surfaces of the objects removed, where the objects each represent an aggregate set of geometry or a group of sets of aggregate geometry that has a binary cycle.

21. The method of claim 20 further including:

performing the image compositing operations on image layers of the objects that form an occlusion cycle to produce an image of the objects that form the occlusion cycle with hidden surfaces removed.

22. The method of claim 20 including:

computing a visibility ordering of graphical objects in a graphics scene, including grouping objects that form an occlusion cycle into a subset of objects that is treated as a single object in the visibility ordering; and

evaluating an occlusion graph of the subset to generate a compositing expression that operates on image layers of the objects in the subset and results in an image of the objects in the subset with hidden surfaces removed.

23. The method of claim 20 wherein the evaluating includes performing the following on objects that form an occlusion cycle:

selecting one of the objects in the occlusion cycle;

finding a first subset of the objects in the cycle that occlude the selected object and a second subset formed by removing the selected object from the list;

generating a first image compositing sub-expression comprising an atop image operation for combining the image layers of the one or more objects in the first subset with the image layer of the selected object;

generating a second image compositing sub-expression comprising an over image operation for combining the first image with the image layers of the objects in the second subset.

24. The method of claim 20 including:

for each object in a set of objects in a scene, determining which objects in the set occlude the object to find an occlusion subgraph defining the subset of occluding objects for each object;

converting the occlusion subgraphs into a chain of out image operations;

computing a compositing expression that represents a sum of each chain of the out image operations, where the compositing expression results in an image representing the objects in the set with hidden surfaces of the objects removed.

25. The method of claim 20 further including:

rendering the objects to separate image layers; and

combining the separate image layers of objects into an output image representing the graphics scene, including performing the image compositing operations on image layers of the objects that form an occlusion cycle to produce an image of the objects that form the occlusion cycle with hidden surfaces removed.

26. The method of claim 20 including:

splitting an object that potentially forms a binary cycle in the graphics scene into one or more sub-parts to prevent the object from forming a binary cycle with another object in the graphics scene.

27. The method of claim 20 including:

removing one or more binary cycles from a group of objects that include at least one pair of objects that form a binary cycle by;

(a) determining which objects form a binary cycle;

(b) merging objects that form a binary cycle into a binary merged component and placing the binary merged component into the group of objects; and

(c) repeating (a) and (b) until no binary cycles remain in the group of objects.

28. A computer readable medium having instructions for performing the following to generate an image:

computing occlusion relationships for graphical objects in a graphics scene, including detecting whether objects in the scene form an occlusion cycle; and

evaluating the occlusion relationships for the objects in the scene to determine image compositing operations on image layers of the objects that produce an image of objects in a non-binary cycle with hidden surfaces of the objects removed, where the objects each represent an aggregate set of geometry or a group of sets of aggregate geometry that has a binary cycle.

29. An image generator for generating an image given an occlusion relationship of objects in a scene and image layers representing rendering of the objects, where the occlusion relation specifies for each object a subset of objects that occlude the object, the image generator comprising:

a display controller for combining image layers of objects in a subset with one or more out image operations, and for combining the results of the out image operations.

30. The image generator of claim 29 further including

a first buffer for accumulating the results of the out image operations; and

a second buffer for accumulating the images generated by combining the results of the out image operations.