Voxel Block Picking



  • Hallo,
    ich versuche jetzt schon seit einer Woche verzweifelt einen Algorithmus zu programmieren um herauszufinden welche Zellen eines 3D Gitters von einer 3D Linie geschnitten werden.
    Das ganze brauche ich um in einem Minecraft ähnlichem Spiel herauszufinden welchen Block der Spieler ansieht.
    Zur Vereinfachung ignoriere ich erst mal Chunks und verschiedene Block Typen und gehe von einem großen statischen 3D Array was bools hält (TRUE = BLOCK, FALSE = LUFT) aus.
    Ich hatte schon so was wie das hier gefunden.
    http://playtechs.blogspot.co.uk/2007/03/raytracing-on-grid.html
    Jedoch weiß ich nicht so recht wie ich das auf die 3 Dimensionen anwenden soll.
    Aber vom Prinzip her ist das schon genau das, was ich suche.
    Wenn jemand weiß wie es geht wäre ich ihm sehr dankbar, wenn er es mir erklären kann.

    Grüße Max



  • Eine kurze Suche im Netz hat einige Implementierungen von 3D-Erweiterungen des Bresenham-Algoritmus ausgespuckt, z.B. diese hier:

    ftp://ftp.isc.org/pub/usenet/comp.sources.unix/volume26/line3d

    Eine alternative, aber artverwandte Methode wird z.B. hier diskutiert:

    http://www.ai.univ-paris8.fr/~jj/Rech/SI/eg98.pdf

    Ansonsten ist es sicher nicht verkehrt, sich mal genauer mit dem Bresenham-Algorithmus - einem echten Klassiker der Computergrafik - auseinanderzusetzen (bzw. mit DDA-Methoden im allgemeinen), und zu versuchen zu verstehen wie und warum dieser funktioniert. Dann sollte die Erweiterung auf 3D nicht allzu schwer sein - falls du Motivation verspürst etwas zu lernen und nicht nur möglichst schnell dein Problem lösen willst 😃

    Finnegan



  • Eine andere Moeglichkeit ist es eine simple line/aabb Abfrage zu nehmen und das ganze hierachisch anzugehen. D.h. du hast erst eine Bounding Box um alle deine Bloecke und schaust ob die Sichtlinie diese schneidet. Wenn ja, teilst du die Bounding Box in 8 Unterwuerfel, und wiederholst bis du beim gesuchten Block ankommst. Das schoene daran ist, man kann es ziemlich gut erweitern auf beliebige Objekte, falls du z.b. mal nicht nur Bloecke sondern auch Gegner anklicken moechtest.


Log in to reply