网格与参数曲面的交集

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），并没有考虑到网格的拓扑结构是基于三角形的，因此输出的点是网格的点而不是利用曲面与三角形相交产生的计算点，并且严重依赖于所设置的公差。

是否有更好的想法或者能够为我推荐一个合适的库来解决这个问题？

- linello

---

你有关于表面的任何其他信息吗？你能有效地进行投影吗？你能高效地找到一个点在它的哪一侧吗？ - maxim1000

表面是一个螺旋曲面 x(r,theta) = r*cos(theta),y(r,theta) = theta,z(r,theta) = r*sin(theta)，因此不可能区分内部和外部。 - linello

哦，对了。所以我的答案并不完全准确。但是你仍然可以从（x，y，z）确定θ和r，并计算出有符号的距离。我不太清楚的是，你期望这个有多精确？如果一个三角形在y方向上与表面交叉多次怎么办？ - Andreas Haferburg

Answer 1

我会遍历每个三角形，并计算与表面相交的位置。我将使用几何着色器作为输入三角形，并输出线条。对于三角形中的每个顶点，计算到表面的有符号距离。然后遍历边缘：如果有两个顶点的 h 符号不同，则连接这些顶点的边缘与表面相交。虽然我确定可以计算出确切的交点，但最简单的解决方案是进行线性插值，即

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

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

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

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

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°翻转时发出。在这里，我简单地过滤了绝对值大于45°的距离:

清晰明了的方式是确定最接近的革命的索引。例如，[-pi，pi] 将是第0个革命，[pi，3pi] = 革命1，依此类推。然后只有在两个距离指向同一革命时才会发出。

- Andreas Haferburg

---

我喜欢你的方法，唯一的问题是我需要更好地学习几何着色器，因为我总是觉得它们非常难以理解。为了降低复杂性，我还考虑使用自定义顶点着色器，将符合接近条件的顶点颜色设置为红色。你有没有任何好的链接可以介绍如何将三角形上传到几何着色器？ - linello

@linello，我为螺旋面添加了一个距离函数。 - Andreas Haferburg

我很难弄清如何将参数螺旋曲面方程翻译成着色器语言。 如果我的螺旋曲面是 x(r,theta)=r cos(theta) y(r,theta)= c*theta z(r,theta)=r sin(theta)`，那么我的螺旋曲面交点函数应该如何编写？我不明白为什么你把 theta 称作顶点的 y 坐标，以及如何平移这个螺旋曲面。 - linello

你有一个方程 (x,y,z) = f(theta, r)。我的目标是解出 theta 和 r。解出 theta 是最容易的，因为 y 只与 theta 线性相关，并且与 r 无关：y=c*theta，所以 theta=y/c。从几何角度来看，我正在通过法向量为 (0,1,0) 的平面与螺旋面相交于点 (0,y,0)。要移动螺旋面，可以偏移 y 或者 theta，因为它们之间是线性关系。换句话说，将螺旋面向上平移与绕 y 轴旋转是等效的。 - Andreas Haferburg

我已经按照你的建议修改了着色器：float distToHelicoid(in vec3 p, in vec3 offset,float baseTheta) { float helicoidC = 1.0; float theta = (p.y -offset.y)/helicoidC+baseTheta; float a = mod(theta - atan(p.z-offset.z, p.x-offset.x), 2*PI) - PI; // [-PI, PI[ return a; }其中helicoidC是你的参数c。此外，我想计算一个更好的交点，而不是使用插值，因为在某些情况下，我得到的线条非常折线。 - linello

Answer 2

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

螺旋状表面由垂直于该圆柱体表面的线组成，在投影后你将得到一个螺旋形。在将3D三角网格投影到该圆柱体上后，你将得到2D三角网格（请注意，某些区域可能被几层三角形覆盖）。

因此，任务变成了查找与螺旋线相交的2D三角网格中的三角形，这更简单。如果您可以接受近似值，您可以将该螺旋线分段，并使用某种树来查找与螺旋线相交的三角形。

当您有一个三角形与螺旋线的某个部分相交时，它们的交点将是一条线段，您只需重新计算该线段的3D坐标，这些线段的集合就是您的交线。

- maxim1000