Topological analysis of voxelized objects by discrete geodesic Reeb graph.(English)Zbl 1390.68708
Summary: We introduce here the concept ofdiscrete level sets (DLS) that can be constructed on a voxelized surface with the assurance of certain topological properties. This eventually aids in construction ofdiscrete geodesic Reeb graph (DGRG) on a voxelized object, for topological analysis. Under various transformations like rotation and topology-constrained anisotropic deformation, a DGRG remains invariant to typical topological features like loops or cycles, which eventually helps in identifying ’handles’ in the underlying object. Experiments on different datasets show promising results on the practical usefulness of DLS and DGRG towards extraction of high-level topological features of arbitrary voxel sets.
MSC:
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
Keywords:
digital geometry;discrete topology;geodesics;geodesic level sets;shape analysis;voxelization;Reeb graphCite
Full Text:DOI
References:
| [1] | Antini, G.; Berretti, S.; Del Bimbo, A.; Pala, P., 3D mesh partitioning for retrieval by parts applications, (Int. Conf. Multimedia and Expo (2005), IEEE), 1210-1213 |
| [2] | Balasubramanian, M.; Polimeni, J. R.; Schwartz, E. L., Exact geodesics and shortest paths on polyhedral surfaces, IEEE Trans. Pattern Anal. Mach. Intell., 31, 6, 1006-1016 (2009) |
| [3] | Berretti, S.; Bimbo, A. D.; Pala, P., Partitioning of 3D meshes using Reeb graph, (18th Int. Conf. Pattern Recognition (2006)), 19-22 |
| [4] | Berretti, S.; Del Bimbo, A.; Pala, P., 3D mesh decomposition using Reeb graphs, Image Vis. Comput., 27, 10, 1540-1554 (2009) |
| [5] | Bhalla, G.; Bhowmick, P., DIG: discrete iso-contour geodesics for topological analysis of voxelized objects, (6th Int. Conf. Computational Topology in Image Context. 6th Int. Conf. Computational Topology in Image Context, Lecture Notes in Computer Science, vol. 9667 (2016), Springer), 265-276 ·Zbl 1339.68254 |
| [6] | Biasotti, S.; Falcidieno, B.; Spagnuolo, M., Extended Reeb graphs for surface understanding and description, (Discrete Geometry for Computer Imagery. Discrete Geometry for Computer Imagery, Lecture Notes in Computer Science, vol. 1953 (2000), Springer), 185-197 ·Zbl 1043.68785 |
| [7] | Biasotti, S.; Giorgi, D.; Spagnuolo, M.; Falcidieno, B., Reeb graphs for shape analysis and applications, Theor. Comput. Sci., 392, 1-3, 5-22 (2008) ·Zbl 1134.68064 |
| [8] | Biswas, R.; Bhowmick, P., On different topological classes of spherical geodesic paths and circles in \(Z^3\), Theor. Comput. Sci., 605, 146-163 (2015) ·Zbl 1337.53048 |
| [9] | Brimkov, V. E., Formulas for the number of \((n - 2)\)-gaps of binary objects in arbitrary dimension, Discrete Appl. Math., 157, 3, 452-463 (2009) ·Zbl 1168.68048 |
| [10] | Brimkov, V. E.; Barneva, R. P., Graceful planes and lines, Theor. Comput. Sci., 283, 1, 151-170 (2002) ·Zbl 1050.68147 |
| [11] | Brimkov, V. E.; Coeurjolly, D.; Klette, R., Digital planarity—a review, Discrete Appl. Math., 155, 4, 468-495 (2007) ·Zbl 1109.68122 |
| [12] | Carr, H., Topological Manipulation of Isosurfaces (2004), The University of British Columbia: The University of British Columbia Canada, PhD thesis |
| [13] | Chandru, V.; Manohar, S.; Prakash, C. E., Voxel-based modeling for layered manufacturing, IEEE Comput. Graph. Appl., 15, 6, 42-47 (1995) |
| [14] | Chang, H.; Lai, Y.; Yao, C.; Hua, K.; Niu, Y.; Liu, F., Geometry-shader-based real-time voxelization and applications, Vis. Comput., 30, 3, 327-340 (2014) |
| [15] | Coeurjolly, D.; Miguet, S.; Tougne, L., 2D and 3D visibility in discrete geometry: an application to discrete geodesic paths, Pattern Recognit. Lett., 25, 5, 561-570 (2004) |
| [16] | Cohen-Or, D.; Kaufman, A., Fundamentals of surface voxelization, Graph. Models Image Process., 57, 6, 453-461 (1995) |
| [17] | Dachille, F.; Kaufman, A. E., Incremental triangle voxelization, (Graphics Interface Conference (2000)), 205-212 |
| [18] | J. DeSimone, A. Ermoshkin, E. Samulski, Method and apparatus for three-dimensional fabrication, US Patent App. 14154700, 2014.; J. DeSimone, A. Ermoshkin, E. Samulski, Method and apparatus for three-dimensional fabrication, US Patent App. 14154700, 2014. |
| [19] | Díaz, R. G.; Jiménez, M. J.; Medrano, B.; Real, P., A graph-with-loop structure for a topological representation of 3D objects, (12th Int. Conf. Computer Analysis of Images and Patterns. 12th Int. Conf. Computer Analysis of Images and Patterns, Lecture Notes in Computer Science, vol. 4673 (2007), Springer), 506-513 |
| [20] | Dionne, O.; de Lasa, M., Geodesic binding for degenerate character geometry using sparse voxelization, IEEE Trans. Vis. Comput. Graph., 20, 10, 1367-1378 (2014) |
| [21] | Dong, Z.; Chen, W.; Bao, H.; Zhang, H.; Peng, Q., Real-time voxelization for complex polygonal models, (12th Pacific Conf. Computer Graphics and Applications (2004), IEEE), 43-50 |
| [22] | Edelsbrunner, H.; Harer, J., Computational Topology: An Introduction (2013), American Mathematical Society |
| [23] | Edelsbrunner, H.; Harer, J.; Mascarenhas, A.; Pascucci, V., Time-varying Reeb graphs for continuous space-time data, (29th Annual Symposium on Computational Geometry (2004), ACM), 366-372 ·Zbl 1377.68271 |
| [24] | Eisemann, E.; Décoret, X., Single-pass GPU solid voxelization for real-time applications, (Graphics Interface (2008)), 73-80 |
| [25] | Fang, S.; Chen, H., Hardware accelerated voxelization, Comput. Graph., 24, 3, 433-442 (2000) |
| [26] | Hilaga, M.; Shinagawa, Y.; Kohmura, T.; Kunii, T. L., Topology matching for fully automatic similarity estimation of 3D shapes, (28th Annual Conf. Computer Graphics and Interactive Techniques. 28th Annual Conf. Computer Graphics and Interactive Techniques, SIGGRAPH (2001)), 203-212 |
| [27] | Hiller, J.; Lipson, H., Design and analysis of digital materials for physical 3D voxel printing, Rapid Prototyping J., 15, 2, 137-149 (2009) |
| [28] | Hiller, J.; Lipson, H., Tunable digital material properties for 3D voxel printers, Rapid Prototyping J., 16, 4, 241-247 (2010) |
| [29] | C. Hull, Apparatus for production of three-dimensional objects by stereolithography, US Patent 4575330, 1986.; C. Hull, Apparatus for production of three-dimensional objects by stereolithography, US Patent 4575330, 1986. |
| [30] | Jee, H.; Sachs, E., A visual simulation technique for 3D printing, Adv. Eng. Softw., 31, 2, 97-106 (2000) |
| [31] | Kamrani, A.; Nasr, E., Engineering Design and Rapid Prototyping (2009), Springer: Springer Boston, USA |
| [32] | Karabassi, E.-A.; Papaioannou, G.; Theoharis, T., A fast depth-buffer-based voxelization algorithm, J. Graph. Tools, 4, 4, 5-10 (1999) |
| [33] | Karmakar, N.; Bhowmick, P.; Biswas, A., Segmentation of 3D articulated components by slice-based vertex-weighted Reeb graph, (18th Int. Conf. Discrete geometry for Computer Imagery. 18th Int. Conf. Discrete geometry for Computer Imagery, Lecture Notes in Computer Science, vol. 8668 (2014), Springer), 370-383 ·Zbl 1417.68264 |
| [34] | Karmakar, N.; Biswas, A.; Bhowmick, P., Reeb graph based segmentation of articulated components of 3D digital objects, Theor. Comput. Sci., 624, 25-40 (2016) ·Zbl 1338.68264 |
| [35] | Klette, R.; Rosenfeld, A., Digital Geometry: Geometric Methods for Digital Picture Analysis (2004), Morgan Kaufmann: Morgan Kaufmann San Francisco ·Zbl 1064.68090 |
| [36] | Liao, D., GPU-accelerated multi-valued solid voxelization by slice functions in real time, (ACM 24th Spring Conf. Computer Graphics (2008)), 113-120 |
| [37] | Malgouyres, R., A discrete radiosity method, (10th Int. Conf. Discrete Geometry for Computer Imagery (2002)), 428-438 ·Zbl 1055.68615 |
| [38] | McLaughlin, K.; Edelsbrunner, H.; Harer, J.; Natarajan, V.; Pascucci, V., Loops in Reeb graphs of 2-manifolds, (19th Annual Symposium on Computational Geometry (2003)), 344-350 ·Zbl 1379.57025 |
| [39] | Milnor, J., Morse Theory (1963), Princeton University Press: Princeton University Press New Jersey ·Zbl 0108.10401 |
| [40] | Mitchell, J.; Mount, D.; Papadimitriou, C., The discrete geodesic problem, SIAM J. Comput., 16, 4, 647-668 (1987) ·Zbl 0625.68051 |
| [41] | Mukhopadhyay, J.; Das, P. P.; Chattopadhyay, S.; Bhowmick, P.; Chatterji, B. N., Digital Geometry in Image Processing (2013), CRC Press: CRC Press Boca Ration, UK ·Zbl 1278.68020 |
| [42] | Nanya, T.; Yoshihara, H.; Maekawa, T., Reconstruction of complete 3D models by voxel integration, J. Adv. Mech. Des. Syst. Manuf., 7, 3, 362-376 (2013) |
| [43] | Nooruddin, F. S.; Turk, G., Simplification and repair of polygonal models using volumetric techniques, IEEE Trans. Vis. Comput. Graph., 9, 2, 191-205 (2003) |
| [44] | I. Pomerantz, J. Cohen-Sabban, A. Bieber, J. Kamir, M. Katz, M. Nagler, Apparatus for production of three-dimensional objects by stereolithography, US Patent 4961154, 1990.; I. Pomerantz, J. Cohen-Sabban, A. Bieber, J. Kamir, M. Katz, M. Nagler, Apparatus for production of three-dimensional objects by stereolithography, US Patent 4961154, 1990. |
| [45] | Prakash, C. E.; Manohar, S., Volume rendering of unstructured grids—a voxelization approach, Comput. Graph., 19, 5, 711-726 (1995) |
| [46] | Qin, Y.; Han, X.; Yu, H.; Yu, Y.; Zhang, J., Fast and exact discrete geodesic computation based on triangle-oriented wavefront propagation, ACM Trans. Graph., 35, 4, 125:1-125:13 (2016) |
| [47] | Shinagawa, Y.; Kunii, T. L., Constructing a Reeb graph automatically from cross sections, IEEE Comput. Graph. Appl., 11, 6, 44-51 (1991) |
| [48] | R. Steingart, C. Robert, D. Tzu-Wei, Fabrication of non-homogeneous articles via additive manufacturing using three-dimensional voxel-based models, US Patent 8509933, 2013.; R. Steingart, C. Robert, D. Tzu-Wei, Fabrication of non-homogeneous articles via additive manufacturing using three-dimensional voxel-based models, US Patent 8509933, 2013. |
| [49] | Surazhsky, V.; Surazhsky, T.; Kirsanov, D.; Gortler, S. J.; Hoppe, H., Fast exact and approximate geodesics on meshes, ACM Trans. Graph., 24, 3, 553-560 (2005) |
| [50] | Tierny, J.; Vandeborre, J.-P.; Daoudi, M., Invariant high level Reeb graphs of 3D polygonal meshes, (3rd Int. Symposium on 3D Data Processing, Visualization, and Transmission (2006), IEEE), 105-112 |
| [51] | Truong-Hong, L.; Laefer, D. F.; Hinks, T.; Carr, H., Combining an angle criterion with voxelization and the flying voxel method in reconstructing building models from LiDAR data, Comput.-Aided Civ. Infrastruct. Eng., 28, 2, 112-129 (2013) |
| [52] | Wood, Z.; Hoppe, H.; Desbrun, M.; Schröder, P., Removing excess topology from isosurfaces, ACM Trans. Graph., 23, 2, 190-208 (2004) |
| [53] | Xin, S.-Q.; Wang, G.-J., Improving Chen and Han’s algorithm on the discrete geodesic problem, ACM Trans. Graph., 28, 4, 104:1-104:8 (2009) |
| [54] | Xin, S.-Q.; Ying, X.; He, Y., Constant-time all-pairs geodesic distance query on triangle meshes, (ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games (2012)), 31-38 |
| [55] | Ying, X.; Wang, X.; He, Y., Saddle vertex graph (SVG): a novel solution to the discrete geodesic problem, ACM Trans. Graph., 32, 6, 170:1-170:12 (2013) |
| [56] | Zhang, Z.; Morishima, S., Application friendly voxelization on GPU by geometry splitting, (Int. Symposium on Smart Graphics. Int. Symposium on Smart Graphics, Lecture Notes in Computer Science, vol. 8698 (2014), Springer), 112-120 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
