komische Artefakte in primitivem Weichzeichner

[J. T. (chaoskind)]

Moin,

ich spiel mal wieder mit Mandelbroten herum. Dabei hab ich mich schon 
immer über die "Pixeligkeit" geärgert.

Dazu hab ich nun "Subpixel" berechnet (1 Pixel wird in 3mal3 Subpixel 
zerlegt) und von diesen Subpixeln den Durchschnitt berechnet.
Hierzu zähle ich die Anzahl an Durchläufen, die es braucht bis der 
Betrag größer 2 wird, und bilde diese Anzahl auf eine Farbtabelle ab.

Ich vermute, das ist eine primitive Form vom Weichzeichner. Nun 
entstehen aber komische gelbe Artefakte, um das "Zentrum" von dem 
Mandelgedöns herum, siehe Bild "highres". Bei "lowres" sieht man den 
selben Auschnitt in der selben Vergrößerung. Wie können so markante 
Farbunterschiede entstehen, wenn ich den Durchschnitt bilde? Hat da 
jemand eine Erklärung für?

Der Sourcecode ist im Anhang, ist aber ziemlich unübersichtlich und 
voller anderem Krams....

MfG Chaos

[DerEinzigeBernd (Gast)]

> Wie können so markante Farbunterschiede entstehen, wenn
> ich den Durchschnitt bilde?

Könnte am Quelltext liegen, in dem ich den Algorithmus für die 
Mittelwertbildung beim Drübergucken nicht sehe.

Worüber bildest Du den Mittelwert, etwa über die Iterationsanzahl und 
nicht über die berechneten Pixel?


Was soll "resistence" sein? Meinst Du "resistance"? Und was hat das 
wiederum mit Mandelbrot-Mengen zu tun?

[J. T. (chaoskind)]

DerEinzigeBernd schrieb:
> Worüber bildest Du den Mittelwert, etwa über die Iterationsanzahl und
> nicht über die berechneten Pixel?

Ich lege mein Pixelarray über die komplexe Ebene, dann nimm ich mir das 
erste Pixel, zerlege es wiederrum in seine Subpixel, ich berechene die 
Farbwerte für die Subpixel, addiere sie auf und dividiere durch die 
Anzahl der Subpixel und erhalte den Farbwert für das Pixel.

 C.Realteil = xMin + ( ( (xMax - xMin) / (BildgroesseX*3) ) * ((Xakt*3)) );
            C.Imaginaerteil = yMin + ( ( (yMax - yMin) / (BildgroesseY*3) ) * ((Yakt*3)-1) );
            Subpixel += ResistenceCheck(MaxResis, C);

Mit der Resistenz bezeichne ich meine Funktion, die überprüft, wie oft 
iteriert werden kann, ohne dass der Betrag größer 2 wird. Ich hatte 
irgendwo mal den Begriff "multiplikative Resistenz" für einen ähnlichen 
iterrativen Prozess gehört und fand den Begriff irgendwie schön.

[J. T. (chaoskind)]

Inzwischen werden die Bilder recht ansehnlich, finde ich.

Wobei ich es mit den Subpixeln noch nicht so richtig hinbekomme....

Noch mach ich es zu Fuß,

           C.Realteil = xMin + ( ( (xMax - xMin) / (BildgroesseX*5) ) * ((Xakt*5)-2) );
            C.Imaginaerteil = yMin + ( ( (yMax - yMin) / (BildgroesseY*5) ) * ((Yakt*5)-2) );
            Subpixel += ResistenceCheck(MaxResis, C);

            C.Realteil = xMin + ( ( (xMax - xMin) / (BildgroesseX*5) ) * ((Xakt*5)-2) );
            C.Imaginaerteil = yMin + ( ( (yMax - yMin) / (BildgroesseY*5) ) * ((Yakt*5)-1) );
            Subpixel += ResistenceCheck(MaxResis, C);

            C.Realteil = xMin + ( ( (xMax - xMin) / (BildgroesseX*5) ) * ((Xakt*5)-2) );
            C.Imaginaerteil = yMin + ( ( (yMax - yMin) / (BildgroesseY*5) ) * ((Yakt*5)) );
            Subpixel += ResistenceCheck(MaxResis, C);

            C.Realteil = xMin + ( ( (xMax - xMin) / (BildgroesseX*5) ) * ((Xakt*5)-2) );
            C.Imaginaerteil = yMin + ( ( (yMax - yMin) / (BildgroesseY*5) ) * ((Yakt*5)+1) );
            Subpixel += ResistenceCheck(MaxResis, C);

            C.Realteil = xMin + ( ( (xMax - xMin) / (BildgroesseX*5) ) * ((Xakt*5)-2) );
            C.Imaginaerteil = yMin + ( ( (yMax - yMin) / (BildgroesseY*5) ) * ((Yakt*5)+2) );
            Subpixel += ResistenceCheck(MaxResis, C);

dass ich dann bei 5 Subpixeln 5 von den 5er Blöcken da stehen habe...


Mit der Schleife ist irgendwo der Wurm drin, da wird alles so gefärbt, 
als wäre nach einer Iteration schon Ende.

    SubX = -SubRes/2;
    SubY = -SubRes/2;
    while(Xakt < (BildgroesseX * SubRes))
    {
        while(Yakt < (BildgroesseY * SubRes))
        {
            Subpixel = 0;

            while(SubX < SubRes/2 )
            {
                while(SubY < SubRes/2)
                {
                    C.Realteil = xMin + ( ( (xMax - xMin) / (BildgroesseX*SubRes) ) * ((Xakt*SubRes)-SubX) );
                    C.Imaginaerteil = yMin + ( ( (yMax - yMin) / (BildgroesseY*SubRes) ) * ((Yakt*SubRes)-SubY) );
                    Subpixel += ResistenceCheck(MaxResis, C);



                    SubY++;
                }
                SubY = SubRes/2;
                SubX++;
            }
            SubX = SubRes/2;

            Subpixel = Subpixel/(SubRes*SubRes);

            if ( Subpixel >= MaxResis )
                {
                    al_draw_pixel (Xakt, Yakt, al_map_rgb(0, 0, 0) );
                }

[J. T. (chaoskind)]

Noch eins in voller Pracht

[J. T. (chaoskind)]

Auch ganz nett, mit zufällig erstellter Farbtabelle. So sieht  man die 
Bereiche der unterschiedlichen "Resistenz" sehr gut.

[J. T. (chaoskind)]

Und nochmal der selbe Bereich wie im Eingangspost, nur mit zufälliger 
Farbtabelle. Wahnsinn wieviel Unruhe in dem Bereich ist, der im 
Eingangspostbild so gleichmäßig grün aussieht. Und das die 
"Zieselierungen" von den lila Dingern zu fehlen scheinen-

[DerEinzigeBernd (Gast)]

Du berechnest also den Mittelwet der "Resistence"-Werte und nicht den 
Mittelwert der darauf bestimmten Farbwerte.

Letzteres dürfte einfacher sein: Einfach eine Bitmap mit neunfacher 
Pixelanzahl (also dreifacher Höhe & Breite) berechnen und die 
RGB-Farbwerte eintragen und dann 9x9-Pixelblöcke aus der Bitmap 
extrahiere und die Mittelung der Farbwerte auf den RGB-Kanälen 
durchführen.

Da könntest Du auch untersuchen, was passiert, wenn Du diese Mittelung 
nicht in konstanten 3x3-Abständen durchführst, sondern in voller 
Auflösung um jeweils ein Pixel verschoben.

[J. T. (chaoskind)]

DerEinzigeBernd schrieb:
> Du berechnest also den Mittelwet der "Resistence"-Werte und nicht den
> Mittelwert der darauf bestimmten Farbwerte.

Das ist ein guter Einwand. Bei der "Resistenz" bleib ich immer nur auf 
ganzen Werten, bei den Farbwerten wären mehr Zwischenwerte möglich. Das 
werd ich wohl nochmal umbauen.

DerEinzigeBernd schrieb:
> Letzteres dürfte einfacher sein: Einfach eine Bitmap mit neunfacher
> Pixelanzahl (also dreifacher Höhe & Breite) berechnen und die
> RGB-Farbwerte eintragen und dann 9x9-Pixelblöcke aus der Bitmap
> extrahiere und die Mittelung der Farbwerte auf den RGB-Kanälen
> durchführen.

Das hatte ich ursprünglich versucht, aber wenn ich Arrays größer 200*200 
erstellt hab, hab ich beim Ausführen immer einen SegmentationError 
bekommen. Dafür muss ich mir auch noch was einfallen lassen. Aber nicht 
mehr heute :D

[J. T. (chaoskind)]

J. T. schrieb:
> Das ist ein guter Einwand.

P.S.
evtl liegt da sogar der Ursprung für die komischen gelben Artefakte...

[DerEinzigeBernd (Gast)]

J. T. schrieb:
> aber wenn ich Arrays größer 200*200
> erstellt hab, hab ich beim Ausführen immer einen SegmentationError
> bekommen.

Worauf lässt Du das laufen? Ist ja wohl kein PC.

Wieviel Speicher hat das, und welche Datentypen verwendest Du für diese 
Arrays? Und wie sind die Arrays definiert?

Du könntest zu Testzwecken Deinen Algorithmus auf einem PC laufen lassen 
und die Bitmap in eine PNG-Datei o.ä. ausgeben.

[J. T. (chaoskind)]

DerEinzigeBernd schrieb:
> Worauf lässt Du das laufen? Ist ja wohl kein PC.

Doch es ist ein knapp 2 Jahre alter Laptop.

DerEinzigeBernd schrieb:
> Wieviel Speicher hat das, und welche Datentypen verwendest Du für diese
> Arrays?

Der hat 16gb RAM. Das sollte eigebtlich für größere Arrays reichen. 
Angedacht waren sie als Int, da ich ja nur mit der Resistenz gerechnet 
hatte.

DerEinzigeBernd schrieb:
> Und wie sind die Arrays definiert?

Zur Zeit ist es ein Allegro-Datentyp, die Leinwand auf die man zeichnet. 
Allegro ist ein lib für Grafikkrams.

DerEinzigeBernd schrieb:
> Du könntest zu Testzwecken Deinen Algorithmus auf einem PC

Tu ich ja, aber es ist schnarchlahm. Je nach dem wie groß der Anteil der 
Punkte ist, die die maximale Anzahl an Iterationen durchlaufen, dauert 
es bos zu 15min, um ein 800*1200 Bild mit 5×5 Subpixeln zu machen.

[DerEinzigeBernd (Gast)]

J. T. schrieb:
> Der hat 16gb RAM. Das sollte eigebtlich für größere Arrays reichen.
> Angedacht waren sie als Int, da ich ja nur mit der Resistenz gerechnet
> hatte.

Wenn es dann zu "segmentation faults" kommt, ist sehr offensichtlich 
irgendwas mit Deinen Arrayzugriffen kaputt. Ein brauchbarer Debugger 
könnte derartige Zugriffe abfangen.

Es kann natürlich auch daran liegen, wie Du diese Arrays anlegst. Als 
statische Variable, als automatische Variable oder mit dynamischer 
Speicherverwaltung?

> dauert es bos zu 15min, um ein 800*1200 Bild mit 5×5 Subpixeln zu machen

Wenn Du einfach nur 'ne Glättung haben willst, ist das nun wirklich 
völlig übertrieben. Statt des neunfachen Rechenaufwandes betreibst Du 
jetzt den 25fachen Rechenaufwand, kein Wunder, daß das dauert.

Tatsächlich sollte schon eine Verdoppelung der Auflösung genügen.

Wenn Du mal wirklich schnelle Algorithmen zur Berechnung von 
Mandelbrotmengen sehen willst, solltesst Du Dir fractint ansehen.
https://www.fractint.org/

[Rolf M. (rmagnus)]

DerEinzigeBernd schrieb:
> Es kann natürlich auch daran liegen, wie Du diese Arrays anlegst. Als
> statische Variable, als automatische Variable oder mit dynamischer
> Speicherverwaltung?

Der Quellcode zeigt, dass es eine automatische Variable ist mit 
großzügigen 32 Bit pro Pixel. Damit wird ein:

J. T. schrieb:
> 800*1200 Bild mit 5×5 Subpixeln

eine stattliche Größe von 800*1200*25*4 Bytes = 93 MB haben, die in der 
Regel nicht in den Stack passen. Default-Größe für den Stack ist auf 
Linux-Systemen 8 MB, auf Windows meines Wissens 1 MB. Daher entweder 
statisch oder dynamisch anlegen.

[J. T. (chaoskind)]

Rolf M. schrieb:
> Der Quellcode zeigt, dass es eine automatische Variable ist mit
> großzügigen 32 Bit pro Pixel. Damit wird ein:

Die 32Bit pro Pixel kommen von der Allegro-Grafiklib. RGBA zu je 8bit.

Rolf M. schrieb:
> eine stattliche Größe von 800*1200*25*4 Bytes = 93 MB haben, die in der
> Regel nicht in den Stack passen

Für ein Bild der Größe natürlich nicht wenig, aber es erscheint mir 
trotzdem winzig, im Vergleich zu den 16gigabytes RAM. Da hat ich nicht 
gedacht, dass da so rumgeknausert wird. Und vor allem muss die Leinwand 
ja auch irgendwo gespeichert sein, und da hatte ich schon welche mit 
über 3000*2000 genutzt. Aber das wird dann vermutlich dynamisch 
gemacht....

Rolf M. schrieb:
> Daher entweder
> statisch

Ich hatte das Array angelegt als:
Bildarray[BildschirmX][BildschirmY];

das ist doch statisch, oder nicht? BildschirmX und Y sind als #define 
angelegt.

DerEinzigeBernd schrieb:
> Tatsächlich sollte schon eine Verdoppelung der Auflösung genügen.

Ich bin mir nicht sicher ob ichs mir einbilde, meine aber die 5fach 
gesubpixelten sehen noch ein wenig besser aus als die 3fachen.

DerEinzigeBernd schrieb:
> Statt des neunfachen Rechenaufwandes betreibst Du
> jetzt den 25fachen Rechenaufwand, kein Wunder, daß das dauert.

Auf der eine Seite, ja sicher, andrerseits hatte ich mal eine ziemlich 
ähnliche Implementierung auf nem DiscoF7 gemacht, das hatte zwar 320mal 
irgendwas Pixel, und da hat er je nach Schwarzanteil im Bild eher 
gefühlte 3-4 Sekunden gebraucht. Und der lief nur 70 oder evtl 120 MHz.
Der Rechner hier ist ein Ryzen7 mit bis zu 4.2GHz. Das sollte doch um 
Größenordnungen schneller laufen. Aber für ein Bild der Größe ohne 
Subpixelung braucht er auch ne knappe Sekunde.

Ich hab mir Mandelbrotvideos angesehen, da fahren sie mit dem Cursor 
übers Mandelbrot und in nem 2ten Fenster wird simultan das zu dem Punkt 
gehörende Julia-Set berechnet und angezeigt, Völlig flüssig. Gut da weiß 
ich natürlich nicht, ob das in Echtzeit gemacht wurde, oder 
gevideotrixt.

[Rolf M. (rmagnus)]

J. T. schrieb:
> Rolf M. schrieb:
>> Der Quellcode zeigt, dass es eine automatische Variable ist mit
>> großzügigen 32 Bit pro Pixel. Damit wird ein:
>
> Die 32Bit pro Pixel kommen von der Allegro-Grafiklib. RGBA zu je 8bit.
>
> Rolf M. schrieb:
>> eine stattliche Größe von 800*1200*25*4 Bytes = 93 MB haben, die in der
>> Regel nicht in den Stack passen
>
> Für ein Bild der Größe natürlich nicht wenig, aber es erscheint mir
> trotzdem winzig, im Vergleich zu den 16gigabytes RAM. Da hat ich nicht
> gedacht, dass da so rumgeknausert wird.

Naja, der Stack ist nicht dafür gedacht, da große Datenmengen zu 
speichern, und da der für jeden Thread in jedem Programm einmal benötigt 
wird, würde sehr viel Platz verschwendet, wenn man den extra groß machen 
würde, nur für den Fall, dass doch mal jemand da 100 MB drin speichern 
will.

> Und vor allem muss die Leinwand ja auch irgendwo gespeichert sein, und
> da hatte ich schon welche mit über 3000*2000 genutzt. Aber das wird dann
> vermutlich dynamisch gemacht....

Ja. Dynamisch kannst da auch 50 GB allokieren, wenn du genug Platz hast. 
Abgesehen davon könnte man dann auch beim Start als Parameter übergeben, 
wie groß das Bild werden soll, statt für jede Änderung der Auflösung neu 
compilieren zu müssen.

> Rolf M. schrieb:
>> Daher entweder
>> statisch
>
> Ich hatte das Array angelegt als:
> Bildarray[BildschirmX][BildschirmY];
>
> das ist doch statisch, oder nicht?

Kommt drauf an, wo du das getan hast. Wenn es wie bei dem 
auskommentierten Teil von oben in einer Funktion ist, dann nicht. Du 
musst dann entweder static davor schreiben oder es außerhalb der 
Funktion definieren.

> Ich hab mir Mandelbrotvideos angesehen, da fahren sie mit dem Cursor
> übers Mandelbrot und in nem 2ten Fenster wird simultan das zu dem Punkt
> gehörende Julia-Set berechnet und angezeigt, Völlig flüssig. Gut da weiß
> ich natürlich nicht, ob das in Echtzeit gemacht wurde, oder
> gevideotrixt.

Diese Berechnungen lassen sich hervorragend parallelisieren und damit 
auf die GPU auslagern. Wenn du da eine moderne hast, die auf über 10.000 
Kernen gleichzeitig rechnet, dann geht das natürlich etwas flotter.

[J. T. (chaoskind)]

Rolf M. schrieb:
> dann geht das natürlich etwas flotter.

Etwas, ein klein wenig :D. So der Faktor von 15min/Bild zu 30fps.

Ansonsten dank ich dir für deinen "Senf" zu dem Thema.

Hast du zu dem Thema "Paralellisierung" zufällig nen guten Link parat? 
Ich laste zur Zeit ein Kern zu 9.2% aus, wenn das Programm läuft. Also 
der Taskmanager meint das zumindest so. Da sollte doch eigentlich auch 
mehr zu holen sein.

[mIstA (Gast)]

J. T. schrieb:
> Ich laste zur Zeit ein Kern zu 9.2% aus, wenn das Programm #
> läuft.

Das scheint mir irgendwie recht wenig. Ist das noch immer die Version 
ausm OP, wo Du jeden Pixel direkt mit Allegro setzt, wenn ich das auf 
die schnelle richtig gesehen hab? Dann solltest Du mal versuchen, zuerst 
das komplette Brötchen fertigzurechnen und erst anschließend das Bild zu 
Allegro rüberschieben, denn irgendwas scheint ja Dein Programm 90% der 
Zeit zum Nixtun zu verdonnern.

[Johann L. (gjlayde)]

Gibt's eingentlich nen besonderen Grund, warum du nicht complex Typen 
verwendest?

#include <complex.h>
#include <stdio.h>

// Oder 1.0 * I.  In GNU-C geht auch 1i.
complex double a = I; 

int main (void)
{
    complex double aa = a * a;
    printf ("a^2 = (%f, %f)\n", creal(aa), cimag(aa));
}

Was sich bzgl. Genauigkeit und Speed durchaus lohnt, ist ein eigener 
Fixed-Point Typ, Arithmetik z.B. per Inline Assembly.  Der Wertebereich 
ist ja begrenzt und 4 oder 3 Vorkommastellen sind ausreichend.

J. T. schrieb:
> Hast du zu dem Thema "Paralellisierung" zufällig nen guten Link parat?

"Low-Level" Parallelisierung geht am einfachsten mit OpenMP.  Bei 
Verwendung von GCC mit "-fopenmp" compilieren und linken, und im 
Programm

#pragma omp parallel for
for (...)

Um Overhead zu reduzieren, würde ich die parallele Schleife nicht über 
einzelne Pixel machen, sondern stattdessen das Bild in 8x8 Blöcke oder 
so unterteilen.  Oder man kann explizit das Scheduling beeinflussen, 
etwa:

#pragma omp for schedule(dynamic,100)
for (...)

https://www.openmp.org/specifications/
https://tildesites.bowdoin.edu/~ltoma/teaching/cs3225-GIS/fall17/Lectures/openmp.html

[Irgend W. (Firma: egal) (irgendwer)]

J. T. schrieb:
> Dazu hab ich nun "Subpixel" berechnet (1 Pixel wird in 3mal3 Subpixel
> zerlegt) und von diesen Subpixeln den Durchschnitt berechnet.

So 100% sicher bin ich mir nicht was du hier meinst.
Hast du z.B. ein Bild mit 3000x3000 Pixel was du zu 1000x1000 
runterrechnest? Wenn du das machst, machst du genau das Gegenteil von 
"weichzeichnen", du schärfst das Bild nach und dabei entstehen fast 
immer Artefakte.

Zum einfachen weichzeichnen wäre eher das Bild in der Zielauflösung und 
dort dann für jedes Pixel mit den Nachbarpixeln gewichtet(!) den 
Durchschnitt ermitteln. Dabei immer die Pixel aus dem Ausgangsbild 
nehmen und nicht die eventuell schon neu berechneten. Auf jeden Fall bei 
dem ganzen Vorgang nicht die Auflösung des Bildes reduzieren, das wirkt 
immer wie ein Nachschärfen.

- ->das machst du: https://en.wikipedia.org/wiki/Bicubic_interpolation
- ->das willst du: https://en.wikipedia.org/wiki/Gaussian_blur

[J. S. (engineer)]

J. T. schrieb:
> obei ich es mit den Subpixeln noch nicht so richtig hinbekomme....
Das Problem ist einerseits die arithmetische Mittelwertbildung. Das 
Oversampling müsste mit 5 Pixeln gemacht werden und dann ein 
biquadratischer- oder noch besserer Interpolationsfilter angewendet 
werden, weil die Ergebnisse von Mandelbrotiterationen sehr nichtlinear 
sind und abrupt gerundet werden. Das führt zu falschen "Tiefen" und 
Säumen und damit Frequenzen die ihrerseits schon falsch sind und bei 
Vergrößerung Artefakte machen.

Das gleiche Problem hast du nochmal bei der rein grafischen 
Weichzeichnerei: Da braucht es einen 7x7 - Filter um eine gute 
Interpolation über die Farben zu bekommen. Wenn das zu einfach ist, z.B. 
nur ein 5 zu 5 oder gar linear, dann wird im 3D-Farbraum sozusagen 
"abgekürzt", um einen Zwischenwert zu berechnen.

Generell würde ich das oversamplen VOR der Berechnung der reinen 
Farbanpassung bei dieser Art von Grafiken vorziehen. Bei einer 
entsprechend hohen Monitorauflösung muss man auch nicht in 2D-Smoothen - 
eher in 3D = 2D+Zeit, wenn man einen Film macht.

[J. S. (engineer)]

J. T. schrieb:
> Wahnsinn wieviel Unruhe in dem Bereich ist, der im
> Eingangspostbild so gleichmäßig grün aussieht.

Die Manelbrotmenge ist überall unruhig und genau genommen entstehen die 
Figuren nur durch das grobe Rechnen, Abbrechen und Runden. Ein bis ins 
Detail berechnete Mandelbrot wird immer völlig pixelig sein. Irgendwann 
- spätestens auf Bildpixelebene - muss man abbrechen und sich für eine 
Farbe entscheiden. Daher entstehen die Figuren. Wenn man in die Täler 
reinrechnet, verschwinden die Pixel gleicher Farbe wieder.