4. LOD-Algorithmus...

LOD-Algorithmus...

  • J

    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?

    0
  • V

    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 😮 👍

    0
  • L

    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..

    0
  • J

    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. 😉

    0
  • C

    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 ...

    0
  • J

    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.

    0
  • C

    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).

    0
  • V

    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!

    0
  • C

    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.

    0
  • V

    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.

    0
  • L

    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..

    0
  • V

    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?

    0
  • C

    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.

    0
  • V

    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!!!!

    0
  • L

    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)

    0
  • C

    Ich weiss nicht wie oder wozu man einen Quadtree für LOD brauchst bzw. was in dem Paper steht.
    Falls er natürlich jedesmal neu berechnet wird musst du dies für alle Knoten tun. Aber ich denke das auch hier während der Berechnung schon früh Pfade abgeschnitten werden weil sie halt z.B. nicht Detailgetreu sichtbar sein sollen, sondern nur LowQuality.
    Das die Planes zwischen den Quadranten durch Bitshifts berechnet werden könnten wäre mir neu, das sind doch floatings, da möcht ich nur ungern shiften 😉

    @Life
    Ich habe geschrieben das bei der FrustumCull methode nicht immer nur ein Quadrant sichtbar ist, aber es sind nicht immer alle sichtbar, darum ging es mir.

    Ansonsten sorry falls ich hier alle zu sehr verwirrt haben sollte, mein Fehler, ich ging vom FrustumCulling aus und nicht vom LOD. Wie man es tatsächlich dort macht weiss ich nicht.
    Aber ich kann dir sagen wenn du beim traversieren jedes Blatt besuchst dann brauchst du keinen Baum mehr, weil dann kannst du auch gleich durch alle Daten rennen 😃

    Also, i werd mich hier mal raushalten bevor ich noch mehr verwirre, grad im Klausurenstress und keine Zeit das Paper zu lesen.

    Have phun

    0
  • L

    Für die Beschreibung des Terrains benutzt man meistens Heightmaps. Diese haben natürlich eine natürlche Zahl von Pixeln (meist sogar 2^k x 2^k). Somit benutzt man intern natürlich auch keine Gleitkommazahlen. Die Umrechnung in den Worldspace findet erst nachher steht.

    Und im Prinzip geht er natürlich in jedes Blatt des Quadtrees, nur ist nicht jedes Blatt gleich tief 😉

    0
  • C

    Und im Prinzip geht er natürlich in jedes Blatt des Quadtrees, nur ist nicht jedes Blatt gleich tief

    Wozu dann der Baum ?!?!?
    Dann soll er doch einfach alle Daten durchgehen !
    Aber egal, hab mir den Algo eh net durchgelesen, also einfach ignorieren ..

    0
Anmelden zum Antworten