网格与参数曲面的交点

Question

我想知道如何编写一个精确的算法来计算参数曲面f : R^2 --> R^3和三角网格之间相交曲面的边界。

我想到了第一种方法：

nStepsU = 100
nStepsV = 100
tolerance=0.01 // pick some sensical value
intersectionVertices={}
for  u from minU to maxU in nStepsU:
    for v from minV to maxV in nStepsV:
        for v in verticesInMesh:
             if euclidean distance( f(u,v), v ) < tolerance:
                 add vertex v in a set

connect the vertices in intersectionVertices with a line strip
draw the vertices in intersectionVertices

该算法非常简单，但速度很慢(n^3)，并且没有考虑到网格的地形是基于三角形的，因此输出点是网格的点，而不是利用曲面与三角形的交点计算的点，并且严重依赖于必须设置的公差。

有没有更好的主意，或者有没有人可以带我去一个合适的库来实现这个目的？

Answer 1

我会迭代每个三角形，并计算三角形与曲面的交点。我会使用一个几何着色器，它将三角形作为输入，并输出线条。对于三角形中的每个顶点，计算到曲面的有符号距离。然后在边上迭代:如果有两个顶点，其中h具有不同的符号，则这些顶点之间的边与曲面相交。虽然我确信可以计算出确切的交叉点，但最简单的解决方案是线性插值，即

vec3 intersection = (h0 * v1 + h1 * v0) / (h0 + h1);

然后将每个交叉点输出为线段的顶点。

我发布的here代码可以帮助您入门。如果您只想绘制结果，您可能会遇到与我在该问题中描述的相同的问题。如果需要客户端上的顶点，可以使用transform feedback。

编辑:我刚刚做了一个小测试。作为我使用的距离函数

float distToHelicoid(in vec3 p)
{
  float theta = p.y / 5 + offset.x / 50;
  float a = mod(theta - atan(p.z, p.x), 2*PI) - PI; // [-PI, PI[
  if (abs(a) > PI/2)
    a = mod(theta - atan(-p.z, -p.x), 2*PI) - PI;
  return a;
}

由于没有内部/外部，并且此距离函数从-90°到90°，因此只有当符号从小负值变为小正值或从小正值变为小负值时，才能发射顶点，而不是在从90°翻转到-90°时发射顶点。这里我简单地过滤掉abs(dist) >45°的距离：

​

​

最干净的方法是确定最近旋转的指数。例如，-pi，pi将是旋转0，pi，3pi =旋转1，等等。只有当两个距离指向相同的旋转时，你才会发射。

Answer 2

如果曲面始终是螺旋面，则可以尝试将所有内容投影到绕Y轴的圆柱体上。

螺旋面的表面由与圆柱表面正交的直线组成，投影后将得到螺旋线。在将3D三角形网格投影到圆柱体上后，您将获得2D三角形网格(请注意，某些区域可能会被几层三角形覆盖)。

因此，任务变成了在2D三角形网格中寻找与螺旋相交的三角形，这是更简单的。如果您可以使用近似，您可以分割该螺旋，并使用某种类型的树来查找与螺旋相交的三角形。

当你有一个三角形与螺旋的相交部分，它的交点将是一个线段，你可以重新计算线段的三维坐标，这些线段的集合就是你的相交线。