Radiosity with intersecting or touching surfaces

• US 6,525,730 B2
• Filed: 01/29/2002
• Issued: 02/25/2003
• Est. Priority Date: 03/03/1999
• Status: Expired due to Term

• Current Assignee: Autodesk, Inc.
• Original Assignee: Autodesk, Inc.
• Inventors: Tampieri, Filippo
• Primary Examiner(s): Zimmerman, Mark
• Assistant Examiner(s): Santiago, Enrique L
• Application Number:
  US10/059,897
• Publication Number:
  US 20020089501A1
• Time in Patent Office: 392 Days
• Field of Search: 345/419, 345/420, 345/421, 345/422, 345/424, 345/426, 345/620, 345/622
• US Class Current: 345/426
• CPC Class Codes: G06T 15/55 Radiosity

Abstract

Image data is generated for a scene, in which the scene includes object surfaces in three-dimensions. Intersecting or touching surfaces are identified by analysing the surfaces within a hierarchy of bounding volumes. Thereafter, a multi-resolution representation of a radiosity equation is constructed for the scene, wherein one of the identified surfaces is considered separately for light emission on either side of a previously identified line of contact or intersection.

Claims

1. A method of generating image data for a scene comprising:

identifying a line of intersection of contact between two or more objects displayed in a three dimensional scene by analyzing surfaces of said objects using a hierarchy of bounding volumes, wherein a bounding volume contains one or more of the objects;

dividing one or more polygons along the line of intersection or contact;

subsequent to dividing the one or more polygons along the line of intersection, constructing a multi-resolution representation of the radiosity equation for said scene, wherein one of said identified surfaces is considered separately for light emission on one side of a line of contact or intersection and then considered for light emission on a reverse side of said line of contact or intersection; and

generating and displaying said scene based on the radiosity equation.

2. A method according to claim 1, wherein said step of identifying a line of intersection or contact by analysis of bounding volumes, comprises the component steps of:

considering bounding volumes and surfaces is items;

identifying pairs of items;

determining whether both items in the pair are surfaces;

determining an overlap of items or an intersection of surfaces; and

upon condition of an overlap, recursing the above component seeps, retaining the smaller item and selecting another;

or

upon condition of an intersection, storing indication of this condition.

3. A method according to claim 1, wherein said hierarchy of bounding volumes is created for the dual purpose of identifying intersecting or touching surfaces, and an additional method for generating image data from said scene.

4. A method according to claim 1, wherein when dividing, mesh elements created from the one or more polygons have edges that align with the line of contact or intersection.

13. The method of claim 1 wherein when identifying a line of intersection or contact, objects from non-overlapping bounding volumes are automatically excluded as not intersecting or touching.

5. An apparatus for generating image data from scene data comprising:

means for identifying a line of intersection or contact between two or more objects displayed in a three dimensional scene by analyzing surfaces of said objects using a hierarchy of bounding volumes, wherein a bounding volume contains one or more of the objects;

means for dividing one or more polygons that intersect along the line of intersection or contact;

means for constructing, subsequent to the dividing, a multi-resolution representation of the radiosity equation for said scene, wherein one of said identified surfaces is considered for light emission on one side of a line of contact or intersection and then considered for light emission on a reverse side of said line of contact or intersection; and

means for displaying said scene.

6. Apparatus according to claim 5, wherein the means for identifying a line of intersection or contact by analysis of bounding volumes comprises:

means for considering bounding volumes and surfaces as items;

means for identifying pairs of items;

means for determining whether both items in said pair are surfaces;

means for determining an overlap of items or an intersection of surfaces; and

means for upon condition of an overlap, recursing the above component steps, retaining the smaller item and selecting another;

or

means for upon condition of an intersection, storing an indication of this condition.

7. Apparatus according to claim 5, further arranged such that said hierarchy of bounding volumes may be created for the dual purpose of identifying intersecting or touching surfaces, and an additional method for generating image data from said scene.

8. Apparatus according to claim 5, wherein when dividing, mesh elements created from the one or more polygons have edges that align with the line of contact or intersection.

14. The apparatus of claim 5 wherein when identifying a line of intersection or contact, object from non-overlapping bounding volumes are automatically excluded as not intersecting or touching.

9. A computer-readable medium having computer-readable instructions executable by a computer such that said computer performs steps for generating image data for a scene, comprising the steps of:

identifying a line of intersection or contact between two or more objects displayed in a three dimensional scene by analyzing surfaces of said objects using a hierarchy of bounding volumes, wherein a bounding volume contains one or more of the objects;

dividing one or more polygons that intersect along the line of intersection or contact;

subsequent to dividing the one or more polygons along the line of intersection, constructing a multi-resolution representation of the radiosity equation for said scene, wherein one of said identified surfaces is considered separately for light emission on one side of a line of contact or intersection and then considered for light emission on a reverse side of said line of contact or intersection; and

generating and displaying said scene based on the radiosity equation.

10. A computer-readable medium according claim 9, wherein said instructions are executed by said computer, such that said step of indentifying a line of intersection or contact by analysis of bounding volumes comprises the component steps of:

considering bounding volumes and surfaces as items;

identifying parts of items;

determining whether both items in a pair are surfaces;

determining an overlap of items or an intersection of surfaces; and

upon condition of a overlap, recursing the above component steps, retaining the smaller item and selecting another;

or

upon condition of an intersection, storing an indication of this condition.

11. A computer-readable medium according to claim 9, wherein said instructions are executed by said computer, such that said hierarchy of bounding volumes is created for the dual purpose of identifying intersecting or touching surfaces, and an additional method for generating image data from said scene.

12. A computer-readable medium according to claim 9, wherein said instructions are executed by said computer such that when dividing, mesh elements created from the one or more polygons have edges that align with the line of contact or intersection.

15. The computer readable medium of claim 9 wherein when identifying a line of intersection or contact, objects from non-overlapping bounding volumes are automatically excluded as not intersecting or touching.