A combinatorial algorithm to construct 3D isothetic covers

References

• Aguilera , A. 1998 . “ Isothetic polyhedra: Study and application ” . Universitat Politécnica de Catalunya . Ph.D. thesis
   Google Scholar
• Beckwith , O. , Grimm , M. , Soprunova , J. and Weaver , B. Minkowski length of 3D lattice polytopes . Discrete Comput. Geom. , in press, doi:10.1007/s00454-012-9433-5
   Web of Science ®Google Scholar
• Bemporad , A. , Filippi , C. and Torrisi , F. D. 2004 . Inner and outer approximations of polytopes using boxes . Comput. Geom. Theory Appl. , 27 : 151 – 178 . (doi:10.1016/S0925-7721(03)00048-8)
   Web of Science ®Google Scholar
• Berg , M. D. , Cheong , O. , Kreveld , M. V. and Overmars , M. 1997 . Computational Geometry: Algorithms and Applications , Berlin, Heidelberg : Springer-Verlag .
   Google Scholar
• Bhaniramka , P. , Wenger , R. and Crawfis , R. 2000 . “ Isosurfacing in higher dimensions ” . In Proceedings of the Visualization, Salt Lake City, Utah , 267 – 273 . Los Alamitos , CA : IEEE Computer Society Press .
   Google Scholar
• Bhaniramka , P. , Wenger , R. and Crawfis , R. 2004 . Isosurface construction in any dimension using convex hulls . IEEE Trans. Vis. Comput. Graph. , 10 : 130 – 141 . (doi:10.1109/TVCG.2004.1260765)
   PubMed Web of Science ®Google Scholar
• 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
   Google Scholar
• Biswas , A. , Bhowmick , P. and Bhattacharya , B. B. 2010 . Construction of isothetic covers of a digital object: A combinatorial approach . J. Vis. Commun. Image Represent. , 21 : 295 – 310 . (doi:10.1016/j.jvcir.2010.02.001)
   Web of Science ®Google Scholar
• 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 .
   Google Scholar
• Brimkov , V. E. 2009 . Digitization scheme that assures faithful reconstruction of plane figures . Pattern Recogn. , 42 ( 8 ) : 1637 – 1649 . (doi:10.1016/j.patcog.2008.12.002)
   Web of Science ®Google Scholar
• 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 .
   Google Scholar
• Coeurjolly , D. and Sivignon , I. 2004 . Reversible discrete volume polyhedrization using Marching Cubes simplification . SPIE Vision Geom. XII, , 5300 : 1 – 11 .
   Google Scholar
• Cohen , J. and Hickey , T. 1979 . Two algorithms for determining volumes of convex polyhedra . J. ACM , 26 ( 3 ) : 401 – 414 . (doi:10.1145/322139.322141)
   Web of Science ®Google Scholar
• Cohen-Or , D. , Shamir , A. and Shapira , L. 2008 . Consistent mesh partitioning and skeletonization using the shape diameter function . Vis. Comput. , 24 : 249 – 259 . (doi:10.1007/s00371-007-0197-5)
   Web of Science ®Google Scholar
• Cormen , T. H. , Leiserson , C. E. , Rivest , R. L. and Stein , C. 1990 . Introduction to Algorithms , England , , Toronto : The MIT Press, McGraw-Hill Book Company .
   Google Scholar
• 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 .
   Google Scholar
• Giles , M. and Haimes , R. 1990 . Advanced interactive visualization for CFD . Comput. Systems Eng. , 1 : 51 – 62 . (doi:10.1016/0956-0521(90)90047-O)
   Google Scholar
• Golovinskiy , A. and Funkhouser , T. 2008 . Randomized cuts for 3D mesh analysis . ACM Trans. Graph. (Proc. SIGGRAPH ASIA) 27, Article , 145
   Google Scholar
• 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
   Google Scholar
• Hearn , D. and Baker , M. P. 2004 . Computer Graphics with OpenGL , Upper Saddle River , NJ : Pearson Education Inc .
   Google Scholar
• Hill , F. S. and Kelley , S. M. 2007 . Computer Graphics Using OpenGL , Upper Saddle River , NJ : Pearson Education Inc .
   Google Scholar
• 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 . May 23–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 .
   Google Scholar
• Katz , S. , Leifman , G. and Tal , A. 2005 . Mesh segmentation using feature point and core extraction . Vis. Comput. , 21 : 649 – 658 . (doi:10.1007/s00371-005-0344-9)
   Web of Science ®Google Scholar
• Kenmochi , Y. and Imiya , A. 2006 . Combinatorial boundary of a 3D lattice point set . J. Vis. Commun. Image Represent. , 17 ( 4 ) : 738 – 766 . (doi:10.1016/j.jvcir.2005.11.001)
   Web of Science ®Google Scholar
• Klette , R. and Rosenfeld , A. 2004 . Digital Geometry: Geometric Methods for Digital Picture Analysis , San Francisco : Morgan Kaufmann .
   Google Scholar
• 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 .
   Google Scholar
• 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 .
   Google Scholar
• Livnat , Y. , Shen , H-W and Johnson , C. 1996 . A near optimal isosurface extraction algorithm using span space . IEEE Trans. Vis. Comput. Graph. , 2 : 73 – 84 . (doi:10.1109/2945.489388)
   Web of Science ®Google Scholar
• Lorensen , W. E. and Cline , H. E. 1987 . Marching cubes: A high resolution 3D surface construction algorithm . Comput. Graph. , 21 : 163 – 169 . (doi:10.1145/37402.37422)
   Google Scholar
• Newman , T. S. and Yi , H. 2006 . A survey of the marching cubes algorithm . Comput. Graph. , 30 : 854 – 879 . (doi:10.1016/j.cag.2006.07.021)
   Web of Science ®Google Scholar
• Preparata , F. P. and Shamos , M. I. 1985 . Computational Geometry: An Introduction , New York : Springer-Verlag .
   Google Scholar
• 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 .
   Google Scholar
• Schulz , H. 2009 . Polyhedral approximation and practical convex hull algorithm for certain classes of voxel sets . Discrete Appl. Math. , 157 ( 16 ) : 3485 – 3493 . (doi:10.1016/j.dam.2009.04.008)
   Web of Science ®Google Scholar
• Shapira , L. , Shalom , S. , Shamir , A. , Cohen-Or , D. and Zhang , H. 2010 . Contextual part analogies in 3D objects . Int. J. Comput. Vis. , 89 : 309 – 326 . (doi:10.1007/s11263-009-0279-0)
   Web of Science ®Google Scholar
• Shlafman , S. , Tal , A. and Katz , S. 2002 . Metamorphosis of polyhedral surfaces using decomposition . Comput. Graph. Forum , 21 ( 3 ) : 219 – 228 . (doi:10.1111/1467-8659.00581)
   Web of Science ®Google Scholar
• 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
   Google Scholar
• 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
   Google Scholar
• 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 .
   Google Scholar
• Stelldinger , P. , Latecki , L. J. and Siqueira , M. 2007 . Topological equivalence between a 3D object and the reconstruction of its digital image . IEEE Trans. Pattern Anal. Mach. Intell. , 29 ( 1 ) : 126 – 140 . (doi:10.1109/TPAMI.2007.250604)
   PubMed Web of Science ®Google Scholar
• 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 .
   Google Scholar
• 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 .
   Google Scholar
• Wilhelms , J. and van Gelder , A. 1990 . Topological considerations in isosurface generation, extended abstract . Comput. Graph. , 24 : 79 – 86 . (doi:10.1145/99308.99325)
   Google Scholar
• Yu , B. , Lin , X. , Wu , Y. and Yuan , B. 1992 . Isothetic polygon representation for contours . CVGIP: Image Underst. , 56 ( 2 ) : 264 – 268 . (doi:10.1016/1049-9660(92)90042-2)
   Google Scholar
• Zhu , B. 1997 . Approximating convex polyhedra with axis-parallel boxes . Int. J. Comput. Geom. Appl. , 7 ( 3 ) : 253 – 267 . (doi:10.1142/S0218195997000168)
   Web of Science ®Google Scholar