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

 

  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教授合影