Boolean operations for subdivision surfaces

• US 6,307,555 B1
• Filed: 09/30/1998
• Issued: 10/23/2001
• Est. Priority Date: 09/30/1998
• Status: Expired due to Fees

• Current Assignee: Autodesk, Inc.
• Original Assignee: Silicon Graphics Incorporated (Graphics Properties Holdings, Inc.)
• Inventors: Lee, Eugene T. Y.
• Primary Examiner(s): Luu, Matthew
• Assistant Examiner(s): Sajous, Wesner
• Application Number:
  US09/164,089
• Time in Patent Office: 1,119 Days
• Field of Search: G06/F 1.500, 345/419, 345/420, 345/421, 345/422, 345/423, 345/424, 345/425, 345/426, 345/427, 345/429, 345/430, 345/428, 345/440, 345/441, 345/435, 345/433
• US Class Current: 345/423
• CPC Class Codes: G06T 17/20 Finite element generation, e.g. wire-frame surface description, tesselation

Abstract

A method for creating a new subdivision surface from one or more prior subdivision surfaces using a computer, the computer having a processor and a memory, includes establishing in the memory a data structure storing data representing the structures of the prior subdivision surfaces, performing Boolean operations upon prior meshes defining the one or more prior subdivision surfaces to form a resulting mesh defining the new subdivision surface, and storing the resulting mesh in the memory.

Claims

1. A method for performing Boolean operations upon two base meshes using a computer, where each base mesh comprises a plurality of faces, the computer having a processor and a memory, the method comprising:

establishing in the memory a data structure storing data representing the structures of the two base meshes;

determining intersections of the two base meshes, the intersections defining an intersection curve;

tessellating faces incident to the intersection curve;

selecting surviving portions of the intersecting faces;

deleting faces of the two base meshes according to the selected surviving portions; and

combining remaining faces of the two base meshes into a resultant base mesh.

2. The method of claim 1 wherein the selecting the surviving portions of the two base meshes is by user input through an input device of the computer.

3. The method of claim 1 wherein the selecting the surviving portions of the two base meshes is automatically calculated by the processor.

4. The method of claim 1 wherein tessellating the faces of the base meshes incident to the intersection curve converts any face having greater than three sides into two or more new faces having only three sides.

5. The method of claim 1 wherein tessellating the faces of the base meshes incident to the intersection curve converts any face having a number of sides different from four into two or more new faces having only four sides.

6. The method of claim 1 further comprising constructing a surface from the resultant base mesh.

7. The method of claim 6 wherein the surface is constructed using subdivision rules.

8. The method of claim 1 further comprising computing a plurality of intersections between intersecting faces of the two base meshes, the plurality of intersections defining a plurality of intersection curves.

9. A computer program, residing on a computer-readable medium, comprising instructions for performing Boolean operations upon two base meshes by causing a computer to:

establish in the memory a data structure storing data representing the structures of the two base meshes;

determine intersections of the two base meshes, the intersections defining an intersection curve;

tessellate faces incident to the intersection curve;

select surviving portions of the intersecting faces;

delete faces of the two base meshes according to the selected surviving portions; and

combine remaining faces of the two base meshes into a resultant base mesh.

10. The computer program of claim 9 wherein the selecting the surviving portions of the two base meshes is by user input through an input device of the computer.

11. The computer program of claim 9 wherein the selecting the surviving portions of the two base meshes is automatically calculated by the processor.

12. The computer program of claim 9 wherein tessellating the faces of the base meshes incident to the intersection curve converts any face having greater than three sides into two or more new faces having only three sides.

13. The computer program of claim 9 wherein tessellating the faces of the base meshes incident to the intersection curve converts any face having a number of sides different from four into two or more new faces having only four sides.

14. The computer program of claim 9 further comprising constructing a surface from the resultant base mesh.

15. The computer program of claim 14 wherein the surface is constructed using subdivision rules.

16. The computer program of claim 9 further comprising computing a plurality of intersections between intersecting faces of the two base meshes, the plurality of intersections definging a plurality of intersection curves.