Lançar raio para selecionar o bloco no jogo voxel

22

Estou desenvolvendo um jogo com um terreno semelhante ao Minecraft feito de blocos. Como a renderização básica e o carregamento de blocos estão concluídos agora, quero implementar a seleção de blocos.

Portanto, preciso descobrir qual bloco a câmera da primeira pessoa está enfrentando. Eu já ouvi falar de não projetar a cena inteira, mas decidi contra isso porque parece hacky e não é preciso. Talvez eu pudesse de alguma forma lançar um raio na direção da vista, mas não sei como verificar a colisão com um bloco nos meus dados voxel. É claro que esses cálculos devem ser feitos na CPU, pois preciso dos resultados para realizar operações de lógica do jogo.

Então, como eu poderia descobrir qual bloco está na frente da câmera? Se for preferível, como eu poderia lançar um raio e verificar colisões?

danijar
fonte
Eu nunca fiz isso sozinho. Mas você não pode simplesmente ter um "raio" (segmento de linha neste caso) do plano da câmera, um vetor normal, com um determinado comprimento (você só quer que ele esteja dentro de um raio) e ver se ele se cruza com um dos blocos. Presumo que o espaçamento parcial e o recorte também sejam implementados. Portanto, saber com quais blocos testar não deve ser um grande problema ... eu acho?
Sidar

Respostas:

21

Quando tive esse problema enquanto trabalhava em meus cubos , encontrei o artigo "Um algoritmo transversal voxel rápido para rastreamento de raios", de John Amanatides e Andrew Woo, 1987, que descreve um algoritmo que pode ser aplicado a esta tarefa; é preciso e precisa de apenas uma iteração de loop por voxel cruzada.

Eu escrevi uma implementação das partes relevantes do algoritmo do artigo em JavaScript. Minha implementação adiciona dois recursos: permite especificar um limite na distância do raycast (útil para evitar problemas de desempenho e definir um 'alcance' limitado) e também calcula qual face de cada voxel o raio digitou.

O originvetor de entrada deve ser dimensionado de forma que o comprimento lateral de um voxel seja 1. O comprimento do directionvetor não é significativo, mas pode afetar a precisão numérica do algoritmo.

O algoritmo opera usando uma representação parametrizada do raio origin + t * direction,. Para cada eixo de coordenadas, nós acompanhar o tvalor que teria se demos um passo suficiente para atravessar uma fronteira voxel ao longo desse eixo (ou seja, alterar a parte inteira da coordenada) nas variáveis tMaxX, tMaxYe tMaxZ. Em seguida, damos um passo (usando as variáveis stepe tDelta) ao longo de qualquer eixo que tenha menos tMax- ou seja, o limite de voxel mais próximo.

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

Link permanente para esta versão da fonte no GitHub .

Kevin Reid
fonte
1
Esse algoritmo também funciona para o espaço numérico negativo? Eu implementei o algoritmo apenas e geralmente estou impressionado. Funciona muito bem para coordenadas positivas. Mas, por alguma razão, obtenho resultados estranhos se algumas vezes coordenadas negativas estiverem envolvidas.
11113 danijar
2
@danijar eu não poderia obter o material intbounds / mod para trabalhar com o espaço negativo, então eu uso isso: function intbounds(s,ds) { return (ds > 0? Math.ceil(s)-s: s-Math.floor(s)) / Math.abs(ds); }. Como Infinityé maior que todos os números, também não acho que você precise se proteger contra ds.
Will
1
@BotskoNet Parece que você tem um problema com a falta de projeção para encontrar seu raio. Eu tive problemas assim desde o início. Sugestão: desenhe uma linha de origem para origem + direção, no espaço do mundo. Se essa linha não estiver embaixo do cursor ou se ela não aparecer como um ponto (já que X e Y projetados devem ser iguais), você terá um problema na desprojeção ( não faz parte do código desta resposta). Se é um ponto confiável sob o cursor, o problema está no raycast. Se você ainda tiver um problema, faça uma pergunta separada em vez de estender este tópico.
Kevin Reid
1
O caso da aresta é o local em que uma coordenada da origem do raio é um valor inteiro e a parte correspondente da direção do raio é negativa. O valor inicial de tMax para esse eixo deve ser zero, pois a origem já está na extremidade inferior de sua célula, mas, em vez disso, está 1/dsfazendo com que um dos outros eixos seja incrementado. A correção é escrever intfloorpara verificar se ambos dssão negativos e se sé um valor inteiro (mod retorna 0) e, nesse caso, retorna 0,0.
Codevarrior
2
Aqui está minha porta para o Unity: gist.github.com/dogfuntom/cc881c8fc86ad43d55d8 . Porém, com algumas mudanças adicionais: integrou as contribuições de Will e de codewarrior e possibilitou a transmissão em um mundo ilimitado.
Maxim Kamalov
1

Talvez veja o algoritmo de linha de Bresenham , principalmente se você estiver trabalhando com blocos de unidades (como a maioria dos jogos minecraft).

Basicamente, isso leva dois pontos e traça uma linha ininterrupta entre eles. Se você lançar um vetor do jogador para a distância máxima de escolha, poderá usá-lo e as posições dos jogadores como pontos.

Eu tenho uma implementação 3D em python aqui: bresenham3d.py .

salmonmoose
fonte
6
Um algoritmo do tipo Bresenham vai perder alguns blocos, no entanto. Ele não considera todos os blocos pelos quais o raio passa; pulará algumas em que o raio não se aproxime o suficiente do centro do bloco. Você pode ver isso claramente no diagrama da Wikipedia . O bloco 3º abaixo e 3º direito do canto superior esquerdo é um exemplo: a linha passa por ele (apenas), mas o algoritmo de Bresenham não o atinge.
Nathan Reed
0

Para encontrar o primeiro bloco na frente da câmera, crie um loop for que faça um loop de 0 a uma distância máxima. Em seguida, multiplique o vetor avançado da câmera pelo contador e verifique se o bloco nessa posição é sólido. Se estiver, armazene a posição do bloco para uso posterior e pare o loop.

Se você também deseja colocar blocos, escolher o rosto não é mais difícil. Basta voltar do bloco e encontrar o primeiro bloco vazio.

sem título
fonte
Não funcionaria, com um vetor para frente em ângulo seria muito possível ter um ponto antes de uma parte de um bloco e o ponto subsequente depois, sem o bloco. A única solução para isso seria reduzir o tamanho do incremento, mas seria necessário reduzi-lo a ponto de tornar outros algoritmos muito mais eficazes.
Phil
Isso funciona muito bem com meu mecanismo; Eu uso um intervalo de 0,1.
untitled
Como o @Phil apontou, o algoritmo perderia blocos onde apenas uma pequena borda é vista. Além disso, fazer um loop para trás para colocar blocos não funcionaria. Também teríamos de avançar e diminuir o resultado em um.
31513 danijar
0

Fiz um post no Reddit com minha implementação , que usa o Algoritmo de Linha de Bresenham. Aqui está um exemplo de como você o usaria:

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

Aqui está a própria implementação:

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
fonte
1
Como alguém nos comentários notou, seu código não está documentado. Embora o código possa ser útil, ele não responde bem à pergunta.
Anko