×

Geometric tomography with topological guarantees. (English) Zbl 1310.68196

Summary: We consider the problem of reconstructing a compact 3-manifold (with boundary) embedded in \(\mathbb R ^3\) from its cross-sections \(\mathcal S\) with a given set of cutting planes \(\mathcal P\) having arbitrary orientations. In this paper, we analyse a very natural reconstruction strategy: a point \(x\in\mathbb R^3\) belongs to the reconstructed object if (at least one of) its nearest point(s) in \(\mathcal P\) belongs to \(\mathcal S\). We prove that under appropriate sampling conditions, the output of such an algorithm preserves the homotopy type of the original object. Using the homotopy equivalence, we also show that the reconstructed object is homeomorphic (and isotopic) to the original object. This is the first time that 3-dimensional shape reconstruction from cross-sections comes with theoretical guarantees.

MSC:

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
57R30 Foliations in differential topology; geometric theory

Software:

CTI
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Bajaj, CL; Coyle, EJ; Lin, KN, Arbitrary topology shape reconstruction from planar cross sections, Graph. Models Image Process., 58, 524-543, (1996)
[2] Barequet, G; Sharir, M, Piecewise-linear interpolation between polygonal slices, Comput. Vis. Image Underst., 63, 251-272, (1996) · Zbl 0859.68120
[3] Barequet, G; Goodrich, MT; Levi-Steiner, A; Steiner, D, Contour interpolation by straight skeletons, Graph. Models, 66, 245-260, (2004) · Zbl 1068.68161
[4] Barequet, G., Vaxman, A.: Reconstruction of multi-label domains from partial planar cross-sections. Symposium on Geometry Processing. Comput. Graph. Forum 28(5), 1327-1337 (2009)
[5] Bermano, A; Vaxman, A; Gotsman, C, Online reconstruction of 3d objects from arbitrary cross-sections, ACM Trans. Graph. (TOG), 30, 113, (2011)
[6] Boissonnat, JD, Shape reconstruction from planar cross sections, Comput. Vis. Graph. Image Process., 44, 1-29, (1988)
[7] Boissonnat, J.D., Geiger, B.: Three dimensional reconstruction of complex shapes based on the Delaunay triangulation. In: Proceedings of Biomedical Image Processing and Biomedical Visualization, San Jose, pp. 964-975 (1993)
[8] Boissonnat, J.D., Memari P.: Shape reconstruction from unorganized cross sections. In: Proceedings of the Fifth Eurographics Symposium on Geometry Processing, pp. 89-98. Barcelona (2007)
[9] Braude, I.: Smooth 3D surface reconstruction from contours of biological data with MPU implicits. PhD thesis, Drexel University. http://dspace.library.drexel.edu/retrieve/4240/Braude_Ilya.pdf (2005)
[10] Chazal, F; Cohen-Steiner, D, A condition for isotopic approximation, Graph. Models, 67, 390-404, (2005) · Zbl 1087.68115
[11] Cheng, S.W., Dey, T.K.: Improved constructions of Delaunay based contour surfaces. In: Proceedings of the Fifth ACM Symposium on Solid Modeling and Applications, pp. 322-323. ACM, New York (1999)
[12] Choi, YK; Park, KH, A heuristic triangulation algorithm for multiple planar contours using an extended double branching procedure, Vis. Comput., 10, 372-387, (1994)
[13] Christiansen, H.N., Sederberg, T.W.: Conversion of complex contour line definitions into polygonal element mosaics. In: Proceedings of the 5th Annual Conference on Computer Graphics and Interactive Techniques, pp. 187-192. ACM, New York (1978)
[14] Cohen-Or, D; Levin, D, Guided multi-dimensional reconstruction from cross-sections, Ser. Approx. Decompos., 8, 47-56, (1996) · Zbl 1273.41023
[15] Cong, G; Parvin, B, Robust and efficient surface reconstruction from contours, Vis. Comput., 17, 199-208, (2001) · Zbl 0972.68764
[16] Dance, C.R.: Delaunay Reconstruction from Multiaxial Planar Cross-Sections. University of Cambridge, Cambridge (1997)
[17] Ekoule, AB; Peyrin, FC; Odet, CL, A triangulation algorithm from arbitrary shaped multiple planar contours, ACM Trans. Graph. (TOG), 10, 182-199, (1991) · Zbl 0738.68077
[18] Federer, H.: Curvature measures. Trans. Am. Math. Soc. 93, 418-491 (1959) · Zbl 0089.38402
[19] Frank Da, T.K.: L’interpolation de formes. PhD thesis, INRIA Sophia-Antipolis (2002)
[20] Fuchs, H., Kedem, Z.M., Uselton, S.P.: Optimal surface reconstruction from planar contours. Commun. ACM 20(10), 693-702 (1977) · Zbl 0399.68099
[21] Ganapathy, S; Dennehy, TG, A new general triangulation method for planar contours, ACM Siggraph Comput. Graph., 16, 69-75, (1982)
[22] Hatcher, A.: Algebraic Topology. Cambridge University Press, Cambridge (2002) · Zbl 1044.55001
[23] Huisken, J; Swoger, J; Bene, F; Wittbrodt, J; Stelzer, EHK, Optical sectioning deep inside live embryos by selective plane illumination microscopy, Science, 305, 1007, (2004)
[24] Ju, T; Warren, J; Carson, J; Eichele, G; Thaller, C; Chiu, W; Bello, M; Kakadiaris, I, Building 3D surface networks from 2D curve networks with application to anatomical modeling, Vis. Comput., 21, 764-773, (2005)
[25] Keppel, E, Approximating complex surfaces by triangulation of contour lines, IBM J. Res. Dev., 19, 2-11, (1975) · Zbl 0295.68076
[26] Leray, Jean, Sur la forme des espaces topologiques et sur LES points fixes des représentations, J. Math. Pures Appl. (9), 24, 95-167, (1945) · Zbl 0060.40703
[27] Lieutier, A, Any open bounded subset of R n has the same homotopy type as its medial axis, Computer-Aided Des., 36, 1029-1046, (2004)
[28] Liu, L; Bajaj, CL; Deasy, JO; Low, DA; Ju, T, Surface reconstruction from non-parallel curve networks, Comput. Graph. Forum, 27, 155-163, (2008)
[29] Lorensen, W.E., Cline H.E.: Marching cubes: A high resolution 3D surface construction algorithm. In: Proceedings of the 14th Annual Conference on Computer Graphics and Interactive Techniques, p. 169. ACM, New York (1987)
[30] Marker, J., Braude I., Museth K., Breen, D.: Contour-based surface reconstruction using implicit curve fitting, and distance field filtering and interpolation. In: Proceedings of International Workshop on Volume Graphics, pp. 95-102 (2006)
[31] Matveev, S.V.: Algorithmic Topology and Classification of 3-Manifolds. Springer, Berlin (2003) · Zbl 1048.57001
[32] May, J.P.: Finite spaces and simplicial complexes. Notes for REU. http://www.math.uchicago.edu/ may/MISCMaster.html (2003)
[33] Memari, P.: Geometric tomography with topological guarantees. PhD thesis, INRIA, Nice Sophia Antipolis University (2010) · Zbl 1284.68577
[34] Memari, P; Boissonnat, JD, Provably good 2D shape reconstruction from unorganized cross sections, Comput. Graph. Forum, 27, 1403-1410, (2008)
[35] Meyers, D.: Reconstruction of surfaces from planar contours. PhD thesis, University of Washington (1994)
[36] Nielson, G.M., Hamann, B.: The asymptotic decider: resolving the ambiguity in marching cubes. In: Proceedings of the Second Conference on Visualization ’91, pp. 91. IEEE Computer Society Press, Los Alamitos (1991)
[37] Oliva, J.M., Perrin M., Coquillart, S.: 3D reconstruction of complex polyhedral shapes from contours using a simplified generalized Voronoi diagram. In: Computer Graphics Forum, vol. 15, pp. 397-408. Blackwell Science Ltd., London (1996)
[38] Park, H, A hybrid approach to smooth surface reconstruction from 2-D cross sections, Int. J. Adv. Manuf. Technol., 25, 1130-1136, (2005)
[39] Park, H; Kim, K, Smooth surface approximation to serial cross-sections, Computer-Aided Des., 28, 995-1005, (1996)
[40] Payne, BA; Toga, AW, Surface reconstruction by multiaxial triangulation, IEEE Comput. Graph. Appl., 14, 28-35, (1994)
[41] Piegl, L; Tiller, W, Algorithm for approximate NURBS skinning, Computer-Aided Des., 28, 699-706, (1996)
[42] Rousseau, F.: Méthodes d’analyse d’images et de calibration pour l’échographie 3D en mode main-libre. PhD thesis (2003)
[43] Segal, G, Classifying spaces and spectral sequences, Publications Mathématiques de l’IHÉS, 34, 105-112, (1968) · Zbl 0199.26404
[44] Shantz, M, Surface definition for branching, contour-defined objects, ACM Siggraph Comput. Graph., 15, 242-270, (1981)
[45] Sidlesky, A., Barequet, G., Gotsman, C.: Polygon reconstruction from line cross-sections. In: Canadian Conference on Computational Geometry (2006)
[46] Tracton, G; Chen, J; Chaney, E, CTI: automatic construction of complex 3D surfaces from contours using the Delaunay triangulation, Math. Methods Med. Imaging, III, 86-97, (1994)
[47] Turk, G., O’Brien, J.F.: Shape transformation using variational implicit functions. In: ACM SIGGRAPH (1999)
[48] Wang, D; Hassan, O; Morgan, K; Weatherill, N, Efficient surface reconstruction from contours based on two-dimensional Delaunay triangulation, Int. J. Numer. Methods. Eng., 65, 734-751, (2006) · Zbl 1114.65026
[49] Welzl, E; Wolfers, B, Surface reconstruction between simple polygons via angle criteria, J. Symb. Comput., 17, 351, (1994) · Zbl 0942.68743
[50] Wolter, F.E.: Cut locus and medial axis in global shape interrogation and representation. In: Computer Aided Geometric Design, pp. 92-2. MIT Ocean Engineering Design Laboratory, Cambridge (1992)
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.