matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenAlgebraische GeometrieKollision 2er Quader
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Deutsch • Englisch • Französisch • Latein • Spanisch • Russisch • Griechisch
Forum "Algebraische Geometrie" - Kollision 2er Quader
Kollision 2er Quader < Algebraische Geometrie < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Algebraische Geometrie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Kollision 2er Quader: Wann kollidieren 2 Quader
Status: (Frage) beantwortet Status 
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

        
Bezug
Kollision 2er Quader: Antwort
Status: (Antwort) fertig Status 
Datum: 18:35 Di 31.05.2016
Autor: sinnlos123

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.

Bezug
                
Bezug
Kollision 2er Quader: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 18:38 Di 31.05.2016
Autor: BennIY

Das verursacht zu viele Fehler bei länglichen gegenständen.

Bezug
        
Bezug
Kollision 2er Quader: Antwort
Status: (Antwort) fertig Status 
Datum: 21:04 Di 31.05.2016
Autor: Al-Chwarizmi


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

     []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

Bezug
        
Bezug
Kollision 2er Quader: einfache Idee
Status: (Antwort) fertig Status 
Datum: 21:17 Di 31.05.2016
Autor: 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.

Bezug
        
Bezug
Kollision 2er Quader: Antwort
Status: (Antwort) fertig Status 
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.

Bezug
                
Bezug
Kollision 2er Quader: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 16:51 Mi 01.06.2016
Autor: Al-Chwarizmi


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

Bezug
                        
Bezug
Kollision 2er Quader: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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.



Bezug
                                
Bezug
Kollision 2er Quader: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 13:16 Do 02.06.2016
Autor: Al-Chwarizmi


> 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


Bezug
                                        
Bezug
Kollision 2er Quader: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 18:45 Do 02.06.2016
Autor: sinnlos123

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.

Bezug
                                                
Bezug
Kollision 2er Quader: Antwort
Status: (Antwort) fertig Status 
Datum: 19:37 Do 02.06.2016
Autor: 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.


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.


Bezug
                                        
Bezug
Kollision 2er Quader: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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.

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Algebraische Geometrie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.matheraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]