Conversion of a hierarchical subdivision surface to nurbs

#1. Field of the Invention

#The present invention is directed to converting surfaces and objects represented by subdivision surfaces into a NURBS (Non-Uniform Rational B-Spline) representation. More particularly, the present invention provides a method, apparatus, and computer readable storage for implementing conversion algorithms, which convert data representing a subdivision surface into a NURBS representation. The NURBS representation can be displayed or stored in a standard data file readable by NURBS modeling applications.

#2. Description of the Related Art

#FIG. 1 is a flowchart illustrating a general method of the present invention, according to an embodiment of the present invention;

#FIG. 2 is a flowchart illustrating the merging method in more detail, according to an embodiment of the present invention;

#FIG. 3 is a flowchart illustrating the stop condition check, according to an embodiment of the present invention;

#The present invention can be described as a conversion method for converting a subdivision surface to a NURBS representation. After conversion, the NURBS representation can be stored as a standard file format readable by NURBS modeling software (i.e. an IGES file).

#The article “Patching Catmull-Clark Meshes,” by Jorg Peters, published July 2000 discusses how a single face of a subdivided surface can be converted into a NURBS representation. While four vertices define a face in the Peter's subdivided surface, sixteen vertices are needed from the subdivided surface to create that face in the NURBS world. The reason sixteen vertices are needed (as opposed to the four) is due to the basic nature of bi-cubic splines. Thus, to convert a single subdivided face to NURBS, the four vertices defining that face and twelve vertices surrounding that face (picture a 4×4 grid of 16 vertices) are needed.

#Each individual face of a subdivided surface can be converted to a 16 vertex NURBS one by one using the Peters method. However, a subdivided surface typically grows at a rate of N{circumflex over ( )}4 faces for each level. When a subdivided surface contains a very large number of faces, using the “one by one” technique can result in a very large file. The size of an IGES file storing a NURBS conversion of a subdivided sphere of many levels created by the above method can be so large as to be impractical. For example, a cube subdivided 5 times may have 6*4{circumflex over ( )}5=more than 6000 separate NURBS patches to represent it. There are many other benefits of a more compact NURBS representation, including efficient evaluation, ray intersection, and bounding box methods, among others.