Приложение 2. Процедуры генерации отрезков
Здесь приведены тексты соответствующих процедур с пояснениями и тестовая программа. Процедуры позволяют генерировать вектора в любом квадранте с использованием алгоритмов несимметричного цифрового дифференциального анализатора и Брезенхема, а также построения ребра, ограничивающего заполненный многоугольник, модифицированным алгоритмом Брезенхема, уменьшающим лестничный эффект.
Предусмотрена возможность задания атрибутов формируемых отрезков - номер цвета и размер пиксела, используемого при формировании отрезков.
В тестовой программе предусмотрено, что при наличии SVGA-адаптера он может использоваться как в обычном режиме, так и в режиме до 1024x768 точек с 256 цветами.
/*------------------------------------------------- V_VECTOR.C
* Подпрограммы генерации векторов
*/
#include
#include
#define PutMay putpixel
static int Pix_X= 3, /* Размер пиксела по X */
Pix_Y= 3, /* Размер пиксела по Y */
Pix_C= 64, /* Нач. индекс цвета пиксела */
Pix_V= 64; /* Количество оттенков */
/*--------------------------------------------------- PutPixLn
* Подпрограмма заносит "кpупный" пиксел в позицию X,Y
* Точка (0, 0) - левый верхний угол экрана.
* Размеры пиксела задается фактическими паpаметpами x и y.
* Hомер оттенка пиксела задается фактическим паpаметpом c.
*/
void PutPixLn (int x, int y, int c)
{ int ii, jj, kk;
x *= Pix_X; y *= Pix_Y;
ii= Pix_Y;
while (--ii >= 0) {
jj= Pix_X; kk= x;
while (--jj >= 0) PutMay (kk++, y, c);
y++;
}
} /* PutPixLn */
/*--------------------------------------------------- V_setlin
* Устанавливает атрибуты построения линий:
* размер элементарного пиксела, индекс цвета, кол-во оттенков
* Если размер <= 0, то он не меняется
* Если атрибут цвета < 0, то он не меняется
*/
void V_setlin (sizex, sizey, colorindex, colorvalue)
int sizex, sizey, colorindex;
{
if (sizex > 0) Pix_X= sizex;
if (sizey > 0) Pix_Y= sizey;
if (colorindex >= 0) Pix_C= colorindex;
if (colorvalue >= 0) Pix_V= colorvalue;
} /* V_setlin */
V_DDA - несимметричный ЦДА
/*----------------------------------------------------- V_DDA
* void V_DDA (int xn, int yn, int xk, int yk)
*
* Подпрограмма построения вектора из точки (xn,yn)
* в точку (xk, yk) в первом квадранте методом
* несимметричного цифрового дифференциального анализатора
* с использованием только целочисленной арифметики.
*
* Обобщение на другие квадранты труда не составляет.
*
* Построение ведется от точки с меньшими координатами
* к точке с большими координатами с единичным шагом по
* координате с большим приращением.
*
* Отдельно выделяется случай вектора с dx == dy
*
* Всего надо выдать пикселы в dx= xk - xn + 1 позиции
* по оси X и в dy= yk - yn + 1 позиции по оси Y.
*
* Для определенности рассмотрим случай dx > dy
*
* При приращении X-координаты на 1 Y-координата должна
* увеличиться на величину меньшую единицы и равную dy/dx.
*
* После того как Y-приращение станет больше или равно 1.0,
* то Y-координату пиксела надо увеличить на 1, а из
* накопленного приращения вычесть 1.0 и продолжить построения
* Т.е. приращение Y на 1 выполняется при условии:
* dy/dx + dy/dx + ... + dy/dx >= 1.0
* Т.к. вычисления в целочисленной арифметике быстрее, то
* умножим на dx обе части и получим эквивалентное условие:
* dy + dy + ... + dy >= dx
*
* Эта схема и реализована в подпрограмме.
*
* При реализации на ассемблере можно избавиться от
* большинства операторов внутри цикла while.
* Для этого перед циклом надо домножить dy на величину,
* равную 65536/dx.
* Тогда надо увеличивать Y на 1 при признаке переноса
* после вычисления s, т.е. операторы
* s= s + dy;
* if (s >= dx) { s= s - dx; yn= yn + 1; }
* заменяются командами ADD и ADC
*
*/
void V_DDA (xn, yn, xk, yk)
int xn, yn, xk, yk;
{ int dx, dy, s;
/* Упорядочивание координат и вычисление приращений */
if (xn > xk) {
s= xn; xn= xk; xk= s;
s= yn; yn= yk; yk= s;
}
dx= xk - xn; dy= yk - yn;
/* Занесение начальной точки вектора */
PutPixLn (xn, yn, Pix_C);
if (dx==0 && dy==0) return;
/* Вычисление количества позиций по X и Y */
dx= dx + 1; dy= dy + 1;
/* Собственно генерация вектора */
if (dy == dx) { /* Наклон == 45 градусов */
while (xn < xk) {
xn= xn + 1;
PutPixLn (xn, xn, Pix_C);
}
} else if (dx > dy) { /* Наклон < 45 градусов */
s= 0;
while (xn < xk) {
xn= xn + 1;
s= s + dy;
if (s >= dx) { s= s - dx; yn= yn + 1; }
PutPixLn (xn, yn, Pix_C);
}
} else { /* Наклон > 45 градусов */
s= 0;
while (yn < yk) {
yn= yn + 1;
s= s + dx;
if (s >= dy) { s= s - dy; xn= xn + 1; }
PutPixLn (xn, yn, Pix_C);
}
}
} /* V_DDA */
V_Bre - алгоритм Брезенхема
/*----------------------------------------------------- V_Bre
* void V_Bre (int xn, int yn, int xk, int yk)
*
* Подпрограмма иллюстрирующая построение вектора из точки
* (xn,yn) в точку (xk, yk) методом Брезенхема.
*
* Построение ведется от точки с меньшими координатами
* к точке с большими координатами с единичным шагом по
* координате с большим приращением.
*
* В общем случае исходный вектор проходит не через вершины
* растровой сетки, а пересекает ее стороны.
* Пусть приращение по X больше приращения по Y и оба они > 0.
* Для очередного значения X нужно выбрать одну двух ближайших
* координат сетки по Y.
* Для этого проверяется как проходит исходный вектор - выше
* или ниже середины расстояния между ближайшими значениями Y.
* Если выше середины, то Y-координату надо увеличить на 1,
* иначе оставить прежней.
* Для этой проверки анализируется знак переменной s,
* соответствующей разности между истинным положением и
* серединой расстояния между ближайшими Y-узлами сетки.
*/
void V_Bre (xn, yn, xk, yk)
int xn, yn, xk, yk;
{ int dx, dy, s, sx, sy, kl, swap, incr1, incr2;
/* Вычисление приращений и шагов */
sx= 0;
if ((dx= xk-xn) < 0) {dx= -dx; --sx;} else if (dx>0) ++sx;
sy= 0;
if ((dy= yk-yn) < 0) {dy= -dy; --sy;} else if (dy>0) ++sy;
/* Учет наклона */
swap= 0;
if ((kl= dx) < (s= dy)) {
dx= s; dy= kl; kl= s; ++swap;
}
s= (incr1= 2*dy)-dx; /* incr1 - констан. перевычисления */
/* разности если текущее s < 0 и */
/* s - начальное значение разности */
incr2= 2*dx; /* Константа для перевычисления */
/* разности если текущее s >= 0 */
PutPixLn (xn,yn,Pix_C); /* Первый пиксел вектора */
while (--kl >= 0) {
if (s >= 0) {
if (swap) xn+= sx; else yn+= sy;
s-= incr2;
}
if (swap) yn+= sy; else xn+= sx;
s+= incr1;
PutPixLn (xn,yn,Pix_C); /* Текущая точка вектора */
}
} /* V_Bre */
V_BreM - модифицированный алгоритм Брезенхема
/*----------------------------------------------------- V_BreM
* void V_BreM (int xn, int yn, int xk, int yk)
*
* Подпрограмма иллюстрирующая построение ребра залитого
* многоугольника из точки (xn,yn) в точку (xk,yk)
* модифициpованным методом Брезенхема.
*
* Строки многоугольника от занесенного пиксела границы до xk
* заполняются оттенком с максимальным номером.
*/
void V_BreM (xn, yn, xk, yk)
int xn, yn, xk, yk;
{ int dx, dy, sx, sy, kl, swap;
long incr1, incr2;
long s; /* Текущее значение ошибки */
long s_max; /* Макс значение ошибки */
int color_tek; /* Текущий номеp оттенка */
int xt;
/* Вычисление приращений и шагов */
sx= 0;
if ((dx= xk-xn) < 0) {dx= -dx; --sx;} else if (dx>0) ++sx;
sy= 0;
if ((dy= yk-yn) < 0) {dy= -dy; --sy;} else if (dy>0) ++sy;
/* Учет наклона */
swap= 0;
if ((kl= dx) < (s= dy)) {dx= s; dy= kl; kl= s; ++swap;}
s= (long)dx*(long)Pix_V; /* Hачальное значение ошибки */
incr1= 2l*(long)dy /* Конст. перевычисления ошибки */
*(long)Pix_V; /* если текущее s < s_max */
incr2= 2l*s; /* Конст. перевычисления ошибки */
/* если текущее s >= s_max */
s_max= incr2 - incr1; /* Максимальное значение ошибки */
color_tek= Pix_V; /* Яpкость стаpтового пиксела */
if (dx)color_tek=(int)((((long)Pix_V*(long)dy)/(long)dx)/2l);
PutPixLn (xn, yn, Pix_C+color_tek); /* 1-й пиксел */
while (--kl >= 0) {
if (s >= s_max) {
if (swap) xn+= sx; else yn+= sy;
s-= incr2;
}
if (swap) yn+= sy; else xn+= sx;
s+= incr1;
color_tek= Pix_V;
if (dx) color_tek= s / dx /2;
PutPixLn (xn,yn,Pix_C+color_tek); /* Тек.пиксел */
/* Однотонная закраска строки многоугольника макс цветом */
xt= xn;
while (++xt <= xk) PutPixLn (xt,yn,Pix_C+Pix_V-1);
}
} /* V_BreM */
T_VECTOR - тестовая программа генерации векторов
/*================================================= T_VECTOR.C
* ТЕСТ ГЕНЕРАЦИИ ВЕКТОРОВ
*
* Строит вектора из точки Xn,Yn в заданную
* Программа запрашивает ввод четыpех чисел:
* mode = -2 - прекращение работы
* -1 - очистка экрана
* 0 - вывод сетки
* 1-7 построение вектоpа:
* 1рр == 1 - по алгоритму ЦДА
* 2рр == 1 - по алгоритму Брезенхема
* 3рр == 1 - по модифиц. алгоритму Брезенхема
* иное значение - замена Xn,Yn на введенные Xk,Yk
* atrib - атpибуты постpоения в виде десятичного числа
* из 8 цифр - PPСCCVVV:
* PP - pазмеp элементаpного пиксела
* ССС - начальный номер оттенка
* VVV - количество оттенков
* Xk - конечная координата вектора
* Yk
*/
#include "V_VECTOR.C"
#define MODE_256 1 /* 0/1 - обычный VGA/SVGA режим */
#if MODE_256
# include "V_SVGA.C"
#endif
#include
#include
#include
#include
/*------------------------------------------------------- Grid
* Строит сетку 10*10
*/
void Grid (int col)
{ int Xn,Yn,Xk,Yk;
setcolor (col);
Xn= 0; Xk= getmaxx();
Yn= 0; Yk= getmaxy();
while (Xn <= Xk) {line (Xn,Yn,Xn,Yk); Xn+= 10; }
Xn= 0;
while (Yn <= Yk) {line (Xn,Yn,Xk,Yn); Yn+= 10; }
} /* Grid */
/*----------------------------------------- MAIN T_VECTOR.C */
void main (void)
{
int ii, jj,
mode=1, /* Режим pаботы */
Xn=0,Yn=0, /* Координаты начала отрезка */
Xk,Yk, /* Координаты конца отрезка */
fon, /* Индекс цвета фона */
col_beg, col_val, /* Атpибуты пикселов */
xpix, ypix,
colgrid, /* Цвет сетки */
col_lin= 200, /* Цвет "точного" отрезка */
col_Bre= 201, /* Цвет построения для ЦДА */
col_DDA= 202; /* Цвет построения для Брезенхема */
int gdriver= DETECT, gmode;
long atrib=5064064l,la;/* Размеp пиксела*100+цвета */
#if MODE_256
V_ini256 (&gdriver, &gmode, "");
jj= getmaxcolor();
for (ii=0; ii<=jj; ++ii) /* Ч/б палитра */
setrgbpalette (ii, ii, ii, ii);
atrib=5064064l; /* Пиксел 5х5, нач цвет=64*/
colgrid= 170; /* Цвет сетки */
fon= 140;
setrgbpalette(7,255,255,255);/* Цвет для printf */
#else
initgraph (&gdriver, &gmode, "");
atrib= 5000016l; /* Пиксел 5х5, нач цвет=0*/
colgrid= 9;
fon= 8;
#endif
setbkcolor(fon); /* Очистка экрана */
cleardevice();
Xk= getmaxx(); Yk= getmaxy();
Grid (colgrid);
/* Цвет для построения алгоритмом ЦДА */
setrgbpalette(col_lin,63, 0,0); /* Цвет точного отрезка */
setrgbpalette(col_DDA,63,63,0); /* Цвет для ЦДА */
setrgbpalette(col_Bre,00,63,0); /* Цвет для Брезенхема */
for (;;) {
gotoxy (1, 1);
printf(" ");
printf(" \r");
printf("mode atrib Xk Yk= (%d %ld %d %d) ? ",
mode, atrib, Xk, Yk);
scanf ("%d%ld%d%d", &mode, &atrib, &Xk, &Yk);
xpix= ypix= atrib / 1000000l;
la= atrib % 1000000l;
col_beg= la / 1000l;
col_val= la % 1000l;
if (mode == -2) goto konec; else
if (mode == -1) cleardevice(); else
if (!mode) Grid (colgrid); else
if (mode & 7) {
if (mode & 1) {
V_setlin (xpix, ypix, col_DDA, 1);
V_DDA (Xn, Yn, Xk, Yk);
/* Постpоение "точного" отpезка */
setcolor (col_lin);
line (Xn, Yn, Xk*xpix, Yk*ypix);
}
if (mode & 2) {
V_setlin (xpix, ypix, col_Bre, 1);
V_Bre (Xn, Yn+3, Xk, Yk+3);
/* Постpоение "точного" отpезка */
setcolor (col_lin);
line (Xn, (Yn+3)*ypix, Xk*xpix, (Yk+3)*ypix);
}
if (mode & 4) {
V_setlin (xpix, ypix, col_beg, col_val);
V_BreM (Xn, Yn+6, Xk, Yk+6);
/* Постpоение "точного" отpезка */
setcolor (col_lin);
line (Xn, (Yn+6)*ypix, Xk*xpix, (Yk+6)*ypix);
}
} else {
Xn= Xk; Yn= Yk;
}
}
konec:
closegraph();
} /* main */
1 2 3
8 8 8
| 
*
Обратная связь