dimensions - 高维等值面跟踪

Question

如何有效地在更高维空间上追踪等值面

Answer 1

你有一个 N 维的标量成本函数，

f(y₀, y₁, .., y_N) ∊ ℝ,   y ∊ ℝ

但仅在规则的矩形网格中采样，

y_k = Ψ_k + ψ_k x_k,   constants Ψ_k ∊ ℝ and ψ_k ∊ ℝ, and grid coordinates x_k ∊ ℕ

问题是定位等值面i，

f(y₀, y₁, .., y_N) = C_i

直接的方法是循环遍历网格中的每个单元格，并检查当前等值面是否与当前单元格相交，如果是，则描述当前单元格内的等值面部分。 (Marching Cubes 是描述等值面如何与每个网格单元相交的一种方法。)

这里的限制是使用基于邻域的搜索而不是检查每个单元格。

OP 有一个 previous question专门针对 3D 案例，我 posted示例代码的链接， grid.h和 grid.c (在 Pastebin.com 上，因为它们太长而无法包含内联)。

该实现与 OP 的切片方法完全不同。我的是在与当前等值面相交的网格单元上进行直接、简单的遍历。它缓存网格样本，并使用单独的映射(每个网格单元一个 char)来跟踪哪些网格单元已被缓存、遍历和/或推送到堆栈以供稍后遍历。这种方法很容易扩展到三个以上的维度。尽管代码完全是针对三个维度编写的，但该方法本身根本不特定于三个维度；您需要做的就是调整数据结构以适应任何(合理的)维数。

等值面游走本身是微不足道的。您从等值面相交的任何网格单元开始，然后检查所有 2N 个最近邻单元以查看等值面是否也与这些单元相交。在实践中，您使用一堆要检查的网格单元位置和网格单元标志图以避免重新检查已检查的网格单元。

因为每个网格单元的网格点样本数是 2N，所以我的示例代码不是最佳的:许多附近的网格点最终会被评估以查看相邻的网格单元是否与等值面相交。 (不是只检查界定等值面的网格点，而是检查属于等值面周围任何网格单元的网格点。)随着 N 的增加，这项额外工作呈指数增长。

更好的方法是分别考虑 2N 个可能的 (N-1) 个面中的每一个，以避免检查等值面根本不相交的单元格。

在 N 维规则矩形网格中，每个单元格都是一个 N 维长方体，由顶点(角)处的 2N 个网格点定义。 N 个长方体单元格有 N(N-1) 个二维面和 2N 个 (N-1) 维面。

要检查每个 (N-1) 面，您需要检查定义该 (N-1) 面的 2N-1 个网格点处的成本函数。如果这些点的成本函数跨越等值面值，则等值面与 (N-1) 面相交，并且等值面也与该方向的下一个网格单元相交。

有两个 (N-1) 面垂直于每个轴。如果等值面与更接近负无穷大的 (N-1) 面相交，则等值面也将沿着该轴与下一个网格单元相交，朝向负无穷大。类似地，如果等值面与更接近正无穷大的 (N-1) 面相交，那么它也沿着该轴与下一个网格单元相交，也朝向正无穷大。因此，(N-1)-faces 非常适合决定应该检查或不检查哪些相邻单元格。这是真的，因为 (N-1) 面正是两个单元共享的网格点集。

我很犹豫是否提供示例 C 代码，因为到目前为止，用于 3D 案例的相同方法的示例代码似乎没有帮助任何人。我担心需要用 2 维和 3 维示例图像进行更长的解释来以易于理解的术语描述该方法；如果没有牢牢掌握逻辑，任何示例代码都会看起来像 gobbledygook。