多边形建模

文章来自于翻译，有删减。来源是：https://isicad.ru/ru/articles.php?article_num=22791

对于大多数算法来说，仅仅把网格看作一组三角形是不够的，比如从STL格式转换得到的结果。对于这样的网格，你唯一能做的就是绘制它并计算面积。对于其他所有事情，我们需要有一种拓扑结构可供使用，这是多边形建模的基础。

这个结构有两个主要的组成部分。第一部分是网格拓扑，它描述了顶点、边和多边形之间的关系。它不仅支持三角形，也支持具有任意边数的多边形，或者说是面片。此外，它负责提供一些基本的基元操作，比如，有序遍历与选定面片相邻的面片，有序遍历某个顶点的扇区，进行边的折叠，插入顶点，扔掉边，等等。

通常，网格本身并不那么有趣，但与之相结合的是一种将面片划分为组的逻辑。这引出了拓扑的第二个组成部分：划分。它有着与标准B-rep模型相同的结构：相同的面、环和边，但是面是链接面片组的，边是由网格边的序列组成的。它也需要一组类似于网格拓扑的基本操作，如遍历相邻段，创建一个新的划分或使用给定的边或面片拆分现有的一个，合并一个或多个段，将边界面片从一个段转移到另一个段，等等。

插图显示了已有划分的分解。不同的片段以不同的颜色高亮，由一组边指定，这由黄色的折线指示。第二幅图是这次切割的结果。此外，每个拓扑元素必须被赋予一个抽象属性——它可以是一个数字，一个向量，一个表面，或者一个任意结构。

乍一看，所有已经讨论过的都是众所周知的事实，看起来非常容易实施。然而，如果我们考虑到所有的算法都是由这些基本操作组成的立方体，原来这是一项非常重要的工作，必须尽可能地认真对待。尤其是如果我们考虑到在算法的每个阶段都需要保持拓扑信息的相关性和有效性。但是结果是，我们得到了一个强大的通用工具，从这个基础开始，可以解决在多边形建模领域的任何问题。目前，我们完全是多边形建模的自给自足的开发者，不依赖任何第三方或开源解决方案或产品。

让我们来看看使用这种系统方法所得到的结果。总体来说，我们看到所有现有功能都有所改善，主要是加速。如今，对网格的基本处理归结为创建拓扑。在这个阶段，最明显的问题被消除了：重复的顶点、退化的三角形、重复的三角形、不一致的法线。此外，还关注了各种非流形的情况。布尔运算和3D凸壳分别加速了30-40倍。网格越大，加速越明显。如寻找开放边界或给定面片集的连通部分的边界等操作变得几乎微不足道。插图显示了对具有不一致法线的网格的处理。在第一个插图中，每个三角形相对于它的邻居都被翻转了，而在第二个插图中，是将网格恢复正常的结果。