Minecraft克隆的最佳盒子选择方法

Question

我正在制作一个Minecraft克隆作为我的第一个OpenGL项目,我被困在盒子选择部分.选择可靠的盒子的最佳方法是什么？

我一直在研究一些AABB算法,但是没有一个能够很好地解释它们到底做了什么(尤其是超级调整的算法)并且我不想使用我不理解的东西.

由于世界是由立方体组成的,我使用八叉树来消除光线投射计算的一些压力,基本上我唯一需要的是这个函数:

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;

min和max是立方体的对角.

考虑到我必须检查的立方体数量,即使是八叉树,我也不确定这是否是正确的方法.

我也试过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测试.我建议你研究一下体素和体素集碰撞检测/光线投射,因为你会发现两种算法都更容易实现并且运行速度更快.