找到给定内部点的可见性多面体
Find visibility polyhedron given a point inside it
我已经准备好一些网格对象，这意味着我在数组中拥有网格的所有顶点和三角形。我还有一个可以用键盘箭头移动的点，只要该点在网格内部，我就想找到它的视点，也就是它可以看到的多面体的一部分。
我想到了非常简单的 O(n^2) 算法，意思是：
对于乱七八糟的每个三角形，我都画了一个由三角形的 3 个顶点和移动点组成的多面体。然后检查这个多面体是否与任何其他三角形相交。如果不是，则三角形包含在结果中。如果确实如此，我会进行一些计算以查看三角形的哪一部分是可见的。
显然，这很慢。在 2D 中找到更快的算法不是问题，但在这里我没有太多想法。
显然，必须有一种方法来避免检查与其他不可能相交的三角形的交点。所以我想一定有一种方法可以对 space 中的三角形进行排序？我应该如何处理整个问题？是否有像二维问题中那样的线性算法？
编辑：我应该使用 kd-tree 三角形排序方法吗？
这是去除隐藏部分的问题
为了应对4π立体角跨度，可以在以查询点为中心的立方体的六个面上进行投影。然后这就变成了一个普通的隐藏面去除问题，有几种成熟的算法可供使用。 https://en.wikipedia.org/wiki/Hidden_surface_determination
这是一个相当广泛的话题，算法的选择取决于将要进行的处理。
在您的特定情况下，使用 space 转换 (x,y,z) => (x/z,y/z,1/z) (以视点为中心），将中心投影变为平行投影。然后通过围绕小平面的 AABB，您可以将问题简化为在矩形集合中查找重叠的问题。这可以通过扫描线方法等来解决。
我已经准备好一些网格对象，这意味着我在数组中拥有网格的所有顶点和三角形。我还有一个可以用键盘箭头移动的点，只要该点在网格内部，我就想找到它的视点，也就是它可以看到的多面体的一部分。
我想到了非常简单的 O(n^2) 算法，意思是：
对于乱七八糟的每个三角形，我都画了一个由三角形的 3 个顶点和移动点组成的多面体。然后检查这个多面体是否与任何其他三角形相交。如果不是，则三角形包含在结果中。如果确实如此，我会进行一些计算以查看三角形的哪一部分是可见的。
显然，这很慢。在 2D 中找到更快的算法不是问题，但在这里我没有太多想法。
显然，必须有一种方法来避免检查与其他不可能相交的三角形的交点。所以我想一定有一种方法可以对 space 中的三角形进行排序？我应该如何处理整个问题？是否有像二维问题中那样的线性算法？
编辑：我应该使用 kd-tree 三角形排序方法吗？
这是去除隐藏部分的问题
为了应对4π立体角跨度，可以在以查询点为中心的立方体的六个面上进行投影。然后这就变成了一个普通的隐藏面去除问题，有几种成熟的算法可供使用。 https://en.wikipedia.org/wiki/Hidden_surface_determination
这是一个相当广泛的话题，算法的选择取决于将要进行的处理。
在您的特定情况下，使用 space 转换 (x,y,z) => (x/z,y/z,1/z) (以视点为中心），将中心投影变为平行投影。然后通过围绕小平面的 AABB，您可以将问题简化为在矩形集合中查找重叠的问题。这可以通过扫描线方法等来解决。