如何在更高维空间上有效地追踪等值面
问问题
249 次
2 回答
1
你有一个N维的标量成本函数，
f ( y 0 , y 1 , .., y N ) ∊ ℝ, y ∊ ℝ</p>
但仅在规则的矩形网格中采样，
y k = Ψ k + ψ k x k，常数Ψ k ∊ ℝ 和ψ k ∊ ℝ，以及网格坐标x k ∊ ℕ</p>
问题是定位等值面i ，
f ( y 0 , y 1 , .., y N ) = C i
直接的方法是循环遍历网格中的每个单元格，并检查当前等值面是否与当前单元格相交，如果是，则描述当前单元格内的等值面部分。（Marching Cubes 是描述等值面如何与每个网格单元相交的一种方法。）
这里的限制是使用基于邻域的搜索，而不是检查每个单元格。
OP 有一个专门针对 3D 案例的先前问题，我在其中发布了示例代码grid.h和grid.c的链接（在 Pastebin.com，因为它们太长而无法包含内联）。
该实现与 OP 的切片方法完全不同。我的方法是直接、简单地遍历与当前等值面相交的网格单元。它缓存网格样本，并使用单独的地图（char每个网格单元一个）来跟踪哪些网格单元已被缓存、遍历和/或推送到堆栈以供稍后遍历。这种方法很容易扩展到三个以上的维度。尽管代码是针对三个维度编写的，但方法本身根本不是针对三个维度的；您需要做的就是调整数据结构以适应任何（合理的）维度。
等值面行走本身是微不足道的。您从等值面相交的任何网格单元开始，然后检查所有 2 N个最近的相邻单元以查看等值面是否也与这些相交。在实践中，您使用一堆要检查的网格单元位置和一个网格单元标记图，以避免重新检查已检查的网格单元。
因为每个网格单元的网格点样本数是 2 N，所以我的示例代码不是最优的：许多附近的网格点最终被评估以查看相邻的网格单元是否与等值面相交。（不是只检查界定等值面的网格点，而是检查属于等值面周围的任何网格单元的网格点。）随着N的增加，这项额外的工作呈指数增长。
更好的方法是分别考虑 2 N个可能的 ( N -1) 面中的每一个，以避免检查等值面根本不相交的单元格。
在N维规则矩形网格中，每个单元都是一个N维长方体，由顶点（角）处的 2 N个网格点定义。N个长方体单元具有N ( N -1) 个二维面和 2 个N ( N -1) 维面。
要检查每个 ( N -1) 面，您需要检查定义该 ( N -1) 面的 2 N -1个网格点的成本函数。如果这些点的成本函数跨越等值面值，则等值面与 ( N -1) 面相交，并且等值面也与该方向上的下一个网格单元相交。
有两个 ( N -1) 面垂直于每个轴。如果等值面与 ( N -1) 面相交更接近负无穷，则等值面也与沿该轴的下一个网格单元相交，朝向负无穷。类似地，如果等值面与 ( N -1) 面相交更接近于正无穷大，那么它也会沿着该轴与下一个网格单元相交，朝向正无穷大。因此，( N -1) 个面非常适合决定是否应该检查哪些相邻单元格。这是真的，因为 ( N -1) 面正是两个单元共享的网格点集。
我非常不愿意提供示例 C 代码，因为到目前为止，针对 3D 案例的相同方法的示例代码似乎对任何人都没有帮助。我担心需要用 2 维和 3 维示例图像进行更长的解释，以便以易于理解的术语描述该方法；如果没有牢牢掌握逻辑，任何示例代码都会看起来像 gobbledygook。
于 2015-05-24T23:38:23.280 回答
1
您最好使用二维库，您可以尝试 Paul Bourke 教授的 conrec 算法。它类似于一个行进立方体。
于 2015-05-25T06:50:44.927 回答