Contour tracing

[Lord Nikon]

Hi,
wer kann mir mir erklären wie Contour tracing funktioniert?

[Demirug]

Dafür gibt es ja soviele unterschiedliche Verfahren. Von was suchst du den die Kontur?

[Lord Nikon]

Ich hab gelesen , dass man mit Contour tracing Mandelbrotdarstellungen optimieren kann. Gibs dafür ein speziales Verfahren ?

[aths]

Hrr hrr. Ja. Frag mal zecki :naughty:

Also ich schreibe gerade fürs Studium 'n Mandelbrot-Rendering, und habe den Rechteck-Algo genommen. Das Bild wird mit dem Aufruf rectangle(0, 0, xmax, ymax); erzeugt. Recangle malt erst mal die Kanten und prüft dann, ob die Randfarbe überall gleich ist. Wenn ja, Blockfill, return. Ansonsten wird geprüft, ob das Rechteck eher in X- oder eher in Y-Richtung gestaucht ist. Dann wird es in zwei Hälften zerlegt, enweder oben/unten oder links/rechts. Für jedes der beiden Unter-Rechtecke wird recangle() mit den neuen Eck-Koordinaten aufgerufen. Die Klasse für das Bild hat einen Alpha-Kanal der die bereits berechneten Punkte vermerkt, so dass schon fertige Pixel nicht erneut berechnet werden.

Es gibt auch ein zweites Abbruchs-Kriterium: Wenn die Breite oder Höhe des Rechtecks <= 2 Pixel ist.

Mit dieser Zerlegung spart man schon kräftig. Aber es geht noch besser. Wenn man nämlich NUR die Pixel berechnet, die am Rand zwischen zwei Farbflächen vorkommen. Dazu beginnt man links oben und sucht eben, bis man zu einer anderen Farbe kommt. Dann sucht man dort nach der ersten Farbe weiter, bis man eine zusammenhängende Struktur gleicher Farbe hat, diese wird gefüllt, man sucht dann einen noch nicht berechneten Bereich und sucht dort die nächste zusammenhängende Fläche, bis alle Pixel ausgemalt sind.

[Lord Nikon]

danke für die Erklärung , die Umsetung scheint nicht ganz leicht zu sein.
@ Aths
Wie findest du dieses Bild von meinem Mandelbrotrenderer
http://home.arcor.de/intelhasser/fraktaldif1.png
Das ist alles noch ungezoomt.Die Farbwerte bassieren auf Zufallszahlen. Ich habe den Verdacht , dass ich irgendwas falsch gemacht habe, da Zeckis Renderer viel bessere Bilder schon beim Start liefert.

[aths]

Die Farbwerte werden nicht mit Zufallszahlen erzeugt, sondern mit

Palette [Iter mod Farbzahl der Palette];

[aths]

Berechnest du die Enwicklung im Orbit? Eigentlich berechnet man nur, ob der Punkt überhaupt rausspringt, oder nicht.

[Lord Nikon]

So berechnete das Bild

korr a;
const char * vendor = glGetString(GL_VENDOR);
mem->Lines->Add(vendor);
Randomize();
wglMakeCurrent(
wglGetCurrentDC(),
wglGetCurrentContext());

glMatrixMode(GL_PROJECTION); // Aktuelle Matrix setztn

farbe fr;
glLoadIdentity();


glOrtho(-2.0,2.0,-2.0,2.0,-38.0,38.0);
/*void glOrtho( GLdouble left,
GLdouble right,
GLdouble bottom,
GLdouble top,
GLdouble zNear,
GLdouble zFar )

*/
glClearColor(0.0f,0.0f,0.0f,0.0f);

glClear(GL_COLOR_BUFFER_BIT|
GL_DEPTH_BUFFER_BIT);
glEnable(GL_NORMALIZE);
glEnable(GL_DEPTH_TEST);

glShadeModel(GL_SMOOTH);
glHint(GL_PERSPECTIVE_CORRECTION_HINT, GL_NICEST);
glEnable(GL_COLOR_MATERIAL);
glEnable(GL_LIGHT0);
glEnable(GL_LIGHTING);
glEnable( GL_POINT_SMOOTH);
glHint( GL_POINT_SMOOTH_HINT , GL_NICEST );

glDisable(GL_CULL_FACE);




double x, y; // ' Laufvariablen
double x1, y1, x2, y2; // ' Mandelbrot-Ausschnitts-Koordinaten
int depth ; // Berechnungstiefe
int d; // Laufvariable für Tiefe
double dx, dy ; // Schrittweite pro Pixel
double px, py; // aktuelle Weltkoordinate
double u, v; // Berechnungsvariablen
double ax, ay ; // Berechnungsvariablen
double r[255];
double g[255];
double b[255];
int zahler=0;

// 255 Zufallsfarben erzeugen
if (pal==false)
{
for ( zahler = 0;zahler<255;zahler++)
{
r[zahler]=random(11)/10;
g[zahler]=random(11)/10;
b[zahler]=random(11)/10;
}

}


// Ausschnitt der Grafik
x1 = -2.0 ;
y1 = -1.6 ;
x2 = 1 ;
y2 = 1.6 ;


/* x1 = 0 ;
y1 = -1 ;
x2 = 1 ;
y2 = 0 ;
*/
depth = 240; // maximal 165 (sonst mehr Zufallsfarben erzeugen!)
dx = (x2 - x1) /3.5 ;
dy = (y2 - y1) / 3.5 ;
int merker;
merker=0;
int merker2=0;
// Erzeugung des Bitmap
// for ( y = -5.5 ;y<=8.5;y=y+0.01) //5.5

// for ( x = -5.5;x<=8.5;x=x+0.01) //-5.5
// {
zeit=GetTickCount();
for (x=-6.0;x<6.1;x=x+0.01)
for (y=-6.0;y<6.1;y=y+0.01)
{






px = x1 + x * dx ;
py = y1 + y * dy ;
d = -1 ;
ax = 0 ;
ay = 0 ;
do
{ merker++;
u = ax * ax - ay * ay + px;
v = 2 * ax * ay + py ;
ax = u ;
ay = v ;


d += 1 ;
if (pal==false)
{
// mem->Lines->Add("Zufallswerte genohmen");
a.rr=r[d];
a.gg=g[d];
a.bb=b[d];
}
if (pal==true)
{
a.rr=l[d].red ;

a.gg=l[d].green;

a.bb=l[d].blue;


}
a.xx=ax;
a.ii=v;
test.push_back(a);
zeit2=GetTickCount();

}

while ( ((ax * ax + ay * ay )<4) && (d<depth));
}
zeit2=zeit2-zeit;
mem->Lines->Add("Gebrauchte Berechnungszeit:"+AnsiString(zeit2));

// mem->Lines->Add("Gebrauche erste Schleife Durchläufe:"+AnsiString(merker));
// Fertiges Bitmap darstellen

// mem->Lines->Add(test.size());
// mem->Lines->Add(test.capacity());

if (rg->ItemIndex==0)
{
glBegin(GL_POINTS);
}
if (rg->ItemIndex==1)
{ Auswahl=1;
glBegin(GL_LINES);
}
zeit=GetTickCount();
for (int i=0;i<test.size()-1;i++)
{
glColor3f(test[i].rr,test[i].gg,test[i].bb);
glVertex2d(test[i].xx,test[i].ii);
glColor3f(test[i+1].rr,test[i+1].gg,test[i].bb);
glVertex2d(test[i+1].xx,test[i+1].ii);
}


glEnd();
zeit2=GetTickCount();
zeit2=zeit2-zeit;
mem->Lines->Add("Gebrauchte Zeit zum Zeichnen:"+AnsiString(zeit2));



mem->Lines->Add("Bild wird jetzt dargestellt");

glFlush();
glFinish();
SwapBuffers(wglGetCurrentDC());

[zeckensack]

Lord Nikon,
du fügst für jede Iteration einen neuen Punkt in test (ein vector?) ein. Das muß zwar nicht schief gehen (tut's in diesem Fall auch nicht), aber es ist ineffizient :)
Du brauchst erst dann ein neues Datum auszuspucken, wenn die Abbruchbedingung erreicht ist.


Die Positionsbestimmung der erzeugten Punkte stimmt nicht. Du benutzt hier die imaginäre Zahl nach einer nicht näher bestimmbaren Anzahl von Iterationen, 'richtig' ist aber das x/y (bzw eine 2D-Transformation davon).

Ich habe da mal ein wenig gebastelt:

zeit=GetTickCount();
for (x=-6.0;x<6.1;x=x+0.01)
for (y=-6.0;y<6.1;y=y+0.01)
{
px = x1 + x * dx ;
py = y1 + y * dy ;
d = -1 ;
ax = 0 ;
ay = 0 ;
do
{ merker++;
u = ax * ax - ay * ay + px;
v = 2 * ax * ay + py ;
ax = u ;
ay = v ;
d += 1 ;
}
while ( ((ax * ax + ay * ay )<4) && (d<depth));

if (pal==false)
{
// mem->Lines->Add("Zufallswerte genohmen");
a.rr=r[d];
a.gg=g[d];
a.bb=b[d];
}
if (pal==true)
{
a.rr=l[d].red ;

a.gg=l[d].green;

a.bb=l[d].blue;
}

//paßt deine x/y-Menge [-5,5 ... 8,5] an deinen Viewport an
//kann natürlich noch vereinfacht werden ...
a.xx=(x+5.5)*4.0/14-2.0;
a.ii=(y+5.5)*4.0/14-2.0;
test.push_back(a);
}

zeit2=GetTickCount();
zeit2=zeit2-zeit;
mem->Lines->Add("Gebrauchte Berechnungszeit:"+AnsiString(zeit2));

// mem->Lines->Add("Gebrauche erste Schleife Durchläufe:"+AnsiString(merker));
// Fertiges Bitmap darstellen

// mem->Lines->Add(test.size());
// mem->Lines->Add(test.capacity());

if (rg->ItemIndex==0)
{
glBegin(GL_POINTS);
}
if (rg->ItemIndex==1)
{ Auswahl=1;
glBegin(GL_LINES);
}
zeit=GetTickCount();
for (int i=0;i<test.size()-1;i++)
{
glColor3f(test[i].rr,test[i].gg,test[i].bb);
glVertex2d(test[i].xx,test[i].ii);
//unnötig. Der nächste Schleifendurchlauf
//erledigt das
// glColor3f(test[i+1].rr,test[i+1].gg,test[i].bb);
// glVertex2d(test[i+1].xx,test[i+1].ii);

}


glEnd();
zeit2=GetTickCount();
zeit2=zeit2-zeit;
mem->Lines->Add("Gebrauchte Zeit zum Zeichnen:"+AnsiString(zeit2));



mem->Lines->Add("Bild wird jetzt dargestellt");

glFlush();
glFinish();
SwapBuffers(wglGetCurrentDC());


Zum Contour-Tracing kann ich jetzt auf die Schnelle nicht viel sagen. Die Entwicklung des Algos hat mich auch ein paar Tage beschäftigt, und ich habe zwischendurch auch öfter mal zu Papier und Bleistift greifen müssen :naughty:

Das Paket hast du ja bereits, der Hauptteil der Arbeit in Contour.cpp wird in trace() erledigt. In refine_image werden ein paar Variablen initialisiert.
Der Algo liefert die gefundene Region als gleichfarbige 'spans', also horizontale Linien.

Kernidee: Wenn ich an einer Wand entlangschleiche, dann darf ich nicht nur nach vorne schauen. Ich muß auch darauf achten was links und rechts von mir passiert, damit ich mich nicht zu weit von der Wand entferne :naughty:

Du kannst aber gerne nochmal nachhaken :)


edit: deklariert -> intialisiert :bonk:

[Lord Nikon]

Original geschrieben von zeckensack


Ich habe da mal ein wenig gebastelt:

}




//paßt deine x/y-Menge [-5,5 ... 8,5] an deinen Viewport an
//kann natürlich noch vereinfacht werden ...
a.xx=(x+5.5)*4.0/14-2.0;
a.ii=(y+5.5)*4.0/14-2.0;
test.push_back(a);
}

Hi Zeckensack ,
irgendiwe hab noch nicht kapiert warum du durch 14 bzw nicht durch irgendeine andere Zahl statt der 14 teilst und warum du mit 4 multiplizierst. Wäre nett wenn du eine Anleitung für Idioten lieferst , wie man die Menge anpasst ,an Hand eines konkreten Beispiels.:)

Zum Contour-Tracing kann ich jetzt auf die Schnelle nicht viel sagen. Die Entwicklung des Algos hat mich auch ein paar Tage beschäftigt, und ich habe zwischendurch auch öfter mal zu Papier und Bleistift greifen müssen :naughty:

Wenn du ein paar Tage brauchst , brauch ich bestimmt ein paar Wochen:...( Ich guck mir deinen Quelltext noch mal genau an.:)

[zeckensack]

Original geschrieben von Lord Nikon
Hi Zeckensack ,
irgendiwe hab noch nicht kapiert warum du durch 14 bzw nicht durch irgendeine andere Zahl statt der 14 teilst und warum du mit 4 multiplizierst. Wäre nett wenn du eine Anleitung für Idioten lieferst , wie man die Menge anpasst ,an Hand eines konkreten Beispiels.:)Oi, da hatte ich mich sogar verlesen :weg:
Auf die Rechnung kam ich anhand deiner auskommentierten Werte. Das kann ich ja nochmal aufdröseln: // Erzeugung des Bitmap
// for ( y = -5.5 ;y<=8.5;y=y+0.01) //5.5

// for ( x = -5.5;x<=8.5;x=x+0.01) //-5.5
// {
zeit=GetTickCount();
for (x=-6.0;x<6.1;x=x+0.01)
for (y=-6.0;y<6.1;y=y+0.01)
Von -5.5 bis +8.5 ist ein Zahlenumfang von 14 :)
Uuund:glOrtho(-2.0,2.0,-2.0,2.0,-38.0,38.0);
Ist ein Zahlenumfang von 4, sowohl in x- als auch in y-Richtung.

Deswegen *4/14. Der Rest befaßt sich mit dem Ursprung der Zahlräume:
a.xx=(x+5.5)*4.0/14-2.0;
Vor der Skalierung schiebe verschiebe ich x von [-5.5;8.5] nach [0;14]. Das Zwischenergebnis der Skalierung liegt in [0;4].

"unten links" ist aber nicht (0;0), sondern (-2;-2), weil du das mit glOrtho so angegeben hast => -2 :)

[Lord Nikon]

Danke, jetzt habe ich das verstanden.

[Lord Nikon]

irgendwie wird jetzt nicht mehr der ganze Bildschirm gefüllt und mit zwei Paletten seh ich ein großes Viereck , dass unten links in der ecke einen Teil des Kreises überdeckt.

if( ((ax * ax + ay * ay )>=4))
{
d += 1 ;
if (d>240)
{
d=0;
}
}

EDIT:
Alles funktioniert nach einem Neustart ohne Probleme.?-)