# Kollision Gerade und Fläche



## colblake (29. Januar 2010)

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. 
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?

Gruß
ColBlake


----------



## FrankBooth (29. Januar 2010)

Hallo,

muß es nicht umgekeht laufen?
Du mußt den Schnittpunkt mit der Ebene berechenen und errechnen, ob er in der Fläche liegt.

Gruß


----------



## colblake (29. Januar 2010)

FrankBooth hat gesagt.:


> Hallo,
> 
> muß es nicht umgekeht laufen?
> Du mußt den Schnittpunkt mit der Ebene berechenen und errechnen, ob er in der Fläche liegt.
> ...



hallo,

das geht natürlich auch. Wichtig ist mir nur wie man berechnet ob er in der Fläche liegt.

Gruß
ColBlake


----------



## FrankBooth (29. Januar 2010)

Naja, wenn du die Geradengleichung und die Ebenengleichung (die Fläche ist auch eine Ebene) hast, setzt du sie gleich.
Die Lösungsmenge ist der Schnittpunkt. Die Ebene und der Strahl treffen sich aber immer,
es sei denn sie sind parallel. Das kann man leicht prüfen. Leider hab ich nicht mehr im Kopf
wie


----------



## colblake (29. Januar 2010)

hi FrankBooth,

Das Ermitteln des Schnittpunktes mit der Ebene ist auch nicht mein Problem. *Sondern berechnen ob er in der Fläche liegt.*

Sorry, falls ich mich missverständlich ausgedrückt haben sollte.

Gruß
ColBlake


----------



## FrankBooth (29. Januar 2010)

Ja aber das ist doch eigentlich das Gleiche. Die Fläche ist ne Ebenen.

Hast du denn die Flächengleichung oder nur die Eckpunkte oder gar nichts?


----------



## colblake (29. Januar 2010)

Ich bin mir nicht sicher ob ich Dich verstehe. Ich habe alle 4 Eckpunkte der rechteckigen Fläche. Die Fläche ist ein Teil der Ebene. 
Bitte mach mal ein Beispiel, wie Du berechen willst, dass der Schnittpunkt in der Fläche liegt.


gruß
ColBlake


----------



## Raubkopierer (29. Januar 2010)

Berechnen ob er in der Ebene geschieht über die Parametergleichung der Ebene. Die Ebene wird bekanntlich durch 2 (eigentlich 3 aber uns interessieren primär die Spannvektoren und nicht der Stützvektor) Vektoren aufgespannt. Nehmen wir also an die Fläche trägt die Bezeichnung ABCD, So nutzen wir A als Stützvektor und die Vektoren AB und ADals Stützvektoren. Nun setzen wir den Durchstechpunkt in diese Gleichung ein. Sind beide Parameter größergleich 0 und kleinergleich 1 liegt der Punkt innerhalb der Fläche, die von den Vektoren ABund ADumschlossen wird.
Wichtig ist hierbei auch die Richtung der beiden Vektoren damit sie auch die richtige Fläche umschließen.


----------



## FrankBooth (29. Januar 2010)

Also eine normale Ebenengleichung sieht so aus:

v1 + x*v2 + y*v3

v1 ist ein Vektor,
v2 ist ein Vektor,
und v3 auch.

x und y sind skalare.

Jetzt hast du 4 Punkte.
Jetzt stellst du eine Ebenengleichung mit 3 Punkten auf
so geht es:
http://www.matheboard.de/archive/376576/thread.html

    Achtung die richtigen Punkte nehmen. Nicht dem vom Aufpunkt diagonal gegenüber nehmen    

Jetzt bekommst du etwas, das in etwa so aussieht:

v1 + v2 + v3
z.B.:
(1,2,3) + x(4,5,6) + y(7,8,9)

Hier sind aber x und y = 1

also: 
(1,2,3)+(4,5,6)+(7,8,9)
Gerade = Ebene

(123) + x(1,2,3) = (1,2,3)+(4,5,6)+(7,8,9)

--->  1+ 1*x1 = 1+4+5
--> x1 = 11

--->  2+ 2*x2 = 2+5+8
--> x2 = 17/2

--->  3 + 3*x3 = 3+6+9
--> x3 = 7


Schnittpunkt (11,8,19/3)

... wenn ich mich nicht vertan habe 

Sorry war gerade etwas essen hat deshalb länger gedauert


----------



## FrankBooth (29. Januar 2010)

Achtung Fehler!!

Das was ich gemacht habe ist am Ende falsch.

(123) + x(1,2,3) = (1,2,3)+(4,5,6)+(7,8,9)

Du musste  ein x finden das für alle Gleichungen gilt.
Geht hier nicht also nicht in der Fläche!

---> 1+ 1*x1 = 1+4+5
--> x  = 11

---> 2+ 2*11 = 2+5+8
--> keine Lösung


----------



## Matthias Reitinger (29. Januar 2010)

colblake hat gesagt.:


> 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.



colblake hat gesagt.:


> 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 (1. Februar 2010)

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 (3. Februar 2010)

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 (5. Februar 2010)

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 (6. Februar 2010)

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 (8. Februar 2010)

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


----------

