Почему в этом коде происходит переполнение стека?

Question

Я написал эту функцию для заполнения замкнутой петли, pixvali объявлен глобально для хранения значения цвета пикселя, где будет сделан первый щелчок (внутри замкнутого цикла).

Но проблема в том, что эта рекурсия не прекращается, когда его первый * заливка (.., ..) * перебираться, и он говорит, что стек переполняется ...

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); 
    } 
} 

Answer 1

Внесите свой собственный стек, не используйте рекурсию для заливки потоком, если вы не заполняете фигуры с относительно небольшой площадью поверхности в пикселях.

типичная реализация:

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 
} 

Answer 2

В переполнения стека потому что вы используете рекурсию, а глубина рекурсии линейна в количестве пикселей в заполняемой вами форме.

Возможно, также вы пытаетесь заполнить форму того же цвета, что и она. То есть текущий цвет gl такой же, как pixvali. В этом случае вы получите бесконечную рекурсию.

Answer 3

Это сложно сказать из вопроса, но я предполагаю, что вы начинаете идти в петлю пикселей.

Например, подумайте, что у вас есть только 4 пикселя, которые вам нужно окрасить (0,0), (0,1), (1,0), (1,1).

Вы начинаете окрашивать (0,0). Тогда ваша рекурсия войдет (1,0), так как (-1,0) не нуждается в раскраске. то (0,0) снова, так как это пиксель, который (x-1, y) снова и так далее.

Вам нужно добавить какой-то способ отметить уже окрашенные пиксели. Но это всего лишь предположение, потому что вы не можете понять, что происходит вне этих функций.

Answer 4

Не уверен в деталях реализации, но если 12 байт локального массива выделяется в стеке (3 плавает 4 байта), то есть 4 байта для параметров x и y и, возможно, четыре байта для обратного адреса. Это дает по крайней мере 24 каждый раз, когда вы рекурсируете. Это означает, что вам нужно всего лишь более 40 000 вызовов, чтобы пробить 1 МБ пространства стека, если на нем больше ничего, что не будет правдой.

Чтобы представить это в перспективе, 43'690 пикселей составляет всего около 10% экрана 800x600.

Answer 5

Вам нужно проверить, какие пиксели вы редактируете.

например. Если у вас есть изображение от 0,0 до 10,10, и вы отредактируете 11,10, вы получите за пределами памяти.

Итак, вам нужно проверить, находится ли x, y между границами изображения.

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

Answer 6

На первый взгляд алгоритм выглядит хорошо. Меня немного беспокоит «==», потому что они не работают с плавающими значениями. Я предлагаю использовать

abs(val1 - val2) < limit 

вместо (где limit < является 1 и> 0. Попробуйте 0,0001, к примеру).

Чтобы отследить ошибку, я предлагаю добавить printf() в начале функции. Когда вы видите, что функция пытается заполнить, это поможет. Может быть, он где-то застрял и снова и снова звонит с теми же координатами?

Кроме того, стек может быть слишком мал для области, которую вы пытаетесь заполнить. Сначала попробуйте небольшую область, скажем, небольшой прямоугольник размером всего 4 на 3 пикселя. Не пытайтесь нажимать на нее мышью, но начинайте с известной точки внутри (просто введите fill() в свой код).

Также может помочь печать значений цвета.

Answer 7

Почему вы злоупотребляете OpenGL для этого? То, что вы там делаете, очень неустойчиво. Например, пиксель, считываемый glReadPixels, будет соответствовать только положению вершин, если используется тщательно подобранная комбинация матрицы проекции и модели. Кроме того, каждая итерация заполнения будет выполнять полный раунд. Просто потому, что вы используете OpenGL, он не получает магически быстро.

Если вы хотите наполнить заливку некоторой областью в фреймбуфере, проверьте весь фреймбуфер, выполните заливку и верните результат в OpenGL. Также, если какая-то часть фреймбуфера закрыта (окном или подобным), эти части не будут

Теперь, чтобы понять, почему вы оказываетесь в бесконечной рекурсии. Рассмотрим это:

fill(4, 4) позвонит fill(5, 4) будем называть fill(5, 5) будем называть fill(4, 5) будем называть fill(4, 4)бум

Теперь у вас есть, что тест там:

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

Обратите внимание, что это оценивает истинный если установленный пиксель уже имеет целевой цвет, снова завершается бесконечной рекурсией. Вы должны проверить на неравенство.

И последнее, но не менее важное: изображение может состоять из миллионов пикселей легко. Обычные размеры стека позволяют использовать только не более 1000 уровней вложенности функций, поэтому вы конвертируете рекурсию хвоста в итерацию.

TL; DR: не используйте для этого OpenGL, работайте с локальным буфером, используйте надлежащий тест условий итерации и используйте итерацию вместо рекурсии (или используйте функциональный язык, тогда компилятор позаботится об этой хвостовой рекурсии).

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