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

Question

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

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

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

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

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

Answer 2

Трудно сказать по этому вопросу, но я думаю, что вы начинаете идти в цикле пикселей.

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

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

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

Answer 3

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

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

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

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

Answer 4

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

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

Answer 5

Почему вы злоупотребляете 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] )

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

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

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

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

Answer 6

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

abs(val1 - val2) < limit

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

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

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

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

Answer 7

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

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

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
}