Frage zu Kollisionsabfrage ohne Framebremse
-
otze schrieb:
das ist interessant TGGC, aber ist das bei einem "modernen" polygonreichen mesh noch durchführbar?
Was sollte dich hindern, es durchzuführen? Das Problem ist auf jeden Fall berechenbar.
Bye, TGGC (Demo or Die)
-
rapso schrieb:
Sgt. Nukem schrieb:
rapso schrieb:
life schrieb:
nicht den endpunkt auf kollisionen überprüfen, sondern den vektor vom startpunkt zum endpunkt
das hilft nicht bei zwei sich bewegenden körpern
Wenn man nur die Relativbewegung nimmt schon...
leider auch dann nicht...
rapso->greets();
...und jetzt bitte nochmal die Version für 3-jährige Windelkacker, damit auch ich das kapiere...
TGGC schrieb:
Genau genommen muss man einfach alles eine Dimension erweitern, das ist dann die Zeit. Für 2D kann man sich das noch recht gut vorstellen. z.b. ein Quadrat, das bei 10s erzeugt wird und bei 20s wieder verschwindet ergibt dann ein Quader mit Länge und Breite des Quadrats und Höhe 10s. Ein Kreis der immer da ist, ergibt einen unendlich hohen Zylinder. Bewegt sich der Kreis, dann hat man einen schiefen Zylinder. Ein Kreis, der zu einem Punkt schrumpft ergibt einen Kegel. Für Kollisionen braucht man nun "nur" Schnitte zwischen diesen n-dimensionalen Körpern suchen. Auf der Zeitachse erkennt man den Zeitpunkt der Kollision.
Echt interessant. Gar nicht so doof auf den ersten Blick.
-
wieso schickst du nicht einen Strahl in einer preframe (oder postframe) funktion los vom Startpunkt des Objekts in Richtung der Bewegung.
Wenn es eine intersection gibt, kannst du Ort und Zeit bestimmen. Bei sampling liegt das Problem in der diskreten Natur, sprich nur wenn die zeitspanne zwischen zwei Mesungen infinitesimal werden, entspricht die Messung einer stetigen Funktion. Glücklicherweise kennen wir das Shanontheorem, dass besagt, das unsere Samplingfrequenz doppelt so gross sein muss wie die höchst vorkommende Frequenz. In deinem beispiel ist die höchst vorkommende Frequenz die Geschwindigkeit mit der sich deine Objekte bewegen. Damit kennst du auch deine Samplingfrequenz und weisst wie oft du nach Kollisionen abfragen.
neben diesen überlegungen gibt es obtimierungsstrategien um den aufwand kleiner zu halten, wie etwa space partitioning, gruppen in bounding volumes packen (schnellster bekannter intersection test ist der "axis aligned boxes", einfachster ist "boundings spheres") oder einen baum zum represäntieren der datenstruktur (octtree o.ä.).Zur vertieften betrachtung würde ich dir die OpenDynamicsEngine empfehlen www.ode.org.
Bei dem Projekt www.delta3d.org wird ODE eingebunden mit einem Szenengraphen www.openscenegraph.org, also wenn dir die Ideen ausgehen, kannst du ja mal schauen wie die das Problem lösen.
-
cof schrieb:
Glücklicherweise kennen wir das Shanontheorem, dass besagt, das unsere Samplingfrequenz doppelt so gross sein muss wie die höchst vorkommende Frequenz. In deinem beispiel ist die höchst vorkommende Frequenz die Geschwindigkeit mit der sich deine Objekte bewegen. Damit kennst du auch deine Samplingfrequenz und weisst wie oft du nach Kollisionen abfragen.
Das ist Quatsch. Die Geschwindigkeit allein sagt überhaupt nichts aus. Wichtig wäre, wie lange sich 2 Objekte berühren. Man muss nämlich in dieser Zeit mindestens einmal testen um die Kollision zu testen. Selbst wenn sich alle Körper langsamer als v bewegen, so gibt es trotzdem eine beliebig kurze Zeit t, nach der sie sich wieder trennen nachdem sie sich berühren.Dazu müssen sie lediglich nach t/2 beide die Richtung umkehren.
Bye, TGGC (Demo or Die)
-
was der satz aussagt ist: "Das Programm muss mindestens so oft testen, dass bei der grösst möglichen verschiebung (abhängig von geschwindigkeit) keine kollision stattfinden darf, denn sonst wird sie nicht erkennt"
-
cof schrieb:
was der satz aussagt ist: "Das Programm muss mindestens so oft testen, dass bei der grösst möglichen verschiebung (abhängig von geschwindigkeit) keine kollision stattfinden darf, denn sonst wird sie nicht erkennt"
Dann ist das wohl auch Quatsch.
Bye, TGGC (Demo or Die)
-
TGGC schrieb:
Genau genommen muss man einfach alles eine Dimension erweitern, das ist dann die Zeit. Für 2D kann man sich das noch recht gut vorstellen. z.b. ein Quadrat, das bei 10s erzeugt wird und bei 20s wieder verschwindet ergibt dann ein Quader mit Länge und Breite des Quadrats und Höhe 10s. Ein Kreis der immer da ist, ergibt einen unendlich hohen Zylinder. Bewegt sich der Kreis, dann hat man einen schiefen Zylinder. Ein Kreis, der zu einem Punkt schrumpft ergibt einen Kegel. Für Kollisionen braucht man nun "nur" Schnitte zwischen diesen n-dimensionalen Körpern suchen. Auf der Zeitachse erkennt man den Zeitpunkt der Kollision.
Das reicht noch nicht ganz, wenn sich beide Körper bewegen. Dann musst du auch noch Prüfen, ob zum Kollisions-Zeitpunkt auch wirklich beide Körper an der Schnittstelle waren. (Falls es so genau sein soll.)
-
Und warum kann man jetzt nicht einen Körper als Basis eines "Kollisions-Koordinatensystems" nehmen und nur die Relativbewegung betrachten (d.h. nur der andere bewegt sich)?!
-
XXXXX X 2 X XXXXX ^ ^ yyyyy<----yyyyy | y 2 y y 1 y | yyyyy<----YYYYY | | | XXXXX X 1 X XXXXXDie Objekte X und Y bewegen sich in einer Zeiteinheit gleich schnell von 1 nach 2. Eigentlich gibt es keine Kollision, da Y schon weg ist, wenn X an diese Stelle kommt. Wenn man jetzt Y still stehen läst oder nur die Zeit-Dimension-Erweiterten Rechecke betrachtet, würde man trotzdem eine Kollision bekommen.
Du weichst der Kugel im letzten Moment aus und wirst trotzdem getroffen.
-
MrBurns: Darum muss man auch für die Zeit eine weitere (in diesem Fall dritte) Dimension einführen, wie TGGC sagte. Dann funktioniert alles Wunderbar, weil physikalisch korrekt. Nur is es wahrscheinlich für Echtzeitdarstellung zu verschwenderisch.
-
MrBurns schrieb:
XXXXX X 2 X XXXXX ^ ^ yyyyy<----yyyyy | y 2 y y 1 y | yyyyy<----YYYYY | | | XXXXX X 1 X XXXXXDie Objekte X und Y bewegen sich in einer Zeiteinheit gleich schnell von 1 nach 2. Eigentlich gibt es keine Kollision, da Y schon weg ist, wenn X an diese Stelle kommt. Wenn man jetzt Y still stehen läst oder nur die Zeit-Dimension-Erweiterten Rechecke betrachtet, würde man trotzdem eine Kollision bekommen.
Du weichst der Kugel im letzten Moment aus und wirst trotzdem getroffen.Quatsch.
In dem Fall würde man dieselbe Situation nicht mit Betrachtungspunkt == Y sehen (und damit Y == still, X bewegt sich --> Relativbewegung) , sondern einen komplett anderen Fall daraus machen.Was man einfach machen müsste, ist die Bewegung von Y negativ aufzurechnen. Dann bleibt Y stehen, und X bewegt sich (in diesem Fall) von Y weg. Dann reicht statt einer 2-dyn-Objekte-Kollision eine 1-dyn-1-stat-Objekt-Kollision.
Das ist alles worauf ich hinaus will.Also so:
XXXXX X 2 X XXXXX / / yyyyy / / y 0 y / / YYYYY / / / / XXXXX X 1 X XXXXX
-
Das Sampling wie rapso es sagte ist zwar schön und gut.
Aber es erzeugt dieselbe Problematik wie bei Physik-Systemen:
Wann ist genug gesamplet?
Wie groß oder klein darf mein Samplings-Zeit-Delta werden, bevor alles in sich zusammenkracht?!?
-
ChockoCookie schrieb:
MrBurns: Darum muss man auch für die Zeit eine weitere (in diesem Fall dritte) Dimension einführen, wie TGGC sagte. Dann funktioniert alles Wunderbar, weil physikalisch korrekt. Nur is es wahrscheinlich für Echtzeitdarstellung zu verschwenderisch.
Hab ich doch gemacht. Ich kann nur in ASCII so schlecht 3D zeichnen, darum hab ich die Bewegung so gewählt, dass das Quadrat ein Quadrat bleibt. Es wird nur größer.
Sgt. Nukem:
OK, das mit der Relativbewegung macht die Sache wohl einfacher.
-
XXXXX W X 2 X A XXXXX N ^ ^ yyyyy<---Dyyyyy | y 2 y Wy 1 y | yyyyy<---AYYYYY | N | | D XXXXX X 1 X XXXXXMir ist da gerade noch ein Problem eingefallen. Wenn sich Y garnicht dahin bewegen kann, wo wir annehmen, dass es sich hinbewegen würde, dann müsste man ja die Berechnung für X auch nochmal durchführen. Und wenn jetzt Y nicht an der Wand sondern an einem anderen Objekt hängen bleibt, aber dieses nur da ist, weil es mit X kollidiert ist, dann rechnen wir im Kreis.
Oder gibts dafür auch ne einfachere Lösung, falls ihr versteht was ich sagen will.
-
MrBurns schrieb:
TGGC schrieb:
Genau genommen muss man einfach alles eine Dimension erweitern, das ist dann die Zeit. Für 2D kann man sich das noch recht gut vorstellen. z.b. ein Quadrat, das bei 10s erzeugt wird und bei 20s wieder verschwindet ergibt dann ein Quader mit Länge und Breite des Quadrats und Höhe 10s. Ein Kreis der immer da ist, ergibt einen unendlich hohen Zylinder. Bewegt sich der Kreis, dann hat man einen schiefen Zylinder. Ein Kreis, der zu einem Punkt schrumpft ergibt einen Kegel. Für Kollisionen braucht man nun "nur" Schnitte zwischen diesen n-dimensionalen Körpern suchen. Auf der Zeitachse erkennt man den Zeitpunkt der Kollision.
Das reicht noch nicht ganz, wenn sich beide Körper bewegen. Dann musst du auch noch Prüfen, ob zum Kollisions-Zeitpunkt auch wirklich beide Körper an der Schnittstelle waren. (Falls es so genau sein soll.)
Doch, das reicht. Du hast es nur nicht verstanden. Die Zeit ist eine weitere Dimension. Und es gibt auch in deinem Fall keinen Schnitt wenn man alle Dimensionen betrachtet. Deine Zeichnung ist nur eine Projektion auf x/y und daher nicht aussagekräftig. Jeweils schraffiert die Endposition auf die x/y - Ebene projeziert und rechts ein Quadrat, das sich den selben Zeitraum nicht bewegt hat.
_____ /__2_/| _____ | | | /____/\ | | | \ \ \ | | | \ \ \ | | | \ \ \ | | | \ \ \ | | | _____ \ \ \ | | | /____/| \ \ \ | | |__ | | | \ \ \ | | |/// /|\ | | | ____ \ \ \| | | | t | | | ///// \____\| | | | | | | | | | | _ | | | | | | | /| | | | | | | | / y | | | | | | | / | | | |_1_|/ | / |___|/ | / /___________________________|/ \ xDas zweite Problem ist schon Kollisionsreaktion und nicht mehr nur Erkennung.
Bye, TGGC (Demo or Die)
-
MrBurns schrieb:
...darum hab ich die Bewegung so gewählt, dass das Quadrat ein Quadrat bleibt. Es wird nur größer...
Genau das ist ja das Problem. Du bleibst in der 2. Dimension.
@TGGC: Tolle Zeichnung
-
OK, wenn mans richtig 3D zeichnet, dann sieht man auch, dass sie sich doch nicht schneiden.
Das mit dem im Kreis rechnen, wie ich oben meine, kann eigentlich auch nicht passieren, wenn man nicht rückwärts in der Zeit reist. Man muss "nur" beim ersten Kollisionszeitpunkt mit den neuen Richtungen rechnen und darf die Richtung davor natürlich nicht ändern. Ohne Abprallen also so:
(Bild klau)_____ Wand /__2_/| _____ _____ | | | /____//____/| | | | | || | | | | | | || | | | | | | || | | | | | | || | | | | | | || | | | | | | || | | | | | | || | | | | | /|\ | || | | | | | | t | | \ \ \| | | | |___|/ \____\| | | | _ | | | | /| | | | | / y | | | | / |_1_|/ | / | / /___________________________|/ \ xWenn man das aber bei mehreren Objekten bei jeder Kollision macht, dann wirds bei vielen Kollisionen auch ziemlich ruckeln. Oder hat jemand eine bessere Idee?
-
joomoo schrieb:
Was wenn das Spiel kurz mal stockert, warum auch immer, und die Zeit zwischen zwei Frames mit einmal 1 Sekunde beträgt. Der Spieler könnte sich dann mit so einem Ruck bewegen, dass er z.B. durch eine Wand hindurch teleportiert wird. Und er würde sich nicht mit der Wand überlappen und könnte einfach weiter fahren/gehen.
Wenn es sich nicht um ein Netzwerkspiel handelt, das Timing also nicht so eine große Rolle spielt, dann hätte ich noch einen Vorschlag.
Ich schätzte du hast eine Variable in der die Zeit gespeichert ist, die der Computer gebraucht hat, um das letzte Bild zu berechnen. Für diese Variable führst du einfach einen Maximalwert ein. Dann läuft das Spiel zwar manchmal langsamer, als vorgesehen, aber der Unterschied zwischen zwei Frames ist nie für die Kollisionserkennung zu groß.
-
Oder Du führst halt das von rapso vorgeschlagene Sampling ein, und iterierst in jeder Schleife erstmal so lange herum, bis ein genügend kleines Zeitdelta erreicht ist.
-
TGGC schrieb:
_____ /__2_/| _____ | | | /____/\ | | | \ \ \ | | | \ \ \ | | | \ \ \ | | | \ \ \ | | | _____ \ \ \ | | | /____/| \ \ \ | | |__ | | | \ \ \ | | |/// /|\ | | | ____ \ \ \| | | | t | | | ///// \____\| | | | | | | | | | | _ | | | | | | | /| | | | | | | | / y | | | | | | | / | | | |_1_|/ | / |___|/ | / /___________________________|/ \ xWuhaaaa!! Die Quali der ASCII Diagramme hier wird ja immer besser!!
