Bounding Box Baum für animierte Modelle?

[Eisflamme]

Hi,

Sicherlich gibt es dazu einiges Material, aber ich habe mir Mal selbst meine Gedanken gemacht. Wäre ganz cool, wenn jemand Vorschläge hätte, wie ich das verbessern kann oder ob ich damit auf große Probleme stoße:

Statische Modelle

Variante 1) Ich würde erstmal eine AABB um das gesamte Modell legen. Zur weiteren Unterteilung gibt es jetzt verschiedene Möglichkeiten. Was mir in den Kopf sprang, ist die drei möglichen Halbierungen der Box zu prüfen und diejenige zu nehmen, welche das größte Ungleichgewicht von Vertices erzeugt. Bei einem Kegel würde beispielsweise ein Schnitt durch die xy- oder yz-Fläche kein Ungleichgewicht erzeugen, die xz-Fläche bringt da mehr. Also sieht das logischer aus. Um zu sehen, wie viele Boxen ich anlege, könnte ich auch die Abweichungen der drei Gewicht betrachten zusammen mit irgend einer Genauigkeitskonstante. Beispielsweise wäre bei einer Kugel das absolute Gleichgewicht und ich würde wohl gar nicht unterteilen, da das relativ spät erst wirken würde.

Variante 2) Wenn ein Model Meshes hat, könnte ich diese natürlich auch nutzen. Meistens ist ein Bein nun Mal ein Bein, also ein zylinderförmiges Ding, was sich sehr gut durch eine Bounding Box approximieren lässt. Ob ich weiter unterteilen würde, weiß ich nicht.

Wenn man Variante 1) und 2) kombiniert, könnte man wohl ganz gute Ergebnisse erzielen. Eine Möglichkeit einen Stopp zu finden wäre neben den o.g. Ungleichgewichten von Unterteilungen vielleicht auch ein Konvexitätsfaktor. Wenn der sehr hoch ist, sollte man tendenziell weiter unterteilen. Aber da muss man wohl auch abwägen, sonst wird man einem Stachelobjekt recht schnell sehr komplexe Boxen basteln.

Animierte Modelle

Ja, da bin ich etwas unschlüssig. Ich habe meine Node- und meine Boneanimationen und damit bewege ich auch meine Vertices. Jetzt wäre es natürlich viel zu umständlich, für jede Vertex-Änderung diese im Programm zu merken und dementsprechend alle Boxen zu ändern. Was mir jetzt einfällt, wäre vielleicht die äußersten Vertices (welche die BoundingBox ja nun definieren) zu betrachten und eben anhand dieser die Box zu ändern. Das funktioniert bei Rotationen wohl ganz gut, bei Rotationen wird das allerdings komplizierter...

Was auch noch geht, wäre ein Mapping von Bounding Boxen zu einzelnen Bones bzw. Nodes, also zum Skelett. Aber das passt ja auch nicht immer 1 : 1. Manche Bereiche werden vll. gar nicht abgedeckt. Aber dann wären die vll. einfach nicht betroffen. Aber mein Skelett ist ja letztendlich nur über die Vertices der Bones an das Modell gebunden... Hm... ich glaube, das wird relativ kompliziert, das macht man so bestimmt nicht, oder?

Und die dritte Variante wäre wohl einfach, ich gehe durch alle Keyframes durch und erstelle für jedes Keyframe ein BoundingBox-System. Das ist dann natürlich etwas speicherlastig, je nachdem, wie genau ich das mit den Boxen bastel. Aber eigentlich finde ich die Idee bisher am Besten und die ist ziemlich einfach umzusetzen. Ist halt nicht gerade elegant, aber könnte ihren Zweck erfüllen.

Also, ich freue mich sehr auf Gedanken und Ideen! Wenn jemand einen Link hat, der sich damit genauer befasst, ist das auch in Ordnung, aber ich freue mich ja hier immer auf Erfahrungen von guten Leuten. ;)

Danke im Voraus und ich freue mich wie immer auf die Diskussion!

[Schrompf]

Irgendwie vermisse ich in dem Text einen Hinweis, was Du mit den Unterteilungen eigentlich vor hast. Strahltest? Rigid Body Physics? Sichtbarkeitsbestimmung? Occlusion Detection?

Falls es um Physik geht, vor allem bei Behandlung von Dreiecken, kann man gar nicht weit genug unterteilen. Unterteile den Mesh mit der Methode, die Du für günstig hälst - ich würd einen banalen Octree wählen - und dann unterteile, bis in jedem Endknoten grob ein Dutzend Dreiecke liegen. Dabei solltest Du eher auf maximale Ausgewogenheit zwischen den Unterteilungen achten - ein Ungleichgewicht anzustreben klingt in der Theorie vielleicht gut, aber Du kannst in den üblichen Kollisionsalgorithmen die Symmetrien eh nicht ausnutzen.

Für Modelle mit Skelett empfehle ich einfache Grundkörper pro Bone. Wir nehmen für die Bones mit dünner Geometrie dran - Arme, Beine und so - Kapseln und für den Rest Kugeln oder Quader.

[kimmi]

Dazumahl die Bounding-Volumes ja mit transformiert werden können und man dementsprechend im Update nicht immer die komplette Bounding-Hierarchie aktualisieren muss.

Gruß Kimmi

[Eisflamme]

Das ist aber auch so ne Sache. Das könnte ich machen, wenn das ganze Modell mit Bones belegt wäre, was aber ja nicht so sein muss. Und mehrere Bones können sich ja auf ein Vertex beziehen und lauter so Späße. Wie soll ich da Transformationen an Bones koppeln? Ich find's immer noch schwierig, wie löst man so was?

Achso und das ist für Kollisionserkennung von Modellen.

[Eisflamme]

Ich hab das hier Mal überflogen: http://onlinelibrary.wiley.com/doi/10.1 ... 861.x/full

Denkt ihr, es lohnt sich, da Mal einzuarbeiten? Ich müsste es jetzt wohl noch ein paar Mal lesen, um es komplett zu verstehen (auch wenn wieder alle sagen: wieso, ist doch gaaanz einfach), aber der Ansatz scheint ja ganz gut zu sein.

Ich habe sonst auch noch keine performante Lösung gefunden, die Bone-Animationen auf AABBs/OBBs zu mappen. Ich hatte die Idee, zunächst einen AABB-Tree zu bauen, dann die relevanten Vertices für die Begrenzung zu speichern, diese dann außerhalb des Vertexshaders nochmal zu speichern und durch die Animationen zu transformieren und darauf basierend dann die AABBs zu OBBs zu machen, d.h. einfach zu rotieren, wie man lustig ist. Man könnte auch von Anfang an OBBs nehmen, aber das erhöht den Aufwand dann auch enorm.

Kommentare?

[Chromanoid]

Habe das mal in Algorithmen und Datenstrukturen verschoben. Bin mir nicht sicher ob es vielleicht besser in allg. Fragen der Spieleentwicklung passt (ggf. also bitte weiter verschieben).

[Eisflamme]

Alles klar. :)

Also das Paper hab ich jetzt Mal etwas angeschaut und ich glaube, das ist ein ziemlich genialer Algorithmus. Leider verstehe ich noch nicht besonders viele Details, na ja. Aber ich bleib da dran und implementier den dann auch irgendwann. :) Es kann sich nur um Monate handeln.

[Eisflamme]

Okay, ich habe das Paper jetzt über nen Monat mehrfach gelesen und ich bin einfach zu blöd. Die mathematischen Erklärungen sind mir nicht eingänglich und ich verstehe nicht, wieso es mehrere JointSets gibt und nicht einfach ein JointSet für eine Menge von Vertices bzw. für eine Sphäre. Z.T. habe ich auch das Gefühl, das Paper widerspricht sich und ich weiß nicht, wie genau ich jetzt die Sphäre erweitern soll, obwohl das nicht nach aufwändigem Code aussieht.

Hat jemand irgendwo ne Implementierung von so was rumfliegen oder hat ne Idee, was ich jetzt tun soll? Ich will endlich das blöde Spiel entwickeln und hänge ständig an so komplizierten Dingen wie Shadern, Mesh-Skinning und Sphärenerstellung für 3D-Modelle -.- Ich weiß, ich sollte mich nicht beschweren, ich könnt ja auch ne 3D-Engine nehmen. Aber bis auf diesen Müll hab ich ja alles geschafft.

[pUnkOuter]

Ich würde das auch so machen wie Schrompf und kimmi erklärt haben. Evtl. musst du dann halt noch zusätzliche Bones einfügen, die dann nur für die Kollisionsmeshes verwendet werden.

[Eisflamme]

Na ja, schon klar, dass ich bei Animationen einfach Bones update und die Spheres irgendwie an Bones hefte. Aber ich habe ja nur ein Mapping von Spheres zu Vertices. Die Überlappungen von Bones zu Spheres können ja in allen möglichen Formen vorliegen. Wie löse ich das? Wenn eine Sphere von Vertices so beeinflusst wird, dass vier Bone beeinflussend wirken, ist es nicht so einfach, die Sphere an die Bones anzupassen, da die Vertexpositionen ja auch von der Ausgangsposition abhängt...

Kurz: Ich weiß nicht, wo ich da das Aktualisieren aller einzelnen Vertices "rauskürzen" kann in meiner Aktualisierung, wenn ich mich nur auf die Bones fokussiere.

[Schrompf]

Stelle pro Bone eine Bounding Sphere im lokalen Koordinatensystem des Bones auf. Die Kriterien dafür kannst Du frei wählen, ich empfehle sowas wie "signifikanter Vertex Weight", also z.B. >0.5f. Und dann transformierst Du nur noch die Sphere mit der Bone-Trafo mit.

[Eisflamme]

Okay, damit müsste ich also mein aktuelles Collision-Sphere-Modell ersetzen bzw. das nur noch für Modelle einsetzen, die keine Bones besitzen.

Aber wie stelle ich sicher, dass ich alle Vertices abdecke? Und wenn ich die obere Sphäre ändere, müssen die darunterliegenden ja mitverändert werden (auf Anfrage). Aber zur Zeit habe ich nur absolute Sphere-Koordinaten, sollte ich dann relative nehmen? Dann müsste ich aber bei ner Kollisionsabfrage mit der untersten Sphäre immer die aktuelle absolute Position mitliefern, hmm... So weit richtige Gedanken?

[Schrompf]

Äh... was? Du hast anscheinend einige sehr feste Ansichten, wie das zu funktionieren hat. Was genau Dein bisheriges System ist, weiß ich nicht. Aber wenn es auf "ein DrawCall == eine Kollisionskugel" basiert, ist das in der Tat überarbeitungswürdig. Für ne sinnvolle Ragdoll-Physik wirst Du mindestens eine Kugel pro Bone brauchen. Eigentlich besser zwei oder andere Grundkörper - die von Dir verwendete Physikbibliothek wird mindestens noch Kapseln und Quader anbieten, mit denen man einen Körper besser approximieren kann. Kapseln entlang der Extremitäten, Quader an den Rumpf-Bones.

Das mit dem "Drüber und Drunter und Abdecken" habe ich auch nicht verstanden. Bones bilden eine Hierarchie. Wenn sich einer bewegt, bewegen sich natürlich alle untergeordneten mit. Deine Update-Funktion muss also verständlicherweise rekursiv arbeiten. Und vergiss die "Abdeckung". Du benutzt Kugeln. Die sind eh nur sehr ungenau - wenn da ein paar Vertizes am Rand nicht von der Kugel erfasst werden, tut das auch nicht weh.

[Eisflamme]

Also zur Zeit erstelle ich einen Bounding-Sphere-Tree entsprechend dem obigen Paper für alle Vertices. D.h. ich bilde erst eine Bounding-Sphere, die alle Vertices abdeckt. Dann mache ich je nachdem, wie ich die Vertices mit bester Gleichverteilung hinbekomme, entlang einer der drei Achsenflächen (xy, yz, xz). Die darunter liegenden Vertices umfasse ich mit wiederum einer Sphäre. Wenn die Tochtersphäre fast den gleichen Radius und Position wie die Muttersphäre hat, wird die Tochtersphäre einfach entfernt und deren Kinder der Muttersphäre angehängt, sodass das nachher kein Binärbaum mehr ist. Das System ist schnell und sehr genau.

So weit funktioniert das wunderbar. Entsprechend obigem Paper kann man durch ein Mapping von Bones zu den Sphären irgendwie ein performantes Live-Update anbieten, aber das verstehe ich halt einfach nicht.

Dein Ansatz funktioniert natürlich nur für Bone-Modelle, aber okay, das passt mir. Also erstelle ich pro Bone eine Sphere. Da verstehe ich bereits nicht, wie. Ich weiß, welche Vertices vom Bone beeinflusst werden. Natürlich gibt es jetzt Überschneidungen, die könnte ich aber ignorieren. Problem ist jetzt, dass ich natürlich mehr Genauigkeit will, also muss diese Sphäre weiter untergliedern (gemäß meines obigen Verfahrens der Ebenenschnitte z.B.).

Und diese darunter liegenden Sphären muss ich dann aber auch transformieren. Und jetzt habe ich das Problem, dass ich nicht weiß, wie. Die haben eine bestimmte Orientierung innerhalb der Muttersphäre und bei Drehungen muss das korrekt gedreht werden. Also muss ich relative Koordinaten speichern, die aber auch die Drehung mit betrachten. Und das bereitet mir gerade Kopfzerbrechen.

[Schrompf]

Bei Kugeln brauchst Du nur den Mittelpunkt transformieren. Kugeln sind doch rotationssymetrisch - die kannst Du drehen, wie Du willst, die sind immer rund :-)

[Eisflamme]

Ja, ich weiß. Aber wenn Kugel 1 die Kugeln 2 und 3 enthält und sich Kugel 1 dreht, bewegen sich Kugeln 2 und 3 ja innerhalb der Kugel 1.

[Schrompf]

Und was ist dann das Problem? Wenn Du das weißt, dann tu's doch.

[Eisflamme]

Ich hab das Gefühl, ich vergesse wieder tausend Dinge, durch die bedingt ich nachher wieder alles wegwerfen kann, wenn ich ein paar Stunden rumgefrickelt hab. -.-

[Top-OR]

Hallo Eisflamme,

ich habe diesen Thread bisher nur überflogen, aber mir kommt eine Frage in den Kopf: Brauchst du diese genaue Auflösung der Boundings bei deinen Modellen WIRKLICH, oder ist das nur ein wäre-schön Feature?

Ich meine, Schrompfs Ansatz mit den geschachtelten Sphären finde ich im ersten Moment nicht sonderlich verwirrend, aber vielleicht hab ich das auch noch nicht bis zum Ende durchdacht.
Ich kenne zumindest das Gefühl, dass das "Problem größer ist als der eigene Kopf". Zurück zum Thema:

Sicher sind so genaue Boundings für Modelle cool. Da kann man für Collision oder Picking (ich sag nur "HEADSHOOOOOT") schöne Dinge machen.
Ich weiß ja nicht, auf was für ne Art Spiel du dein System trimmst, aber würde es nicht vielleicht auch Ausreichen, wenn du pro Objekt nen passend anliegenden Ellipsoiden (oder ne andere Form) nimmst?

Sicher kannst du dann nicht einzeln subselekten, aber es reicht, um dein ganzes Model (den Player oder was weiss ich) gegen andere Objekte zu testen, ohne wahnsinnig zu werden.
So coole Geschichten wie die riesigen Painkiller-Bosse (ich denke da an den Giganten) kannste dann zwar nicht machen, aber vielleicht brauchst du das ja auch nicht?!? Und du wirst NICHT wahnsinnig. ;-)

Beste Grüße,
Top-OR

[Eisflamme]

Es ist aber performant umsetzbar. Dann will ich das auch haben. Hat ja keine Nachteile. Und etwas nicht einzubauen, weil ich zu blöd bin, find ich doof.

[Top-OR]

Kann ich natürlich auch verstehen...

[Eisflamme]

Jetzt hab ich aber Mal überlegt. Schrompfs Methode klappt ja mit großer Genauigkeit nicht mehr, weil mehrere Vertices von verschiedenen Bones beeinflusst werden. Wenn man je Bone eine Sphere macht und die Spheres durch die Bones abändert, wird nicht bedacht, dass die darin liegenden Vertices ja nicht nur durch diesen einen Bone geändert werden. Also ändern sich die Spheres nicht korrekt und das ist nur eine grobe Annäherungslösung.

In dem Paper wird nämlich eine genaue Möglichkeit beschrieben.

[pUnkOuter]

Wenn ein Vertex von mehreren Bones bewegt wird, ist seine resultierende Verschiebung meist aber nur sehr klein, weshalb die "grobe Annäherungslösung" in den allermeisten Fällen eben doch genügt.

[Eisflamme]

Das ist spätestens dann knapp, wenn ich Gewichte von 0,4, 0,3, 0,2, 0,1 habe...

Ich würde daher lieber über das Paper gehen, da ich ja auch genaue Auswertungen so machen würde.

Schrompf: Nutzt ihr wirklich nur die beschriebene Methode? Sind die resultierenden Ungenauigkeiten so klein, dass es echt egal ist, oder nutzt ihr noch einen weiteren Trick oder braucht einfach nicht so viel Genauigkeit?

[Top-OR]

Ich denke, dass pUnkOuter Recht hat. Ich glaube, dass die Beeinflussung durch mehrere Bones meist zu vernachlässigen ist.

Ich denke (mal so übern Daumen; ich bitte um Korrektur, falls ich Brei rede), dass das mit den multiplen Boneweights pro Vertex auch nur für die Vertices an den Verbindungszonen "von einem Bone zum Anderen" interessant ist. Also z.B. am Hals oder Arm-Ansatz. Wenn du da nicht wichten würdest, würdest du "zu unrealistische" Verformungen sehen. Daher wichtet man schön.

Aber wenn du es dir mal plastisch vorstellst, wird z.B. ein "normaler Vertex im Armbereich" nur von den Arm-Bones beeinflusst werden und nicht vom linken Zeh. Selbst wenn er ein Stück Schulter-Weight mitbekommt, wird der Vertex nicht plötzlich am Bein kleben.

Ums kurz zu fassen: Auch ich glaube(!), dass diese Abweichungen bei "normalen" Bonemodellen zu vernachlässigen sind. Natürlich kann man welche konstruieren, wo es "schief" geht.

[Schrompf]

Schrompf: Nutzt ihr wirklich nur die beschriebene Methode? Sind die resultierenden Ungenauigkeiten so klein, dass es echt egal ist, oder nutzt ihr noch einen weiteren Trick oder braucht einfach nicht so viel Genauigkeit?

Genauigkeit wofür denn? Treffertests für Strahlenwaffen? Das sollte reichen. Kollisionstest für bewegte Wesen? Da reicht eine banale stehende Kapsel. RagDoll-Physik? Dafür reicht das Kugelsystem, schlimmstenfalls liegt der Charakter dann halt hier und da fünf Zentimeter über dem Terrain. Das sieht man üblicherweise nichtmal, und für die üblichen Schatten- oder SSAO-techniken ist das sogar von Vorteil.

Wir machen das aktuell noch recht schlicht: eine stehende Kapsel für die Bewegungskollision, für Strahltest benutzen wir aktuell OBBs um alle beeinflusten Vertizes pro Bone. Diese OBBs sind teilweise deutlich zu groß, aber das war bisher kein Problem. Wir sind gerade dabei, die Physik aufzubohren. In dem Zug soll dann auch bessere Kollision für geriggte Modelle kommen - wahrscheinlich Kapseln für die Extremitäten und Quader oder Kugelgruppen für den Rumpf. Das sollte dann auch für alle Arten von Kollisionstests reichen. Pfeile und so. Schwerttreffer werden eh nur anhand des Charakter Controllers bestimmt.

[Chromanoid]

Die Unreal Engine macht das ganze übrigens auch "nur" mit groben Bounding Volumes (bei Ragdoll Effekten). Beim Rest wird zumindest in UT der Spieler zu einem Zylinder reduziert...

[Eisflamme]

Na ja, ich würde beispielsweise gerne recht genau darstellen, wenn der Zwerg mit der Axt einen anderen Charakter trifft. Das sollte schon genauer als eine Kapsel sein, sonst ist das doch wirklich ziemlich nervig. Mir geht es um mit dem Modell verflochtene Waffen. Da soll auf keinen Fall eine Kollision gemeldet werden, wenn die schmale Hüfte des anderen Modells noch gar nicht berührt wurde, dafür aber irgendein Zylinder.

[joggel]

Hab leider keine Ahnung mit Models und interaktionen dieser mit anderen, aber ich denke da
dass dies ausreichein sollte.
Ich meine, meist sind doch solche Attack-Actions eine Animation. ZB, der Zwerg schwinkt die Axt von rechts oben nach links unten, wenn der Gegner dabei in der Bahn ist, wird dieser getroffen...
Wenn man aber zB eine Fechtsimualtion machen möchte, da wäre das vlt. ungenau...

[Top-OR]

Na ja, ich würde beispielsweise gerne recht genau darstellen, wenn der Zwerg mit der Axt einen anderen Charakter trifft. Das sollte schon genauer als eine Kapsel sein, sonst ist das doch wirklich ziemlich nervig. Mir geht es um mit dem Modell verflochtene Waffen. Da soll auf keinen Fall eine Kollision gemeldet werden, wenn die schmale Hüfte des anderen Modells noch gar nicht berührt wurde, dafür aber irgendein Zylinder.

Hmm, keene Ahnung :shock: : Ich durchschaue noch nicht so ganz warum/wie du was machen willst, aber das klingt irgendwie sehr fragil ...
Ich meine, dass willst du doch: Auf Kollision checken, wenn die Axt den Charakter am Bein berührt?!?!?
Dafür reicht doch ein Box-Modell (oder eben Sphären-Modell) wie auf Chromanoids Unreal-Bild, oder nicht?

Wie machen das denn andere Spiele?