On efficient computation of inter-simplex Chebyshev distance for voxelization of 2-manifold surface.(English)Zbl 1451.68299
Summary: Determining an appropriate voxel size is the foremost step for topology-aware voxelization of a 2-manifold surface. In this paper, we show how this is related to computation of inter-simplex Chebyshev distance (ICD) and how this computation is efficiently doable using a hierarchical decomposition of ICD function for higher-order simplices to that of lower-order ones. A novel idea of partitioning the manifold surface based on functional components is used alongside to reduce the number of distance computations. Geometric data structures and efficient query algorithms are also used to speed up the computation further. Detailed experimental results have been furnished to demonstrate its merit and aptness.
MSC:
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
Keywords:
digital geometry;digital line;digital triangle;discretization;Chebyshev distance;manifolds;voxelizationCite
Full Text:DOI
References:
| [1] | Bhunre, P. K.; Bhowmick, P.; Mukhopadhyay, J., On characterization and decomposition of isothetic distance function for 2-manifold surface, Proceedings of the 18th International Workshop of Combinatorial Image Analysis (IWCIA). Proceedings of the 18th International Workshop of Combinatorial Image Analysis (IWCIA), Lecture Notes in Computer Science, 10256, 212-225 (2017), Springer ·Zbl 1486.68203 |
| [2] | Chandru, V.; Manohar, S.; Prakash, C. E., Voxel-based modeling for layered manufacturing, IEEE Comput. Graph. Appl., 15, 6, 42-47 (1995) |
| [3] | Cohen-Or, D.; Kaufman, A., Fundamentals of surface voxelization, Graph. Models Image Process., 57, 6, 453-461 (1995) |
| [4] | Huang, J.; Yagel, R.; Filippov, V.; Kurzion, Y., An accurate method for voxelizing polygon meshes, Proceedings of the IEEE Symposium on Volume Visualization. Proceedings of the IEEE Symposium on Volume Visualization, VVS, 119-126 (1998) |
| [5] | Karabassi, E.-A.; Papaioannou, G.; Theoharis, T., A fast depth-buffer-based voxelization algorithm, J. Graph. Tools, 4, 4, 5-10 (1999) |
| [6] | Prakash, C.; Manohar, S., Volume rendering of unstructured grids—a voxelization approach, Comput. Graph., 19, 5, 711-726 (1995) |
| [7] | Fei, Y.; Wang, B.; Chen, J., Point-tessellated voxelization, Proceedings of the Graphics Interface. Proceedings of the Graphics Interface, GI, 9-18 (2012) |
| [8] | Laine, S., A topological approach to voxelization, Comput. Graph. Forum, 32, 4, 77-86 (2013) |
| [9] | S. Laine, System, method, and computer program product implementing an algorithm for performing thin voxelization of a three-dimensional model, 2016, US Patent 9,245,363.; S. Laine, System, method, and computer program product implementing an algorithm for performing thin voxelization of a three-dimensional model, 2016, US Patent 9,245,363. |
| [10] | Pantaleoni, J., VoxelPipe: A programmable pipeline for 3D voxelization, Proceedings of the ACM SIGGRAPH Symposium on High Performance Graphics. Proceedings of the ACM SIGGRAPH Symposium on High Performance Graphics, HPG, 99-106 (2011) |
| [11] | Schwarz, M.; Seidel, H.-P., Fast parallel surface and solid voxelization on GPUs, ACM Trans. Graph., 29, 6, 179:1-179:10 (2010) |
| [12] | Zhang, J., Speeding up large-scale geospatial polygon rasterization on GPGPUs, Proceedings of the ACM SIGSPATIAL Second International Workshop on High Performance and Distributed Geographic Information Systems. Proceedings of the ACM SIGSPATIAL Second International Workshop on High Performance and Distributed Geographic Information Systems, HPDGIS, 10-17 (2011) |
| [13] | Zhang, X.; Stockel, J.; Wolf, M.; Cathier, P.; McLennan, G.; Hoffman, E.; Sonka, M., A new method for spherical object detection and its application to computer aided detection of pulmonary nodules in CT images, (Ayache, N.; Ourselin, S.; Maeder, A., Medical Image Computing and Computer-Assisted Intervention (MICCAI 2007) (2007), Springer Berlin Heidelberg), 842-849 |
| [14] | Niebner, M.; Zollhöfer, M.; Izadi, S.; Stamminger, M., Real-time 3d reconstruction at scale using voxel hashing, ACM Trans. Graph., 32, 6, 169:1-169:11 (2013) |
| [16] | Brunton, A.; Arikan, C. A.; Urban, P., Pushing the limits of 3d color printing: error diffusion with translucent materials, ACM Trans. Graph., 35, 1, 4:1-4:13 (2015) |
| [17] | Chen, X.; Zhang, H.; Lin, J.; Hu, R.; Lu, L.; Huang, Q.; Benes, B.; Cohen-Or, D.; Chen, B., Dapper: decompose-and-pack for 3D printing, ACM Trans. Graph., 34, 6, 213:1-213:12 (2015) |
| [18] | J.M. Desimone, A. Ermoshkin, E.T. Samulski, Method and apparatus for three-dimensional fabrication, 2014, (US Patent 20140361463).; J.M. Desimone, A. Ermoshkin, E.T. Samulski, Method and apparatus for three-dimensional fabrication, 2014, (US Patent 20140361463). |
| [19] | Vidimče, K.; Wang, S.-P.; Ragan-Kelley, J.; Matusik, W., Openfab: a programmable pipeline for multi-material fabrication, ACM Trans. Graph., 32, 4, 136:1-136:12 (2013) |
| [20] | Wu, J.; Dick, C.; Westermann, R., A system for high-resolution topology optimization, IEEE Trans. Vis. Comput. Graph., 22, 3, 1195-1208 (2016) |
| [21] | Zhou, Y.; Sueda, S.; Matusik, W.; Shamir, A., Boxelization: folding 3D objects into boxes, ACM Trans. Graph., 33, 4, 71:1-71:8 (2014) |
| [22] | Koa, M. D.; Johan, H., ESLPV: Enhanced subsurface light propagation volumes, Vis. Comput., 30, 6, 821-831 (2014) |
| [23] | Laine, S.; Karras, T., Efficient sparse voxel octrees, Proceedings of the ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games. Proceedings of the ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games, I3D, 55-63 (2010) |
| [24] | Kämpe, V.; Sintorn, E.; Assarsson, U., High resolution sparse voxel DAGs, ACM Trans. Graph., 32, 4, 101:1-101:13 (2013) ·Zbl 1305.68245 |
| [25] | Sintorn, E.; Kämpe, V.; Olsson, O.; Assarsson, U., Compact precomputed voxelized shadows, ACM Trans. Graph., 33, 4, 150:1-150:8 (2014) |
| [27] | Dumas, J.; Lu, A.; Lefebvre, S.; Wu, J.; Dick, C., By-example synthesis of structurally sound patterns, ACM Trans. Graph., 34, 4, 137:1-137:12 (2015) |
| [28] | Zhao, S.; Hašan, M.; Ramamoorthi, R.; Bala, K., Modular flux transfer: efficient rendering of high-resolution volumes with repeated structures, ACM Trans. Graph., 32, 4, 131:1-131:12 (2013) ·Zbl 1305.68293 |
| [29] | Dionne, O.; de Lasa, M., Geodesic voxel binding for production character meshes, Proceedings of the 12th ACM SIGGRAPH/Eurographics Symposium on Computer Animation. Proceedings of the 12th ACM SIGGRAPH/Eurographics Symposium on Computer Animation, SCA, 173-180 (2013) |
| [30] | Lozano-Durán, A.; Borrell, G., Algorithm 964: an efficient algorithm to compute the genus of discrete surfaces and applications to turbulent flows, ACM Trans. Math. Softw., 42, 4, 34:1-34:19 (2016) ·Zbl 1369.65033 |
| [31] | Lachaud, J.; Thibert, B., Properties of gauss digitized shapes and digital surface integration, J. Math. Imaging Vis., 54, 2, 162-180 (2016) ·Zbl 1338.65060 |
| [32] | Stelldinger, P.; Latecki, L. J.; Siqueira, M., Topological equivalence between a 3d object and the reconstruction of its digital image, IEEE Trans. Pattern Anal. Mach. Intell., 29, 1, 126-140 (2007) |
| [33] | Toutant, J.; Andres, E.; Largeteau-Skapin, G.; Zrour, R., Implicit digital surfaces in arbitrary dimensions, Proceedings of the DGCI. Proceedings of the DGCI, Lecture Notes in Computer Science, 8668, 332-343 (2014), Springer ·Zbl 1417.68253 |
| [34] | Klette, R.; Rosenfeld, A., Digital Geometry: Geometric Methods for Digital Picture Analysis (2004), Morgan Kaufmann: Morgan Kaufmann San Francisco ·Zbl 1064.68090 |
| [35] | Brimkov, V. E.; Barneva, R. P., Plane digitization and related combinatorial problems, Discrete Appl. Math., 147, 2-3, 169-186 (2005) ·Zbl 1068.68111 |
| [36] | Brimkov, V. E.; Coeurjolly, D.; Klette, R., Digital planarity—a review, Discrete Appl. Math., 155, 4, 468-495 (2007) ·Zbl 1109.68122 |
| [37] | 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 |
| [38] | P.K. Bhunre and P. Bhowmick, Topological analysis of voxelized objects by using discrete geodesic Reeb graph, J. Computer & System Sciences, https://doi.org/10.1016/j.jcss.2017.09.002; P.K. Bhunre and P. Bhowmick, Topological analysis of voxelized objects by using discrete geodesic Reeb graph, J. Computer & System Sciences, https://doi.org/10.1016/j.jcss.2017.09.002 ·Zbl 1390.68708 |
| [39] | de Berg, M.; Cheong, O.; van Kreveld, M.; Overmars, M., Computational Geometry: Algorithms and Applications (2008), Springer ·Zbl 1140.68069 |
| [40] | Latecki, L. J., 3D well-composed pictures, CVGIP Graph. Model Image Process., 59, 3, 164-172 (1997) |
| [41] | Boutry, N.; Géraud, T.; Najman, L., How to make nD images well-composed without interpolation, Proceedings of the IEEE International Conference on Image Processing (ICIP), 2149-2153 (2015) |
| [42] | González-Díaz, R.; Jiménez, M. J.; Medrano, B., 3D Well-composed polyhedral complexes, Discrete Appl. Math., 183, 59-77 (2015) ·Zbl 1319.68229 |
| [44] | Stelldinger, P.; Köthe, U., Towards a general sampling theory for shape preservation, Image Vis. Comput., 23, 23:237-248 (2005) |
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.
