LOD-Algorithmus...

VirtualDreams

Hab jetzt mal 2 sourcecodes runtergeladen und die mir angeschaut. Das Problem ist jetzt hierbei, das man den code ziemlich schwer nachvollziehen kann (verständlich). Der eine basiert vollkommen auf LOD, der andere auf einem anderen Algo. Aus diesem Grund suche ich ja Tut's die es Schritt für Schritt erklären.
Bzw wäre ich auch schon dankbar wenn jemand mal ein QuadTree (Anfang...) Beispiel posten kann. Auf der Basis würde ich dann weiterarbeiten, muß ja nix komplettes sein. Es geht ersmal nur um das Verständnis zu bekommen.
Wäre ja möglich das ich den QT völlig falsch angefangen hab...

Danke schon im voraus! =))

life

Hier ein Paper, bei dem ein Quadtree fürs LODing verwendet wird:
http://www.vis.uni-stuttgart.de/~roettger/data/Papers/TERRAIN.PDF

Eine Implementiereung, die sich daran orientiert, ist auch auf meiner HP zu finden..

Bei meinem Sourcecode lief es dann wohl auf eine solche Struktur hinaus:

renderQuadTree(blabla) 
{
    if(tesselate(blabla))
    {
        renderQuadTree(blalba/4);
        renderQuadTree(blalba/4);
        renderQuadTree(blalba/4);
        renderQuadTree(blalba/4);
    }
    else
        renderSelf(blabla);
}

ChaosAngel

Minutenlang kann nicht sein.
Bei nem Quadtree unterteilst du einfach das Level in 4 Teile, und das Rekursiv.
Wie Tief geht dein Baum denn, also dafür das es Minutenlang dauert müsstest du schon mehr als die komplette Welt Detailgetreu rendern.
Also leg vielleicht einfach erstmal ne Tiefe vno 10 fest. Das sollten dann max. 20 Tests werden, das ist wirklich im Millisekundenbereich abgegessen.

Ansonsten vielleicht mal nach Octree Tutorials suche, is das selbe nur ne Dimension mehr ...

VirtualDreams

Erst mal vielen Dank für das Bsp! Werd mir das Paper auf jeden Fall durchlesen.

Hmm, hatte ne Tiefe von vlt 10-20 gehabt, das war dann schon etwas übel geworden. Wie gesagt hatte der tree noch nix berechnet oder so, war einfach nur ein laufzeittest...

VirtualDreams

Wie ist das mit dem

renderQuadTree(blalba/4);

zu verstehen?

hab jetzt das ähnlich gemacht - trotzdem langsam

void QuadTree(int deep)
{
if(deep > 0)
{
QuadTree(deep-1);
QuadTree(deep-1);
QuadTree(deep-1);
QuadTree(deep-1);
}
}

Hat trotzdem eine ziemlich schlechte Laufzeit. hab mal als ausgang für deep=10 genommen. Und wenn man das ´mehrmals hintereinander aufruft dauert ein paar sekunden bis er es geschafft hat....

Mach ich hier irgendwas falsch?

Jester

Wenn Du nix aussortierst ist das auch schon ganz gut tief. Bedenke: Dein Quadtree hat in jeder Ebene 4^tiefe Knoten (Tiefe mit 0 beginnen ganz oben). Die Laufzeit ist auf jeden Fall also exponentiell mit der Tiefe, sowas kann schon sehr schnell sehr lahm werden.

Du hast aber im Release-Modus getested, oder?

VirtualDreams

nein, hab bloß den test im debug-mode gemacht. werd mal fix in release machen.
ansonsten glaub ich schon das die laufzeit besser wird wenn man aussortiert, sollte ja auch bloß ein test sein.

[EDIT] hui, ganz schön fix die sache.

for(int i = 0; i < 60; i++)
{
QuadTree(40);
}

Laufzeit < 1 sec

life

Wenn man mal davon ausgeht, dass ein Blatt in deinem Quadtree ein Höhenpunkt darstellt, dann haste bei einem Baum mit Tiefe 40 schon ein Terrain mit 4^40 Höhenpunkten. Wenn nun jeder Höhenpunkt ein Byte braucht, sind das schon mal eben mehr als 10^15 GB= 1000000000000000 GB, die dein Terrain groß sein würde..

Jester

VirtualDreams schrieb:

nein, hab bloß den test im debug-mode gemacht. werd mal fix in release machen.

Merke: Zeitmessungen *immer* im Release-Modus! Warum sollte nun klar sein.

ChaosAngel

Mkere, Zeitmessungen überhaupt nicht an solchen Beispielen !!!

Wenn du in der Funktion nichts machst dann optimiert er es einfach weg, er bräuchte für dein Beispiel also garkeinen Code ausfürehn, deshalb ist er so schnell ...
Aber wie gesagt, der Vorteil bei dem Quadtree ist ja das du etwas suchst ... also du nicht in alle 4 Leafes schaust sondern in jeweils immer nur EINES !!!
Das macht die Laufzeit schon linear und nicht mehr exponentiell ...

Jester

ChaosAngel schrieb:

Mkere, Zeitmessungen überhaupt nicht an solchen Beispielen !!!

Warum? Er hat doch so mind. einen Denkfehler gefunden. Generell ist es doch sinnvoll mal laufen zu lassen, bevor man die aufwendigen Sachen implementiert um zu sehen, ob es überhaupt Sinn macht. Das mag jetzt in diesem Fall nicht unbedingt nötig sein, aber generell schon ne wichtige Sache.

ChaosAngel

Ich meinte nur das man leider an realistischen Beispielen testen muss da sonst auch solche Fehler auftreten wie hier, das der Release mode einfach alles wegoptimiert. Ich weiss nicht ob ihm der Fehler dadurch aufgefallen ist das er nur in einen Node reingehen muss, ich denke nicht. Und es ist ein Unterschied ob ich 10 Schritte mache oder 4^10(oder so).

VirtualDreams

Also ich muß schon sagen das mir das mit dem Releasemodus eine große erkenntniss gebracht hat. Sonst hätte ich wahrscheinlich relativ lange nach dem Fehler gesucht.
Ansonsten ist mir schon klar das ich nicht so tief verschachteln brauch, würde irgendwann ja keinen Sinn mehr machen.

Aber sehr gutes Forum mit sehr guten praktischen Tips - immer wieder!!! Weiter so!

ChaosAngel

Ansonsten ist mir schon klar das ich nicht so tief verschachteln brauch, würde irgendwann ja keinen Sinn mehr machen.

Und genau das meine ich ja !!! Du hast das Problem nicht erkannt ! Deine Verschachtelung kann sonst was wie tief sein ! Die Laufzeit bleibt linear, das heisst sie entspricht der Tiefe ! Ein Quadtree ist dafür da etwas zu suchen (was auch immer) und damit du nicht alle Daten durchgehen musst kannst du sie nach Position sehr schnell sortieren mit deinem Quadtree.

Dein TestAlgo müsste also folgendermassen aussehen

void QuadTree::traverse(someinfo) 
{ 
if(deep > 0) 
{ 
int r = rand() % 4;// here the info comes into play
node[r].traverse(someinfo);
} 
}

Also nur in einem Node weiter gehen!

Wenn du alles zeichnen möchtest dann brauchst du
1. kein Quadtree
2. Kannst dir das Traversieren sparen.(Quadtree enthält meisst sowieso nur Referenzen auf die Grafikdaten, und besitzt sie meisst nicht.)

Hoffe das ist etwas klarer geworden.

VirtualDreams

Bedeutet also wenn ich irgendwo stehe das ich in dem tree dann suche "noch weiter unterteilen oder nicht"? Hab ich das soweit richtig verstanden?
Bedeutet gleichermaßen das ich den tree nicht jedesmal neu erstellen muß, sondern nur einmal und ansonsten nur in dem tree suchen muß s.o.?
Wenn es so ist wird mir einiges klar...

Wie gesagt würde ich mich über kleine stepbystep minisources/-tutorials riesig freuen damit das verständniss besser ist.

life

Vergiss lieber gleich wieder was Chaos geschrieben hat.. Es mag zwar Anwendungen geben, in denen ein Quadtree als ein Suchbaum verwendet wird, aber natürlich muss nicht jeder Quadtree als Suchbaum verwendet werden.
Bei dem von mir verlinkten Paper wird der Quadtree z.B. nicht verwendet um irgendwelche Daten zu suchen..

VirtualDreams

Also doch mehrere Möglichkeiten der Anwendung. Im Paper steht ja glaub ich, dass das Terrain rekursiv aufgebaut wird, wenn ich das richtig übersetzt hab.
Also doch immer wieder neu erstellen?

ChaosAngel

Ja eben nicht wieder neu erstellen. Also da liegt der Feler, da ham wa ihn doch. Falls ich dich jetzt falsch verstehe sag mir (oder auch du Life) bescheid.
(Verdammt, nu komm i zu spät zur Vorlesung!)

Also, der Quadtree wird nur einmal erstellt, indem du all deine Daten Rekursiv zuordnest.
Bei einer Flachen Ansicht wären das z.B. alle Daten im hinteren Rechten Quadranten in ein Quad, alle im Hinteren Linken, vorderen rechten und so weiter ....
das ganze dann natürlich Rekursiv unterteilt.
In deinen Nodes von deinem Quadtree stehen dann (verweise auf) die Daten.
Wenn du nun einen bestimmten Abschnitt deines Levels (whatever) recndern möchtest, zum Beispiel der Teil der gerade sichtbar ist (alles andere zu rendern wäre ja schwachsinn) dann gehst du den Baum Rekursiv durch (traversierst ihn) indem du schaust, liegt mein ViewingFrustum komplett in einem SubQuad, gehe hinein und teste weiter. Falls es z.B. in zwei subquads gleichzeitig liegt dann musst du natürlich nacheinander in beide subquads gehen. Auf jeden Fall findest du am Ende die Geometrie die du gesucht hast, nämlich die die z.B. von deiner Kamera aus sichtbar war. Und das ist normalerweise das Ziel eines Quadtrees. Du musst dann also nur noch diese Daten zeichnen und nicht mehr das ganze riesige Gelände.

Wie gesagt, such mal nach Octree, da sollte es viele Tutorials geben, Quadtree ist ja nur ne Abart davon.

Hoffe i konnte etwas helfen bzw. habe dein Problem richtig verstanden.

VirtualDreams

Ja, das hat mir jetzt erst mal wesentlich geholfen. von der seite her hab ich es nämlich noch nicht betrachtet. Ist für mich schon mal ein guter Anfang!

Aber ist das LoD genauso aufgebaut? ich denke mal schon vom Verständnis her.

Auch hier erst mal wieder vielen Dank für die Hilfe!!!!

life

Bei dem Paper wird eben doch immer neu "aufgebaut". So werden die Koordianten der "Quadranten" garnicht gespeichert, sondern einfach on-the-fly berechnet (sind ja nur ein paar bitshifts).

Weiter ist das Frustrumculling nur eine Teilaufgabe des Quadtrees. So wird er bei weit entfernten "Quadranten" diese auch nicht beliebig weit unterteilen, sondern relativ grob lassen, obwohl sie vielleicht im View-Frustrum liegen.

Aufjedenfall ist auch bei deiner Methode nicht nur unbedingt nur ein "Quadrant" sichtbar, sondern auch mehrere. Somit werden eben auch mehrere Kinder für einen Knoten besucht und nicht nur jeweils ein Kind. Damit ist die Laufzeit auch nicht linear mit der Tiefe des Quadtrees. (Stelle dir z.B. einfach mal Vogelperspektive vor. Dann sind alle Quadranten jeweils im Frustrum und müssen gezeichnet werden)