网格与参数曲面的交点

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符号不同，则这些顶点之间的边与曲面相交。虽然我确信可以计算出精确的交集，但最简单的解决方案是线性插值，即

\n\n

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

\n\n

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

\n\n

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

\n\n

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

\n\n

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

\n\n

由于没有内部/外部，并且这个距离函数从 -90\xc2\xb0 到 90\xc2\xb0，所以只有当符号从小负变为小正时才能发出顶点，反之亦然，而当它翻转时则不能发出顶点从 90\xc2\xb0 到 -90\xc2\xb0。这里我简单地过滤掉了abs(dist) > 45\xc2\xb0的距离：

\n\n

\n\n

干净的方法是确定最接近的转数的索引。例如，[-pi, pi] 表示转数 0，[pi, 3pi] = 转数 1，等等。只有当两个距离指向同一转时，您才会发出信号。

\n