静园5号院科研讲座 | 柏林工业大学Marc Alexa教授谈Harmonic三角剖分

关键词：Dirichlet energy, tetrahedral mesh

编者按

2019年8月25日，柏林工业大学的Marc Alexa教授受邀访问北京大学前沿计算研究中心，并在静园五院做了题为“Harmonic Triangulations”的主题报告。报告由中心执行主任陈宝权教授主持，听众包括来自北京大学信息科学技术学院、中科院计算所等单位的师生。

▲ Marc Alexa教授报告现场

Alexa 教授介绍了他发表在 SIGGRAPH 2019上的一篇工作：Harmonic Triangulations。这项工作引入 Harmonic 三角化概念：Harmonic 三角剖分使所有分段线性函数的 Dirichlet 能量最小。Alexa 教授证明了 flip 算法是调和的：如果它们降低了一组函数值的 Dirichlet 能量，它们就会降低所有函数值。这一观测结果提出了局部调和三角剖分的概念，及衡量三角剖分质量的方法。局部三角剖分可以有效计算，并有效地减少条状四面体，一般优于现有基于 Delaunay 三角剖分的算法。

Alexa 教授首先回顾了 Delaunay 三角剖分算法，接下来讲解 Harmonic 三角化的定义。首先引入 Dirichlet 能量，以及 PL function。由 Rippa 定理，引出 Harmonic 三角剖分的定义：使 PL function 梯度最小的三角划分。在二维情况下，Harmonic 三角化是存在的，即为 Delaunay 三角化。而在三维或更高维的情况下，Harmonic 三角化是不存在的。

▲ 在三维情况下的flip操作

Alexa 教授接下来介绍了 flip 操作的标准。对于 d 维空间中 d+2个点，最多有2种三角剖分。考虑任意的三角剖分，在其凸包中选取 d+2个点，如果梯度比另一种剖分大，则通过 flip 降低梯度。

在三维情况下：给定四面体的六个顶点，将一个额外的点 y 投影到四面体的6个面上，这构成了新的四面体。当新四面体退化时，可以认为原四面体质量好。注意到，当点 y 位于 Cayley modal cubic 上时，新四面体退化。在这种投影的基础上，引出了基于 Delaunay 剖分的 Harmonic filp 算法。在计算出 Delaunay 剖分后，遍历所有 Harmonic flip，对可操作的元素进行移动。将 CGAL 现有的优化算法与 Harmonic 进行对比，并将运行结果可视化。后者最小角小于25°的三角元明显更少，产生更少的四面体网格，有更好的形状。

▲ Harmonic与Delaunay三角剖分结果对比

▲ 陈宝权教授与Marc Alexa教授合影

文字 | 宋振华

Visual Computing and Learning (VCL)

往 期 报 告

—   版权声明  —

本微信公众号所有内容，由北京大学前沿计算研究中心微信自身创作、收集的文字、图片和音视频资料，版权属北京大学前沿计算研究中心微信所有；从公开渠道收集、整理及授权转载的文字、图片和音视频资料，版权属原作者。本公众号内容原作者如不愿意在本号刊登内容，请及时通知本号，予以删除。

点“阅读原文”看报告概要等信息