Survey of polygonal surface simplification algorithms on GPU
https://doi.org/10.15514/ISPRAS-2014-26(2)-7
Abstract
Rendering time depends on number of faces in polygonal mesh. Displaying large number of objects or objects with a lot of faces can result in performance degradation. One of the ways to overcome this problem is to use several levels of detail for polygonal mesh. Levels of detail with low quality are used when object is far away from camera and difference in number of faces is not apparent to viewer. Coarse meshes can be generated manually which is difficult and time consuming. For many applications (computer graphics, computer vision, finite element analysis) it's preferable to use automated methods for polygonal surface simplification to increase performance. Traditional methods for surface simplification are designed for CPU. GPU methods provide improvements in performance and have comparable visual quality. This survey covers algorithms on GPU. They are based on either shader programming or general purpose computing frameworks like OpenCL and CUDA. Shader methods are very restrictive. They are designed to render images in real-time. General purpose computing frameworks provide flexible APIs but require attention to hardware implementation details to avoid performance bottlenecks. Main features of algorithms are provided for comparison as the result. The most used operation for geometry simplification is edge collapse. It's difficult to avoid expensive data exchange between GPU and CPU. It's important to take into account computational model of GPU to increase number of stream processors working in parallel.
References
1. Garland M., Heckbert P. "Surface simplification using quadric error metrics" in Proceedings of the 24th annual conference on Computer graphics and interactive techniques, pp. 209–216, 1997.
2. DeCoro C., Tatarchuk N. "Real–time Mesh Simplification Using GPU" in Proceedings of the symposium on interactive 3D graphics and games, 2007.
3. Blythe D. "The Direct3D 10 System" in ACM Transactions on Graphics, vol. 25, no. 3, pp. 724–734, 2006.
4. Lindstrom P. "Out–of–core simplification of large polygonal models" in Proceedings of the 27th annual conference on Computer graphics and interactive techniques, 259–262, 2000.
5. Rossignac J., Borrel P. "Multi–resolution 3D approximations for rendering complex scenes" Modeling in Computer Graphics: Methods and Applications, pp. 455–465, 1993.
6. Vad'ura J. "Parallel mesh decimation with GPU" 2011.
7. Gueziec A. "Surface simplification inside a tolerance volume" Second Annual International Symposium on Medical Robotics and Computer Aided Surgery, pp. 123–139, 1995.
8. Hjelmervik J., Leon J. "GPU–accelerated shape simplification for mechanical based applications" Shape modeling international, pp. 91–102, IEEE Computer Society, 2007.
9. Shreiner D., Woo M., Neider J., Davis T. "OpenGL(R) Programming Guide: The Official Guide to Learning OpenGL(R), Version 2", 2005.
10. Papageorgiou A., Platis N. "Triangular mesh simplification on the GPU" NASAGEM Geometry Processing Workshop, Computer Graphics International, 2013.
11. Shontz S., Nistor D. "CPU–GPU algorithms for triangular surface mesh simplification" in Proceedings of the 21st international meshing roundtable, pp. 475–492, Springer, Berlin, 2013.
12. Schroeder W., Zarge J. and Lorensen W. "Decimation of Triangle Meshes" ACM Siggraph Computer Graphics, vol. 26, no. 2, pp. 65–70, 1992.
13. Rossignac J. and Borrel P. "Multi–Resolution 3D Approximations for Rendering Complex Scenes" Geometric Modeling in Computer Graphics, pp. 455–465, 1993.
14. He T., Hong L., Kaufman A., Varshney A. and Wang S. "Voxel–Based Object Simplification" in Proceedings of the 6th conference on Visualization '95, pp. 296–303, 1995.
15. Low K. and Tan T. "Model Simplification Using Vertex–Clustering" in Proceedings of the 1997 symposium on Interactive 3D graphics, pp. 75–82, 1997.
16. Schroeder W. "A Topology Modifying Progressive Decimation Algorithm" in Proceedings of the 8th conference on Visualization '97, pp. 205–212, 1997.
17. Cohen J., Varshney A., Manocha D., Turk G., Weber H., Agarwal P., Brooks F. and W. Wright "Simplification Envelopes" in Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, pp. 119–128, 1996.
18. Hoppe H. "Progressive Meshes" in Proceedings of the 24th annual conference on Computer graphics and interactive techniques, pp. 209–216, 1997.
19. Garland M. and Heckbert P. "Surface Simplification Using Quadric Error Metrics" in Proceedings of the 24th annual conference on Computer graphics and interactive techniques, pp. 209–216, 1997.
20. Garland M. and Heckbert P. "Simplifying Surfaces with Color and Texture using Quadric Error Metrics" in Proceedings of the conference on Visualization '98, pp. 263–269, 1998.
21. Popovic J. and Hoppe H. "Progressive Simplicial Complexes" in Proceedings of the 24th annual conference on Computer graphics and interactive techniques, pp. 217–224, 1997.
22. Dehne F., Langis C. and Roth G. "Mesh simplification in parallel" in Proceedings of the 4th International Conference on Algorithms and Architectures for Parallel Processing, pp. 281–290, 2000.
Review
For citations:
Gonakhchyan V.I. Survey of polygonal surface simplification algorithms on GPU. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2014;26(2):159-174. (In Russ.) https://doi.org/10.15514/ISPRAS-2014-26(2)-7
Email this article 