Halfedge Collapse

Incremental Mesh Reduction

The fundamental algorithm for incremental mesh reduction has the following general form:

• Select one of the Euler operators to remove vertices
• Algorithm
  • for each vertex, compute the error that its removal would produce
  • collect all errors in a priority queue, smallest error first
  • Mail loop:
    • remove first element from the queue
    • recompute errors and update priority queue
    • stop if a given number of elements were removed or the smallest error is above a given threshold

Euler Operators

An Euler operator modify the mesh topology locally by preserving the Euler-Poincaré characteristic of the mesh.

For incremental mesh reduction the following Euler operators are commonly used

• vertex removal followed by hole filling without vertex insertion
• edge collapse
• halfedge collapse

Halfedge Collapse

A halfedge collapse consist is collapsing one halfedge, which results in removing the origin vertex. Intuitively, a halfedge collapse consist in merging the origin vertex of the halfedge with the vertex to which the halfedge points.

Error Quadrics

The error being produced by removing a vertex is computed using error quadrics. The quadric error of a point is the sum of its squared distance to a set of planes.

---

---

The JavaScript Code