Accurate boolean operations for subdivision surfaces and relaxed fitting

A method, comprising:

• identifying selected faces calculated from intersection curves formed by intersecting two Catmull-Clark subdivision surfaces created from two base meshes, the selecting based on a selected Boolean operation;
• chopping the two base meshes directly to create base mesh pieces which form the selected faces;
• creating edges on the base mesh pieces to create quadrangular faces;
• merging the base meshes into a single Boolean base mesh.

A method for creating a Catmull-Clark Boolean base mesh which subdivides to a Boolean surface which represents a Boolean operation of two subdivided surfaces generated from two input base meshes, comprising:

• chopping the input base meshes into pieces containing endpoints having limit points at intersection points of the two subdivided surfaces;
• modifying the chopped pieces to create pieces which can subdivide using Catmull-Clark subdivision rules;
• and
• merging the modified chopped pieces to create the Catmull-Clark Boolean base mesh.

A method comprising:

• traversing a higher level vertex on a Boolean base mesh;
• identifying and flattening influencing vertices influencing the traversed vertex;
• and
• mapping a new vertex, computed by applying subdivision weights to the flattened influencing vertices, to the Boolean base mesh.

A method, comprising:

• chopping pieces of two Catmull-Clark bases meshes which correspond to pieces of a Boolean surface computed from limit surfaces of the two base meshes;
• creating new edges on the chopped pieces to create quadrilaterals and triangles;
• and
• merging the chopped pieces with the new edges into a Boolean base mesh which approximates the Boolean surface;
• traversing a higher level vertex on a Boolean base mesh;
• identifying and flattening influencing vertices influencing the traversed vertex;
• mapping a new vertex, computed by applying subdivision weights to the flattened influencing vertices, to the Boolean base mesh;
• repeating the traversing, identifying, and mapping for a plurality higher level vertices for the Boolean base mesh identified according to subdivision rules;
• refitting the Boolean base mesh using a plurality of mapped new vertices,
• wherein a Boolean operation used to create the Boolean surface is one of scoring, intersection, difference, union,
• wherein the chopping the pieces is performed directly onto the original base meshes,
• wherein the faces are calculated by generating cubic Bezier surfaces,
• wherein the merging merges pieces of the base mesh at intersection points of the limit surfaces,
• wherein the base meshes comprise quadrilaterals,
• wherein during the creating, quadrilaterals are preferred over triangles,
• wherein the quadrilaterals created are convex quadrilaterals.

A method, comprising:

• flattening vertices of a base mesh;
• mapping a vertex computed by applying subdivision rules to the flattened vertices onto the base mesh;
• and
• refitting the base mesh using the mapped vertex.

A computer readable storage medium controlling a computer by,

• chopping pieces of two Catmull-Clark bases meshes which correspond to pieces of a Boolean surface computed from limit surfaces of the two base meshes;
• creating new edges on the chopped pieces to create quadrilaterals and triangles;
• and
• merging the chopped pieces with the new edges into a Boolean base mesh which approximates the Boolean surface.

An apparatus, comprising:

• a chopping module chopping pieces of two Catmull-Clark bases meshes which correspond to pieces of a Boolean surface computed from limit surfaces of the two base meshes;
• a creating module creating new edges on the chopped pieces to create quadrilaterals and triangles;
• and
• a merging module merging the chopped pieces with the new edges into a Boolean base mesh which approximates the Boolean surface.