Bryan Chan
CS779 W03 Project
A-Patches are an implicit surface construction scheme used to build interpolating C1 surfaces on triangular meshes. The basic goal of the project was to generate and render cubic A-Patches[1] in OpenGL. This involves construction of the simplicial hull of tetrahedra; setting the Bezier control points in each tetrahedra under interpolation, C1, and single-sheetedness constraints; and finally tesselating across each tetrahedra with a Cubic root finder.
Because the construction algorithm depends heavily on face adjacency information and uses mesh subdivision to handle special cases, I chose to use a half-edge data structure. An added benefit of the half-edge is that each face corresponds to a face tetrahedron (or a pair of top/bottom face tetrahedra), and each edge corresponds to an edge tetrahedron (or pair) in the simplicial hull.
To store control point information, the class for tetrahedra keeps a 3-dimensional array that uses the first 3 indices of each control points multi-index. When accessing control points, the tetrahedra class can permute the order of the indices
The simplicial hull is a group of tetrahedra surrounding the original mesh. There is a face tetrahera or a pair of face tetrahedra for each face, and edge tetrahedra that join face tetrahedra across edges in the mesh.
To ensure that it is possible to construct a surface within the simplicial hull, the tangent plane at each vertex must lie within the hull. To achieve tangent plane containment, the new vertex for each face tetrahedra is chosen by intersecting the vertex tangent planes with a perpendicular drawn from the center of the inscribed circle in the face. The intersection furthest from the face is used, so that all the other tangent planes lie within.
When the face is negative convex, then only the tetrahedra below the surface needs to be built. For a positive convex face, only the tetrahedra above the surface needs to be built. A pair of tetrahedra are built for non-convex faces. After building the face tetrahedra, two edge tetrahedra are created for each edge to join together the face tetrahedra.
| Negative Convex | Positive Convex | Non-Convex |
|
|
|
This construction can fail two cases.
The control points within each tetrahedra must be chosen to satisfy three conditions: vertex/normal interpolation, and C1 continuity across tetrahedra, and single-sheetedness. Here's how I implemented the construction:
These are set by default to approximate a quadratic patch
The special surface construction cases that require a Clough-Tocher split of a face tetrahedra are not handled. This occurs when two triangles are coplanar, or when a nonconvex face is neighboured by some faces the make a dihedral angle < 180 degrees and some that do not.
The single-sheetedness checks fail occasionally when the control points are very small, leading to gaps in the surface where multiple sheets occur.
Local Butterfly subdivision was implemented to handle special cases during simplicial hull construction. The original scheme to handle sharp edges and vertices[1] does not appear to give an interpolating surface. A later paper suggests using a Butterfly local subdivision[4] which is what I implemented. For sharp vertices, each incident edge is subdivided, and then all adjacent faces are removed and re-triangulated using the new edge points.
| Sharp Vertex | Fixed Sharp Vertex |
 |
 |
Sharp edges are similar, except new edge points are generated for every edge incident to one of the sharp edge's vertices.
| Sharp Edge | Fixed Sharp Edge |
 |
 |
Butterfly subdivision can also be done on the whole mesh. This was used to generate some of the comparison surfaces in the gallery.
| Blob Mesh | Blob (3 levels of Butterfly) |
 |
 |
The free surface parameters must be set carefully to avoid bumpy surfaces. One way the free cubic parameters in a tetrahedra can be set so that they approximate a quadratic patch. This is by finding the quadratic tetrahedron control points with the best least squares fit to the non-free cubic control points. Then, degree elevation is used to find the free cubic control points.
The GUI supports the following:
The four sliders along the bottom globally scale the different free parameters using a logarithmic scale.
If the slider value is set to s, then the actual value used for that parameter is es
The Base and Face Top controls scales the parameters on the bottom and top of the face tetrahedra. Decreasing
The Edge control scales the one free parameter on the edge tetrahedra. Decreasing this parameter lifts the surface near the edge up, and vice versa.
The Vertex Normal slier scales vertex normals. Smaller vertex normals result in a surface closer to the original mesh.
A number of items can be toggled to show different steps in the construction.
Mesh
In general, the A-Patch surfaces produced by the current renderer C1 but somewhat bumpy. This is probably because the default parameter approximation works well only for certain shapes, and fails in most cases where the mesh is not a quadric surface.
| ball |
 |
ball (face patches only) |
 |
These were built using a mesh modeller from a CS488 project modified to output s3d and generate vertex normals using Loop subdivision[4]
blob (A-Patch with convexity) |
 |
| This is a simple blob with some non-convex faces. It is apparent that the quadratic approximation used to set the free parameters still gives a bumpy surface. |
enterprise (mesh with vertex normals) |
 |
enterprise (A-Patch) |
 |
starfish (mesh with vertex normals) |
 |
starfish (A-Patch) |
 |
mannequin (mesh with convexity) |
 |
mannequin (simplicial hull) |
 |
mannequin (butterfly, 3 levels) |
 |
mannequin (A-Patch) |
 |
modeling with A-patches
from rational trivariate functions.'' Computer Aided Geometric
Design, Vol. 18, No. 3, April 2001.