Epsilon-Sampling of Loop-Subdivision Surfaces

Download: Available after publication

The representation of surfaces proportional to their local feature size (lfs) is a long-standing problem in geometry processing. This type of surface sampling is referred to as epsilon-sampling. For meshes it can be used to reduce the vertices to those, that contribute the highest amount of information to the shape of the mesh. Therefore, this technique can be used to reduce the memory requirement for storing a surface and accelerate geometry processing. The lfs of a point on a surface is usually defined as its distance to the medial axis of the surface. The medial axis can be defined as the set of center points of all maximally inscribed spheres of the surface. Calculating the medial axis of a surface analytically is only feasible for special cases and sampling it by finding maximal inscribed spheres is expensive. Another problem is that for non-smooth surfaces such as triangle meshes the lfs vanishes on edges. It is thus desirable to find an approximation of the lfs that is non-vanishing on discrete meshes and can be calculated reasonably fast. Such an approximation of the medial axis should converge to the medial axis as the minimum sample density of a surface grows.

The aim of my thesis is to develop a method to approximate the lfs of points on a closed triangular mesh through an approximation of the medial axis of the Loop subdivision surface (Loop ss) of the mesh. The medial axis of the Loop ss will be approximated by first approximating the maximal, enclosed tangential sphere at every point in a set of samples of the Loop ss. This results in a point cloud of sphere centers which will be triangulated (This might include line segments). From there an epsilon- sampling process can be implemented: The Loop ss is sampled and for every new sampling point the lfs is approximated by finding the distance of this point to the medial axis approximation. A subdivision surface is the smooth limit surface of a subdivision process of a mesh. In the case of loop subdivision, it has been shown that this limit surface can be parametrized over any regular triangle mesh with a surrounding ring of triangles, called a patch. The limit surface parametrization w.r.t. barycentric coordinates is defined through a set of basis functions, one for each patch vertex. This project will only involve closed manifold meshes which can contain irregular vertices. For irregular triangles it has been shown by Stam that for an arbitrary point inside the triangle, which is not an irregular vertex, one can subdivide the triangle until the point lies inside a new smaller regular triangle with a corresponding patch and that the basis functions can be expressed in terms of the vertices of this smaller patch. Thus a parametrization is available on the smaller triangle. The closer the point, that needs to be evaluated, lies to an irregular vertex of the original triangle, the more subdivision steps are necessary. The considerations that lead to the representations of the basis functions w.r.t. the smaller triangles are based on Eigen-space analysis of the matrix that encodes the loop subdivision scheme. Taking these considerations to the limit allows evaluation of the subdivision surface on irregular vertices

My approach comes with several implementation challenges, which I will tackle with the following strategies:

• Finding the closest point on a subdivision surface:
  The proposed method of sampling the medial axis of the Loop ss by sphere shrinking requires a closest-point-on-Loop-ss operation for a patch. The closest point on the Loop ss will be found by implementing a Newton approximation where in each step the closest point on the tangential plane is found.
   
• Sampling the medial axis
  For every sample point on the Loop ss the largest, enclosed, tangential sphere of the Loop ss is found. Initially, this tangential sphere is chosen to have twice the diameter of the mesh. It is gradually reduced in size until it only intersects the convex hull of one patch. (This requires the convex hulls to be registered in a bounding volume hierarchy). During the reduction process, a list of intersected patch convex hulls is created for each radius. Then, using the closest-point-on-Loop-ss operation the distance of the tangential sphere center to the Loop ss is compared to the tangential sphere radius. Based on this comparison the tangential sphere is iteratively shrunken further or grown until its radius matches its center’s distance to the loop ss. If the tangential sphere has to be iteratively grown all convex hulls that it intersects (registered in the previously created list) must also be checked for sphere intersection with the Loop ss. The iteration is performed until the required precision is reached.
   
• Meshing the medial axis samples
  Once a sample of the medial axis has been found for every sample point on the Loop ss, the obtained cloud of medial axis points can be meshed using a weighted Delaunay triangulation to connect the corresponding sample points of the medial axis. The result is a mesh consisting of tetraeders, triangles, and line segments. The tetraeders are reduced to triangles (based on a heuristic) which produces a mesh of triangles and line segments that approximates the medial axis of the loop ss.