research-article

Galaxy Maps: Localized Foliations for Bijective Volumetric Mapping

Authors:

Steffen Hinderink,

Marcel CampenAuthors Info & Claims

ACM Transactions on Graphics (TOG), Volume 42, Issue 4

Article No.: 129, Pages 1 - 16

https://doi.org/10.1145/3592410

Published: 26 July 2023 Publication History

Abstract

A method is presented to compute volumetric maps and parametrizations of objects over 3D domains. As a key feature, continuity and bijectivity are ensured by construction. Arbitrary objects of ball topology, represented as tetrahedral meshes, are supported. Arbitrary convex as well as star-shaped domains are supported. Full control over the boundary mapping is provided. The method is based on the technique of simplicial foliations, generalized to a broader class of domain shapes and applied adaptively in a novel localized manner. This increases flexibility as well as efficiency over the state of the art, while maintaining reliability in guaranteeing map bijectivity.

Supplementary Material

MP4 File (papers_546_VOD.mp4)

presentation

Download
150.39 MB

References

[1]

S. Mazdak Abulnaga, Oded Stein, Polina Golland, and Justin Solomon. 2023. Symmetric Volume Maps: Order-invariant Volumetric Mesh Correspondence with Free Boundary. ACM Trans. Graph. 42, 3 (2023), 25:1--25:20.

Digital Library

[2]

Noam Aigerman and Yaron Lipman. 2013. Injective and Bounded Distortion Mappings in 3D. ACM Trans. Graph. 32, 4 (2013), 106:1--106:14.

Digital Library

[3]

Marc Alexa. 2023. Tutte Embeddings of Tetrahedral Meshes. Discrete & Computational Geometry (2023).

[4]

Marc Alexa, Daniel Cohen-Or, and David Levin. 2000. As-Rigid-As-Possible Shape Interpolation. In Proc. SIGGRAPH 2000. 157--164.

Digital Library

[5]

Stephen Boyd and Lieven Vandenberghe. 2004. Convex Optimization. Cambridge University Press.

Digital Library

[6]

Hendrik Brückler, David Bommes, and Marcel Campen. 2022a. Volume Parametrization Quantization for Hexahedral Meshing. ACM Trans. Graph. 41, 4 (2022), 60:1--60:19.

Digital Library

[7]

Hendrik Brückler, Ojaswi Gupta, Manish Mandad, and Marcel Campen. 2022b. The 3D Motorcycle Complex for Structured Volume Decomposition. Computer Graphics Forum 41, 2 (2022), 221--235.

[8]

Marcel Campen, Ryan Capouellez, Hanxiao Shen, Leyi Zhu, Daniele Panozzo, and Denis Zorin. 2021. Efficient and Robust Discrete Conformal Equivalence with Boundary. ACM Trans. Graph. 40, 6 (2021), 261:1--261:16.

Digital Library

[9]

Marcel Campen, Cláudio T. Silva, and Denis Zorin. 2016. Bijective Maps from Simplicial Foliations. ACM Trans. Graph. 35, 4 (2016), 74:1--74:15.

Digital Library

[10]

David Cohen and Mirela Ben-Chen. 2019. Generalized volumetric foliation from inverted viscous flow. Computers & Graphics 82 (2019), 152--162.

Digital Library

[11]

Xingyi Du, Noam Aigerman, Qingnan Zhou, Shahar Z. Kovalsky, Yajie Yan, Danny M. Kaufman, and Tao Ju. 2020. Lifting Simplices to Find Injectivity. ACM Trans. Graph. 39, 4 (2020), 120:1--120:17.

Digital Library

[12]

Xingyi Du, Danny M. Kaufman, Qingnan Zhou, Shahar Z. Kovalsky, Yajie Yan, Noam Aigerman, and Tao Ju. 2022. Isometric Energies for Recovering Injectivity in Constrained Mapping. In Proc. SIGGRAPH Asia 2022. 36:1--36:9.

Digital Library

[13]

J. M. Escobar, E. Rodrıguez, R. Montenegro, G. Montero, and J. M. González-Yuste. 2003. Simultaneous untangling and smoothing of tetrahedral meshes. Comput. Methods Appl. Mech. Eng. 192, 25 (2003), 2775--2787.

[14]

Yu Fang, Minchen Li, Chenfanfu Jiang, and Danny M. Kaufman. 2021. Guaranteed Globally Injective 3D Deformation Processing. ACM Trans. Graph. 40, 4 (2021), 75:1--75:13.

Digital Library

[15]

Michael S. Floater. 1997. Parametrization and smooth approximation of surface triangulations. Computer Aided Geometric Design 14, 3 (1997), 231--250.

Digital Library

[16]

Michael S. Floater and Valérie Pham-Trong. 2006. Convex combination maps over triangulations, tilings, and tetrahedral meshes. Advances in Computational Mathematics 25, 4 (2006), 347--356.

[17]

Xiao-Ming Fu, Yang Liu, and Baining Guo. 2015. Computing Locally Injective Mappings by Advanced MIPS. ACM Trans. Graph. 34, 4 (2015), 71:1--71:12.

Digital Library

[18]

Xiao-Ming Fu, Jian-Ping Su, Zheng-Yu Zhao, Qing Fang, Chunyang Ye, and Ligang Liu. 2021. Inversion-free geometric mapping construction: A survey. Computational Visual Media 7, 3 (2021), 289--318.

[19]

Robert Furch. 1924. Zur Grundlegung der kombinatorischen Topologie. Abhandlungen aus dem mathematischen Seminar der Universität Hamburg 3, 1 (1924), 69--88.

[20]

Vladimir Garanzha, Igor Kaporin, Liudmila Kudryavtseva, François Protais, Nicolas Ray, and Dmitry Sokolov. 2021. Foldover-free maps in 50 lines of code. ACM Trans. Graph. 40, 4 (2021), 102:1--102:16.

Digital Library

[21]

Mark Gillespie, Boris Springborn, and Keenan Crane. 2021. Discrete Conformal Equivalence of Polyhedral Surfaces. ACM Trans. Graph. 40, 4 (2021), 103:1--103:20.

Digital Library

[22]

Yixin Hu, Qingnan Zhou, Xifeng Gao, Alec Jacobson, Denis Zorin, and Daniele Panozzo. 2018. Tetrahedral Meshing in the Wild. ACM Trans. Graph. 37, 4 (2018), 60:1--60:14.

Digital Library

[23]

Lisa Huynh and Yotam Gingold. 2015. Bijective Deformations in ℝⁿ via Integral Curve Coordinates. arXiv:1505.00073

[24]

S. S. Iyengar, Xin Li, Huanhuan Xu, Supratik Mukhopadhyay, N. Balakrishnan, Amit Sawant, and Puneeth Iyengar. 2012. Toward More Precise Radiotherapy Treatment of Lung Tumors. Computer 45, 1 (2012), 59--65.

Digital Library

[25]

Zhongshi Jiang, Scott Schaefer, and Daniele Panozzo. 2017. Simplicial Complex Augmentation Framework for Bijective Maps. ACM Trans. Graph. 36, 6 (2017), 186:1--186:9.

Digital Library

[26]

Bert Jüttler, Sofia Maroscheck, Myung-Soo Kim, and Q Youn Hong. 2019. Arc fibrations of planar domains. Computer Aided Geometric Design 71 (2019), 105--118.

Digital Library

[27]

Shahar Z. Kovalsky, Noam Aigerman, Ronen Basri, and Yaron Lipman. 2014. Controlling Singular Values with Semidefinite Programming. ACM Trans. Graph. 33, 4 (2014), 68:1--68:13.

Digital Library

[28]

Xin Li, Xiaohu Guo, Hongyu Wang, Ying He, Xianfeng Gu, and Hong Qin. 2007. Harmonic Volumetric Mapping for Solid Modeling Applications. In Proc. SPM 2007. 109--120.

Digital Library

[29]

Juncong Lin, Jiazhi Xia, Xing Gao, Minghong Liao, Ying He, and Xianfeng Gu. 2015. Interior structure transfer via harmonic 1-forms. Multimedia Tools and Applications 74, 1 (2015), 139--158.

Digital Library

[30]

Manish Mandad, Ruizhi Chen, David Bommes, and Marcel Campen. 2022. Intrinsic mixed-integer polycubes for hexahedral meshing. Computer Aided Geometric Design 94 (2022), 102078.

[31]

Tobias Martin, Guoning Chen, Suraj Musuvathy, Elaine Cohen, and Charles Hansen. 2012. Generalized Swept Mid-structure for Polygonal Models. Computer Graphics Forum 31, 4 (2012), 805--814.

Digital Library

[32]

Tobias Martin, Elaine Cohen, and Robert M. Kirby. 2008. Volumetric Parameterization and Trivariate B-spline Fitting using Harmonic Functions. In Proc. SPM 2008. 269--280.

Digital Library

[33]

I. Moerdijk and J. Mrčun. 2003. Introduction to Foliations and Lie Groupoids. Cambridge University Press.

[34]

Alexander Naitsat, Yufeng Zhu, and Yehoshua Y. Zeevi. 2020. Adaptive Block Coordinate Descent for Distortion Optimization. Computer Graphics Forum 39, 6 (2020), 360--376.

[35]

M. Nieser, U. Reitebuch, and K. Polthier. 2011. CubeCover - Parameterization of 3D Volumes. Computer Graphics Forum 30, 5 (2011), 1397--1406.

[36]

Valentin Z. Nigolian, Marcel Campen, and David Bommes. 2023. Expansion Cones: A Progressive Volumetric Mapping Framework. ACM Trans. Graph. 42, 4 (2023).

Digital Library

[37]

Matthew Overby, Danny Kaufman, and Rahul Narain. 2021. Globally Injective Geometry Optimization with Non-Injective Steps. Computer Graphics Forum 40, 5 (2021), 111--123.

[38]

Nico Pietroni, Marcel Campen, Alla Sheffer, Gianmarco Cherchi, David Bommes, Xifeng Gao, Riccardo Scateni, Franck Ledoux, Jean Remacle, and Marco Livesu. 2022. Hex-Mesh Generation and Processing: A Survey. ACM Trans. Graph. 42, 2 (2022), 16:1--16:44.

[39]

Roman Poya, Rogelio Ortigosa, and Theodore Kim. 2023. Geometric Optimisation Via Spectral Shifting. ACM Trans. Graph. 42, 3 (2023), 29:1--29:15.

Digital Library

[40]

Michael Rabinovich, Roi Poranne, Daniele Panozzo, and Olga Sorkine-Hornung. 2017. Scalable Locally Injective Mappings. ACM Trans. Graph. 36, 4 (2017), 16:1--16:16.

Digital Library

[41]

Patrick Schmidt, Janis Born, Marcel Campen, and Leif Kobbelt. 2019. Distortion-Minimizing Injective Maps Between Surfaces. ACM Trans. Graph. 38, 6 (2019), 156:1--156:15.

Digital Library

[42]

Christian Schüller, Ladislav Kavan, Daniele Panozzo, and Olga Sorkine-Hornung. 2013. Locally Injective Mappings. Computer Graphics Forum 32, 5 (2013), 125--135.

Digital Library

[43]

Hang Si. 2015. TetGen, a Delaunay-Based Quality Tetrahedral Mesh Generator. ACM Trans. Math. Softw. 41, 2 (2015), 11:1--11:36.

Digital Library

[44]

Breannan Smith, Fernando De Goes, and Theodore Kim. 2019. Analytic Eigensystems for Isotropic Distortion Energies. ACM Trans. Graph. 38, 1 (2019), 3:1--3:15.

Digital Library

[45]

Jason Smith and Scott Schaefer. 2015. Bijective Parameterization with Free Boundaries. ACM Trans. Graph. 34, 4 (2015), 70:1--70:9.

Digital Library

[46]

Tommaso Sorgente, Silvia Biasotti, and Michela Spagnuolo. 2022. Polyhedron kernel computation using a geometric approach. Computers & Graphics 105 (2022), 94--104.

Digital Library

[47]

Jian-Ping Su, Xiao-Ming Fu, and Ligang Liu. 2019. Practical Foldover-Free Volumetric Mapping Construction. Computer Graphics Forum 38, 7 (2019), 287--297.

[48]

Jian-Ping Su, Chunyang Ye, Ligang Liu, and Xiao-Ming Fu. 2020. Efficient Bijective Parameterizations. ACM Trans. Graph. 39, 4 (2020), 111:1--111:8.

Digital Library

[49]

Thomas Toulorge, Christophe Geuzaine, Jean-François Remacle, and Jonathan Lambrechts. 2013. Robust untangling of curvilinear meshes. J. Comput. Phys. 254 (2013), 8--26.

Digital Library

[50]

Sofia Trautner, Bert Jüttler, and Myung-Soo Kim. 2021. Representing planar domains by polar parameterizations with parabolic parameter lines. Computer Aided Geometric Design 85 (2021), 101966.

Digital Library

[51]

W. T. Tutte. 1963. How to draw a graph. Proc. Lond. Math. Soc. 13 (1963), 743--767.

[52]

Yalin Wang, Xianfeng Gu, Tony F. Chan, Paul M. Thompson, and Shing-Tung Yau. 2004. Volumetric harmonic brain mapping. In Proc. ISBI 2004. 1275--1278.

[53]

Ofir Weber and Denis Zorin. 2014. Locally Injective Parametrization with Arbitrary Fixed Boundaries. ACM Trans. Graph. 33, 4 (2014), 75:1--75:12.

Digital Library

[54]

Jiazhi Xia, Ying He, Shuchu Han, Chi-Wing Fu, Feng Luo, and Xianfeng Gu. 2010. Parameterization of Star-Shaped Volumes Using Green's Functions. In Proc. GMP 2010. 219--235.

Digital Library

[55]

Yongjie Zhang, Wenyan Wang, and Thomas J. R. Hughes. 2012. Solid T-spline construction from boundary representations for genus-zero geometry. Comput. Methods Appl. Mech. Eng. 249--252 (2012), 185--197.

[56]

Qingnan Zhou and Alec Jacobson. 2016. Thingi10K: A Dataset of 10,000 3D-Printing Models. arXiv:1605.04797

Cited By

Nigolian VCampen MBommes D(2024)A Progressive Embedding Approach to Bijective Tetrahedral Maps driven by Cluster Mesh TopologyACM Transactions on Graphics10.1145/368799243:6(1-14)Online publication date: 19-Dec-2024
https://dl.acm.org/doi/10.1145/3687992
Hinderink SBrückler HCampen M(2024)Bijective Volumetric Mapping via Star DecompositionACM Transactions on Graphics10.1145/368795043:6(1-11)Online publication date: 19-Dec-2024
https://dl.acm.org/doi/10.1145/3687950
Livesu M(2024)Stripe Embedding: Efficient Maps with Exact Numeric ComputationACM Transactions on Graphics10.1145/368791543:6(1-14)Online publication date: 19-Dec-2024
https://dl.acm.org/doi/10.1145/3687915
Show More Cited By

Index Terms

Galaxy Maps: Localized Foliations for Bijective Volumetric Mapping
1. Computing methodologies
  1. Computer graphics
    1. Shape modeling
      1. Mesh models
      2. Volumetric models

Recommendations

Expansion Cones: A Progressive Volumetric Mapping Framework

Volumetric mapping is a ubiquitous and difficult problem in Geometry Processing and has been the subject of research in numerous and various directions. While several methods show encouraging results, the field still lacks a general approach with ...
A Progressive Embedding Approach to Bijective Tetrahedral Maps driven by Cluster Mesh Topology

We present a novel algorithm to map ball-topology tetrahedral meshes onto star-shaped domains with guarantees regarding bijectivity. Our algorithm is based on the recently introduced idea of Shrink-and-Expand, where images of interior vertices are ...
Bijective Volumetric Mapping via Star Decomposition

A method for the construction of bijective volumetric maps between 3D shapes is presented. Arbitrary shapes of ball-topology are supported, overcoming restrictions of previous methods to convex or star-shaped targets. In essence, the mapping problem is ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Graphics

ACM Transactions on Graphics Volume 42, Issue 4

August 2023

1912 pages

ISSN:0730-0301

EISSN:1557-7368

DOI:10.1145/3609020

Issue’s Table of Contents

Copyright © 2023 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 26 July 2023

Published in TOG Volume 42, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Deutsche Forschungsgemeinschaft

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
224
Total Downloads

Downloads (Last 12 months)77
Downloads (Last 6 weeks)2

Reflects downloads up to 14 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Nigolian VCampen MBommes D(2024)A Progressive Embedding Approach to Bijective Tetrahedral Maps driven by Cluster Mesh TopologyACM Transactions on Graphics10.1145/368799243:6(1-14)Online publication date: 19-Dec-2024
https://dl.acm.org/doi/10.1145/3687992
Hinderink SBrückler HCampen M(2024)Bijective Volumetric Mapping via Star DecompositionACM Transactions on Graphics10.1145/368795043:6(1-11)Online publication date: 19-Dec-2024
https://dl.acm.org/doi/10.1145/3687950
Livesu M(2024)Stripe Embedding: Efficient Maps with Exact Numeric ComputationACM Transactions on Graphics10.1145/368791543:6(1-14)Online publication date: 19-Dec-2024
https://dl.acm.org/doi/10.1145/3687915
Livesu M(2024)Advancing Front Surface MappingComputer Graphics Forum10.1111/cgf.1502643:2Online publication date: 30-Apr-2024
https://doi.org/10.1111/cgf.15026
Brückler HCampen M(2023)Collapsing Embedded Cell Complexes for Safer Hexahedral MeshingACM Transactions on Graphics10.1145/361838442:6(1-24)Online publication date: 5-Dec-2023
https://dl.acm.org/doi/10.1145/3618384
Nigolian VCampen MBommes D(2023)Expansion Cones: A Progressive Volumetric Mapping FrameworkACM Transactions on Graphics10.1145/359242142:4(1-19)Online publication date: 26-Jul-2023
https://dl.acm.org/doi/10.1145/3592421

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents