A combinatorial algorithm to construct 3D isothetic covers.(English)Zbl 1276.68160
Summary: Three-dimensional (3D) isothetic outer (inner) cover of a digital object is a 3D polytope of minimum (maximum) volume defined w.r.t. an underlying grid, having surfaces parallel to the coordinate planes, and circumscribing (inscribing) the entire object. It is useful for a unique approximation of 3D objects and to obtain shape-related information. We propose here a combinatorial algorithm for construction of such outer and inner covers of a 3D object imposed on the background grid. The algorithm consists of two passes. In the first pass, the unit faces on the surface of the cover are detected and stored in a doubly connected edge list (DCEL). In the second pass, an efficient merging of contiguous and coplanar unit faces from the DCEL produces a compact representation of the cover. The accuracy of the cover can be adjusted by changing the face planes, whether placed uniformly or non-uniformly. Experimental results demonstrate the effectiveness of the algorithm.
MSC:
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
| 65D18 | Numerical aspects of computer graphics, image analysis, and computational geometry |
| 68U10 | Computing methodologies for image processing |
Keywords:
object approximation;object representation;isothetic cover;isothetic polytope;shape analysisSoftware:
OpenGLCite
Full Text:DOI
References:
| [1] | Aguilera, A. 1998. ”Isothetic polyhedra: Study and application”. Universitat Politécnica de Catalunya. Ph.D. thesis |
| [2] | Beckwith O., Discrete Comput. Geom. |
| [3] | DOI: 10.1016/S0925-7721(03)00048-8 ·Zbl 1044.65016 ·doi:10.1016/S0925-7721(03)00048-8 |
| [4] | Berg M. D., Computational Geometry: Algorithms and Applications (1997) ·Zbl 0877.68001 |
| [5] | Bhaniramka P., Proceedings of the Visualization, Salt Lake City, Utah pp 267– (2000) |
| [6] | DOI: 10.1109/TVCG.2004.1260765 ·doi:10.1109/TVCG.2004.1260765 |
| [7] | Biswas, A., Bhowmick, P. and Bhattacharya, B. B. TIPS: On finding a tight isothetic polygonal shape covering a 2D object. Proceedings of the 14th Scandinavian Conference on Image Analysis, Joensuu, Finland. Edited by: Kalviainen, H., Parkkinen, J. and Kaarna, A. Vol. 3540, pp.930–939. Berlin, Hiedelberg: Springer-Verlag. LNCS |
| [8] | DOI: 10.1016/j.jvcir.2010.02.001 ·doi:10.1016/j.jvcir.2010.02.001 |
| [9] | Brimkov, V. E. Discrete volume polyhedrization: Complexity and bounds on performance. Computational Methodology of Objects Represented in Images: Fundamentals, Methods and Applications, Proceedings of the International Symposium CompIMAGE ’06. Coimbra, Portugal. Edited by: Tavares, J. M.R.S. and Jorge, R. M.N. pp.117–122. London: Taylor and Francis. |
| [10] | DOI: 10.1016/j.patcog.2008.12.002 ·Zbl 1182.68330 ·doi:10.1016/j.patcog.2008.12.002 |
| [11] | Charrier, E. and Lachaud, J. Maximal planes and multiscale tangential cover of 3D digital objects. Proceedings of the 14th International Workshop on Combinatorial Image Analysis (IWCIA’11). Madrid, Spain. Edited by: Aggarwal, J. K., Barneva, R. P., Brimkov, V. E., Koroutchev, K. N. and Korutcheva, E. R. pp.132–143. Berlin, Heidelberg: Springer-Verlag. |
| [12] | DOI: 10.1117/12.525391 ·doi:10.1117/12.525391 |
| [13] | DOI: 10.1145/322139.322141 ·Zbl 0403.68067 ·doi:10.1145/322139.322141 |
| [14] | DOI: 10.1007/s00371-007-0197-5 ·doi:10.1007/s00371-007-0197-5 |
| [15] | Cormen T. H., Introduction to Algorithms (1990) ·Zbl 1158.68538 |
| [16] | Demaine, E. D. and Schulz, A. Embedding stacked polytopes on a polynomial-size grid. Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’11). San Francisco. pp.1177–1187. Philadelphia: Society of Industrial and Applied Mathematics. ·Zbl 1372.52019 |
| [17] | DOI: 10.1016/0956-0521(90)90047-O ·doi:10.1016/0956-0521(90)90047-O |
| [18] | Golovinskiy A., ACM Trans. Graph. (Proc. SIGGRAPH ASIA) 27, Article 145 (2008) |
| [19] | Gonzalez-Diaz, R., Lamar, J. and Umble, R. Cup products on polyhedral approximations of 3D digital images. Proceedings of the 14th International Workshop on Combinatorial Image Analysis: IWCIA’11. Madrid, Spain. Edited by: Aggarwal, J. K., Barneva, R. P., Brimkov, V. E., Koroutchev, K. N. and Korutcheva, E. R. pp.108–119. Berlin, Hiedelberg: Springer-Verlag. LNCS |
| [20] | Hearn D., Computer Graphics with OpenGL (2004) |
| [21] | Hill F. S., Computer Graphics Using OpenGL (2007) |
| [22] | Karmakar, N., Biswas, A., Bhowmick, P. and Bhattacharya, B. B. Construction of 3D orthogonal cover of a digital object. Proceedings of the 14th International Workshop on Combinatorial Image Analysis: IWCIA’11, LNCS. May23–25, Madrid, Spain. Edited by: Aggarwal, J. K., Barneva, R. P., Brimkov, V. E., Koroutchev, K. N. and Korutcheva, E. R. Vol. 6636, pp.70–83. Berlin, Hiedelberg: Springer-Verlag. |
| [23] | DOI: 10.1007/s00371-005-0344-9 ·doi:10.1007/s00371-005-0344-9 |
| [24] | DOI: 10.1016/j.jvcir.2005.11.001 ·doi:10.1016/j.jvcir.2005.11.001 |
| [25] | Klette R., Digital Geometry: Geometric Methods for Digital Picture Analysis (2004) |
| [26] | Li, F. and Klette, R. Approximate shortest paths in simple polyhedra. Proceedings of the 16th IAPR International Conference on Discrete Geometry for Computer Imagery (DGCI’11). Edited by: Debled-Rennesson, I., Domenjoud, E., Kerautret, B. and Even, P. pp.513–524. Berlin, Heidelberg: Springer-Verlag. |
| [27] | Linh, T. K. and Imiya, A. Reconstruction of Euclidean planes from voxels. Proceedings of the 3D Data Processing, Visualization, and Transmission, 2nd International Symposium (3DPVT ’04). pp.781–788. Washington, DC: IEEE Computer Society. |
| [28] | DOI: 10.1109/2945.489388 ·doi:10.1109/2945.489388 |
| [29] | DOI: 10.1145/37402.37422 ·doi:10.1145/37402.37422 |
| [30] | DOI: 10.1016/j.cag.2006.07.021 ·doi:10.1016/j.cag.2006.07.021 |
| [31] | DOI: 10.1007/978-1-4612-1098-6 ·doi:10.1007/978-1-4612-1098-6 |
| [32] | Schulz, H. Polyhedral surface approximation of non-convex voxel sets through the modification of convex hulls. Proceedings of the 12th International Workshop on Combinatorial Image Analysis (IWCIA’08). Edited by: Brimkov, V. E., Barneva, R. P. and Hauptman, H. A. pp.38–50. Berlin, Heidelberg: Springer-Verlag. |
| [33] | DOI: 10.1016/j.dam.2009.04.008 ·Zbl 1186.68510 ·doi:10.1016/j.dam.2009.04.008 |
| [34] | DOI: 10.1007/s11263-009-0279-0 ·doi:10.1007/s11263-009-0279-0 |
| [35] | DOI: 10.1111/1467-8659.00581 ·doi:10.1111/1467-8659.00581 |
| [36] | Shreiner, D., Woo, M., Neider, J. and Davis, T. 2004. ”OpenGL Programming Guide: The Official Guide to Learning OpenGL”. Version 1.4. Pearson Education, Singapore |
| [37] | Stelldinger, P. and Latecki, L. J. 3D object digitization: Topology preserving reconstruction. Proceedings of the 18th International Conference on Pattern Recognition. Vol. 3, pp.693–696. IEEE. ICPR |
| [38] | Stelldinger, P. and Strand, R. Topology preserving digitization with FCC and BCC grids. Proceedings of the 11th International Workshop on Combinatorial Image Analysis. Edited by: Reulke, R., Eckardt, U., Flach, B., Knauer, U. and Polthier, K. pp.226–240. Berlin: Springer-Verlag. |
| [39] | DOI: 10.1109/TPAMI.2007.250604 ·doi:10.1109/TPAMI.2007.250604 |
| [40] | Turk, G. and Levoy, M. Zippered polygon meshes from range images. Proceedings of the 21st Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH’94. pp.311–318. New York: ACM. |
| [41] | Weber, G., Kreylos, O., Ligocki, T., Shalf, J., Hagen, H., Hamann, B. and Joy, K. I. Extraction of crack-free isosurfaces from adaptive mesh refinement data. Proceedings of the Joint Eurographics – IEEE TCVG Symposium on Visualization EGVisSym’01. Ascona, Switzerland. Edited by: Ebert, D. S., Favre, J. M. and Peikert, R. pp.25–34. Aire-la-Ville, Switzerland: Eurographics Association. ·Zbl 1015.68230 |
| [42] | DOI: 10.1145/99308.99325 ·doi:10.1145/99308.99325 |
| [43] | DOI: 10.1016/1049-9660(92)90042-2 ·Zbl 0779.68096 ·doi:10.1016/1049-9660(92)90042-2 |
| [44] | DOI: 10.1142/S0218195997000168 ·doi:10.1142/S0218195997000168 |
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.
