spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

Hallo Leute

Studienbedingt war oft keine Zeit zu programmieren, jetzt habe ich ein bisschen Zeit gefunden und bin wieder da

Im Moment arbeite ich an einer kleinen Voxel-engine, stecke jedoch an einem Problem fest. Und zwar laufe ich mit
dem Bresenham-Algorithmus durch die Zellen (Um alle zu erwischen mit einer Supercover-version die Jede getroffene
Zelle einschließt). Ich kann also wenn ich den Start und Zielpunkt kenne linear durch alle möglichen Zellen iterieren
(im Anhang hellblau markiert).




Allerdings möchte ich jetzt auch bestimmen können, ob eine Zelle (im Bild die rote) von meiner Strecke geschnitten
wird und zwar in O(schnell), am besten in O(1), natürlich möglichst ohne teure Operationen (das übliche halt ).

Habe schon eine Zeit lang nachgegrübelt aber irgentwie komm ich da auf keine befriedigende Lösung.

An sich schon, aber das wäre viel zu langsam. Ich kenne durch den Bresenham einige nützliche Werte,
z.b. kann ich die Abweichung des Blocks von der Ideallinie berechnen (Die Errorvariable). Gibt es
da nicht irgenteinen Trick das beschleunigend auszunutzen? ein kompletter Strahl-Box Test in 3D
kostet leider einfach zu viel

Hmm hmm

Vllt sollte ich ein bisschen mehr ausholen:




Vereinfacht gesagt schieße ich für einige Pixel auf dem Bildschirm einen Strahl in den Raum. Das geht mit dem Bresenham sehr einfach und vor allen schnell, ich verlängere den Vektor Pixelposition minus Auge (natürlich in 3D, also ein Punkt auf der vorderen Ebene des View-Frustrums) in die Ferne und erhalte so meinen Endpunkt, zu dem ich dann vom Auge aus hinlaufe. Soweit sogut. Wenn ich aber beim hinlaufen merke, dass "über" mir ein Voxel ist (hier der Rote Voxel über dem Violetten), dann möchte ich die Projizierte Position auf dem Bildschirm berechnen (fürs Verständnis reicht erstmal eine 2D-betrachtung), in dem Fall wäre das ein Strich (genau genommen suche ich das unterste Pixel dieser Linie).

Da der Bildschirm nicht notwendigerweise parallel zur Y-Achse (bei mir oben) ist, ist das ganze etwas schwieriger. Mein erster Ansatz war, den Bildschirm Stück für Stück entlangzulaufen (und dazu jeweils die neue Endposition in der Ferne zu berechnen), den Bresenham schonmal mit der entsprechenden X-koordinate zu initialisieren und dann solange nach oben zu laufen bis der Fehler wieder im Rahmen liegt. Das ist natürlich sehr langsam, daher suche ich jetzt was schnelleres