GCL学术成果：SIGGRAPH Asia 2024—用于网格排列的精确高效相交消除算法
【论文标题】Exact and Efficient Intersection Resolution for Mesh Arrangements
【作者】郭佳鹏，傅孝明
【单位】中国科学技术大学
【背景与问题】
网格排列将相交的三角网格转换为适当的形式，同时保留输入的几何形状。它为许多高级算法（例如网格修复、布尔运算和体积网格剖分）提供了基础。本文重点关注网格排列的关键初始阶段：在不对输入做任何额外假设的情况下处理任意三角形集合，并输出一个无交集且保持原始几何一致性的单纯复形（见图1）。
【解决方案】
这篇论文提出了一种精确且高效的三角网格相交消除方法，包含两个关键部分。首先，我们引入了一种新型几何谓词，称为“间接偏移谓词”。通过新的公式表示所有交点，并建立了所有必要的几何谓词，从而有效减少了浮点运算中的数值误差，提高了算术过滤早期阶段的成功率。这一方法充分利用了几何元在构造交点时的局部性，将隐式点的表达构造为基部分和偏移部分的和，使得涉及隐式点的谓词仅包含坐标差值项。由于交点构造中的局部性，坐标差值通常比坐标值本身小几个数量级，从而在半静态浮点过滤期间进一步降低了数值误差，提高了过滤器的成功率。
进一步，我们在已有算法的基础上扩展并优化了这些谓词，以提升算法的效率。我们构造了一种新的隐式点以简化表达已有交点；我们将交点去重过程局部化以避免使用全局映射方法，这种局部化显著减少了排序规模，增强了并行性。此外，为减少计算开销大的谓词调用次数，我们通过将三角形投影到正交平面，将受约束的三角化简化为二维问题，并挖掘出三角化算法的新性质，从而进一步简化了交点定位和重新三角化过程。
【实验结果】
我们在Thingi10k数据集以及一个压力测试数据集（通过多次旋转一个模型并将其组合而成）上对算法进行了测试，以验证其鲁棒性和效率。与最先进的方法相比，我们的算法效率提高了一个数量级。详细的统计数据与分析请参见论文。
【技术贡献】
- 引入了“间接偏移谓词”这一新型几何谓词概念，并提出新的隐式点形式用以精确表示交点并减少浮点运算中的数值误差。
- 开发了局部化技术用于高效排序、去重和定位交点，显著提升了算法的效率和并行性。通过开发降维技术将受约束的三角化简化为二维问题并挖掘新性质，进一步简化了交点定位和重新三角化过程。
【论文发表】
该工作已被计算机图形学顶会SIGGRAPH Asia 2024接收，并将发表于顶级期刊《ACM Transactions on Graphics》。该期刊2023-2024年度影响因子为7.8，是计算机科学与软件工程领域的一区刊物之一。
【论文原文】
Jia-Peng Guo, Xiao-Ming Fu. Exact and Efficient Intersection Resolution for Mesh Arrangements. ACM Transactions on Graphics (Proc. SIGGRAPH Asia), 43(6),2024.