Approximation of catmull-clark subdivision surfaces by bezier patches

• US 20040001061A1
• Filed: 07/01/2002
• Published: 01/01/2004
• Est. Priority Date: 07/01/2002
• Status: Active Grant

• Current Assignee: Autodesk, Inc.
• Original Assignee: Autodesk, Inc.
• Inventors: Rice, Richard Everett, Stollnitz, Eric Joel
• Granted Patent: US 6,950,099 B2
• Time in Patent Office: Days
• US Class Current: 345/423
• CPC Class Codes: G06T 17/30 Polynomial surface description

Abstract

A method for converting a subdivision surface, such as a Catmull-Clark subdivision surface, into a cubic Bezier surface defined by sixteen control points. The method includes (a) converting a subdivision face to Bezier control points using a conversion matrix using fifteen points and a dummy value for an unavailable sixteenth point; and (b) replacing one of the Bezier control points which corresponds to an extraordinary point on the subdivision face with the extraordinary point'"'"'s limit point.

Claims

1. A method, comprising:

converting a subdivision face to Bezier control points using a conversion matrix using fifteen points and a dummy value for an unavailable sixteenth point; and

replacing one of the Bezier control points which corresponds to an extraordinary point on the subdivision face with the extraordinary point'"'"'s limit point.

2. A method as recited in claim 1, further comprising:

adjusting affected Bezier control points which are affected by using the dummy value to better fit a Bezier patch defined by the Bezier control points with a limit surface of the subdivision face.

3. A method as recited in claim 2, wherein an affected Bezier control point is adjusted by sliding the affected control point along a tangent of a respective limit side of the subdivision face.

4. A method as recited in claim 3, wherein a location the affected Bezier control point is moved to is determined by using a least squares determination.

5. A method as recited in claim 4, wherein the least squares determination computes a best solution for the affected control point, using three other control points defining the curve, to fit a point on the curve with a corresponding point on the limit surface of the subdivision face.

6. A method as recited in claim 5, wherein the corresponding point is halfway along the curve.

7. A method as recited in claim 1, wherein the subdivision face is formed using Catmull Clark subdivision rules.

8. A method, comprising:

converting a subdivision face to Bezier control points using a conversion matrix using fifteen points and a dummy value for an unavailable sixteenth point; and

replacing one of the Bezier control points which corresponds to an extraordinary point on the subdivision face with the extraordinary point'"'"'s limit point.

adjusting affected Bezier control points which are affected by using the dummy value to better fit a Bezier patch defined by the Bezier control points with a limit surface of the subdivision face,

wherein an affected Bezier control point is adjusted by sliding the affected control point along a tangent of a respective limit side of the subdivision face,

wherein a location the affected Bezier control point is moved to is determined by using a least squares determination,

wherein the least squares determination computes a best solution for the affected control point, using three other control points defining the curve, to fit a point on the curve with a corresponding point on the limit surface of the subdivision face,

wherein the corresponding point is halfway along the curve,

wherein the subdivision face is formed using Catmull Clark subdivision rules.

9. A method, comprising:

converting a subdivision face to Bezier control points using a conversion matrix using fifteen points and a dummy value for an unavailable sixteenth point;

calculating a tangent to a limit surface of the subdivision face at an extraordinary point; and

moving an affected Bezier control point of the Bezier control points along the tangent to better fit a Bezier surface defined by the Bezier control points to the subdivision limit surface.

10. A method for converting to a Bezier representation when an edge of a face is creased, comprising:

converting a subdivision face to Bezier control points using a creased conversion matrix using sixteen points; and

replacing one of the Bezier control points which corresponds to an endpoint of a creased edge of the subdivision face with the endpoint'"'"'s limit point.

11. A method, comprising:

converting a subdivision face containing an extraordinary point to a Bezier patch defined by Bezier control points; and

adjusting a Bezier control point to improve the conversion.

12. A method, comprising:

converting a subdivision face with a creased edge to a Bezier patch defined by Bezier control points; and

adjusting a Bezier control point to improve the conversion.

13. A computer readable storage, controlling a computer by,

converting a subdivision face to Bezier control points using a conversion matrix using fifteen points and a dummy value for an unavailable sixteenth point;

and

replacing one of the Bezier control points which corresponds to an extraordinary point on the subdivision face with the extraordinary point'"'"'s limit point.

14. A computer readable storage as recited in claim 14, further comprising:

adjusting affected Bezier control points which are affected by using the dummy value to better fit a Bezier patch defined by the Bezier control points with a limit surface of the subdivision face.

15. An apparatus, comprising:

a converting module converting a subdivision face to Bezier control points using a conversion matrix using fifteen points and a dummy value for an unavailable sixteenth point; and

a replacing module replacing one of the Bezier control points which corresponds to an extraordinary point on the subdivision face with the extraordinary point'"'"'s limit point.

16. An apparatus as recited in claim 15, further comprising:

an adjusting module adjusting affected Bezier control points which are affected by using the dummy value to better fit a Bezier patch defined by the Bezier control points with a limit surface of the subdivision face.

17. An apparatus, comprising:

means for converting a subdivision face to Bezier control points using a conversion matrix using fifteen points and a dummy value for an unavailable sixteenth point; and

means for replacing one of the Bezier control points which corresponds to an extraordinary point on the subdivision face with the extraordinary point'"'"'s limit point.

18. An apparatus as recited in claim 17, further comprising:

means for adjusting affected Bezier control points which are affected by using the dummy value to better fit a Bezier patch defined by the Bezier control points with a limit surface of the subdivision face.