★ FEATURED ARTICLE 多边形网格处理是计算机图形学和几何建模里绕不开的基础课尤其是第二章讲的内容通常是一个建模系统或者网格处理框架的地基。很多人学到这里会觉得枯燥一堆数据结构定义、邻接关系、遍历方法看起来离“做出效果”很远。但恰恰是这些看似枯燥的东西决定了你后面做网格简化、细分、形变、参数化时代码能不能写得优雅、性能能不能撑得住。这篇文章我想从实际工程的角度把这章的核心内容拆开揉碎了讲。我会结合自己踩过的坑和积累的经验把网格数据结构的设计思路、半边结构Half-Edge的实现细节、以及常见操作背后的原理讲清楚。不管你是刚入门图形学的新手还是已经写过一些网格处理代码但总觉得哪里没想明白的开发者这篇文章应该都能给你一些启发。1. 从“存三角形”到“管拓扑”数据结构选型的底层逻辑1.1 为什么不能只用一个顶点数组很多初学者第一次写网格相关的代码时最容易想到的表示方法就是用一个大数组存所有顶点坐标再用一个大数组存所有三角形。每个三角形由三个顶点索引构成画的时候直接按索引取坐标就行。这种表示方法在OpenGL里画模型完全够用代码写起来也异常简单。但如果你真的要写一个网格处理库比如要对网格做平滑、简化或者形变这种“顶点索引 三角形索引”的表示法很快就捉襟见肘了。原因在于你要频繁做“查询”和“修改”操作而这些操作在这种朴素表示下效率极低。举个例子假设你要对平坦区域做一个简化操作——把某个边坍缩成一个顶点。你首先需要知道这条边的两个端点分别是哪些面的公共边也就是说你需要知道每条边被哪些三角形共享。在朴素的索引表示下你只能把整个三角形列表扫一遍逐个检查哪几个三角形包含这两个顶点以及它们的公共边顺序。这个操作的时间复杂度直接退化成O(N)当网格有几百万个三角形时每做一次边坍缩就要全网格扫描一遍整个流程根本跑不动。更麻烦的是修改操作。当你把一个顶点位置调整后所有共享这个顶点的三角形的法线、面积、邻接关系都需要更新。如果你不知道哪些三角形用了这个顶点你就又得全网格遍历一遍。每帧渲染前做一次全遍历还能接受但算法迭代几十次甚至上百次每一轮都要做全局扫描这就完全不现实了。1.2 核心矛盾查询需求与存储结构的博弈网格处理本质上需要回答的问题就几类给定一个顶点找出所有共享这个顶点的三角形“顶点的一环邻域”。给定一条边找出共享这条边的三角形。给定一个三角形找出它的三个邻居三角形。给定一个顶点找出从它出发的所有边。这些查询需求非常高频任何一个像样的网格处理算法都会大量用到它们。如果你把每个查询都做成全网格扫描那不管算法本身设计得多精巧跑起来都会让人崩溃。所以这章的核心内容就是设计一种数据结构让这些高频查询能高效完成同时保证修改操作不至于让结构瞬间失效。这里需要理解一个关键概念——拓扑关系。网格处理时我们通常把几何信息和拓扑信息分开看几何信息是顶点的坐标、法线、纹理坐标这些数值拓扑信息是顶点、边、面之间怎么连接谁跟谁相邻。朴素的“顶点数组三角形数组”能表达几何信息但拓扑信息只能靠反复扫描现算而像半边结构Half-Edge这样的数据结构本质上是把拓扑关系显式地存储下来用空间换时间。当你理解了这一层就会明白为什么教材里花了那么多篇幅讲数据结构——这不是为了考试而是每一个网格处理算法能否落地的关键。1.3 面片邻接信息为什么不能只存“邻居面索引”有些人会觉得那我给每个三角形额外存三个邻居三角形的索引不就行了吗这个思路方向是对的但实现上有几个问题。第一你存的是“面-面相邻”关系但很多算法需要的是“顶点-面相邻”或者“边-顶点相邻”。比如做Laplacian平滑时你需要拿到一个顶点的所有邻居顶点这个操作用面-面关系来做中间要绕好几层。第二当你做编辑操作比如把一条边一分为二、插入一个新顶点时所有相关三角形、顶点的邻居关系都要更新。如果你只存了面-面关系那么更新范围很难界定——你不知道除了直接邻接的面之外还有哪些面间接依赖了这个关系。第三面-面关系没有方向信息。网格处理中经常需要知道“从某个面穿过某条边会走到哪个面”但更细化的问题如“这条边在三角形里的哪一侧”也很关键。比如你在做法线传播时必须知道穿过某条边后新面的朝向与旧面的朝向是否一致。没有方向就丢失了半边顺序的信息很多判断无从下手。这些问题综合起来就指向了一个更优雅的解——半边结构。这也是多边形网格处理课程第二章的核心内容用一个带方向性的半边概念把顶点、边、面的关系全部串联起来。2. 半边结构Half-Edge深入拆解核心机制与设计哲学2.1 半边到底是什么一次从“边”到“方向”的思维升级半边结构的核心思想很朴素把一条无向的边拆成两条有向的半边half-edge。一条边连接两个顶点所以它对应两个方向各异的半边。每个半边“从某个顶点出发指向另一个顶点”并且归属于一个相邻的面。这里最关键的是“与面绑定”的设定。对一个闭合流形网格来说每条边恰好被两个面共享边界边只被一个面共享半边结构对边界有额外处理。所以当你从一个半边的起点出发沿着这个半边走到终点再“顺着这个面的下一条半边”继续走就能绕成一个环正好把所属面的所有边遍历一遍。为什么叫“半边”而不是直接叫“有向边”因为它的核心作用是统一了三种拓扑元素的关联半个边归属于一个面面上按逆时针或顺时针顺序绕着走。每一条边对应两个半边彼此通过孪生半边twin/sibling half-edge互相查找。每个半边都对应一个起点顶点。一旦建立了这种结构你能迅速回答前面所有的高频查询要找一个面的邻居就沿面绕着走一圈每条半边取孪生半边看它落在哪个面里要找一个顶点的一环邻域就从某条从该顶点出发的半边出发绕一圈遍历要找一条边的两个邻接面就直接取这条边和它的孪生半边各自所属的面即可。2.2 边界处理边界半边与“虚拟面”的约定闭合网格比如一个球体的每条边都有两个邻接面于是半边总能成对出现。但现实中的网格大多是开放的比如一块布料、一栋建筑的表面、一个杯子的外形——它们都有边界边边界边只有一个邻接面。半边结构处理边界有两种常见方案。方案一给每条边界边创建一个特殊的“虚拟面”有时叫无穷面或边界环把边界半边也配对。这样做的好处是代码逻辑统一半边一定有孪生半边缺点是“虚拟面”要特殊标记处理时容易漏判。方案二允许半边存在“孪生半边为空”的状态。也就是说某个半边是边界半边时它的对偶指针指向空。这种方案实现更直观但在编写遍历算法时每步都要检查孪生半边是否为空代码会多一点条件分支。我个人在项目里更推荐方案一因为后续很多算法比如与邻域相关的几何计算都假设“闭环遍历”有了虚拟面可以避免处处判断空指针。当然代价就是你在构建网格时必须对所有边界边单独创建虚拟面。提示无论选哪种方案都要在数据结构里明确标注一条半边的“边界状态”。否则当你做网格简化时把一条边界边坍缩成顶点后整个边界环会变得混乱不堪调试起来极其痛苦。2.3 网格简化中实际遇到的问题引子有了半边结构许多算法的实现复杂度瞬间下降。以边坍缩为例你要把一条边塌成一个点在朴素表示里需要扫描所有三角形找出包含这两个顶点的三角形集合。判断这条边是否是边界边、两顶点的公共邻域是否闭合。手动合并所有受影响三角形的顶点索引小心处理三角形退化面积为零的三角形。每一步都很容易出错而且很难做到高效。而在半边结构里边坍缩的“该合并哪些面、哪些面不受影响、边界如何更新”全都天然地由半边拓扑关系决定了。你把共享这条边的那两个三角形删除然后把与该边两个端点相关的半边的起点逐一调整到新顶点再更新相应的半边归属关系即可。整个操作是局部修改涉及范围极小时间复杂度为O(1)或者O(邻域大小)与网格总规模无关。这就是为什么说“数据结构选型决定了算法的效率”——这句话在网格处理领域体现得淋漓尽致。3. 从零搭建半边结构核心实现步骤与代价分析3.1 节点定义顶点、半边、面一个都不能少我把半边结构最常见的定义方式用类似C的伪代码列出来方便你对照理解。struct Vertex { Vec3 position; // 几何坐标 HalfEdge* outgoing; // 从该顶点出发的任意一条半边 }; struct HalfEdge { Vertex* origin; // 这条半边从哪个顶点出发 HalfEdge* twin; // 孪生半边对偶边 HalfEdge* next; // 同面内下一条半边逆时针/首尾相接 Face* face; // 这条半边所属的面 }; struct Face { HalfEdge* halfEdge; // 属于该面的任意一条半边 };这三个结构加上可以扩充的附加属性如边的权重、面的法线等就能完整表达一个多边形网格的全部拓扑关系。这里需要特别说明一个容易被新手忽略的点next指针遵守的方向规则。标准约定是在一个面内从一个半边出发沿着next指针按逆时针方向绕一圈能正好遍历该面的所有半边并回到起点。这个约定一旦建立所有遍历代码就统一了。3.2 从输入索引到半边网络的完整流程假设你已经有一个“顶点坐标数组 三角形索引数组”的网格要把它转换成半边结构分三步做分配基础结构体遍历所有顶点为每个顶点分配一个Vertex填充位置信息遍历所有三角形为每个三角形分配一个Face结构体但此时先不填充halfEdge指针。创建半边并建立next链每个三角形有三条边对应三个三角形内的有向半边逆时针方向。把这些半边创建出来每个顶点记录一条出边每个面记录第一条半边然后为每个三角形内部的三条半边设置next指针让它们首尾相接成环。填充twin指针这一步是核心中的核心。遍历每一条半边在整体的半边集合中寻找是否存在一条与之共享两个端点但方向相反的半边。如果存在建立互指关系如果不存在说明这条是边界半边twin指向空或按方案一做特殊处理。第3步的朴素实现是O(H^2)的H是半边总数。优化方式是构建一个哈希表以“无向边”作为键即把两个顶点的索引按大小排序后拼接成键值是该无向边对应的两条半边中的一个。这样你遍历半边时只要查到同一个键下已存在半边就能直接配对填好双向指针整体复杂度降到O(H)均摊。构建完成后我强烈建议写一个自检函数遍历所有半边检查twin的twin是不是自己、next链能否从任意半边出发回到自身、每个面的halfEdge能不能绕一圈覆盖所有顶点。这种自检查一遍能过滤掉绝大多数构建时的低级错误。3.3 核心遍历原语让一切操作变得简单构建出结构后你要熟练几个遍历原语它们是所有高级算法的基石。遍历一个面的所有顶点HalfEdge* h face-halfEdge; do { Vertex* v h-origin; // 处理v h h-next; } while (h ! face-halfEdge);遍历一个顶点的所有相邻面俗称“绕点转圈”HalfEdge* h vertex-outgoing; do { Face* f h-face; // 处理f h h-twin-next; } while (h ! vertex-outgoing);这段代码的意思是从某条出边出发进入该半边所属的面然后转向孪生半边沿着下一半边继续就能绕顶点走一圈。对这种遍历暂时看不明白也没关系实际写几遍就记住了。它是网格处理中最重要的循环之一几乎所有局部算法都会用到它。遍历一条边的邻接信息直接取半边和孪生半边的origin/face即可无需任何遍历。有了这三种原语你去看很多论文伪代码比如Remeshing、Simplification、Smoothing都会觉得豁然开朗——原来那些复杂的邻域操作落到代码层面就这几招。4. 实操现场我来带你把一个网格简化操作跑通有了基础数据结构下面我们实打实做一件小事用一个简单的边坍缩操作来验证半边结构的效果。为什么要选边坍缩因为它涉及的场景足够多能很好地展示半边结构是如何简化问题的。4.1 准备工作读入网格并转成半边结构我用一个标准的面片模型来演示比如一个随机的扫描模型几万面量级。读入格式我就用最简单的OBJ因为OBJ里自带顶点索引和面索引转半边结构非常顺手。读入完成后第一件事是“统一朝向与封闭性检查”。检查所有三角形是否按一致的方向比如逆时针排列。如果OBJ里部分面是顺时针、部分是逆时针半边的next链会绕出错误方向后续几何量计算也会出问题。我的做法是对每个三角形计算法线以模型重心为参照判断法线是否朝外。发现翻转的就交换该三角形的两个顶点索引。这个预处理非常重要值得单独用一个pass来做。4.2 一种可复现的边坍缩实现边坍缩的目标选定一条边(u, v)把v合并到u删除与该边相邻的两个三角形更新相关顶点与半边关系。具体步骤用半边定位边和两个邻接面。从任意半边h出发h-origin记为uh-twin-origin记为vh-face和h-twin-face就是要删除的两个面。收集受影响的顶点和半边集合。遍历u和v的一环邻域找出所有以u或v为origin的半边以及所有以u或v为终点的半边通过遍历面的next链获得。删除两个面并把指向被删面的半边全部重定向到未删除的面上。这个“重定向”需要小心处理两个相邻面的边界我直接遍历受影响的半边列表遇到face指向被删面就改成相邻体的面。将v的所有出边改成从u出发。简而言之找到v-outgoing把它以及沿twin-next绕回v的所有半边把它们的origin改成u。更新u的几何坐标为新位置并更新u-outgoing。随后删除v和两个被删面检查所有受影响三角形的退化情况面积小于阈值就标记为待删除。在真实实现时你可能只需要两个小时就能写完但调试可能要花一天。最常见的bug来源就是遗漏了某条半边的面指针更新导致后续遍历跳到了已被删除的面。4.3 踩坑记录三个最容易搞错的细节第一半边的next链别破坏了。在边坍缩里你删除了两个三角形也就是说删除了六条半边。删除后剩下的半边中凡是原本next指向这六条半边之一的都要重新指向新的下一半边。这一步如果漏了后面的遍历全是乱走排查起来特别费劲。第二不稳定坐标下的三角形朝向。边坍缩后有些三角形的三个顶点几乎共线面积趋近于零。如果在这些退化三角形里继续做后续处理法线方向会剧烈抖动甚至引发数值问题。稳妥做法是在坍缩完成后扫描受影响区域如果退化立即删除该三角形并修复局部拓扑。第三边界状态的变化。坍缩前你判断过这条边是内部边还是边界边。内部边删除两个面边界边只删除一个面。这两种情况下需要更新的半边数量差异很大。我刚开始实现时统一代码逻辑处理边界边结果在退化三角形判断上出了不少错。后来改为把边界边单独用一套分支逻辑处理问题就清晰多了。注意如果你的数据模型在后续还会反复做参数化比如展开成平面贴图那边界边的处理更要谨慎。参数化对边界环的完整性要求极高一旦边界半边逻辑乱了二维展开结果会严重变形。4.4 验证工具用欧拉公式自检每一项修改这一步是我个人强烈建议养成的习惯。每次做大规模结构修改后用欧拉公式验证网格拓扑是否守恒V - E F 2 - 2g闭合曲面g为亏格即便是在开放边界网格上也有广义欧拉公式V - E F C - H其中C是连通分量数H是边界环数。修改前后V、E、F都在变化但差值必须保持一致。如果对不上说明你的修改破坏了网格拓扑。我见过很多刚上手的学生调试边坍缩时眼睛看花了看不出bug跑一遍欧拉公式差值立刻定位到是哪一步多了或少了元素。这种方法不花什么计算时间却能让你的调试效率翻倍。5. 常见问题排查与效率优化那些文档里不会写的经验5.1 内存布局与缓存友好性为什么跑得很慢半边结构的经典实现是指针满天飞每个节点都是new出来的离散小对象。这在几百K面以下还行一旦到几百万面内存碎片化非常严重CPU缓存命中率也极低跑起来就一个字——卡。我的建议是把顶点、半边、面分别放进连续的std::vector用整数索引代替裸指针。这样内存局部性好加载快而且序列化到磁盘也方便。唯一需要适应的是原来代码里h-twin的写法变成了 h - twin (因为半边结构里存的可能是索引或指针)。同样的逻辑用索引数组管理起来对调试更友好。如果你想继续压榨性能可以把半边按内存池方式分配把同一个面的三条半边放在相邻内存这样遍历时能获得更好的预取效果。做大规模网格处理时这一步优化带来的加速往往肉眼可见。5.2 网格数据不一致的超实用排查策略当你的代码出现“遍历到一半指到空节点”或者“三角形数量对不上”时别急着蒙头debug。按下面步骤逐项排查能省掉至少70%的苦功打印欧拉公式差值。差值不对说明拓扑改动环节有增删遗漏。检查twin互指的一致性。遍历所有半边验证 h-twin-twin h。如果有不满足的说明配对环节出了问题。检查next链闭环性。从每个面的任意半边出发绕一圈必须回到起点如果中途绕到别的面说明next指针更新错乱。检查孤立顶点与孤立边。一个合法半边结构中不应该存在“不是任何半边起点或终点的顶点”也不应该存在“两头空洞的半边”。遍历所有顶点和半边看是否都能从某个面访问到。用一个小网格10个三角形以内做单元测试。与其在大模型上反复调试不如手工构造形状简单的网格把每一步结果打印出来手算验证。5.3 拓扑操作的安全准则三条从不打破的规矩多年代码实战里我总结出几条不成文但非常重要的安全准则操作后必做完整性校验。任何拓扑修改函数在返回之前做一遍O(相关区域)的校验。看起来很浪费实际能防住大量隐藏bug。不直接删除元素而是先做标记再清理。比如边坍缩时先标记被删除的顶点、面、半边最后统一回收。否则在修改过程中某个被删元素的指针可能被其他路径间接访问到。几何和拓扑分开更新。先只改拓扑结构再统一更新几何量法线、面积等。混合在一起更新极容易引入中间态不一致的问题。6. 写在最后关于“越基础越重要”这件事如果你跟着这篇文章的思路把半边结构亲手实现一遍再去读后续章节里那些更复杂的算法细分、简化、参数化、形变你会发现很多难点其实早就在数据结构这一层给化解了。我至今记得自己第一次把半边结构写对时那种“眼里有光”的感觉——原本需要几百行还老出错的邻域遍历变成了一两段循环原语原本一改就崩的拓扑操作变成了局部套路的组合。后来再看各种网格处理论文第一件事就是找它的数据结构定义能看懂这个论文后半段的算法基本也就通了大半。最后分享一个小技巧学网格数据结构时一定不要只看书一定要动手搭一个迷你引擎渲染出网格结构把半边、twin、next可视化成不同颜色的箭头。当你亲眼看到一条半边通过twin跳到另一个面、再沿着next绕回时很多抽象概念一下子就落地了。那种恍然大悟的爽快感是看多少篇文档都换不来的。
阅读完成 · 觉得有帮助？
