algorithm - 与四面体相交的线段

Question

我正在尝试编写 C++ 代码来查找与四面体相交的线段的交点。我这样减少了问题:

1. 对于四面体(三角形)的每个面，找到线段的交点。然后，我有三种情况:a) 该线段不与任何面相交 - 因此该线段要么完全在四面体中，要么完全在四面体之外。b) 该段只与一个面相交。然后我只需要确定四面体中线段的一侧，然后我得到四面体中的两个点。c) 该线段与两个面相交。

我在实现这个算法时遇到了问题。以下是问题:

1. 如果线段和三角形在同一平面上，如何找到交点？
2. 如何确定线段是否位于四面体的边缘之一？

谢谢。

Answer 1

提示:

您无法避免复杂的案例讨论。这里介绍线段和三角形的平面情况。

三角形的边定义了 3 条直线，将平面划分为 7 个区域，一个有界区域和 6 个无界区域。在图中，它们由将点的坐标插入这些直线的三个隐式方程中时获得的符号指定。

如果需要考虑正好在一边的端点，则需要在讨论中添加 6 条半线和 3 条线段。

然后取开始和结束区域的所有可能组合。

许多案例都很简单。当两个线段端点属于同一区域时，线段全部在内部或外部；当其中一个区域是 +++ 而另一个区域不同时，恰好有一个交集...

在图中(--+ to ++-)，你肯定有一个与底边的交点；但不确定哪一边是另一侧相交:要回答这个问题，您需要知道顶部顶点位于线段的哪一侧。

如果有勇气，您可以讨论所有 16 x 15/2 = 120 的情况，其中许多与元素的排列相同。

与3D问题相比，这只是开胃菜。