GPU-Accelerated Triangle Mesh Simplification Using Parallel Vertex Removal

We present an approach to triangle mesh simplification
designed to be executed on the GPU. We use a quadric error metric
to calculate an error value for each vertex of the mesh and order all
vertices based on this value. This step is followed by the parallel
removal of a number of vertices with the lowest calculated error
values. To allow for the parallel removal of multiple vertices we use
a set of per-vertex boundaries that prevent mesh foldovers even when
simplification operations are performed on neighbouring vertices. We
execute multiple iterations of the calculation of the vertex errors,
ordering of the error values and removal of vertices until either a
desired number of vertices remains in the mesh or a minimum error
value is reached. This parallel approach is used to speed up the
simplification process while maintaining mesh topology and avoiding
foldovers at every step of the simplification.

Authors:

• Thomas Odaker
• Dieter Kranzlmueller
• Jens Volkert

Keywords:

• Computer graphics
• half edge collapse
• mesh simplification
• precomputed simplification
• topology preserving.

References:

[1] Clark, J. H. Hierarchical geometric models for visible surface
algorithms, Com. of ACM 19, No. 10, pp.547-554, 1976
[2] Rossignac, J., and Borrell, P. Multi-resolution 3D Approximations for
Rendering Complex Scenes, Modeling of Computer Graphics: Methods
and Applications, pp.455-465, 1992
[3] Schaefer, S., and Warren., J. Adaptive vertex clustering using octrees,
Proceedings of SIAM Geometric Design and Computing 2003, Vol. 2,
pp.491-500, 2003
[4] Low, K.-L., and Tan, T., S., Model simplification using vertex-clustering,
SI3D Proceedings 1997, pp.75-ff., 1997
[5] Schroeder, W., J., Zarge, J., A., and Lorensen, W., E. Decimation of
triangle meshes, ACM SIGGRAPH Computer Graphics Vol. 26, No. 2,
pp.65-70, 1992
[6] Hoppe, H., DeRose, T., Duchamp, T., McDonald, J., A., and Stuetzle,
W. Mesh optimization, ACM SIGGRAPH Proceedings 1993, pp.19-26,
1993
[7] Hu, L., Sander, P., V., and Hoppe, H. Parallel view-dependent refinemnet
of progressive meshes, I3D 2009 Proceedings of the 2009 Symposium
on Interactive 3D Graphics and Games, pp.169-176, 2009
[8] DeCoro, C., and Tatarchuk, N. Real-time mesh simplification using the
GPU, I3D 2007 Proceedings of the 2007 Symposium on Interactive 3D
Graphics Vol. 2007, pp.161-166, 2007
[9] Hoppe, H. Progressive meshes, ACM SIGGRAPH 1996 Proceedings,
pp.99-108, 1996
[10] Xia, J., C., El-Sana, J., and Varshney, A. Adaptive real-time
level-of-detail-based rendering for polygonal models, IEEE Transactions
on Visualization and Computer Graphics Vol. 3, No. 2, pp.171-187, 1997
[11] Garland, M., and Heckbert, P., S. Surface simplification using quadric
error metrics, SIGGRAPH Proceedings 1997, pp.209-216, 1997
[12] Hu, L., Sander, P., and Hoppe, H. Parallel view-dependent level of detail
control, IEEE Transactions on Visualization and Computer Graphics Vol.
16, No. 5, pp.718-728, 2010
[13] Papageorgiou, A., and Platis, N. Triangular mesh simplification on the
GPU, The Visual Computer: International Journal of Computer Graphics
Vol. 31, Issue 2, pp.235-244, 2015
[14] Odaker, T., Kranzlmueller, D., Volkert, J. View-dependent Simplification
using Parallel Half Edge Collapses, WSCG 2015 Conference
Proceedings, pp.63-72, 2015