Abstand zwischen Kugel und Polygon

Dein Thema passt einfach in kein Forum? Dann probiers mal hier.
N¤X
Beiträge: 77
Registriert: 21. September 2009 12:24

Beitrag von N¤X »

Nochmal ein bisschen zusammenfassen.

Kamera: Punkt vs. Volumen
Ob es einen Geschwindigkeitsunterschied macht weiß ich grad nicht, aber Volumenlose Objekte miteinander auf Schnitt zu überprüfen ist immer schwierig, vor allem wenn ein Objekt davon auch noch flächenlos ist. Entweder du merkst dir für die Flächen auf welcher Seite die Kamera ist und wenn das Wechselt schaust du, ob die Kamera durch das Dreieck oder dran vorbei gegangen ist (dann wär ein BSP-Tree aber praktischer) oder du gibst der Kamera halt ein Volumen und testest auf Schnitt (Dann wär meiner Meinung nach ne BVH geeigneter). Sind unterschiedliche Ansätze, musst dich halt für einen Entscheiden...
(Octrees sind glaub am geeignetsten um möglichst uniform verteilte Punkte zu speichern, aber generell kann man da alles für alles Benutzen.)

Kugeln vs. AABBs
Kugeln sind für die Kollisionsberechnung am schnellsten, dafür sind sie ziemlich aufwändig zu erstellen (vor allem für komplexere Gebilde wie z.B. BVHs) und schmiegen sich denkbar ungünstig an Flächige Primitive an, was dir wieder mehr false positives und somit mehr aufwändige Schnitttests bringt.
AABBs (Quader) haben keinen sonderlich großen Kollisions-Berechnungs-Aufwand, auch wenn sie 6 Flächen haben. Da sie Achsenorientiert sind reicht es einfach alle drei Dimensionen einzeln auf Überlapp zu testen und nur wenn alle drei Tests true liefern schneiden sich die Boxen auch wirklich. Die Komplexität mit den 6 Flächen hast du nur, wenn du OOBs benutzt. Auch AABBs schmiegen sich nicht immer gut an die Primitive an, aber im Schnitt wenigstens besser als Kugeln, und sie sind sehr einfach zu erstellen.

"Ich meine ob ich mehrere Polygone in einer Boundingbox zusammenfassen sollte"
Dein Ziel zur Optimierung ist die Dreiecke in einer Baumstruktur abzulegen, wie z.B. in deinem Quadtree. Dein Wurzelknoten repräsentiert den Kompletten Raum und enthält somit noch alle Dreiecke (Damit sind sie zusammengefasst, die grenzen des Knotens bilden so zu sagen eine AABB), dessen Kinder repräsentieren jeweils ein Achtel des Gesamtraums und enthalten nur noch die entsprechenden Kinder (Achtung: Dreiecke die in zwei Kinder ragen müssen gesplittet und aufgeteilt werden!) etc..
Was du tust für deine Kollisionsberechnung ist: Du gehst vom Wurzelknoten aus immer in das Kind in dem deine Kamera sich gerade befindet, bis du in einem Blatt ankommst. Optimalerweise ist dieses Blatt Leer (-> keine Kollision) oder du musst alle Dreiecke aus dem Blatt einzeln auf Kollision prüfen (Deshalb macht man den Baum normalerweise so tief, dass nurnoch ein Primitiv pro Blatt übrig ist, aber mit nem Octree geht das nicht so gut...). Dadurch dass du dich jeweils für ein Kind entschieden hast hast du dir durch eine "Kollisionsprüfung" (Die Kamera kollidiert so zu sagen mit dem Unterraum in dem sie sich befindet) die Kollisionsprüfungen mit 7/8 der verbleibenden Dreiecke gespart. Also es lohnt sich schon, aber in unterster Ebene sollte jedes Objekt dann seine eigene Box haben ;)
mfg N¤X
superkarnickel
Beiträge: 13
Registriert: 17. Februar 2010 18:51

Beitrag von superkarnickel »

Vielen Dank.
Dann werde ich höchstwahrscheinlich Quader (gegebenenfalls natürlich auch andere Objekte mit Volumen) als Boundingboxes benutzen.
Da sie Achsenorientiert sind reicht es einfach alle drei Dimensionen einzeln auf Überlapp zu testen
Das ist wirklich ein Vielfaches einfacher. Da bin ich nicht drauf gekommen. Danke :D.

Grüße,
superkarnickel
Antworten