Construction of 3D orthogonal cover of a digital object.(English)Zbl 1330.68305
Aggarwal, Jake K. (ed.) et al., Combinatorial image analysis. 14th international workshop, IWCIA 2011, Madrid, Spain, May 23–25, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-21072-3/pbk). Lecture Notes in Computer Science 6636, 70-83 (2011).
Summary: The orthogonal cover of a 3D digital object is a minimum-volume 3D polytope having surfaces parallel to the coordinate planes, and containing the entire object so as to capture its approximate shape information. An efficient algorithm for construction of such an orthogonal cover imposed on a background grid is presented in this paper. A combinatorial technique is used to classify the grid faces constituting the polytope while traversing along the surface of the object in a breadth-first manner. The eligible grid faces are stored in a doubly connected edge list, using which the faces are finally merged to derive the isothetic polygons parallel to the coordinate planes, thereby obtaining the orthogonal cover of the object. The complexity of the cover decreases with increasing grid size. The algorithm requires computations in integer domain only and runs in a time linear in the number of voxels constituting the object surface. Experimental results demonstrate the effectiveness of the algorithm.
For the entire collection see [Zbl 1214.68004].
For the entire collection see [Zbl 1214.68004].
MSC:
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
| 68U10 | Computing methodologies for image processing |
Cite
Full Text:DOI
References:
| [1] | Berg, M.D., Cheong, O., Kreveld, M.V., Overmars, M.: Computational Geometry–Algorithms and Applications. Springer, Heidelberg (1997) |
| [2] | Bhaniramka, P., Wenger, R., Crawfis, R.: Isosurface construction in any dimension using convex hulls. IEEE Trans. on Visualization and Computer Graphics 10, 130–141 (2004) ·doi:10.1109/TVCG.2004.1260765 |
| [3] | Bhaniramka, P., Wenger, R., Crawfis, R.: Isosurfacing in higher dimensions. In: Proceedings of Visualization, Salt Lake City, pp. 267–273 (2000) ·doi:10.1109/VISUAL.2000.885704 |
| [4] | Biswas, A., Bhowmick, P., Bhattacharya, B.B.: Construction of Isothetic Covers of a Digital Object: A Combinatorial Approach. Journal of Visual Communication and Image Representation 21, 295–310 (2010) ·doi:10.1016/j.jvcir.2010.02.001 |
| [5] | Biswas, A., Bhowmick, P., Bhattacharya, B.B.: TIPS: On Finding a Tight Isothetic Polygonal Shape Covering a 2D Object. In: Kalviainen, H., Parkkinen, J., Kaarna, A. (eds.) SCIA 2005. LNCS, vol. 3540, pp. 930–939. Springer, Heidelberg (2005) ·doi:10.1007/11499145_94 |
| [6] | Brimkov, V.: Discrete volume polyhedrization: Complexity and bounds on performance. In: Proc. of the International Symposium on Computational Methodology of Objects Represented in Images: Fundamentals, Methods and Applications, CompIMAGE 2006, pp. 117–122. Taylor and Francis, Coimbra (2006) |
| [7] | Coeurjolly, D., Sivignon, I.: Reversible discrete volume polyhedrization using Marching Cubes simplification. In: SPIE Vision Geometry XII, vol. 5300, pp. 1–11 (2004) ·doi:10.1117/12.525391 |
| [8] | Cohen-Or, D., Shamir, A., Shapira, L.: Consistent Mesh Partitioning and Skeletonization using the Shape Diameter Function. The Visual Computer 24, 249–259 (2008) ·doi:10.1007/s00371-007-0197-5 |
| [9] | Giles, M., Haimes, R.: Advanced interactive visualization for CFD. Computing Systems in Engineering 1, 51–62 (1990) ·doi:10.1016/0956-0521(90)90047-O |
| [10] | Golovinskiy, A., Funkhouser, T.: Randomized cuts for 3D mesh analysis. ACM Transactions on Graphics (Proc. SIGGRAPH ASIA) 27, Article 145 (2008) |
| [11] | Hearn, D., Baker, M.P.: Computer Graphics with OpenGL. Pearson Education Inc., London (2004) |
| [12] | Hill, F.S., Kelley, S.M.: Computer Graphics Using OpenGL. Pearson Edcation Inc., London (2007) |
| [13] | Katz, S., Leifman, G., Tal, A.: Mesh segmentation using feature point and core extraction. The Visual Computer 21, 649–658 (2005) ·doi:10.1007/s00371-005-0344-9 |
| [14] | Klette, R., Rosenfeld, A.: Digital Geometry: Geometric Methods for Digital Picture Analysis. Morgan Kaufmann, San Francisco (2004) ·Zbl 1064.68090 |
| [15] | Livnat, Y., Shen, H.-W., Johnson, C.: A near optimal isosurface extraction algorithm using span space. IEEE Trans. Visualization and Computer Graphics 2, 73–84 (1996) ·doi:10.1109/2945.489388 |
| [16] | Lorensen, W.E., Cline, H.E.: Marching Cubes: A high resolution 3D surface construction algorithm. Computer Graphics 21, 163–169 (1987) ·doi:10.1145/37402.37422 |
| [17] | Newman, T.S., Yi, H.: A Survey of the Marching Cubes Algorithm. Computers & Graphics 30, 854–879 (2006) ·doi:10.1016/j.cag.2006.07.021 |
| [18] | Preparata, F.P., Shamos, M.I.: Computational Geometry–An Introduction. Spinger, New York (1985) ·Zbl 0575.68059 ·doi:10.1007/978-1-4612-1098-6 |
| [19] | Shapira, L., Shalom, S., Shamir, A., Cohen-Or, D., Zhang, H.: Contextual Part Analogies in 3D Objects. International Journal of Computer Vision 89, 309–326 (2010) ·doi:10.1007/s11263-009-0279-0 |
| [20] | Shlafman, S., Tal, A., Katz, S.: Metamorphosis of Polyhedral Surfaces using Decomposition. In: Eurographics 2002, pp. 219–228 (2002) |
| [21] | Turk, G., Levoy, M.: Zippered polygon meshes from range images. In: SIGGRAPH 1994, pp. 311–318 (1994) ·doi:10.1145/192161.192241 |
| [22] | Weber, G., Kreylos, O., Ligocki, T., Shalf, J., Hagen, H., Hamann, B.: Extraction of crack-free isosurfaces from adaptive mesh refinement data. In: Proceedings of VisSym 2001, Ascona, Switzerland, pp. 25–34 (2001) ·Zbl 1015.68230 ·doi:10.1007/978-3-7091-6215-6_4 |
| [23] | Wilhelms, J., van Gelder, A.: Topological considerations in isosurface generation extended abstract. Computers Graphics 24, 79–86 (1990) ·doi:10.1145/99308.99325 |
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.
