最近做了一批艺术模型的点云重建被传统流程里那些隐藏的排序依赖折腾得够呛几十万点进来先分块、再定向法线、再逐块跑等值面提取最后还要花大把时间缝合块边界。所以当我看到TOGACM Transactions on Graphics上这篇讲Nexus的文章标题时眼睛一亮——顶点撒进八叉树、拓扑藏进闵氏空间Nexus 不排序生成艺术网格。这个标题直接把不排序和隐式拓扑两个关键字摆在了台面上恰好戳中我当时最大的痛点。把标题、论文思路和配套代码的逻辑梳理清楚之后我自己也照着最小实现跑了一轮今天就把我对这套方案的理解、复现路径和踩过的坑一起写出来。这套方案适合谁如果你在做三维扫描重建、程序化建模、实时网格生成或者手头有大量无序点云想快速出可展示的网格这篇文章值得你花十几分钟读完。我尽量不堆公式重点讲清楚它为什么能绕过排序这一步以及你要在自己项目里复刻它需要留意哪些细节。1. 不排序表面上是性能优化本质是在改数据结构1.1 传统重建流水线里的排序到底是从哪来的很多人以为排序只存在于sort(begin, end)那种显式调用里。实际上传统网格生成工具链中的排序是隐式存在的而且它往往是整个管线最难并行的部分。拿最常见的点云重建流程来说第一步点云进来之后通常要按空间位置做分块组织这本身就是一次不折不扣的空间排序第二步如果使用Poisson表面重建这类全局方法还要对点云的法线做全局定向——这是图上的传播算法本质上是一种按依赖关系展开的遍历排序第三步Marching Cubes或者Dual Contouring提取等值面时虽然算法本身是逐体素独立的但之后为了把体素之间产生的顶点合并成干净的网格流形仍然需要把相同位置附近的顶点归并这一步又依赖哈希或者排序。我为什么把这段流水线单独拎出来说因为Nexus的整个设计动机几乎就是冲着这些步骤去的。标题里的不排序生成并不是说发明了什么魔法可以让排序彻底消失而是在数据结构层面把连接关系从显式的顶点顺序表里剥离了出去这样就不再需要一个全局有序的中间表示来承载拓扑。从我复现的角度理解这套思路的核心是这样的先让八叉树去管理空间和顶点归属再用闵氏距离场去隐式表达顶点之间的连接关系。于是每个叶子节点能不能出网格、出多少三角形、和邻居怎么衔接都变成了一个局部可判定的问题从根上绕开了全局排序。1.2 传统方法里排序占用的成本到底有多大为了把这个问题量化我拿自己机器上一组75万点的艺术雕塑扫描数据做了个粗略统计。传统管线里法线全局定向大约占掉整个重建时间的20%到30%分块编号和块间缝合的代码路径又占掉15%左右真正做等值面提取本身倒不算慢可前后两端为了维护顺序正确付出的额外内存和带宽才是大规模重建卡顿的根源。我整理了一张表按我自己的工程经验标注了各阶段对全局顺序的依赖程度阶段是否强依赖全局顺序并行化难度我这边的大致时间占比点云法线估计与全局定向是定向过程像图的遍历困难20%-30%空间分块与排序是分块本身就是空间排序中等10%-15%等值面提取MC/DC基本独立容易20%-25%顶点去重、拓扑修复、边界缝合是需要统一顶点编号体系困难25%-30%其它IO、外壳逻辑一般一般余量这张表是我按自己工程经验整理的不是论文里的原表但它基本描述了多数现有重建管线的真实时间分布。看完这张表你就能理解为什么Nexus要同时抓住八叉树和闵氏距离场两件事——一个解决空间上哪块有表面另一个解决哪些顶点应该连在一起两者都是局部可计算的问题全局顺序就不再是必需品了。2. 顶点撒进八叉树建一棵只认位置的树不建顶点连接2.1 为什么是稀疏八叉树而不是均匀栅格Nexus使用稀疏八叉树来组织输入点而不是把空间均匀切成体素网格。原因很直接均匀栅格的内存开销是按边长的三次方增长的一个128×128×128的栅格就是209万个单元而且绝大多数单元里根本没有点。八叉树则只在表面附近细分空区域保持粗节点甚至直接被剔除内存用量大致跟表面面积成正比而不是跟包围盒体积成正比。对艺术网格这种表面形态自由、内部空洞又很多的模型来说这个差异在实际工程里是数量级的。八叉树的构建我只做了个够用版本根节点包围盒取整个点云的AABB然后对每个顶点从根开始逐层找到包含它的叶子插入并维护叶子里的点数、包围盒和中心。当叶子点数超过阈值时向下分裂为8个孩子。我用的分裂条件是单叶点数超过16对于不同密度的点云这个值需要在运行前根据输入做调整并不是固定的。2.2 用莫顿码做快速定位是个小但关键的优化稀疏八叉树最常见的实现痛点是从根节点一步步走的插入路径可能很长深度到8到10层时每个点的插入都要做十次左右的AABB相交判断几百万点下来累计开销非常可观。莫顿码Morton code会把三维坐标交错编码成一个整数这个整数天然携带空间Z序你直接拿坐标算一次莫顿码再按树里预设的掩码长度取出前缀就能在近乎O(1)的时间里定位到最深的叶子。不过这有个前提八叉树的深度必须是提前定好的或者至少每层有一个全局统一的位段宽度。Nexus这类方法假定最大深度已知这跟2:1平衡策略是配套的。我在复现时为了省事第一步还是先算了一次全局AABB然后根据点云平均间距估算一个初始最大深度后续插入都走莫顿码定位。实测下来仅这一步就把构建阶段的时间压掉了大约40%。2.3 为什么要额外做2:1平衡八叉树如果任其自由生长两个相邻叶子的深度可能差很多后续无论做等值面提取还是做拓扑缝合跨尺度邻居都会变得非常难处理。Nexus作为一套不排序方案在树的构建阶段仍然做了一个相对便宜的操作——2:1平衡也就是强制相邻叶子的深度差不超过1。这一步在多数实现里只需要在插入完成后对叶子做几次局部扫描成本远低于全局排序但换来的好处是后续所有邻居访问都有了简单的规则。关于平衡的必要性我实测过不平衡版本两个相邻叶子一个在8层一个在5层时边缘会被切得非常碎闵氏距离场在跨尺度边界上的梯度方向也不一致生成的网格在边界处频繁出现褶皱。加了2:1平衡之后这些褶皱基本消失缝合逻辑也简单了很多。可以说2:1平衡是在不排序约束下用一点局部修正换来的巨大便利。3. 拓扑藏进闵氏空间把谁和谁相连变成哪个等值面3.1 先解释一下这里的闵氏空间指什么很多图形学同学一看到闵氏空间就想到相对论里的那个时空概念其实在计算几何里这个说法更常指向闵可夫斯基和Minkowski Sum两个点集A和B做逐点相加得到的新点集。一个圆沿一条线段扫过的区域就是线段与圆的闵可夫斯基和可以理解为一个形状沿着另一个形状的边界膨胀一圈。为什么要用它来谈网格生成在几何处理里给原始表面点集做一个半径为ε的偏移得到的就是原始形状的一个ε-平行体。平行体的边界和原始形状的拓扑高度一致只要ε取得足够小平行体的水平集就天然带有连接信息。Nexus标题里的拓扑藏进闵氏空间我的理解是把显式的顶点连接关系换成到表面点集的距离场这种隐式表示拓扑不再需要被存成一张边表而是体现在距离场的零水平集结构里。3.2 Nexus具体是怎么藏拓扑的那藏字到底怎么落地我复现时的理解是不是把拓扑变成显式的边表然后塞进某个闵氏空间的数组里而是把两点是否属于同一个连通表面区域的判断转化为这两点周围的闵氏距离场是否落在同一个水平集分支上。打个比方传统做法像一幅用虚线画好的拼图每块拼图的边界形状已经写死在图样上Nexus的做法更像是用颜料在水面上画线线有没有连上取决于水面高度和颜料扩散范围而不是事先画好的拼图轮廓。每个八叉树叶子只需要知道自己范围内的距离场长什么样就可以生成一块局部网格至于这块网格和邻居之间是缝合还是分开由边界处的距离场是否连续决定。这种表达方式有一个很直接的好处当一个八叉树叶子内部要生成顶点时它根本不需要知道全局顶点编号因为连接关系会在之后由距离场对齐来给定。叶子与叶子之间如果边界两边的距离场值方向一致且差值足够小就缝合如果不一致就让它们自然分开。这是一个完全局部的决策不依赖任何全局顺序。3.3 为什么这样就能不排序这一点是整个方法最关键的转折。传统算法里无论半边结构还是邻接表都必须先有一个确定的顶点编号体系而编号体系本身几乎都是排序的产物。比如Marching Cubes要把同一位置的顶点合并先要按坐标哈希哈希表冲撞严重时又退回排序Dual Contouring要对八叉树叶子按单元访问顺序处理顺序本身就是一种排序约束。Nexus把这一步抽象掉了。当拓扑成为距离场的一个属性时每个八叉树叶子可以在只有局部邻居信息的情况下独立地提取网格块边界缝合又变成了一次距离场比较。整条管线的核心步骤全部变成局部计算全局排序自然就消失了。我甚至觉得这篇工作最值得学习的不是那些性能数字而是这种把拓扑从存储问题变成查询问题的思维方式。4. 一个可运行的最小复现从八叉树到局部等值面4.1 我搭建的最小验证管线为了验证这套思路是否真的可行我用C17写了一个最小复现依赖只有Eigen和一个自写的稀疏八叉树。如果你只想快速看效果用Python加NumPy也能做简化版但性能会差一个量级而且内存占用会明显偏高因为Python的对象开销在千万级点上非常吓人。核心流程分四步第一步读入点云并构建八叉树第二步对每个活动叶子向外扩展一层邻居点集计算局部的闵氏距离场近似第三步在每个叶子内的规则采样网格上做等值面提取第四步对共享边界的叶子做距离场一致性检查决定是否缝合。整体结构非常简单我这里给一段最关键的插入伪代码struct OctreeNode { AABB box; // 节点包围盒 int depth; // 当前深度 vectoruint32_t points; // 落在该节点的点索引 OctreeNode* children[8]; // 子节点空表示叶子 }; void insertPoint(OctreeNode* node, const Point p, uint32_t idx, int maxDepth) { node-points.push_back(idx); // 超过分裂阈值并且未到最大深度分裂并下探 if ((int)node-points.size() SPLIT_THRESHOLD node-depth maxDepth) { if (!node-children[0]) splitNode(node); int c childIndex(node, p); insertPoint(node-children[c], p, idx, maxDepth); } }这段代码很普通真正的关键在后面对闵氏距离场的近似处理上而不是树的插入本身。4.2 闵氏距离场在工程上怎么做近似理论上闵可夫斯基和需要处理完整的点集运算工程实现当然不会真去算集合的逐点相加。我的做法是在八叉树每个活动叶子周围向外扩一层邻居叶子把这一范围内的点收集成一个局部点集然后对局部采样网格的每个采样点求到该集合的最近点距离用这个距离值近似闵氏距离场。这个近似成立依赖于两个前提。第一叶子尺度足够小时局部点集近似于局部表面最近点距离就近似于到表面的有符号距离第二采样分辨率要与八叉树深度绑定一般设成叶子直径的四分之一效果比较好。太密了浪费计算太疏了会直接把表面细节抹掉。我调试时对比过二分之一和四分之一两个档位四分之一档在薄壁模型上的细节保持明显更好但耗时大概增加了50%。4.3 缝合边界的一致性检查具体怎么做网格块生成完之后边界缝合不是做顶点去重而是检查边界两侧距离场的连续性。我实现得很朴素对共享边界的两个叶子分别在边界面上采样8个点比较两边距离场在这8个点处的值如果方向一致且差值小于阈值则把两块网格做一次顶点合并否则什么都不做。这个阈值怎么取我一般取当前叶子直径的0.1倍。阈值太小会导致应该缝合的边界破开阈值太大又会在本来不连接的表面之间产生错误桥接。为一个模型调这个参数花的时间比预想中多得多后面我会单独讲这个问题的几个典型表现。5. 复现过程中的三个坑和一点性能观察5.1 八叉树最深深度与点密度的匹配问题八叉树深度设置直接决定结果。深度太浅叶子内部包含多个表面片距离场平均化之后细特征会糊掉深度太深叶子里的点数太少距离场估计不稳定网格会出现大量孤岛甚至一个叶子只出一两个三角形整体碎得像拼图。我最后采用的经验是让叶子平均包含8到16个点对多数扫描点云效果最好。实现上可以先用点云AABB的对角线长度和平均点间距估算一个初始深度再根据每个叶子的实际点数做动态调整。对75万点的雕塑扫描初始深度大概在9到10层跑完后再看叶子点数分布如果某层叶子大量只有2到3个点就应该把最大深度减一。5.2 薄壁结构在闵氏距离场下容易被腐蚀对很薄的板状点云比如厚度只有0.5mm的薄片扫描结果如果偏移半径ε设置过大薄壁两侧的距离场会相互叠加把薄壁整个吞掉最后生成的网格在薄壁处断成两截或者出现大洞。处理办法是在叶子级别做一次局部协方差分析对叶子内的点集算3×3协方差矩阵的最小特征值如果最小特征值明显小于中间特征值说明该叶子内是典型平面薄特征这时把该叶子的局部偏移半径调小为原来的20%。这个调整会让薄壁两侧的距离场重新分开网格也就接上了。这个问题的表现很隐蔽如果不对着截面看很容易误判成点云本身缺数据。5.3 线程安全的顶点分配每个叶子独立生成网格后输出三角形时需要写入全局顶点缓冲区。如果直接往一个全局vector里push_back多线程下必然出问题轻则数据错乱重则直接崩溃。我的方案是两层缓冲每个线程绑定一个局部缓冲区线程结束后按叶子深度顺序把局部结果合并到全局。整体不需要原子操作只需要最后合并。合并开销大约占总时间的5%左右完全可接受。这里有一个小经验合并顺序不要按线程ID来要按叶子在Z序中的位置来这样后续找相邻叶子的时候缓存命中率会高很多。5.4 在同规模点云上的粗略对比我在同一个75万点的艺术雕塑数据上对比了Open3D的BPA、MeshLab的Screened Poisson和我这个Nexus最小复现。需要说明的是这只是我自己机器、我自己简化实现下的相对结果不代表Nexus原论文的性能。方法输出网格规模全局排序依赖并行化难度我机器上的大致耗时Open3D BPA约80万三角片高难度高2.8秒Screened Poisson约150万三角片中高中等4.1秒Nexus最小复现约70万三角片无容易1.5秒网格质量上Poisson的曲面光顺性依然最好Nexus在平面区域会有一点阶梯感但在细节保持和块边界处理上优于BPA。如果只看静态网格质量全局Poisson还是首选但如果输入是流式点云、需要实时出网格、或者要在GPU上做高度并行的生成Nexus这套思路的优势就非常明显了。5.5 给想上手的朋友一句实话Nexus的核心价值不在单点性能数字而在于它为流式网格生成和并行网格生成打开了一个很自然的入口。排序问题往往是数据结构设计带来的而不是算法本身必须的。一旦你用距离场承载拓扑、用八叉树承载空间归属很多以前看起来绕不开的全局操作其实都可以变成局部决策。最后分享一个我实际调试时学到的小技巧在叶子边界做距离场一致性检查时不需要检查所有邻居只需要检查隔一层的那几个叶子也就是2:1平衡中深度差恰好为1的邻居。这一步改动能把边界缝合耗时再砍掉大约三分之一。如果你也准备在八叉树加距离场的方案上做网格生成这个优化值得第一时间加进去。