Keluarkan ray untuk memilih blok di game voxel

22

Saya mengembangkan game dengan medan seperti Minecraft yang terbuat dari balok. Karena rendering dasar dan pemuatan chunk dilakukan sekarang, saya ingin mengimplementasikan pemilihan blok.

Karena itu saya perlu mencari tahu blok apa yang dihadapi kamera orang pertama. Saya sudah mendengar tentang tidak memproyeksikan seluruh adegan tetapi saya memutuskan untuk tidak melakukannya karena kedengarannya gila dan tidak akurat. Mungkin saya entah bagaimana bisa melemparkan sinar ke arah tampilan, tetapi saya tidak tahu cara memeriksa tabrakan dengan blok di data voxel saya. Tentu saja perhitungan ini harus dilakukan pada CPU karena saya perlu hasil untuk melakukan operasi logika permainan.

Jadi bagaimana saya bisa mengetahui blok mana yang ada di depan kamera? Jika lebih disukai, bagaimana saya bisa melemparkan sinar dan memeriksa tabrakan?

danijar
sumber
Saya tidak pernah melakukannya sendiri. Tapi tidak bisakah Anda hanya memiliki "ray" (garis dalam kasus ini) dari bidang kamera, vektor normal, dengan panjang tertentu (Anda hanya ingin berada dalam radius) dan melihat apakah itu bersinggungan dengan salah satu blok. Saya berasumsi spasi dan kliping parsial diterapkan juga. Jadi mengetahui blok mana yang harus diuji dengan seharusnya tidak menjadi masalah besar ... saya pikir?
Sidar

Jawaban:

21

Ketika saya memiliki masalah ini saat mengerjakan Cubes saya , saya menemukan makalah "Algoritma Traversal Fast Voxel untuk Ray Tracing" oleh John Amanatides dan Andrew Woo, 1987 yang menjelaskan algoritma yang dapat diterapkan untuk tugas ini; itu akurat dan hanya perlu satu perulangan loop per voxel berpotongan.

Saya telah menulis implementasi dari bagian-bagian yang relevan dari algoritma kertas dalam JavaScript. Implementasi saya menambahkan dua fitur: memungkinkan menentukan batas jarak raycast (berguna untuk menghindari masalah kinerja serta mendefinisikan 'jangkauan' terbatas), dan juga menghitung wajah masing-masing voxel yang dimasukkan oleh sinar.

originVektor input harus diskalakan sedemikian sehingga panjang sisi voxel adalah 1. Panjang directionvektor tidak signifikan tetapi dapat mempengaruhi akurasi numerik algoritma.

Algoritma beroperasi dengan menggunakan representasi sinar yang parameter origin + t * direction,. Untuk setiap sumbu koordinat, kami melacak tnilai yang kita akan memiliki jika kita mengambil langkah yang cukup untuk menyeberangi batas voxel sepanjang sumbu yang (yaitu mengubah bagian integer dari koordinat) dalam variabel tMaxX, tMaxYdan tMaxZ. Kemudian, kita mengambil langkah (menggunakan variabel stepdan tDelta) di sepanjang sumbu mana yang memiliki paling sedikit tMax- yaitu batas voxel mana yang paling dekat.

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

Tautan permanen ke versi sumber ini di GitHub .

Kevin Reid
sumber
1
Apakah algoritma ini juga berfungsi untuk ruang angka negatif? Saya menerapkan algoritma hanya adil dan umumnya saya terkesan. Ini berfungsi baik untuk koordinat positif. Tetapi untuk beberapa alasan saya mendapatkan hasil yang aneh jika kadang-kadang melibatkan koordinat negatif.
danijar
2
@danijar Aku tidak bisa mendapatkan intbounds / mod hal untuk bekerja dengan ruang negatif, jadi saya menggunakan ini: function intbounds(s,ds) { return (ds > 0? Math.ceil(s)-s: s-Math.floor(s)) / Math.abs(ds); }. Karena Infinitylebih besar dari semua angka, saya tidak berpikir Anda perlu menjaga ds menjadi 0 di sana juga.
Will
1
@BotskoNet Sepertinya Anda memiliki masalah dengan unprojecting untuk menemukan ray Anda. Saya punya masalah seperti itu sejak awal. Saran: Gambar garis dari asal ke arah + arah, di ruang dunia. Jika garis itu tidak di bawah kursor, atau jika itu tidak muncul sebagai satu titik (karena diproyeksikan X dan Y harus sama) maka kamu mempunyai satu masalah di dalam proyeksi ( bukan bagian dari kode jawaban ini). Jika itu benar-benar titik di bawah kursor maka masalahnya ada di raycast. Jika Anda masih memiliki masalah, ajukan pertanyaan terpisah alih-alih memperpanjang utas ini.
Kevin Reid
1
Kasus tepi adalah di mana koordinat asal sinar adalah nilai integer, dan bagian yang sesuai dari arah ray adalah negatif. Nilai tMax awal untuk sumbu itu harus nol, karena titik asal sudah ada di tepi bawah selnya, tetapi malah 1/dsmenyebabkan salah satu sumbu lainnya bertambah. Cara mengatasinya adalah menulis intflooruntuk memeriksa apakah keduanya dsnegatif dan smerupakan nilai integer (mod mengembalikan 0), dan mengembalikan 0,0 dalam kasus itu.
codewarrior
2
Ini port saya untuk Unity: gist.github.com/dogfuntom/cc881c8fc86ad43d55d8 . Namun, dengan beberapa perubahan tambahan: kontribusi Will dan codewarrior yang terintegrasi dan memungkinkan untuk dilemparkan ke dunia yang tidak terbatas.
Maxim Kamalov
1

Mungkin melihat ke dalam algoritma garis Bresenham , terutama jika Anda bekerja dengan blok-unit (seperti kebanyakan gim minecraftish cenderung).

Pada dasarnya ini membutuhkan dua poin, dan melacak garis yang tidak terputus di antara mereka. Jika Anda melemparkan vektor dari pemain ke jarak pengambilan maksimum, Anda dapat menggunakan ini, dan posisi pemain sebagai poin.

Saya memiliki implementasi 3D dalam python di sini: bresenham3d.py .

salmonmoose
sumber
6
Algoritma tipe Bresenham akan melewatkan beberapa blok. Itu tidak mempertimbangkan setiap blok sinar melewati; itu akan melewati beberapa di mana sinar tidak cukup dekat dengan pusat blok. Anda dapat melihat ini dengan jelas dari diagram di Wikipedia . Blok ke-3 ke bawah dan ke-3 dari sudut kiri atas adalah contoh: garis melewatinya (nyaris) tetapi algoritma Bresenham tidak mengenai itu.
Nathan Reed
0

Untuk menemukan blok pertama di depan kamera, buat loop for yang loop dari 0 ke jarak maksimum. Kemudian, gandakan vektor maju kamera dengan penghitung dan periksa apakah blokir pada posisi itu solid. Jika ya, maka simpan posisi blok untuk digunakan nanti dan hentikan perulangan.

Jika Anda juga ingin dapat menempatkan balok, memetik wajah tidak lebih sulit. Cukup putar kembali dari blok dan temukan blok kosong pertama.

tanpa judul
sumber
Tidak akan bekerja, dengan vektor maju miring akan sangat mungkin untuk memiliki titik sebelum satu bagian dari blok, dan titik berikutnya setelah itu, kehilangan blok. Satu-satunya solusi dengan ini adalah mengurangi ukuran kenaikan, tetapi Anda harus mendapatkannya sangat kecil untuk membuat algoritma lain jauh lebih efektif.
Phil
Ini bekerja cukup baik dengan mesin saya; Saya menggunakan interval 0,1.
Tanpa judul
Seperti yang ditunjukkan @Phil, algoritme akan kehilangan blok di mana hanya tepi kecil yang terlihat. Selain itu, pengulangan ke belakang untuk menempatkan blok tidak akan berhasil. Kita harus mengulang ke depan juga dan mengurangi hasilnya satu per satu.
danijar
0

Saya membuat posting di Reddit dengan implementasi saya , yang menggunakan Algoritma Line Bresenham. Berikut ini contoh bagaimana Anda akan menggunakannya:

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

Inilah implementasinya sendiri:

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
sumber
1
Seperti yang diperhatikan seseorang di komentar, kode Anda tidak berdokumen. Walaupun kodenya mungkin membantu, itu tidak cukup menjawab pertanyaan.
Anko