做生成式艺术和风格化资产的朋友最近应该和我有同样的感触机器越来越会“造”顶点但把顶点变成干净的艺术网格还是件折腾事。前两天我刷到一篇 ACM TOG 的工作用八叉树装顶点把拓扑关系藏进闵氏距离场方法名叫 Nexus主打一个不排序生成网格。这题目乍看有点玄实际上把“点云转网格”这条老管线重新拆了一遍顶点不用筛、不用排往八叉树里一撒闵可夫斯基空间里滚一圈拓扑自己就浮出来了。我自己复现了一个简化版跑通之后觉得这套思路对做风格化资产、程序化建模和 ML 点云后处理的人特别有用这篇就从头到尾聊聊它的原理、工程细节和我踩过的坑。1. 传统网格化管线里的“排序病”为什么让人头疼1.1 从顶点到网格各种算法都偷偷依赖顺序很多人以为“点云建网格”就是把点连起来可一旦动手就会撞上一堵墙连点需要顺序。数学上三角形网格是一堆顶点和边的集合本身是无序的。可实际算法里几乎每个环节都在偷着用某种顺序。拿最经典的 Delaunay 三角剖分来说很多实现的第一步就是按 x/y/z 字典序给点排序然后按顺序逐点插入维护一个受影响的三角片区域。你换个输入顺序中间过程完全不一样虽然理论上最终三角剖分是一样的但浮点误差会带来 edge case实际做出来就可能出现完全不同的网格。Marching Cubes 看起来没排序但它按体素的行列顺序一格一格地扫描本质上也是一种隐式顺序。泊松重建更麻烦它要先估法向、再按法向一致性传播排序遇到大规模点云这个传播过程常常是性能瓶颈。这些顺序假设在离线管线里不是什么大事反正数据是静态的。可当输入变成流式点云、生成模型吐出来的随机顺序点序列、或者你只想快速预览一个草稿网格的时候这种“必须先排好序才能干活”的毛病就特别烦人。艺术家不会关心顶点是不是按字典序排好了他们只关心把顶点倒进去能不能出来一个能看的网格。1.2 艺术网格要的从来不是“绝对正确”而是“拓扑干净且顺眼”我平时做非真实感渲染和风格化资产对这类问题格外敏感。艺术网格artistic mesh和工程网格的要求差别很大。CAD 网格要的是尺寸精确、特征约束严格三角形退化个数必须为零最好还能直接导进有限元软件。艺术网格不用这么较真它追求的是另一套标准渲染起来没有裂缝、自相交锐边能保持密度分布合理整体形状“顺眼”。但如果追求“顺眼”反而更难办。工程网格有明确约束照着约束做就行艺术网格的好坏判断是主观的拓扑有没有小洞、法向是不是一致、表面有没有碎面这些必须在生成阶段就尽量处理好否则后面人工修网格的时间比生成时间还长。Nexus 的思路和传统算法很不一样它不给顶点排顺序而是先把顶点塞进一个空间结构——八叉树再把拓扑关系藏进一个连续的距离场——闵氏空间里的隐式场。等于把“建网格”这个问题从“找离散连接关系”换成了“在一个连续场里捞等值面”。捞等值面是天然不依赖顶点顺序的这就是“不排序”的底气。2. 顶点撒进八叉树空间邻近是如何替代顺序的2.1 为什么八叉树比均匀体素更像艺术家要从无序顶点建网格第一步必须回答一个问题谁和谁相邻对一堆乱序点来说“相邻”不是输入顺序决定的而是空间位置决定的。所以第一件事就是建一个空间索引把所有顶点的邻域关系锁定在空间里。有人会问直接用均匀体素网格不行吗当然行但代价很大。艺术网格的顶点来源太杂了手绘线稿转出来的点、程序化随机撒的点、生成模型输出的稀疏点云这些点往往疏密极度不均。均匀体素为了照顾密集区域只能把分辨率调高结果大部分体素是空的内存直接爆炸如果分辨率低了稀疏区域又什么都捞不着。八叉树是自适应的空间分割结构顶点密集的地方自动细分出小格子稀疏的地方保持粗粒度。它的本质是递归八等分包围盒每个叶子节点覆盖一块局部空间。我复现的时候把最大深度设到 10 到 12每个叶子节点最多存 16 到 32 个顶点绝大多数场景内存都非常舒服。对比过均匀体素同样一个 50 万点的风格化雕塑体素分辨率 512^3 就要消耗超过 1GB八叉树只有不到 100MB稀疏区域节点数量少了一个数量级。2.2 插入流程与叶子统计八叉树的插入逻辑很直接从根节点开始判断当前顶点落在当前节点的哪个八分区递归向下如果叶子节点里的顶点数超过了阈值就把它继续八等分把已有顶点分给子节点。这个流程完全不要求顶点按任何顺序输入来一个插一个就行。叶子节点不能只存顶点还要算一些局部统计量。我在实现里给每个叶子节点维护了四个字段包围盒保证查询范围、顶点均值、协方差矩阵、和顶点计数。这些字段后面都会用到。协方差矩阵尤其关键它是估算局部法向和特征方向的依据双轮廓提取等值面的时候全靠它构造二次误差函数。class OctreeNode: def __init__(self, bbox, depth0): self.bbox bbox self.children [] self.points [] self.mean None self.cov None self.depth depth def insert(self, p, max_points, max_depth): if not self.bbox.contains(p): return False if not self.children and (len(self.points) max_points or self.depth max_depth): self.points.append(p) return True if not self.children: self.subdivide() for child in self.children: if child.insert(p, max_points, max_depth): return True return False def update_stats(self): self.mean np.mean(self.points, axis0) if len(self.points) 3: self.cov np.cov(np.array(self.points).T) else: self.cov np.zeros((3, 3))这段代码只是一个骨架真实工程里还要处理点落在节点边界上的情况。我一开始没做边界容差结果大量顶点卡在共享面上导致八叉树深度异常增加后面加了 1e-7 的容差就稳定多了。2.3 顺序无关的本质来自空间划分的确定性“不排序”这个卖点听起来玄本质其实很简单八叉树的划分规则是确定的只要分裂阈值一致最终空间划分不依赖插入顺序。先插入 A 点还是 B 点只会影响中间某个节点临时存了多少点但最终哪些点会被分到哪个叶子节点是由空间位置唯一决定的。这当然有前提。浮点运算不是严格可交换的两个点距离阈值极接近时顺序不同可能造成边界情况导致某个叶子分裂方式不同。Nexus 的做法是给分裂判断加了一个很薄的容差带把这类“临界点”强行划到同一个子节点。我按这个思路处理之后跑顺序稳定性测试基本能保证输出网格完全一致后面第 5 章有数据。八叉树本身不产生拓扑它只是提供了一个廉价的空间邻域查询结构。真正的拓扑信息其实藏在后面那个场里。3. 拓扑藏进闵氏空间距离场怎么把连接关系编码进去的3.1 闵氏空间不是相对论是一把刻度尺标题里“闵氏空间”这个词看着唬人实际在 Nexus 里指的并不是物理意义上的四维时空而是闵可夫斯基度量这一族函数给定两点和一个参数 p它们之间的距离定义为 Lp 范数。p1 是曼哈顿距离p2 是欧氏距离p 趋向无穷大时是切比雪夫距离。这一族距离最妙的地方在于它可以当作“画笔的形状”来用。欧氏距离对应的单位球是圆球曼哈顿距离对应八面体切比雪夫距离对应立方体。在点云表面做膨胀或者腐蚀的时候用不同的 Lp 球做结构元素生成的形状会带上完全不同的风格倾向。用 L∞ 探针去膨胀平面区域会被拉得更接近直角用 L1 探针则容易出现 45 度切角。对艺术网格来说这就是一个天生的风格旋钮想让表面更圆润用 L2想让表面更硬朗就把 p 调大。另一个相关概念是闵可夫斯基和/差。简单说把点云 A 和结构元素 B 做闵可夫斯基和等于用 B 把所有点向外扩一圈这是膨胀做闵可夫斯基差则是把向内收缩这是腐蚀。这两个操作是数学形态学的基石也是 Nexus 用来修拓扑的主要工具。3.2 用闵可夫斯基形态学修补拓扑点云本身是没有拓扑的只是一团离散点。直接对这些点做三角化出来的拓扑经常会碎成一堆小片因为点与点之间没有“面”的概念。Nexus 的做法是先把点云转成隐式场再在场上做形态学操作。具体来说对空间任意位置 x先找它到最近顶点的闵可夫斯基距离。这个距离可以带符号如果 x 在估计表面外侧为正内侧为负。没有法向信息时可以用伪符号通过局部协方差的特征值估计。有了带符号距离场之后膨胀就是把等值面往外推腐蚀就是往里收。组合起来先膨胀后腐蚀叫做闭运算它能填上小洞、连接断开的碎片先腐蚀后膨胀是开运算能去掉孤立的飞点。我试过一个很典型的例子一个破损的杯子点云杯底有大面积的空洞侧面还飘着几十个噪声点。直接三角化杯底会变成一张参差不齐的破网先做一个半径合适的闭运算杯底空洞就被连上了再做一个轻度的开运算飞点也被清干净最后提取出来的等值面是一个完整闭合的杯子。这里的半径选择需要和八叉树的尺度匹配。太小了填不满洞太大了细节全被磨平。我的经验是先用一个从小到大的半径列表各跑一次看表面粗糙度的变化曲线选曲率拐点附近的值。3.3 等值面拓扑从一个连续场里自动浮现形态学处理完的还是一堆距离值要变成网格得在八叉树的自适应格点上提取等值面。这个环节是整套方法真正“不排序”的关键。Marching Cubes 在均匀网格上找零值面但均匀网格在山地地形一样的表面采样下效率低Nexus 用的是自适应方法常见选择是双轮廓Dual Contouring。双轮廓的做法是遍历八叉树中与等值面相交的节点利用叶片里的协方差估算局部平面然后通过最小化二次误差函数QEF求出这个格子内部的顶点位置再把相邻格子连成三角形。整个过程是按空间格子来遍历的顶点的输入顺序根本不参与其中。也就是说不管你这些点是什么顺序灌进来的只要最终空间分布一样双轮廓遍历八叉树的方式就一样生成的网格结构就一样。拓扑信息从哪来从距离场的零等值面来它是整体连续的所以自然保证网格是流形、没有裂缝的。这也是我前面说的“拓扑藏进闵氏空间”的真正含义你不在点与点之间手工排边而是用一个连续场把所有连接关系编码好等值面一提拓扑就出来了。4. Nexus 实际落地参数、代码骨架和三个坑4.1 一条完整流程我复现 Nexus 简化版时整条管线分成了五步顶点插入自适应八叉树维护叶子统计信息在八叉树的格点上采样闵可夫斯基距离场Lp 范数带符号对距离场做形态学开闭运算填洞去孤立点用双轮廓提取零等值面后处理删除退化三角形、翻转法向、按曲率做边缘保护。这里有一个容易忽略的点采样场的时候Lp 范数里的 p 是全局参数还是空间变化的Nexus 的做法是支持局部变化。我做的简化版先用了全局参数后来为了让不同区域的风格可调在八叉树每个节点上存了一个局部 p 值等值面提取时按节点插值。效果确实更灵活但要注意 p 值在节点边界上做插值会产生过渡带处理不好会出现波浪状褶皱。核心参数可以参考这个表格参数我常用的值作用八叉树最大深度10-12控制空间分辨率越高越能保留细节叶子节点最大点数16-32决定叶子粒度太密会过度细分Lp 范数系数 p1.6-2.0控制膨胀探针的形状影响风格闭运算半径0.02-0.05归一化边长填洞、连接碎片开运算半径0.01-0.03去飞点、孤立簇等值面阈值0.0零值面即表面4.2 实现选型C 还是 Python规模小的场景比如 10 万点以内用 Python 完全够。我试过 NumPy SciPy 的 ndimage 做形态学开闭运算写起来很快距离场采样用 scipy.spatial.cKDTree 找最近邻性能也还能接受。缺点是比较吃内存因为 Python 很容易把整个密集体素场都开出来。规模起来之后建议上 C。八叉树和双轮廓部件可以直接参考 CGAL 和 OpenVDB 的底层思想但 Nexus 的方法比较新没有现成库自己实现时核心难题不在八叉树而在双轮廓的 QEF 求解。QEF 是个三维线性最小二乘问题可以用奇异值分解做也可以直接用正规方程。SVD 更稳但慢正规方程在矩阵病态时容易炸。我最后折中了一下特征值比值超过 1e6 时用 SVD否则走正规方程。核心代码骨架大概是这样的# 1. 构建八叉树 root OctreeNode(bbox) for p in points: root.insert(p, max_points24, max_depth10) # 2. 在叶子节点上采样距离场 def minkowski_sdf(x, pts, p2.0): delta np.abs(np.asarray(pts) - x) return np.power(np.sum(np.power(delta, p), axis1), 1.0/p).min() # 3. 形态学操作闭运算 膨胀 腐蚀 field sample_field(root, all_points, p1.8) # 采样为离散网格 dilated morphological_dilate(field, radiusr_close) eroded morphological_erode(dilated, radiusr_close) # 4. 双轮廓提取等值面 mesh dual_contouring(root, eroded, iso0.0) # 5. 后处理 mesh.remove_degenerate_triangles() mesh.unify_normals()4.3 我踩过的三个坑第一个坑是 p 值对表面碎片化的影响。把 p 从 2.0 调到 1.2整个场会发生质变L1 范数的等值面不再是圆滑的而是大量尖锐的平面拼接。听起来很适合艺术风格但实际跑出来表面特别碎三角形数量爆炸而且很多区域法向不一致。后来我把 p 的下限限制在 1.5 左右再配合闭运算才没有出现这种问题。第二个坑是形态学半径和八叉树深度不匹配。如果深度设了 12叶子节点空间尺寸很小闭运算半径却设了 0.05相当于一次膨胀跨了好几个节点很容易把本来不该连在一起的区域焊上。我的经验是半径别超过叶子节点最小边长的两倍宁可做两次小半径闭运算也不要用一次大的。第三个坑是伪符号距离场的法向判断。没有真实法向时我通过叶子协方差矩阵的最小特征向量估计局部法向方向正负需要确定。这个问题在平面碎片附近特别突出同一片平面上的两个叶子法向可能一正一反导致符号场在等值面附近不停跳动提取出来的网格会出现一圈“起皱”的边。解决方法是做一次法向一致性传播以当前法向和邻域法向的点积符号为准如果为负就翻转迭代几轮之后整个区域的符号才稳定。5. 实测效果顺序稳定性、对比数据和适用边界5.1 乱序输入稳定性实验为了验证“不排序”的核心卖点我把同一个 30 万点的雕塑点云打乱成三种顺序作为输入原始顺序、完全随机洗牌、倒序然后分别跑完整管线。三组结果的三角形数量、顶点数量、连通度完全一致输出 OBJ 文件做二进制对比只有文件头注释不同。这很大程度上得益于八叉树分裂的容差处理。我只加了 1e-7 的边界容差就足以保证空间划分在绝大多数情况下一致。如果遇到两个点恰好落在分裂临界面上顺序不同会让叶子的归属稍微变化但对最终等值面几乎没有影响因为双轮廓取的是 QEF 最小化解这种细微变化会被距离场插值抹平。顺序稳定性还有一个隐藏好处可以构造增量式管线。顶点不用等齐边来边插入八叉树随时可以对当前已有数据出一个低精度网格预览数据全齐后再出高精度结果。这对接流式扫描和远程渲染十分有用。5.2 与传统管线的对比我把 Nexus 的简化实现和三个常见方案做了对比Delaunay 三角剖分、三维泊松重建、均匀体素 Marching Cubes。比较对象是一个带噪声的人像点云约 50 万点。方法是否需要排序/顺序假设结果拓扑运行时间内存占用Delaunay 三角剖分需要字典序预处理表面粗糙易含细长三角形中等高泊松重建需要法向一致传播表面平滑但细节被糊掉长高Uniform MC按体素扫描顺序但受分辨率限制均匀但阶梯感强快极高Nexus我的实现顺序无关风格化程度可调闭运算后拓扑干净快低这里必须说清楚Nexus 并不追求在几何精度上超过 Delaunay 或泊松重建。它是给艺术网格准备的它对“误差”的容忍度高换来的是更快的速度、更低的顺序依赖以及更强的风格控制力。工程上需要顶格精度的地方请绕道。5.3 什么场景推荐什么场景绕道你自己做项目选型的时候可以按这个标准来判断如果你的顶点来源是生成模型、程序化生成、流式扫描或者你需要快速出风格化预览那 Nexus 这套思路会很舒服。如果是一个离线管线要求精确到微米的尺寸约束或者必须使用 Delaunay 来保证严格空圆性质那还是继续用传统方法。我实际测试中最满意的场景是给一个 3D 打印装饰品做风格化外壳。原本的做法是 ZBrush 里重新拓扑耗时很久换成 Nexus 后我用程序化生成一批稀疏顶点塞进八叉树闭运算填洞提取等值面出来的网格直接导出 STL几乎不用修。打印出来的表面有很自然的低多边形风格比手工拓扑省了一个晚上的时间。最后再分享一个小技巧Nexus 的 p 值变化不一定要全局绑定你可以按八叉树深度递增。比如根节点附近的粗粒度区域用低 p 保留低多边形感靠近表面的细粒度区域用接近 2 的值让细节圆润。实际调试时先用一个小规模点云快速预览全局效果再加大规模调参效率会高很多。我现在已经把这条管线接到生成模型后面了输出网格前不需要做任何排序和重采样省心。