Dijkstra

3D 曲面力场重建与点云显示算法研究 背景 三维曲面力场重建要解决的，是如何根据少量离散传感器的空间位置、表面方向和测量值，估计模型表面上没有传感器位置的力值，并把结果显示成连续、稳定且符合物体形状的分布。 这件事看起来像普通插值，实际包含两个性质不同的问题。第一个问题是力值应该传播到哪里。它由距离定义、曲面连通关系和传感器朝向决定。第二个问题是重建结果应该怎样显示。它由表面采样密度、颜色映射和几何位移决定。早期方案多次调整，根本原因就是把传播算法和显示载体混在一起：传播关系不正确时，仅改变颜色无法消除串色；传播关系正确时，直接在粗三角面上着色又可能产生大片色块。 最终采用的思路是先把三角模型整理成可传播的曲面图，再把每个传感器附着到模型表面，沿曲面执行有限半径的最短路径搜索，用 Wendland C² 核计算距离权重。多个传感器按连续场采样点进行归一化插值，再通过 coverage 控制支撑区域边缘的衰减。显示层不再改变模型本身，而是在灰色模型表面覆盖彩色点云，用颜色和沿法线的隆起共同表达力值。 图 Fig001：力场算法的主要演进。距离定义、边缘衰减和显示载体分别经历调整，最终形成曲面传播与点云显示的组合。 本文以左手手套三维模型作为演示对象，使用确定性的 Wave 合成力值观察动态效果。由于没有与该模型对应的真实加载实验数据，文中的结果只能说明算法行为和显示效果，不能被解释为真实设备精度验证。 从欧氏插值到曲面传播 最直接的重建方法，是计算传感器与模型顶点之间的三维直线距离，然后让距离近的传感器具有更大权重。这种方法实现简单，在平面或结构单一的缓曲面上也可能得到合理结果，但它隐含了一个不适用于复杂模型的假设：空间上接近的位置，也可以沿物体表面直接传播。 手套模型能清楚暴露这个问题。两根手指之间的空气间隙很小，手掌正反面之间也可能只有很薄的模型厚度。欧氏距离会把这些位置视为近邻，使一个传感器的影响直接到达另一根手指或模型背面。折角附近也有同样的问题。两个点的直线距离可能很短，但真实的表面路径需要绕过较长距离，甚至根本不存在连续路径。 早期的视觉修正曾把低值区域改成灰色，重新定义平滑显示与离散点显示的切换，并调整颜色过渡。这些改动提高了画面可读性，却没有改变传播距离，因此不能从根本上修复薄壁、折角和相邻部件之间的串色。 像素化重建是另一条尝试路线。它先把模型投影到高分辨率平面，在规则像素网格上插值和后处理。规则像素能够减轻原始三角面大小不均造成的色块，Gaussian 平滑也能让边缘更柔和，但单一投影难以表达任意方向、多层和自遮挡曲面。模型前后两层还可能落到相同像素位置。高分辨率重建带来的计算量也比较大。因此，这条路线适合作为视觉实验，却不适合作为一般三维模型的传播基础。 曲面传播的核心变化，是把"距离"从三维空间中的直线长度，改成模型表面的路径长度。模型顶点作为图节点，共享三角形边作为图边，边权是相邻顶点之间的几何长度。传感器先找到附近且朝向兼容的表面点，再从该点沿曲面图执行截断 Dijkstra。一个位置只有在曲面上存在合法路径，并且路径总长不超过传播半径时，才会受到该传感器影响。 这并不意味着算法完全不再使用欧氏距离。传感器的导出位置可能略微离开模型表面，因此仍要用直线距离找到附近表面作为附着点。区别在于，这个距离只用于完成传感器到表面的初始附着。附着之后的扩散范围由曲面路径决定，不能继续穿过模型内部走捷径。 曲面如何变成可计算的传播域 三角网格不能直接拿来做曲面搜索。STL 模型通常以彼此独立的三角形保存，同一个几何点可能在相邻三角形中重复出现。如果不先合并这些重复顶点，算法看到的会是大量互不连接的小三角形，最短路径也无法跨越三角形边界。 因此，曲面准备的第一步是顶点焊接。算法按照一个较小的位置容差，将坐标相同或足够接近的顶点合并为共享顶点，同时删除顶点重复或面积接近零的退化三角形。焊接容差需要与模型单位和导出精度匹配。容差过小会留下不应存在的裂缝，容差过大则可能把距离很近但实际分离的两层表面错误连接起来。 焊接之后可以根据三角形共享边建立邻接图。图边的长度取两个顶点之间的几何距离。为了避免传播穿过尖锐折角，还要比较相邻顶点法线。设相邻顶点为 $u$ 和 $v$，只有满足 $$ \mathbf{n}_u\cdot\mathbf{n}_v\ge\tau_e $$时，二者之间的边才允许参与传播。本文采用的邻接法线阈值为 $\tau_e=0.25$。这是一种硬门控：达到阈值的边可以通过，低于阈值的边完全禁止通过。它的优点是折角隔离清楚，缺点是高曲率但连续的表面也可能被切断。更平滑的替代方案是根据夹角增加路径代价，但这会引入新的衰减参数，必须通过真实数据才能判断是否更合理。 网格密度同样会影响曲面距离和点云连续性。如果最大三角形边长远大于传播半径，支撑区域内可能只有少量顶点，最短路径会变得粗糙，显示点也会过于稀疏。可以把目标边长定义为 $$ E_{target}=\max\left(\frac{R}{4},1\text{ mm}\right) $$当最大边长明显超过目标边长时，将一个三角形沿三条边的中点拆成四个子三角形。共享边的中点必须复用，避免细分后重新产生裂缝。细分还要设置顶点数上限，否则高面数模型可能快速膨胀。 细分后需要重新计算顶点法线。顶点法线既控制传播能否经过某条边，也决定点云隆起方向，因此不能把它当成单纯的光照数据。通常将相邻三角形的面积加权法线累加到顶点，再进行归一化。无条件执行 Laplacian 平滑并不稳妥，因为平滑会收缩几何并改变传感器到表面的物理距离。视觉上更圆润不代表几何关系更准确。 传感器附着也使用法线约束。设曲面点法线为 $\mathbf{n}_v$，传感器法线为 $\mathbf{n}_i$，只有满足 $$ \mathbf{n}_v\cdot\mathbf{n}_i\ge\tau_c $$的顶点才参与附着点选择。本文采用 $\tau_c=0.1$。在所有兼容顶点中选择与传感器中心最近的点作为种子。如果传感器到种子的初始距离已经大于传播半径，该传感器不产生曲面影响。 从种子开始执行 Dijkstra 搜索，路径距离由曲面边长累计： $$ d_i(v)=\min_{\pi:i\rightarrow v}\sum_{(u,w)\in\pi}\|\mathbf{x}_u-\mathbf{x}_w\| $$路径只能经过法线兼容的邻接边，并在距离超过半径 $R$ 时停止。这样得到的 $d_i(v)$ 是离散网格上的测地距离近似。它不完美依赖模型质量，但比直接使用穿过空间的直线距离更符合复杂表面的传播关系。 图 Fig004：传感器附着、曲面路径和紧支撑权重。欧氏距离只用于选择附近表面，实际传播距离由曲面路径决定。 离散测量如何形成连续场 得到曲面距离之后，仍然需要决定距离如何转化为权重。本文采用 Wendland C² 紧支撑核。对曲面距离 $d$ 和传播半径 $R$，令 $r=d/R$，权重定义为 ...