Autor Wątek: QuadTree/LOD przy renderowaniu terenu  (Przeczytany 673 razy)

Offline Dragomirus

  • Użytkownik

# Lipiec 23, 2017, 05:54:13
Witam,
jeżeli temat nie pasuję to działu to proszę o przeniesienie bo za bardzo nie wiedziałem gdzie go dać.

Ostatnio dwoje się i troje żeby rozwiązać pewien problem związany z renderowaniem terenu. Otóż na początku wyświetlałem mój teren jako jedną wielką siatkę (która zajmowała jedno VAO w openGLu), teraz jednak chciałbym usprawnić to wyświetlanie poprzez dodanie LOD. Zacząłem od implementacji drzewa czwórkowego. Najważniejsza metoda to ta:
/**
 * Render tile
 * @param program - shader program
 */
public void render(Camera camera, Shader program)
{
    if(camera.hasMoved())
        this.quadtree.updateQuadTree(camera);

    this.quadtree.render(program);
}

/**
 * Update quadtree
 * @param camera - camera
 */
public void updateQuadTree(Camera camera)
{
    for(Node node : getChildren())
        ((TerrainTreeNode) node).updateQuadtree(camera);
}

Następnie zaimplementowałem element tego drzewa i najważniejsze jego metody to te:
/**
 * Update quad tree
 * @param camera - camera
 */
public void updateQuadtree(Camera camera)
{
    updateChildNodes(camera.position);

    for(Node node : getChildren())
    {
        ((TerrainTreeNode) node).updateQuadtree(camera);
    }
}

/**
 * Update child nodes
 * @param cameraPosition - camera position
 */
private void updateChildNodes(Vector3f cameraPosition)
{
    Vector3f tempCamera = new Vector3f(cameraPosition);
    Vector3f tempPosition = new Vector3f(this.position);
    Vector3f.sub(tempCamera, tempPosition, tempCamera);
    float distance = tempCamera.length();

    switch(this.lod)
    {
        case 0:
            if(distance < 1750)
            {
                addChildNodes(this.lod+1);
            }
            else if(distance >= 1750)
            {
                removeChildNodes();
            }
            break;

        case 1:
            if(distance < 874)
            {
                addChildNodes(this.lod+1);
            }
            else if(distance >= 874)
            {
                removeChildNodes();
            }
            break;

        case 2:
            if(distance < 386)
            {
                addChildNodes(this.lod+1);
            }
            else if(distance >= 386)
            {
                removeChildNodes();
            }
            break;

        case 3:
            if (distance < 192)
            {
                addChildNodes(this.lod+1);
            }
            else if(distance >= 192)
            {
                removeChildNodes();
            }
            break;

        case 4:
            if(distance < 100)
            {
                addChildNodes(this.lod+1);
            }
            else if(distance >= 100)
            {
                removeChildNodes();
            }
            break;

        case 5:
            if(distance < 50)
            {
                addChildNodes(this.lod+1);
            }
            else if(distance >= 50)
            {
                removeChildNodes();
            }
            break;

        case 6:
            if(distance < 0)
            {
                addChildNodes(this.lod+1);
            }
            else if(distance >= 0)
            {
                removeChildNodes();
            }
            break;

        case 7:
            if (distance < 0)
            {
                addChildNodes(this.lod+1);
            }
            else if(distance >= 0)
            {
                removeChildNodes();
            }
            break;
    }
}

/**
 * Add child nodes
 * @param lod - level of detail
 */
public void addChildNodes(int newLod)
{
    if(isLeaf)
    {
        isLeaf = false;
        if(this.mesh != null)
            this.mesh.dispose();
    }
    if(getChildren().size() == 0)
    {   
        float newWidth = this.width/2f;
        float newWidth2 = newWidth/2f;
        for(int i = 0; i < 2; i++)
        {
            for(int j = 0; j < 2; j++)
            {
                float first, second;
                if(i == 0)
                    first = -(newWidth/2f);
                else
                    first = newWidth/2f;
                if(j == 0)
                    second = -(newWidth/2f);
                else
                    second = newWidth/2f;

                Vector3f newPosition = new Vector3f(this.position.x+first,
                        0f, this.position.z+second);
                addChild(new TerrainTreeNode(newPosition,
                        newLod,
                        new Vector2f(i, j),
                        newWidth));
            }
        }
    }   
}

/**
 * Remove child nodes
 */
private void removeChildNodes()
{
    if(!isLeaf)
    {
        isLeaf = true;
        this.mesh = generateMesh();

    }
    //Remove childrends
    if(getChildren().size() != 0)
    {
        for(Node child : getChildren())
            child.dispose();

        getChildren().clear();
    }
}

Jak widać mój element drzewa albo jest gałęzią i wtedy posiada dzieci, albo jest liściem i wtedy posiada własne VAO (jest to 10 wierzchołków z czego pierwszy jest na środku kwadratu, a pozostałe na krawędziach tego kwadratu, sposób wyświetlania to triangle fan). Całość dziala bardzo ładnie i utrzymuje się te 60 klatek jednak pojawił się problem. Pomiędzy elementami drzewa, które mają różny LOD pojawiają się dziury. Nie mam pojęcia za bardzo jak je załatać chociaż mam taki pomysł, żeby obok każdego stworzonego w liściu VAO dodatkowo przechowywać jeszcze 8 permutacji tak jak opisano to w tym dokumencie: http://www.dice.se/wp-content/uploads/2014/12/Chapter5-Andersson-Terrain_Rendering_in_Frostbite.pdf -> strona 53-55.
Jednak nadal nie mam pojęcia skąd mam wiedzieć jaką permutacje obecnie wyświetlić. Ponad to mam pomysł żeby wyszukiwać LOD sąsiadów danego liścia (górnego, dolnego, prawego i lewego) i na podstawie tego wybrać permutacje, ale również nie mam pojęcia jak to wyszukać.

Byłbym wdzięczny za każdą pomoc. Wiem, że w OpenGLu 4.0 jest tesalacja, która wszystko robi za nas i nie trzeba się martwić o dziury, ale jednak póki co wolałbym pozostać przy wersji 3.3.

Offline Mr. Spam

  • Miłośnik przetworów mięsnych

Offline Mergul

  • Użytkownik

  • +1
# Lipiec 23, 2017, 09:37:02
10 wierzchołków dla chunka terenu to strasznie mało, sugerowałbym stworzyć chunki 32x32 (33x33 wierzcholki). Jeżeli dalej chcsz wykorzystywać triangle fan, albo triangle strip to można wykorzystać glPrimitiveRestartIndex i zbudować taki chunk z kilku pasków.
Sposobów na pozbycie się dziór jest całkiem sporo. Najprostszy (i najgorszy chyba) to jest po prostu zrobienie dodatkowej obwódki dla każdego chunka która byłaby przesunięta mocno w dół (co powodowałoby zakrycie przerw). Inny sposób to to co opisane jest w pdf-ie który podlinkowałeś. Albo stworzyć permutacje dla boków dopasowanych do niższego poziomu szczegółowości, albo te do wyższego (co wydaje się lepsze, ze względu na mniejszą ilość permutacji). W tej metodzie wiesz z góry którą permutację wybrać. pierwszy chunk jest pełny, nastepnie obok Ciebie 8 chunków to 8 kolejnych permutacji. Dalej mamy 2 LOD a nastepnie permutacje 2 LOD.
Jest jeszcze kolejna metoda, seamless lod. Na podstawie kamery zbliżasz ustawienie wierzchołków 1LOD do wierzchołków 2LOD, a kiedy osiągniesz taki chunk wyglądający w pełni jak 2LOD to zaczynasz wyświetlać faktycznie drugie LOD.

Offline Dragomirus

  • Użytkownik

# Lipiec 23, 2017, 14:13:20
Z tymi wierzchołkami to rzeczywiście w przyszłości chciałbym zrobić więcej na jednego chunka terenu jak już będę miał podstawowy algorytm bo rzeczywiście słusznie zauważyłeś, że to mało. Najbardziej mnie zainteresowała metoda w której to chunk z niższym LODem dopasowuje się do tego z wyższym. Rozumiem, że w tym wypadku dla każdego chunka sprawdzam jego tylko najbliższych sąsiadów, które mają ten sam LOD (zawsze będzie ich tylko dwóch) i w zależności od tego czy mają dzieci (co oznacza, że mają jeszcze większy LOD) to wybieram odpowiednią permutacje?

Offline Mergul

  • Użytkownik

# Lipiec 23, 2017, 15:56:53
hmmm... nie rozumiem co masz na myśli i w czym widzisz problem. Więc od początku, wszystkie chunki mają identyczną wielkość (np. 32x32m), i możesz myśleć o nich jak o chunkach trzymanych w gridzie. LOD zmienia się na podstawie odległości od kamery (a przynajmniej większość tak robi). Chunki blisko Ciebie są bardzo szczegółowe, a im sa dalej, tym gorzej wyglądają (ale nie widać tego częśto ze względu na odległość). Skoro w zalężności od odległości od kamery, to bez zbędnego sprawdzania czegokolwiek wiesz który LOD ma dany chunk, i jaką permutację należy mu wybrać (bo wynika to z jego relatywnej pozycji względem kamery). Oczywiście można różnie to zakodzić, najprościej jest tak żeby LOD zmieniał się w zależności od odległości po składowej, czyli sprawdzam czy która składowa relatywnej pozycji jest większa i po tej ustawiam LOD. Albo który to jest chunk od głównego (ten na którym się znajdujesz), i wtedy wystarczy "przesuwać" permutacje. Nie wiem czy dobrze wytłumaczyłem.

Offline DezerteR

  • Użytkownik

# Lipiec 23, 2017, 16:13:51
Ja jak kiedyś robiłem teren to żeby sie nie męczyć po prostu zagęściłęm wierzchołki na krawędziach wyższych LOD(miałem jeden mesh chunka, kolejne poziomy lod były dwa razy większe). Rysowanie terenu jest na tyle tanie że nie ma sensu męczyć się nad jakimiś skomplikowanymi implementacjami, taniej będzie odrysować wszystko jednym callem niż bawić się w składanie i analizowanie pierdyliarda krawędzi.

Offline Dragomirus

  • Użytkownik

# Lipiec 24, 2017, 03:29:21
@Mergul
Ok już wszystko jasne. Zacząłem właśnie już robić tak jak mi mówiłeś, czyli chunki wielkości 32x32 wierzcholki. Mam cztery poziomy level of detail i kod działa, jednak jeszcze z braku czasu nie zacząłem robić spojenia pomiędzy chunkami, ale już mam jakiś tam pomysł w głowie zwłaszcza, że sąsiadów teraz mi łatwiej znaleźć niż w drzewie czwórkowym co za tym idzie ich LOD. Jak będę miał problemy to na pewno się odezwę. Dzięki chłopaki za pomoc :)