圣杯问题 I
波士顿三一教堂，姜健摄影。
（2016年九月27-30日，第二十五届国际网格生成圆桌会议在美国华盛顿召开（25th International Meshing Roundtable），受会议主席斯杭博士的邀请，老顾在会上介绍了如何用计算共形几何计算曲面和体的网格化。
斯杭博士是网格生成领域的绝对国际权威，久负盛名的传奇人物，目前在德国维尔斯特拉斯应用分析和随机研究所任资深研究员。老顾和斯博士神交已久，一见如故，通过热烈的讨论，深入交流了许多学术思想。经过数十年的积累沉淀，斯博士对于这一领域许多根本性问题具有非常深刻的见解，提出了大量的几何猜想。同时老顾结识了许多年轻才俊，思想的交流碰撞产生了许多火花，必将引发一系列的新颖算法。）
中国龙的三角剖分，斯杭作。
波音747飞机的空气动力学模拟网格化，斯杭作。
小白鼠的肺部气管混合网格，焦向民用TetGen作。
在漫长的教学和科研的生涯中，老顾经常和一线的纯粹数学家和一线的工程师合作，也正在指导数学方向和计算机方向的博士生。一些纯粹数学背景的学生和学者对于抽象深邃的理论如何在实际中应用产生深深的困惑，许多学生因为无法看到抽象数学（例如代数拓扑）的用途而缺乏深入钻研的内在动力。同时另一方面，工程师往往从实用角度出发，利用直觉经验设计各种技术方案，往往忽视构建严密的理论体系。对于简单的技术问题，这种发展方式行之有效，但是对于更为深刻的问题，因为缺乏理论的指导，很容易陷入瓶颈。在以商业利益为主导的工业界，理论研究一直是难得的奢侈；在以科研教育为主导的学术界，许多问题的规模和复杂程度超越了学者个人的想象能力，研究者往往缺乏第一手的实践经验，以及深刻的直觉和洞察，从而无法提炼思想精髓。如何将理论和实践有机结合，令人深思。这种现象在网格生成领域（Mesh Generation）体现得淋漓尽致。
网格生成问题
图1. CAD 模型。
在现代社会，几乎所有的工业产品都是在计算机上设计出来，一般都是用样条曲面来表示，因此计算机辅助设计（Computer Aided Design CAD）具有根本的重要性。
图2. CAE 模型，计算受力分析。
CAD模型在真正生产之前，需要在计算机上进行模拟仿真，计算其力学特性，从而改进设计。这类计算问题属于计算机辅助工程领域（Computer Aided Engineering CAE）。模拟仿真需要建立物理模型，往往是偏微分方程，然后利用有限元方法求解方程。例如波音公司大量使用CAE方法进行模拟仿真，从而减少风洞实验时间。
图3. 有限元方法需要将空间网格化。
有限元方法需要将曲面和空间网格化，从而将偏微分方程转化成代数方程，然后用计算机求解。如图3所示，为了模拟飞机的飞行情况，我们需要求解流体力学方程，这需要将飞机外围的空间网格化。网格的质量和数量会根本地影响计算结果的精度和速度。因此，毫不夸张地说网格生成（Mesh Generation）是整个现代工业的基础。
据纽约州立大学的陈世魁教授估计，每年全世界的CAD市场大概为5千亿美元，CAE市场大概为50亿美元。因为其巨大的实用价值，工业界和学术界都在竭尽全力地研究开发网格生成算法工具。斯杭博士独自开发和维护的TetGen系统，在业界极其著名，几乎所有这个领域的学者和工程师都曾经用过TetGen。同时，几乎世界上所有网格生成系统都曾参考借鉴过TetGen的算法。斯杭博士只手擎天地开发了TetGen，却从未从中谋求过任何经济利益，高风亮节，令人钦佩，堪称网格生成领域的Linus （Linux的发明人）。
四面体网格化
图4. 四面体网格化。（France Inria）
如图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三角剖分，这一问题长期以来悬而未决。经过大量的实验，斯杭博士认为这一算法也存在全局的拓扑障碍，并进一步提出了许多深刻的猜想。
图7. 黎曼映照将无穷小圆映到无穷小圆，从而保持Delaunay三角剖分。（马明作）
Delaunay三角剖分和共形几何之间存在深刻的内在联系。如图7所示，我们用黎曼映照（保角变换）将一张人脸曲面映到平面圆盘，人脸上的无穷小圆映到平面上的无穷小圆。Delaunay三角剖分的最主要特性就是“空圆性”，由此我们看到保角变换保持Delaunay三角剖分。因此曲面的测地Delaunay三角剖分可以被转化成平面Delaunay三角剖分。历史上，Delaunay三角剖分的算法提出于1970年代，共形几何算法提出于2000年左右，因此这种基于共形几何的曲面Delaunay网格化算法在工业界并不普遍。我们相信，在不久的未来，这一方法在实践中会日益普及。
但是，这一方法无法直接向三维推广。其主要的困难在于三流形间的保角变换基本上都是等距变换，因此我们无法用保角变换化弯为直。这一现象实质是由三维流形的Mostow刚性所决定。
六面体网格化
图8. 六面体网格化。（贺英作）
如图8所示，六面体网格化是将空间中的区域剖分，每个胞腔都是六面体。六面体网格具有四面体网格无法比拟的优越性。对于模拟大形变的物理现象，六面体网格更加灵活，四面体网格过于僵硬；对于同样的精度要求，六面体网格的体元数目远远小于四面体体元个数；据纽约州立大学的焦向民教授介绍，存在特殊的一类问题，其精度要求很难用四面体网格达到，只能用六面体网格才能达到。因此，在广大工业界和国家实验室，六面体网格被广泛使用。
相比于四面体网格化，六面体网格化非常不成熟，算法设计和理论理解都存在许多问题。目前，四面体网格可以自动生成，六面体网格的生成经常需要人工干预。同时需要用户积累的大量经验来事先将物体切割成简单形状。在许多工业研发部门，都有专门的小组专注于网格生成。就目前发展水平而言，六面体网格生成依然处于“艺术”阶段，而非“技术”阶段。由于工业界的强烈要求和算法理论幼稚原始之间的巨大落差，下列的问题被称为是网格生成领域的“圣杯”（Holy Grail）
对于给定的三维空间中的区域，具有复杂拓扑和几何，如何自动生成高质量的结构化的六面体网格？
这一问题又被称为是“神圣网格”（Holy Grid）问题。
数十年来，无数的工程师为此殚精竭虑，奋斗终生。他们发展了大量的复杂算法，开发了昂贵的商用软件，但是依然无法建立普适的几何拓扑理论和自动的算法来统一处理这一问题。
近期突破
图9. 亏格为三的曲面上的叶状结构。（雷娜，郑晓朋作）
在过去的学术访问中，老顾接触了许多学者和工程师，他们都不约而同的提到了神圣网格问题。焦向民教授告诉老顾：“这一领域的理论非常匮乏，任何理论的建立都是一个突破！”
关于非结构性的六面体网格的存在性理论，早在1980年代由菲尔兹奖得主瑟斯顿（Thurston）洞察到，其主要工具是微分拓扑，特别是光滑同伦理论，其主要的光滑同伦定理由另一位菲尔兹奖得主斯梅尔（Smale）证明。历经几十年的发展，理论上没有实质性改变，近期又由计算拓扑学家 Jeff Erickson用代数拓扑的语言加以厘清。
结构性的六面体网格的存在性理论，最近被大连理工大学的罗钟铉，雷娜团队和老顾合作共同创立，其理论根基是流形的叶状结构理论和黎曼面的亚纯微分理论。这一理论给出了复杂拓扑三维流形六面体网格的存在性证明，并给出了神圣网格的自动生成算法。美国三院院士(国家科学院，国家工程院，国家科学和艺术院），Thomas Hughes教授对于这项工作给与高度评价，他认为这项工作极其重要（Extremely Important）。相对于微分拓扑，叶状结构理论对于问题的刻画更为精致而深刻。在未来的系列文章中，老顾将会给出这一系列理论发展的历史脉络，和拓扑实质。囿于个人学识有限，错误之处在所难免，希望能够抛砖引玉，欢迎广大读者批评指导，更欢迎有心人一同钻研探讨！
请长按下方二维码，选择 “识别图中二维码”，即可关注。
【老顾谈几何】邀请国内国际著名纯粹数学家，应用数学家，理论物理学家和计算机科学家，讲授现代拓扑和几何的理论，算法和应用。