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!

Werbeanzeige

roka

Frischling

  • »roka« ist der Autor dieses Themas

Beiträge: 4

Wohnort: Grosse Stadt

  • Private Nachricht senden

1

12.07.2011, 22:33

SFML/OpenGL: Grid, Quadtree, OpenGL - Verständnisfrage

Hallo Com,

zunächst möchte ich mitteilen, dass dies mein erster Beitrag in diesem Forum ist. Mir geht es grundlegend um die Verständnisfrage der Verwendung von Grids und/oder Quadtrees in Bezug auf OpenGL und das Culling von Objekten. In meinem Fall handelt es sich um eine einfache 2D-OpenGL-Anwendung mit entspr. orthogonalem Frustum. Mein Problem ist, dass ich mir im Moment nicht sicher bin wie ich eine zukünftig wesentlich größere Menge an Objekten sinnvoll verwalten kann. Meine Idee ist es einen Quadtree zu verwenden, der in seinen Nodes entsprechend die OpenGL-Objekte enthält - daher meine Verständnisfrage:

Bildet man mit einem Quadtree üblicherweise immer nur den aktuellen Bildschirmausschnitt ab oder nutzt man diesen dazu um eine gesamte Karte einschl. Paging abzubilden?

Mir geht es hier auch um das nötige Culling nicht sichtbarer OpenGL-Objekte die entspr. fehlender Sichtbarkeit nicht gerendert werden sollen (boolsches Attribut "rendern" in jeder Node). Zusätzliche dazu habe ich aber im diesem Thread auch etwas über eine mögliche Lösung mit einem Grid gelesen - ich denke aber, dass ein Quadtree sinnvoller ist um später auch eine Collision Detection zu implementieren. Im Anhang befindet sich mein aktueller Quelltext einschl. dem angefangenen Header für einem Quadtree sowie ein Screenshot.

Mit dank für euer Feedback

roka


C-/C++-Quelltext

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

int DrawScene() {
    int sc=40;
    glLoadIdentity();
    glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);
        
    //[.......]
    
    glPushMatrix();
        glTranslated(300, -100, 0);
        glScalef(sc,sc ,0);
        glColor3f(0.5,0.5,0.5);
        glRotatef(110,0,0,1);
        glEnableClientState(GL_VERTEX_ARRAY);
            glVertexPointer(2, GL_FLOAT, 0, q2);
            glDrawArrays(GL_QUADS, 0, 4);
        glDisableClientState(GL_VERTEX_ARRAY);
    glPopMatrix();
    
    return 0;
}


//[.....]



int main(int argc, char** argv) {

    sf::RenderWindow App(sf::VideoMode(1024, 768, 32), "OpenGL", sf::Style::Close);

    sf::Clock Clock;
    
    //[.....]
    
    // getting real-time input for event handling (continious move, etc.)
    const sf::Input& Input = App.GetInput();
    
    std::ostringstream out;
    
    while (App.IsOpened()) {   // Start game loop
    
        float Framerate = 1.f / App.GetFrameTime();
        float ElapsedTime = Clock.GetElapsedTime();
        Clock.Reset();
        
        //[....]
        
        InitViewMatrix2D();

        glMatrixMode(GL_PROJECTION);
        glTranslated(TranslationX, TranslationY, 0);
        glScalef(Scale,Scale,0);
        glMatrixMode(GL_MODELVIEW);
        
        glEnable (GL_CULL_FACE); //enables faceculling
        glFrontFace (GL_CCW);
        glCullFace (GL_BACK);
        
        DrawScene();
        
        App.PreserveOpenGLStates(true);
            txt.SetText(temp);
            App.Draw(txt);
        App.PreserveOpenGLStates(false);
        // Finally, display rendered frame on screen
        App.Display();
    }

    return EXIT_SUCCESS;
}
»roka« hat folgende Datei angehängt:
Signatur?

idontknow

unregistriert

2

12.07.2011, 22:42

Naja mit dem QuadTree bildest du ja ne ganze Map ab teilst diese eben auf bis zu nem minimalen Rect und has tdann natürlich irgendwo ne Position "an der du dich befindest" und kannst ausgehend von der dann eben entsprechend viel rendern und das damit schon eingrenzen. Die Kollision kannst so natürlich auch auf die Rects anwenden die in Frage kommen.

dot

Supermoderator

Beiträge: 9 757

Wohnort: Graz

  • Private Nachricht senden

3

12.07.2011, 23:51

Wie sehen diese Maps aus? Wenn alles auf einem regelmäßigen Gitter aufbaut ist ein Grid evtl. sehr viel effizienter als ein Quadtree. Wenn es nur ein Haufen verschiedenster Objekte beliebiger Größe mit beliebiger Position und eher ungleichmäßiger Verteilung ist wird ein Quadtree oder eine Bounding-Volume-Hierarchy evtl. besser sein. Quadtree hört sich vielleicht auf den ersten Blick toll an, aber bedenke dass du diesen Tree auch ständig updaten musst wenn sich irgendwas bewegt. Abgesehen davon hindert dich auch Nichts dran verschiedene Ansätze zu kombinieren ;)

roka

Frischling

  • »roka« ist der Autor dieses Themas

Beiträge: 4

Wohnort: Grosse Stadt

  • Private Nachricht senden

4

13.07.2011, 00:07

Vielen Dank für das sehr schnelle Feedback!

Das was man auf dem Screenshot sehen kann, soll im späteren Spiel Häuser darstellen. Damit handelt es sich also um feststehende Objekte - eine ungleichmäßige Verteilung und Position - die Häuser sollen im Editor frei positionierbar sein - trifft ebenfalls zu. Allerdings wird es auch bewegliche Elemente geben, in diesem Fall dann "Bewohner" die sich zwischen den Häusern bewegen können sollen - respektive entspr. auch kollidieren oder eben nicht.

Zitat

Abgesehen davon hindert dich auch Nichts dran verschiedene Ansätze zu kombinieren
Und dieser Tipp bewegt mich doch glatt dazu auszuprobieren die festen Objekte auf einem Grid und die beweglichen Objekte in einem Quadtree zu verwalten - meinen grossen Bruder G frage ich dann nochmal was es mit der Bounding-Volume-Hierarchy auf sich hat. Ei, ich glaub das wird ne lange Nacht ..... :) Ich melde mich dann nochmal. :D

Gruß

roka
Signatur?

dot

Supermoderator

Beiträge: 9 757

Wohnort: Graz

  • Private Nachricht senden

5

13.07.2011, 00:10

Wenn die Anzahl der beweglichen Objekte die sich gleichzeitig am selben Fleck befinden in einem gesunden Rahmen liegt dann kannst du die auch einfach in ein Grid packen. Ein Quadtree ist gerade für bewegliche Objekte nicht unbedingt so toll ;)

Der wesentliche Vorteil von einem regelmäßigen Gitter ist dass du sehr schnell drauf zugreifen kannst.

roka

Frischling

  • »roka« ist der Autor dieses Themas

Beiträge: 4

Wohnort: Grosse Stadt

  • Private Nachricht senden

6

14.07.2011, 20:00

Gelöst.

Hallo Com,

hier meine versprochene Rückmeldung - habe es mit einem Grid ausprobiert - funktioniert wunderbar! :) Danke für den Tipp. Problem gelöst. Anbei auch wieder mein aktueller, noch schwer verbesserungswürdiger Quelltext und kleiner Screenshot. Da es im Moment noch einen Prototyp darstellt render und "culle" ich momentan noch das Grid selbst, das Verbinden mit einer Objektklasse sollte aber kein Problem darstellen. :) Und falls jemand zu guter letzt eine gute Quelle (Tutorial, HowTo, Source) für die Implementierung eines Quadtrees hat freue ich mich über entspr. Links. Danke - ansonsten Problem gelöst.

[SOLVED]

Meine Gridklasse:

C-/C++-Quelltext

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
class Grid {
private:
    std::vector< std::vector<Field> > mFields;
    int mSize; // mSize*mSize = Fields
    sf::String s;

public:
    //ctor
    Grid () {};
    //ctor
    Grid (int pSize) {
        for (int i=0; i<pSize; i++) {
            for (int a=0; a<pSize; a++) {
                this->mFields.push_back(std::vector<Field>(pSize));
            }
        }
        for (int i=0; i<pSize; i++) {
            for (int a=0; a<pSize; a++) {
                this->mFields[i][a].y = i; //row,y
                this->mFields[i][a].x = a; //col, x
            }
        }
        this->mSize = pSize;
        s.SetSize(10);
        s.SetColor(sf::Color(60,60,60));
        s.SetScale(1.2,1.2);
    }
    
    //add the [] operator to vector member
    inline std::vector<Field> & operator[](int i) { return mFields[i]; }

    void Render(sf::RenderWindow& win, int tx, int ty, int sc) {
        for (int i=0; i<mSize; i++) {
            for (int a=0; a<mSize; a++) {

                if (sc*mFields[i][a].x+tx<0) continue;
                if (sc*mFields[i][a].x+sc+tx>1280) continue;
                if (sc*mFields[i][a].y+ty<0) continue;
                if (sc*mFields[i][a].y+sc+ty>1024) continue;

                glPushMatrix();
                    glTranslated(a,i,0);
                    glScalef(1,1,0);
                    glColor3f(0.65,0.65,0.65);
                    glBegin(GL_LINES);
                        glVertex3f(0,0,0);
                        glVertex3f(1,0,0);
                        glVertex3f(0,0,0);
                        glVertex3f(0,1,0);
                        if (a<mSize) {
                            glVertex3f(1,0,0);
                            glVertex3f(1,1,0);
                        }
                        if (a<mSize) {
                            glVertex3f(0,1,0);
                            glVertex3f(1,1,0);
                        }
                    glEnd();
                glPopMatrix();
            }
        }
    }

};
»roka« hat folgende Datei angehängt:
Signatur?

dot

Supermoderator

Beiträge: 9 757

Wohnort: Graz

  • Private Nachricht senden

7

14.07.2011, 20:26

Kleiner Tipp: Um die Performance noch ein bisschen zu verbessern kannst du statt einem vector<vector<Field>> einfach ein normales, lineares Array aus Field verwenden und deine 2D-Koordinaten auf Indices in das Array abbilden (einfach das Gitter z.B. Zeile für Zeile hintereinander ablegen). Denn im Moment brauchst du zwei Arrayzugriffe um ein Field zu bekommen statt nur einem. Schreib dir eine einfache Funktion die dir das Field zu einem Satz an Koordinaten liefert und verwend einfach immer die. Der Compiler wird das sowieso inlinen und du bist flexibel was die interne Repräsentation angeht:

C-/C++-Quelltext

1
2
  const Field& operator ()(int x, int y) const { return ...; }
  Field& operator ()(int x, int y) { return ...; }

Btw: Funktionen die in einer Klassendefinition definiert werden sind automatisch inline, dort brauchst du das Schlüsselwort also nicht explizit hinschreiben (du darfst aber natürlich wenn du willst).

Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »dot« (14.07.2011, 20:42)


Werbeanzeige