Frage zu Collision Detection Primitives
-
Hallo zusammen
Ich lese gerade das Buch Realtime Collision Detection von Christer Erricson und bin bei Kapiel 4 BoundingVolumes.Also in meiner Engine mache ich es so: jedes Objekt hat eine BoundingSphere sowie einer beliebigen Anzahl von Planes, welche den Raum in zwei Hälften Teilen. Nun mache ich für jedes Objekt zuerst die äusserst günstige Sphere Sphere intersection test und wenn dieser Positiv ausfällt, transformiere ich sämtliche Planes von beiden betroffenen Objekten vom Model in den Worldspace und fange an, diese zu überprüfen (Ich weiss, ist vielleicht nicht gerade der Geniestreich, aus diesem Grund lese ich ja nun auch das erwähnte Buch). Trotzdem fange ich lang an, mich zu fragen, ob ich es vielleicht doch gar nicht soo schlecht mache. Folgendes sind meine Überlegungen:
BoundingSpheres: Extrem billig, aber in den meisten Fällen auch extrem ungenau. Für das Ausschliessen der offensichtlichsten 95% der Fälle aber IMHO am besten geeignet.
AABB: Ich muss den VertexBuffer locken, die Daten von der Grafikkarte zurückholen (oder eine Kopie im Hauptmemory haben) und anschliessend abertausende von Vertices durchlaufen, um nach einer Rotation die AABB neu zu berechnen (natürlich nur, wenn der BS - BS Test angeschlagen hat), zudem ist das Resultat dann meistens immer noch äusserst ungenau.
OBB: Immerhin muss ich diese nicht neu berechnen sondern kann sie einfach mit Hilfe einer verketteten Matrixtransformation vom Model in den Worldspace transformieren, dafür ist der eigentliche Kollisionstest deutlich teurer als bei AABB. Nachteil, vielleicht immer noch sehr ungenau, erfordert genau wie bei AABB eine ganze Hierarchie.
kDOPS: Sind verhältnismässig genau, aber genau wie bei den AABB müssen diese immer wieder neu berechnet werden (VertexBuffer sperren usw., abertausende von Punkten durchlaufen), wenn entsprechende Objekt rotiert wurde -> sehr teuer....
Meine Variante mit Halfspace Planes: Können ebenfalls einfach transformiert werden und mit Hilfe von SSE kann ich immer jeweils 4 Planes gleichzeitig überprüfen...
Allerdings, und das macht mich nun doch etwas stuzig, wird meine Lösung in dem Buch überhaupt nicht erwähnt und da ich bekanntlich kein Genie bin, welches nun einfach so DIIEE Lösung gefunden hat, nach der all die Professoren ein Leben lang gesucht haben, frage ich mich doch, ob meine Vorgehensweise vielleicht gravierende Nachteile mit sich bringt, die mir noch nicht aufgefallen sind, welche diese Technik jedoch disqualifizieren?
Mfg Samuel
-
Ishildur schrieb:
Also in meiner Engine mache ich es so: jedes Objekt hat eine BoundingSphere sowie einer beliebigen Anzahl von Planes, welche den Raum in zwei Hälften Teilen. Nun mache ich für jedes Objekt zuerst die äusserst günstige Sphere Sphere intersection test und wenn dieser Positiv ausfällt, transformiere ich sämtliche Planes von beiden betroffenen Objekten vom Model in den Worldspace und fange an, diese zu überprüfen (Ich weiss, ist vielleicht nicht gerade der Geniestreich, aus diesem Grund lese ich ja nun auch das erwähnte Buch). Trotzdem fange ich lang an, mich zu fragen, ob ich es vielleicht doch gar nicht soo schlecht mache.
Klingt vernünftig, ist eigentlich der ganz normale Ansatz sich vom Groben ins Feine vorzuarbeiten. Schonmal dran gedacht nicht alle Ebenen in den Worldspace sondern nur die Ebenen vom einem Modell in den Objectspace des andren zu transformieren?
Ishildur schrieb:
AABB: Ich muss den VertexBuffer locken, die Daten von der Grafikkarte zurückholen (oder eine Kopie im Hauptmemory haben) und anschliessend abertausende von Vertices durchlaufen [...]
Naja normalerweise würde man sich die entsprechenden Daten des Modells im RAM halten. Es ist z.B. auch ganz üblich eine Version des Modells mit reduzierter Zahl an Vertices/Polygonen für Kollision etc. zu verwenden. Und wie du schon erkannt hast ist es in so einem Fall sicherlich sehr viel schlauer (effizienter und genauer) mit OBBs zu arbeiten. Man kann ein Modell z.B. auch mit mehreren OBBs umgeben die das Modell genauer approximieren. Ich könnte mir da sogar eine Hierarchie vorstellen, ganz oben eine OBB und dann mit jedem Level mehr OBBs die das Modell genauer approximieren. Für genaue Objekt vs. Objekt Tests macht es vielleicht Sinn das Modell in einen Octree oder BSP-Tree o.ä. zu packen um nur eine minimale Anzahl an Dreieck vs. Dreieck Tests zu haben.
Und um am Ende dann auch die Objekt vs. Objekt Tests zu minimieren wird man BVHs und/oder irgendein Raumaufteilungsverfahren (Quad-/Octree, BSP-Tree, kd-Tree, ...) verwenden.
-
Schonmal dran gedacht nicht alle Ebenen in den Worldspace sondern nur die Ebenen vom einem Modell in den Objectspace des andren zu transformieren?
Habe ich, allerdings bin ich zum Schluss gekommen, dass das Erstellen einer Matrix Inversen plus eine Matrizenmultiplikation am Ende langsamer ist als 2 Matrizenmultiplikationen. Jedenfalls mit SSE
-
Ich würde meinen das hängt extrem stark davon ab wieviele Ebenen du hast
-
Ishildur schrieb:
dass das Erstellen einer Matrix Inversen plus eine Matrizenmultiplikation am Ende langsamer ist als 2 Matrizenmultiplikationen.
Die Inverse hat man doch meisstens schon.
Wenn Du beispielsweise die Positionen der Lichtquellen in den Objektraum bringst spart Dir das *pro Normale* eine Matrixmultiplikation...
Wenn Deine Matrix orthonormal ist, braucht's sogar nur die Transponierte.
-
@dot
Ich kann dir gerade nicht folgen, wie wieso hängt das von der Anzahl ab?@hellihjb
Ich beleuchte mit Normalmapping im Objektspace, da muss ich ohnehin eine Matrixmultiplikation pro Pixel machen. Sowie eine Transformation der Basisvektoren des Tangenspace vom Model in den Worldspace.
-
Ishildur schrieb:
@dot
Ich kann dir gerade nicht folgen, wie wieso hängt das von der Anzahl ab?Je mehr Ebenen desto mehr Matritzenmultiplikationen sparst du dir da du dann ja nur die Ebenen von einem der beiden Objekte transformieren musst...
Ishildur schrieb:
Ich beleuchte mit Normalmapping im Objektspace, da muss ich ohnehin eine Matrixmultiplikation pro Pixel machen. Sowie eine Transformation der Basisvektoren des Tangenspace vom Model in den Worldspace.
Du meinst wohl Normalmapping im Worldspace!?
-
Je mehr Ebenen desto mehr Matritzenmultiplikationen sparst du dir da du dann ja nur die Ebenen von einem der beiden Objekte transformieren musst...
Ja schon, aber um so mehr Matrizeninversionen muss ich berechnen. Die Frage beschränkt sich IMHO auf "Was ist schneller, 1x Matrizenmultiplikation od 1x Matrizeninversion?
Du meinst wohl Normalmapping im Worldspace!?
Hehe, ja natürlich. Ich habe übrigens auch die Beleuchtung im Tangentspace ausprobiert, aber so ab. ca. 5 dynamischen Lichtern, war plötzlich Worlspace Beleuchtung schneller als Tangentspace, auch wenn überall das Gegenteil steht. Kommt aber halt auch sehr auf die Anzahl Vertices des entsprechenden Modells an und wieviel man vom entsprechenden Objekt gerade sieht
-
Ishildur schrieb:
Ja schon, aber um so mehr Matrizeninversionen muss ich berechnen. Die Frage beschränkt sich IMHO auf "Was ist schneller, 1x Matrizenmultiplikation od 1x Matrizeninversion?
Huh? Du brauchst doch nur eine Matritzeninversion pro Objekt und die Multiplikation brauchst du so oder so!? Und wie hellihjb schon sagte brauchst du die inverse Object to World Matrix sehr wahrscheinlich sowieso auch für andere Dinge.
Die Frage ist also was ist schneller:- Alle Ebenen von Objekt1 -> Worldspace + Alle Ebenen von Objekt2 -> Worldspace
oder
- (1x Matritzeninversion) + Alle Ebenen von Objekt1 -> Objekt2
-
Huh? Du brauchst doch nur eine Matritzeninversion pro Objekt
Ah LORD, jtzt verstehe ich was du meinst, natürlich!
-
Ich habe noch eine Frage. In dem erwähnten Buch steht zwar so ziemlich alles, was man über die Kollisionserkennung wissen muss, allerdings nur wenn es darum geht, festzustellen, ob eine Kollision stattgefunden hat oder nicht. Ich erweitere gerade auch noch die Physikengine und hierfür benötige ich das Zentrum des Schnittvolumens zweier Proxykörper. Weiss vielleicht jemand von euch, wo ich Literatur zu diesem Thema finden kann?
Gruss Samuel
-
Ein interessantes Stichwort ist vielleicht "Closest Point Computations"...
