DIG: discrete iso-contour geodesics for topological analysis of voxelized objects.(English)Zbl 1339.68254
Bac, Alexandra (ed.) et al., Computational topology in image context. 6th international workshop, CTIC 2016, Marseille, France, June 15–17, 2016. Proceedings. Cham: Springer (ISBN 978-3-319-39440-4/pbk; 978-3-319-39441-1/ebook). Lecture Notes in Computer Science 9667, 265-276 (2016).
Summary: Discretized volumes and surfaces – used today in many areas of science and engineering – are approximated from the real objects in a particular theoretical framework. After a discretization produces a triangle mesh (2-manifold surface), a well-formed voxel set can be prepared from the mesh by voxelization of its constituent triangles based on some digitization principle. Since there exist different topological models of digital plane, choosing the appropriate model to meet the desired requirement appears to be of paramount importance. We introduce here the concept of discrete iso-contour geodesics (DIG) and show how they can be constructed on a voxelized surface with the assurance of certain topological requirements, when the voxelization conforms to the naive model with judicious inclusion of Steiner voxels from the graceful model, as and when needed. We also show some preliminary results on its practical application towards extraction of high-level topological features of 3D objects, which can subsequently be used for various shape-analytic applications.
For the entire collection see [Zbl 1337.68003].
For the entire collection see [Zbl 1337.68003].
MSC:
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
Cite
Full Text:DOI
References:
| [1] | Balasubramanian, M., Polimeni, J.R., Schwartz, E.L.: Exact geodesics and shortest paths on polyhedral surfaces. IEEE TPAMI 31, 1006–1016 (2009) ·doi:10.1109/TPAMI.2008.213 |
| [2] | Biswas, R., Bhowmick, P.: On different topological classes of spherical geodesic paths and circles in \[{\mathbb{{Z}}}^3\] Z 3 . Theoret. Comput. Sci. 605, 146–163 (2015) ·Zbl 1337.53048 ·doi:10.1016/j.tcs.2015.09.003 |
| [3] | Brimkov, V.E.: Formulas for the number of \[(n-2)\] ( n - 2 ) -gaps of binary objects in arbitrary dimension. Discrete Appl. Math. 157, 452–463 (2009) ·Zbl 1168.68048 ·doi:10.1016/j.dam.2008.05.025 |
| [4] | Brimkov, V.E., Barneva, R.P.: Graceful planes and lines. Theoret. Comput. Sci. 283, 151–170 (2002) ·Zbl 1050.68147 ·doi:10.1016/S0304-3975(01)00061-5 |
| [5] | Brimkov, V.E., Coeurjolly, D., Klette, R.: Digital planarity–a review. Discrete Appl. Math. 155, 468–495 (2007) ·Zbl 1109.68122 ·doi:10.1016/j.dam.2006.08.004 |
| [6] | Chandru, V., Manohar, S., Prakash, C.E.: Voxel-based modeling for layered manufacturing. IEEE Comput. Graph. App. 15, 42–47 (1995) ·doi:10.1109/38.469516 |
| [7] | Chang, H.H., Lai, Y.C., Yao, C.Y., Hua, K.L., Niu, Y., Liu, F.: Geometry-shader-based real-time voxelization and applications. Vis. Comput. 30, 327–340 (2014) ·doi:10.1007/s00371-013-0858-5 |
| [8] | Coeurjolly, D., Miguet, S., Tougne, L.: 2D and 3D visibility in discrete geometry: an application to discrete geodesic paths. PRL 25, 561–570 (2004) ·doi:10.1016/j.patrec.2003.12.002 |
| [9] | Cohen-Or, D., Kaufman, A.: Fundamentals of surface voxelization. Graph. Models Image Process. 57, 453–461 (1995) ·doi:10.1006/gmip.1995.1039 |
| [10] | Dachille, F., Kaufman, A.E.: Incremental triangle voxelization. In: Graphics Interface Conference, pp. 205–212 (2000) |
| [11] | Desimone, J.M., Ermoshkin, A., Samulski, E.T.: Method and apparatus for three-dimensional fabrication. US Patent 20140361463 (2014) |
| [12] | Dionne, O., de Lasa, M.: Geodesic binding for degenerate character geometry using sparse voxelization. IEEE TVCG 20, 1367–1378 (2014) |
| [13] | Dong, Z., Chen, W., Bao, H., Zhang, H., Peng, Q.: Real-time voxelization for complex polygonal models. In: PG 2004, pp. 43–50 (2004) |
| [14] | Edelsbrunner, H., Harer, J.L.: Computational Topology. American Mathematical Society, Providence (2009) ·Zbl 1193.55001 ·doi:10.1090/mbk/069 |
| [15] | Eisemann, E., Décoret, X.: Single-pass GPU solid voxelization for real-time applications. In: GI 2008, pp. 73–80 (2008) |
| [16] | Fang, S., Fang, S., Chen, H., Chen, H.: Hardware accelerated voxelization. Comput. Graph. 24, 433–442 (2000) ·doi:10.1016/S0097-8493(00)00038-8 |
| [17] | Hiller, J., Lipson, H.: Design and analysis of digital materials for physical 3D voxel printing. Rapid Prototyping J. 15, 137–149 (2009) ·doi:10.1108/13552540910943441 |
| [18] | Hiller, J., Lipson, H.: Tunable digital material properties for 3D voxel printers. Rapid Prototyping J. 16, 241–247 (2010) ·doi:10.1108/13552541011049252 |
| [19] | Hull, C.: Apparatus for production of three-dimensional objects by stereolithography. US Patent 4575330 (1986) |
| [20] | Jee, H.J., Sachs, E.: A visual simulation technique for 3D printing. Adv. Eng. Softw. 31, 97–106 (2000) ·doi:10.1016/S0965-9978(99)00045-9 |
| [21] | Kamrani, A.K., Nasr, E.A.: Engineering Design and Rapid Prototyping. Springer, Boston (2009) |
| [22] | Karabassi, E.A., Papaioannou, G., Theoharis, T.: A fast depth-buffer-based voxelization algorithm. J. Graph. Tools 4(4), 5–10 (1999) ·doi:10.1080/10867651.1999.10487510 |
| [23] | Klette, R., Rosenfeld, A.: Digital Geometry: Geometric Methods for Digital Picture Analysis. Morgan Kaufmann, San Francisco (2004) ·Zbl 1064.68090 |
| [24] | Liao, D.: GPU-accelerated multi-valued solid voxelization by slice functions in real time. In: VRCAI 2008, pp. 18:1–18:6 (2008) ·doi:10.1145/1477862.1477886 |
| [25] | Malgouyres, R.: A discrete radiosity method. In: Braquelaire, A., Lachaud, J.-O., Vialard, A. (eds.) DGCI 2002. LNCS, vol. 2301, p. 428. Springer, Heidelberg (2002) ·Zbl 1055.68615 ·doi:10.1007/3-540-45986-3_38 |
| [26] | Mitchell, J.S.B., Mount, D.M., Papadimitriou, C.H.: The discrete geodesic problem. SIAM J. Comput. 16, 647–668 (1987) ·Zbl 0625.68051 ·doi:10.1137/0216045 |
| [27] | Mukhopadhyay, J., Das, P.P., Chattopadhyay, S., Bhowmick, P., Chatterji, B.N.: Digital Geometry in Image Processing. CRC, Boca Ration (2013) ·Zbl 1278.68020 |
| [28] | Nanya, T., Yoshihara, H., Maekawa, T.: Reconstruction of complete 3D models by voxel integration. J. Adv. Mech. Des. Syst. Manuf. 7, 362–376 (2013) ·doi:10.1299/jamdsm.7.362 |
| [29] | Nooruddin, F.S., Turk, G.: Simplification and repair of polygonal models using volumetric techniques. IEEE TVCG 9, 191–205 (2003) |
| [30] | Pomerantz, I., Cohen-Sabban, J., Bieber, A., Kamir, J., Katz, M., Nagler, M.: Three dimensional modelling apparatus. US Patent 4961154 (1990) |
| [31] | Prakash, C., Manohar, S.: Volume rendering of unstructured grids–a voxelization approach. Comput. Graph. 19, 711–726 (1995) ·doi:10.1016/0097-8493(95)00053-4 |
| [32] | Steingart, Robert, C., Tzu-Wei, D.: Fabrication of non-homogeneous articles via additive manufacturing using three-dimensional voxel-based models. US Patent 8509933 (2013) |
| [33] | Surazhsky, V., Surazhsky, T., Kirsanov, D., Gortler, S.J., Hoppe, H.: Fast exact and approximate geodesics on meshes. ACM TOG 24, 553–560 (2005) ·doi:10.1145/1073204.1073228 |
| [34] | 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, 112–129 (2013) ·doi:10.1111/j.1467-8667.2012.00761.x |
| [35] | Xin, S.Q., Wang, G.J.: Improving Chen and Han’s algorithm on the discrete geodesic problem. ACM TOG 28, 104:1–104:8 (2009) |
| [36] | Xin, S.Q., Ying, X., He, Y.: Constant-time all-pairs geodesic distance query on triangle meshes. In: I3D 2012, pp. 31–38 (2012) ·doi:10.1145/2159616.2159622 |
| [37] | Ying, X., Wang, X., He, Y.: Saddle vertex graph (SVG): a novel solution to the discrete geodesic problem. ACM TOG 32, 170:1–170:12 (2013) ·doi:10.1145/2508363.2508379 |
| [38] | Zhang, Z., Morishima, S.: Application friendly voxelization on GPU by geometry splitting. In: Christie, M., Li, T.-Y. (eds.) SG 2014. LNCS, vol. 8698, pp. 112–120. Springer, Heidelberg (2014) |
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.
