Kollision Gerade und Fläche

[Matthias Reitinger]

Hallo
ich versuche mich gerade an einem einfachen RayTracer zu bauen der mit einfachen geometrischen Körpern funktioniert. Und beim einfachstem Objekt , dem Quader bzw Würfel, scheiterts schon.

Ein Quader ist nicht gerade das einfachste Objekt. Probier es erst mal mit Ebenen und Kugeln. Das reicht zum anfänglichen Herumexperimentieren auf jeden Fall.

Beim Raytracer verfolgt man ja einen gedachten "Blickstrahl" in die 3D-Scene hinein und behandelt jene Objekte auf die der Strahl trifft. Nun besteht der Körper ja aus 6 Flächen. Mittels Vektorrechnung kann man zwar den Schnittpunkt zwischen Strahl und Ebene berechen, der kann aber außerhalb der Fläche liegen.

Nun zur Frage:
Wie kann ich jetzt berechnen ob der Strahl mit der Fläche kollidiert, um im zweiten Schritt den Schnittpunktberechnung mittels Vektorrechnung zu bestimmen?

Einfachste Möglichkeit, die mir gerade einfällt: das Rechteck in zwei Dreiecke unterteilen und überprüfen, ob der Schnittpunkt mit der Stützebene in mindestens einem Dreieck liegt (z.B. über baryzentrische Koordinaten).

Für achsenorientierte Quader gibt es aber noch wesentlich effizientere Algorithmen. Du kannst aber jeden Quader durch eine einfache Drehung an den Achsen ausrichten, also sind solche Algorithmen auch allgemein anwendbar.

Grüße,
Matthias

 

[colblake]

Danke für eure Hilfe.
Werd sie mir mal zu Gemühte ziehn. Ich geb bescheid wenns soweit ist

Danke & Gruß
Col.Blake

PS: Es kommen sicherlich noch weitere Fragen.

 

[Vereth]

Du kannst das ganze Problem mit Hilfe der Vektorrechnung behandeln. Dabei bekommst du ein lineares Gleichungssystem, das mit dem Gaußalgorithmus berechnet werden kann. Du bekommst dann entweder eine eindeutige Lösung, den Schnittpunkt, oder das Gleichungssystem ist nicht lösbar, Gerade und Ebene sind dann parallel zueinander. An den erhaltenen Parametern kannst du dann erkennen, ob der Punkt innerhalb deines Rechtecks liegt, und ob das Rechteck auch wirklich vor dir liegt und nicht hinter dem Betrachter ist.
Dein Rechteck ist gegeben durch die Formel

R = v0 + a*v1 + b*v2

Dabei ist v0 der Vektor vom Ursprung zu der Ecke deines Rechtecks, von denen deine das Rechteck aufspannenden Vektoren ausgehen.
Deine Gerade ist gegeben durch die Gleichung

G = g0 + c*g1

Auch hier ist wieder g0 der Vektor zum Fußpunkt deiner Gerade. Die Schnittpunktsgleichung lautet dann

                          R = G
<=> v0 + a*v1 + b*v2        = g0 + c*g1
<=>      a*v1 + b*v2 - c*g1 = g0 - v0

Du hast dann drei Unbekannte und, weil du im dreidimensionalen Raum operierst, drei Gleichungen, also ist das Gleichungssystem entweder eindeutig lösbar, dann hast du die Parameter für den Schnittpunkt, oder nicht, weil die Erzeugenden nicht linear unabhängig sind; das ist genau dann der Fall, wenn G Parallel zu R ist, oder v1 und v2 in dieselbe Richtung zeigen, was bei dir (hoffentlich) nicht der Fall sein wird.
Wenn c negativ ist, liegt der Schnittpunkt hinter dem Betrachter, die Ebene ist also nicht sichtbar. Die Parameter a und b müssen beide positiv sein und dürfen die Länge der jeweiligen Rechteckkante nicht überschreiten, nur dann liegt der Schnittpunkt innerhalb deines Rechtecks.

Ich hoffe, mein Beitrag hat dir weitergeholfen, und wünsche dir noch viel Erfolg bei deinem Projekt.

 

[colblake]

So,

ich hab jetzt eine Lösung gefunden. Maßgeblicher Hinweis kam dabei von Raubkopierer.



Lösung:


a)Schnittpunkt Gerade und Ebene ermitteln:

Gegeben:
	Gerade: g: U+t*V //U und V sind vectoren
	Ebene:  e: a*x+b*y+c*z+d = 0 (Koordinatenform)


	Gerade g in Ebene e einsetzen 
		a(ux+t*vx) + b(uy+t*vy) + c(uz+t*vz) + d = 0

	und nach t umstellen
		t = (-(a*ux) -(b*uy) -(c*uz) -d)/(a*vx + b*vy + c*vz)

	jetzt noch t in die Geradengleichung g einsetzen um den Schnittpunkt zu erhalten

b)Prüfen ob der SChnittpunkt in der Fäche liegt (Das eigendliche Problem).

Gegeben:
	Vorher ermittelter Schnittpunkt: s: S 
	Ebene:  e: E1 +r*E2 +s*E3 (Parameterform) Dabei ist E1 der Ortsvektor 
		und E2 und E3 die Spannvektoren. Also je eine Seite der Fläche. Siehe Bild 1


	Der Schnittpunkt liegt genau dann in der Fläche wenn gilt 
	0 <= r <=1 und  0 <= s <= 1 

a)	Also den Schnittpunkt mit der  Ebene gleichsetzen, so erhält man 3 Gleichungen
	
	1) Sx=E1x +r*E2x +s*E3x
	2) Sy=E1y +r*E2y +s*E3y
	3) Sz=E1z +r*E2z +s*E3z

b) Eine der Gleichungen nach r umstellen, in eine andere einsetzen und nach s umstellen. Ich hab 2 nach r umgestellt und in 1 eingesetz:

	s = (Sx-E1x-((Sy-E1y-s*E2y)/E3y)*E3x)/E2x
	
	-> s = (Sx -E1x -E3x*(Sy-E1y/E3y)) / (E2x - E3x*(E2y / E3y))

c) Dann noch r ermitteln und prüfen auf:
	0 <= r <=1 und  0 <= s <= 1

Im Bild 2 seht Ihr schonmal meine ersten Renderversuche mit dem Algorithmus (Zwei Lichtquellen und 3 Flächen).

Danke & Gruß
Col.Blake

 

[Vereth]

Das Ganze ist ein bißchen komplizierter als du es darstellst. Du hast sehr viele Nenner, die du auf !=0 abfragen musst. Und wenn einer doch 0 ist, heißt das noch nicht, dass keine Lösung existiert; du musst dann erst eine Alternativformel probieren. Was tust du beispielsweise, wenn E2x*E3y==E3x*E2y ist?
Es gibt eine relativ einfache und sichere Formel, mit der man herausfinden kann, ob ein Schnittpunkt existiert.
Ich habe oben gezeigt, dass die Gleichung

a*v1 + b*v2 - c*g1 = g0 - v0

erfüllt sein muss, wenn ein Schnittpunkt vorhanden ist. Man kann das als Multiplikation einer Matrix A mit dem Vektor u schreiben, der einen Vektor d ergeben muss. Die Spaltenvektoren von A sind (von links nach rechts) die Vektoren v1, v2 und -g1. Der Vektor u besteht aus den Unbekannten, also (von oben nach unten) a, b und c. Der Ergebnis-Vektor d ist gleich g0-v0. Wir haben dann die Gleichung

A*u = d

Dies kann man auflösen, indem man die Gleichung mit der inversen Matrix A' der Matrix A multipliziert. Man hat dann

A'*A*u = A'*d

und wegen A'*A=1

u = A'*d

d ist bekannt, es muss also 'nur' noch A' berechnet und mit d multipliziert werden. A' berechnet man mit

A' = adj(A) / det(A)

wobei adj(A) die Adjunkte von A und det(a) die Determinante von A ist; die Adjunkte ist eine Matrix, die Determinante ist ein Skalar, also eine Zahl. Sowohl bei der Berechnung von adj(A) als auch bei der von det(A) werden nur Multiplikation, Addition und Subtraktion verwendet, aber keine Division. Darum existiert genau dann eine Lösung, also ein Schnittpunkt, wenn die Determinante ungleich 0 ist. Die Formel für die Determinante kann man (für eine 3*3-Matrix) mit Hilfe der Sarrusschen Regel herleiten. Sie lautet:

det(A) = v1x*g1y*v2z + v2x*v1y*g1z + g1x*v2y*v1z
       - v1x*v2y*g1z - v2x*g1y*v1z - g1x*v1y*v2z

Mit Hilfe der Adjunkten bekommt man dann die Lösungsformeln für a, b und c.

a = ((-g1z*v2y+g1y*v2z)*dx+(-g1x*v2z+v2x*g1z)*dy+(-v2x*g1y+g1x*v2y)*dz)/det(a)
b = ((-v1z*g1y+v1y*g1z)*dx+(-v1x*g1z+g1x*v1z)*dy+(-g1x*v1y+v1x*g1y)*dz)/det(a)
c = (( v2z*v1y-v2y*v1z)*dx+( v2x*v1z-v1x*v2z)*dy+( v1x*v2y-v2x*v1y)*dz)/det(a)

PS: Wer in meinen Formeln einen Fehler findet, möge sich bitte melden und seine Korrektur hier veröffentlichen.

 

[colblake]

Hallo Vereth,

Du hast natürlich recht. Da ich so viele Sachen im Nenner stehen habe kam es auch schonmal zu einer Division durch Null Exception.
Bislang hatte ich auch noch keine Lösung für diese konkreten Fälle. Ich werde mir mal Deinen Ansatz zu Gemühtre führen. Danke.


Gruß
Col.Blake