PDA

Archiv verlassen und diese Seite im Standarddesign anzeigen : Kollision mit Bezier-Kurve


ethrandil
2004-04-26, 20:42:22
Hoi,
ich möchte einen kleinen Simulator schreiben, worum es genau geht ist nicht so wichtig. Allerdings besteht die Umgebung eventuell aus Bezierkurven.

Nun muss ich testen, ob eine Gerade (bzw. die Fahrtrichtung) diese Kurve schneidet.

Wie kann ich das tun,? ich kenne mich in dieser speziellen Mathematik nicht so wirklich aus...

Über ein paar Links oder Erklärungen wäre ich sehr froh.

- Eth

Corrail
2004-04-27, 00:03:38
Hello!

Ich bin mir nicht ganz sicher, ist mal nur so eine spontane Überlegung:

Sei p(u,v) dein Polynom für das Bezier-Patch. Sei weiters g(x) eine Gerade in Parameterform und e(s,t) eine Ebene in Parameterform.

Hier müstest du die einzelnen "Nebenräume" (wie es in der linearen Algebra so schön heißt; wobei ein Bezier-Patch sicher kein Nebenraum ist, Geraden und Ebene schon, ...) einfach gleich setzen. Also

Sei
p(u,v) = u^2 * a1 + u * a2 + v^2 * a3 + v * a4 + a5
und
g(x) = x * b1 + b2

Wobei die fetten Buchstaben Vektoren sind.

So gilt:

Wenn du u,v und x finden kannst, für die gilt:

p(u,v) = g(x)

Dann hast du gezeigt, dass es einen Punkt gibt, der sowohl auf der Gerade, als auch auf dem Bezier-Patch liegt. Es kann natürlich auch sein, dass du mehrere Möglichkeiten für u,v und x findest oder gar keine Möglichkeiten. Dann bekommst du mehrere Schnittpunkte oder halt keinen Schnittpunkt. Wenn du jetzt das x in g(x) einsetzt bekommst du den Schnittpunkt herraus. Es sollte der gleiche Schnittpunkt herrauskommen, wenn du die zu dem x dazugehörigen u und v in p(u,v) einsetzt.

So, das ganze ist komplett theoretisch und ein wenig schwer zu implementieren. Ich kann dir nur folgenden Tipp geben: Ein Bezier-Patch ist IMMER innerhalb der konvexen Hülle der einzelnen Gewichtspunkte. Also eine Bounding Box um diese Punkte herum ergibt mal eine grobe Abschätzung, ob überhaupt eine Kollision auftritt.

RLZ
2004-04-27, 08:16:35
Wenns nicht 100% genau sein muss gibts noch die Möglichkeit die Kurve mit Geraden zu approximieren und mit denen die Schnittpunkte zu berechnen.
Ansonsten musst du wohl so vorgehen wie Corrail es beschrieben hat.

ethrandil
2004-04-27, 11:18:01
Zuersteinmel: Es geht nur um 2 Dimensionen...

Original geschrieben von Corrail
p(u,v) = u^2 * a1 + u * a2 + v^2 * a3 + v * a4 + a5
und
g(x) = x * b1 + b2

Ich habe also 3 Unbekannte (dazu noch 2 Quadrate), ich glaub ich bin dafür zu doof :| (d.h. meine Mathe-[LK]-Kentnisse reichen nichtmal dafür)
brauche ich im zweidimensionalen Raum immernoch p(u,v)?

-Eth

*schnell mal selber google*

Corrail
2004-04-30, 12:11:19
Sorry für die späte Antwort...
Ich hab mir das angeschaut und bin drauf gekommen, dass es für ein Bezier-Patch, das größer als 2x2 ist, bei WEITEM nicht mehr trivial zu lösen ist. Hab mir ein bissi was so überlegt und das ganze in Derive eingegeben und selbst Derive schafft es nicht u bzw. v auszudrücken.
Ich hab ein wenig im Internet gesucht und das einzige halbwegs vernünftige hab ich hier gefunden:
http://www.flipcode.com/cgi-bin/msg.cgi?showThread=00003489&forum=3dtheory&id=-1
Der Typ schreibt, dass es am besten ist zuerst einen Bounding-Volumn Text zu machen (wie ich auch schon gemeint hab) und dann das Patch tesslieren.
Bei der Möglichkeit die ich aufgeschrieben hab hast du erstens mal das Problem, dass es sicher nicht schnell sein wird. Noch dazu bezweifle ich, dass es ab einer gewissen Größe explizit zum Berechnen ist. Das heißt du müsstest sowieso Näherungsverfahren (wie z.B. Newton) anwenden und da kannst du gleich das Patch tesslieren und Triangle - Plane/Line Kollisionen machen.

Xmas
2004-04-30, 14:41:33
Original geschrieben von ethrandil
Zuersteinmel: Es geht nur um 2 Dimensionen...



Ich habe also 3 Unbekannte (dazu noch 2 Quadrate), ich glaub ich bin dafür zu doof :| (d.h. meine Mathe-[LK]-Kentnisse reichen nichtmal dafür)
brauche ich im zweidimensionalen Raum immernoch p(u,v)?

-Eth

*schnell mal selber google*
Bei 2D hast du natürlich nur noch p(u). In 2D dürfte das ganze eigentlich noch relativ einfach sein (mal für eine quadratische Kurve)

p(u) = g(µ)
u² * Ax + u * Bx + Cx = µ * Dx + Ex
u² * Ay + u * By + Cy = µ * Dy + Ey

Wenn Dy != 0, kommst du auf folgende Gleichung. Wenn Dy = 0, musst du die x- und y-Komponenten alle vertauschen (Dx und Dy können nicht beide 0 sein, dann wärs keine Gerade)

u² * Ax + u * Bx + Cx - Ex = (u² * Ay + u * By + Cy - Ey) * Dx/Dy

u² * (Ax - Ay * Dx/Dy) + u (Bx - By * Dx/Dy) + Cx - Ex - (Cy - Ey * Dx/Dy) = 0

Damit sollte man relativ schnell auf die Lösungen, falls vorhanden, kommen.

Corrail
2004-04-30, 14:54:56
Aso, so waren die 2 Dimensionen gemeint... :banghead:

Ok, falls du die quadratische Formel nicht zur Hand hast:

A*x² + B*x + C = 0

ist x = (-B +/- SQRT(B² - 4*A*C)) / (2*A)

Bei kubischen Gleichungen und Gleichungen vom Grad 4 gibt es auch eine Lösungsformel, siehe
http://www.mathematik.ch/anwendungenmath/Cardano/FormelCardano.php

Bei Gleichungen mit Grad höher als 5 muss man Näherungsverfahren wie z.B. Newton anwenden, siehe
http://de.wikipedia.org/wiki/Newton-Verfahren