Hallo allesamt,

für mein (wahrscheinlich niemals vollendetes) Direct3D-Spiel habe ich vor Anno-dazumal eine simple Kollisionserkennung geschrieben, es wird einfach jedes Objekt mit einer Box umgeben, und die Boxen werden auf Kollision geprüft.

Die Definition einer solchen Box liegt als ein 6-Elemente-Array aus einem Ebenen-Record vor, ein Ebenen-Rekord setzt sich zusammen aus einem Positionsvektor und einem Normalenvektor (Hessesche Normalform).

Nun wollte ich mal diese Boundingbox rendern, und frage mich plötzlich, wie ich nun eigentlich an die 8 Eckpunkte der Box komme. Ich muss ja eigentlich immer den Schnittpunkt von jeweils 3 der Box-Ebenen berechnen, also eine Funktion...



mit Leben füllen. Nur, Mathematikunterricht liegt so arg lang zurück, ich kriege irgendwie keinen Anfang... Hat irgendjemand einen Tip für mich?

Die Normalvektoren der übergebenden Ebenen sind nicht unbedingt orthogonal zueinander, aber niemals parallel.

Cu,
Udontknow


Moderiert von UGrohne: Topic aus Sonstiges (Delphi) verschoben am Mi 01.02.2006 um 18:24

Die hessische Normalform ist ja bekanntermaßen:



Wobei sich d aus einem Punkt ergibt, der auf dieser Ebene liegt (einfach durch einsetzen und ausrechnen)

Um jetzt an die 8 Eckpunkte des Würfels, der durch deine Ebenen beschrieben wird, zu kommen, stellst Du folgendes Gleichungssystem auf:



Wobei a1, b1, c1 und d1 die Werte der ersten Ebene, a2, b2, c2 und d2 die der zweiten und a3, b3, c3 und d3 die der dritten Ebene sind.

Dieses Lineare Gleichungssystem musst Du einfach (z.B. mit Gauß oder nach Kramer) lösen.

Am Ende erhältst Du für x, y und z die koordinaten des Schnittpunkts der Ebenen (oder eben kein Ergebnis, wenn es keinen eindeutigen Schnittpunkt gibt).

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

Hallo

ein Wuerfel hat 6 Ebenen die paarweise parallel sind.
Aber hat man einen Schnittpunkt sind die Verschiebungsverktoren der parallelen Ebenen(Die Differenz der Aufpunkte) gleich den aufspannenenden Vektoren des Quaders.
Damit kann man dan die anderen Punkte leicht bestimmen.

Gruss Horst

Hmmm, das wäre eine Möglichkeit, allerdings wollte ich es so halten, daß diese Box nicht unbedingt ein Würfel sein muß (also daß die Vektoren nicht unbedingt orthogonal zueinander sind).

Cu,
Udontknow

@UDontKnow: Würde bei meiner Version funzen. Allerdings ist der Rechenaufwand für 24 Determinanten nach Sachus (beim Lösen über Kramer) nicht unbedingt das schnellste.

Zu den Determinanten:

Eine Determinante einer 3x3-Matrix berechnet sich wie folgt:



Ergibt



Wobei die 4 zu berechnenden Determinanten folgende wären:



Die Lösungspunkte wären dann:



Für DM <> 0. Der Fall DM = 0 würde bedeuten, dass sich die 3 Ebenen nicht in einem Punkt schneiden.

Und diese Berechnung für alle Ebenen-Kombinationen ausführen (insgesamt also 8 Schnittpunkt-Berechnungen, die insgesamt 32 Determinanten-Lösungen und 24 Divisionen benötigen.

Insgesamt solltest Du daher auf folgende Stats kommen:
- 8 Schnittpunkt-Berechnungen
- 8 Zahlenvergleiche (Zur Überprüfung)
- 24 Divisionen
- 32 Determinanten
- 192 Multiplikationen
- je 64 Additionen und Subtrktionen

Sachus lässt sich durch Ausklammern noch etwas optimieren, was aber den Rechenaufauch nicht wirklich reduziert.

Hoffe diese Anleitung hilft erstmal. Die 8 Gruppen zu untersuchender Ebenen solltest Du glaube selber rausfinden können *g*

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

Hallo,

meine Aussage war zu ungenau, es muss sich kein >Wuerfel< ergeben .Es ergibt sich ein Spat (hoffe ich), also die gegenueberliegenden Seiten sind parallelverschobene Paralellogramme.
Das ist doch allgemein genug.
Der Punkt der diagonal dem Schnittpunkt gegenueberliegt ist Schnittpunkt + die drei Abstandsvektoren der parallelen Ebenen.

Grus Horst.
P.S.:
Wieder anders.
Der Schnitt der drei Ebenen erzeugt einen Schnittpunkt und drei Geraden.
Die Richtungsvektoren dieser Geraden ist dann auch der Richtungsvektoren der Kanten des Spates.
Jetzt richtig ?

Danke euch beiden, ich muss mir das mal in Ruhe am Wochenende ankucken.

@Horst_H: Also eigentlich kann diese Box jede beliebige Form annehmen, es müssen nicht unbedingt irgendwo rechte Winkel oder parallele Ebenen auftauchen... Vielleicht verstehe ich dich auch nur nicht richtig, muß mich wieder in Mathe einarbeiten.

Danke erstmal.

Cu,
Udontknow

Wenn du das Gauß-System löst, kann es sein, dass du keine Lösung erhälts (Ebenen parallel zueiander) oder du erhältst Unendlich als Lösung (Ebenen schneiden sich). Es gibt bei Ebenen keinen Schnittpunkt, sondern nur Schnittgeraden (unendlich viele Schnittpunkte) Wenn sich die beiden Ebenen schneiden erhältst du als Lösung deines Gauß-Systems eine Geradengleichung.

Hallo!

Ich kombiniere immer nur drei Ebenenen miteinander, von der keine parallel zu einer anderen ist, also müsste es immer ein Punkt sein, oder?

Edit: Nein, stimmt nicht.

Cu,
Udontknow

Jup, korrekt.

Sors und Horst gehen von Spaten aus. Siehe oben meinen Ansatz, der ist auf deine Anwendung aufgebaut...

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

Hmmm, gut, es wird bei mir nicht auftauchen, aber theoretisch gesehen müssen sich drei beliebige Ebenen nicht an einem Punkt schneiden. Man stelle sich drei Ebenen vor, die auf X,Y-Projektion z.B. durch ihre Schnittpunkte (also Schnittgeraden im Raum) ein Dreieck bilden... Doof beschrieben, vielleicht versteht´s ja doch einer...

Cu,
Udontknow

Hallo,

Du meinst in deinem Beispiel,dass die drei Ebenen ein unendlichlanges Prisma (hier Dreikant) begrenzen.
Dann haben die jeweiligen Schnittgeraden der Ebenen den gleichen Richtungsvektor a*V (a aus R).
Aber dann hast Du auch keinen Schnittpunk der dei Ebenen.
Hast Du so etwas schon gerechnet?

Gruss Horst

Du meinst also, du verwendest keine unendlich großen Ebenen, sondern praktisch dreieckige "Ebenenausschnitte"?

Oder meinst du folgendes: Die Ebenen schneiden sich gegenseitig in einer Schnittgerade und schließen dadurch im Querschnitt eine Dreiecksfläche ein. Und die Eckpunkte dieser Dreiecksfläche meinst du mit Schnittpunkte?

Seien die 3 Ebenen gegeben durch Aufhängepunkte p1, p2, p3 und Normalen n1, n2, n3.
Definiere M die Matrix mit den Spalten (oder Zeilen, ist egal) n1, n2, n3 und d deren Determinante d = det(M).

Ist d = 0, dann existiert kein eindeutiger Schnittpunkt, weil die Normalen nicht den gesamten Raum aufspannen ("Dreikant", parallele Ebenen).

Ist d <> 0, dann ist der eindeutige Schnittpunkt p gegeben durch:

p = (dot(p1,n1)*cross(n2,n3)-dot(p2,n2)*cross(n1,n3)+dot(p3,n3)*cross(n1,n2))/d
wobei dot() das Skalarprodukt und cross() das Kreuzprodukt ist.

Entspricht mathematisch der Methode von BenBE. Der Rechenaufwand ist so aber wahrscheinlich kleiner, da die Terme wegen der passenden geometrischen Interpretation bereits auf eine geschickte Weise zusammengefasst sind.