“Topology-controlled reconstruction of multi-labelled domains from cross-sections” by Huang, Zou, Carr and Ju
Conference:
Type:
Title:
- Topology-controlled reconstruction of multi-labelled domains from cross-sections
Session/Category Title: Reconstructing 3D Surfaces From Points, Lines, Images & Water
Presenter(s)/Author(s):
Moderator(s):
Abstract:
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.
References:
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
