Mesh is Art (1): Mesh

#前言
我一直认为这样写学习笔记总结是最好的学习方式，一方面能系统地梳理自己的知识框架，另一方面能促进不断地思考，加深自己对一些概念的领悟。先介绍下自己，我是一名美术生，虽说高中数学成绩一直名列前茅，但大学后数学也就没怎么碰了。本科是环境设计，对参数化设计痴迷向往，但是随着技术的不断精进，渐渐意识到很多所谓的参数化设计其实是伪参数化，之后的很长一段时间都陷入一种苦恼，就是那种知道这是未来但是没有明确方向。

后来阅读了清华大学代数拓扑专家顾险峰教授的相关文章，意识到参数化设计真正的核心应该是“量化”和“映射”。然而要想实现对形体的**“量化”和“映射”，网格处理是最关键的技术，借助网格才能将数字转化成形体，才能更容易地建立设计中的“概念”与实际形体地映射关系**（Nurbs与网格相比并不是很好的选择，原因就不在这里提了）。在那之后便开启了我的网格技术学习之路。通过两年多的学习和理解，现在已经成为了一名助理研发工程师（网格算法方向）。但仍然无奈于没有系统地学过代数拓扑和微分几何，很多概念只是道理上有了一定的理解，无法从数学上去严格地证明（说白了就是因为不懂数学，心里没底），只能从逻辑上去推导着理解网格的相关知识。不管怎么说，这次重启网格学习笔记就是为了梳理一遍自己的最底层理解，去寻找一些看似约定俗成的事物的背后的原因。

有趣的是，在学习网格技术的过程中，随着我对网格技术的理解越来越深，在处理一些复杂的设计问题上，能很轻易地找到了各种简单、巧妙的方法。比如建筑上，基本所有的节点形式都可以表达成网格，各种看似复杂的节点或幕墙设计都能轻松地运用网格表达出来；各种复杂的结构，做有限元分析时能够很自然地划出均匀、高效的有限元单元；在做造型设计时，也有了很强的布线能力。工作中经常体会到“刚刚好就应该是那个样子”的感觉。我想说的是，网格思维真的是一种非常棒的设计思维、几何思维，网格不只是一种建模工具，Mesh is Art！

网络上对于网格技术的信息非常非常少，虽然本系列文章也是不专业的，但我想对于设计师这个群体而言，认真读完这个系列文章之后应该能有所收获，至少能加深对一些软件的理解能力，在学习软件的路上走得更快一些吧。

#网格建模简介
大家都了解过CAD软件，例如Auto CAD、Rhinoceros、Maya、3D MAX等等都是工业界和设计界常用的软件。通过这些软件，我们可以在软件中的虚拟空间建立二维、三维模型，实现对脑海中所想像出的形体进行建模，这样无论是生产制造还是设计，我们都有了直观的参考，不需要再像以前一样通过理解图纸加上想像去费时费力地推测形体本身的样子。那么，计算机是如何建模表达这些三维模型的呢？

学过了高中数学，我们知道可以通过构建坐标系去实现各种形体的绘制。有了坐标系，我们能在空间中绘制各种各样的曲线或者图形。然而，像曲线这样的连续几何体是不可能完全精准的表达成图形的（即便是计算机也不能），计算机的表达方法和我们高中画函数的方法其实如出一辙，就是在空间中插值取点的方法，离散地来表达形体。比如绘制一个二次函数的函数图像，我们需要通过均匀地插值取点，然后用直线段顺次连接，最终得到一条折线(Polyline)，当取无数个插值点时，就可以近似拟合成曲线了。

那么，根据上面的例子，我们发现，对于一条曲线的表达，通常是用线段去拟合的（每条线段是由两个点加一根线构成的，两点一定共线）把曲线用若干条线段的过程叫做离散化。以此类推，我们不难想到，曲面的表达是用三角面去拟合的（因为每个三角面是由三个点加三条线构成的，三点一定共面，三角形是最简单的平面图形）。线段和三角形都可以称为其所处维度的单纯形（代数拓扑）。一维单纯形就是线段；二维单纯形就是三角形；三维单纯形就是四面体。

有了单纯形，我们就可以用它来表达生活中能见到的所有形体（通过将形体离散成若干个单纯形的方式）。现在我们再说回到计算机表达，通过单纯形，计算机可以将任何形体用三角形或四面体表达（这里主要说二维和三维，一维的线可以看作三角形和四面体的子集），像这种用三角形或四面体表示形体的建模方式称为网格建模，说网格通常指的就是三角形或四面体（当然还有其他形式，这里先不做展开）及所构成的图形。

#网格的应用
在引言中，相信大家对网格有了基本的认识，对于网格在各行各业的应用，我们就直接来看图吧。

• 对于建筑设计师来说，理解了网格可以使用算法生形，提高建模的效率和建模质量，对接其他工程师可以降低沟通成本。风环境、光环境、热环境等各种可视化分析均与网格质量密切相关。
• 对于幕墙设计师来说，理解网格可以快速生成曲面的幕墙嵌板模型，可以利用细分算法变换嵌板类型，利用平板算法降低幕墙造价，利用网格几何特性减少嵌板数量及安装复杂度。
• 对于结构（机械）工程师来说，理解网格可以更好地使用有限元计算，对于合适的模型采用合适的网格划分。在拓扑优化中可以用网格算法进行后处理。
• 对于CG艺术家来说，理解网格有助于提高建模质量，理解贴图、渲染等技术。

#网格的基本单元

这里我们再回到单纯形的解释，前面说了网格通常指三角形、四面体及它们所构成的图形。这里还有一些值得一提的点，我们先来设想这样的问题，对于一个球体的表达，可以有两种认识：其一是将球认为是球的外壳，即我们将这个球看作一个闭合成球这个形状的曲面，生活中举例的话比如足球，只有外皮，里面是空的；另一种是将球认为是填实的实体，举个例子就比如雪球，里面都是雪，很厚实。这两种表达方法各有优劣，对于“球壳”来说，我们对它进行一些剪切、拼贴、变形等操作都相对较容易，在网格处理上大多都会选择这样的表达方法，如Rhinoceros、Maya；对于实体球来说，一般用于结构工程的有限元分析，可以想象，结构分析当然要认定一个结构体是密闭填实的，只计算“外皮”和计算实体是完全不同的两个概念，因此在计算一些需要考虑到内部填充的操作时必须将物体考虑成密闭实体，这类软件的代表就如结构专业常用的有限元分析Abaqus。相信大家也猜到了，前者的单纯形就是三角形，后者是四面体。由于四面体填充的形式一般仅在结构分析中会涉及，非结构和计算机专业的人一般不会过多去关注这方面，本系列笔记也是介绍二维单元作为网格基本单元的情况。

理解了为什么要用二维单纯形作为网格基本单元后，我需要再补充一下，网格的基本单元除了三角形还有四边形（四边形不叫作单纯形了，但仍然是网格的基本单元）。为什么又多了一个四边形呢？这里又得提两个概念了，结构化网格和非结构化网格。**结构化网格是说，这个网格模型的大多数顶点所连接的网格面的数目（网格顶点的价）是相等的。**如果这句话现在理解不了也没关系，因为大多出情况都没有那么严格，比较直观的理解就是一张网格拟合的曲面，看上去结构线清晰分明就是结构化网格（如图5、6）。非结构化网格就是与结构化网格相对，看上去乱七八糟的单元排布就是非结构化网格。通常我们得到的三维扫描模型都是非结构化网格，这样的网格如果每个网格面片的大小近似相等的话那还好说，但是如果大小变化剧烈，就很难继续编辑，网格质量糟糕，一般必须通过算法或人工重建才能继续使用。



然而四边形，作为具有明显方向特征的基本单元，通常就被用作表达结构化网格了。四边形网格和三角形网格的特性如图8所示。

#网格的数据结构

阅读到这大概对网格有了一个感性的认识了，对于好奇心比较重的你可能会发问：计算机是如何识别出这是一个三角网格（或四边网格）的呢？（我们这里先不讨论颜色）

实际上计算机并不认识图形，要想让计算机知道，哦这里有一个三角面，那就必须用逻辑关系来表达出来。比如我们知道，三角面由三个顶点三条边和一张面构成（点线面全了），那么，顶点在空间中能表达出来，就是三个三维坐标嘛；边可以看作是两个顶点放在一起，也就是一个有顺序的，从一个三维坐标到另一个三维坐标的关系；面则可认为是三条边有序排列在一起的关系。再傻瓜一点说，就是空间三个顶点A、B、C，我把顶点A和顶点B放在一起就能表示从A到B这条边，其他边的表示依次类推，面的表示就是把三个顶点按照某一顺序放在一起就是一张面。

也就是说，网格最最底层的构成就是顶点的坐标和它们相连的关系。由此引出，网格的存储信息分为两部分，几何信息（顶点坐标）和拓扑信息（顶点连接关系）。

网格模型的数据存储有很多种方式，当前数据结构有很多，篇幅关系我这里说两个最常用的，Faced-Based Data Structures和Half-Edge Data Structure。

Faced-Based Data Structures是最简单直观的数据结构，说它直观是因为它就是上文我们所说的，只存储了顶点坐标和顶点拓扑关系两种数据的数据结构。但看似简单的东西其实也还有玄机，这里暂且不谈，下一节将焊接和法向的时候会再提出来的，现在只要有个感性的认识即可。

 Half-Edge Data Structure直译就是半边数据结构，半边是非常好用的网格数据结构，它在相邻元素查找的问题上十分方便。这种数据结构是以网格边为主导的，是将每条边分成两条半边，这两条半边的长度与原网格边相同，但是方向相反。可以理解为把一条边拆成了两个方向相反、长度相同的向量，向量都是有始有终的，因此可以很容易将一个网格的所有半边首尾相接连起来，这也正是这种数据结构的妙处所在。具体的内容也在后面会详细解析，这里说太多反而容易把读者绕晕。

总之在这里我们只需要知道一点，在解决不同的网格编辑问题时，数据结构的选择非常重要，在运行程序时，合适的数据结构能大大提高运行效率，同样的算法，用不同的数据结构来实现，其运行效率会有很大的差别。

一般来说，判定一个网格的数据结构是否适合解决这个问题的依据有以下几点（现在理解不了可以后面靠实践去体会）：
      （1）构建数据结构的时间复杂度
      （2）进行查询操作的时间复杂度
      （3）网格编辑操作的时间复杂度
      （4）空间复杂度

作为笔记的第一篇，我想讲的详细一些，里面内容很多是我查阅的资料加上自己的理解。由此可见，对网格有一定程度（几何上）的理解根本不需要什么高等数学，初中数学足以。相信本系列笔记会对大家有所启发。

下面是网格数据结构相关的资料链接，放出来供大家学习参考：

https://mrl.nyu.edu/~dzorin/ig04/lecture24/meshes.pdf

https://www.jianshu.com/p/464cda593ac1

https://blog.csdn.net/wozhengtao/article/details/51430025

作为笔记的第一篇，我说了很多我自己的底层认识，看完的朋友应该也能感觉到，理解网格根本不需要什么高等数学，初中数学足以。有了这些认识，在平常的建模和设计过程中，可能就会有更多的角度和思路去看待问题。当然仅是这一篇还远远不够，有兴趣的童鞋可以关注一下，希望本系列笔记会对大家有所启发。