定制网站设计,photoshop网站模板下载,网站挂马处理百度快照,景观设计公司起名1、介绍 热方法是一种算法#xff0c;通过返回三角形网格中所有顶点到给定源顶点集合中最近顶点的测地距离近似值#xff0c;解决单源或多源最短路径问题。网格中两个顶点的测地距离是指从网格表面#xff08;可能经过面的内部#xff09;行进的距离。例如#xff0c;在章…
1、介绍 热方法是一种算法通过返回三角形网格中所有顶点到给定源顶点集合中最近顶点的测地距离近似值解决单源或多源最短路径问题。网格中两个顶点的测地距离是指从网格表面可能经过面的内部行进的距离。例如在章鱼的两个相邻臂上三维空间中靠近的两个顶点可能在表面上很远。在图中我们使用渐变的红色/绿色对距离进行着色编码对应于接近/远离源顶点。 热方法非常高效因为该算法简化为两个标准的稀疏线性代数问题。在需要对固定域进行重复距离查询的情况下该方法特别有用因为第一次查询的预计算可以重复使用。 一般来说该方法在Delaunay三角形网格上表现良好尽管在实践中对于远离Delaunay的网格也可能表现良好。为了确保良好的性能我们启用了预处理步骤该步骤构建了内在Delaunay三角剖分iDT这个剖分不会改变输入几何体但通常会提高解决方案的质量。该预处理步骤的成本大约会使总预处理成本翻倍。 内在Delaunay三角剖分Intrinsic Delaunay TriangulationIDT 在不进行iDT重网格和进行iDT重新网格的情况下放置在网格上的等值线。 在下一节中我们给出了一些例子。理论背景部分介绍了热方法的数学理论。最后一节是关于实施历史。 请注意此软件包依赖于第三方 Eigen 库3.3 或更高版本或概念 SparseLinearAlgebraWithFactor Traits_d 的其他模型。。 此软件包与三角曲面网格最短路径软件包相关。两者都处理测地线距离。热方法软件包为网格的每个顶点计算到一或多个源顶点的近似距离。测地线最短路径软件包计算曲面任意两点之间的精确最短路径。
2、理论背景 “热方法算法”一节概述了热方法所需的理论。“内蕴Delaunay三角化”一节介绍了内蕴Delaunay三角化所需的背景。
2.1、加热法 关于热方法的详细概述读者可以参考[1]阅读原文。在接下来的内容中我们将介绍一些基本概念以便解释我们的算法。一般来说热方法适用于任何设置如果存在一个梯度算子一个发散算子和一个拉普拉斯算子 Δ∇⋅∇Δ这是向量微积分的标准导数。 热处理方法包括三个主要步骤 将热流u˙Δu整合在某个固定的时间 t求向量场X−∇ut/|∇ut|求解泊松方程 Δϕ∇⋅X 函数 ϕ 是到给定源集的距离的近似值并且随着 t 趋近于零而接近真实距离。 然后必须通过用近似值替换空间和时间中的导数将该算法转化为离散算法。 热方程可以用一个向后欧拉步进行时间离散化。这意味着必须求解以下方程 (id−tΔ)utδγ(x)其中δγ(x)是狄拉克δ函数编码“无限”热尖峰如果x在源集γ中则为1否则为0其中id是单位算子。 空间离散化取决于离散表面表示的选择。对于这个包我们只使用三角形网格。设u∈R|V|表示一个在三角表面上的分段线性函数该三角表面有V个顶点、E条边和F个面。在顶点i处的拉普拉斯算子的标准离散化是 Lui12Ai∑j(cotαijcotβij)(uj−ui)其中Ai是所有与顶点i相交的三角形的面积的三分之一。 该和值由所有相邻顶点 j 计算得出。此外αij 和 βij 是与相应边 ij 对角的角度。我们通过矩阵 LM−1Lc 表示这一操作其中 M∈R|V|x|V| 是一个包含顶点面积的对角矩阵Lc∈R|V|x|V| 是余切算子表示剩余的和值。 由此对称正定系统M−tLCuδγ可以求解以找到u其中δγ是γ上的克罗内克δ。 接下来给定三角形中的梯度可以表示为 ∇u12Af∑iui(N×ei) 其中 Af 是三角形的面积N 是其外单位法线ei 是第 i 条边向量逆时针方向ui 是 u 在相对顶点的值。与顶点 i 相关的积分散度可以表示为 ∇⋅X12∑jcotθ1(e1⋅Xj)cotθ2(e2⋅Xj) 其中总和是针对每个具有向量Xj的入射三角形j求得的e1和e2是包含i的三角形j的两个边向量θ1和θ2是相对角。 最后设b∈R|V|为归一化向量场X的积分散度。因此求解对称泊松问题Lcϕb可以计算出最终的距离函数。
2.2、内在Delaunay三角剖分 cotan Laplace 算子的标准离散化使用三角形网格中角度的余切。 内在的 Delaunay 算法构造了相同多面体的三角剖分这反过来又产生了不同的通常更精确的cotan Laplace 算子。从概念上讲iDT 的边缘仍然连接原始输入表面上的对顶点但现在允许沿着多面体是测地线路径并且不必对应于输入三角剖分的边缘。这些路径不是显式存储的相反我们只是在三角剖分更新时跟踪它们的长度。这些长度足以确定内在三角形的面积和角度进而确定新的 cotan Laplace 矩阵。 如果对角之和不小于 pi或者等价地如果对角之余切线为非负数则网格的边缘是局部 Delaunay。如果网格的所有边缘都是局部 Delaunay则网格是 Delaunay。 将给定的平面三角剖分转换为Delaunay三角剖分的标准算法是翻转网格中的非Delaunay边直到网格为Delaunay。同样单形表面的内在Delaunay三角剖分是通过执行内在边翻转来构造的。 设 K(V,E,T) 是一个二维流形三角形网格其中 V 是顶点集E 是边集T 是面集三角形集。设 L 是欧几里得距离集其中 L(eij)lij||pi−pj||其中 pi 和 pj 分别是顶点 i 和 j 在 R3 中的位置。然后将 (K,L)作为输入输入到 iDT 算法中该算法返回 (K~,L~)即内在 Delaunay 网格和内在长度。该算法如下 for all edge e in E : Mark(e)Stack s -- Ewhile !Empty(s) doedge(ij) Pop(s) and Unmark(edge(ij))if !Delaunay(edge(ij)) thenedge(kl) Flip(edge(ij)) and compute the new length length(kl) using the Cosine Theoremfor all edge e in {edge(kj), edge(jl), edge(li), edge(ik)} doif !Mark(e) thenMark(e) and Push(s,e)end ifend forend ifend while
return (~K,~L) 然后新的KL被用来像往常一样实现热方法。 我们在开始时已经举了一个例子其中内禀Delaunay三角化改进了结果。网格是通过给2D三角化赋予高程而获得的这导致了高度细长的三角形。 这种情况类似于任何具有非常小角度面的三角形网格如下图所示。 放置在没有iDT重新网格的网格上的等值线 使用iDT重新网格化放置在网格上的等值线
3、性能 算法的时间复杂度主要由线性求解器的选择决定。在目前的实施方案中Cholesky预系数约为ON1.5距离的计算大致为ON其中N是三角测量中的顶点数。该算法使用两个N×N 矩阵两者都具有相同的非零模式平均每行/列7个非零。计算成本与源集的大小无关。基运算包括稀疏数值线性代数双精度和基本算术运算包括平方根。 我们在英特尔酷睿i7-7700HQ 2.8HGz上执行基准测试并使用Visual Studio 2013进行编译。
Number of trianglesInitialization iDT (sec)Distance computation iDT (sec)Initialization Direct (sec)Distance computation Direct (sec)30,0000.180.020.120.01200,0001.821.311.320.11500,00010.450.758.070.551,800,00038.912.2435.681.1
4、其他 CGAL::Heat_method_3::estimate_geodesic_distances 是一个用于估计三维空间中给定源集的内在测地距离的函数。它使用热方法heat method来求解测地距离问题。 该函数接受一个三维三角形网格作为输入其中每个三角形由三个顶点表示。它还接受一个源集表示要计算测地距离的目标点集。 函数的工作原理如下首先它在三角形网格上定义一个初始温度场其中每个顶点的温度初始化为无穷大。然后它使用向后欧拉步backward Euler step对热方程进行离散化以更新温度场。在每个时间步长中函数计算每个顶点处的梯度并根据梯度更新温度值。随着时间的推移温度值逐渐接近测地距离最终收敛到稳定状态。函数返回收敛后的温度场其中每个顶点的温度值即为该顶点到源集的测地距离。 该函数使用了一些数学公式和概念来计算测地距离包括拉普拉斯算子、梯度、散度和离散化等。这些公式和概念在数学和物理中有广泛的应用特别是在计算几何和数值分析领域。 总结CGAL::Heat_method_3::estimate_geodesic_distances 是一个用于估计三维空间中给定源集的测地距离的函数它使用热方法进行求解。该函数通过离散化热方程并计算梯度来逼近测地距离最终返回收敛后的温度场作为结果。 CGAL::Heat_method_3::Surface_mesh_geodesic_distances_3 是一个用于计算三维网格上点到源集的测地距离的函数它使用热方法进行求解。该函数通过离散化热方程并计算梯度来逼近测地距离最终返回收敛后的温度场作为结果。
