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!

2D Szenengraph und Transformationen

Werbeanzeige

Endgegner

Treue Seele

  • »Endgegner« ist der Autor dieses Themas

Beiträge: 209

  • Private Nachricht senden

1

07.02.2012, 18:50

2D Szenengraph und Transformationen

Ich möchte einen simplen 2D Szenengraphen schreiben. Der Graph soll aus Blatt- und Gruppenknoten bestehen und in einer Baumstruktur organisiert sein. Ich habe etwas Pseudocode beigefügt, der vermitteln soll, wie ich mir das Ganze vorstelle.

Meine Frage ist nun: Ist mein Ansatz richtig und auch empfehlenswert?

Vor allem bei den Zeilen 20 bis 23 bin ich mir unsicher (Transformationsmatrix, Position, Skalierung, Rotation). Ist es sinnvoll, bspw. neben der lokalen Position auch die globale in dem Struct zu speichern? Oder berechnet man das besser on-the-fly mithilfe der Transformationsmatrix? Gehört die Transformationsmatrix überhaupt an diese Stelle? Ich denke schon, denn dadurch könnte ich z.B. jederzeit eine beliebige Koordinate in das lokale Koordinatensystem eines Gruppenknotens übertragen. Enthielte der Gruppenknoten keine Matrix, wäre das schon aufwendiger. Aber vielleicht überschätze ich den Nutzen auch.

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

// Bezeichnet den Typ eines Szenengraph-Knotens.
enum scene_node_type
{
    ENTITY,
    SPRITE
    // ...
};

// Basisstruktur aller Knoten eines Szenengraphen.
struct scene_node_base
{
    enum   scene_node_type type;
    struct scene_node_base *parent, *next_sibling;
};

// Basisstruktur aller Gruppenknoten eines Szenengraphen.
struct scene_node_group_base
{
    struct scene_node_base  base;
    struct transform_matrix transform;
    struct vector2          local_pos,   global_pos;
    struct vector2          local_scale, global_scale;
    float                   local_rot,   global_rot;
    struct scene_node_base  *first_child;
};

// Ein Gruppenknoten, der ein Levelobjekt zusammenfasst.
// Kann aus mehreren Sprites (siehe unten), untergeordneten Entitys usw. bestehen.
struct scene_node_entity
{
    struct scene_node_group_base base;
    // ...
};

// Ein Blattknoten, der eine zu zeichnende Bitmap referenziert.
struct scene_node_sprite
{
    struct scene_node_base base;
    // ...
};

Powerpaule

Treue Seele

Beiträge: 162

Wohnort: Berlin

Beruf: Softwareentwickler

  • Private Nachricht senden

2

07.02.2012, 22:22

Also dein Ansatz ist durchaus richtig, allerdings nicht so ganz empfehlenswert ; ) - Du benutzt ja C++, oder? Dann solltest du dich nicht mit so einer Pseudo-Vererbung aus lauter Einzelobjekten (die auch
noch structs sind) herumschlagen, sondern richtige Vererbung nehmen, diesich ja für eine Baumstruktur bestens eignet.
Im Objekt brauchst du nur die Transformationsmatrix zu speichern, das ist also auf jeden Fall richtig, du multiplizierst dann einfach beim Rendern die Transformationsmatrix des aktuellen Objekts auf die bisherige Transformation auf.

Das Ganze könnte dann so aussehen:

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

// abstraktes Basis-Element
class Element {
public:
   virtual void render(MatrixStack) = 0;

   void setTransform(Matrix m) {...}
   Matrix getTransform() const {...}

protected:
   Matrix transform;
};

// Gruppenelement
class ElementGroup: public Element {
public:
    virtual void render(MatrixStack) {
    MatrixStack.push(transform);

    foreach (Element e in elemente) { 
        el.render(MatrixStack);
        }

        MatrixStack.pop();
   }

    void addElement(Element e) {
        elements.push_back(e);
    }

protected:
    std::vector<Element> elemente;
};

// bspw ein sprite
class Sprite : public Element {
public:
   virtual void render(MatrixStack) {
    MatrixStack.push(transform);
    // render bitmap ...
    MatrixStack.pop();
    }
};


So schreibst du einfach für alle deine Objekttypen eine Klasse, und kannst die alle in eine beliebige Gruppe schmeißen bzw dort weitere Gruppen reinpacken. Den Typ kannst du dann so weglassen.

Endgegner

Treue Seele

  • »Endgegner« ist der Autor dieses Themas

Beiträge: 209

  • Private Nachricht senden

3

10.02.2012, 16:07

Ich schreibe in C - Entschuldigung, dass ich das nicht erwähnt habe. Die konkrete Programmierung war mir hierbei eher zweitrangig, deswegen habe ich die Sprache mal außen vor gelassen.

Danke für dein Beispiel!
Mal sehen, ob ich es auch richtig verstanden habe: Die Matrix "transform" enthält die lokale Transformation eines Elements. Auf dem Matrixstapel liegt die globale Transformation, also das Produkt aus allen Transformationen, die sich auf dem Stapel befinden, inklusive der lokalen Transformation des aktuellen Elements.

Eine Frage hätte ich dann aber noch: Wie berechne ich (beispielsweise) den euklidischen Abstand zwischen zwei Elementen? Dafür müsste ich ja entweder die globalen Koordinaten beider Elemente kennen oder die Koordinaten des einen Elements in das Koordinatensystem des anderen Elements übertragen. Ich weiß allerdings nicht, wie ich aus der globalen Transformationsmatrix die globalen Koordinaten ableiten kann. Muss ich dafür die Matrix zerlegen?

In dem Zusammenhang möchte ich erwähnen, dass ich die Transformationsfunktionen von Allegro 5 verwende (bzw. vorhabe, das zu tun). Eine decompose-Funktion ist leider nicht dabei. Gibt es noch einen anderen, vielleicht sogar besseren Weg, um an die globalen Koordinaten zu gelangen? Ansonsten müsste ich mich wohl selbst an einer decompose-Funktion versuchen.

Jonathan_Klein

Community-Fossil

Beiträge: 3 820

  • Private Nachricht senden

4

10.02.2012, 16:33

Mach dir klar, was genau die Matrix macht, wenn du einen Vektor damit multiplizierst, nämlich Vektoren von dem einen Raum ('Koordinatensystem'), in den anderen Raum transformieren. Möchtest du also Wissen, wie weit der Ursprung (also (0|0) im 2D Fall) von Raum A von dem Raum B entfernt ist, brauchst du eine Matrix, die von A nach B transformiert, denn Vektoren aus verschiedenen Räumen kannst du nicht sinnvoll miteinander vergleichen.
Wenn du also im 2D Raum 3x3 Matrizen verwendest, musst du nur jeweils die Vektoren (0|0|1) (da es Positionen und keine Richtungen sind) mit der Objektmatrix multiplizieren (die ja von lokalen Koordinaten nach globale Koordinaten abbildet) und kannst diese Punkte im globalen Raum miteinander vergleichen.
Lieber dumm fragen, als dumm bleiben!

Endgegner

Treue Seele

  • »Endgegner« ist der Autor dieses Themas

Beiträge: 209

  • Private Nachricht senden

5

11.02.2012, 19:34

Stimmt, das ist einleuchtend. Danke für die Erklärung.

In die Transformationsmatrizen muss ich mich noch einfinden. Ich habe mir zwar vor einiger Zeit ein Buch über solche Themen gekauft (Mathematics for 3D Game Programming and Computer Graphics), musste allerdings feststellen, dass ich wohl nicht zur Zielgruppe dieses Buchs gehöre: Der Inhalt ist ziemlich harter Tobak. Ich werde mich mal nach einer nicht ganz so theoretischen Alternative umschauen.

dot

Supermoderator

Beiträge: 9 757

Wohnort: Graz

  • Private Nachricht senden

6

11.02.2012, 20:19

Gibt es irgendeinen besonderen Grund warum du C verwendest? Ich würde dir C++ sehr zu Herzen legen. Es gibt eigentlich keinen Grund C zu verwenden wenn man auch C++ verwenden könnte. Selbst wenn man in C++ dann nur prozedural programmiert, hat man doch wesentliche Vorteile gegenüber C (templates, overloading, namespaces, inline, ...)

Dein Buch kann ich übrigens nur empfehlen, auch wenn es vielleicht "harter Tobak" ist. Ansonsten gibts noch den 3D Math Primer (nun offenbar auch als 2nd Edition). Den hab ich aber selbst nicht gelesen.
m4studios

Dieser Beitrag wurde bereits 5 mal editiert, zuletzt von »dot« (11.02.2012, 20:27)

Jonathan_Klein

Community-Fossil

Beiträge: 3 820

  • Private Nachricht senden

7

11.02.2012, 22:15

Lineare Algebra ist nun einmal schwer, damit muss man sich abfinden :D
Selbst wenn man das Gefühl hat, ein recht gutes intuitives Verständnis von der ganzen Sache zu haben, kommt man ums "harte Rechnen" nicht drum herum. Ich hatte es schon relativ oft, dass ich irgendwelche Probleme mit Shadern hatte, die einfach falsch Ergebnisse lieferten. Obwohl die grundsätzliche Rechnung richtig war, passieren leicht Fehler im Detail, so dass es wirklich am allerbesten ist, alles mathematisch korrekt aufzuschreiben und dann Schritt für Schritt zu überprüfen.
Letztendlich sind sehr viele Berechnungen in der Computergraphik von der Idee her recht einfach, aber man muss wirklich die Rechenmethoden verinnerlicht haben, weil es eben so unglaublich viele Stellen gibt, an denen man Kleinigkeiten falsch machen kann, die einem dann das gesamte Programm zerschießen. Einfach nur auf gut Glück losprogrammieren hat da wenig Sinn.
Lieber dumm fragen, als dumm bleiben!

Endgegner

Treue Seele

  • »Endgegner« ist der Autor dieses Themas

Beiträge: 209

  • Private Nachricht senden

8

12.02.2012, 18:28

@dot

Mit C komme ich besser zurecht als mit C++. An C gefallen mir besonders die geringe Abstraktion und der kleine Umfang der Sprache. Objektorientierte und generische Programmierung finde ich an sich praktisch, aber ich kann mich nicht damit anfreunden, wie C++ diese Sprachelemente in C integriert hat. Ich finde, sie fügen sich nicht nahtlos in die Sprache ein und machen sie dadurch komplexer als nötig. Wenn ich objektorientiert oder generisch programmieren wollte, würde ich mich vermutlich für eine andere Sprache als C++ entscheiden. Ich schreibe aber lieber einigermaßen guten C-Code als prozedurales C++.

Inlining gibt es übrigens seit C99 auch in C. Bislang gab es bei mir allerdings noch keine Notwendigkeit dafür.

Und bzgl. des Buchs: Inhaltlich ist das Buch auch wirklich toll. Die Themen sind interessant und werden ausführlich und präzise dargelegt. Mir ist aber der Stil insgesamt zu theoretisch. Bei mir darf es auch mal etwas verspielter sein. ;)

Den 3D Math Primer werde ich mir mal ansehen. Positiv aufgefallen sind mir die toten Schafe im Beispielkapitel.

@Jonathan

Jap, man sollte schon wissen, was man tut. Lineare Algebra ist eigentlich auch gar nicht so schwierig, wenn man für sich selbst den richtigen Zugang dazu gefunden hat. Für dot war das womöglich das genannte Buch, für mich sind es vielleicht die toten Schafe. Auf jeden Fall gehören die Matrixtransformationen zu den Themen, die ich gerne besser verstehen möchte, bevor ich sie im großen Stil einsetze.

Sylence

Community-Fossil

Beiträge: 1 663

Beruf: Softwareentwickler

  • Private Nachricht senden

9

13.02.2012, 12:56

Zitat von »Endgegner«

@dot

Mit C komme ich besser zurecht als mit C++. An C gefallen mir besonders die geringe Abstraktion und der kleine Umfang der Sprache. Objektorientierte und generische Programmierung finde ich an sich praktisch, aber ich kann mich nicht damit anfreunden, wie C++ diese Sprachelemente in C integriert hat. Ich finde, sie fügen sich nicht nahtlos in die Sprache ein und machen sie dadurch komplexer als nötig. Wenn ich objektorientiert oder generisch programmieren wollte, würde ich mich vermutlich für eine andere Sprache als C++ entscheiden. Ich schreibe aber lieber einigermaßen guten C-Code als prozedurales C++.

Inlining gibt es übrigens seit C99 auch in C. Bislang gab es bei mir allerdings noch keine Notwendigkeit dafür.


Genau das meinte Dot doch. Du kannst weiterhin so programmieren, wie du es gewohnt bist, aber auch noch mehr möglichkeiten.
Strings und dynamische arrays vereinfachen dir das Leben zum Beispiel enorm. An deinem Programm wie es jetzt schon ist müsstest du ja nichts ändern und an deinen Gewohnheiten auch nicht.
Du kannst C++ ja halt auch einfach als C mit mehr Funktionen benutzen.

Endgegner

Treue Seele

  • »Endgegner« ist der Autor dieses Themas

Beiträge: 209

  • Private Nachricht senden

10

16.02.2012, 01:43

dots Vorschlag habe ich schon verstanden, Sylence. Aber wie ich in meinem letzten Post schon angedeutet habe, widerstrebt es mir, C++ als "erweitertes C" zu benutzen. In dieser Hinsicht bin ich ein Sprachpurist. Die Umstände, die sich daraus ergeben, stören mich allerdings nicht. Anstatt des std::vector verwende ich beispielsweise mein eigenes Modul für dynamische Arrays. Gleiches gilt für andere gängige Datenstrukturen. Diese Module sind simpel, genügen aber meinen Ansprüchen.

Werbeanzeige

Ähnliche Themen