Yusuf SAHİLLİOĞLU

A marching algorithm for isosurface extraction from face-centered cubic lattices

This work provides a novel method that extracts isosurfaces from face-centered cubic (FCC) lattices. It has been theoretically shown that sampling volumetric data on an FCC lattice tiled with rhombic dodecahedra is more efficient than sampling them on a Cartesian lattice tiled with cubes, in that the FCC lattice can represent the same data set as a Cartesian lattice with the same accuracy, yet with approximately 23% fewer samples. This fact, coupled with the good properties of rhombic dodecahedra, encouraged us to develop this related isosurface extraction technique. Thanks to the sparser sampling required by the FCC lattices, the de facto standard isosurface extraction algorithm, namely marching cubes, is accelerated significantly, as demonstrated. This reduced sampling rate also leads to a decrement in the number of triangles of the extracted models when compared to the marching cubes result. Finally, the topological consistency problem of the original marching cubes algorithm is also resolved. We show the potential of our algorithm with an indirect volume-rendering application.

PDF

___

[1] Lorensen WE, Cline HE. Marching cubes: a high resolution 3D surface construction algorithm. In: SIGGRAPH 1987 Conference on Computer Graphics and Interactive Techniques; 2731 July 1987; Anaheim, CA, USA. New York, NY, USA: ACM, pp. 163-169.
[2] Theussl T, Moller T, Groller M. Optimal regular volume sampling. In: IEEE 2001 Conference on Visualization; 2126 October 2001; San Diego, CA, USA. New York, NY, USA: IEEE. pp. 91-98.
[3] Vad V, Csebfalvi B, Rautek P, Groller E. Towards an unbiased comparison of CC, BCC, and FCC lattices in terms of prealiasing. Comp Graph Forum 2014; 33: 81-90.
[4] Keppel E. Approximating complex surfaces by triangulation of contour lines. IBM J Res Dev 1975; 19: 2-11.
[5] Herman GT, Lun HK. Three-dimensional display of human organs from computed tomograms. Comput Vision Graph 1979; 9: 1-21.
[6] Bourke P. Polygonising A Scalar Field Using Tetrahedrons. Norwich, UK: University of East Anglia, 1997.
[7] Strand R. Interpolation and sampling on a honeycomb lattice. In: IEEE 2010 International Conference on Pattern Recognition; 2326 August 2010; ˙Istanbul, Turkey. New York, NY, USA: IEEE. pp. 2222-2225.
[8] Middleton L, Sivaswamy J. Hexagonal Image Processing. New York, NY, USA: Springer, 2005.
[9] Treece GM, Prager RW, Gee AH. Regularised marching tetrahedra: improved iso-surface extraction. Comput Graph 1999; 23: 583-598.
[10] Carr H, Theussl T, Moller T. Isosurfaces on optimal regular samples. In: VISSYM 2003 Symposium on Data Visualization; 2628 May 2003; Grenoble, France. Aire-la-Ville, Switzerland: Eurographics Association. pp. 39-48.
[11] Takahashi T, Yonekura T. Isosurface construction from a data set sampled on a face-centered-cubic lattice. Proc ICCVG 2002; 2: 754-763.
[12] Petkov K, Qiu F, Fan Z, Kaufman A, Mueller K. Efficient LBM visual simulation on face-centered cubic lattices. IEEE T Vis Comput Gr 2009; 15: 802-814.
[13] Strand R, Stelldinger P. Topology preserving marching cubes-like algorithms on the face-centered cubic grid. In: IEEE 2007 International Conference on Image Analysis and Processing; 1014 September 2007; Modena, Italy. New York, NY, USA: IEEE. pp. 781-788.
[14] Wells P, Smith R, Suparta G B. Sampling the sinogram in computed tomography. Mater Eval 1997; 5: 772-783.
[15] Elaff I, El-Kemany A, Kholif M. Universal and stable medical image generation for tissue segmentation (the unistable method). Turk J Elec Eng & Comp Sci 2017; 25: 1070-1081.
[16] Aydo˘gan T, Bayılmı¸s C. A new efficient block matching data hiding method based on scanning order selection in medical images. Turk J Elec Eng & Comp Sci 2017; 25: 461-473.
[17] Hang X, Paragios N, Metaxas D. Shape registration in implicit spaces using information theory and free form deformations. IEEE T PAMI 2006; 28: 1303-1318.
[18] Eyiyurekli M, Breen D. Interactive free-form level-set surface-editing operators. Comput Graph 2010; 34: 621-638.
[19] Hoppe H, DeRose T, Duchamp T, McDonald J, Stuetzle W. Surface reconstruction from unorganized points. In: SIGGRAPH 1992 Conference on Computer Graphics and Interactive Techniques; 2631 July 1992; Chicago, IL, USA. New York, NY, USA: ACM. pp. 71-78.
[20] Frisken P, Rockwood J. Adaptively sampled distance fields: a general representation of shape for computer graphics. In: SIGGRAPH 2000 Conference on Computer Graphics and Interactive Techniques; 2328 July 2000; New Orleans, LA, USA. New York, NY, USA: ACM. pp. 249-254.
[21] Kobbelt L, Botsch M, Schwanecke U, Seidel HP. Feature-sensitive surface extraction from volume data. In: SIGGRAPH 2001 Conference on Computer Graphics and Interactive Techniques; 1217 August 2001; Los Angeles, CA, USA. New York, NY, USA: ACM. pp. 57-66.
[22] Sahillio˘glu Y, Yemez Y. Coarse-to-fine surface reconstruction from silhouettes and range data using mesh deformation. Comput Vis Image Und 2010; 114: 334-348.
[23] Petersen DP, Middleton D. Sampling and reconstruction of wave-number-limited functions in N -dimensional Euclidean spaces. Info Control 1962; 5: 279-323.
[24] Bloomenthal J, Bajaj C. Introduction to Implicit Surfaces. New York, NY, USA: Kaufmann, 1997.
[25] Botsch M, Kobbelt L, Pauly M, Alliez P, Levy B. Polygon Mesh Processing. Boca Raton, FL, USA: CRC Press, 2010.
[26] Wells AF. Structural Inorganic Chemistry. 5th ed. Oxford, UK: Oxford University Press, 2012.
[27] Jackson AG. Handbook of Crystallography. New York, NY, USA: Springer, 2011.
[28] Marder MP. Condensed Matter Physics. 2nd ed. Hoboken, NJ, USA: Wiley, 2010.
[29] Ashcroft NW, Mermin ND. Solid State Physics. Upper Saddle River, NJ, USA: Prentice Hall, 1976.
[30] Wolfram Web Resources. Rhombic Dodecahedron. MathWorld, 2017. Available online at http://mathworld.wolfram.com/RhombicDodecahedron.html.
[31] Cignoni P, Montani C, Scopigno R. A comparison of mesh simplification algorithms. Comput Graph 1998; 22: 37-54.
[32] Marschner SR, Lobb RJ. An evaluation of reconstruction filters for volume rendering. In: IEEE 1994 Conference on Visualization; 2128 October 1994; Washington, DC, USA. New York, NY, USA: IEEE. pp. 100-107.