Hi,
ich versuche im Moment einen RayTracer zu Programmieren. Als erstes würde ich einfach schauen, ob eine Halbgerade eine Kugel schneidet. Mein Problem ist, dass ich keinen Ansatz habe, wie ich anfagen muss, da wir das in der Schule noch nicht hatten. Ich denke ich würde es noch in 2 Dimensionen hinbekommen, nur mit 3 fehlt mir jeder Ansatz. Wisst ihr eine Weg mit der man Prüfen kann, ob die Kugel geschnitten wird, in den Tutorials habe ich es nicht so (oder bessergesagt garnicht) verstanden.

_________________
You even trying ...

Website: http://rise-of-light.de/

Ich bin das so angegangen:

Geradengleichung in Parameterform:
OP = OA + λ * AB
AB... Richtungsvektor der Gerade

Überprüfung ob ein Punkt auf der Oberfläche der Kugel liegt:
(OM.x - OP.x)² + (OM.y - OP.y)² + (OM - OP.z)² = r²
OM... Ortsvektor auf den Mittelpunkt der Kugel
r... Der Radius der Kugel
Die Formel ist nur etwas unpraktisch. Nach ein bisschen Grübeln bin ich auf etwas besseres gekommen:
(OM - OP)² = r²

Dann kommen folgende Schritte:
- Einsetzen
- Ausmultiplizieren
- Herausheben
- Umformen zu der Form eine quadratischen Gleichung (a*x² + b*x² + c = 0 in deinem Fall x = λ)

Für a, b und c kommen dann Folgende Gleichungen heraus:
a = AB²
b = 2 * [(OA * AB) - (OM * AB)]
c = (OA - OM)² - r²

Ich würde Vorschlagen a, b und c separat aus zu rechnen und dann die Werte in die Lösungsformel einzusetzen.
So kommst du
- keine Lösung, wenn der Term unter der Wurzel < 0 ist
- eine Lösung wenn der Term unter der Wurzel = 0 ist
- zwei Lösungen wenn der Term unter der Wurzel > 0 ist
Die Position des/der Schnittpunktes/Schnittpunkte kannst du ausrechnen indem du λ/λ1, λ2 in die Geradengleichung einsetzt.

Ich verstehs immer noch nicht wirklich, am besten wäre Code. Ich versuchs mal zu lösen, indem ich 2 Zweidimensionale Koordinatensysteme nehme einmal x,y und x,z wenn ich nun in beide den Kreis einfüge und dann schaue, dann weis ich zumindest ob man es sieht. (Achso, mit "hatten wir noch nicht in der Schule" meine ich, dass die meisten Mitschüler noch nichtmal wissen was ein Vektor ist).

_________________
You even trying ...

Website: http://rise-of-light.de/

Das im 2D könnte funktionieren.

Ich halte bei sowas nicht viel von Code (außerdem kann ich kein Delphi). Das macht die Sache nicht verständlicher. Ganz im Gegenteil.
Aber wenn du nicht sagst was du nicht verstehst, kann ich dir nicht helfen.

Ok dann sage ich jetzt was ich nicht verstehe. Ich gehe einfachmal den Text durch.


Ich verstehe auch nicht was OP oder OA heißt, ich kenne mich leider nicht so aus was Namensgebung angeht.


(OM.x - OP.x)² ... =r² : bringt es alles in eine 1 Dimensionale Ebene oder?
(OM - OP)² = r² : Das ist doch die erste Formel, nur zusammengefasst.


Die ganzen Schritte hatten wir in dem Maße noch nicht, was mich allerdings mehr interessiert, wo sind OM OP und r hin, oder hat das jetzt nichtsmehr mit den anderen Formeln zu tun?


a=AB²: AB ist doch der Richtungsvektor der Geraden, wie bekomme ich einen Richtungsvektor in eine Zahl.
Überhaupt sehe ich nicht den Bezug zu OA, wie kommst du von a*x²... zu a=AB² etc.
(Die Suchmaschine WolframAlpha kommt übrigens zum Ergebniss, dass bei
a*x² + b*x² + c = 0 die Lösung b=-a und c=0 ist)


Das zumindest glaube ich habe ich verstanden, Formel nach x umstellen, und schauen was rauskommt.

Ich hoffe ich bin kein hoffnungsloser Fall, aber wie gesagt in der Schule hatten wir das noch in keiner Weise.

_________________
You even trying ...

Website: http://rise-of-light.de/

Ok dann sage ich jetzt was ich nicht verstehe. Ich gehe einfachmal den Text durch.



OP... Ortsvektor vom Punkt P der auf deiner Geraden liegt
OA... Ortsvektor vom Anfangspunkt der Gerade



Es gibt keine "1 Dimensionale Ebene".
Angenommen wir kennen OM, OP und r.
Um prüfen zu können ob P sich auf der Kugel befindet brauchen wir jetzt den Pythagoras.
(OM.x - OP.x)² + (OM.y - OP.y)² + (OM.z - OP.z)² = Abstand²
Ist aber nicht so schön zum Rechnen wenn die Komponenten irgendwo in der Formel herumkugeln.
Wenn man aber genau hinsieht, erkennt man dass der linke Teil durch das Skalareprodukt ersetzt werden kann:
(OM - OP) * (OM - OP) = r²
oder kurz:
(OM - OP)² = r²



a*x² + b*x² + c = 0
Ist die allgemeine Form eine quadratischen Gleichung.
Die quadratische Gleichung hab ich nicht komplett hingeschrieben weil es nicht wirklich übersichtlich ist.
AB² * λ² + 2 * [(OA * AB) - (OM * AB)] * λ + (OA - OM)² - r² = 0
Die Lösungsformel für diese Gleichung ist allgemein gefasst:
x1,2 = (-b ± √(b² - 4ac)) / (2a)



AB² ist eine Zahl, AB ist der Richtungsvektor. AB² = AB * AB = AB.x² + AB.y² + AB.z²

a*x² + b*x² + c = 0
sollte eig.
a*x² + b*x + c = 0
lauten.
Und die Gleichung kann keine Lösung heben, immerhin sind da 4 Unbekannte.

a = AB²
b = 2 * [(OA * AB) - (OM * AB)]
c = (OA - OM)² - r²
Rechnest du aus und setzt es in die Lösungsformel für quadratische Gleichungen ein.

Edit: Weiß garnicht ob das gestimmt hat

Ich schaus mir nochmal an, ich habe jetzt aber einen Lösungsansatz für 2D selber gemacht, ich schreib es einfach mal hin denn ich bin mir nicht so sicher ob ich einen Fehler gemacht habe.
Als erstes braucht man ja die Definition eins Kreisringes die ist ja
r²=(Kreis.x-X)²+(Kreis.y-Y)² oder r=Wurzel((Kreis.x-X)²+(Kreis.y-Y)²)

Dann haben wir die Gerade Gerade.y=AnfangsPunkt.y+(Steigung.y/Steigung.x)*X
Jetzt formen wir nach X um
Also minus AnfangsPuntk.y und geteilt durch (Steigung.y/Steigung.x)
Dann haben wir
(Gerade.y-AnfangsPunkt.y)/(Steigung.y/Steigung.x)=X

Jetzt kommt der Teil wo ich mir nicht sicher bin:
Jetzt muss man die andere Formel nach X umstellen
Also erstmal (Kreis.x-X)² auflösen dann haben wir
r²=Kreis.x²-2*X*Kreis.x+X²+(Kreis.y-Y)²
Jetzt habe ich minus Kreis.x² und minus (Kreis.y-Y)² gerechnet
Danach sah es so aus
r²-Kreis.x²-(Kreis.y-Y)²=-2*X*Kreis.x+X²
Danach habe ich plus 2*X*Kreis.x gerechnet.
Die Formel sah dann so aus
(r²-Kreis.x²-(Kreis.y-Y)²)/(2*X*Kreis.x)=X²
Wenn man jetzt die Wurzel zieht hat man das Ergebniss für X und kann gleichsetzten, oder?

_________________
You even trying ...

Website: http://rise-of-light.de/

Nein.
Auf der linken Seite steht immer noch X.
Wie ich schon erwähnt habe muss da eine quadratische Gleichung raus kommen (tut sie ja auch bei dir), da eine Gerade mit einem Kreis bis zu 2 Schnittpunkte haben kann.
Wenn du deine Gleichung lösen willst musst du sie in genannte Form bringen. a*x² + b*x + c = 0.
Bzw. in deinem Fall praktischer Weise nur x² + p*x + q = 0.

r²-Kreis.x²-(Kreis.y-Y)²=-2*X*Kreis.x+X²
X² - X*2*Kreis.x - r² + Kreis.x² + (Kreis.y-Y)² = 0
somit wäre p = -2*Kreis.x
und q = - r² + Kreis.x² + (Kreis.y-Y)²

Dann rechnest du p und q aus (sofern die Formeln stimmen) und setzt in diese Formel ein
x1,2 = -p/2 ± √(p²/4 - q)
und bekommst die x-Werte der Schnittpunkte.
Jetzt noch die Werte in die Geradengleichung einsetzten und so bekommst du die y-Werte.

Ich würde mir an deiner Stelle einmal genau Vektoren ansehen. Die Geradengleichung ist da um einiges vorteilhafter.
Es gibt bei der Gleichung y = kx + d den Sonderfall dass k unendlich ist. Was dir bei den Vektoren nicht passieren kann.

Sehr anschaulich wird das auch in den Kollisiontutorials erläutert.

_________________
Es werde Licht.
glEnable(GL_LIGHTING);
Und es ward Licht.

Zitat aus einem Java Buch: "C makes it easy to shoot yourself in the foot; C++ makes it harder, but when you do it blows your whole leg off"

on error goto next

Danke für den Tipp, ich bin eben selber drauf gekommen. Ich mache es ein bischen anders.

Ich weis nicht ob das jetzt 100% richtig ist, (vorallem drehen habe ich noch nicht getestet). Aber zumindest erscheint eine Kugel auf dem Bildschirm. (Ersetzt man zum Schluss B/radius durch B erscheinen Muster, die man durch die Farbwerte verändern kann)

_________________
You even trying ...

Website: http://rise-of-light.de/

Ein paar Optimierungen:

-B kann nicht negativ werden, deswegen ist die if-Abfrage nicht nötig
-wenn du B mit radius*radius (speicherst du am besten vorher) vergleichst sparst du dir ein teures sqrt()

Außerdem glaube ich nicht, dass das stimmt. Es sei denn Ray.Richtung = normalize(Ray.Richtung) * |(Ray.Position - Position)|
Man sollte erst die Distanz zwischen der Kugel (M) und dem Ausgangspunkt des Strahls (R) ausrechnen. Danach rechnet man den Punkt (P) aus, der die gleiche Distanz von R hat und auf der Gerade liegt. Wenn nun |P - M| <= r ist, dann liegt es in der Kugel.

Ich hab hier nur den Code aus meinem Java-Raytracer, vielleicht hilft er ja:

Die verwendeten Klassen Sphere, Vector3f und IntersectInfo sind denke ich selbsterklärend

mfg

@Seth: Super danke, endlich Code den man vernünftig in Delphi umschreiben kann, die ganzen C++ Codes im Internet benutzen alle überladene Operatoren und das ist dann eine riesen Arbeit das ganze in Delphi zu schreiben. Ich werde mir den Code mal anschauen, diese Woche bin ich zwar weg aber dann melde ich mich nochmal.

_________________
You even trying ...

Website: http://rise-of-light.de/

p ist übrigens der Orts- und d der Richtungsvektor der Halbgeraden