Алгоритм Брезенхема
При ограниченном разрешении точка приближаемой линии может находиться либо на самой линии, либо слева от нее либо справа. Расстояние на котором фактически установленная точка находиться от рисуемой линии, -- ошибка в рисовании линии. Переходя к каждой следующей точке, ошибка скажет какая точка будет хуже приближать кривую а какая лучше.
Принцип Брезенхема состоит в том, чтобы с каждой итерaцией двигаться на одну точку по той оси проекция на которую больше. По другой оси смешение на один пиксель происходит лишь тогда, когда линия отклонилась от текущей оси более чем на полпикселя (Рисунок 1).
Приведенные рассуждения рассматривают лишь суть, а не точный механизм работы алгоритма Брезенхема . Рассмотрим реализацию.
inline void Image::Octant0(int X0,int Y0,int DeltaX,int DeltaY,int XDirection) {
/* DeltaX -- поэкция на ось X
DeltaY -- проэкция на ось Y
XDirection -- направление движения
для данной функции |DeltaX|>DeltaY
следовательно основная ось X, a
вспомогaтельная Y
*/
int DYx2;
int DYx2MinusDXx2;
int ErrorTerm;
/* Установим начальную ошибку накопления и значения,
используемые во внутреннем цикле */
DYx2=DY*2;
DYx2MinusDXx2= DYx2 - DX*2;
ErrorTerm = DYx2 - DX;// ошибка
/* ставим первую точку */
setZPixel(X0,Y0,getZPixel(DeltaX),Color);
while(DeltaX--) {
if(ErrorTerm >=0) {
/* шагаем по вспомогательной оси
и подправляем ошибку накопления */
Y0++;
ErrorTerm+=DeltaYx2MinusDeltaXx2;
} else {
/* добавляем ошибку накопления */
ErrorTerm+= DeltaYx2;
}
/* двигаемся по основной оси */
X0+= XDirection;
/* ставим точку */
setZPixel(X0,Y0,getZPixel(DeltaX),Color);
}
}
Теперь о том как мы будем находить Z координаты для каждой точки рисуемой прямой. Очевидно они меняются по линейному закону y=k*x+b, где k,b подлежат определению. Их можно найти посмотрев на рисунок 3.
Для того чтобы рисовать линию необходимо определить в какой области (октанте) находится линия. На рис 2 показаны восемь октант. Очевидно четыре из них избыточны, нижние четыре октанты можно преобразовать в четыре верхнии, поменяв начальную точку линии с конечной. Т.е, поменять местами
После этого надо определить в какой из четырех октант находится линия. Из этих четырех две октанты имеют в качестве основной имеют горизонтальную ось, а в качетве второстепенной вертикальную. У остальных основная ось вертикальная. Видно что оканты 0,3 отличаются только по направлению движения, тоже самое можно сказать об октантах 1,2. От сюда видно что рисование линии можно свести к двум функциям. Octant0 для 0,3 октант и Octant1 для 1,2. Точнее :
void Image::line(int X0,int Y0,float Z0,int X1,int Y1,float Z1,color C){
int DeltaX,DeltaY;
Color=C;/* установим цвет */
/* инициализируем закон изменения глубины */
double dist = distance(X0, Y0, X1, Y1);
if (dist < 0.0001) {
setZPixel(X0, Y0, (Z0 < Z1 ? Z0 : Z1), C);
return;
}
k = (Z0 - Z1) / dist;
b = Z1;
/* уменьшим число условий наполовину
в результатe DeltaY всегда > 0
и можно работать с октантами
0-3
*/
if (Y0 > Y1 ) {
swap (Y0,Y1);
swap (X0,X1);
}
/* проэкция на ось X */
DeltaX = X1 - X0;
/* проэкция на ось Y */
DeltaY = Y1 - Y0;
if(DeltaX >0) {
/* рисуем с лева направо */
if (DeltaX > DeltaY ) {
Octant0(X0,Y0, DeltaX,DeltaY,1);
} else {
Octant1(X0, Y0, DeltaX ,DeltaY,1);
}
} else {
/* с права налево */
DeltaX = -DeltaX;
if( DeltaX > DeltaY) {
Octant0(X0,Y0, DeltaX, DeltaY,-1);
} else {
Octant1(X0,Y0, DeltaX, DeltaY,-1);
}
}
}
