c++ - Minecraft 克隆的最佳框选择方法

Question

我正在制作一个 Minecraft 克隆作为我的第一个 OpenGL 项目，并且卡在框选择部分。做出可靠的框选择的最佳方法是什么？

我一直在研究一些 AABB 算法，但它们都没有很好地解释它们到底做了什么(尤其是经过 super 调整的算法)，我不想使用我不理解的东西。

因为世界是由立方体组成的，所以我使用八叉树来消除光线转换计算的一些压力，基本上我唯一需要的就是这个函数:

float cube_intersect(Vector ray, Vector origin, Vector min, Vector max)
{
    //???
}

光线和原点很容易获得

Vector ray, origin, point_far;
double mx, my, mz;

gluUnProject(viewport[2]/2, viewport[3]/2, 1.0, (double*)modelview, (double*)projection, viewport, &mx, &my, &mz);
point_far = Vector(mx, my, mz);
gluUnProject(viewport[2]/2, viewport[3]/2, 0.0, (double*)modelview, (double*)projection, viewport, &mx, &my, &mz);
origin = Vector(mx, my, mz);
ray = point_far-origin;

最小值和最大值是立方体的对角。

我什至不确定这是正确的方法，考虑到我必须检查的立方体数量，即使是八叉树也是如此。

我也尝试过 gluProject，它可以工作，但是非常不可靠，并且没有给我选定的立方体面。

---

编辑

所以这就是我所做的:用射线计算空间中的位置:

float t = 0;
for(int i=0; i<10; i++)
{
    Vector p = ray*t+origin;
    while(visible octree)
    {
        if(p inside octree)
        {
            // then call recursive function until a cube is found
            break;
        }
        octree = octree->next;
    }
    if(found a cube)
    {
        break;
    }
    t += .5;
}

它实际上出奇地快，并在找到第一个立方体后停止。

如您所见，光线在找到立方体(实际上是空间中的一个位置)之前必须经过多个八叉树 - 屏幕中间有一个十字准线。增量步长越低，选择越精确，但也越慢。

Answer 1

将框作为基元使用在内存需求和处理能力方面是过大的。立方体非常适合渲染，即使在那里你也可以找到更高级的算法来为你提供更好的最终图像(Marching cubes)。 Minecraft 的图形在这个意义上非常原始，因为体素渲染已经存在很长时间并且已经取得了重大进展。

基本上，您应该利用所有盒子的间距和大小都相同这一事实。这些被称为体素。与您所拥有的相比，网格中的光线转换是微不足道的 - 宽相八叉树和窄相 AABB 测试。我建议您对体素和体素集碰撞检测/光线转换进行一些研究，因为您会发现这两种算法更容易实现并且运行速度更快。