2009-05-24 16 views
0

Ich schrieb diese Funktion zum Füllen geschlossener Schleife, pixvali wird global deklariert, um den Farbwert des Pixels zu speichern, wo der erste Klick erfolgt (innerhalb der geschlossenen Schleife).Warum wird der Stack in diesem Code übergelaufen?

Aber das Problem ist, dass diese Rekursion nicht beendet, wenn sein erst * fill (.., ..) * über bekommen, und es sagt Stapel überschwemmt werden ...

void fill(int x,int y) 
{ 
    GLfloat pixval[3]; 
    glReadPixels(x,y,1,1,GL_RGB,GL_FLOAT,pixval); 
    if(pixval[0]==pixvali[0] && pixval[1]==pixvali[1] && pixval[2]== pixvali[2]) 
    { 
     glBegin(GL_POINTS); 
      glVertex2i(x,y); 
     glEnd(); 
     glFlush(); 
     fill(x-1,y); 
     fill(x+1,y); 
     fill(x,y-1); 
     fill(x,y+1); 
    } 
} 
+1

Und fügen Sie die Sprache den Tags hinzu. Es könnte wie C aussehen, aber es gibt eine ganze Reihe von Sprachen, die wie C aussehen: – extraneon

+0

sind die Pixelwerte irgendwo gesetzt? – Dario

+0

Meine Kristallkugel sagt mir "pixvali" ist die Farbe, die Flut gefüllt werden sollte. –

Antwort

0

Ihren eigenen Stack implementieren, keine Rekursion für Flutfüllung verwenden, wenn Sie Formen mit relativ kleiner Fläche in Form von Pixeln füllen.

eine typische Implementierung ist:

Stack stack; 
stack.push(firstPoint); 

while(!stack.isEmpty()){ 
    Point currentPoint= stack.pop(); 
    //do what ever you want to do here, namely paint. 
    //boundary check ur surrounding points and push them in the stack if they are inbounds 
} 
4

Der Stapelüberlauf weil Sie Rekursion verwenden und die Tiefe der Rekursion linear in der Anzahl der Pixel in der Form ist, die Sie ausfüllen.

Es kann auch sein, dass Sie versuchen, die Form in der gleichen Farbe zu füllen, wie sie bereits ist. Das heißt, die aktuelle gl Farbe ist die gleiche wie pixvali. In diesem Fall erhalten Sie eine unendliche Rekursion.

3

Es ist schwer zu sagen von der Frage, aber meine Vermutung wäre, dass Sie beginnen, in einer Schleife von Pixeln zu gehen.

Zum Beispiel, denken Sie, dass Sie nur 4 Pixel haben, die Sie benötigen, um (0,0), (0,1), (1,0), (1,1) zu färben.

Sie beginnen zu färben (0,0). Dann wird Ihre Rekursion (1,0) eingeben, da (-1,0) keine Färbung benötigt. dann (0,0) wieder seit, es ist das Pixel, das ist (x-1, y) wieder und so weiter.

Sie müssen einen Weg hinzufügen, um bereits farbige Pixel zu markieren. Aber das ist nur eine Vermutung, weil Sie nicht wirklich sehen können, was außerhalb dieser Funktionen abläuft.

+0

Der Vergleich zwischen Pixval und Pixvali ist angeblich dieser Marker. Ich hoffe nur, dass er mit der pixvali Farbe zeichnet, während er die aktuelle xy Farbe in pixval liest ... – extraneon

+0

Wo vergleicht er dann mit der gefüllten Farbe? (Dh Sie Farbe x mit Farbe y füllen möchten, müssen Sie diese Farbe x überprüfen gefüllt und sonst nichts, andere weise kann man einfach den ganzen Bildschirm überfluten) Ich persönlich für eine Farbe von x in einiger Entfernung aussehen würde, aber das ist nicht der Punkt wirklich. – SurDin

+0

siehe mein Problem kommt wie: Es zeichnet eine Linie vom angeklickten Punkt bis die Grenze in -x Richtung geht. Als meine erste Rezension ist für -x; nach der Linie wird gezeichnet, es zeigt Stack-Überlauf .. Denken Sie daran richtig und dann posten Sie einen Kommentar .. – Abhay

1

der Implementierungsdetails nicht sicher, aber wenn das 12-Byte-lokale Array auf dem Stapel zugeordnet ist (3 schwebt einen 4 Byte pro Stück), dann haben Sie je 4 Byte für die x- und y-Parameter und wahrscheinlich vier Bytes für die Rückkehradresse. Das gibt mindestens 24 jedes Mal, wenn Sie rekrutieren. Das bedeutet, dass Sie nur ein bisschen mehr als 40'000 Anrufe benötigen, um 1 MB Speicherplatz freizugeben, wenn es nichts anderes mehr gibt, was nicht wahr ist.

Um das in die richtige Perspektive zu bringen, sind 43'690 Pixel nur etwa 10% eines 800x600 Displays.

+0

Hoppla, bemerkte nicht, dass das Array GLFloat war, mein Gehirn hat gerade drei Bytes für RGB ersetzt. Offensichtlich würde dies die Stapelanforderungen pro Anruf noch verschlimmern. – JimG

+0

Die Nummern wurden korrigiert :) –

1

Sie müssen überprüfen, welche Pixel Sie bearbeiten.

z.B. Wenn Sie ein Bild von 0,0 bis 10,10 haben und Sie 11,10 bearbeiten, gelangen Sie außerhalb des Speichers.

Sie müssen also überprüfen, ob x, y zwischen den Grenzen des Bildes ist.

x>=left&&x<=right&&y>=top&&y<=bottom 
0

Auf den ersten Blick sieht der Algorithmus gut aus. Ich mache mir ein bisschen Sorgen wegen des "==", weil sie mit Float-Werten nicht gut funktionieren. Ich schlage vor,

abs(val1 - val2) < limit 

stattdessen zu verwenden (wo limit ist < 1 und> 0 Versuche 0,0001, zum Beispiel).

die Fehler aufzuspüren, schlage ich vor, ein printf() am Anfang der Funktion hinzuzufügen. Wenn Sie sehen, was die Funktion zu füllen versucht, wird das helfen. Vielleicht steckt es irgendwo fest und ruft sich immer wieder mit den gleichen Koordinaten auf?

Auch der Stapel kann einfach für den Bereich zu klein sein, Sie zu füllen versuchen. Versuchen Sie es zuerst mit einem kleinen Bereich, sagen Sie ein kleines Rechteck nur 4 mal 3 Pixel. Versuchen Sie nicht, mit der Maus darauf zu klicken, sondern beginnen Sie mit einem bekannten guten Punkt darin (rufen Sie einfach fill() in Ihrem Code auf).

Druck auch die Werte für die Farbe helfen könnte.

0

Warum missbrauchen Sie OpenGL für das? Was Sie dort tun, ist sehr instabil. Zum Beispiel entspricht das von glReadPixels gelesene Pixel nur dann der Scheitelpunktposition, wenn eine sorgfältig ausgewählte Kombination aus Projektions- und Modellansichtsmatrix verwendet wird. Auch jede Iteration von Fill wird eine vollständige Rundreise machen. Nur weil Sie OpenGL verwenden, wird es nicht magisch schnell.

Wenn Sie einen Bereich im Framebuffer überfluten möchten, lesen Sie den gesamten Framebuffer aus, tun Sie den Floodfill und schieben Sie das Ergebnis zurück zu OpenGL. Auch wenn ein Teil des Framebuffers verdeckt ist (durch ein Fenster oder ähnliches), sind diese Teile nicht

Nun zu verstehen, warum Sie in einer unendlichen Rekursion enden. Bedenken Sie:

fill(4, 4) wird fill(5, 4) nennen fill(5, 5) rufen rufen fill(4, 5)fill(4, 4)Boom

Jetzt haben Sie, dass Testanruf wird es bekam:

if(pixval[0] == pixvali[0] && 
    pixval[1] == pixvali[1] && 
    pixval[2] == pixvali[2]) 

Beachten Sie, dass dies wahr ausgewertet Wenn das zu setzende Pixel bereits die Zielfarbe hat, wird es wieder zu einer endlosen Rekursion. Sie sollten für Ungleichheit testen.

Last but not least: Ein Bild kann leicht von Millionen von Pixeln besteht. Übliche Stapelgrößen erlauben nur maximal einige 1000 Verschachtelungsebenen, so dass Sie Ihre Tail-Rekursion in eine Iteration konvertieren müssen.

TL; DR: Verwenden Sie nicht OpenGL dafür, arbeiten Sie auf einem lokalen Puffer, verwenden Sie geeignete Iteration Condition Test und verwenden Sie Iteration anstelle von Rekursion (oder verwenden Sie eine funktionale Sprache, dann wird der Compiler für diese Tail-Rekursion sorgen).

http://en.wikipedia.org/wiki/Flood_fill

Verwandte Themen