Wirke einen Strahl, um einen Block im Voxel-Spiel auszuwählen

22

Ich entwickle ein Spiel mit einem Minecraft-ähnlichen Gelände aus Blöcken. Da das grundlegende Rendern und Laden von Chunks jetzt erfolgt, möchte ich die Blockauswahl implementieren.

Deshalb muss ich herausfinden, welchem ​​Block die Kamera der ersten Person gegenübersteht. Ich habe schon davon gehört, dass ich die ganze Szene nicht projiziert habe, aber ich habe mich dagegen entschieden, weil es hackig klingt und nicht genau ist. Vielleicht könnte ich einen Strahl in Blickrichtung werfen, aber ich weiß nicht, wie ich die Kollision mit einem Block in meinen Voxeldaten überprüfen soll. Natürlich müssen diese Berechnungen auf der CPU durchgeführt werden, da ich die Ergebnisse benötige, um Spiellogikoperationen durchzuführen.

Wie kann ich also herausfinden, welcher Block sich vor der Kamera befindet? Wie könnte ich einen Strahl werfen und Kollisionen überprüfen, wenn es vorzuziehen ist?

danijar
quelle
Ich habe es nie selbst gemacht. Aber könnten Sie nicht einfach einen "Strahl" (in diesem Fall ein Liniensegment) von der Kameraebene aus haben, einen normalen Vektor mit einer bestimmten Länge (Sie möchten nur, dass er sich innerhalb eines Radius befindet) und prüfen, ob er sich mit einem der Liniensegmente schneidet? Blöcke. Ich gehe davon aus, dass auch Teilabstände und Clipping implementiert sind. Zu wissen, mit welchen Blöcken getestet werden soll, sollte also kein so großes Problem sein ... denke ich?
Sidar

Antworten:

21

Als ich dieses Problem bei der Arbeit an meinen Cubes hatte , fand ich die Arbeit "Ein schneller Voxel-Traversal-Algorithmus für die Raytracing" von John Amanatides und Andrew Woo, 1987, die einen Algorithmus beschreibt, der auf diese Aufgabe angewendet werden kann. es ist genau und benötigt nur eine Schleifeniteration pro durchschnittenem Voxel.

Ich habe eine Implementierung der relevanten Teile des Algorithmus des Papiers in JavaScript geschrieben. Meine Implementierung fügt zwei Funktionen hinzu: Sie ermöglicht das Festlegen einer Grenze für die Entfernung des Raycasts (nützlich zum Vermeiden von Leistungsproblemen sowie zum Definieren einer begrenzten Reichweite) und das Berechnen der Fläche jedes Voxels, in das der Ray eingegeben wurde.

Der Eingabevektor originmuss so skaliert werden, dass die Seitenlänge eines Voxels 1 beträgt. Die Länge des directionVektors ist nicht signifikant, kann jedoch die numerische Genauigkeit des Algorithmus beeinflussen.

Der Algorithmus arbeitet unter Verwendung einer parametrisierten Darstellung des Strahls origin + t * direction. Für jede Koordinatenachse, verfolgen wir den tWert, den wir haben würde , wenn wir ein Voxel Grenze entlang dieser Achse (dh Änderung der ganzzahlige Teil der Koordinate) in den Variablen einen Schritt ausreichend zu durchqueren hat tMaxX, tMaxYund tMaxZ. Dann machen wir einen Schritt (unter Verwendung der Variablen stepund tDelta) entlang derjenigen Achse, die die geringste hat tMax- dh derjenigen, die der Voxelgrenze am nächsten liegt.

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

Permanenter Link zu dieser Version der Quelle auf GitHub .

Kevin Reid
quelle
1
Funktioniert dieser Algorithmus auch für den negativen Zahlenraum? Ich habe den Algorithmus gerade erst implementiert und bin im Allgemeinen beeindruckt. Es funktioniert gut für positive Koordinaten. Aber aus irgendeinem Grund bekomme ich seltsame Ergebnisse, wenn manchmal negative Koordinaten beteiligt sind.
Danijar
2
@danijar Ich konnte die Intbounds / Mod-Inhalte nicht für negative Leerzeichen verwenden function intbounds(s,ds) { return (ds > 0? Math.ceil(s)-s: s-Math.floor(s)) / Math.abs(ds); }. Da Infinityes größer als alle Zahlen ist, glaube ich nicht, dass Sie ds davor schützen müssen, dort 0 zu sein.
Will
1
@BotskoNet Das hört sich so an, als hättest du ein Problem mit der Projektionsentfernung, um deinen Strahl zu finden. Ich hatte schon früh solche Probleme. Vorschlag: Zeichnen Sie im Weltraum eine Linie von Ursprung zu Ursprung + Richtung. Befindet sich diese Linie nicht unter dem Cursor oder erscheint sie nicht als Punkt (da projiziertes X und Y gleich sein sollten), liegt ein Problem bei der Entprojektion vor ( nicht Teil des Codes dieser Antwort). Wenn es sich zuverlässig um einen Punkt unter dem Cursor handelt, liegt das Problem im Raycast. Wenn Sie immer noch ein Problem haben, stellen Sie bitte eine separate Frage, anstatt diesen Thread zu erweitern.
Kevin Reid
1
Der Kantenfall ist, wenn eine Koordinate des Strahlursprungs ein ganzzahliger Wert ist und der entsprechende Teil der Strahlrichtung negativ ist. Der anfängliche tMax-Wert für diese Achse sollte Null sein, da sich der Ursprung bereits am unteren Rand der Zelle befindet. Stattdessen wird jedoch 1/dseine der anderen Achsen inkrementiert. Der Fix besteht darin, zu schreiben intfloor, um zu prüfen, ob beide dsnegativ und sein ganzzahliger Wert sind (mod gibt 0 zurück), und in diesem Fall 0.0 zurückzugeben.
Codewarrior
2
Hier ist mein Port zu Unity: gist.github.com/dogfuntom/cc881c8fc86ad43d55d8 . Mit einigen zusätzlichen Änderungen: Die Beiträge von Will und Codewarrior wurden integriert und es wurde möglich, in einer unbegrenzten Welt zu wirken.
Maxim Kamalov
1

Schauen Sie sich vielleicht Bresenhams Linienalgorithmus an , besonders wenn Sie mit Unit-Blocks arbeiten (wie es die meisten minecraftischen Spiele tun).

Im Grunde genommen nimmt dies zwei beliebige Punkte und zeichnet eine ungebrochene Linie zwischen ihnen. Wenn Sie einen Vektor vom Spieler auf die maximale Reichweite werfen, können Sie diese verwenden und die Positionen der Spieler als Punkte.

Ich habe hier eine 3D-Implementierung in Python: bresenham3d.py .

Lachs
quelle
6
Bei einem Bresenham-Algorithmus fehlen jedoch einige Blöcke. Es wird nicht jeder Block berücksichtigt, den der Strahl durchläuft. es werden einige übersprungen, bei denen der Strahl nicht nahe genug an der Blockmitte ankommt. Sie können dies deutlich aus dem Diagramm auf Wikipedia sehen . Der Block 3. runter und 3. rechts von der oberen linken Ecke ist ein Beispiel: Die Linie verläuft (kaum) durch den Block, aber Bresenhams Algorithmus trifft ihn nicht.
Nathan Reed
0

Um den ersten Block vor der Kamera zu finden, erstellen Sie eine for-Schleife, die von 0 bis zu einem gewissen maximalen Abstand eine Schleife bildet. Multiplizieren Sie dann den Vorwärtsvektor der Kamera mit dem Zähler und prüfen Sie, ob der Block an dieser Position fest ist. Wenn dies der Fall ist, speichern Sie die Position des Blocks für die spätere Verwendung und beenden Sie die Schleife.

Wenn Sie auch Blöcke platzieren möchten, ist das Face-Picking nicht schwieriger. Gehen Sie einfach vom Block zurück und suchen Sie den ersten leeren Block.

ohne Titel
quelle
Das würde nicht funktionieren, mit einem abgewinkelten Vorwärtsvektor wäre es sehr gut möglich, einen Punkt vor einem Teil eines Blocks zu haben und den nachfolgenden Punkt danach, wenn der Block fehlt. Die einzige Lösung wäre, das Inkrement zu verkleinern, aber es müsste so klein sein, dass andere Algorithmen weitaus effektiver sind.
Phil
Das funktioniert ziemlich gut mit meinem Motor; Ich benutze ein Intervall von 0,1.
Ohne Titel
Wie @Phil hervorhob, würde der Algorithmus Blöcke übersehen, in denen nur eine kleine Kante zu sehen ist. Darüber hinaus würde das Zurückschleifen zum Platzieren von Blöcken nicht funktionieren. Wir müssten uns ebenfalls vorwärts drehen und das Ergebnis um eins verringern.
Danijar
0

Ich habe mit meiner Implementierung , die den Bresenhamschen Linienalgorithmus verwendet, einen Beitrag zu Reddit verfasst . Hier ist ein Beispiel, wie Sie es verwenden würden:

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

Hier ist die Implementierung selbst:

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
quelle
1
Wie jemand in den Kommentaren bemerkt hat, ist Ihr Code undokumentiert. Der Code ist zwar hilfreich, beantwortet die Frage jedoch nicht ganz.
Anko