Mesh simplification by stochastic sampling and topological clustering

We introduce TopStoc, a fast mesh simplification algorithm. The two main components are stochastic vertex selection and re-indexing of triangles. The probability for vertex selection depends on a local feature estimator, which prefers areas of high curvatures but still ensures sufficient sampling in flat parts. Re-indexing the triangles is done by breadth-first traversal starting from the selected vertices and then identifying triangles incident upon three regions. Both steps are linear in the number of triangles, require minimal data, and are very fast, while still preserving geometrical and topological features. Additional optional processing steps improve sampling properties and/or guarantee homotopy equivalence with the input. These properties provide an alternative to vertex clustering especially for CAD/CAM models in the areas of previewing or network graphics.