Octree Division

Ich habe einen Octree mit einem hohen Polykaninchen und einer 12-Polygon-Plattform.

Der Deal ist das. Sie schießen einen Strahl auf das Kaninchen. Er weicht natürlich aus (oder du vermisst).

Der gelbe Strahl ist dein Todeslaser.

Die "Kandidaten" -Dreiecke, die aufgrund der von Ihnen getroffenen Teile des Oktrees ausgewählt werden, werden in lila angezeigt.

Sie haben also eindeutig dieses Striping, das auftritt, weil der Wurzelknoten getroffen wurde. Am Ende haben Sie alle Polys im Wurzelknoten getestet. Und die Polys, die sich an den Rändern der Octree-Unterteilung befinden, landen im Wurzelknoten mit dem von mir verwendeten Unterteilungsalgorithmus.

Daher möchte ich die Anzahl der Polys im Stammknoten reduzieren.

Wenn ich den Hasen nur in die Ecke bewege,

Mit dem Hasen in der Ecke Raytracing dauert die gesamte Szene 1/3 der Zeit (35s vs 95s, wenn der Hase in der Mitte ist). Ich glaube, das liegt daran, dass sich weniger Dreiecke des Hasen in der Wurzel befinden und Treffer mit nur Octree-Wurzeln weniger Polygone prüfen.

Ich untersuche Möglichkeiten zur Leistungsverbesserung. Grundsätzlich schieben Sie die Tris so weit wie möglich nach unten, so dass sich die Objekte meist in den Blättern befinden.

Ich habe dies naiv versucht und diesen Unterteilungsalgorithmus verwendet, den ich erfunden habe:

split root into 8 CANDIDATE CHILDREN
foreach TRI in root:
  foreach of the 8 CANDIDATE CHILDREN
    if the CANDIDATE CHILD partially contains TRI (at least one vertex of TRI)
      add TRI to CANDIDATE CHILD
CLEAR tris in root

Dadurch werden Dreiecke entlang der Hierarchie in Blattknoten verschoben. Aber ich bekomme Löcher aus bestimmten Winkeln mit seltsamen Fehlmustern:

(erwartet)

Löcher aus einem Winkel:

gleiche Szene, anderer Blickwinkel:

Ich denke, das liegt daran, dass ich die Wurzel räume. (Denn wenn ich die Wurzel nicht lösche, funktioniert Raytracing in allen Winkeln korrekt.)

Habe ich die Polygone richtig auf den Baum "geschoben"? Kann jemand erraten, warum ich Löcher habe?

Wie verbessern Sie die Leistung Ihres Octree?

Muss ich die Dreiecke teilen? Ich versuche das zu vermeiden, damit ich nicht immer dünnere Dreiecke bekomme / die Szenengeometrie nicht mehr multipliziere, als ich brauche.

Mir ist auch bewusst, dass KD-Bäume und dass sie Octrees übertreffen sollten, aber sie erfordern auch Poly Splitting. Ich suche wirklich nach Möglichkeiten, mein Octree hier zu verbessern.

Ich verstehe jetzt, warum ich Löcher bekomme. Ich verwende ein schlechtes AABB-Dreieck-Teileinschlussschema: Ein AABB "enthielt teilweise" ein Dreieck, wenn der AABB mindestens einen Scheitelpunkt des Dreiecks enthielt .

E sind "leer", gemäß dem schlechten Erkennungsschema "Dreieck teilweise in AABB".

Ich denke, dies bedeutet, dass Sie die Dreiecke teilen müssen , wenn Sie alles auf Blattknoten drücken möchten .