Cast ray para seleccionar el bloque en el juego de vóxel

22

Estoy desarrollando un juego con un terreno similar a Minecraft hecho de bloques. Dado que la renderización básica y la carga de fragmentos se realizan ahora, quiero implementar la selección de bloques.

Por lo tanto, necesito averiguar a qué bloque se enfrenta la cámara en primera persona. Ya escuché que no se proyectó toda la escena, pero decidí no hacerlo porque suena raro y no es exacto. Quizás de alguna manera podría lanzar un rayo en la dirección de la vista, pero no sé cómo verificar la colisión con un bloque en mis datos de vóxel. Por supuesto, estos cálculos deben hacerse en la CPU ya que necesito los resultados para realizar operaciones de lógica de juego.

Entonces, ¿cómo podría averiguar qué bloque está delante de la cámara? Si es preferible, ¿cómo podría lanzar un rayo y verificar las colisiones?

danijar
fuente
Nunca lo hice yo mismo. Pero, ¿no podría simplemente tener un "rayo" (segmento de línea en este caso) desde el plano de la cámara, un vector normal, con una cierta longitud (solo desea que esté dentro de un radio) y ver si se cruza con uno de los bloques Supongo que también se implementa el espacio parcial y el recorte. Entonces, saber con qué bloques probar no debería ser un gran problema ... ¿creo?
Sidar

Respuestas:

21

Cuando tuve este problema mientras trabajaba en mis Cubos , encontré el artículo "Un algoritmo de desplazamiento rápido de vóxel para el trazado de rayos" de John Amanatides y Andrew Woo, 1987, que describe un algoritmo que se puede aplicar a esta tarea; es precisa y solo necesita una iteración de bucle por vóxel intersectado.

He escrito una implementación de las partes relevantes del algoritmo del artículo en JavaScript. Mi implementación agrega dos características: permite especificar un límite en la distancia de la emisión de rayos (útil para evitar problemas de rendimiento, así como definir un 'alcance' limitado), y también calcula qué cara de cada vóxel ingresó el rayo.

El originvector de entrada se debe escalar de modo que la longitud lateral de un vóxel sea 1. La longitud del directionvector no es significativa, pero puede afectar la precisión numérica del algoritmo.

El algoritmo funciona mediante el uso de una representación parametrizada del rayo, origin + t * direction. Para cada eje de coordenadas, hacemos un seguimiento de la tvalor que tendríamos si tomamos un paso suficiente para cruzar un límite voxel largo de ese eje (es decir, cambiar la parte entera de la coordenada) en las variables tMaxX, tMaxYy tMaxZ. Luego, damos un paso (usando las variables stepy tDelta) a lo largo del eje que tenga menos tMax, es decir, el límite de vóxel más cercano.

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

Enlace permanente a esta versión de la fuente en GitHub .

Kevin Reid
fuente
1
¿Este algoritmo también funciona para el espacio de números negativos? Implementé el algoritmo solo y, en general, estoy impresionado. Funciona muy bien para coordenadas positivas. Pero por alguna razón obtengo resultados extraños si las coordenadas negativas están involucradas a veces.
danijar
2
@danijar no pude conseguir las cosas intbounds / mod de trabajo con el espacio negativo, así que utilizo la siguiente: function intbounds(s,ds) { return (ds > 0? Math.ceil(s)-s: s-Math.floor(s)) / Math.abs(ds); }. Como Infinityes mayor que todos los números, tampoco creo que deba protegerse de que ds sea 0 allí.
Será el
1
@BotskoNet Parece que tiene un problema al no proyectar para encontrar su rayo. Tuve problemas así desde el principio. Sugerencia: Dibuje una línea desde el origen hasta el origen + dirección, en el espacio mundial. Si esa línea no está debajo del cursor, o si no aparece como un punto (ya que X e Y proyectados deberían ser iguales), entonces tiene un problema en la no proyección ( no forma parte del código de esta respuesta). Si es confiablemente un punto debajo del cursor, entonces el problema está en la emisión de rayos. Si todavía tiene un problema, haga una pregunta por separado en lugar de extender este hilo.
Kevin Reid
1
El caso de borde es donde una coordenada del origen del rayo es un valor entero, y la parte correspondiente de la dirección del rayo es negativa. El valor inicial de tMax para ese eje debe ser cero, ya que el origen ya está en el borde inferior de su celda, pero en cambio está 1/dscausando que se incremente uno de los otros ejes. La solución es escribir intfloorpara verificar si ambos dsson negativos y si ses un valor entero (mod devuelve 0), y devuelve 0.0 en ese caso.
codewarrior
2
Aquí está mi puerto a Unity: gist.github.com/dogfuntom/cc881c8fc86ad43d55d8 . Sin embargo, con algunos cambios adicionales: se integraron las contribuciones de Will y codewarrior y se hizo posible lanzar en un mundo ilimitado.
Maxim Kamalov
1

Tal vez busque en el algoritmo de línea de Bresenham , especialmente si está trabajando con bloques de unidades (como suelen hacer la mayoría de los juegos de minecraft).

Básicamente, esto toma dos puntos, y traza una línea continua entre ellos. Si lanzas un vector desde el jugador a su distancia máxima de selección, puedes usar esto, y los jugadores se posicionan como puntos.

Tengo una implementación 3D en python aquí: bresenham3d.py .

salmón
fuente
66
Sin embargo, un algoritmo de tipo Bresenham perderá algunos bloques. No considera cada bloque por el que pasa el rayo; se saltará algunos en los que el rayo no se acerque lo suficiente al centro del bloque. Puedes ver esto claramente en el diagrama de Wikipedia . El bloque 3º hacia abajo y 3º desde la esquina superior izquierda es un ejemplo: la línea lo atraviesa (apenas) pero el algoritmo de Bresenham no lo alcanza.
Nathan Reed
0

Para encontrar el primer bloque frente a la cámara, cree un bucle for que recorra de 0 a cierta distancia máxima. Luego, multiplique el vector de avance de la cámara por el contador y verifique si el bloque en esa posición es sólido. Si es así, almacene la posición del bloque para su uso posterior y detenga el bucle.

Si también desea poder colocar bloques, la selección de caras no es más difícil. Simplemente retroceda desde el bloque y encuentre el primer bloque vacío.

intitulado
fuente
No funcionaría, con un vector en ángulo hacia adelante sería muy posible tener un punto antes de una parte de un bloque, y el siguiente punto después, sin el bloque. La única solución con esto sería reducir el tamaño del incremento, pero tendría que hacerlo tan pequeño como para que otros algoritmos sean mucho más efectivos.
Phil
Esto funciona bastante bien con mi motor; Yo uso un intervalo de 0.1.
sin título el
Como señaló @Phil, el algoritmo perdería bloques donde solo se ve un pequeño borde. Además, el bucle hacia atrás para colocar bloques no funcionaría. Tendríamos que avanzar también y disminuir el resultado en uno.
danijar
0

Hice una publicación en Reddit con mi implementación , que utiliza el Algoritmo de línea de Bresenham. Aquí hay un ejemplo de cómo lo usarías:

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

Aquí está la implementación en sí:

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
fuente
1
Como alguien en los comentarios notó, su código no está documentado. Si bien el código puede ser útil, no responde a la pregunta.
Anko