6

我想知道如何编写一个精确的算法来计算参数表面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)，并且没有考虑到网格的地形是基于三角形的，因此输出点是网格的点，而不是利用曲面与三角形的交点计算的点并且严重依赖于必须设置的容差。

有人有更好的主意，或者可以为此目的带我去一个合适的图书馆吗？

4

2 回答 2

3

我会遍历每个三角形，并计算三角形与表面的交点。我会使用一个几何着色器，它将三角形作为输入，并输出线条。对于三角形中的每个顶点，计算到表面的有符号距离。然后遍历边：如果有两个顶点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° 时°。在这里，我只是过滤掉了 abs(dist) > 45° 的距离：

在此处输入图像描述

干净的方法是确定最近革命的指数。例如，[-pi, pi] 将是第 0 圈，[pi, 3pi] = 第 1 圈，等等。只有当两个距离指的是同一圈时，您才会发射。

于 2013-06-10T21:34:30.157 回答
1

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

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

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

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

于 2013-06-11T15:33:20.157 回答