spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

Ich bin mir nicht sicher, ob ich dein Anliegen richtig verstehe. Was genau meinst du mit der Schreibweise A-B-C-D-A und A-D, B-C-D, B-A? Was möchtest du letztlich mit dieser Optimierung erreichen? Speicher einsparen? Ist diese Optimierung für dein Problem wirklich nötig, oder ist das rein theoretisch?

Deine Frage hat mich aber zum Nachdenken gebracht. Wenn die Darstellungen ABC, BCA und CAB jeweils dasselbe Dreieck beschreiben, dann gibt es da eine gewisse Redundanz. Kann man diese Redundanz irgendwie wegkriegen und dadurch ein bisschen Speicher einsparen?

Zitat von »Elmi«

Für die interne Datenverwaltung und die Zeichenfunktione einer Software ist der Unterschied allerdings deutlich größer, besonders wenn das bei Polygonen mit deutlich mehr Ecken auftritt.

Also wenn das Polygon mit OpenGL oder Direct3D gerendert wird, ist doch die Reihenfolge der Vertices eh quasi vorgegeben. Die Effizienz sollte sich mit der Reihenfolge nicht groß ändern, aber bei der 'falschen' Reihenfolge ist das Ergebnis halt kaputt.

Um was für eine Software geht es denn überhaupt und aus welche Quelle kommen die Daten? Eine Beschreibung wie "A-D, B-C-D, B-A" erscheint mir absolut unüblich. Ohne konkrete Beispiele hört sich das für mich wie ein theoretisches Problem an, und da fällt es schwer praktische Lösungen vorzuschlagen.

Ach so, jetzt glaube ich es verstanden zu haben. Es geht nur um die Linienzüge, oder? A-B-C-D-A bedeutet: Zeichne eine Linie von A nach B, dann von B nach C, ... so wie GL_LINE_STRIP in OpenGL. Analog für Dreiecke gibt es ja Triangle Strips (GL_TRIANGLE_STRIP). Dazu gibt es Verfahren, wie man die Geometrie entsprechend optimieren kann. Google mal nach "triangle strip optimization". Vielleicht kannst du diese Verfahren auf Line Strips übertragen.

Wenn du geschlossene Polygone brauchst, was machst du bei sowas hier?

Zitat von »Elmi«

Dabei beschreibt mein Beispiel einmal den Optimalzustand "A-B-C-D-A" für ein Rechteck und einmal das, was man z.B. bekommt, wenn man DXF- oder SVG-Dateien importiert. Je nach dem, was der Zeichner sich gedacht hat oder wie oft an einer Zeichnung schon herumgebastelt wurde, kann dabei nämlich so ein verhackstücktes Zeug herauskommen.

Interessant, ich hätte jetzt nicht gedacht dass irgendwelche Tools so eine Grütze exportieren. Ich kann mir auch kaum vorstellen, dass die Reihenfolge fürs Anzeigen wirklich egal ist, ich denke mir wenn man z.B. in Inkscape ein Polygon mit einer Farbe oder Muster füllen will, würde man die Punkte auch wirklich sortiert haben wollen. Gut vorstellbar, dass das dann intern auch passiert, aber eigentlich merkwürdig wieso die es dann nicht vernünftig exportiert wird...

Ich glaube ich würde tatsächlich dazu tendieren das Sortieren von Hand zu schreiben. Es sollte nicht besonders schwierig sein, und wenn es sich z.B. um ein C++ Projekt handeln sollte willst du vermutlich lieber einmal Code von Hand schreiben als für den Rest des Projektes eine externe Abhängigkeit pflegen.
Ich habe neulich erst Gaussian-Smoothing von Hand in C++ implementiert, das waren auch nur 30 Zeilen und insgesamt vermutlich weniger Arbeit als eine externe Bibliothek dafür zu finden, einzubinden und zu verwenden. Je nachdem was so eine Bibliothek für ein Interface hat ist es ja auch gar nicht so einfach die eigenen Datenstrukturen darauf zu mappen, der Vorteil des vorhandenen Codes wird bei so kleinen Problemchen also echt schnell wieder zunichte gemacht. Ich würde da gar nicht so lange drüber nachdenken und es einfach schnell von Hand machen. Wie man das am effizientesten Implementiert ist ja vielleicht auch eine Interessante Diskussion, aber da es vermutlich nur einmal durchlaufen muss, ist Effizienz vermutlich sowieso ziemlich zweitrangig...