Global Mesh Operations - cmu462/Scotty3D GitHub Wiki

In addition to local operations on mesh connectivity, Scotty3D provides several global remeshing operations (as outlined in the User Guide). Two different mechanisms are used to implement global operations:

• Repeated application of local operations. Some mesh operations are most easily expressed by applying local operations (edge flips, etc.) to a sequence of mesh elements until the target output is achieved. A good example is mesh simplification, which is a greedy algorithm that collapses one edge at a time.
• Global replacement of the mesh. Other mesh operations are better expressed by temporarily storing new mesh elements in a simpler mesh data structure (e.g., an indexed list of faces) and completely re-building the halfedge data structure from this data. A good example is Catmull-Clark subdivision, where every polygon must be simultaneously split into quadrilaterals.

Note that in general there are no inter-dependencies among global remeshing operations (except that some of them require a triangle mesh as input, which can be achieved via the method HalfedgeMesh::triangulate).

Resampling algorithms should complete almost instantaneously (no more than a second or so) on meshes of a few hundred polygons. If performance is significantly worse than this, ensure that implementations are not repeatedly iterating over more elements than needed, or allocating/deallocating more memory than necessary. A useful debugging technique is to print out (or otherwise keep track of, e.g., via an integer counter or a profiler) the number of times basic methods like Halfedge::next() or HalfedgeMesh::newVertex() are called during a single execution of one of the methods; for most methods this number should be some reasonably small constant (no more than, say, 1000!) times the number of elements in the mesh.