Archiv verlassen und diese Seite im Standarddesign anzeigen : Algorithmus: Möbelstück durch Tür
mekakic
2009-05-18, 08:24:35
Hi,
gibt es ein sicheres Verfahren oder Vorgehensweise, um zu testen ob ich durch Translation und Rotation einen Gegenstand durch einen bestimmten begrenzten Raum bekomme?
Angenommen ich habe ein 3D Modell einer Tür und ein 3D Modell irgendeines (komplexen) Möbelstücks, kann ich irgendwie Verschiebungen und Rotationen errechnen, wenn es einen Weg durch die Tür gibt, der dazu nicht trivial ist?
danke =)
tombman
2009-05-18, 08:44:26
Hmm, du drehst den Gegenstand um 3 Achsen und betrachtest dabei immer das Projektionsbild. Sobald das Bild die maximale Ausdehnung von x/y des Loches zu mindestens einem Zeitpunkt nicht überschreitet sollte es gehen.
Es gibt aber auch Gegenstände (zb ein Winkel), der diese Anforderung niemals erfüllt und trotzdem reinpaßt- nämlich indem man zb das Stück "einfädelt".
Ganon
2009-05-18, 08:48:25
Na das wird wohl nicht klappen, so wie ich dich verstehe. Einen großen Sessel schiebst du ja auch erst mit der Lehne/Sitzfläche durch die Tür und "drehst" den Sessel dann in den Raum. Trotzdem passt das Projektionsbild zu keiner Zeit durch die Tür.
@TS
Wichtig wäre für eine sinnvolle Anwendung auch der Raum um die Tür. Natürlich je nachdem was du vor hast mit der Anwendung :D
eine perspektivische projektion ist nicht längenerhaltend
d.h. wenn, dann musst du schon in weltkoordinaten rechnen
tombman
2009-05-18, 08:57:22
Ist nicht perfekt, siehe mein edit ;)
Die echte Lösung wird wohl Schulmathe übersteigen...
DocEW
2009-05-18, 09:57:12
Ich weiß nicht, ob man deinen Spezialfall irgendwie geschickt ausnutzen kann, aber generell ist Bewegungsplanung im 3D NP-schwer. Dabei sucht man allerdings auch den kürzesten Weg, nicht irgendeinen, wenn ich mich recht erinnere. Wenn du Approximationsalgorithmen suchst, schau vielleicht mal unter Motion Planning (http://en.wikipedia.org/wiki/Motion_planning)
Monger
2009-05-18, 10:27:40
Sehr spezielle Lösung: das ganze mit Koordinatentransformationen übersetzen (http://de.wikipedia.org/wiki/Denavit-Hartenberg-Transformation). Da sieht man dann sehr genau, ob man auf dem Weg mit irgendwas kollidieren kann. Sowas braucht man z.B. für Industrieroboter, damit die sich nicht gegenseitig blockieren.
Ist aber höllisch kompliziert. Da steckt ein riesiges Forschungsfeld dahinter. Das ist viel, VIEL komplizierter als man glauben könnte. Dazu musst du dem Computer nämlich sowas wie "Augenmaß" beibringen, weil er kann und soll nicht jede denkbare Drehung ausprobieren. Wir Menschen machen das ziemlich intuitiv richtig, teils auch aus Erfahrung heraus. Den Luxus hat ein Computer nicht, der braucht dafür ein ziemlich komplexes mathematisches Modell.
Simple Methode: miss die längste Kante deines Objektes, und die kürzeste Öffnung deiner Tür. Wenn das passt, kriegst du dein Objekt auf jeden Fall rein. Wenn die Tür kleiner ist, hast du zwar noch lange keine Aussage darüber ob es nicht vielleicht doch gehen kann, aber immerhin.
Ich denke, über den Weg würde ich mich dann auch rantasten. Die nächste Approximation wäre dann ein Quader. Da der drehbar ist, wird die Sache gleich wesentlich komplexer.
Sehr spezielle Lösung: das ganze mit Koordinatentransformationen übersetzen (http://de.wikipedia.org/wiki/Denavit-Hartenberg-Transformation). Da sieht man dann sehr genau, ob man auf dem Weg mit irgendwas kollidieren kann. Sowas braucht man z.B. für Industrieroboter, damit die sich nicht gegenseitig blockieren.
was ist daran kompliziert? also das prinzip der koordinatentransformation und die verkettung durch matrizenmult.
das die ausgangsfrage nicht trivial ist, ist klar
Ganon
2009-05-18, 11:14:53
Bei Möbeln kommt ja auch noch erschwerend hin, dass diese ja auch in einem gewissen Maße formbar sind. D.h. von der Außenform könnte er vllt. gar nicht durchpassen, wenn man aber das Polster etwas "reindrückt", dann geht es. ;)
Monger
2009-05-18, 12:14:48
was ist daran kompliziert? also das prinzip der koordinatentransformation und die verkettung durch matrizenmult.
Die Datenmenge ist schlicht bäh. Ich kenns halt nur von der Robotik her, und das ergibt bereits mit dreiachsigen Robotern ziemlich hässliche Berechnungen.
Wie gesagt: damit kann man viel Zeit verbringen. Das ist kein Algorithmus den man sich mal "schnell" irgendwo reinflanscht.
Controller Khan
2009-05-18, 12:36:33
was ist daran kompliziert? also das prinzip der koordinatentransformation und die verkettung durch matrizenmult.
so was wird kaum Teil eines Frameworks sein, sei .Net oder Java.
=> alles selber machen, optimieren, docu.
so was wird kaum Teil eines Frameworks sein, sei .Net oder Java.
=> alles selber machen, optimieren, docu.
matrixmultiplikationen und kinematische ketten selber programmieren...
ich gebe zu das könnte den gemeinen modulzusammenklicker überfordern
klar ist es arbeit, aber es ist nicht kompliziert
Das Möbelstück wird duch ein Polygonnetz dargestellt und es wird überprüft, ob die Vektoren der Tür eine Fläche des Netzes durchstoßen. :confused:
Spasstiger
2009-05-18, 13:42:49
Das Möbelstück und den Raum für HL2 nachbauen und dann schauen, ob man das Möbelstück per Gravity-Gun durch die Tür bekommt.
Ganon
2009-05-18, 14:00:04
Virtuelles "ausprobieren" ist ja nun nicht gerade ein mathematischer Ansatz :D
Wenn das in HL2 mit der Gravity Gun geht (oder auch nicht), dann müssen diese Algorithmen dort doch in irgendeiner Weise implementiert sein?
DocEW
2009-05-18, 14:09:07
Nein. Wenn du in HL2 das Möbelstück losballerst, prüfst du genau eine Möglichkeit, es durch die Tür zu kriegen. Du willst aber eigentlich wissen, ob es irgendeine Möglichkeit gibt.
Pinoccio
2009-05-18, 14:13:21
Nein. Wenn du in HL2 das Möbelstück losballerst, prüfst du genau eine Möglichkeit, es durch die Tür zu kriegen.Och, das ist doch weit verbreitet. Z. B. bei Primzahltests. Die Tür passt zu 99,95% nicht oder eben sicher durch die Tür ist doch ein brauchbares Ergebnis.
mfg
Ganon
2009-05-18, 15:13:08
Wenn das in HL2 mit der Gravity Gun geht (oder auch nicht), dann müssen diese Algorithmen dort doch in irgendeiner Weise implementiert sein?
Nein ;)
Das ist ausprobieren. Dann braucht man kein Programm, weil dann kann man sich auch gleich mit dem Möbelstück vor die Tür stellen. ;)
Und dann geht die Prüfung auch nur soweit DU sie gemacht hast. Ob es nicht doch noch eine andere Möglichkeit gibt, wird dabei nicht gefunden.
Monger
2009-05-18, 15:14:39
matrixmultiplikationen und kinematische ketten selber programmieren...
ich gebe zu das könnte den gemeinen modulzusammenklicker überfordern
klar ist es arbeit, aber es ist nicht kompliziert
Du bist ein elender Angeber, weißt du das? :tongue:
"Viel Arbeit" setze ich mit "kompliziert" gleich. Machbar ist grundsätzlich mal programmtechnisch (*fast*) alles, nur entsprechend aufwendig.
Da du das Möbelstück hier ja mal grundsätzlich in jede Richtung drehen und schieben kannst, ist das ein ziemlich vielachsiger Vektorraum. Dann musst du auch noch das Möbelstück selbst und die Tür in diesen kinematischen Raum übertragen (was bei Robotern selten gemacht wird. Da ist man froh, wenn sich nur die Roboterarme nicht verheddern), und muss dann die Schnittmenge aus diesen Räumen berechnen. Und danach musst du aus diesem mehrdeutigen Raum dir zumindest mal eine Lösung errechnen.
Ich finde, das ist verhältnismäßig viel Mathematik, um einen Stuhl durch die Tür zu kriegen.
Das:
http://www.math.berkeley.edu/~sethian/2006/Applications/Robotics/robotics.html
könnte Dich vielleicht interessieren. Fast Marching ist in 2D relativ einfach zu implementieren, vermutlich ist es in 3D nicht deultich komplizierter.
Fast Marching hört sich in 2d ganz verwendbar an. In 3d ist es allerdings deutlich rechenaufwändiger, 6 Dimensionen für den Zustandsraum statt nur 3.
Da kommt man schnell zu Problemgrößen, die man nicht mehr lösen kann. Schon 30° Winkelstufen und 10 cm Bewegungsgitter (über 3x3x3m Würfel) gibt 46 Mio Konfigurationen. Für jede davon muss man nichttriviale Operationen ausführen, das dürfte schon Laufzeit in Minuten ergeben. Alles doppelt so fein diskretisiert gibt direkt den 64-fachen Aufwand.
Pinoccio
2009-05-18, 16:54:03
Fast Marching ist in 2D relativ einfach zu implementieren, vermutlich ist es in 3D nicht deultich komplizierter.sOT: nicht alles, was in zwei Dimesionenen gut geht, funktioniert auch in dreien. Zum Beispiel besoffen zu Hause ankommen.
mfg
Fast Marching hört sich in 2d ganz verwendbar an. In 3d ist es allerdings deutlich rechenaufwändiger, 6 Dimensionen für den Zustandsraum statt nur 3.
Da kommt man schnell zu Problemgrößen, die man nicht mehr lösen kann. Schon 30° Winkelstufen und 10 cm Bewegungsgitter (über 3x3x3m Würfel) gibt 46 Mio Konfigurationen. Für jede davon muss man nichttriviale Operationen ausführen, das dürfte schon Laufzeit in Minuten ergeben. Alles doppelt so fein diskretisiert gibt direkt den 64-fachen Aufwand.
Fast Marching lässt sich aber prima parallelisieren, ab auf die GPU damit und gut ist. Die Menge an Konfigurationen ist erstmal nebensächlich, was ich weiß läuft das ganze ungefähr in O(n*logn), sollte also auch für "richtige" Problemgrößen anwendbar sein.
tombman
2009-05-18, 22:09:01
Wär doch mal eine schöne Aufgabe für die checker hier so ein Programm zu schreiben ;)
Also eine Wand+ Tür definieren, dann ein beliebig geformtes Objekt erstellen lassen per Zufallsprinzip- und dann ein Programm schreiben, welches versucht, das Objekt durch die Tür zu bekommen.
für ne (schnelle) Grafikkarte mach ichs
Flashpoint
2009-05-19, 20:16:51
Was ist denn bei dir schnell? ;)
für ne (schnelle) Grafikkarte mach ichs
Naja so, dass man nachher wieder 3 Softwareentwickler braucht, um das Ganze zu entwirren und daraus ein vernünftiges Programm zu machen? ;) :D scnr
Was ist denn bei dir schnell? ;)
GTX280/HD4890 wär was feines
Naja, so schnell, dass man nachher wieder 3 Softwareentwickler braucht, um das ganze zu entwirren und daraus ein vernünftiges Programm zu machen :D scnr
ach du hast doch keine ahnung. ich hatte mir deine kritik ja teilweise zu herzen genommen
aber nachdem ich seit nunmehr 1monat an einem größeren software-projekt mitarbeite muss ich sagen, das du keine ahnung hast was spaghetti-code ist
da ich aber täglich an diesem mist, den andere verzapft haben, verzweifle,
habe ich mir zumindest an paar sachen angewöhnt, die auch mir das arbeiten erleichtern...
mathematische prozeduren werden aber weiterhin eingehackt, schließlich funktionieren die so wie sie sollen und müssen nicht verändert werden
soviel dazu
vBulletin®, Copyright ©2000-2024, Jelsoft Enterprises Ltd.