algorithm - 查明 3d 空间中的特定三角形是否从给定点可见，并且可能有任意多个其他三角形

Question

如果 3D 空间中的三角形(由其顶点和法线指定)从 3D 空间中的给定点可见(由其 x、y 和 z co 指定)，我想编写一个返回“True”的函数rds) 鉴于空间中的其他三角形可能充当“障碍物”，阻止您从该点看到指定的三角形。

“看见”和“可见”是指可以用不与任何点相交的直线线将三角形上的任何点连接到观察点阻塞三角形。

hopefully this shows what I mean

我研究了“z 缓冲”和其他解决“可见性问题”的技术，但是由于我没有将三角形渲染成像素以通过特定视口(viewport)显示在屏幕上，我认为这些是不相关的。

我的两个天真的方法是；

1) 从观察点通过潜在“阻塞”三角形的每个顶点投影一条线到某个非常大的半径(对于我的应用程序，没有三角形距离观察点超过 1000 个单位，所以我会选择1001 个单位)。然后我会在三角形后面有一个区域，其边缘由我投影的线描述，在该区域中看不到对象。我会对所有阻挡物执行此操作，然后找到所有这些区域的并集，并检查我的测试三角形是否落在创建的(可能很多)区域之一内。

或

2) 再次向所有阻挡三角形顶点射线，找到这些线与待测三角形所在平面相交的点，得到平面中每个阻挡物的投影三角形。将任何重叠的投影三角形合并为一个多边形。然后检查被测三角形是否完全位于任何投影三角形或合并多边形内。

方法 1) 的问题在于，很难找到一个形状是否完全被 3D 体积包围，更难将相交的 3D 体积组合成一个大的 3D 体积。

方法 2) 的问题在某些情况下，通过阻塞三角形顶点的投影线永远不会碰到感兴趣的三角形的平面。也不能忽略这些情况，它们仍然可以遮挡感兴趣的三角形，它们只是在平面上投下无限长的阴影。

我倾向于方法 2，但就像我说的那样，这些方法似乎有点天真，如果有人能提出更优雅的解决方案，我会非常感兴趣!描述或伪代码是理想的，最终我希望在 matlab 或 c++ 中实现它，但现在让我们保持通用!

Answer 1

我也会采用您的第二种方法，但要进行一些修改。

首先，假设您要将三角形投影到某个平面上。这里有几架飞机可供选择，但我不确定哪架飞机更适合您:

您可以将所有三角形投影到您测试的三角形平面上。通过这种方式，如果您的遮挡三角形位于被测遮挡三角形的前面或后面，您可以轻松获得信息。不利之处在于，当您查看测试三角形上的掠角时，数值误差会增加并可能会破坏您的解决方案。

下一个选项，我将从它开始，选择 6 个轴对齐的平面之一进行投影。将它们想象成天空盒的墙壁。根据观察者和三角形的相对位置，您可以选择沿轴距离最大的一个。此外，选择与轴对齐的平面可能会稍微简化您的数学运算。

下一个选项可能是使用垂直于观察者和三角形中心之间的线的平面。当您将三角形放置在极端角度时，此选项可以最大限度地减少错误，但您需要自己进行测试。

投影测试三角形后，您可以计算它的边界矩形 - 这是您感兴趣的区域，您不需要知道它之外的任何内容。您可以计算 4 个穿过观察者和矩形边界的平面，就像典型的视锥体一样。

当您投影遮挡三角形时，您建议将它们全部连接成一个大多边形，但这样您最终可能会得到一个非常复杂的多边形。我会采取相反的方式，从您正在测试的投影三角形中减去投影遮挡物。在这种方法中，您不需要测试每个三角形组合，因为如果在任何时候您的投影三角形减少为空三角形 - 这意味着它已经被遮挡，无需测试其余的遮挡器。

这是最重要的部分:

据我所知，唯一不可能以这种方式投影的三角形是那些至少有一个顶点在观察者后面(或恰好在侧面)的三角形。所以对于那些你可以用你的截头体剪裁平面剪裁它们。裁剪一个三角形的结果可能包含很少的新三角形，但它们都将适合您上面定义的感兴趣区域。

如果您决定执行所有这些操作，请记住您的遮挡物可能在测试三角形后面，因此您需要考虑到这一点。最简单的解决方案是用经过测试的三角形平面将它们夹住，只留下前面的部分。