#1 22.08.2007 12:27:44

Chris
ExtremeMember
Ort: Erlangen, Bay
Registriert: 24.01.2005
Beiträge: 694
Web-Seite

Abstand OBB <--> OBB

Hallo,

schon wieder ich.
(Ich hab eigentlich gar keine Fragen, will nur GodLike-Status haben lol cool )

Aber jetzt zum Problem:

Ich hab zwei OBBs. Definiert durch Mittelpunkt. 3 Achsen des Lokalen Koordinatensystems und Höhe,Breite,Länge. Wenn ich jetzt deren Abstand berechen will (auch negativ wenn sie ineinander stecken) dann schaff ich das irgendwie nicht wirklich...
Also ich kann den Abstand einer OBB zu einem Punkt berechnen. Das ist kein Problem. Aber den Abstand zu einer anderen OBB... da fehlt mir der Ansatz.

Für den Abstand zu einem Punkt hab ich mir folgendes ausgedacht.
Ich nehme mir den Vektor MittelPunkt-Punkt und projeziere ihn auf die X-Achse des lokalen KoSys. Wenn er nun länger ist als die Halbe Breite der Box wird er Abgeschnitten. Genauso mit Y und Z. Am Schluss hab ich den Punkt auf der Box der meinem anderen Punkt am nähesten ist.
Und dann brauch ich bloß noch den Abstand der 2 Punkte berechnen.

Wenn man aber 2 Boxen hat fällt mir nichts gutes ein.

Chis


Nimm meinen Rat an - ich brauch ihn sowieso nicht

Offline

 

#2 22.08.2007 13:18:54

DerPeer
GodlikeMember
Ort: Berlin
Registriert: 04.02.2005
Beiträge: 1291

Re: Abstand OBB <--> OBB

Du könntest die Distanzen aller 8 Eckpunkte der einen Box zu allen 8 Eckpunkten der anderen Box berechnen. Das ist zwar nicht gerade die richtige Methode aber sehr einfach zu implementieren.

DerPeer

Offline

 

#3 22.08.2007 13:42:45

Chris
ExtremeMember
Ort: Erlangen, Bay
Registriert: 24.01.2005
Beiträge: 694
Web-Seite

Re: Abstand OBB <--> OBB

Aber dann hab ich doch immer noch nicht den minimalen Abstand der beiden Boxen, oder?


Nimm meinen Rat an - ich brauch ihn sowieso nicht

Offline

 

#4 22.08.2007 19:16:39

DerPeer
GodlikeMember
Ort: Berlin
Registriert: 04.02.2005
Beiträge: 1291

Re: Abstand OBB <--> OBB

Nein, vermutlich nicht. Hatten wir da nicht schonmal so ne Frage?
Du könntest auch die einen 12 Kanten mit den anderen 12 vergleichen. Also jeweils den nahsten Abstand berechnen.
Als Gerade-Gerade-Abstand. Mußt dann bloß gucken, ob die beiden Fußpunkte auch zwischen den zugehörigen Eckpunkten liegen.

Ist nur ein wenig rechenaufwändig (12*12). Wieviele OOBs hast Du denn?

DerPeer

Offline

 

#5 23.08.2007 08:27:56

Coolcat
ProGuru
Ort: Aachen, NRW
Registriert: 24.01.2005
Beiträge: 2780
Web-Seite

Re: Abstand OBB <--> OBB

Du solltest wirklich überlegen ob du wirklich den exakten minimalen Abstand brauchst oder nur etwas ungefähres. Der Trick mit den Kugel dürfte hier genauso funktionieren wie bei den Rechtecken.

Coolcat


My software never has bugs. It just develops random features.

Offline

 

#6 23.08.2007 09:47:09

Chris
ExtremeMember
Ort: Erlangen, Bay
Registriert: 24.01.2005
Beiträge: 694
Web-Seite

Re: Abstand OBB <--> OBB

diesmal brauch ich ihn wirklich exakt... Sau kompliziert das problem...
Wenn ich das mit den Rechtecken hätte, könnte ich es für die Quader verwenden. Wenn ich das mit den quadern hätte ginge es auch für rechtecke.

Wie schauts eigentlich mathematisch aus? Also die Gleichung für alle Punkte auf der Oberfläche aufstellen und dann von der anderen Gleichung abziehen. Das ganze ableiten und ein Minimum suchen.
Bei rechecken ist das wahrscheinlich leichter als bei Quadern.

Chris


Nimm meinen Rat an - ich brauch ihn sowieso nicht

Offline

 

#7 23.08.2007 10:58:38

DerPeer
GodlikeMember
Ort: Berlin
Registriert: 04.02.2005
Beiträge: 1291

Re: Abstand OBB <--> OBB

Du kannst aber ein Rechteck nicht analytisch einfach ausdrücken. Da sind immer Fallunterscheidungen nötig. Also viele IFs.
Und wenn es nur die je zwei Limits in den drei Dimensionen sind.

Ich glaube, alle Kantenpaare zu betrachten ist schon ein richtiger und schneller Weg.

DerPeer

Offline

 

#8 23.08.2007 12:39:13

Chris
ExtremeMember
Ort: Erlangen, Bay
Registriert: 24.01.2005
Beiträge: 694
Web-Seite

Re: Abstand OBB <--> OBB

ok anderer Ansatz:

nehmen wir an Quader A steckt in Quader B. Ich möchte nun wissen, wie weit A eingedrungen ist.

Geht das irgendwie?

Beitrag geändert von Chris (23.08.2007 12:54:40)


Nimm meinen Rat an - ich brauch ihn sowieso nicht

Offline

 

#9 23.08.2007 13:46:24

Coolcat
ProGuru
Ort: Aachen, NRW
Registriert: 24.01.2005
Beiträge: 2780
Web-Seite

Re: Abstand OBB <--> OBB

Du kannst einen beliebigen Quader mit den Eckpunkten p_i so ausdrücken:
Die Menge aller Randpunkte:
{ p | Summe von i=1 bis 8: c_i * p_i = p UND Summe von i=1 bis 8: c_i =1 }
Das heißt du müsstes folgende Gleichung minimieren:

d = c1*p1 + c2*p2 + c3*p3 + c4*p4 + c5*p5 + c6*p6 + c7*p7 + c8*p8 - d1*q1 + d2*q2 + d3*q3 + d4*q4 + d5*q5 + d6*q6 + d7*q7 + d8*q8
Mit den Nebenbedingungen:
| d | > 0
c1 + c2 + c3 + c4 + c5 + c6 + c7 + c8 = 1
d1 + d2 + d3 + d4 + d5 + d6 + d7 + d8 = 1

Naja, das ist ne Gleichung mit 16 Unbekannten. Ich habe keine Ahnung wie man da ran geht, aber gibt es bestimmt einen Algo für.


My software never has bugs. It just develops random features.

Offline

 

#10 23.08.2007 14:32:38

Chris
ExtremeMember
Ort: Erlangen, Bay
Registriert: 24.01.2005
Beiträge: 694
Web-Seite

Re: Abstand OBB <--> OBB

Hm...

das einzige was mit dazu einfällt ist ein Downhill-Simplex... puh nicht schön.
Und die Eindingtiefe lässt sich auch nicht leichter berechnen?


Nimm meinen Rat an - ich brauch ihn sowieso nicht

Offline

 

#11 23.08.2007 15:36:52

Coolcat
ProGuru
Ort: Aachen, NRW
Registriert: 24.01.2005
Beiträge: 2780
Web-Seite

Re: Abstand OBB <--> OBB

BTW, es müsste so heißen:
d = c1*p1 + c2*p2 + c3*p3 + c4*p4 + c5*p5 + c6*p6 + c7*p7 + c8*p8 - d1*q1 - d2*q2 - d3*q3 - d4*q4 - d5*q5 - d6*q6 - d7*q7 - d8*q8
(naja, scheint ja keiner gemerkt zu haben... tongue )

Zitat:

Und die Eindingtiefe lässt sich auch nicht leichter berechnen?

Man könnte wieder alle Ecken, Kanten und Flächen durchgehen wie bei dem Rechteck. Aber schön ist das auch nicht.


My software never has bugs. It just develops random features.

Offline

 

#12 23.08.2007 15:46:13

Coolcat
ProGuru
Ort: Aachen, NRW
Registriert: 24.01.2005
Beiträge: 2780
Web-Seite

Re: Abstand OBB <--> OBB

Ähm, http://de.wikipedia.org/wiki/Downhill-Simplex-Verfahren ist laut Wikipedia für nicht lineare Probleme. Die Gleichung oben ist aber linear, dürfte also schon mal eine wesentliche Vereinfachung sein: http://de.wikipedia.org/wiki/Simplex-Algorithmus

In dem Artikel steht auch das es noch andere Verfahren gibt.

Coolcat


My software never has bugs. It just develops random features.

Offline

 

#13 23.08.2007 15:55:41

Chris
ExtremeMember
Ort: Erlangen, Bay
Registriert: 24.01.2005
Beiträge: 694
Web-Seite

Re: Abstand OBB <--> OBB

sollte für die c_i nicht auch noch 0 <= c_i <= 1 gelten?

oh, das Problem ist linear? Sicher? man braucht ja den Abstand, und nicht den Punkt... oder liege ich da jetzt falsch?

Beitrag geändert von Chris (23.08.2007 15:56:04)


Nimm meinen Rat an - ich brauch ihn sowieso nicht

Offline

 

#14 23.08.2007 21:30:44

DerPeer
GodlikeMember
Ort: Berlin
Registriert: 04.02.2005
Beiträge: 1291

Re: Abstand OBB <--> OBB

Leute! Ein iterativer Optimierungsalgorithmus ist garantiert langsamer als die Kantenpaare zu untersuchen. Und häßlicher.
Nimm sowas nur, wenn es unbedingt sein muß.

Außerdem findest Du damit auch nicht die optimale Lösung, sondern nur eine SO genaue wie Du Zeit hast.

In Echtzeitanwendungen, wo ich pro Frame die Minimalabstände von 100 Quadern berechnen muß, will ich keinen schrittweisen Optimierungsalgorithmus anstrengen ... also, Du solltest das auch nicht wollen big_smile

Bedenke doch mal, was Du schon tun mußt. Du mußt pro Gerade-Gerade-Abstand vielleicht 10 Vektoroperationen durchführen (bin mir da nicht sicher). Macht dann maximal 1440 Vektoroperationen. Das geht fix.
Du kannst auch noch Vorauswahlen treffen, wenn die zugehörigen Ecken weiter weg sind oder so, vielleicht kann man da noch was rausholen.
Das ganze wird direkt ausgerechnet. In EINEM Schritt. Da wird nix angenähert oder Gleichungssysteme gelöst.

Sorry, falls ich mich hier überschlage. Meine KantenIdee ist vielleicht auch nicht die beste, aber (ich hoffe) wahrscheinlich schneller.

Viel Glück smile

DerPeer

Offline

 

#15 23.08.2007 21:32:04

Coolcat
ProGuru
Ort: Aachen, NRW
Registriert: 24.01.2005
Beiträge: 2780
Web-Seite

Re: Abstand OBB <--> OBB

Zitat:

sollte für die c_i nicht auch noch 0 <= c_i <= 1 gelten?

Jap, hab ich vergessen.

Zitat:

oh, das Problem ist linear? Sicher?

ja, linear heißt, dass kein x^2 oder so drin vorkommt, also nur
variable * konstante + variable2 * konstante2 + ....

Zitat:

man braucht ja den Abstand, und nicht den Punkt... oder liege ich da jetzt falsch?

richtig, man muss den Betrag des Vektors, was als die Länge definiert ist, minimieren.

Bevor du dich jetzt fragst wie den die Berechnung der Länge linear sein kann wo doch da Quadrate und wurzeln vorkommen:
Das ist kein Problem da die Normen untereinander äquivalent sind, man kann also auch z.B. das Minimum bezüglich einer einfacheren Norm (z.B Betragsnorm oder Maximumsnorm) nehmen:
Betragsnorm, die Summe der Beträge von xyz:
|x| + |y| + |z|
Maximumsnorm, das Maximum der Beträge von xyz:
max {|x|,|y|,|z|}

Am Ende brauchst du nur einen Ergebnis-Vektor nur nochmal mit der "richtigen" Norm, also der üblichen 2-Norm bzw. das was du unter "Länge" verstehst, ausrechnen.

Coolcat


My software never has bugs. It just develops random features.

Offline

 

#16 23.08.2007 22:40:54

Chris
ExtremeMember
Ort: Erlangen, Bay
Registriert: 24.01.2005
Beiträge: 694
Web-Seite

Re: Abstand OBB <--> OBB

Das Problem mit der Kantenidee ist, dass sie nicht stimmt.

Wenn der eine Quader eher eine große Fläche ist und auf der Großen fläche in der Mitte ein kleiner Würfel auf einer Kante steht, dann stimmt das mit dem Abstand nicht mehr.

@Coolcat
Das war meine Überlegung, dass der Betrag des Vektors aus der lienaren gleichung dann doch eine quadratische macht. (Man hätte sich die Wurzel sparen können) Aber wenn das stimmt dass die Betragsnorm zur Länge äquivalent ist, dann wäre das kein Problem mehr. Trotzdem hat DerPeer recht. Einen Optimierer zu benutzen, ist wahrscheinlich immer langsamer als eine Berechnung.

Aber eigentlich brauch ich die Eindingtiefe, und die lässt sich mit keiner der beiden Methoden berechnen.

Ich muss nach der Kollision die Quader auseinander ziehen, so dass sie nicht ineinander stecken bleiben. Jetzt sagt ihr bestimmt: merk dir doch die letzte Koordinate vor der Kollision und setze den Quader einfach dahin zurück. Aber dann kann ein Quader nicht mehr über den anderen ruschen, weil er ganz rurückgesetzt wird, und nicht nur rausgeholt wird. Bei rausholen bleibt die Komponente der Bewegung die senkrecht zur Fläche ist erhalten. beim Zurücksetzen nicht.

Chris


Nimm meinen Rat an - ich brauch ihn sowieso nicht

Offline

 

#17 24.08.2007 09:08:57

DerPeer
GodlikeMember
Ort: Berlin
Registriert: 04.02.2005
Beiträge: 1291

Re: Abstand OBB <--> OBB

Oh sorry. Du hast recht. Die Kantenidee ist nicht richtig. Nehme alles zurück und bin das nächste Mal bescheidener big_smile

Willst Du Kollisionsbehandlungen der Quader machen? Da bin ich mal gespannt, da hab ich enorme Probleme mit.

DerPeer

Offline

 

#18 24.08.2007 09:56:13

Coolcat
ProGuru
Ort: Aachen, NRW
Registriert: 24.01.2005
Beiträge: 2780
Web-Seite

Re: Abstand OBB <--> OBB

Zitat:

Einen Optimierer zu benutzen, ist wahrscheinlich immer langsamer als eine Berechnung.

Ähm, ein Approximations-Algorithmus ist häufig sehr viel schneller. Ob das in diesem Fall so ist kann ich nicht sagen, weil ich Simplex halt nicht kenne.


My software never has bugs. It just develops random features.

Offline

 

#19 24.08.2007 18:12:38

Chris
ExtremeMember
Ort: Erlangen, Bay
Registriert: 24.01.2005
Beiträge: 694
Web-Seite

Re: Abstand OBB <--> OBB

[quote=DerPeer]Willst Du Kollisionsbehandlungen der Quader machen?

Die Kollisionsbehandlung hab ich schon, nur das auseinanderziehen klappt eben noch nicht.
Also die RigidBody Engine ist fast fertig bis auf diesen winzigen Teil...

Chris


Nimm meinen Rat an - ich brauch ihn sowieso nicht

Offline

 

#20 28.08.2007 09:18:44

Chris
ExtremeMember
Ort: Erlangen, Bay
Registriert: 24.01.2005
Beiträge: 694
Web-Seite

Re: Abstand OBB <--> OBB

Soo...
nach Tagen mühevoller Suche big_smile hab ich eine Methode gefunden mit der man sowas machen kann.

Man nimt den Seperating-Axis-Test. Der bei Überscheindung natürlich keine Separations-Achse findet. Man merkt sich aber die Achse die den geringsten 'Überlappungsabstand' hat. Diese Achse ist die Normale der Kollision. Der Überlappungsabstand ist dann die Eindringtiefe. Um jetzt noch den Kollisionspunkt ausrechnen zu können macht man folgendes:
Man benutzt die Normale und Projeziert da jeweils die Ecken der Quader drauf. Man merkt sich von Box1 die Maximalen Punkte in Richtung Normale und von Box2 die Minimalen. Man bekommt für jede Box dann 1,2 oder 4 Vertices. Je nach der Anzahl hat man dann eine VertexVertexKollision( 1 vs 1 ) oder zb Edge-Face (2 vs 4) etc...

sehr genial finde ich. Und vor allem extremst schnell!

Mein Problem (ja ich hab immer noch eins) ist jetzt: Wie kann wenn ich eine Face Face Kollision habe den Mittelpunkt der Fläche ausrechnen, weil den Brauche ich füch meine Kollisionsbehandlung. Das gleiche Problem hab ich bei Face-Edge. Die anderen Fälle kann ich behandeln, nur diese 2 bekomme ich nicht hin.

Chris


Nimm meinen Rat an - ich brauch ihn sowieso nicht

Offline

 

Brett Fußzeile

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson