Лучший метод выбора коробки для клона Minecraft

Я делаю клон Minecraft в качестве своего самого первого проекта OpenGL и застрял в части выбора коробки. Каков наилучший способ сделать надежный выбор коробки?

Я прошел через некоторые алгоритмы AABB, но ни один из них не объясняет достаточно хорошо, что именно они делают (особенно супер-настроенные), и я не хочу использовать то, чего не понимаю.

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

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;
}

Это на самом деле удивительно быстро и останавливается после первого найденного куба.

альтернативный текст

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


c++ opengl picking
person Solenoid    schedule 02.01.2011    source источник

Ответы (3)


arrow_upward
5
arrow_downward

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

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

person Alexander Dzhoganov    schedule 03.01.2011
comment
Скопируйте то, что вы сказали, в Google и найдите следующее: metanetsoftware.com/technique/tutorialB.html Спасибо, намного лучше моего решения. - person Solenoid; 03.01.2011
comment
Согласен.. Я работал над клоном для xbox и обнаружил, что обработка вершин интенсивна.. переключился на марширующие кубы для моей следующей игры, и она работает намного быстрее (как Chrome APP в javascript!) мой Марс - person John David Five; 24.12.2011

arrow_upward
0
arrow_downward

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

person exe    schedule 22.01.2011

arrow_upward
0
arrow_downward

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

Я подробно рассказываю об этой теории здесь https://stackoverflow.com/a/18028366/94167.

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

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

person Scott Barnes    schedule 03.08.2013