Лучший метод выбора ящика для клона 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, это работает, но очень ненадежно и не дает мне выбранную грань куба.

---

EDIT

Итак, вот что я сделал: вычислил положение в пространстве с лучом:

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

Работа с блоками в качестве примитивов является чрезмерным требованием к памяти и вычислительной мощности.Кубы хороши для рендеринга, и даже там вы можете найти более продвинутые алгоритмы, которые дают вам лучшее конечное изображение (марширующие кубы).Графика Minecraft очень примитивна в этом смысле, так как рендеринг вокселей существует уже давно, и был достигнут значительный прогресс.

В основном вам следует использовать тот факт, что все ваши блоки имеют одинаковое расстояние и одинаковый размер.Они называются вокселями.Лучевое вещание в сетке тривиально по сравнению с тем, что у вас есть - широкофазное октавное дерево и узкофазный тест AABB.Я предлагаю вам немного изучить воксели и обнаружение столкновений с воксельными наборами / лучевую трансляцию, поскольку вы найдете оба алгоритма, которые проще в реализации и будут работать быстрее.

Answer 2

Я бы также сказал, что вам не нужно полагаться на фактические лучевые трансляции, чтобы определить, что визуализировать. Учитывая, что вы находитесь в предопределенном сеточном формировании, вы действительно не становитесь заложниками «точно видимых» требований. Если вы можете отследить положение вашей камеры и выделить компас NSWE некоторых видов, вы также можете использовать его, чтобы определить, должен ли буфер GPU даже учитывать массив вершин для рендеринга.

Я подробно расскажу об этой теории https://stackoverflow.com/a/18028366/94167

Но, используя Octree и Camera позиционирование + расстояние / границы камеры, вы в основном знаете, что видит пользователь, не прибегая к точным трассировкам лучей? Если вы можете объединить свои треугольники в более крупные для целей рендеринга, а затем использовать текстуру, чтобы вернуть видимость большого объема обратно в кубическую форму (небольшое расстояние от руки), вы значительно уменьшите количество вершин. Тогда это просто рендеринг корпуса и отслеживание того, каково направление вашей камеры и где она находится, xyz, вы можете уйти, допуская некоторые лица, которые не должны отображаться, поскольку это будет иметь минимальное влияние на производительность (особенно если ваши шейдеры сами выполняют часть работы)

Я продолжаю экспериментировать, отслеживая центральную точку камеры, чтобы определить ее горизонтальную фокусную точку, и исходя из этого вы можете определить угол, который, в свою очередь, определяет глубину фрагмента, который вы, вероятно, увидите в направлении, на которое он смотрит ,

Answer 3

Вам не нужна какая-либо явная структура октодерева в памяти. Все, что нужно, это байт [,,]. Просто лениво генерируйте 8 детей из ящика во время поиска (как шахматный движок генерирует игровые состояния детей).