Frage von Florian366, 8

2 Quader in einem 3 dimensionalen Raum ausrechnen. Wie berechne ich ob sie sich berühren?

Ich habe 2 Quader in einem 3 Dimensinalen Raum. Sie haben immer unterschiedliche Positionen, Größen und Rotationen (in alle 3 Richtungen). Ich weiß die Positionen(px, py, pz), Größe(s) und Rotation(rx, ry, rz). Wie kann ich ausrechnen ob sie sich berühren (ohne Skizzen)?

Antwort
von girlyglitzer, 7

Hallo!

Wo bekommst du denn so komische Aufgaben? Ich nehme einmal an, dass du schon studierst?

Ich würde folgendermaßen vorgehen: Stelle die Quader in Parameterform auf, das heißt zum Beispiel für einen Quader Q, dass du ihn in der folgenden Form (sozusagen als Punktmenge) vorliegen hast: Q = {S + q*v1 + r*v2 + s*v3 | 0 <= q, r, s <= 1}, wobei S eine beliebige Ecke des Quaders ist und v1, v2, und v3 die jeweiligen Verbindungsvektoren zu den drei nächstgelegen Ecken.

Seien also Q1 = {S1 + q*v1 + r*v2 + s*v3 | 0 <= q, r, s <= 1} und Q2 = {S2 + a*w1 +b*w2 + c*w3 | 0 <= a, b, c <= 1} zwei Quader.


Dann kannst du die Q1 und Q2 schneiden, indem du die beiden definierenden Gleichungen gleichsetzt: S1 + q*v1 + r*v2 + s*v3 = S2 + a*w1 +b*w2 + c*w3. Das ist quasi ein lineares Gleichungssystem von sechs Unbekannten in drei Gleichungen. (Am besten mit Gauß-Jordan-Eliminationsverfahren über Matrizen lösen, wenn du es händisch machen musst...) An den Stellen, an denen du passende Werte für 0 <= q,r,s,a,b,c <= 1 rausbekommst, schneiden sie sich offenbar und dort, wo das nicht der Fall ist, logischerweise nicht :D

LG girlyglitzer






Kommentar von Florian366 ,

Hallo! 

Danke für deine Antwort. 

Ich beschäftige mich in letzer Zeit ein bisschen mit Softwareentwicklung und studiere noch nicht, weshalb ich nicht alles genau verstanden habe. Du musst nicht alles genau erklären, aber es würde mir helfen, wenn du ein Beispiel mit ein irgentwelchen Werten schreiben würdest.

LG Florian

Kommentar von girlyglitzer ,

Hallo!

Ok, das ändert die Situation völlig. Den Lösungsweg, den ich dir hier beschrieben habe, liefert eine exakte und analytische Lösung der Schnittkörper. In der Softwareentwicklung (wahrscheinlich Spieleentwicklung?) ist es wahrscheinlich weniger relevant, wo sich die Quader schneiden, als vielmehr ob sie sich überhaupt schneiden (Kollisionserkennung?).

Kurz gesagt, das Verfahren ist für dich wahrscheinlich gar nicht sinnvoll, weil die Berechnung zu aufwendig ist und zu viel Rechenleistung in Anspruch nimmt.

Ich habe ein wenig im Internet recherchiert und bin auf folgende Seite gestoßen, von der du dir sicher ein paar Anstöße holen kannst: http://matheplanet.com/default3.html?call=article.php?sid=322&ref=https%3A%2...


Was mir persönlich aus dem Artikel ganz nützlich erscheint, ist folgendes Zitat von "viertel":

Hallo Matroid,

wenn es nur um die Frage geht, OB sich zwei Quader schneiden (und nicht
etwa nach dem Volumen des Schnittkörpers gefragt wird), dann geht das
ganz einfach:

Teste jede der 6 Flächen des einen Quaders, ob sie von einer der 12
Kanten des Anderen durchstoßen wird (nicht in der Verlängerung, sondern
"in echt"). Sobald ein Hit gefunden ist ==> Schnitt.

Wenn kein Treffer, dann die Rollen der beiden Quader vertauschen und
alles nochmal. Wenn dann immer noch kein Durchstoßpunkt zu finden ist,
dann schneiden sich die beiden Quader nicht.

Daß das Ganze mit viel linearer Algebra und lin. Gleichungssystemen
abgeht ist klar. Als Denk- und Rechenhilfe kann man zu Beginn einer
Testserie ja so transformieren, daß eine Ecke des ersten Quaders im
Ursprung liegt und die 3 an dieser Ecke anliegenden Kanten auf den
Achsen des Koordinatensystems liegen. Dann laufen die "Durchstoßtests"
einfacher ab.

Gruß
Dietmar das 1/4


Hier ist noch eine Seite, die ganz interessant sein könnte: http://people.mpi-inf.mpg.de/~schoemer/GIBU2000/koltheo.html (Der Fall, den du brauchst, ist 2 * konvex, weil Quader konvexe Körper sind) Da ist sogar eine Quelle dabei.

Zum Schluss noch ein praxisorientierter Link: https://developer.mozilla.org/en-US/docs/Games/Techniques/3D_collision_detection Hier ist schon ein fertiger Algorithmus angegeben (in JavaScript).

Vielleicht solltest du dich aber auch an erfahrene Softwareentwickler wenden und sie fragen, welche Lösung sie zu diesem Problem empfehlen - vor allem, da es ja ein Problem ist, das in nahezu jedem Computerspiel relevant ist und sicher schon irgendwo annehmbar gelöst wurde.

LG girlyglitzer

Kommentar von Florian366 ,

Vielen Dank. 

Ich bin noch am testen, aber im Prinzip habe ich es verstanden. Ohne dich würde ich wahrscheinlich immer noch verzweifelt.

Mfg

Keine passende Antwort gefunden?

Fragen Sie die Community

Weitere Fragen mit Antworten