Kollision 2er Quader < Algebraische Geometrie < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 18:26 Di 31.05.2016 | | Autor: | BennIY |
| Aufgabe | Gegeben:
2 Körper (Quader)
Die eckpunkte der Quader(2Stk diagonal gegenüber bei Rotation 0°
Die Rotation der Quader im "betrieb"
Gesucht:
Überlappen diese sich? JA / NEIN |
Guten Nachmittag Community,
ich programmiere ein Spiel und brauche nachhilfe in Mathe/Geometrie.
Ich muss herausfinden ob sich 2 Quader berühren und die Logik in einer Funktion implementieren. Soweit zwar kompliziert aber mit mein Kentnissen noch geradeso machbar, was mir den Rest gibt, die Körper können sich drehen. In allen 3 Achsen.
Was ich über die Objekte aussagen kann:
Jeweils 2 Punkte im Raum (xyz) diagonal gegenüber um die Quader zu definieren bei 0° auf allen Achsen und die Rotation in Grad pro Objekt.
Nun muss ich herausfinden ob sich diese überlappen.
Wie kann ich da vor gehen?
Da es sich um ein Hobbyprojekt handelt ist keine Antwort zu spät.
Beste Grüße
|
|
| |
|
Hi,
ich würde einfach aus den Quadern für die Kollisionsberechnung Kugeln mit d=größte diagonale
machen.
So können die Dinger schwingen wie sie wollen, du wirst eine Kollision berechnen können.
Nachteil: falsch positive sind offensichtlich so nicht vermeidbar.
Aber nur so als Idee von mir.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:38 Di 31.05.2016 | | Autor: | BennIY |
Das verursacht zu viele Fehler bei länglichen gegenständen.
|
|
|
| |
|
> Gegeben:
> 2 Körper (Quader)
> Die eckpunkte der Quader(2Stk diagonal gegenüber bei
> Rotation 0°
> Die Rotation der Quader im "betrieb"
>
> Gesucht:
> Überlappen diese sich? JA / NEIN
> Guten Nachmittag Community,
>
> ich programmiere ein Spiel und brauche nachhilfe in
> Mathe/Geometrie.
>
> Ich muss herausfinden ob sich 2 Quader berühren und die
> Logik in einer Funktion implementieren. Soweit zwar
> kompliziert aber mit mein Kentnissen noch geradeso machbar,
> was mir den Rest gibt, die Körper können sich drehen. In
> allen 3 Achsen.
>
> Was ich über die Objekte aussagen kann:
> Jeweils 2 Punkte im Raum (xyz) diagonal gegenüber um die
> Quader zu definieren bei 0° auf allen Achsen und die
> Rotation in Grad pro Objekt.
>
> Nun muss ich herausfinden ob sich diese überlappen.
> Wie kann ich da vor gehen?
>
> Da es sich um ein Hobbyprojekt handelt ist keine Antwort zu
> spät.
>
> Beste Grüße
Guten Abend BennIY
ich fürchte, dass diese Aufgabe (mit elementaren Mitteln)
nicht ganz leicht sein dürfte. Ich habe mal bei Wikipedia
diesen Artikel angeschaut:
![[]](/images/popup.gif) Kollisionserkennung
Für deinen Fall mit zwei Quadern scheint der sogenannte
V-Clip - Algorithmus (v-clip-algorithm) in Frage zu kommen.
Such mit dem Begriff mal weiter und entscheide dann, ob
du damit umgehen kannst.
Ein einfacher Test mit Kugeln, wie ihn sinnlos123 vorschlägt,
könnte sicher als "Vortest" benutzt werden, um den V-Clip
erst dann bemühen zu müssen, wenn sich die beiden Körper
schon recht nahe sind. So wird man viel Rechenzeit sparen
können.
LG , Al-Chwarizmi
|
|
|
| |
|
Mir fällt gerade ein theoretisch recht einfacher Test ein
und hoffe, dass meine Idee richtig ist:
Zwei Quader überlappen sich im Raum genau dann,
wenn mindestens eine Ecke des einen Quaders im Inneren
des anderen liegt (dann ist der Fall schon klar) oder aber,
wenn wenigstens eine Kante des einen Quaders einen
gemeinsamen Punkt mit wenigstens einem der sechs
begrenzenden Rechtecke des anderen hat.
Prüfe diese Vermutung zuerst auf ihre Richtigkeit.
Anschließend kann man sich überlegen, auf welche
Weise dieser Test algorithmisch realisiert werden
könnte. Ich befürchte allerdings, dass er nicht so
elegant wie der Voronoi-Test sein wird ...
LG , Al-Chw.
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 08:12 Mi 01.06.2016 | | Autor: | hippias |
In Analogie zu Al-Chwarizmis Vorschlag mein Vorschlag:
Zuerst eine Notation: Eine Ebene zerlegt den Raum in zwei Teile, welche ich Innenseite und Aussenseite nenne. Zu prüfen, ob ein Punkt in der Innen- oder Aussenseite liegt, ist sehr leicht.
Jeder Quader lässt sich als Durchschnitt von $6$ Innenseiten darstellen. Damit lässt sich auch leicht testen, ob ein Punkt in einem Quader enthalten ist, nämlich indem er in den $6$ Innenseiten liegt.
Wie bereits aufgeführt, genügt es zu testen, ob eine der $8$ Ecken des anderen Quaders im Quader liegt.
Dieses Verfahren lässt sch auf beliebige konvexe Körper verallgemeinern.
|
|
|
| |
|
> In Analogie zu Al-Chwarizmis Vorschlag mein Vorschlag:
>
> Zuerst eine Notation: Eine Ebene zerlegt den Raum in zwei
> Teile, welche ich Innenseite und Aussenseite nenne. Zu
> prüfen, ob ein Punkt in der Innen- oder Aussenseite liegt,
> ist sehr leicht.
>
> Jeder Quader lässt sich als Durchschnitt von [mm]6[/mm] Innenseiten
> darstellen. Damit lässt sich auch leicht testen, ob ein
> Punkt in einem Quader enthalten ist, nämlich indem er in
> den [mm]6[/mm] Innenseiten liegt.
>
> Wie bereits aufgeführt, genügt es zu testen, ob eine der
> [mm]8[/mm] Ecken des anderen Quaders im Quader liegt.
Hallo hippias,
leider muss ich dir mitteilen, dass ich dies nicht so ausgeführt habe.
Bei zwei Quadern im [mm] \IR^3 [/mm] , die sich überlappen, muss es nicht
sein, dass es eine Ecke des einen gibt, welche im Inneren des
anderen liegt.
Mit deinem Vorschlag behandelst du also erst den "einfachen"
Fall, den ich auch als ersten Teil meines Tests vorschlage.
Falls aber dieser Vortest ergibt, dass keine Ecke von einem der
beiden Quader im Inneren des anderen Quaders liegt, dann
ist die Kollisionsfrage noch nicht entschieden, und man muss
weiter testen, zum Beispiel mit der Idee, die ich dann als
zweiten Teil angegeben habe. Dieser Teil ist aber wohl noch
um einiges aufwendiger.
LG , Al-Chw.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 08:21 Do 02.06.2016 | | Autor: | hippias |
Du hast recht, es könnte auch eine Durchdringung vorliegen, ohne dass eine Ecke im anderen Quader liegt. Dann müsste man also auch den Schnitt der Kanten mit den Seitenflächen überpüfen, was aber auch nicht zu aufwendig ist.
Dazu würde ich die Kanten der Seitenflächen mit einer Orientierung versehen, die aussagt in welcher Richtung die Innenseite der Kante ist; ähnlich wie bei den Seitenflächen. So lässt sich recht zügig nachrechnen, ob ein Schnittpunkt einer Kante mit einer Ebene, in der eine Seitenfläche liegt, in der Seitenfläche ist oder nicht.
|
|
|
| |
|
> Du hast recht, es könnte auch eine Durchdringung
> vorliegen, ohne dass eine Ecke im anderen Quader liegt.
> Dann müsste man also auch den Schnitt der Kanten mit den
> Seitenflächen überpüfen, was aber auch nicht zu
> aufwendig ist.
> Dazu würde ich die Kanten der Seitenflächen mit einer
> Orientierung versehen, die aussagt in welcher Richtung die
> Innenseite der Kante ist; ähnlich wie bei den
> Seitenflächen. So lässt sich recht zügig nachrechnen, ob
> ein Schnittpunkt einer Kante mit einer Ebene, in der eine
> Seitenfläche liegt, in der Seitenfläche ist oder nicht.
Um den Rechenaufwand in etwa abzuschätzen, müsste man
also:
1.) jede der 12 Kantengeraden von A mit jeder der 6 Seitenflächen
von B schneiden
2.) jeden dieser (maximal 72) Schnittpunkte darauf prüfen,
ob er innerhalb der betreffenden Kante und innerhalb des
entsprechenden Seitenflächenrechtecks liegt.
3.) dann dasselbe wie in (1.) und (2.) nochmals mit vertauschten
Rollen von A und B
Man kann den Suchprozess aber sofort abbrechen, wenn
einer der so berechneten Schnittpunkte tatsächlich innerhalb
seiner Kante und innerhalb seiner Rechtecksfläche liegt.
In diesem Fall liegt nämlich eine "Kollision" bzw. Durch-
dringung der beiden Quader vor.
Einer wie ich, der noch mit Programmen auf Lochkarten
oder Kassettenrecordern und mit Apple 2 und Commodore
Rechnern und Kilobytes und Kiloflops und nicht mit
Mega- oder gar Gigaflops angefangen hat, sieht halt
dahinter doch immer noch einen immensen Rechenaufwand ...
Als Hobbyprogrammierer und auch Informatik Unterrichtender
musste ich wesentlich kleinere Brötchen backen.
LG , Al-Chwarizmi
|
|
|
| |
|
Hi Al-Chwarizmi,
rein aus Interesse,
Kann man bei deiner Methode dann auf den Kugeltest verzichten?
Letztlich möchte man doch sowas haben:
1)ist "grober test" wahr? -> bei ja gehe weiter, bei nein teste erst im nächsten frame
2)Wenn oben ja: ist "feiner test" wahr?-> bei ja, gehe weiter, bei nein teste im nächsten frame wieder auf 1)
3) exakter test (jeden nötigen Eckpunkt testen)
Meine Frage wär halt ob der Kugeltest so grob ist, dass er eig. "nichts" aussagt.
|
|
|
| |
|
> Hi Al-Chwarizmi,
>
> rein aus Interesse,
>
> Kann man bei deiner Methode dann auf den Kugeltest
> verzichten?
>
> Letztlich möchte man doch sowas haben:
>
> 1)ist "grober test" wahr? -> bei ja gehe weiter, bei nein
> teste erst im nächsten frame
> 2)Wenn oben ja: ist "feiner test" wahr?-> bei ja, gehe
> weiter, bei nein teste im nächsten frame wieder auf 1)
> 3) exakter test (jeden nötigen Eckpunkt testen)
>
> Meine Frage wär halt ob der Kugeltest so grob ist, dass er
> eig. "nichts" aussagt.
Guten Abend,
ich würde den Kugeltest unbedingt als erste Stufe beibehalten.
Der Grund dafür: er erfordert einen minimalen Rechenaufwand
und kann in einer realistischen Situation vielleicht in 99% aller
Fälle schon zum Ergebnis kommen, dass sich die Quader nicht
überlappen können, egal, wie sie im Raum genau orientiert
sind. Ein Test für zwei Quader erfordert nur eine einfache Rechnung
aufgrund der Mittelpunktspositionen und der Umkugelradien
beider Quader.
Nur in dem einen verbleibenden Prozent wäre dann der
aufwendige Test mit den Kanten und Seitenflächen noch nötig.
Falls du ein solches Programm schreibst, kannst du dann ja
selber ausprobieren, wie es sich auf die Geschwindigkeit der
Abläufe auswirkt, ob du den Kugeltest mit einbeziehst oder
nicht.
Obwohl ich die konkreten geometrischen Einzelheiten
deines Spiels, insbesondere die durchschnittlichen Größen
und Abstände der Quader überhaupt nicht kenne, würde
ich fast wetten, dass der Einbezug des Kugeltests das
Tempo mindestens um den Faktor 10 erhöhen wird.
LG , Al-Chw.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:43 Do 02.06.2016 | | Autor: | hippias |
Selbst ein Kiloflop-Rechner dürfte diese [mm] $2\cdot [/mm] 72$ Rechnungen ziemlich zügig durchgeführen.
Ich selber habe vor kurzem ein Programm geschrieben, das Kantenmodelle dreidimensional so darstellt, dass auch nur sichtbare Punkte geplottet werden. Dazu habe ich genau die von mir vorgebrachten Überlegungen angewendet, um die Körper zu beschreiben. Und obwohl zur Berechnung des Bildes sehr viel mehr als $144$ Schnittpunktberechnungen der Sichtlinien mit den Seitenflächen des Körpers notwendig sind, kann ich Körper, die komplexer als aus $2$ Quadern zusammengesetzt sind, in Echtzeit auch auf einem altem Lenovo Thinkpad T400 annehmbar flüssig rotieren lassen.
Damit will ich nicht behauptet haben, dass meine Methode besonders gut ist, sie scheint mir aber auch nicht schrecklich aufwendig, wenn sie sicher stark verbessert werden kann. Per Hand möchte ich die notwendigen Rechnungen natürlich auch nicht durchführen.
|
|
|
|
