Geometric Processing

This project implements algorithms for the subdivision and decimation of polygonal meshes loaded from .OBJ files, in an interactive WebGL renderer.

GitHub Repository: https://github.com/b1skit/GeometricModeling

Project Details:

This project was initially created as a series of assignments for SFU’s Geometric Modeling In Computer Graphics course. Several classic algorithms for polygonal mesh refinement and decimation are implemented in JavaScript, and presented via a WebGL canvas embedded in an interactive HTML/CSS GUI.

The program can process arbitrary, closed-manifold meshes supplied in .OBJ format (Note: uploading of user-supplied .OBJs has been disabled here for security reasons). The resulting mesh can be optionally downloaded in .OBJ format after processing.

Internally, triangular mesh geometry is represented using a winged-edge data structure, which allows for constant-time (i.e. O(1)) queries of topology and adjacency via vertex, edge, and face references.

Loop & Butterfly Subdivision Schemes:

Both the loop and butterfly subdivision schemes are implemented, allowing polygonal meshes to be smoothed through local refinement. The resulting limit surface produced by these algorithms is C² continuous, except for extraordinary vertices (i.e. vertices of a triangular mesh with a degree ≠ 6), which are C¹ continuous.

Loop Subdivision:

• Each triangle is recursively replaced with 4 smaller triangles created from new vertices.
• Loop subdivision is an approximating subdivision scheme: Weighted combinations of neighboring vertices are used to compute vertex locations in the resulting subdivided mesh.
  • Thus, the original vertices are not guaranteed to be included in the subdivided result.

Butterfly Subdivision:

• Each edge is recursively divided by inserting new vertices.
• Butterfly subdivision is an interpolating subdivision scheme: The location of new vertices inserted along each edge is computed as a weighted combination of neighboring vertices in the original mesh.
  • Thus, all original vertices are guaranteed to be included in the subdivided result.

Quadric-based Mesh Decimation via a Multiple Choice Scheme:

A multiple choice decimation scheme is implemented to allow polygonal meshes to be simplified through iterative edge removal. Edges are removed by collapsing corresponding pairs of vertices to a single point, a potentially topology-modifying operation. The ideal location of this new point is found by solving for the minimum squared distance (via error quadrics) possible between each of the supporting planes of the triangles incident to the vertices of the current edge.

During each iteration of the decimation process, the quality of the resulting mesh approximation is ensured through two optimizations:

1. Outer optimization: The edge that will result in the least quadric error being introduced after collapse is selected from amongst a set k randomly chosen candidate edges.
   • Earlier versions of this algorithm employ a priority queue of the quadric errors associated with each edge; choosing the best candidate edge from a small set of randomly chosen edges is faster and provides comparable decimation quality. The value of k can be tuned to trade efficiency for correctness.
2. Inner optimization: The vertex location is chosen to minimize quadric error introduced by collapsing the chosen edge.