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

[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 \-/

[TS++]

Ach ja,
Ihr dürft auch nicht vergessen, dass eine BVH kein Suchbaum im klassischen Sinne ist.( wie z.B. der binäre Suchbaum )
In einer BVH erfolgt ja in keinster Weise eine Einsortierung der BVs nach irgendwelchen Schlüsseln. Beim binären Suchbaum wäre das ja so. Zum Test einzelner Knoten würde man dort unmittelbaren Gebrauch von der aufsteigenden Sortierung der Knoten machen. Es besteht beim binären Suchbaum also ein unmittelbarer Zusammenhang zwischen der Baumstruktur(ausbalanciert oder nicht) und dem Test einzelner Knoten. Die Verteilung der Knoten bestimmt letztendlich im Einzelfall, welche Teilproblemmenge verworfen werden kann und welche noch getestet werden muss. Die Wahrscheinlichkeit, in der größeren Restproblemmenge weitertesten zu müssen wird also immer höher sein, als die Wahrscheinlichkeit, den gesuchten Schlüssel im kleineren Teil wiederzufinden.
Das ist bei BVH nicht der Fall. Der Test einzelner Knoten findet völlig unabhängig vom Gleichgewicht der BVH durch Kollisionstests statt. Das Ergebnis so eines Kollisionstests und somit die Entscheidung, ob ein Teilbaum verworfen wird oder nicht, wird durch viele Faktoren beeinflusst, z.B. Volumenverhältnis zwischen BV und ViewFrustrum, aber eben nicht durch die Struktur der BVH. Der ViewFrustrum kann sich zu jedem Zeitpunkt irgendwo in der BVH befinden. Bewegt man den ViewFrustrum nur lange genug durch die BVH, so werden genausoviele 'kleine' Teilbäume wie 'grosse' Teilbäume verworfen. Im Schnitt müsste sich also eine unausbalancierte BVH in etwa so verhalten wie eine ausbalancierte BVH. Das einzig Auffällige wäre die Tatsache, dass unausbalancierte BVH bei eingeschränkter Bewegungsfreiheit des ViewFrustrums instabil arbeiten. Tests in realitätsnaher Zeit wären somit nur schwer möglich. Je nachdem wo sich der ViewFrustrum gerade befindet und wie BVs und VF zueinander liegen wird die Effizienz schwanken. Mal hat man Pech O(n), dann wieder Glück O(1). Im average case aber auf jeden Fall O(log n).
Allgemeingültig, also für alle Szenarien, ist es mathematisch nur schwer zu fassen, wann ein frei beweglicher VF welchen Teilbaum schneidet und welchen nicht. (Daher auch meine Idee Schnittwahrscheinlichkeiten mit einzubauen)
Man kann somit das Konzept der BVH und das Konzept klassischer Schlüsselbasierter Bäume nur schwer miteinander vergleichen! Bei klassischen Suchbäumen kann man sich bei der Suche mit vorgegebenen Schlüsseln an absehbaren Bahnen durch den Baum hangeln. Also leichter formulierbar und vorhersehbar.

Grüße,
TS++

[TGGC]

Schon mal darüber nachgedacht, das eine kleinerer Node auch eine geringere Wahrscheinlichkeit hat, den Rand des VF zu schneiden?

Bye, TGGC \-/

[TS++]

Servus!

Das hab ich ja schon in meiner Formel berücksichtigt!

Angenommen ich würde für den durchschnittlichen Fall eine Basisschnittwahrscheinlichkeit von 0,5 wählen.(ich leg mich also im Schnitt auf keinen Trend fest) und ich stelle mir eine BVH der Höhe 2 vor, dann könnte man für einen vollständigen Baum auf Folgendes kommen:

T(n) = 0,5*c + 0,5*(c + k * (0,5*c + 0,5 * (c + k*c)))

c entspricht hierbei dem Arbeitsaufwand für einen Kollisionstest (der Algo ist ja immer der gleiche)
Mit 50% könnte ich also bereits bei der Wurzel zu dem Ergebnis kommen, dass der gesamte Baum sichtbar bzw. unsichtbar ist --> es wäre also lediglich ein Aufwand von c erforderlich!
Es kann aber ebenso mit 50% der Fall eintreten, dass die Wurzel den VF schneidet --> ich muss eine Ebene tiefer weitermachen!
==> je tiefer ich also in den Baum eintauche um so geringer wird auch die Wahrscheinlichkeit werden, dass noch ein BV geschnitten wird!
Man könnte den Effekt natürlich noch verstärken, indem man jeder Ebene nochmal eine eigene Schnittwahrscheinlichkeit zuordnet. Hab ich schon mal ausprobiert! Am grundsätzlichen Ergebnis hat sich nichts geändert! Klar der Graf wird etwas verformt, muss ja so sein! Nur der prinzipielle Verlauf hat sich nicht geändert!

Es gibt wahrscheinlich unendlich viele Ansätze an die Problematik heranzugehen!
Und kaum einer dieser Ansätze wird den Kern des Algo für alle denkbaren Fälle wirklich zu 100% treffen. Das behaupte ich von meinem Ansatz auch nicht! Ich denke nur, man kann sich über Wahrscheinlichkeiten stufenweise der Realität nähern und somit den wirklichen Aufwand abschätzen!

Schönen Sonntag!

Grüße,
TS++

[TGGC]

Und wieso sagst du dann:

Bewegt man den ViewFrustrum nur lange genug durch die BVH, so werden genausoviele 'kleine' Teilbäume wie 'grosse' Teilbäume verworfen.

Bye, TGGC \-/

[TS++]

Vielleicht drück ich mich ja auch nur so unglücklich aus!

Ich hab mich dabei auf den unausbalancierten Baum bezogen.

Bewege ich mich genausoviel in den Ecken mit wenig Geometrie wie in den Bereichen mit viel Geometrie, so ergibt sich im Schnitt das gleiche Verhalten wie bei einer ausbalancierten BVH. Denn wieviel Geometrie ich im average case verwerfen kann hängt ja letztendlich u.a. von der Position des ViewFrustrums ab. Egal wieviel Geometrie unter einem BV hängt, die Schnittwahrscheinlichkeit für diesen BV wird dadurch nicht zwangsläufig größer.
Hab ich Pech und ich bewege mich jetzt eine Zeit lang nur in dichten Bereichen, so wird der gemessene zeitliche Aufwand (jetzt nicht die Komplexitätsklasse) z.B. im worst case natürlich höher sein als in Ecken, in denen weniger los ist. Der Betrachter wird also so einen Positionswechsel von einem Bereich mit einer bestimmten Geometriedichte in einen anderen Bereich mit anderer Dichte spüren.(z.B. durch Ruckeln des Bildes) Nur die Komplexitätsklassen werden für jeden dieser Bereiche isoliert betrachtet(das sind ja auch wieder ausbalancierte oder unausbalancierte Bäume) und auch für den kompletten Baum wieder O(1) im best, O(log n) im average und O(n) im worst case sein.
Klingt verrückt, macht aber Sinn!

Grüße,
TS++