Journal

Galaxy Maps: Localized Foliations for Bijective Volumetric Mapping

Steffen Hinderink, Marcel Campen

Osnabrück University

SIGGRAPH 2023Geometry & ModelingVolumetric MappingBijective MappingTetrahedral MeshParametrizationFoliation
PaperCode

一句话总结

本文提出一种通过”局部化单纯形叶状结构”（localized simplicial foliations）构造体积映射的方法，能把任意球拓扑的四面体网格可靠地、按构造保证连续且双射地映射到任意星形（含凸）目标域上，并支持完整的边界映射约束。

研究背景

  • 领域现状：体积映射与体参数化是网格生成、样条建模、配准、纹理/结构迁移、插值变形等任务的基础模块，其中”双射性”（局部或全局单射）往往是硬性要求。二维里 Tutte 嵌入（凸组合映射）能按构造给出双射，但这一性质无法推广到三维；离散共形方法在三维也过于受限。
  • 核心痛点：三维里的主流做法是各种”尽力而为”（best-effort）的优化方法，能否得到双射结果因例而异、没有保证。唯一带双射保证的构造类方法是基于叶状结构的 Campen et al. 2016，但它只支持球和立方体两种目标域（且立方体情形无法完整控制边界映射），并且效率相对现代方法偏低。
  • 本文 idea：沿用”用叶状结构可靠构造双射”的核心思想，做两点推广与改进——(1) 把目标域从球/立方体推广到任意凸域乃至任意星形域，并支持完整边界约束；(2) 不再全局施加该构造，而是先用快速方法（如 3D Tutte）给出可能非双射的初始映射，再仅在其失效的局部区域施加叶状结构构造做”双射替换”，从而大幅提升效率。

方法

整体框架分两层。底层是一个”星形域双射构造算法”：给定球拓扑网格与到星形域的边界映射，用叶状结构逐叶（leaf-by-leaf）拼出一个按构造保证的连续双射。上层是”星系（galaxy）”策略：对一个有翻转缺陷的初始映射，只在缺陷附近切出若干星形子块（star），逐块调用底层算法做局部替换，再融合回全局映射。

flowchart LR
  A["初始映射 Φ (可能含翻转)"] --> B["定位翻转四面体"]
  B --> C["贪心生长星形子块 → 星系 G"]
  C --> D["每块用叶状结构构造双射替换 Ψ_i"]
  D --> E["分片线性化 + 界面细化链接"]
  E --> F["融合为全局双射 Ψ"]

关键设计：

  1. 星形域上的双射构造（底层算法）。 对网格 \([M]\) 构造一个径向叶状结构 \(\mathcal{F}_M\)（所有叶线从边界出发汇聚到内部中心点），对星形域 \(X\) 则以其核（kernel）中一个守卫点 \(x_0\) 为中心取”自然径向叶状结构”（守卫到边界的可见线段）。边界映射 \(\psi\) 把两组叶线一一对应起来。对内部点 \(p\)，设它所在叶线与边界交点为 \(s(p)\)、沿叶线的相对位置为 \(t(p)\in[0,1]\)，则映射定义为 \(\Psi(p)=t(p)\,\psi(s(p))+(1-t(p))\,x_0\)。这里 \(t(p)\) 被当作叶线上的重心坐标而非极坐标半径，从而把 Campen 2016 的球/立方体特例推广到一般星形域。文中证明该映射连续且双射。

  2. 全部运算落在有理数域。 构造刻意只用加减乘和行列式等基本算术，可用精确有理数（GMP）实现，杜绝浮点误差破坏正确性；只有星形性检验里的法向归一化用到浮点，但可用精确定向谓词做保守判定，仍不失可靠性。

  3. 星形子块的生长（星系算法）。 从一个被翻转的四面体作种子，逐个吞并面相邻四面体，直到满足”星形条件”（子块球拓扑、边界映射像围成星形集、边界映射单射且保定向）。星形性用一个线性规划求解切比雪夫中心（最大内切球）来检验：内切球半径 \(r>0\) 即星形，且给出守卫点 \(x_0\)；\(r\le 0\) 时其解还提供了生长方向的线索。生长启发式选取”最违反”的边界三角形 \(f^\ast=\arg\max_f\, n_f^{\mathsf T}x_0-n_f^{\mathsf T}a_f\) 并吞并其相邻四面体，以尽快消除星形性违反。子块碰撞时相互吸收，保证最终各星形块互不重叠。整个连通的翻转四面体簇会被一次性整块吞并。

  4. 分片线性化与界面链接。 上述 \(\Psi\) 逐四面体并非线性；要得到逐四面体线性的可用映射，需对每个星形块做嵌套细化。细化后星形块与外部网格不再共形，故对包围星形块的一层四面体按”扇形（fan）/花束（bouquet）”规则细化，复杂邻接先经重心分裂归约为简单情形，从而重新拼出共形网格并保持全局映射连续。

实验结果

方法在 C++ + GMP + CGAL 中实现，评测涵盖 TLC、CUB 两个已有数据集及作者新构造的六个数据集（基于 Thingi10K + TetWild/TetGen，映射到球、立方体、非凸双锥体），共 7500+ 实例。核心结论是可靠性：初始 3D Tutte 在所有实例上都非双射（成功率 0%），本方法在所有实例上都产出双射（100%），而两种代表性的尽力而为优化方法 TLC 与 FFM 在多数数据集上成功率明显偏低。

下表为主实验——各数据集上产出双射的成功率对比（本文 vs TLC vs FFM）：

数据集 实例数 本文成功率 TLC 成功率 FFM 成功率
TLC 46 100% 100% 100%
CUB 60 100% 58.33% 46.67%
TWS 2738 100% 69.10% 56.50%
TWC 1884 100% 79.56% 60.72%
TWN 2340 100% 57.91% 51.84%
TGS 249 100% 32.93% 38.96%
TGC 108 100% 44.44% 42.59%
TGN 166 100% 30.12% 30.72%

补充结论（文字）：绝大多数星形块很小（多数不超过 20 个四面体），说明局部化确实把修复限制在了缺陷附近；运行时间跨度极大（毫秒到数天），约 1% 的超大实例（\(\lvert C\rvert>150000\)、初始映射含大簇翻转）耗时超过一天，瓶颈主要在星形块生长时反复重解 LP 与线性化细化。在那 85 个对本方法最难的实例上，TLC/FFM 分别只成功 9 个和 0 个。把 Tutte→TLC→本方法组成三级递进（escalating）策略，可在几乎不牺牲双射保证的前提下显著压缩最长的那批运行时间。畸变方面本方法不作主要目标（最小雅可比行列式可正但接近 0），但把结果作为初值再跑一个保双射的畸变优化即可达到与 TLC/FFM 相当的水平。

亮点与局限

  • 亮点：
    • 按构造保证连续 + 双射，实验中 100% 成功，是三维里少有的带可靠性保证的构造类方法。
    • 把目标域从球/立方体推广到任意星形（含凸）域，并支持完整边界约束。
    • 局部化”星系”策略把重活压缩到缺陷附近的小块，效率相比全局施加可提升多个数量级；细化量也大幅减少（多数实例全局细化比 < 2）。
    • 可用精确有理算术实现，避免浮点误差破坏正确性保证；开源。
    • 可作为保双射后处理优化的可靠初值。
  • 局限：
    • 保证仅限星形域；对非星形域虽常能成功（858 个非星形实例成功 310 个）但无保证。
    • 可能较慢：星形块生长（反复重解 LP、精确算术）和线性化细化是两大瓶颈；极端实例可耗时数天。
    • 线性化会引入网格细化，改变原有网格连通性，可能给下游应用带来额外负担；文中也指出细化过程尚有较大优化空间。
    • 不以映射畸变为目标，需额外优化步骤才能得到低畸变映射。

延伸思考

  • 本方法把”可靠但慢”的构造与”快但不保证”的优化解耦，天然适配递进式流水线（Tutte→best-effort→本方法兜底），这种”用保证方法收尾”的思路可迁移到其它需要硬约束的几何构造问题。
  • 星形域是介于凸域与任意域之间的一个甜蜜点：既显著扩大了可处理域，又保留了叶线”直线段”的良好性质以便线性化。走向任意域可能需要分治或对目标域也做叶状结构，代价是失去直线段带来的便利。
  • 主要开销来自 LP 的增量重解与精确算术；增量式 LP 更新、过滤式精确谓词、以及更聪明的星形块生长顺序都是明显可加速的方向。线性化的细化膨胀问题（以及事后 decimation）也值得单独研究。