3D Model Simplification through Elementary Geometric Structures using Hough Transform

  • Nicolas Ebone Cendron UFRGS
  • Dennis Giovani Balreira UFRGS


Current methods for three-dimensional (3D) model simplification often involve intricate algorithms that may compromise visual fidelity or incur high computational costs. Traditional approaches using decimation algorithms may still fall short in terms of achieving storage efficiency comparable to basic 3D geometric primitives. This paper proposes an approach centered on the utilization of elementary geometric structures, such as spheres and cylinders, for efficient 3D model simplification. Our approach capitalizes on the inherent simplicity of such shapes, enabling representation with fewer parameters and minimal storage requirements. The proposed method replaces intricate geometric details with these fundamental shapes, identifying regions suited to substitution using a Hough Transform-based method. Preliminary findings replace a region of the mesh with a single sphere.We present these primary results visually with the use of spheres for three 3D meshes along with their corresponding percentage gain regarding fundamental characteristics such as vertices, edges, faces, and size. For future work, we intend on expanding our technique to map other parts of the model and exploring further elementary geometries with Hough Transform.


D. Luebke, Level of detail for 3D graphics. Morgan Kaufmann, 2003.

M. Corsini, M.-C. Larabi, G. Lavoué, O. Petřík, L. Váša, and K. Wang, “Perceptual metrics for static and dynamic triangle meshes,” in Computer graphics forum, vol. 32, no. 1. Wiley Online Library, 2013, pp. 101–125.

R. L. Cook, J. Halstead, M. Planck, and D. Ryu, “Stochastic simplification of aggregate detail,” ACM Transactions on Graphics (TOG), vol. 26, no. 3, pp. 79–es, 2007.

J. Hasselgren, J. Munkberg, J. Lehtinen, M. Aittala, and S. Laine, “Appearance-driven automatic 3d model simplification.” in EGSR (DL), 2021, pp. 85–97.

J.-M. Thiery, ´ E. Guy, and T. Boubekeur, “Sphere-meshes: Shape approximation using spherical quadric error metrics,” ACM Transactions on Graphics (TOG), vol. 32, no. 6, pp. 1–12, 2013.

M. Garland and P. S. Heckbert, “Surface simplification using quadric error metrics,” in Proceedings of the 24th annual conference on Computer graphics and interactive techniques, 1997, pp. 209–216.

A. Kaiser, J. A. Ybanez Zepeda, and T. Boubekeur, “A survey of simple geometric primitives detection methods for captured 3d data,” in Computer Graphics Forum, vol. 38, no. 1. Wiley Online Library, 2019, pp. 167–196.

Z. Liu, C. Zhang, H. Cai, W. Qv, and S. Zhang, “A model simplification algorithm for 3d reconstruction,” Remote Sensing, vol. 14, no. 17, p. 4216, 2022.

Y. Xian, Y. Fan, Y. Huang, G. Wang, C. Tu, X. Meng, and J. Peng, “Mesh simplification with appearance-driven optimizations,” IEEE Access, vol. 8, pp. 165 769–165 778, 2020.

J. Rossignac and P. Borrel, “Multi-resolution 3d approximations for rendering complex scenes,” in Modeling in computer graphics: methods and applications. Springer, 1993, pp. 455–465.

W. J. Schroeder, J. A. Zarge, and W. E. Lorensen, “Decimation of triangle meshes,” in Proceedings of the 19th annual conference on Computer graphics and interactive techniques, 1992, pp. 65–70.

M. Garland and Y. Zhou, “Quadric-based simplification in any dimension,” ACM Transactions on Graphics (TOG), vol. 24, no. 2, pp. 209–239, 2005.

J. Cohen, A. Varshney, D. Manocha, G. Turk, H. Weber, P. Agarwal, F. Brooks, and W. Wright, “Simplification envelopes,” in Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, 1996, pp. 119–128.

J. Illingworth and J. Kittler, “A survey of the hough transform,” Computer vision, graphics, and image processing, vol. 44, no. 1, pp. 87–116, 1988.

P. Mukhopadhyay and B. B. Chaudhuri, “A survey of hough transform,” Pattern Recognition, vol. 48, no. 3, pp. 993–1010, 2015.

A. Abuzaina, M. S. Nixon, and J. N. Carter, “Sphere detection in kinect point clouds via the 3d hough transform,” in Computer Analysis of Images and Patterns: 15th International Conference, CAIP 2013, York, UK, August 27-29, 2013, Proceedings, Part II 15. Springer, 2013, pp. 290–297.

K. Khoshelham, “Extending generalized hough transform to detect 3d objects in laser range data,” in ISPRS Workshop on Laser Scanning, vol. 36, 2007, p. 206.

A. K. Patil, P. Holi, S. K. Lee, and Y. H. Chai, “An adaptive approach for the reconstruction and modeling of as-built 3d pipelines from point clouds,” Automation in construction, vol. 75, pp. 65–78, 2017.

T. Rabbani and F. Van Den Heuvel, “Efficient hough transform for automatic detection of cylinders in point clouds,” Isprs Wg Iii/3, Iii/4, vol. 3, pp. 60–65, 2005.

Y.-H. Jin and W.-H. Lee, “Fast cylinder shape matching using random sample consensus in large scale point cloud,” Applied Sciences, vol. 9, no. 5, p. 974, 2019.

D. Borrmann, J. Elseberg, K. Lingemann, and A. Nüchter, “The 3d hough transform for plane detection in point clouds: A review and a new accumulator design,” 3D Research, vol. 2, no. 2, pp. 1–13, 2011.

R. Wang, K. Zhou, J. Snyder, X. Liu, H. Bao, Q. Peng, and B. Guo, “Variational sphere set approximation for solid objects,” The Visual Computer, vol. 22, pp. 612–621, 2006.

M. Garland and P. S. Heckbert, “Simplifying surfaces with color and texture using quadric error metrics,” in Proceedings Visualization’98 (Cat. No. 98CB36276). IEEE, 1998, pp. 263–269.
Como Citar

Selecione um Formato
CENDRON, Nicolas Ebone; BALREIRA, Dennis Giovani. 3D Model Simplification through Elementary Geometric Structures using Hough Transform. In: WORKSHOP DE TRABALHOS EM ANDAMENTO - CONFERENCE ON GRAPHICS, PATTERNS AND IMAGES (SIBGRAPI), 36. , 2023, Rio Grande/RS. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2023 . p. 105-108. DOI: https://doi.org/10.5753/sibgrapi.est.2023.27460.