BVH --> Annäherung an O(n) ?

TS++

Hallo zusammen!

Ich hab mir gerade mal ein paar Gedanken zur Effizienz von Bounding Volume Hierarchien gemacht und den Arbeitsaufwand T(n) allgemeingültig formuliert.
Dabei ist mir interessanterweise folgendes aufgefallen:

Jedem wird wohl klar sein, dass man sich mit einer Steigerung des Verzweigungsgrades k einer BVH stufenweise in Richtung linearen Aufwand bewegt. Das war auch mir schon bereits vor meiner Analyse klar. Jedoch bin ich bisher davon ausgegangen, dass ich relativ grosse Werte für k ansetzen müsste, um zu einer linearen Komplexitätsklasse zu kommen (also: O(n))
Das scheint offensichtlich nicht so zu sein!
Einen eindeutigen logarithmischen Verlauf des Aufwands T(n) erkenne ich nur für k=2, also für BSPs. Bereits für k=4 ähnelt der Graf für T(n) langfristig schon eher einer linearen Funktion. Also für viel niedrigere Werte für k, als ich gedacht hätte!

Da stellt sich mir natürlich die Frage:
Warum sollte ich denn dann eigentlich einen Octree verwenden, wenn der zeitliche Aufwand zur Durcharbeitung des Baumes mit einer Vergrößerung meiner Szenerie nahezu linear wächst?

Ach und ich bin auf einen weiteren interessanten Punkt gestossen:

Offensichtlich hat die Tatsache ob eine BVH ausbalanciert ist oder nicht, keinen direkten Einfluss auf die Komplexitätsklasse. Im Schnitt (also im average case) ergibt sich sowohl für eine ausbalancierte BVH als auch für eine unausbalancierte BVH die Klasse O(log n).
Den einzigen Unterschied, den ich zwischen ausbalancierten BVH und unausbalancierten BVH feststellen konnte ist die Tatsache, dass ausbalancierte BVH auch kurzfristig stabil arbeiten. Unausbalancierte BVH arbeiten kurzfristig mit hoher Wahrscheinlichkeit instabil. D.h.: die Verwerfungsraten von BoundingVolumes schwanken kurzfristig. Bei längerem Testen pendelt sich aber eine konstante Rate ein. Man muss den ViewFrustrum nur lange genug durch den Baum bewegen.

Was sagt Ihr dazu?

Grüße,
TS++

TS++

Ich versuch meine Frage etwas umzuformulieren:

Welche Gründe sprechen für den Einsatz von Quad- bzw. OcTrees?
Was die Suchgeschwindigkeit anbelangt, so hat doch der binäre Baum die Nase vorn!

Grüße,
TS++

TGGC

Deine empirischen Messungen sind offensichtlich nicht repräsentativ oder gar falsch/ falsch interpretiert.

Bye, TGGC \-/

TS++

Wie sollte denn der Verlauf von T(n) für einen OcTree aussehen?

Über einen Grad k der Größe 8 bewege ich mich doch definitiv ein Stück weg vom logarithmischen hin zum linearen Aufwand. Sicher, der Logarithmus ist für kleinere Werte für n noch erkennbar. Jedoch was den Verlauf in Richtung +Unendlich anbelangt, so kann T(n) leichter durch eine Gerade als durch den Logarithmus approximiert werden. Muss doch auch so sein. Bei der Traversierung einer BVH bin ich auf jeder Ebene dazu gezwungen jeden BV einem Kollisionstest zu unterziehen. Das wären beim BSP pro Ebene nur 2 Stück. Beim OcTree dann eben jeweils 8.

Ich spreche von einem kontinuierlichen Übergang von O(log n) zu O(n) mit steigendem k.

Was ist denn daran falsch?

Grüße,
TS++

0x00000001

Deine Überlegungen ergeben Sinn Ich habe mich bereits für einen Octree entschieden, aber nachdem ich Deinen Text gelesen habe fühle ich mich nicht mehr wohl damit.

Ein Octree ist "vom Gefühl her" die beste Raumaufteilung, weil er alle 3 Dimensionen jeweils halbiert. Das wird wohl auch der Grund sein, warum ihn so viele benutzen (inklusive mir). Bei so einer Aufwandsanalyse sieht er dagegen schon etwas schlechter als ein Binärbaum aus.

Ein Vorteil von Octrees, der mir spontan einfallen würde:
Die Wahrscheinlichkeit, dass ein Ast/Blatt leer ist und somit wegfällt ist etwas höher als beim Binärbaum, da er kleinere Bereiche des Levels abdeckt.

Bei Spielen sind die Bäume ja nicht allzu tief, trotzdem werde ich meinen Octabaum(?) bei Gelegenheit mal in einen Binärbaum umändern. Das ist in meinem Fall nicht sonderlich kompliziert.

rapso

Die geschwindigkeit von sowas hat mit der theorie nicht sonderlich viel zu tun. wichtig ist z.b. wie die nodes im speicherliegen, wenn ihr hundertausend nodes habt und ihr springt mit BSP durch den speicher, ist das culling an sich und die aufteilung der scene egal, denn die meißte zeit wird die cpu warten bis sie die daten vom ram hoch bekommt, eventuell, wenn die scene wirklich gross ist, muss die cpu sogar warten bis die platte etwas nachschiebt. Deswegen kann ein Octtree oftmals schneller sein, denn dort sind die daten für die 8 cubes hintereinander im ram, wenn man dafür an 6stellen im ram im BSP springen muss, gewinnt meißt der Octree.

NVidia schlägt in einem ihrer paper AABB-Trees vor, weil sie gutes "volume fitting" haben und trotzdem compakt im speicher liegen können (mit eigenem Memory management). Ich nutze auch gerne SphereTrees, für Animierte Objekte die rotieren z.b. Asteoriden, teile von Raumstationen, das Rohr eines Panzers... muss man die Hierarchy vom CullingTree beim updateScene nicht verändern.

man muss eben immer sein anwendungsgebiet wissen. Kriterien sind:
-Anzahl objekte
-Dynamic der Objekte und ihre Art (z.b. nur rotation, langsamme bewegung oder schnelles auftauchen und wieder verschwinden)
-verhältniss von Dynamischen zu statischen objekten
-Ihre Dichte (z.b. Vollgestelles zimmer <->weltraum mit auseinander liegenden Objekten)
-Relation von der Anzahl der sichtbaren Objekte zur gesammtanzahl.
-Kosten eines Objektes beim Rendern (z.b. ob ein 2instructin shader vorhanden ist oder einer mit 64 instructions)
-...

und je nachdem was gerade wichtig ist, kann man zwischen einer linearen listen mit "Sweep and Prune" und K-Tress mit/ohne PVS wählen.

rapso->greets();

TGGC

TS++ schrieb:

Ich spreche von einem kontinuierlichen Übergang von O(log n) zu O(n) mit steigendem k.

Was ist denn daran falsch?

Das ist eben völliger Quatsch, es gibt da keinen "Übergang". Alles O(log n) ist auch O(n) aber nicht alles was O(n) ist auch O(log n). "Ein bisschen O(log n)" gibt es nicht! Frage einfach mal im Matheforum nach, die beweisen dir das sicher gern.

Bye, TGGC \-/

TS++

Morgen!

Bitte tipp mal folgende Formel in, meinetwegen Excel, ein und lass dir die Grafen für k = 2,4,8 und 16 anzeigen:

c = Konstante für den Kollisionstest (setze diese z.B. auf 1)
n = Gesamtproblemmmenge
k = Grad der BVH

(
                |  c * ( ldn +1 )                  ;  k = 2
                |
Taverage(n) =  <            (1 + logk n)
                |        (k/2)            -  1 
                |  2c * ------------------------   ;  sonst 
                (               k - 2

Wie würdest Du die Grafen interpretieren?
Vielleicht sind meine Schlussfolgerungen ja nur fehlerhaft!

Grüße,
TS++

TS++

P.S.:
n ist für mich die Anzahl an BVs
--> wächst die Szenerie, so muss auch die Präzision der BVH zunehmen!!!

Grüße,
TS++

TGGC

Ich habe es mal eingetippt. Eindeutig nicht linear. Für jedes k lies sich ein n finden, bei dem Taverage(n) << n war. Aber das war klar.

Bye, TGGC \-/

b7f7

irgendwie versteh ich hier was nicht.
also was für einen Aufwand meinst du?
wenn ich ein OcTree habe Teste ich stufenweise
in der ersten Stufe habe ich ur noch 1/8 mögliche kandidaten.
in der zweiten 1/8/8
das wird nur dan linear wen der Tree degeneriert ist und dan ist es erst O(n).
bei einer räumlich gleichverteilten Punktmenge n->infinity ist das suchen O(log n).

TS++

Servus!

Der Aufwand, den ich meine, ist der Arbeitsaufwand (demzufolge der zeitl. Aufwand) der betrieben werden muss um eine BVH im Rahmen des Cullings vollständig durchzuarbeiten, also die einzelnen BVs mit den entsprechenden Flags auszuzeichnen.

Ich gehe hierbei von folgendem Ansatz aus:

Referenzbaum: geordneter vollständiger Mehrwegbaum

T(n) = (W1+W2) * c + W3 * ( c + k * T((n-1)/k) )
T(1) = (W1+W2) * c + W3 * c

wobei gilt:
c : Konstante für den Kollisionstest
W1 : Wahrscheinlichkeit, dass BV nicht sichtbar ist
W2 : Wahrscheinlichkeit, dass BV sichtbar ist
W3 : Wahrscheinlichkeit, dass BV den ViewFrustrum schneidet

mit W1 + W2 = 1 - W3 ergibt sich:

T(n) = c + W3 * k * T((n-1)/k)
T(1) = c

Die Schnittwahrscheinlichkeit W3 könnte man nun für individuelle BVH ermitteln oder evtl. sogar einzelnen BVs eigene Schnittwahrscheinlichkeiten zuordnen.
Das muss aber für eine allgemeine Analyse nicht sein!
Ich setze hier z.B. für den average case eine Schnittwahrscheinlichkeit von 50% an (in der Realität auftreten wird ja ein Gemisch aus 0, 0.5 und 1)

Das führt zu der bereits erwähnten Formel!

Grüße,
TS++

TS++

TGGC schrieb:

Ich habe es mal eingetippt. Eindeutig nicht linear. Für jedes k lies sich ein n finden, bei dem Taverage(n) << n war. Aber das war klar.

T(n) kann doch ohne Schwierigkeiten kleiner als n sein und trotzdem proportional zu n verlaufen. T(n) muss doch nicht n entsprechen um auf O(n) zu kommen. Es kommt doch gerade auf einen proportionalen Verlauf von T(n) zu n an!

Grüße,
TS++

TGGC

Hast du eigentlich gelesen, was ich schrieb? Taverage(n) ist O(n). Mit "proportional" hat das aber garnichts zu tun.

Vielleicht liest du mal das hier: http://www.zfx.info/DisplayThread.php?MID=84153 (ja, auch da steht mal was Interessantes oder gleich ein Buch.

Bye, TGGC \-/

TS++

Servus!

Wie Du bereits gemerkt hast, bin ich erst dabei, mich in die Materie einzuarbeiten! Ein Sprung ins kalte Wasser kann nie schaden!

Können wir uns darauf einigen, dass

T1(n) = c * ( ldn +1 ) auf jeden Fall O(log n)

und

(1 + logk n) 
               (k/2)          -  1 
T2(n) = 2c * ------------------------   
                     k - 2

auf jeden Fall O(n) ist !?

Falls ja, bin ich noch am grübeln, ob es noch eine weitere sinnvolle untere Schranke unterhalb von O(n) gibt? Ein Logarithmus kann es nicht sein. Egal welche Variation c*g(n) ich wähle, der Logarithmus wird früher oder später T2(n) unterschreiten! Alles, was ich weiß ist also, dass T2(n) auf jeden Fall für n -> unendlich zwischen linearer und logarithmischer Schranke verläuft. Es muss doch noch eine genauere obere Schranke geben!

Grüße,
TS++

b7f7

TGGC schrieb:

Ich habe es mal eingetippt. Eindeutig nicht linear. Für jedes k lies sich ein n finden, bei dem Taverage(n) << n war. Aber das war klar.

TGGC schrieb:

Taverage(n) ist O(n). Mit "proportional" hat das aber garnichts zu tun.

O(1000*n) == O(n) ==O(n*0.0001)
hat nur was von der linearen abhängikeit zu n zu tuten.

TGGC

TS++ schrieb:

T1(n) = c * ( ldn +1 ) auf jeden Fall O(log n)

und

(1 + logk n) 
               (k/2)          -  1 
T2(n) = 2c * ------------------------   
                     k - 2

Wenn ich das so sehe, behaupte ich mal, die zweite Formel ist ohnehin falsch. Es müsste nämlich gelten T1(n)= T2(n) mit k=2, da der binäre Baum ein Spezialfall eines kd-Baums ist.

Bye, TGGC \-/

TS++

Servus!

Ich hab bei der Entwicklung der Formel folgende Gesetzmäßigkeit ausgenutzt:

a^(n+1) -1
f(n) = a^0 + a^1 + a^2 + .....  + a^n   =   --------------
                                                a - 1

Dadurch ersetze ich an einer Stelle eine Summe.
f(n) ist allerdings für a = 1 nicht definiert!
==> das enspricht bei meiner Aufwandsfunktion im average case eben genau dem Fall k = 2. Daher die Fallunterscheidung.
==> Ich wollte nur das Summensymbol vermeiden!

Grüße,
TS++

Jester

TS++ schrieb:

Jedoch bin ich bisher davon ausgegangen, dass ich relativ grosse Werte für k ansetzen müsste, um zu einer linearen Komplexitätsklasse zu kommen (also: O(n))

Sorry, aber Du kannst so schlicht nicht auf O(n) kommen.
Stell Dir die Formel für den Binärbaum auf. der ist dann mit dem 2er log. Und für nen Baum mit k Nachfolgeknoten wird dadraus ein log mit Basis k.

So, und da

log_k(x) = log(x)/log(k) ist (log(k) ist konstant) sind alle Logarithmen in der gleichen Komplexitätsklasse.

MfG Jester

TS++

Servus Jester!

Jester schrieb:

Sorry, aber Du kannst so schlicht nicht auf O(n) kommen.

Das ist mir jetzt mittlerweilen auch schon klar!
Trotzdem danke für deinen Beitrag!

Ich bin ja mittlerweilen schon so weit, dass ich O(log n) als obere Schranke für T1(n) und O(n) als obere Schranke für T2(n) anerkenne.
T1(n) wird höchstens logarithmisch und T2(n) mindestens logarithmisch und höchstens linear mit n mitwachsen.
Das ist der aktuelle Stand!

Grüße,
TS++

TGGC

Jester schrieb:

TS++ schrieb:

Jedoch bin ich bisher davon ausgegangen, dass ich relativ grosse Werte für k ansetzen müsste, um zu einer linearen Komplexitätsklasse zu kommen (also: O(n))

Sorry, aber Du kannst so schlicht nicht auf O(n) kommen.
Stell Dir die Formel für den Binärbaum auf. der ist dann mit dem 2er log. Und für nen Baum mit k Nachfolgeknoten wird dadraus ein log mit Basis k.

So, und da

log_k(x) = log(x)/log(k) ist (log(k) ist konstant) sind alle Logarithmen in der gleichen Komplexitätsklasse.

MfG Jester

Ich sag's doch, frag die Leute aus'm Matheforum, die kennen auch die ganzen Formeln dahinter.

Bye, TGGC \-/

BVH --&gt; Annäherung an O(n) ?

BVH --> Annäherung an O(n) ?