Алгоритм заполнения с затравкой { push(x0,y0); // координаты пикселя затравки - в стек setcolor(incol); while(стек не пуст) { pop(x,y);//извлекаются координаты пикселя из стека xm=x; //запоминание абсциссы пикселя затравки //поиск крайнего правого пикселя интервала while(_getpixel(++x,y) != bndcol); rx=x--; //запоминается крайний правый пиксель интервала x=xm; //поиск крайнего левого пикселя интервала while (_getpixel(--x,y) != bndcol); lx=x++; //запоминается крайний левый пиксель интервала // закрашивание строки пикселей [lx,rx] _rectangle(_gfillinterior,lx,rx,y,y);
ym=y; for(y=ym-1; y<=ym+1; y+=2){ x=lx; while(x<=rx){ empty=0; pixcol=_getpixel(x,y); while (pixcol !=bndcol && pixcol !=intcol && x<rx){ //перебор пикселей, пока не встретится пиксель, //закрашенный цветом границы или внутренней области empty=1; pixcol=getpixel(x++,y); } if(empty){ // крайний правый пиксель помещается в стек if(pixcol !=bndcol && pixcol !=intcol && x==rx) push(x,y); else push(x-1,y); }
// поиск других незаполненных интервалов на строке x++; while (_getpixel(x,y)==bndcol || _getpixel(x,y)==intcol && x<rx) x++; }// конец цикла x<=rx } // конец цикла по y }
Способы устранения лестничного эффекта Закраска фигуры с проявлением лестничного эффекта на ее границе Идея смягчения лестничного эффекта – закрашивать пиксели пропорционально площади пикселя, попадающей внутрь фигуры
Вспомогательные формулы Уравнение границы многоугольника Площадь пикселя, попавшая в многоугольник, вычисляется по формуле трапеций В алгоритме Брезенхема используется функция ошибки пикселя Переходя по строке пикселей и вычисляя e(x,y), следим за знаком e и переходим на верхнюю строку, если e(x,y) > 0.
{ int x=x1; int y=y1; int dx=x2-x1; int dy=y2-y1; k=dy/dx; e=1/2; putpixel(x,y,e); while(x<x2){ if(e<1){ x++; e+=k; } else{ x++; y++; e--; } putpixel(x,y,e); } Если к e добавить 1, e' = e + 1, e' может служить мерой интенсивности свечения пикселя в пределах от 0 до 1. Критерий перехода на следующую строку пикселей функция ошибки превышает 1: e' > 1.
Некорректная визуализация мелких деталей Алгоритм визуализации: пиксель закрашивается, если центр пикселя оказывается внутри этого объекта Побочные эффекты: 1. Объект не будет показан 2. Передав свой цвет пикселю, объект будет выглядеть несоразмерно большим Актуально в случае визуализации большого количества мелких объектов – пылевого облака
Буфер кадра с большим разрешением Для улучшения визуализации мелких деталей создается промежуточный буфер кадра, в котором по каждому из направлений число пикселей увеличено в 2 или более раз. Построение сцены производится в промежуточном буфере с большим разрешением. После этого изображение переносится в основной буфер с усреднением пикселей. Формула усреднения w – вес пикселя Равномерное усреднение
Взвешенное усреднение