Gehe eine Linie zwischen zwei Punkten in einem 3D-Voxel-Raum und besuche alle Zellen.

Question

Ich habe ein Sichtlinienproblem, das ich lösen muss, indem ich alle möglichen Zellen in einem 3D-Voxelraum zwischen zwei (nicht Gitter-ausgerichteten) Punkten besuche .

Ich habe überlegt, einen 3D-Bresenham-Algorithmus zu verwenden, aber es wird einige Zellen auslassen.

Eine naive Implementierung könnte darin bestehen, Punkte entlang der Linie mit einer höheren Auflösung als das Voxelraster zu überprüfen, aber ich habe auf eine intelligentere Lösung gehofft.

Wer hat irgendwelche Leads?

Answer 1

kam auf diese sehen, oder: http://jsfiddle.net/wivlaro/mkaWf/6/

function visitAll(gx0, gy0, gz0, gx1, gy1, gz1, visitor) { 

    var gx0idx = Math.floor(gx0); 
    var gy0idx = Math.floor(gy0); 
    var gz0idx = Math.floor(gz0); 

    var gx1idx = Math.floor(gx1); 
    var gy1idx = Math.floor(gy1); 
    var gz1idx = Math.floor(gz1); 

    var sx = gx1idx > gx0idx ? 1 : gx1idx < gx0idx ? -1 : 0; 
    var sy = gy1idx > gy0idx ? 1 : gy1idx < gy0idx ? -1 : 0; 
    var sz = gz1idx > gz0idx ? 1 : gz1idx < gz0idx ? -1 : 0; 

    var gx = gx0idx; 
    var gy = gy0idx; 
    var gz = gz0idx; 

    //Planes for each axis that we will next cross 
    var gxp = gx0idx + (gx1idx > gx0idx ? 1 : 0); 
    var gyp = gy0idx + (gy1idx > gy0idx ? 1 : 0); 
    var gzp = gz0idx + (gz1idx > gz0idx ? 1 : 0); 

    //Only used for multiplying up the error margins 
    var vx = gx1 === gx0 ? 1 : gx1 - gx0; 
    var vy = gy1 === gy0 ? 1 : gy1 - gy0; 
    var vz = gz1 === gz0 ? 1 : gz1 - gz0; 

    //Error is normalized to vx * vy * vz so we only have to multiply up 
    var vxvy = vx * vy; 
    var vxvz = vx * vz; 
    var vyvz = vy * vz; 

    //Error from the next plane accumulators, scaled up by vx*vy*vz 
    // gx0 + vx * rx === gxp 
    // vx * rx === gxp - gx0 
    // rx === (gxp - gx0)/vx 
    var errx = (gxp - gx0) * vyvz; 
    var erry = (gyp - gy0) * vxvz; 
    var errz = (gzp - gz0) * vxvy; 

    var derrx = sx * vyvz; 
    var derry = sy * vxvz; 
    var derrz = sz * vxvy; 

    do { 
     visitor(gx, gy, gz); 

     if (gx === gx1idx && gy === gy1idx && gz === gz1idx) break; 

     //Which plane do we cross first? 
     var xr = Math.abs(errx); 
     var yr = Math.abs(erry); 
     var zr = Math.abs(errz); 

     if (sx !== 0 && (sy === 0 || xr < yr) && (sz === 0 || xr < zr)) { 
      gx += sx; 
      errx += derrx; 
     } 
     else if (sy !== 0 && (sz === 0 || yr < zr)) { 
      gy += sy; 
      erry += derry; 
     } 
     else if (sz !== 0) { 
      gz += sz; 
      errz += derrz; 
     } 

    } while (true); 
} 

Answer 2

Ich denke, 3d Bresenham ist der Weg zu gehen, nur ein bisschen zwickte. Gehen Sie als erster Durchlauf des Problems wie Bresenham vor, aber seien Sie misstrauisch, wenn Sie vorhaben, einen Schritt zu tun, oder Sie haben nur einen Schritt getan, da dies die Stellen sind, an denen die Leitung zusätzliche Zellen passieren kann.

Nehmen wir zur Vereinfachung an, dass z dominant ist, was bedeutet, dass z jeden Schritt erhöht. Die 3d Bresenham Frage ist: "Wann erhöhen/dekrementieren wir in x oder y?" Die Antwort ist, wenn der akkumulierte Fehler in x .5 erreicht, oder wenn der Fehler in y oder beides tut.

Für Ihren Fall, ich denke, Sie müssen eine sekundäre Schwelle haben, die slopeY = deltaY/deltaZ verwendet, um zu entscheiden, ob die Linie in eine benachbarte Zelle zu überqueren ist. Wenn stepZ die Änderung von z entlang der Linie für jedes Pixel ist, sollte ein Test wie error > .5 - slopeY/stepZ Ihnen sagen, Zellen auf beiden Seiten der Linie in y zu erhalten. Ein ähnlicher Test sagt Ihnen, ob Sie die zusätzliche Zelle in x erhalten müssen. Wenn Sie die zusätzliche Zelle sowohl in x als auch in y erhalten müssen, müssen Sie auch die Zelldiagonale zur Bresenham-Zelle bringen.

Wenn Sie festgestellt haben, dass Sie vor dem Inkrement eine Zelle in y hinzugefügt haben, fügen Sie keine Zelle nach. Wenn Sie noch keine y Zelle hinzugefügt haben, müssen Sie nachher, es sei denn, Sie passierten zufällig eine Zellenecke. Wie Sie damit umgehen, hängt von Ihrem Anwendungsfall ab.

Dies sind meine Gedanken zu dem Thema, ich habe nichts getestet, aber etwas wie es sollte funktionieren.

Answer 3

Soweit ich mich erinnere, dass der ursprüngliche Bresenham-Algorithmus annimmt, dass die Bewegung entlang der Diagonalen erlaubt ist, ist es in Ihrem Fall sinnvoll, sie zu verbieten.

Aber die Grundidee ist die gleiche - für jedes Voxel die Frage "was kommt als nächstes?"

Jedes Voxel hat 6 Gesichter, die jeweils zu einem anderen Nachbarn führen. Überprüfen Sie einfach das Zentrum, dessen Voxel näher an der Linie liegt als andere. Das ist das nächste Voxel.

Anmerkung: Dies setzt voraus, dass Voxel die gleiche Größe entlang jeder Achse aufweist, wenn das nicht der Fall ist, sollte man modifizierte Abstand berechnen (jede Komponente durch Voxelgrße entlang entsprechenden Achsen verteilt werden sollten)

Answer 4

Hier ist eine öffentliche Verbindung zu einem aktuellen Port meines Voxel ray von C++ in javascript:

https://github.com/jeremykentbgross/EmpathicCivGameEngine/blob/master/engine/public/scripts/Ray2D.js

Hinweis: Der Port befindet sich derzeit in 2D auf einem Quadtree (anstelle von 3D in einem Oktbaum), aber nur, weil eine Dimension für meine 2D-JavaScript-Engine auskommentiert ist. Es funktioniert gut in meiner 3D-C++ - Engine (wo ich es portierte), also wenn Sie die Z-Achsen-Zeilen auskommentieren, wird es funktionieren. Die Datei enthält auch viele Inline-Kommentare zur Funktionsweise der Mathematik.

Sie sollten auch auf den RayTracer2D.js (im selben Verzeichnis) verweisen, der den Strahl verwendet, um alle geschnittenen Objekte und ihre Schnittpunkte in der Reihenfolge zu finden, in der sie getroffen wurden.

Als Referenz der Quad Baumstruktur es durch ist Tracing ist auch im selben Ordner: QuadTree.js

Beachten Sie, dass Sie könnte auch Raytraceergebnis unteren LOD einfach ist durch eine Begrenzung, wie tief man in den Baum während der Ablaufverfolgung durchqueren .

Hoffe, dass hilft.