Du bist nicht angemeldet.

Stilllegung des Forums
Das Forum wurde am 05.06.2023 nach über 20 Jahren stillgelegt (weitere Informationen und ein kleiner Rückblick).
Registrierungen, Anmeldungen und Postings sind nicht mehr möglich. Öffentliche Inhalte sind weiterhin zugänglich.
Das Team von spieleprogrammierer.de bedankt sich bei der Community für die vielen schönen Jahre.
Wenn du eine deutschsprachige Spieleentwickler-Community suchst, schau doch mal im Discord und auf ZFX vorbei!

Octree mit Frustum Culling

  • 1
  • 2

Werbeanzeige

da_oAsch

Treue Seele

  • »da_oAsch« ist der Autor dieses Themas

Beiträge: 92

  • Private Nachricht senden

1

22.01.2004, 17:10

Octree mit Frustum Culling

Hi Leutz,

hab in meinem Spiel kürzlich einen Octree für meine statischen Objekte (Haus, Brunnen, Bank, Mauern, Bäume, Pflanzen, ...) implementiert:
Jedes Objekt soll den kleinsten Knoten gerendert werden in den es hineinpasst.

Dann hab ich das Frustum Culling hinzugefügt und gerendert.

Meine FPS gingen in den Keller...

Daher meine Frage: Ist Octree - Frustum Culling eine gute Methode um ein wenig mehr Performance bei vielen Objekten herauszuholen (wenn ja, ist wahrscheinlich mein Code falsch :rolleyes: )

Oder eignet sich diese Methode weniger für oben beschriebene Aufgabe?


Danke & Greetings,
da_oAsch

DragonMaster

Community-Fossil

Beiträge: 1 603

  • Private Nachricht senden

2

22.01.2004, 20:16

Ein Aenhliches Problem hab ich bei meinem Terrain-Renderer. Ich hab mein Terrain in einen Quad-Tree eingeteilt. Das Problem ist nur das alles bald schneller gerendert wird wenn ich alles auf einmal render statt immer den Baum zu durchlaufen. Vor allem sinkt die Performance wenn der Baum sehr tief ist.

Woran das liegen kann weis ich leider auch nicht so genau. Kann mir aber einfach gut vorstellen das es an Mangelnder Optimierung liegt. Besonders wenn es darum geht die BoundingBox gegen das ViewFrustum zu testen.
Wichtig! Ich übernehme keinerlei Verantwortung für eventl. Datenverlust oder Schäden am Rechner ;D

da_oAsch

Treue Seele

  • »da_oAsch« ist der Autor dieses Themas

Beiträge: 92

  • Private Nachricht senden

3

23.01.2004, 09:44

Also der Quadtree haut bei mir bis zur Tiefe 7 hin (ich hoffe das ist dann ausreichend, aber beim Octree hab ich wahnsinnige probleme!

Aber nicht wegen der Tiefe, sondern bei meiner Funktion die prüfen soll, ob ein Knoten sichtbar ist:

NodeIsVisible(SOctNode* Node)
// Prüfen ob BoundingSphere des Knoten im ViewFrustum ist
// wenn ja -> NodeIsVisible(Node->children
// wenn nein: return
// wenn schneidet: prüfen ob Bounding Box im ViewFrustum ist
// wenn ja -> NodeIsVisible(Node->children[i]
// wenn nein: return

tjo ...
mfG
da_oAsch

DragonMaster

Community-Fossil

Beiträge: 1 603

  • Private Nachricht senden

4

23.01.2004, 19:26

Zitat

Aber nicht wegen der Tiefe, sondern bei meiner Funktion die prüfen soll, ob ein Knoten sichtbar ist:

NodeIsVisible(SOctNode* Node)
// Prüfen ob BoundingSphere des Knoten im ViewFrustum ist
// wenn ja -> NodeIsVisible(Node->children
// wenn nein: return
// wenn schneidet: prüfen ob Bounding Box im ViewFrustum ist
// wenn ja -> NodeIsVisible(Node->children[i]
// wenn nein: return

Ist kein Wunder das er so langsam ist. Wenn ich das ganze richtig Interpretiere durchlaufst du deinen Baum 2mal in jedem Frame. Einmal fuer die BoundingSphere und einmal fuer die BoundingBox. Ist dein Modell also komplett sichtbar, haste den totalen Overkill ;D Kommentier mal den Test fuer die BoundingSphere aus und schau was passiert.
Wichtig! Ich übernehme keinerlei Verantwortung für eventl. Datenverlust oder Schäden am Rechner ;D

da_oAsch

Treue Seele

  • »da_oAsch« ist der Autor dieses Themas

Beiträge: 92

  • Private Nachricht senden

5

24.01.2004, 10:51

Nein ich durchlaufe ihn nicht zweimal, weil wenn der viel schnellere Test mit der Bounding sphere fehlschlägt (d.h. der Knoten ist nicht sichtbar) wird der test mit der BoundingBox gar nicht erst durchgeführt.

Hab vorher eh nur den test mit der BoundingBox gehabt, und hab eben aus gründen der Performance noch den Vortest mit der BoundingSphere hinzugefügt.

Recht viel schneller geworden ist das ganze allerdings nicht...

Vielleicht hast du meinen Pseudocode falsch aufgefasst:

Quellcode

 
1
2
3
4
5
6
7
8
9

NodeIsVisible(SOctreeNode *Node)
{
if(IsVisible(Node->BoundingSphere) == OUT)
return;
else if(IsVisible(Node->BoundingSphere) == IN)
NodeIsVisible(Node->children[alle];
else  ...
// hier kommt dann das gleiche mit der BoundingBox
}


mfG
da_oAsch

Jumping Jack

Treue Seele

Beiträge: 142

Wohnort: Hamburg

Beruf: Schüler

  • Private Nachricht senden

6

24.01.2004, 16:48

wenn du weißt, das die bounding sphere komplett inerhalb des frsutrums ist, dann brauchst du die childnodes ja nicht mehr überprüfen.

DragonMaster

Community-Fossil

Beiträge: 1 603

  • Private Nachricht senden

7

24.01.2004, 19:22

Habs wircklich falsch verstanden :huhu:

Wann ist den eine BoundingSphere IN und wann OUT? Ist sie IN wenn sie komplett sichbar ist oder auch Teilweise? Daselbe auch fuer OUT. Ich frage nur weil, bei meinem QuadTree ist eine Quad OUT wenn er gar nicht sichtbar ist und IN wenn er zu min. teilweise sichtbar ist. Wuerde ich deinen vortest also mit einbauen, wuerde das heissen das mein BoundingBox Test nie ausgefuehrt wuerde.
Denn zu pruefen ob eine BoundingSphere nur teilweise sichtbar ist also SPLIT und dafuer dann den BoundingBox Test zu berappen ist irgendwie doppelt, oder?
Wichtig! Ich übernehme keinerlei Verantwortung für eventl. Datenverlust oder Schäden am Rechner ;D

da_oAsch

Treue Seele

  • »da_oAsch« ist der Autor dieses Themas

Beiträge: 92

  • Private Nachricht senden

8

24.01.2004, 21:35

IN: komplett drinnen
OUT: komplett draußen

darum der dritte zweig des if-Satzes (d.h. den betret ich wenn die Sphere teilweise drinnen ist)

Wird dieser betreten prüfe ich die BoundingBox.
Bei der Bounding Box gibt es dann nur mehr

IN: mindestens eine Ecke der Box ist drinnen
OUT: alle Ecken sind außerhalb

NoName

Treue Seele

Beiträge: 118

Beruf: Student

  • Private Nachricht senden

9

24.01.2004, 23:37

Poste mal den "richtigen" Code :).

da_oAsch

Treue Seele

  • »da_oAsch« ist der Autor dieses Themas

Beiträge: 92

  • Private Nachricht senden

10

25.01.2004, 15:58

Quellcode

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

void CStatics::NodeIsVisible(SOctNode *Node)
{
    if(Node != NULL)
    {
        float       fDistance;
        WORD        iVertxOut = 0;
        WORD        iVertxIn = 0;
        tbVector3   fCheckPoints[8];
        tbVector3   vMiddle = Node->vMiddle;
        tbVector3   vEdge = Node->vEdge;
        float       fSqRadius;
        
        // Sphere check
        fSqRadius = tbVector3LengthSq(vMiddle);

        for(WORD h = 0; h < 6; h++)
        {
            fDistance = tbPlaneDotCoords(   m_pFrustum->Planes[h],
                                            Node->vMiddle);

            if(fDistance * fDistance < -fSqRadius)
            {   // Sphere is out
                Node->isVisible = false;
                return;
            }
            iVertxIn += 1;
        }

        if(iVertxIn < 6) // Intersecting
        {
            // Box check
            fCheckPoints[0] = vMiddle + tbVector3(vEdge.x, vEdge.y, vEdge.z);
            fCheckPoints[1] = vMiddle + tbVector3(vEdge.x, -vEdge.y, vEdge.z);
            fCheckPoints[2] = vMiddle + tbVector3(-vEdge.x, -vEdge.y, vEdge.z);
            fCheckPoints[3] = vMiddle + tbVector3(-vEdge.x, vEdge.y, vEdge.z);
            fCheckPoints[4] = vMiddle + tbVector3(vEdge.x, vEdge.y, -vEdge.z);
            fCheckPoints[5] = vMiddle + tbVector3(vEdge.x, -vEdge.y, -vEdge.z);
            fCheckPoints[6] = vMiddle + tbVector3(-vEdge.x, -vEdge.y, -vEdge.z);
            fCheckPoints[7] = vMiddle + tbVector3(-vEdge.x, vEdge.y, -vEdge.z);


            // calculate our distances to each of the planes
            for(WORD i = 0; i < 6; ++i)
            {
                for(WORD j = 0; j < 8; ++j)
                {
                    // find the distance to this plane
                    fDistance = tbPlaneDotCoords(   m_pFrustum->Planes[i],
                                                    fCheckPoints[j]);
                    if(fDistance < 0.0f) iVertxOut += 1;
                }

                // Wenn Knoten nicht sichtbar, return
                if(iVertxOut == 8)
                {
                    Node->isVisible = false;
                    return; 
                }
                iVertxOut = 0;
            }
        }

        // Node is Visible
        Node->isVisible = true;

        // Wenn es kein Blatt war, weitersplitten
        if(!(Node->isLeaf))
        {
            for(WORD k = 0; k < 8; ++k)
            {
                NodeIsVisible(Node->pChildren[k]);
            }
        }
    }
}

Werbeanzeige

  • 1
  • 2