“Topology-controlled reconstruction of multi-labelled domains from cross-sections” by Huang, Zou, Carr and Ju

  • ©Zhiyang Huang, Ming Zou, Nathan Carr, and Tao Ju



Session Title:

    Reconstructing 3D Surfaces From Points, Lines, Images & Water


    Topology-controlled reconstruction of multi-labelled domains from cross-sections




    In this work we present the first algorithm for reconstructing multi-labeled material interfaces the allows for explicit topology control. Our algorithm takes in a set of 2D cross-sectional slices (not necessarily parallel), each partitioned by a curve network into labeled regions representing different material types. For each label, the user has the option to constrain the number of connected components and genus. Our algorithm is able to not only produce a material interface that interpolates the curve networks but also simultaneously satisfy the topological requirements. Our key innovation is defining a space of topology-varying material interfaces, which extends the family of level sets in a scalar function, and developing discrete methods for sampling distinct topologies in this space. Besides specifying topological constraints, the user can steer the algorithm interactively, such as by scribbling. We demonstrate, on synthetic and biological shapes, how our algorithm opens up new opportunities for topology-aware modeling in the multi-labeled context.


    1. Hyung Taek Ahn and Mikhail Shashkov. 2007. Multi-material Interface Reconstruction on Generalized Polyhedral Meshes. J. Comput. Phys. 226, 2 (Oct. 2007), 2096–2132. Google ScholarDigital Library
    2. John C. Anderson, Christoph Garth, Mark A. Duchaineau, and Ken Joy. 2008. Discrete Multi-Material Interface Reconstruction for Volume Fraction Data. Computer Graphics Forum (Proc. of Eurographics/IEEE-VGTC Symposium on Visualization 2008) 27, 3 (2008).Google Scholar
    3. J. C. Anderson, C. Garth, M. A. Duchaineau, and K. I. Joy. 2010. Smooth, Volume-Accurate Material Interface Reconstruction. IEEE Transactions on Visualization and Computer Graphics 16, 5 (2010), 802–814. Google ScholarDigital Library
    4. Marco Attene, Marcel Campen, and Leif Kobbelt. 2013. Polygon mesh repairing: An application perspective. ACM Comput. Surv. 45, 2 (2013), 15. Google ScholarDigital Library
    5. Pierre-Louis Bazin and Dzung L. Pham. 2007. Topology-Preserving Tissue Classification of Magnetic Resonance Brain Images. IEEE Trans. Med. Imaging 26, 4 (2007), 487–496. Google ScholarCross Ref
    6. Amit Bermano, Amir Vaxman, and Craig Gotsman. 2011. Online Reconstruction of 3D Objects from Arbitrary Cross-sections. ACM Trans. Graph. 30, 5, Article 113 (Oct. 2011), 11 pages. Google ScholarDigital Library
    7. Martin Bertram, Gerd Reis, Rolf H. van Lengen, Sascha Köhn, and Hans Hagen. 2005. Non-manifold Mesh Extraction from Time-varying Segmented Volumes Used for Modeling a Human Heart. In Proceedings of the Seventh Joint Eurographics / IEEE VGTC Conference on Visualization (EUROVIS’05). 199–206.Google ScholarDigital Library
    8. Dobrina Boltcheva, Mariette Yvinec, and Jean-Daniel Boissonnat. 2009. Feature preserving Delaunay mesh generation from 3D multi-material images. Comput. Graph. Forum 28, 5 (2009), 1455–1464. Google ScholarCross Ref
    9. Kathleen S. Bonnell, Mark A. Duchaineau, Daniel Schikore, Bernd Hamann, and Kenneth I. Joy. 2003. Material Interface Reconstruction. IEEE Trans. Vis. Comput. Graph. 9, 4 (2003), 500–511. Google ScholarDigital Library
    10. Kenneth A. Brakke. 1992. The surface evolver. Experiment. Math. 1, 2 (1992), 141–165. http://projecteuclid.org/euclid.em/1048709050Google ScholarCross Ref
    11. Jonathan R. Bronson, Joshua A. Levine, and Ross T. Whitaker. 2014. Lattice Cleaving: A Multimaterial Tetrahedral Meshing Algorithm with Guarantees. IEEE Trans. Vis. Comput. Graph. 20, 2 (2014), 223–237. Google ScholarDigital Library
    12. Hamish Carr and David J. Duke. 2014. Joint Contour Nets. IEEE Trans. Vis. Comput. Graph. 20, 8 (2014), 1100–1113. Google ScholarDigital Library
    13. Hamish Carr, Zhao Geng, Julien Tierny, Amit Chattopadhyay, and Aaron Knoll. 2015. Fiber Surfaces: Generalizing Isosurfaces to Bivariate Data. Comput. Graph. Forum 34, 3 (2015), 241–250. Google ScholarDigital Library
    14. Fang Da, Christopher Batty, and Eitan Grinspun. 2014. Multimaterial Mesh-based Surface Tracking. ACM Trans. Graph. 33, 4, Article 112 (July 2014), 11 pages.Google ScholarDigital Library
    15. Tamal K. Dey, Firdaus Janoos, and Joshua A. Levine. 2012. Meshing interfaces of multi-label data with Delaunay refinement. Eng. Comput. (Lond.) 28, 1 (2012), 71–82. Google ScholarDigital Library
    16. Scott Dillard, Dan Thoma, Bernd Hamann, and John Bingert. 2007. Construction of Simplified Boundary Surfaces from Serial-sectioned Metal Micrographs. IEEE Transactions on Visualization & Computer Graphics 13, undefined (2007), 1528–1535.Google Scholar
    17. H. Edelsbrunner and J. Harer. 2002. Jacobi Sets of Multiple Morse Functions. In Foundations in Computational Mathematics. Cambridge University Press, 37–57.Google Scholar
    18. Herbert Edelsbrunner and John L. Harer. 2009. Computational Topology: An Introduction. American Mathematical Society. Google ScholarCross Ref
    19. Noura Faraj, Jean-Marc Thiery, and Tamy Boubekeur. 2016. Multi-material Adaptive Volume Remesher. Comput. Graph. 58, C (Aug. 2016), 150–160. Google ScholarDigital Library
    20. Riccardo Fellegara, Federico Iuricich, Leila De Floriani, and Kenneth Weiss. 2014. Efficient computation and simplification of discrete morse decompositions on triangulated terrains. In Proceedings of the 22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. 223–232. Google ScholarDigital Library
    21. Powei Feng, Tao Ju, and Joe D. Warren. 2010. Piecewise Tri-linear Contouring for Multi-material Volumes. In Advances in Geometric Modeling and Processing, 6th International Conference, GMP 2010, Castro Urdiales, Spain, June 16–18, 2010. Proceedings. 43–56. Google ScholarDigital Library
    22. Yotam I. Gingold and Denis Zorin. 2006. Controlled-topology filtering. In Proceedings of the Tenth ACM Symposium on Solid and Physical Modeling 2006, Cardiff University, Wales, UK, June 6–8, 2006. 53–61. Google ScholarDigital Library
    23. David Günther, Alec Jacobson, Jan Reininghaus, Hans-Peter Seidel, Olga Sorkine-Hornung, and Tino Weinkauf. 2014. Fast and Memory-Efficienty Topological Denoising of 2D and 3D Scalar Fields. IEEE Trans. Vis. Comput. Graph. 20, 12 (2014), 2585–2594. Google ScholarCross Ref
    24. M. Haitham Shammaa, Yutaka Ohtake, and Hiromasa Suzuki. 2010. Segmentation of Multi-material CT Data of Mechanical Parts for Extracting Boundary Surfaces. Comput. Aided Des. 42, 2 (Feb. 2010), 118–128. Google ScholarDigital Library
    25. Gabor T. Herman, Jingsheng Zheng, and Carolyn A. Bucholtz. 1992. Shape-Based Interpolation. IEEE Comput. Graph. Appl. 12, 3 (1992), 69–79. Google ScholarDigital Library
    26. Tao Ju, Frank Losasso, Scott Schaefer, and Joe D. Warren. 2002. Dual contouring of hermite data. ACM Trans. Graph. 21, 3 (2002), 339–346. Google ScholarDigital Library
    27. Tao Ju, Qian-Yi Zhou, and Shi-Min Hu. 2007. Editing the Topology of 3D Models by Sketching. ACM Trans. Graph. 26, 3, Article 42 (July 2007). Google ScholarDigital Library
    28. Byungmoon Kim. 2010. Multi-phase Fluid Simulations Using Regional Level Sets. ACM Trans. Graph. 29, 6, Article 175 (Dec. 2010), 8 pages. Google ScholarCross Ref
    29. Lu Liu, C. Bajaj, Joseph Deasy, Daniel A. Low, and Tao Ju. 2008. Surface Reconstruction From Non-parallel Curve Networks. Comput. Graph. Forum 27, 2 (2008), 155–163. Google ScholarCross Ref
    30. Frank Losasso, Tamar Shinar, Andrew Selle, and Ronald Fedkiw. 2006. Multiple Interacting Liquids. ACM Trans. Graph. 25, 3 (July 2006), 812–819. Google ScholarDigital Library
    31. Miriah D. Meyer, Ross T. Whitaker, Robert M. Kirby, Christian Ledergerber, and Hanspeter Pfister. 2008. Particle-based Sampling and Meshing of Surfaces in Multi-material Volumes. IEEE Trans. Vis. Comput. Graph. 14, 6 (2008), 1539–1546. Google ScholarDigital Library
    32. J. Milnor. 1963. Morse Theory. Princeton Univ. Press, New Jersey.Google Scholar
    33. Nathan Mitchell, Mridul Aanjaneya, Rajsekhar Setaluri, and Eftychios Sifakis. 2015. Non-manifold Level Sets: A Multivalued Implicit Surface Representation with Applications to Self-collision Processing. ACM Trans. Graph. 34, 6, Article 247 (Oct. 2015), 9 pages.Google ScholarDigital Library
    34. Fakir S. Nooruddin and Greg Turk. 2003. Simplification and Repair of Polygonal Models Using Volumetric Techniques. IEEE Trans. Vis. Comput. Graph. 9, 2 (2003), 191–205. Google ScholarDigital Library
    35. Jean-Philippe Pons, Florent Ségonne, Jean-Daniel Boissonnat, Laurent Rineau, Mariette Yvinec, and Renaud Keriven. 2007. High-Quality Consistent Meshing of Multi-Label Datasets. In International Conference on Information Processing in Medical Imaging 2007. Netherlands, 200. https://hal.archives-ouvertes.fr/hal-00488043Google Scholar
    36. Jin Qian and Yongjie Zhang. 2011. Dual Contouring for Domains with Topology Ambiguity. In Proceedings of the 20th International Meshing Roundtable, IMR 2011, October 23–26, 2011, Paris, France. 41–60. Google ScholarCross Ref
    37. R. I. Saye. 2015. An Algorithm to Mesh Interconnected Surfaces via the Voronoi Interface. Eng. with Comput. 31, 1 (Jan. 2015), 123–139. Google ScholarDigital Library
    38. Andrei Sharf, Thomas Lewiner, Ariel Shamir, Leif Kobbelt, and Daniel Cohen-Or. 2006. Competing fronts for coarse-to-fine surface reconstruction. In Eurographics. Vienna, 389–398. http://www.mat.puc-rio.br/~tomlew/competing_fronts_eg.pdfGoogle Scholar
    39. Andrei Sharf, Thomas Lewiner, Gil Shklarski, Sivan Toledo, and Daniel Cohen-Or. 2007. Interactive Topology-aware Surface Reconstruction. ACM Trans. Graph. 26, 3 (July 2007). Google ScholarDigital Library
    40. Hang Si. 2007. TetGen. A Quality Tetrahedral Mesh Generator and Three-Dimensional Delaunay Triangulator. (2007). http://tetgen.berlios.deGoogle Scholar
    41. Julien Tierny and Hamish Carr. 2017. Jacobi Fiber Surfaces for Bivariate Reeb Space Computation. IEEE Trans. Vis. Comput. Graph. 23, 1 (2017), 960–969. Google ScholarDigital Library
    42. Greg Turk and James F. O’Brien. 1999. Shape transformation using variational implicit functions. In SIGGRAPH ’99: Proceedings of the 26th annual conference on Computer graphics and interactive techniques. ACM Press/Addison-Wesley Publishing Co., 335–342. Google ScholarDigital Library
    43. J. Waggoner, Y. Zhou, J. Simmons, M.D. Graef, and S. Wang. 2015. Topology-Preserving Multi-label Image Segmentation. In 2015 IEEE Winter Conference on Applications of Computer Vision. 1084–1091. Google ScholarDigital Library
    44. Kangxue Yin, Hui Huang, Hao Zhang, Minglun Gong, Daniel Cohen-Or, and Baoquan Chen. 2014. Morfit: Interactive Surface Reconstruction from Incomplete Point Clouds with Curve-driven Topology and Geometry Control. ACM Trans. Graph. 33, 6 (Nov. 2014), 202:1–202:12.Google ScholarDigital Library
    45. Zhan Yuan, Yizhou Yu, and Wenping Wang. 2012. Object-space Multiphase Implicit Functions. ACM Trans. Graph. 31, 4, Article 114 (July 2012), 10 pages.Google ScholarDigital Library
    46. Yun Zeng, Dimitris Samaras, Wei Chen, and Qunsheng Peng. 2008. Topology cuts: A novel min-cut/max-flow algorithm for topology preserving segmentation in N-D images. Computer Vision and Image Understanding 112, 1 (2008), 81–90. Google ScholarDigital Library
    47. Yongjie Zhang, Thomas J. R. Hughes, and Chandrajit L. Bajaj. 2007. Automatic 3D Mesh Generation for a Domain with Multiple Materials. In Proceedings of the 16th International Meshing Roundtable, October 14–17, 2007, Seattle, Washington, USA, Proceedings. 367–386.Google Scholar
    48. Hong-Kai Zhao, T. Chan, B. Merriman, and S. Osher. 1996. A Variational Level Set Approach to Multiphase Motion. J. Comput. Phys. 127, 1 (1996), 179 — 195. Google ScholarDigital Library
    49. Wen Zheng, Jun-Hai Yong, and Jean-Claude Paul. 2006. Simulation of Bubbles. In Proceedings of the 2006 ACM SIGGRAPH/Eurographics Symposium on Computer Animation (SCA ’06). 325–333.Google ScholarDigital Library
    50. Ming Zou, Michelle Holloway, Nathan Carr, and Tao Ju. 2015. Topology-constrained surface reconstruction from cross-sections. ACM Trans. Graph. 34, 4 (2015), 128. Google ScholarDigital Library

ACM Digital Library Publication: