Technical SectionMesh simplification by stochastic sampling and topological clustering
Introduction
Mesh simplification is a fundamental tool in geometry processing. One may distinguish two different application scenarios:
Constructing the best possible approximation of a given discrete surface, where the resulting mesh will be stored and reused, and the time spent on the simplification is of minor concern [1], [2], [3].
Down-sampling a mesh instantly for preview on or transmission over limited devices, where the approximation is usually discarded after the task is performed, and it is critical that the mesh is provided instantly [4], [5].
TopStoc is designed for cases in which simplification is not performed in a preprocess, but as part of a loop combined with other processing steps on data that is large and contains geometrical and topological features that would ideally be retained. Our approach is composed of two steps, which are each interesting in their own right as a tool in digital geometry processing:
- 1.
The set of vertices for the simplified model is computed by sweeping over the input and selecting vertices probabilistically (see Section 3.1). The number of vertices can be prescribed and the selected vertices concentrate around features.
- 2.
The triangles connecting the selected vertices are computed by first assigning all vertices in the original mesh to the topologically closest selected vertex and then identifying triangles in the original mesh that are incident upon vertices assigned to three different selected vertices (see Section 3.2).
We have implemented this approach and analyzed the distribution of resulting meshes (see Section 5). It turns out that the method is generally very fast, and that the feature-driven stochastic vertex selection provides significant improvements in visual quality over similarly fast techniques. We substantiate this claim by measuring errors in differentials of the mesh, rather than only Hausdorff distance. Generally, stochastic selection and topological clustering are interesting linear approaches with good global properties. We provide more detailed conclusions in Section 6.
Section snippets
Previous work
Quality-oriented simplification was initiated by the seminal work of Hoppe [1], introducing an optimization approach with a set of local mesh operators, among which the edge-collapse/vertex-split pair also proved instrumental for multiresolution mesh representations [6]. Garland and Heckbert [7] introduced the quadric error metric (or QEM) for driving the simplification process. This metric computes and stores the error/importance of a vertex as the sum of its squared distances to the
The algorithm
The TopStoc algorithm is designed to operate on a simple triangle mesh with the list of vertices and the list of triangles indexed over (standard representation in rendering engines of modeling tools). The main steps are selecting a subset of size , then partitioning into connected components covering the mesh, and identifying triangles that belong to three different components in the partition of . The mesh is the output of the algorithm. Note that, in
Establishing guarantees
TopStoc is based purely on local stochastic selection. This makes the algorithm very fast, but also means the placement of vertices as well as the topology of the resulting surface might sometimes turn out to be inadequate. We offer a modification of the sampling so that selected vertices have specified minimum distances; and we introduce resampling of sub-meshes that violate the closed-ball property [22] so that can be enforced to be homotopy equivalent to or to specifically remove
Implementation and results
TopStoc has been designed for aggressive in-core simplification, providing an alternative to grid clustering [4], [5], yet adapting to the topology and features of models in a CAD or geometry processing environment. Despite of its adaptivity, TopStoc is linear, both in time and memory. It only requires a fixed and small amount of memory for a given object, stored in a standard indexed mesh format, with unordered one-ring vertex references—in particular, no higher order mesh or hierarchical data
Conclusion and future work
TopStoc is a simple but nevertheless very useful mesh simplification algorithm. By combining simple statistic and probabilistic tools, we design a geometry aware stochastic sampling that preserves important geometric features without requiring global sorting of the surface elements (spatial, error-driven, etc). With topological clustering, TopStoc preserves the topology of its input 3D surfaces, and in contrast to space partitioning approaches, avoids the collapsing of multiple surface layers.
Acknowledgements
We thank Nina Amenta for early discussion on the nerve lemma. We also thank reviewers for helping improving this paper. Models are courtesy Aim@Shape Network and Stanford University.
References (30)
- et al.
Optimal triangulation and quadric-based surface simplification
Journal of Computational Geometry: Theory and Applications
(1999) - et al.
Mesh optimization
- et al.
Simplifying surfaces with color and texture using quadric error metrics
- et al.
Variational shape approximation
- et al.
Multi-Resolution 3D approximation for rendering complex scenes
Modeling in Computer Graphics
(1993) Out-of-core simplification of large polygonal models
- Hoppe H. Progressive meshes. In: ACM SIGGRAPH; 1996. p....
- et al.
Surface simplification using quadric error metrics
- et al.
Fast mesh decimation by multiple-choice techniques
- et al.
Real-time Mesh Simplification using the GPU
Efficient simplification of point-sampled surfaces
A stream algorithm for the decimation of massive meshes
Re-tiling polygonal surfaces
Computer Graphics (SIGGRAPH 92)
Mesh saliency
Efficient adaptive simplification of messive meshes
Cited by (26)
Proximity-aware multiple meshes decimation using quadric error metric
2020, Graphical ModelsCitation Excerpt :Low and Tan [6] extend this idea to arbitrary shapes using voxel grids. Following these ideas, Boubekeur andAlexa [7] use stochastic vertex selection based on a local feature estimator, combined with triangle re-indexing to better preserve areas of high curvature. Overall, it remains difficult to localize decimation and control the granularity of the simplification with this family of approaches.
Error diffusion on meshes
2015, Computers and Graphics (Pergamon)Citation Excerpt :As an application of this idea we show how to subsample a mesh for simplification (see Section 5). The remaining vertices are then reconnected as triangles based on intrinsic graph distances, as in Boubekeur and Alexa [20]. We show that we achieve better preservation of the original geometry in linear time for the same vertex count, thus providing a very fast mesh decimation technique with acceptable quality.
Fiedler trees for multiscale surface analysis
2010, Computers and Graphics (Pergamon)Citation Excerpt :These methods, however, are rather sensitive to noise and computationally costly, particularly for the purposes of generating a hierarchy of quality meshes, as any algorithm would need to be run from scratch each time for each resolution. These two issues can be alleviated via heuristic methods [4], albeit at the cost of good quality meshes. Our tree construction is based on recent results in the areas of spectral graph theory and spectral geometry processing; we refer to [2,21] for comprehensive surveys on the subjects, respectively.
3D point clouds simplification based on geometric primitives and graph-structured optimization
2022, Proceedings - International Conference on Pattern RecognitionMesh simplification accompanied by its denoising of scanned data
2019, Engineering with Computers