我目前正在Unity中编写一个Minecraft克隆作为我的宠物项目，我正在尝试为它实现光线投射，这样我就能知道玩家看的是哪个区块（我也会将光线投射用于其他目的）。游戏的世界是一个完美的单位立方体的三维网格。网格的每个元素要么是实心的，要么不是。我希望能够从我的世界的任何一点发射一条射线，并得到射线击中它所经过的第一个固体块的表面的点。
下面是一个c#伪代码，它大概是我的游戏的样子：
// An aproximation of what Unity's Vector3 looks like.
public struct Vector3
{
public float x, y, z;
}
public class World
{
public bool[,,] blocks;
public bool IsSolid(Vector3 pos) // i.e. if pos is inside a solid block
{
return blocks[Math.Floor(pos.x), Math.Floor(pos.y), Math.Floor(pos.z)]
}
public Vector3 Raycast(Vector3 origin, Vector3 direction)
{
// some algorithm, that returns the point at which ray hits a solid block
}
}注意，Vector3的坐标可能不是整数，光线完全可能以分数坐标开始（或结束）。为了简单起见，你可以（也可以不）假设世界是无限的，光线最终总会击中某个块。记住，Raycast()应该返回光线击中立方体表面的点。
我可以使用的最佳算法是什么？我的优先级（按顺序）是：
1.速度-进行光线投射应该很快
1.优雅-算法应简单明了
1.通用性-算法应易于修改（即添加一些额外功能）。
以下是一些可能出现的问题的问答：
**问：**为什么不使用Unity自带的碰撞器和光线投射？
**答：**Unity的对撞机和光线投射太慢了，没有为我的需要进行优化，而且，这绝不是优雅的通用。
**问：**您想要一个算法的实现，还是只想要基本概念？
**答：**我只理解算法的基础就可以了，但我真的很喜欢实现（最好是C#）。
1条答案
按热度按时间fnx2tebb1#
这里有一些基本原则。你需要对线性代数相当熟悉才能尝试这个，并阅读和理解ray-plane intersection是如何工作的。
你的射线会从立方体内部开始，在正常情况下，我们可以通过检查射线方向是否与立方体面指向相同的方向来快速消除其中的三个面。这是通过检查矢量之间的点积符号来完成的。为了找到剩余的三个面中的第一个，我们对相应的平面进行相交测试，并选择最接近的一个，如果你知道撞击面，你就知道它撞击的是哪个立方体。如果那个立方体是空的，你就重复这个过程，直到你找到一个非空的立方体。你也可以添加一些检查来避免边缘情况，比如尽早消除所有平行于射线的平面。
然而，为了获得真实的速度，你真的需要某种树结构来减少检查的次数。有很多替代方案，kd树，r树等等，但是在这个特定的例子中，我可能会考虑sparse octree。这意味着你的立方体将是更大的2x2x2部分的一部分，在那里整个部分可以被标记为空，填充，部分填充等。这些部分也将被分组为更大的2x2x2部分等，直到你达到一些最大的大小，要么包含你的整个游戏区域，或一个独立的可加载单位，你的游戏区域，并有一些逻辑测试多个单位，如果需要的话。
光线投射的实现方式与简单情况下的八叉树差不多，只是现在立方体的大小是可变的，当你碰到一个面时，你需要遍历树，找到下一个要测试的立方体。
但要真正实现这一点，需要相当多的经验，无论是在概念上，还是在语言和硬件上。你可能还需要对你的实际游戏世界结构的洞察力，因为可能有一些不明显的捷径，你可以采取，大大有助于加速性能。因此，它不能保证你的实现将比内置单元更快。