Cast ray, чтобы выбрать блок в воксельной игре

22

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

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

Итак, как я могу узнать, какой блок перед камерой? Если это предпочтительнее, как я могу навести луч и проверить столкновения?

Данияр
источник
Я никогда не делал это сам. Но разве вы не могли просто получить «луч» (в данном случае отрезок линии) от плоскости камеры, вектор нормали определенной длины (вы хотите, чтобы он был только в радиусе), и посмотреть, пересекается ли он с одним из блоки. Я предполагаю, что частичный интервал и отсечение также реализованы. Так что зная, с какими блоками тестировать, не должно быть такой большой проблемы ... я думаю?
Сидар

Ответы:

21

Когда у меня возникла эта проблема во время работы над моими кубами , я обнаружил статью «Быстрый алгоритм обхода вокселей для трассировки лучей» Джона Аманатида и Эндрю Ву, 1987 г., в которой описывается алгоритм, который можно применить к этой задаче; он точен и требует только одной итерации цикла на пересеченный воксель.

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

Входной originвектор должен быть масштабирован таким образом, чтобы длина стороны вокселя была равна 1. Длина directionвектора не является существенной, но может повлиять на числовую точность алгоритма.

Алгоритм работает с использованием параметризованного представления луча origin + t * direction. Для каждой оси координат, мы продолжаем отслеживать tзначение , которое мы имели бы , если бы мы сделали шаг достаточного , чтобы пересечь границу вокселей вдоль этой оси (то есть изменение целой части координат) в переменных tMaxX, tMaxYи tMaxZ. Затем, мы делаем шаг (используя stepи tDeltaпеременные) , вдоль какой оси имеет наименьшее tMax- то есть в зависимости от того вокселей-граница ближе.

/**
 * Call the callback with (x,y,z,value,face) of all blocks along the line
 * segment from point 'origin' in vector direction 'direction' of length
 * 'radius'. 'radius' may be infinite.
 * 
 * 'face' is the normal vector of the face of that block that was entered.
 * It should not be used after the callback returns.
 * 
 * If the callback returns a true value, the traversal will be stopped.
 */
function raycast(origin, direction, radius, callback) {
  // From "A Fast Voxel Traversal Algorithm for Ray Tracing"
  // by John Amanatides and Andrew Woo, 1987
  // <http://www.cse.yorku.ca/~amana/research/grid.pdf>
  // <http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.42.3443>
  // Extensions to the described algorithm:
  //   • Imposed a distance limit.
  //   • The face passed through to reach the current cube is provided to
  //     the callback.

  // The foundation of this algorithm is a parameterized representation of
  // the provided ray,
  //                    origin + t * direction,
  // except that t is not actually stored; rather, at any given point in the
  // traversal, we keep track of the *greater* t values which we would have
  // if we took a step sufficient to cross a cube boundary along that axis
  // (i.e. change the integer part of the coordinate) in the variables
  // tMaxX, tMaxY, and tMaxZ.

  // Cube containing origin point.
  var x = Math.floor(origin[0]);
  var y = Math.floor(origin[1]);
  var z = Math.floor(origin[2]);
  // Break out direction vector.
  var dx = direction[0];
  var dy = direction[1];
  var dz = direction[2];
  // Direction to increment x,y,z when stepping.
  var stepX = signum(dx);
  var stepY = signum(dy);
  var stepZ = signum(dz);
  // See description above. The initial values depend on the fractional
  // part of the origin.
  var tMaxX = intbound(origin[0], dx);
  var tMaxY = intbound(origin[1], dy);
  var tMaxZ = intbound(origin[2], dz);
  // The change in t when taking a step (always positive).
  var tDeltaX = stepX/dx;
  var tDeltaY = stepY/dy;
  var tDeltaZ = stepZ/dz;
  // Buffer for reporting faces to the callback.
  var face = vec3.create();

  // Avoids an infinite loop.
  if (dx === 0 && dy === 0 && dz === 0)
    throw new RangeError("Raycast in zero direction!");

  // Rescale from units of 1 cube-edge to units of 'direction' so we can
  // compare with 't'.
  radius /= Math.sqrt(dx*dx+dy*dy+dz*dz);

  while (/* ray has not gone past bounds of world */
         (stepX > 0 ? x < wx : x >= 0) &&
         (stepY > 0 ? y < wy : y >= 0) &&
         (stepZ > 0 ? z < wz : z >= 0)) {

    // Invoke the callback, unless we are not *yet* within the bounds of the
    // world.
    if (!(x < 0 || y < 0 || z < 0 || x >= wx || y >= wy || z >= wz))
      if (callback(x, y, z, blocks[x*wy*wz + y*wz + z], face))
        break;

    // tMaxX stores the t-value at which we cross a cube boundary along the
    // X axis, and similarly for Y and Z. Therefore, choosing the least tMax
    // chooses the closest cube boundary. Only the first case of the four
    // has been commented in detail.
    if (tMaxX < tMaxY) {
      if (tMaxX < tMaxZ) {
        if (tMaxX > radius) break;
        // Update which cube we are now in.
        x += stepX;
        // Adjust tMaxX to the next X-oriented boundary crossing.
        tMaxX += tDeltaX;
        // Record the normal vector of the cube face we entered.
        face[0] = -stepX;
        face[1] = 0;
        face[2] = 0;
      } else {
        if (tMaxZ > radius) break;
        z += stepZ;
        tMaxZ += tDeltaZ;
        face[0] = 0;
        face[1] = 0;
        face[2] = -stepZ;
      }
    } else {
      if (tMaxY < tMaxZ) {
        if (tMaxY > radius) break;
        y += stepY;
        tMaxY += tDeltaY;
        face[0] = 0;
        face[1] = -stepY;
        face[2] = 0;
      } else {
        // Identical to the second case, repeated for simplicity in
        // the conditionals.
        if (tMaxZ > radius) break;
        z += stepZ;
        tMaxZ += tDeltaZ;
        face[0] = 0;
        face[1] = 0;
        face[2] = -stepZ;
      }
    }
  }
}

function intbound(s, ds) {
  // Find the smallest positive t such that s+t*ds is an integer.
  if (ds < 0) {
    return intbound(-s, -ds);
  } else {
    s = mod(s, 1);
    // problem is now s+t*ds = 1
    return (1-s)/ds;
  }
}

function signum(x) {
  return x > 0 ? 1 : x < 0 ? -1 : 0;
}

function mod(value, modulus) {
  return (value % modulus + modulus) % modulus;
}

Постоянная ссылка на эту версию источника на GitHub .

Кевин Рид
источник
1
Этот алгоритм также работает для отрицательного числа? Я реализовал алгоритм только справедливо, и в целом я впечатлен. Отлично работает для положительных координат. Но по какой-то причине я получаю странные результаты, если иногда используются отрицательные координаты.
Данияр
2
@danijar я не мог получить intbounds / мод материала для работы с отрицательным пространством, поэтому я использую это: function intbounds(s,ds) { return (ds > 0? Math.ceil(s)-s: s-Math.floor(s)) / Math.abs(ds); }. Поскольку Infinityоно больше всех чисел, я не думаю, что вам нужно защищаться от того, чтобы ds был там 0.
Будет
1
@BotskoNet Похоже, у вас есть проблема с не проектированием, чтобы найти свой луч. У меня были такие проблемы на раннем этапе. Предложение: Нарисуйте линию от начала координат до направления + направление в мировом пространстве. Если эта линия не находится под курсором или если она не отображается в виде точки (поскольку проецируемые X и Y должны быть равны), у вас возникла проблема с непроекцией ( не являющейся частью кода этого ответа). Если это надежно точка под курсором, то проблема в raycast. Если у вас все еще есть проблема, пожалуйста, задайте отдельный вопрос вместо расширения этой темы.
Кевин Рид
1
В случае с краем координата начала луча является целочисленным значением, а соответствующая часть направления луча является отрицательной. Начальное значение tMax для этой оси должно быть равно нулю, поскольку начало координат уже находится у нижнего края его ячейки, но вместо этого оно 1/dsвызывает увеличение одной из других осей. Исправление состоит в том, чтобы написать, intfloorчтобы проверить, является ли оба dsотрицательным и sявляется целочисленным значением (mod возвращает 0), и возвращает 0.0 в этом случае
Codewarrior
2
Вот мой порт для Unity: gist.github.com/dogfuntom/cc881c8fc86ad43d55d8 . Тем не менее, с некоторыми дополнительными изменениями: интегрированы вклады Уилла и Codewarrior и стало возможным играть в неограниченном мире.
Максим Камалов
1

Возможно, обратите внимание на линейный алгоритм Брезенхэма , особенно если вы работаете с юнит-блоками (как это обычно бывает в большинстве игр Minecraftish).

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

У меня есть 3D-реализация в Python здесь: bresenham3d.py .

salmonmoose
источник
6
Однако алгоритм типа Брезенхема будет пропускать некоторые блоки. Он не учитывает каждый блок, через который проходит луч; он пропустит некоторые, в которых луч не подходит достаточно близко к центру блока. Вы можете ясно видеть это из диаграммы в Википедии . Например, блок 3-й вниз и 3-й справа от верхнего левого угла: линия проходит через нее (едва), но алгоритм Брезенхэма не попадает в него.
Натан Рид
0

Чтобы найти первый блок перед камерой, создайте цикл for, который проходит от 0 до некоторого максимального расстояния. Затем умножьте передний вектор камеры на счетчик и проверьте, является ли блок в этой позиции сплошным. Если это так, сохраните положение блока для последующего использования и прекратите цикл.

Если вы также хотите иметь возможность размещать блоки, выбор лица не сложнее. Просто вернитесь назад от блока и найдите первый пустой блок.

без названия
источник
Не сработает, с наклонным вектором вперед было бы очень возможно иметь точку перед одной частью блока, а следующую точку после пропуска блока. Единственным выходом из этого является уменьшение размера приращения, но вам нужно сделать его настолько маленьким, чтобы другие алгоритмы были намного эффективнее.
Фил
Это работает очень хорошо с моим двигателем; Я использую интервал 0,1.
без названия
Как указал @Phil, алгоритм пропустит блоки, в которых виден только небольшой край. Кроме того, цикл назад для размещения блоков не будет работать. Мы должны были бы также выполнить цикл вперед и уменьшить результат на единицу.
Данияр
0

Я сделал сообщение о Reddit с моей реализацией , в которой используется алгоритм Брезенхема. Вот пример того, как вы бы это использовали:

// A plotter with 0, 0, 0 as the origin and blocks that are 1x1x1.
PlotCell3f plotter = new PlotCell3f(0, 0, 0, 1, 1, 1);
// From the center of the camera and its direction...
plotter.plot( camera.position, camera.direction, 100);
// Find the first non-air block
while ( plotter.next() ) {
   Vec3i v = plotter.get();
   Block b = map.getBlock(v);
   if (b != null && !b.isAir()) {
      plotter.end();
      // set selected block to v
   }
}

Вот сама реализация:

public interface Plot<T> 
{
    public boolean next();
    public void reset();
    public void end();
    public T get();
}

public class PlotCell3f implements Plot<Vec3i>
{

    private final Vec3f size = new Vec3f();
    private final Vec3f off = new Vec3f();
    private final Vec3f pos = new Vec3f();
    private final Vec3f dir = new Vec3f();

    private final Vec3i index = new Vec3i();

    private final Vec3f delta = new Vec3f();
    private final Vec3i sign = new Vec3i();
    private final Vec3f max = new Vec3f();

    private int limit;
    private int plotted;

    public PlotCell3f(float offx, float offy, float offz, float width, float height, float depth)
    {
        off.set( offx, offy, offz );
        size.set( width, height, depth );
    }

    public void plot(Vec3f position, Vec3f direction, int cells) 
    {
        limit = cells;

        pos.set( position );
        dir.norm( direction );

        delta.set( size );
        delta.div( dir );

        sign.x = (dir.x > 0) ? 1 : (dir.x < 0 ? -1 : 0);
        sign.y = (dir.y > 0) ? 1 : (dir.y < 0 ? -1 : 0);
        sign.z = (dir.z > 0) ? 1 : (dir.z < 0 ? -1 : 0);

        reset();
    }

    @Override
    public boolean next() 
    {
        if (plotted++ > 0) 
        {
            float mx = sign.x * max.x;
            float my = sign.y * max.y;
            float mz = sign.z * max.z;

            if (mx < my && mx < mz) 
            {
                max.x += delta.x;
                index.x += sign.x;
            }
            else if (mz < my && mz < mx) 
            {
                max.z += delta.z;
                index.z += sign.z;
            }
            else 
            {
                max.y += delta.y;
                index.y += sign.y;
            }
        }
        return (plotted <= limit);
    }

    @Override
    public void reset() 
    {
        plotted = 0;

        index.x = (int)Math.floor((pos.x - off.x) / size.x);
        index.y = (int)Math.floor((pos.y - off.y) / size.y);
        index.z = (int)Math.floor((pos.z - off.z) / size.z);

        float ax = index.x * size.x + off.x;
        float ay = index.y * size.y + off.y;
        float az = index.z * size.z + off.z;

        max.x = (sign.x > 0) ? ax + size.x - pos.x : pos.x - ax;
        max.y = (sign.y > 0) ? ay + size.y - pos.y : pos.y - ay;
        max.z = (sign.z > 0) ? az + size.z - pos.z : pos.z - az;
        max.div( dir );
    }

    @Override
    public void end()
    {
        plotted = limit + 1;
    }

    @Override
    public Vec3i get() 
    {
        return index;
    }

    public Vec3f actual() {
        return new Vec3f(index.x * size.x + off.x,
                index.y * size.y + off.y,
                index.z * size.z + off.z);
    }

    public Vec3f size() {
        return size;
    }

    public void size(float w, float h, float d) {
        size.set(w, h, d);
    }

    public Vec3f offset() {
        return off;
    }

    public void offset(float x, float y, float z) {
        off.set(x, y, z);
    }

    public Vec3f position() {
        return pos;
    }

    public Vec3f direction() {
        return dir;
    }

    public Vec3i sign() {
        return sign;
    }

    public Vec3f delta() {
        return delta;
    }

    public Vec3f max() {
        return max;
    }

    public int limit() {
        return limit;
    }

    public int plotted() {
        return plotted;
    }



}
ClickerMonkey
источник
1
Как заметил кто-то в комментариях, ваш код недокументирован. Хотя код может быть полезным, он не совсем отвечает на вопрос.
Анко