如何在3D网格中找到光线相交的所有立方体？

Question

我需要从地面向太阳投射一条射线，并想知道是否有物体在阴影中。 我计划通过从地面立方体到太阳追踪一条线，并查找是否有任何物体挡道来完成这个任务。 然而，我不熟悉如何找到线穿过的所有立方体，以便测试它们是否被填充。 有人可以帮忙解决这个问题吗？

- Xavier

---

你可能想尝试 http://gamedev.stackexchange.com 。 - PrettyPrincessKitty FS

Answer 1

你想要执行一个（或者说很多）光线和盒子的交叉检测。以下是一个示例算法： http://www.siggraph.org/education/materials/HyperGraph/raytrace/rtinter3.htm 或者，如果你的立方体都是轴对齐的，并且紧密排列，你可以尝试使用Bresenham算法的三维版本（用于通过像素绘制线条）。

- Jackson Pope

Answer 2

“暴力方法是检查你的线上每一个立方体。如果我没记错，这里涉及到一些不平凡的几何学问题。啊，谷歌搜索“线立方体碰撞”出现了很多结果。这个看起来非常有希望。”

http://www.devmaster.net/forums/archive/index.php/t-371.html

基本上，它是这样的（我肯定会犯错）：

取组成立方体角落的8个顶点。我们将使用四边形来进行计算。

第一个任务是计算出所有6个面的法线，并将它们存储在某个数组中。要计算法线，必须使用与面平行的两个向量的叉积。从那个法线可以使用平面方程确保射线的终点在所有平面之外（结果> 0）。

好的，有些数学：

组成面ABCD的四个顶点（x，y，z）用于构造两个向量。 为了得到这两个向量，只需要简单地使用B-A和C-A（这意味着B.x - A.x，B.y - A.y等）。

我们有了两个平行向量A和B，我称它们为清晰度……

接下来还有几段类似的内容。

您可以做的一件可能加快速度的事情是确定立方体与所讨论的直线的距离有多近。 还需要更多的数学来找到给定点（立方体的中心）到直线上最近的点。

http://www.gamedev.net/community/forums/topic.asp?topic_id=185204

你不必在不知道是否会有碰撞的情况下做所有表面测试。

---

快速碰撞检测技巧： 在二维空间中两点之间的距离：sqrt(x^2 + y^2)。基本的。 但是如果你只想知道两个物体之间的相对距离，可以跳过平方根。

if ((x1^2 + y1^2) > (x2^2 + y2^2)) { // x1，y1比x2，y2更长。 }

平方根很昂贵，在内部循环中避免使用它们是一件好事，特别是在碰撞检测这样的任务中。

嘿，想到了一个办法。建立一个平面，该平面是您线条的延伸（例如直向垂直，y从不改变...等等）。获取所有立方体点的点积。如果它们全部在一侧（全部为正或全部为负），则该立方体未被平面“切割”，因此不能与该线相交。

点积很便宜。

现在再建立另一个垂直于第一个平面的平面，并再次获取您的点积。如果你的立方体也被这第二个平面所切割......糟糕，这种情况下仍然可能被切割两次而不在该线上。

第一个也是唯一的平面需要垂直于立方体中心和最近点之间的线（叉积时间）。如果那个平面切割了立方体（你的立方体顶点的点积既为正数又为负数），那么立方体与该线相交。

- Mark Storer