Java Ein wenig Ünterstützung beim "Raycasten" benötigt

[Krik]

Das geht geht auch. Das ist aber ganz schön getrickst. ^^

Du hast dann aber das Problem, dass du keinen horizontalen oder vertikalen Stripe (einfach zu berechnen) für die Regenbogenlinie verwenden kannst. Der Stripe wird geht ja in irgendeinem Winkel quer über die Textur. Da bist du ja dauernd am Neuausschneiden.


Also wie schon geschrieben, für die Wände nimmst du einen horizontalen/waagerechten Strahlenfächer. Das hast du schon. Und jetzt nimmst du einen vertikalen/senkrechten Strahlenfächer für die Decke und den Boden. Die Wände musst du damit nicht nochmal berechnen.

Wobei, wenn man schon Horizontale und Vertikale getrennt berechnet und deren Berechnung, von den Variablen mal abgesehen, identisch ist... da wäre es doch besser gleichen einen Strahl im 3D-Raum statt in einer 2D-Ebene zu werfen. Der kann dann alles (Decke, Wand, Boden). Das ist aber mit "einfacher" Mathematik etwas umfangreich. Mit Vektorrechnung geht das runder von der Hand.

 

[CPU]

Hallo e-Laurin,

ich sag' schon mal Danke für Deine Geduld mit mir!

Das geht geht auch. Das ist aber ganz schön getrickst. ^^

Du hast dann aber das Problem, dass du keinen horizontalen oder vertikalen Stripe (einfach zu berechnen) für die Regenbogenlinie verwenden kannst. Der Stripe wird geht ja in irgendeinem Winkel quer über die Textur. Da bist du ja dauernd am Neuausschneiden.

Das ist in der Tat ein Problem.

Also wie schon geschrieben, für die Wände nimmst du einen horizontalen/waagerechten Strahlenfächer. Das hast du schon. Und jetzt nimmst du einen vertikalen/senkrechten Strahlenfächer für die Decke und den Boden. Die Wände musst du damit nicht nochmal berechnen.

Okay. Beschränken wir uns mal auf den Boden (die Decke geht ja analog). Also nehme ich für jeden einzelnen der 320 horizontalen Strahlen, die die Wand abtasten, wieder eine Schar von vertikalen x Strahlen, die dann den Boden Pixel für Pixel abtasten? Aber dadurch, dass ich ja schon den horizontalen Strahl werfe, habe ich ja sozusagen schon eine Menge von Pixeln, die ich vertikal treffe, oder?

In dem Tutorial von Permadi steht ja:

* Start from the bottom of the wall slice.
1. Take the pixel.
2. Draw a line (a ray) from the pixel to the viewers eye.
3. Extends the line so that it intersect the floor.
4. The point where the line "intersect" the floor is the point on the texture map that is being hit by the ray.
5. Take the pixel value of that point on the texture map (see the next figure to see how this can be done) and draw it on the screen.
* Repeat 1-5 until the bottom of the screen is reached.

Zu (1): Welches Pixel wähle ich denn (also von wo?)? Und was hat die Projektionsfläche damit zu tun?

Gruß,
CPU

EDIT: Hier habe ich einen alten Newsgroupeintrag dazu gefunden. Dort sagt er ja, dass nachdem man die Wand gezeichnet hat müssen ja die Texturkoordinaten berechnet werden. Also muss man für den "Pixelstreifen" unter der Wand (von mir vorhin bunt visualisiert) jeden Pixel einzeln berechnen und dort hin kleben?

EDIT 2: Ich glaube ich habe ein bisschen mehr verstanden. Es wird in der Erklärung so gesehen, dass man von der Hälfte der Pseudo-3D-Ansicht los geht (ist der Horizont). Dort ist der Boden unendlich weit entfernt, da es ja im Horizont liegt. Je weiter man nach unten in y-Richtung geht auf der Pseudo-3D-Ansicht, umso kürzer wird die Entfernung von dem Betrachter zum Bodenpixel. Und ganz unten ist der Boden ganz nah. Und was geben nun "XWall" und "YWall" an?
Nun muss da aber nicht noch der Winkel mit rein irgendwo? Denn wenn ich einen krummen Winkel habe, dann muss ich doch auch so einen diagonalen Ausschnitt des Fußbodens sehen, oder?
Sonst könnte man ja nur den ersten Pixel unter der Wand berechnen und dann immer dekrementieren und modulo Texturgröße rechnen und dann wieder Textur-Streifen hin kleben ...

 

[Krik]

Also nehme ich für jeden einzelnen der 320 horizontalen Strahlen, die die Wand abtasten, wieder eine Schar von vertikalen x Strahlen, die dann den Boden Pixel für Pixel abtasten? Aber dadurch, dass ich ja schon den horizontalen Strahl werfe, habe ich ja sozusagen schon eine Menge von Pixeln, die ich vertikal treffe, oder?

Auf beide Fragen lautet die Antwort ja.
Die Menge vertikaler Pixel ist allerdings pro Strahl nur einer. Und der ist noch auf halber Höhe der Mauer. Du brauchst allerdings alle vertikalen Pixel vom Fußpunkt der Mauer bis zur Unterseite der Projektionsfläche.

Und da du gefragt hast: Die Projektionsfläche ist deine 3D-Anzeige. Alles, was man im Spiel sieht, wird darauf projiziert, deshalb der Name.

Die Anleitung ist etwas doof, er wirft laufend Pixel und Würfel durcheinander. Da muss man immer ein wenig raten, ob er jetzt einen Bildschirm-, Texturpixel oder eine Wand auf der Karte meint.
Bei Schritt 1 meint er den Pixel unterhalb der Mauer auf der Projektionsfläche, also auf der 3D-Anzeige.

Zum Edit:
Ja, du musst jeden Texturpixel extra berechnen, weil Texturstreifen sind ja zu aufwändig.
height beschreibt die Höhe der Projektionsfläche. 1/2 height ist hier der Horizont und der ist quasi unendlich weit weg. Zumindest rechnerisch. Und wenn keine Wand im Weg steht.
y dürfte die Höhe im Raum sein, also weit die Projektionsfläche vom Boden unter ihm entfernt ist. Kann sein, dass ich jetzt aber auch height und y verwechsle. Im Text wird das nicht klar.

 

[CPU]

Hey Leute,

also, ich habe jetzt folgendes gemacht: es wird geschaut, wie hoch die gefundene Wand ist und der Rest oben und unten ermittelt. Dann wird die Länge des Strahls, der die Wand getroffen hat, durch diese "Höhe" geteilt (ich teile also den Strahl in so viele Teile auf, wie viele Pixel auf der Pseudo-3D-Ansicht unterhalb der Wand noch sind). Und dann wird für die verbleibende höhe iteriert und immer einen Bruchteil von (Länge/Anzahl Pixel in der Höhe) drauf addiert. Somit erreiche ich es, dass ich mir "sozusagen" für jeden Bodenpixel unter der Wand einmal die Position auf den Feld errechne - also ein virtuelles Mapping. Dann wird wieder mit floor gearbeitet um den Offset zu bekommen (siehe auch Wandtexturen weiter oben) und das in x und y Richtung und dann mit der Texturgröße multipliziert ergibt für x und y einen Wert zwischen [0, 64]. Das ist dann das Pixel in der Textur, dass an dieser Stelle auf dem Boden ist.

Wenn ich mir dann in der 2D-Ansicht mal den Vergrößerungsfaktor auf 64 stelle (Texturgröße), dann werden auch die korrekten Pixel-Angaben zwischen [0, 64] erzeugt und wenn man auf der 2D-Karte dann diese Pixel hinkleben würde, würde auch der Boden dort komplett richtig angezeigt.

Nun, wenn ich dann diese Pixel der Reihe nach auf die Ansicht zeichne, dann kommt nur Mist raus. Sehet selbst:

Gruß,
CPU

Wer braucht schon Boden oder Decke? Zu Wolfenstein3D-Zeiten war das auch nur grau ...

Ergänzung (24. August 2012)

Um das Ganze zu vereinfachen: wie kann ich dann ein einfaches Karo-Muster auf den Boden malen (z.B. alle Fliesen mit x+y mod 2 == 0)?

Edit: Hier und hier hat sich auch jemand an der Geschichte versucht und war erfolgreicher ...

 

[Krik]

Karos sind auch nur eine Textur. Du kommst nicht drum rum, das exakte gleiche Prinzip wie beim horizontalen Strahlenfächer anzuwenden.

Warum machst du das nicht? Den Algo dafür hast du doch schon in der Tasche, du musst ihn doch nur mit anderen Variablen füttern.

 

[CPU]

Hallo e-Laurin,

nur noch eine letzte Frage: ich habe mir nochmals das Tutorial von Permadi zu "Floor-Casting" durchgelesen; für jeden der 320 Strahlen/Rays mache ich also folgendes:

1. Man iteriert über alle Pixel, die unter der Wand liegen. D.h. zwischen "Streifen.top+Streifen.height" und "screenHeight"
2. Für jeden Pixel will man nun eine Stelle auf dem Boden in der 2D-Karte finden, um den entsprechenden Pixel aus der Textur zu mappen
3. Dazu verbindet man den Pixel mit dem Betrachter und kann dann eine Aussage über die Distanz zu dem entsprechenden Punkt auf der 2D-Karte machen
4. Mit dem Winkel aus der Wandabtastung und der gerade bestimmten Distanz kann man dann auf eine Koordinatenangabe der in der 2D-Karte schließen und dann wie bei den Wänden mittels Offset die Textur bestimmen

So habe ich das verstanden und auch an mehreren Stellen jetzt so gelesen. Nun wo liegt also mein Problem?

Nun die Formel (nach dem Bild) lautet ja:

straightDistance = distanceOfPlayerToProjectionPlane * (playersHeight/currentRow-centerRow)

Die "distanceOfPlayerToProjectionPlane" ist ja in meinem Quellcode die viewDist (=(screenWidth/2)/tan(60°/2) = 277 auch bei Permadi). Die "playersHeight" keine Ahnung, aber laut Bild und meiner Anschauung müsste die so groß sein, wie die Hälfte der screenHeight (also halb so groß wie die Wände). Die "currentRow" ist entsprechende Zeile nach dem unteren Ende der Wand und "centerRow" ist screenHeight/2.

Ein kleines Beispiel. Die Daten: Winkel = 0°, 160. Streifen, Höhe des Streifens = 62 Pixel, Top-Ausrichtung = 69 Pixel, screenWidth = 320 Pixel, screenHeight = 200 Pixel.

• D.h. es müssen 69 Pixel unterhalb der Wand bestimmt werden
• Beginne also mit Pixel 132 (erstes Pixel unterhalb des Endes der Wand):
• straightDistance = 277 * (100 Pixel/(132-100)) = 277 * 3.125 = 865.625
• Also muss in einem Winkel von 0° die Textur nach einer Entfernung von 865.625 kommen
• Fahre Fort mit Pixel 133:
• ...

Nun die Entfernung bis zur Wand beträgt aber nur 4.5 Längeneinheiten. Also müsste doch ein Wert nahe 4.5 heraus kommen, oder? Und nicht 870!

Ich hoffe ich habe anschaulich erklärt, wo es noch hakt! Aber ich denke, dass ich das Prinzip verstanden habe!

Gruß,
CPU

EDIT: hier mein Code, und im Anhang noch ein Bild

		// Startzeile
		int row = str.height+str.top+1;
		
		// Solange wir noch nicht am unteren Bildrand
		while (row < screenHeight) {
			// Bestimme Entfernung nach Formel
			double d = viewDist*((100)/(row-(screenHeight/2.0)));
		
			// Mit Entfernung d und aktuellem Winkel des Rays
			// a können die Koordinaten berechnet werden
			double newx = px+Math.cos(a)*d;
			double newy = py+Math.sin(a)*d;
		
			// Pixel aus der Textur auslesen
        	str.addC(new Color(textures.getRGB(
        			(int) Math.abs(newx-Math.floor(newx) * 64) % 64, 
        			192+(int) Math.abs(newy-Math.floor(newy) * 64) % 64)));
			
        	// Weiter geht es ...
			row++;
		}

 

[Krik]

Du rechnest mit Pixelwerten, wo du eigentlich die Koordinaten der Map verwendet werden sollen.

Beginne also mit Pixel 132 (erstes Pixel unterhalb des Endes der Wand):
straightDistance = 277 * (100 Pixel/(132-100)) = 277 * 3.125 = 865.625

Du musst die 132 Pixel vorher in Kartenkoordinaten umrechnen.
Was das für andere Zahlen sind, weiß ich nicht.

Ich zitiere mich mal selber:

Im Grunde rechnest du also mit drei verschiedenen Koordinatensystemen und bildest sie vollständig aufeinander ab, wobei sich die Umrechnung zwischen einerseits dem Bildschirm und andererseits dem Block und der Textur laufend verändert.

Du hast am Anfang Punkte auf der Projektionsfläche, die du mit einer Textur füllen willst. Das bedeutet, du musst die Koordinaten der Bildschirmpixel (320x200) auf die Karte (dein Array mit den Mauern) abbilden. D. h. du wirfst für jeden Pixel einen Strahl, der dir genau sagt, wo der Texturpixel in der Karte liegen muss. Der Strahl gibt dir die Kartenkoordinaten. Dann rechnest du die Kartenkoordinaten in Texturkoordinaten um und schließlich hast du den ursprünglich gesuchten Texturpixel.

Diese Rechnung erkenne ich so nicht in der Formel und auch nicht in deinem Code.

 

[CPU]

Hallo,

Das bedeutet, du musst die Koordinaten der Bildschirmpixel (320x200) auf die Karte (dein Array mit den Mauern) abbilden. D. h. du wirfst für jeden Pixel einen Strahl, der dir genau sagt, wo der Texturpixel in der Karte liegen muss.

den Strahl habe ich ja geworfen. Aber wie übersetze ich denn jetzt genau die Werte aus den Bildschirmpixeln in die Karte?

Du musst die 132 Pixel vorher in Kartenkoordinaten umrechnen.

Wie mache ich das?

Was das für andere Zahlen sind, weiß ich nicht.

Wie ich es oben erklärt habe: screenHeight = 200, 100 ist also die Hälfte und die 277 ist die Entfernung zwischen Projektionsfläche und Betrachter.

Gruß,
CPU

 

[Krik]

die 277 ist die Entfernung zwischen Projektionsfläche und Betrachter

Das ist quatsch. Du gibst die Länge in Bildschirmpixeln an, wo eigentlich eine Länge zwischen Kartenkoordinaten gefordert ist. Du brauchst Längeneinheiten auf der Karte, keine Pixel! Und eine Längeneinheit ist so lang wie eine Mauer.

Erkennst du jetzt deinen Irrtum? Wenn ja, stellt die restliche Rechnung kein Problem mehr dar.


Ich habe ganz stark das Gefühl, dass du überhaupt keine Ahnung hast, was du da rechnest. Das ist mir schon vorher beim horizontalen Strahlenfächer aufgefallen. Dir jetzt ein paar Formel an den Kopf werfen, bringt dich nicht weiter. Du musst verstehen, was du da rechnest.
Das Ganze ist nur eine Anwendung von Winkelfunktionen und des Strahlensatzes. Ich habe keine Ahnung, warum du so etwas Grundlegendes nicht richtig anwendest.

 

[CPU]

Hallo e-Laurin,

Das ist quatsch.

Aber im Tutorial von Permadi steht das so mit den 277 (Im ersten Bild dieser Seite steht "distance of the player to the projection pane" und auf dieser Seite steht das genau diese Entfernung eben 277 ist).

Du gibst die Länge in Bildschirmpixeln an, wo eigentlich eine Länge zwischen Kartenkoordinaten gefordert ist. Du brauchst Längeneinheiten auf der Karte, keine Pixel! Und eine Längeneinheit ist so lang wie eine Mauer.

Könntest Du mir zu den folgenden Beispielzahlen denn mal kurz vorrechnen, wie Du meinst, dass man rechnen soll?

Winkel = 0°, Höhe des Wandstreifens = 62 Pixel, Top-Ausrichtung = 69 Pixel, screenWidth = 320 Pixel, screenHeight = 200 Pixel.

Also, ich muss ja jetzt die vertikalen Pixel (unter der Wand) von 132 bis 200 berechnen. Angenommen ich will jetzt für den 132. (erster Pixel unter der Wand) die entsprechende Position auf der Karte finden. Was mache ich?

Ich habe ganz stark das Gefühl, dass du überhaupt keine Ahnung hast, was du da rechnest. Das ist mir schon vorher beim horizontalen Strahlenfächer aufgefallen. Dir jetzt ein paar Formel an den Kopf werfen, bringt dich nicht weiter.

Also die horizontale Wanderkennung habe ich anfangs nicht verstanden, doch jetzt habe ich sie wirklich verstanden. Und ich meine auch verstanden zu haben nach welchem Prinzip die Abtastung von Boden & Decke funktioniert.

Gruß,
CPU

 

[Krik]

Komisches Tutorial. Der rechnet tatsächlich in Pixeln. Damit spannt er die Ebene der Projektion in einen Raum auf. Und den Raum soll man dann mit der Ebene der Welt (= Karte) verrechnen? "Zu Fuß" ist das schwer.

Es sind auch viele andere Dinge komisch. Da wird ein Strahl in den Raum geschossen und dann noch extra zwischen Horizontale und Vertikale unterschieden? Wozu? Für einen Strahl im Raum ist das völlig egal. Der hat seinen Ausgangspunkt, seine Richtung und ab geht die Post.

Könntest Du mir zu den folgenden Beispielzahlen denn mal kurz vorrechnen, wie Du meinst, dass man rechnen soll?

Winkel = 0°, Höhe des Wandstreifens = 62 Pixel, Top-Ausrichtung = 69 Pixel, screenWidth = 320 Pixel, screenHeight = 200 Pixel.

Was die Top-Ausrichtung ist, weiß ich nicht.
Da fehlen aber noch mehr Werte, zB vertikaler FOV, Abstand zwischen Kamera und Projektionsfläche.

Vorrechnen kann ich das jetzt aber nicht. Die Rechnungen habe ich schon so lange nicht mehr angefasst, dass ich die Hälfte der Formeln vergessen habe. Da brauche ich ein paar Tage, um wieder reinzukommen. Und dann würde ich auch gleich auf Vektorrechnung gehen, da die mMn einfacher zu handhaben ist, als das "zu Fuß" rechnen. Und da gehen Dinge wie Ebenen im Raum viel einfacher zu berechnen.

Was mache ich?

Die Sache am besten ein paar Tage ruhen lassen. Danach überblickt man es besser.
Du erkennst im Moment zB nicht, dass für Böden und Decken die gleichen Formeln wie bei den Wänden gelten. Man muss sich nur vorstellen, dass Boden und Decke Wände sind. Und wie man Wände erkennt, hast du ja schon raus.
Das sage ich schon seit zig Posts.

Wenn du dich dann wieder an die Sache machst, dann bau dir diese vier Methoden:
Texturkoordinaten2Weltkoordinaten
Weltkoordinaten2Projektionskoordinaten (= Ray werfen und auswerten)
und umgekehrt.
Diese Probleme stellen mMn im Moment dein größtes Problem dar, vor allem, weil du das alles in einem Rutsch in einer Formel machen willst. Wenn du das zerlegst, wird es einfacher.

 

[CPU]

Hallo e-Laurin,

erst nochmals: super vielen Dank für Deine Unterstützung!

Was die Top-Ausrichtung ist, weiß ich nicht.

Na wie viele Pixel die Wand eben auf der Pseudo-3D-Ansicht von oben eben gezeichnet wird (einfach (Bildschirmhöhe-Wandhöhe)/2).

Da fehlen aber noch mehr Werte, zB vertikaler FOV, Abstand zwischen Kamera und Projektionsfläche.

Das vertikale FOV wird 60° betragen und Abstand Kamera <-> Projektionsfläche eben 277 (habe ich auch schon bei der Wand verwendet.

Die Sache am besten ein paar Tage ruhen lassen.

Das werde (muss) ich sogar machen.

Du erkennst im Moment zB nicht, dass für Böden und Decken die gleichen Formeln wie bei den Wänden gelten. Man muss sich nur vorstellen, dass Boden und Decke Wände sind.

Okay. D.h. im Groben kann ich eigentlich die Wanderkennungsmethode nehmen, kopieren "drehen" und dann sind ehem. Wände Boden und ehem. Boden Wände. Die werden dann erkannt und fertig. Aber: wie drehe ich denn jetzt die 2D-Karte entsprechend um?

Texturkoordinaten2Weltkoordinaten

Aber die Texturkoordinaten wiederholen sich ja immer von 0-64. Z.B. hätte ja 8.5 die Texturkoordinate 32 (50% im 8. Feld, das eine 64 Pixel breite Textur hat). Rückwärts ginge das ja nicht.

Gibt es nich einen Weg, um das Ganze noch zu vereinfachen? Also, wie hier. Dort wird ja der Boden nur mit der Blickrichtung gedreht und dann so transformiert und einfach unten hin gezeichnet. Ich weiß, dass wir mal in der Schule solche Transformationen besprochen haben. Könntest Du (oder jemand anders) mir kurz ein Stichwort nenne, wo ich zu diesen Transformationen kommen kann?

Vielen Dank nochmals für Alles,
CPU

 

[Krik]

Ein vertikaler FOV von 60° klingt nicht gut. Dann wäre das Verhältnis horizontaler und vertikaler FOV 60° zu 60° bzw. 1:1. Das Seitenverhältnis der Projektionsfläche ist 320 zu 200 bzw. 16:10. Das wird mindestens eine Stauchung des Bildes ergeben, vielleicht auch andere unerwünschte optische Effekte.
Ein vertikaler FOV von 40°, um das Seitenverhältnis zu wahren, wäre besser.

wie drehe ich denn jetzt die 2D-Karte entsprechend um?

Das kannst und musst du on-the-fly generieren. Schau mal in das Bild im Anhang.

Angenommen ein Strahl aus deinem horizontalen Strahlenfächer trifft auf eine Wand. Am Kollisionspunkt denken wir uns, dass der Strahl senkrecht auf eine gedachte Wand fällt. (Bild links oben).

Aus der Sicht des Strahls ist es am Kollisionspunkt egal, welchen Winkel die Wand hat. Da du bei der Wand keinerlei Perspektive beachtest, kann man eine senkrechte Achse am Kollisionspunkt aufstellen. Jeder Punkt dieser Achse hat dieselbe Distanz zur Kamera wie der Strahl zur Kamera. Würdest du die Perspektive beachten, dann gäbe es diese Achse so nicht. (Bild rechts oben)

Mit diesem Wissen konstruiert man sich eine neue (kleine) Karte. Die Karte besteht nur aus einem Gang, wobei die linke Wand die Bodentexturen trägt und die rechte Wand die Deckentexturen. Das Ende des Gangs bildet die gedachte Mauer. Die gedachte Mauer ist exakt so weit von der Kamera entfernt wie im Bild links oben. (Bild links unten)

Tja, und nun musst du nur noch auf diesen Gang deinen horizontalen Stahlenfächer anwenden. (Bild rechts unten)

Fertig.


Zu deinem verlinkten Beispiel:
Ich weiß nicht, was sie da für eine Berechnung verwenden. Das kann echtes Raytracing sein, oder deine Variante mit der Unterscheidung zwischen horizontal und vertikal.

 

[CPU]

Hey e-Laurin,

Danke für die Erklärung und die Zeichnung. Ich werde es jetzt mal ein bisschen ruhen lassen und später fortfahren.

Aber Danke bis hier her!

Gruß,
CPU