波士顿三一教堂，姜健摄影。

（2016年九月27-30日，第二十五届国际网格生成圆桌会议在美国华盛顿召开（25th International Meshing Roundtable），受会议主席斯杭博士的邀请，老顾在会上介绍了如何用计算共形几何计算曲面和体的网格化。

斯杭博士是网格生成领域的绝对国际权威，久负盛名的传奇人物，目前在德国维尔斯特拉斯应用分析和随机研究所任资深研究员。老顾和斯博士神交已久，一见如故，通过热烈的讨论，深入交流了许多学术思想。经过数十年的积累沉淀，斯博士对于这一领域许多根本性问题具有非常深刻的见解，提出了大量的几何猜想。同时老顾结识了许多年轻才俊，思想的交流碰撞产生了许多火花，必将引发一系列的新颖算法。）

在漫长的教学和科研的生涯中，老顾经常和一线的纯粹数学家和一线的工程师合作，也正在指导数学方向和计算机方向的博士生。一些纯粹数学背景的学生和学者对于抽象深邃的理论如何在实际中应用产生深深的困惑，许多学生因为无法看到抽象数学（例如代数拓扑）的用途而缺乏深入钻研的内在动力。同时另一方面，工程师往往从实用角度出发，利用直觉经验设计各种技术方案，往往忽视构建严密的理论体系。对于简单的技术问题，这种发展方式行之有效，但是对于更为深刻的问题，因为缺乏理论的指导，很容易陷入瓶颈。在以商业利益为主导的工业界，理论研究一直是难得的奢侈；在以科研教育为主导的学术界，许多问题的规模和复杂程度超越了学者个人的想象能力，研究者往往缺乏第一手的实践经验，以及深刻的直觉和洞察，从而无法提炼思想精髓。如何将理论和实践有机结合，令人深思。这种现象在网格生成领域（Mesh Generation）体现得淋漓尽致。

网格生成问题

在现代社会，几乎所有的工业产品都是在计算机上设计出来，一般都是用样条曲面来表示，因此计算机辅助设计（Computer Aided Design CAD）具有根本的重要性。

CAD模型在真正生产之前，需要在计算机上进行模拟仿真，计算其力学特性，从而改进设计。这类计算问题属于计算机辅助工程领域（Computer Aided Engineering CAE）。模拟仿真需要建立物理模型，往往是偏微分方程，然后利用有限元方法求解方程。例如波音公司大量使用CAE方法进行模拟仿真，从而减少风洞实验时间。

有限元方法需要将曲面和空间网格化，从而将偏微分方程转化成代数方程，然后用计算机求解。如图3所示，为了模拟飞机的飞行情况，我们需要求解流体力学方程，这需要将飞机外围的空间网格化。网格的质量和数量会根本地影响计算结果的精度和速度。因此，毫不夸张地说网格生成（Mesh Generation）是整个现代工业的基础。

据纽约州立大学的陈世魁教授估计，每年全世界的CAD市场大概为5千亿美元，CAE市场大概为50亿美元。因为其巨大的实用价值，工业界和学术界都在竭尽全力地研究开发网格生成算法工具。斯杭博士独自开发和维护的TetGen系统，在业界极其著名，几乎所有这个领域的学者和工程师都曾经用过TetGen。同时，几乎世界上所有网格生成系统都曾参考借鉴过TetGen的算法。斯杭博士只手擎天地开发了TetGen，却从未从中谋求过任何经济利益，高风亮节，令人钦佩，堪称网格生成领域的Linus （Linux的发明人）。

四面体网格化

如图4所示，给定三维欧式空间中的一个区域，我们将其三角剖分，每个胞腔都是四面体，这种网格化被称为是四面体网格化（Tetrahedral Meshing）。四面体网格化算法基本上是基于所谓的Delaunay三角剖分。

如图4所示，给定三维欧式空间中的一个区域，我们将其三角剖分，每个胞腔都是四面体，这种网格化被称为是四面体网格化（Tetrahedral Meshing）。四面体网格化算法基本上是基于所谓的Delaunay三角剖分。

图5. Delaunay三角剖分。

图5解释了Delaunay三角剖分的概念：给定平面一组离散点，构造一个三角剖分，使得每个三角形的外接圆内不包含第四个点。在三维情形，我们构造四面体剖分，使得每个四面体的外接球不包含第五个点。Delaunay三角剖分使得最小内角最大化，从而提高数值模拟的稳定性，因此成为网格生成算法的根基。

Delaunay三角剖分算法于1970年代被发明出来，由此诞生了“计算几何”这一学科。从此，计算几何领域的主旋律一直是Delaunay三角剖分。经过数十年的发展，Delaunay三角剖分算法日趋成熟，目前自动四面体网格生成问题已经被解决，并且在工业界得到广泛应用。

计算几何领域的翘楚- Herbert Edelsbrunner 基于Delaunay三角剖分技巧开创了知名的Geomagic公司，主要应用于点云重建。Geomagic于2013年被3D Systems收购，成为3D打印工业不可或缺的软件工具。

与之成为鲜明对比的是斯杭博士的理想主义历程。斯杭博士开发的TetGen在工业界影响广泛，其核心算法被许多商业软件无偿借鉴和使用，极大地推动了网格生成算法的普及和推广，对于CAD和CAE领域的发展，起到了不可取代的推动作用。

斯杭博士告诉老顾这段历史：在他开发TetGen系统之前，世界上只有法国Inria（法国国家计算机与应用数学研究所）开发的一个商业软件，Tetmesh-GHS3d, 这是由一个团队开发三十年的成果，基本上所有大型的有限元商业软件，例如Ansys，都用GHS3d来做四面体网格生成。斯杭博士独力开发了TetGen，在许多关键技术上都超过了GHS3d，这一点在国际网格生成领域得到广泛承认。

图6. EdgeSwap操作。

经验表明，平面Delaunay三角剖分可以如下生成。给定平面离散点集，我们从任意一个三角剖分开始，任给一条边，与其相邻的两个三角形构成一个四边形。如果与此边相邻的两个三角形不是Delaunay，如图6左帧所示，则将此边替换成四边形的另外一条对角线，如右帧所示。这种操作被称为是换边操作（Edge Swap）。那么经过一系列换边操作，我们一定能够得到一个Delaunay三角剖分。斯杭告诉老顾，虽然算法非常成熟，并且理论上有严格证明，但是反过来，从Delaunay三角剖分经过一系列的换边操作到任意给定的三角剖分，如果要求换边操作具有某种单调性，则不存在理论上的完整证明。斯博士认为存在本质的拓扑障碍。同时，类似的算法是否可以求三维Delaunay三角剖分，这一问题长期以来悬而未决。经过大量的实验，斯杭博士认为这一算法也存在全局的拓扑障碍，并进一步提出了许多深刻的猜想。

Delaunay三角剖分和共形几何之间存在深刻的内在联系。如图7所示，我们用黎曼映照（保角变换）将一张人脸曲面映到平面圆盘，人脸上的无穷小圆映到平面上的无穷小圆。Delaunay三角剖分的最主要特性就是“空圆性”，由此我们看到保角变换保持Delaunay三角剖分。因此曲面的测地Delaunay三角剖分可以被转化成平面Delaunay三角剖分。历史上，Delaunay三角剖分的算法提出于1970年代，共形几何算法提出于2000年左右，因此这种基于共形几何的曲面Delaunay网格化算法在工业界并不普遍。我们相信，在不久的未来，这一方法在实践中会日益普及。

但是，这一方法无法直接向三维推广。其主要的困难在于......

本文转载于技术邻，未经授权不得转载！！！如果您想要了解更多内容可以搜索技术邻哦