Abstand zwischen Kugel und Polygon

[superkarnickel]

Hallo,
ich möchte zwecks Kollisionserkennung im dreidimensionalen Raum die Entfernung zwischen einer Kugel und einem Polygon bestimmen. Ich vermute, dass der einfachse Weg ist, den kürzesten Abstand zwischen Mittelpunkt der Kugel und Polygon zu bestimmen, und diesen mit dem Radius der Kugel zu vergleichen.
Jedoch weiß ich nicht wie ich diese kürzeste Entfernung bestimme.
Kann mir dabei jemand helfen?
Ich freue mich auch über eine Möglichkeit, die nur bei Polygonen bestimmter Seitenanzahl funktioniert.

Dank für's Lesen und Beantworten,
Grüße,

superkarnickel

[neuer_user]

Wurzel aus (x2-x1)²+(y2-y1)²+(z2-z1)²

ohne Garantie, hab ich von Google

[superkarnickel]

Danke, allerding ist das meines Wissens nach der Betrag der Differenz zweier Vektoren (sprich die Entfernung von einem Punkt zum anderen).

[-=Freaky=-]

entweder ich denk gerade wie sooft viel zu kompliziert, oder die kuerzeste entfernung zwischen einem beliebigen polygon und einer kugel ist doch ziemlich kompliziert zu berechnen ... (?)

man muesste doch prinzipiell
1. die entfernung der kugel zu dem geradenabschnitt zwischen jedem "punktepaar" des polygons
2. ggf. die entfernung der kugel zu jeder ebenen flaeche des polygons, sofern eine normale der jew. ebene die kugel schneidet (?)
3. ggf. dann noch die entfernung der kugel zu jedem einzelnen punkt
berechnen?

waere das da fuer eine kollisionserkennung nicht evtl. einfacher die "bounding box" oder so etwas zu benutzen?

mfg,
julian

[upsala]

Dann zieh halt noch die Wurzel, oder besser noch, quadriere den Radius, dann gehts ein bischen schneller.

Im übrigen ist das einfachste Schulmathematik (Satz des Pythagoras).

[-=Freaky=-]

aber die distanz zw. 2 punkten ist je nach fall doch eine relativ ungenaue naeherung zur exakten distanz zw. kugel/beliebigem polgyon?

mfg,
julian

[neuer_user]

Dann berechne doch
Wurzel aus (x2-x1)²+(y2-y1)²+(z2-z1)²
mit den Eckpunkten und einigen Punkten zwischen den Eckpunkten,
und dann den kürzesten Wert berechnen.
Ist dann aber nicht so genau :/

[N¤X]

Zunächst mal: ich geh hier einfach mal von Dreiecken aus, kannst du auch auf Polygone verallgemeinern, aber nur solange sie planar sind! Des weiteren nehme ich einfach mal an, dass du die QVector3D Klasse benutzt, sonst hätte es ja in nem Qt-Forum nix zu suchen...

Prinzipiell ists erstmal so wie du es dir dachtest: Du brauchst den Punkt x deines Polygons für den der Abstand zum Mittelpunkt der Kugel (r) minimal ist. Dann musst du testen, ob (r-x).length() <= 0. Wenn ja, dann gibts ne Kollision.

Das Problem ist den Punkt mit dem kleinsten Abstand zu finden. Wie -=Freaky=- schon gesagt hat muss das kein Vertex sein sondern er kann auch auf ner Kante oder sogar auf der Fläche liegen. Um das ganze etwas zu vereinfachen geht man einfach mal von der Fläche aus, Kanten und Ecken sind schließlich auch Elemente der Fläche.

(Achtung, ich kenne hierfür leider keine Standardlösung, aber so hab ich mir das grad logisch hergeleitet.)

Zunächst mal brauchst du die Normale n von deinem Dreieck (Eck-Vertices sind v1..v3), also einfach n=QVector3D::crossProduct(v2-v1, v3-v1).normalized().
Dann kannst du mit d=r.distanceToPlane(v1, n) den kürzesten Abstand von r zur vom Dreieck aufgespannten Fläche, und mit r+d*n schließlich den Punkt xmin auf der Fläche mit dem geringsten Abstand berechnen.
Dann nimmst du den Vektor (xmin-v1) und clippst ihn an der Geraden v2v3. Der Vektor zeigt dann auf den Punkt des Dreiecks mit dem geringsten Abstand zur Kugel, und damit kannst du dann den Test von ganz am Anfang machen.

Da das aber alles ein bisschen aufwändig ist lohnt es sich aber auf jeden fall Bounding Boxen zu verwenden. Kugeln bieten sich bei dir grad ziemlich an

PS: Es könnte zu kleineren Vorzeichenfehlern kommen bezüglich der Normale n, also ausprobieren oder nachdenken...

[superkarnickel]

Danke!

Da das aber alles ein bisschen aufwändig ist lohnt es sich aber auf jeden fall Bounding Boxen zu verwenden. Kugeln bieten sich bei dir grad ziemlich an

Die Kugel ist die Boundingbox der Kamera. Die Polygone stellen die Umgebung dar und sollen mit einem Octree gruppiert werden. Ist es schlauer andere Formen als Polygone zu prüfen?

[N&#164;X]

OK, also wenn die Kugel die Bounding-Box der Kamera ist nehme ich mal an, dass du die Kamera durch eine 3D-Szene bewegst und damit verhindern willst dass man sich durch Objekte bewegen kann, oder versteh ich das falsch? (Tut vllt nicht viel zur Sache, aber interessiert mich halt grad was du da überhaupt machst ^^)

Ob es schlauer ist andere Formen als Polygone zu prüfen? Wie meinst du das?
Die Wahl deiner Primitive sollte sich eigentlich nach was anderem richten. Du überlegst wie deine Szene sein soll, dementsprechend modellierst du sie mit Polygonen oder parametrisierten Flächen deiner Grafikbibliothek oder aber deine ganz eigenen Primitive (Kugeln, Quader, etc..., z.B. für nen Ray Tracer). Basierend auf der Wahl nimmst du dann halt den passenden Kollisionsalgorithmus, also nicht andersrum.
Wenns dir nur drum geht ob generell Polys oder nur Dreiecke ist das halt so, dass deine Polys von ner normalen Grafikbib wie OpenGL oder DirectX sowieso tesseliert werden, also kannst du auch gleich mit Dreiecken zeichnen und deine Algorithmen drauf abstimmen.
Wenns dir nur um die Wahl der Bounding-Boxes geht, die brauchst du bei nem Octree nicht, deine Knoten stellen ja bereits sowas wie ein Bounding Volumen dar. Du kannst natürlich anstatt nem Octree ne Bounding-Volume-Hierarchie (BVH) nehmen, zum Beispiel mit Axis Aligned Bounding Boxes (AABBs), aber wenn du schon nen Octree hast oder die Datenstruktur auch an anderer Stelle verwendet wird würd ichs einfach so lassen wies ist.

Für die Kollisionstests traversierst du "einfach" deinen Octree, also gehst immer in den Ast in dem deine Kamera grad liegt (vorsicht, weil deine Kamera ein Volumen hat musst du sie gegebenenfalls spliten und in mehrere Äste absteigen!) bis du in ein Blatt kommst, da musst du dann halt gegebenenfalls den Schnitttest durchführen.

Schreib mal ein bisschen was du da so machst, vllt kann man da ein paar Dinge ausschließen oder vereinfachen, weil so generell ist das irgendwie ein bisschen aufwändig...

Wenn es NUR um die Kollisionserkennung geht würd ich glaub einfach ne BVH mit AABBs machen, und um die Kamera auch nur ne AABB legen. Du musst dabei zwar aufpassen mit Dreiecken die parallel zu den Ebenen die durch die Achsenpaare aufgespannt werden (deren AABBs hätten kein Volumen), aber mit nem kleinen Offset lässt sich das umgehen. Der Schnitttest wäre so halt am einfachsten (das zerfällt in drei Schnitttests im 1D) und ne BVH konvergiert schneller als n Octree.

[superkarnickel]

OK, also wenn die Kugel die Bounding-Box der Kamera ist nehme ich mal an, dass du die Kamera durch eine 3D-Szene bewegst und damit verhindern willst dass man sich durch Objekte bewegen kann, oder versteh ich das falsch?

Verstehst du richtitg. Die Kamera kann im Raum bewegt werden, soll aber an Wänden, Decken und Böden "hängen" bleiben.

Ob es schlauer ist andere Formen als Polygone zu prüfen? Wie meinst du das?

Ich meine ob ich mehrere Polygone in einer Boundingbox zusammenfassen sollte (Die Berechnung wir dadurch aber auch nur unwesentlich leichter, oder?).

Die Wahl deiner Primitive sollte sich eigentlich nach was anderem richten. Du überlegst wie deine Szene sein soll, dementsprechend modellierst du sie mit Polygonen oder parametrisierten Flächen deiner Grafikbibliothek oder aber deine ganz eigenen Primitive (Kugeln, Quader, etc..., z.B. für nen Ray Tracer).

Eben aus diesem Grund wollte ich auf dreisetige Polygone prüfen. Es existiert bereits ein Model-Parser von einem Kumpel, der ebenfalls an diesem Projekt mitarbeitet, der dreisetige Polygone ausspuckt.

Wenns dir nur um die Wahl der Bounding-Boxes geht, die brauchst du bei nem Octree nicht, deine Knoten stellen ja bereits sowas wie ein Bounding Volumen dar.

So kann man es machen. Allerdings ist das für meine Begriffe bei Ebenenausschnitten die in einem Winkel != 90° zu einer anderen Ebene liegen sehr umständlich, um eine einigermaßen genaue Kollisionserkennung durchzuführen müsste man den Octree sehr stark untergliedern.
In einem Tutorial über Octrees, welches ich im Netz gefunden habe, wurde es so gemacht: Der Octree gibt nicht an ob der Knoten passierbar ist oder nicht, sondern beinhaltet lediglich Objekte die den Octreeknoten schneiden. So muss man dann in einer sehr großen Szene nicht mehr beispielsweise 1000 Objekte (im ganzen Raum) prüfen sondern nur 10 (an der aktuellen Position). Desweiteren ist es so sehr viel genauer.

Schreib mal ein bisschen was du da so machst, vllt kann man da ein paar Dinge ausschließen oder vereinfachen, weil so generell ist das irgendwie ein bisschen aufwändig...

Ich arbeite mit einem Kumpel an einem OpenGL Spiel. Man soll sich frei auf allen 3 Achsen bewegen können und lediglich durch die Kollisionserkennung eingeschränkt werden. Die Szenen sollen mit einem Programm wie SketchUp erstellt werden, wobei man natürlich auch darüber nachdenken könnte, 2 Files pro Szene zu erstellen: eine Datei für das Aussehen der Szene, und eine Datei für die dazu passenden Boundingboxes.

Wenn es NUR um die Kollisionserkennung geht würd ich glaub einfach ne BVH mit AABBs machen, und um die Kamera auch nur ne AABB legen.

Über AABBs im Zusammenhang mit Kollisionserkennung habe ich ehrlich gesagt noch nichts gelesen. Werde ich natürlich nachholen.

[RHBaum]

Ob es schlauer ist andere Formen als Polygone zu prüfen? Wie meinst du das?

kommt IMHO auf die Anwednung an ....
Es kann mit unter recht komplex sein, mit einem Polygon da zu rechnen. Je nachdem wir schnell man es braucht ....
bei spielen legt man oft fuer die kollisionsberechnung einfacherere (berechenbare) formen(kugeln, quadrate) drueber, die mit der darstellung nix zu tun haben ...

Verstehst du richtitg. Die Kamera kann im Raum bewegt werden, soll aber an Wänden, Decken und Böden "hängen" bleiben.

Dementsprechend koenntest du nen alternatives viel simpleres 3d model machen, welches nur den bewegungsraum der Kamera darstellt.
Wenn in dem Modell schon die "dicke" der kamera bereucksichtigst, brauchst es bei der berechnung nimmer .... und brauchst nur noch den mittelpunkt nehmen ... etc

Ciao ...

[superkarnickel]

Je nachdem wir schnell man es braucht ....
bei spielen legt man oft fuer die kollisionsberechnung einfacherere (berechenbare) formen(kugeln, quadrate) drueber, die mit der darstellung nix zu tun haben ...

Deswegen soll ja ein Octree zum Einsatz kommen. Um weniger Formen prüfen zu müssen.

Dementsprechend koenntest du nen alternatives viel simpleres 3d model machen, welches nur den bewegungsraum der Kamera darstellt.

Das hab ich ja bereits angesprochen... Aber ich bin nicht sicher ob das wirklich sehr viele Einsparungen mit sich bringt.

[-=Freaky=-]

ich denke mal, wenn du eine kugel oder einen quader als bounding box benutzt, ist die rechnung wesentlich einfacher.
du kannst ja die berechnung vereinfachen und ueberfluessige pruefungen weglassen (im gegensatz zum beliebigen polygon), weil du die form, radius/seitenlaenge etc. kennst, dann ist das doch wesentlich einfacher (bzogen auf denk- sowie spaeter rechenleistung), zu gucken, ob sich 2 kugeln/quader schneiden - denke ich.

wird wohl nicht umsonst der standard in computerspielen sein, kollisionstests nach demselben prinzip zu vereinfachen.

mfg,
julian

[superkarnickel]

ich denke mal, wenn du eine kugel oder einen quader als bounding box benutzt, ist die rechnung wesentlich einfacher.

Kugel - OK, aber bei einem Quader ist die Berechnung fast genauso, da er aus 6 Polygonen besteht.

berechnung vereinfachen und ueberfluessige pruefungen weglassen

Man muss weniger prüfen (wird durch den Octree trotzdem stark eingegrenzt), aber die Kollisionserkennung ist wesentlich ungenauer.

weil du die form, radius/seitenlaenge etc. kennst

Die Form und Seitenlänge ist bei einem Polygon auch bekannt .