Pythagorasbaum

Cyianor

Hallo zusammen!

Nachdem ich vor kurzem auf dem Matheplaneten einen interessanten Artikel über Pythagorasbäume gelesen habe, hat mich die Lust gepackt das ganze auch mal zu implementieren. Zunächst hab ich die Java Version wie sie in dem Artikel entwickelt wurde nachgebaut. Die Performance lässt dabei allerdings sehr zu wünschen übrig. Lässt man einen Baum mit 15 Stufen zeichnen so dauert das schon gut und gerne 2 bis 3 Sekunden. Bei 20 Stufen sitzt man auch schonmal fast 10 Sekunden vor einem leeren Bildschirm.
Das und die Tatsache, dass ich endlich einmal C ordentlich lernen wollte hat mich dazu bewegt das ganze Projekt nach C zu portieren. Da stellt sich jetzt natürlich die Frage wie man das Problem mit der Grafikausgabe löst. Hab mich dann (hauptsächlich aus Interesse) dazu entschieden mit Hilfe der SDL ein Fenster zu erzeugen und auf Benutzereingaben zu reagieren aber das komplette Zeichnen selbst mit Algorithmen zu übernehmen. Zunächst hab ich dann einen einfachen Bresenham-Algorithmus implementiert um Linien zeichnen zu können. Das sah dann so aus:
(verschiedene zufällige Grüntöne, 15 Stufen, 0.6 Verhältnis)
Link zu Bild

Das hat mir aber noch nicht gereicht und somit hab ich mich mit gefüllten Polygonen auseinander gesetzt. Hab dann einen Scanlinealgorithmus implementiert und kann jetzt schöne ausgefüllt Quadrate zeichnen (zufällige Farbe, 5 Stufen, 0.3 Verhältnis) Bild

Die Performance unter C hat mich auf jedenfall überzeugt für dieses Projekt erstmal nicht mehr zu Java zurückzugehen. Ich hab auf meinem MacBook (2,0 Ghz DualCore, 2 GB RAM) mit der Wireframe Version erst ab Stufe 17 eine ganz leichte Verzögerung. Auch 20 Stufen werden innerhalb von knapp 1 Sekunde gezeichnet. Die Version mit gefüllten Polygonen ist ein klein wenig langsamer. Leichte Rechenpause ab Stufe 15 und knapp 2 Sekunden Wartezeit für 20 Stufen. Nachdem Java seine Polygone auch ohne Antialiasing zeichnet ist meine zweite Version ziemlich gut vergleichbar mit dem was ich unter Java hatte und da siegt C einfach mal um Längen.

Wer dem Projekt gerne mal unter die Haube schauen würde kann sich den Source Code runterladen. Auf Windows und Linux können die Dateien SDLmain.h und SDLmain.m einfach weggelassen werden. Auf Mac OS X werden diese benötigt. Einzige Abhängigkeit des Programms ist die SDL.
Ansonsten ist noch drauf zu achten, dass das Programm dem C Standard C99 entspricht. Beim gcc muss man also -std=c99 einstellen, damit ordentlich compiliert wird. Was man bei Visual C++ einstellen muss weiß ich leider nicht.

Für die nächste Version will ich Unterstützung für Transparenz und Farbverläufe einbauen.

Würde mich sehr über Kommentare freuen und wäre super wenn auch mal jemand den Code auf Windows oder Linux testen könnte

Schönen Gruß,
Cyianor

[EDIT]
Hier gibts den aktuellen Source Code (ver. 0.2.1). Es gibt mittlerweile Projektdateien für Xcode 3.2 und Dev-C++ und es ist auch ein Makefile (nicht getestet, da kein Linux vorhanden. Wäre super wenn das jemand testen könnte!) dabei. Ein Projekt für Visual C++ hab ich leider nicht hingekriegt, der Compiler von MVC++ wehrt sich und mag kein C99. Hat mich zumindestens momentan dazu bewogen kein Projekt für MVC++ zu erstellen, da mir der Arbeitsaufwand nicht in Relation zum Gewinn steht, da es ja immerhin auch Dev-C++ und MinGW gibt (oder auch Code::Blocks und MinGW), die mit C99 Code wunderbar klar kommen. In Dev-C++ ist es so eingestellt, dass die SDL Entwicklerdateien im selben Ordner liegen wie der PythTree Ordner (aber nicht IM PythTree Ordner), kann aber natürlich auch verstellt werden.

Blue-Tiger

Okay. Erstmal Respekt, die Screenshots schauen sehr gut aus! Hut ab, als erstes Projekt in C ist das sehr, sehr gut gelungen.

Ich hab mir den Code mal angeschaut und ihn unter Linux (64 bit, GCC 4.4.1) kompiliert. War nicht ganz unkompliziert, da ein Code Fehler enthaelt. Ausserdem hab ein paar Verbesserungsvorschlaege:

in DrawRecursivePythTree legst du das vertices-Array dynamisch an (mittels calloc), obwohl du genau weisst, dass das Array 4 gross ist. Das ist ineffizient! Wenn die Array-Groesse bereits im Voraus bekannt ist, kannst du das Array statisch anlegen, das ist wesentlich schneller als calloc/free!
Du hast Bubblesort selbst implementiert. Das ist (a) kein schneller Sortieralgorithmus, aber viel wichtiger (b) hat C seine eigene Sortierroutine, qsort. Es ist ungewoehnlich/unueblich, dass jemand seine eigene Routine schreibt. Nimm naechstes mal qsort, das spart dir Arbeit (und ist effizienter als Bubblesort ).
du verwendest makros. Das macht man heutzutage nicht mehr (besonders wo du doch C99 benutzt). Benutze Inline-Funktionen!
Wenn du willst, dass andere Leute deinen Code testen, mach ihnen doch das Leben einfacher und leg ein Makefile bei!
in basic_drawing.h fehlt 1 Inklude-Datei: du musst stdint.h einbinden (fuer int32_t, uint32_t, etc.)
in basic_drawing.c fehlt 1 Inklude-Datei: du musst stdlib.h einbinden (fuer calloc)
Ausserdem meckert der GCC, weil das #endif am Ende von util.h noch extra unnoetigen Text enthaelt.

(Manche der Fehler sind dir vllt. nicht aufgefallen weil eine IDE z. B. stdlib.h automatisch inkludiert (oder ein Compiler so eingestellt ist dass er das tut), etc.)
Wenn man das mal beseitigt hat laesst sich der Code problemlos kompilieren und das Programm funktioniert einwandfrei. Und sieht wie gesagt gut aus. Hut ab!

Edit: wenn dich die genauen Fehlermeldungen interessieren:

tom@blulap:~/jedi/pt$ gcc -std=c99 -c basic_drawing.c -o basic_drawing.o
In file included from basic_drawing.c:9:
basic_drawing.h:20: error: expected specifier-qualifier-list before ‘int32_t’
basic_drawing.h:30: error: expected specifier-qualifier-list before ‘uint8_t’
basic_drawing.h:34: error: expected specifier-qualifier-list before ‘uint32_t’
basic_drawing.h:40: error: expected declaration specifiers or ‘...’ before ‘int32_t’
[... und noch viele Folgefehler ...]

tom@blulap:~/jedi/pt$ gcc -std=c99 -c basic_drawing.c -o basic_drawing.o
In file included from basic_drawing.c:10:
util.h:15:8: warning: extra tokens at end of #endif directive
basic_drawing.c: In function ‘DrawFilledPolygon’:
basic_drawing.c:85: warning: implicit declaration of function ‘calloc’
basic_drawing.c:85: warning: incompatible implicit declaration of built-in function ‘calloc’
basic_drawing.c:113: warning: implicit declaration of function ‘free’
basic_drawing.c:113: warning: incompatible implicit declaration of built-in function ‘free’

Cyianor

Hey Blue-Tiger!
Erstmal vielen Dank für die Arbeit die du dir gemacht hast!

Ich hab mir deine Verbesserungsvorschläge zu Herzen genommen und die Fehler ausgebessert und eine Sourcecode Version mit Xcode Projekt, Makefile und Dev-C++ Projekt hoch geladen.

Ich hab versucht auch ein Visual C++ Projekt zu erstellen und richtig einzustellen aber hab nach ner knappen Stunde aufgegeben nachdem ich feststellen musste, dass MVC++ wohl einfach kein C99 mag (ist ja anscheinend auch nicht implementiert). Deshalb gibt es jetzt momentan nur ein Projekt für Dev-C++, da diese IDE standardmäßig mit dem MinGW ausgeliegert wird und da es sich dabei ja auch um den gcc handelt kompiliert der meinen Code ohne irgendwelche Zicken

Einzige Mehrarbeit die man auf Windows zu leisten hat ist, dass die SDL Entwicklerdateien im selben Ordner sein müssen wie der PythTree Ordner. Oder man ändert die eingestellten Pfade im Dev-C++ Projekt. Ist auch keine große Arbeit.

Ein kleiner Hinweis noch zur Linux Version:
Da Mac OS X mit Frameworks arbeitet konnte ich das Makefile nicht testen (hab hier nirgendwo Linux). Ich hab es also mal so aufs gerate Wohl geschrieben und hoffe das es funktioniert. Kann aber keine Garantie dafür geben.

Ansonsten gibt es keine bemerkenswerten Änderungen.

Ganz ohne Fortschritt ist mein Projekt aber auch nicht gewesen. Ich möchte ja Farbverläufe einbauen und da ich das nicht in meinem Programm ausprobieren wollte hab ich mir eine Testanwendung geschrieben anhand derer ich meine Funktion zum Erstellen von Farbverläufen (zunächste gabs nur lineare Farbverläufe und dann auch noch gewichtete) testen konnte. Gibt natürlich auch hier wieder einen Screenshot: Schwarz nach Weiß, 30% Gewichtung nach rechts und Braun nach Grün, 20% Gewichtung nach rechts

Das funktioniert so weit schon ganz gut aber ich bin mir nicht sicher ob es nicht vlt noch elegantere Lösungen gibt. Da ich im Internet nichts brauchbares gefunden habe, hab ich mir selbst ausgedacht wie man die Farbverläufe realisieren könnte. Lineare Farbverläufe hab ich mir so überlegt, dass man eine Startfarbe und eine Endfarbe angibt und in wie vielen Schritten man den Farbverlauf denn gerne hätte. Dann wird für jede Farbe der Unterschied von der Start- zur Endfarbe berechnet und dieser Unterschied durch die Anzahl der Schritte geteilt. Und das liefert dann ein Array mit so vielen Elementen wie angegebenen Schritten zurück.

Um gewichtete Farbverläufe zu berechnen geh ich ähnlich vor:
Ich betrachte den ganzen Farbverlauf dabei als ein Intervall von 0% bis 100%. Hat man nun einen linearen Farbverlauf so ist die Gewichtung 50%, da keine Farbe bevorzugt wird und sich der Mittelwert der beiden Farben genau in der Mitte des Farbverlaufs befindet. Ist die Gewichtung größer oder kleiner als 50% so verschiebt sich der Mittelwert. Ist die Gewichtung beispielsweise 80% so wird der Mittelwert erst nach 80% aller Schritte erreicht und der Verlauf vom Mittelwert zum Endwert erfolgt in 20% aller Schritte.
Ich es also im Prinzip auf zwei lineare Farbverläufe heruntergebrochen. Ist c dabei die Gewichtung (0 <= c <= 1) und steps die Gesamtanzahl der Schritte die der resultierende Farbverlauf haben soll, dann berechne ich den Mittelwert, berechne einen linearen Verlauf vom Startwert zum Mittelwert in c * steps Schritten und einen zweiten linearen Verlauf vom Mittelwert zum Endwert in (1 - c) * steps Schritten. Dann füge ich die beiden Farbverläufe in einer for - Schleife zu einem einzelnen Verlauf zusammen.

Ist das so sinnvoll wie ich das mache oder löst man das normalerweise anders/effizienter?

So, das wars von mir für heute.

Hier noch der Link zum aktuellen SourceCode (ver. 0.2.1) (Bin auf .tar.gz umgestiegen. Sollte aber unter Windows mit WinRAR auch leicht zu öffnen sein.)

Schönen Gruß,
Cyianor

Arkus

Man sieht es nicht wirklich, aber wenn du dir das ganze mal als Graph vorstellst (x Achse: Position im Verlauf, y Achse: Farbe) hast du einen Knick drin. du könntest aber z.B. auch eine Parabel benutzen, oder allgemein jede beliebige Funktion die von 0/0 nach 1/1 verläuft.
Aber ich meine, so isses ja in Ordnung und sieht ganz gut aus.

Cyianor

Hallo Arkus!

Ich hab mir die Idee mit der Parabel für den gewichteten Farbverlauf mal durch den Kopf gehen lassen. Komm aber zu keiner Lösung. Wenn ich mir das als Graph vorstelle hab ich ja drei Punkte für die Farbe: (w ist dabei die Gewichtung mit 0 <= w <= 1)

Anfangswert der Farbe bei 0
Mittelwert bei w
Endwert bei 1

Dann betrachte ich die Normalform der Parabelgleichung:

y = a * ( x - b ) ^ 2 + c

a: Streckungs-/Dehnungsfaktor
b: Achsenverschiebung auf Gewichtungsachse (da der Verlauf ja immer von 0 bis 1 geht ist b = 0)
c: Achsenabschnitt auf Farbachse

Da der Farbwert bei 0 immer der Anfangswert ist gilt ja logischerweise c = Anfangswert. Um jetzt a zu bestimmen muss man ja einen Punkt einsetzen bei dem x != 0 gilt.

Ich hab also zwei Möglichkeiten:

Mittelwert = a * w^2 + Anfangswert <=> a = (Mittelwert - Anfangswert) / w^2

oder

Endwert = a * 1^2 + Anfangswert <=> a = Endwert - Anfangswert

Damit die Parabel durch alle drei Punkte geht müsste ja dann gelten:

Endwert - Anfangswert = (Mittelwert - Anfangswert) / w^2
wobei gilt Mittelwert = 1/2 * (Anfangswert + Endwert).

Diese Gleichung ist aber nicht für alle Anfangs- und Endwerte und alle w mit 0 <= w <= 1 wahr. Also kann ich meinen gewichteten Farbverlauf nicht für beliebige Farbwerte und Gewichtungen als eine durchgehende Parabel beschreiben. Hat da noch jemand eine Idee? Ich steck da momentan ein wenig fest.

Schönen Gruß!