:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте ::
Путь: Графика » Рисование » Отрезок
  Генерация отрезка



Алгоритмы взяты из прекрасной книги
П.В.Вельтмандер "Машинная графика"

Назначение генератора векторов - соединение двух точек изображения отрезком прямой.

Далее будут рассмотрены четыре алгоритма:

· два алгоритма ЦДА - цифрового дифференциального анализатора (DDA - Digital Differential Analyzer) для генерации векторов - обычный и несимметричный;

· алгоритм Брезенхема для генерации векторов[];

· алгоритм Брезенхема для генерации ребер заполненного многоугольника с уменьшением ступенчатости.

Перед рассмотрением конкретных алгоритмов сформулируем общие требования к изображению отрезка:

· концы отрезка должны находиться в заданных точках;

· отрезки должны выглядеть прямыми,

· яркость вдоль отрезка должна быть постоянной и не зависеть от длины и наклона.

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

· концы отрезка в общем случае располагаются на пикселах, лишь наиболее близких к требуемым позициям и только в частных случаях координаты концов отрезка точно совпадают с координатами пикселов;

· отрезок аппроксимируется набором пикселов и лишь в частных случаях вертикальных, горизонтальных и отрезков под 45° они будут выглядеть прямыми, причем гладкими прямыми, без ступенек только для вертикальных и горизонтальных отрезков (рис. );

· яркость для различных отрезков и даже вдоль отрезка в общем случае различна, так как, например, расстояние между центрами пикселов для вертикального отрезка и отрезка под 45° различно (см. рис. ).


Рисунок 14

Рис. 1: Растровое представление различных векторов

Объективное улучшение аппроксимации достигается увеличением разрешения дисплея, но в силу существенных технологических проблем разрешение для растровых систем приемлемой скорости разрешение составляет порядка 1280×1024.

Субъективное улучшение аппроксимации основано на психофизиологических особенностях зрения и, в частности, может достигаться просто уменьшением размеров экрана. Другие способы субъективного улучшения качества аппроксимации основаны на различных программных ухищрениях по "размыванию" резких границ изображения.

Далее в этом разделе рассмотрены три алгоритма генерации отрезка.


  1  Цифровой дифференциальный анализатор



С помощью ЦДА решается дифференциальное уравнение отрезка, имеющее вид:

dY
dX
= Py
Px
,

где Py = Yk - Yn - приращение координат отрезка по оси Y, а Px = Xk - Xn - приращение координат отрезка по оси X.

При этом ЦДА формирует дискретную аппроксимацию непрерывного решения этого дифференциального уравнения.

В обычном ЦДА, используемом, как правило, в векторных устройствах, тем или иным образом определяется количество узлов N, используемых для аппроксимации отрезка. Затем за N циклов вычисляются координаты очередных узлов:

X0 =   Xn;     Xi+1 = Xi + Px/N.

Y0 =   Yn;     Yi+1 = Yi + Py/N.

Получаемые значения Xi, Yi преобразуются в целочисленные значения координаты очередного подсвечиваемого пиксела либо округлением, либо отбрасыванием дробной части.

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

Кроме того из-за независимого вычисления обеих координат нет предпочтительных направлений и построенные отрезки кажутся не очень красивыми.

Субъективно лучше смотрятся вектора с единичным шагом по большей относительной координате (несимметричный ЦДА). Для Px > Py (при Px, Py > 0) это означает, что координата по X направлению должна увеличиться на 1 Px раз, а координата по Y-направлению должна также Px раз увеличиться, но на Py/Px.

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

Для генерации отрезка из точки (x1,y1) в точку (x2,y2) в первом октанте (Px і Py і 0) алгоритм несимметричного ЦДА имеет вид:

  1. Вычислить приращения координат:
           Px= x2 - x1;
           Py= y2 - y1;
     
  2. Занести начальную точку отрезка
           PutPixel (x1, y1);
     
  3. Сгенерировать отрезок
           while (x1  <  x2) {
               x1:= x1 + 1.0;
               y1:= y1 + Py/Px;
               PutPixel (x1, y1);
               }
     
     
Пример генерации отрезка по алгоритму несимметричного ЦДА приведен на рис. .

В Приложении 2 приведена программа V_DDA, реализующая данный алгоритм.


Рисунок 15

Рис. 2: Генерация отрезка несимметричным ЦДА


  2  Алгоритм Брезенхема



Так как приращения координат, как правило, не являются целой степенью двойки, то в ЦДА-алгоритме (см. предыдущий пункт) требуется выполнение деления, что не всегда желательно, особенно при аппаратной реализации.

Брезенхем в работе [] предложил алгоритм, не требующий деления, как и в алгоритме несимметричного ЦДА, но обеспечивающий минимизацию отклонения сгенерированного образа от истинного отрезка, как в алгоритме обычного ЦДА. Основная идея алгоритма состоит в том, что если угловой коэффициент прямой < 1/2, то естественно точку, следующую за точкой (0,0), поставить в позицию (1,0) (рис. а), а если угловой коэффициент > 1/2, то - в позицию (1,1) (рис. б). Для принятия решения куда заносить очередной пиксел вводится величина отклонения Е точной позиции от середины между двумя возможными растровыми точками в направлении наименьшей относительной координаты. Знак Е используется как критерий для выбора ближайшей растровой точки.


Рисунок 16

Рис. 3: Алгоритм Брезенхема генерации отрезков

Если Е < 0, то точное Y-значение округляется до последнего меньшего целочисленного значения Y, т.е. Y-координата не меняется по сравнению с предыдущей точкой. В противном случае Y увеличивается на 1.

Для вычисления Е без ограничения общности упрощающе положим, что рассматриваемый вектор начинается в точке (0,0) и проходит через точку (4, 1.5) (см. рис. 0.3в), т.е. имеет положительный наклон меньший 1.

Из рис. 0.3в видно, отклонение для первого шага:

Е1 = Py/Px - 1/2 < 0,

поэтому для занесения пиксела выбирается точка (1,0).

Отклонение для второго шага вычисляется добавлением приращения Y-координаты для следующей X-позиции (см. рис. 0.3в):

Е2 = Е1 + Py/Px > 0,

поэтому для занесения пиксела выбирается точка (2,1). Так как отклонение считается от Y-координаты, которая теперь увеличилась на 1, то из накопленного отклонения для вычисления последующих отклонений надо вычесть 1:

Е2 = Е2 - 1.

Отклонение для третьего шага:

Е3 = Е2 + Py/Px < 0,

поэтому для занесения пиксела выбирается точка (3,1).

Суммируя и обозначая большими буквами растровые точки, а маленькими - точки вектора, получаем:

Е1 = y1 - 1/2 = dY/dX - 1/2.

Возможны случаи:

Е1 > 0 E1 Ј 0
ближайшая точка есть:
X1 = X0 + 1;    Y1 = Y0 + 1; X1 = X0 + 1;     Y1 = Y0;
E2 = Е1 + Py/Px - 1; E2 = E1 + Py/Px.

Так как интересует только знак Е, то можно избавиться от неудобные частных умножением E на 2×Px:

E1 = 2×Py - Px
E1 > 0: E2 = E1 + 2×(Py - Px)
E1 Ј 0: E2 = E1 + 2×Py


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

X=  x1;
Y=  y1;
Px= x2 - x1;
Py= y2 - y1;
E=  2*Py - Px;
i=  Px;
PutPixel(X, Y);    /* Первая точка вектора */
while ( i=i- 1 >=  0) {
  if (E  >=  0) {
    X= X + 1;
    Y= Y + 1;
    E= E + 2*(Py - Px);
  } else
    X= X + 1;
    E= E + 2*Py;
  PutPixel(X, Y); /* Очередная точка вектора */
}

Этот алгоритм пригоден для случая 0    Ј   dY    Ј   dX. Для других случаев алгоритм строится аналогичным образом.

На рис.  приведен пример генерации по алгоритму Брезенхема того же самого отрезка, что и показанного на рис. 0.2 для генерации по алгоритму несимметричного ЦДА. Из сравнения рисунков видно, что результаты различны.


Рисунок 17

Рис. 4: Генерация отрезка по алгоритму Брезенхема

В Приложении 2 приведена программа V_BRE, реализующая описанный выше алгоритм.

Разработаны алгоритмы цифрового генератора для окружностей и других конических сечений.


  3  Улучшение качества аппроксимации векторов



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

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

Наиболее заметно ухудшает качество изображения ступенчатость. Имеется следующие способы борьбы со ступенчатостью :

· увеличение пространственного разрешения за счет усовершенствования аппаратуры,

· трактовка пиксела не как точки, а как площадки конечного размера, яркость которой зависит от размера площади пиксела, занятой изображением отрезка,

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

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

Модифицированный алгоритм Брезенхема

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

На рис.  приведена иллюстрация построения ребра многоугольника с тангенсом угла наклона 11/21.

На рис. а) показан результат генерации многоугольника с использованием ранее рассмотренного алгоритма Брезенхема при двухуровневом изображении (пиксел или закрашен или не закрашен).

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

На рис. в) показан результат генерации многоугольника с вычислением интесивности пиксела, через который проходит ребро многоугольника в соответствии с модифицированным алгоритмом Брезенхема.

Как видно из рис.  при построении ребра многоугольника с тангенсом угла наклона t  (0 Ј t Ј 1) могут захватываться либо один пиксел (пикселы (0,0), (2,1), (4,2), (6,8)) либо два пиксела (пикселы (1,0) и (1,1), (3,1) и (3,2), (5,2) и (5,3)). Если захватывается один пиксел, то часть его площади, попавшая внутрь многоугольника, равна dy + t/2 (рис. a).

Если же захватывается два пиксела, то часть площади нижнего пиксела, попавшая внутрь многоугольника равна 1 - [((1 - dy)2)/ 2t], а верхнего - [((dy - 1 + 2)2)/ 2t] (см. рис. б). Суммарная площадь частей для двух пикселов, попавшая внутрь многоугольника, равна dy + t/2.

Если теперь в исходном алгоритме Брезенхема (см. 2) заменить отклонение E на E' = E + (1-t), то 0 Ј E' Ј 1) и значение E' будет давать значение той части площади пиксела, которая находится внутри многоугольника.

Выполняя преобразование над значением отклонения для первого шага (см. 2) получим, что начальное значение станет равным 1/2. Максимальное значение отклонения E'max, при превышении которого производится увеличение Y-координаты занесения пикселов, станет равным (1 - t).


Рисунок 18

Рис. 5: Устранение ступенчатости ребер многоугольника

а) генерация ребер без устранения ступенчатости;
б) точное вычисление интенсивности пикселов границы;
в) формирование пикселов границы по модифицированному методу Брезенхема.


Рисунок 19

Рис. 6: Устранение ступенчатости за счет учета площади пикселов, пересекаемых ребром многоугольника

Для того, чтобы оперировать не дробной частью максимальной интенсивности, а непосредственно ее значениями достаточно домножить на полное число уровней интенсивности I тангенс угла наклона (t), начальное (E') и максимальное (E'max) значения отклонения.

В результате получается следующий алгоритм, пригодный для случая 0 Ј dY Ј dX:

X=  x1;
Y=  y1;
Px= x2 - x1;
Py= y2 - y1;>
t= I*Py / Px;
E' >= I/2;
E'max= I - I*Py / Px;
i=  Px;
PutPixel(X, Y, t/2);    /* Первая точка вектора */
while (i = i - 1 >= 0) {<br>
  if (E' >= і E'max) {
    X= X + 1;
    Y= Y + 1;
    E' = E'- E'max;
  } else
    X= X + 1;
    E' = E'+ t;
  PutPixel(X, Y, E'); /* Очередная точка вектора */
}

Для избавления от вещественной арифметики при манипулировании с E' можно домножить уже упомянутые величины на 2*Px. Но в этом случае при занесении пикселов потребуется деление E' на 2*Px.

В Приложении 2 приведена процедура V_BreM, реализующая модифицированный алгоритм Брезенхема для генерации ребра заполненного многоугольника и пригодная для любого октанта.


  4  Улучшение качества изображения фильтрацией



Мы здесь рассмотрим методы, основанные на "размывании" границы.

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

Другой метод заключается в усреднении изображения без изменения его разрешения. В этом случае усредняющая маска перемещается по изображению с единичными шагами.

Очевидно, что первый метод должен давать более качественное изображение, но при больших затратах ресурсов. Для усреднения предложены различные маски ([,]).

Простейшее усреднение - равномерное (рис. ). Улучшить усреднение можно за счет использования весов, задающих влияние отдельных подпикселов на атрибут пиксела экрана (см. рис. ).


Рисунок 20

Рис. 7: Маски для равномерного усреднения изображения


Рисунок 21

Рис. 8: Маски для взвешенного усреднения изображения

Эти массивы должны быть пронормированы для получения единичного коэффициента передачи, чтобы не вызывать неправильного смещения средней яркости изображения. Нормирующий коэффициент равен 1 / (сумму членов массива).

Ясно, что эти преобразования, примененные изображению зашумленному случайными импульсными помехами, будут подавлять шум. Это так называемые низкочастотные фильтры.

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


  0.13  Приложение 2. Процедуры генерации отрезков



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

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

В тестовой программе предусмотрено, что при наличии SVGA-адаптера он может использоваться как в обычном режиме, так и в режиме до 1024x768 точек с 256 цветами.

/*------------------------------------------------- V_VECTOR.C
 * Подпрограммы генерации векторов
 */

#include <graphics.h>
#include <stdio.h>

#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 */


  0.13.1  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 */


  0.13.2  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 */


  0.13.3  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 */


  0.13.4  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 <conio.h>
#include <graphics.h>
#include <stdio.h>
#include <stdlib.h>

/*------------------------------------------------------- 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 */

  0.14  Приложение 3. Процедуры фильтрации



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

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

Аналогично, представлены две процедуры усреднения изображения с понижением разрешения - V_fltr2 и V_fltr3.

При фильтрации и усреднении может использоваться одна из пяти предусмотренных масок фильтрации.

/*================================================== V_FILTR.C
 * В файле V_FILTR.C содержатся процедуры
 * поддержки фильтрации изображений:
 *
 * GetStr, PutStr - служебные
 *
 * V_fltr0 - фильтрует изображение в прямоугольной области,
 *           работая прямо с видеопамятью
 * V_fltr1 - фильтрует изображение в прямоугольной области,
 *           работая с буферами строк
 * V_fltr2 - усредняет картину по маске с понижением
 *           разрешения, работая прямо с видеопамятью
 * V_fltr3 - усредняет картину по маске с понижением
 *           разрешения, работая с буферами строк
 */

#include <alloc.h>

#define GetMay getpixel
#define PutMay putpixel

static int
   Mask0[]= {1,1, 1,1 },
   Mask1[]= {1,1,1, 1,1,1, 1,1,1 },
   Mask2[]= {1,1,1, 1,2,1, 1,1,1 },
   Mask3[]= {1,2,1, 2,4,2, 1,2,1 },
   Mask4[]= {1,1,1,1,
             1,1,1,1,
             1,1,1,1,
             1,1,1,1 },
   Mask5[]= {1,2, 3, 4, 3,2,1,
             2,4, 6, 8, 6,4,2,
             3,6, 9,12, 9,6,5,
             4,8,12,16,12,8,4,
             3,6, 9,12, 9,6,5,
             2,4, 6, 8, 6,4,2,
             1,2, 3, 4, 3,2,1 },
   Mask_ln[]= {2, 3, 3, 3, 4, 7},   /* Размер маски    */
   Mask_st[]= {2, 2, 2, 2, 4, 4},   /* Шаг усреднения  */
   Mask_vl[]= {4, 9,10,16,16,256},  /* Сумма элементов */
   *Mask_bg[]={                    /* Адреса начал    */
      Mask0,Mask1,Mask2,Mask3,Mask4,Mask5
   };

/*----------------------------------------------------- GetStr
 * Запрашивает фрагмент растровой строки из видеопамяти
 */
static void GetStr (st, Yst, Xn, Xk)
char *st;  int Yst, Xn, Xk;
{ while (Xn <= Xk) *st++= GetMay (Xn++, Yst); }


/*----------------------------------------------------- PutStr
 * Записывает фрагмент растровой строки в видеопамять
 */
static void PutStr (st, Yst, Xn, Xk)
char *st;  int Yst, Xn, Xk;
{while (Xn <= Xk) PutMay (Xn++, Yst, *st++); }


/*---------------------------------------------------- V_fltr0
 * Фильтрует изображение в прямоугольной области,
 * работая прямо с видеопамятью
 * msknum              = 0-5 - номер маски фильтра
 * Xn_source,Yn_source - окно исходного изображения
 * Xk_source,Xk_source
 * Xn_target,Yn_target - верхний левый угол результата
 */
void V_fltr0 (msknum,Xn_source,Yn_source,Xk_source,Yk_source,
              Xn_target,Yn_target)
int  msknum,Xn_source,Yn_source,Xk_source,Yk_source,
     Xn_target,Yn_target;
{
   char *plut;          /* Указатель палитры */
   int  *pi;            /* Тек указат маски  */
   int  pixel;          /* Пиксел исх изображения */
   int  *Maska,         /* Указатель маски */
        Mask_Y,Mask_X,  /* Размеры маски   */
        X_centr,Y_centr,/* Центр маски     */
        Mask_sum,       /* Сумма элементов */
        Xk,             /* Предельные положения маски */
        Yk,             /* в исходной области */
        s, sr, sg, sb,  /* Скаляры для суммир в маской   */
        ii, jj,
        Xt, Yt;

/* Запрос параметров маски */
   Maska=  Mask_bg[msknum];             /* Указатель маски */
   Mask_Y= Mask_X= Mask_ln[msknum];     /* Размеры маски   */
   X_centr= Mask_X / 2;                 /* Центр маски     */
   Y_centr= Mask_Y / 2;
   Mask_sum= Mask_vl[msknum];           /* Сумма элементов */

/* Предельные положения маски в исходной области */
   Xk= Xk_source+1-Mask_X;
   Yk= Yk_source+1-Mask_Y;

/*------- Фильтрация с прямой работой с видеопамятью -------*/

   for (Yt= Yn_source; Yt<=Yk; ++Yt) {
      for (Xt=Xn_source; Xt<=Xk; ++Xt) {
         pi= Maska; sr=0; sg=0; sb=0;   /* Суммированные RGB*/
         for (ii=0; ii<Mask_Y; ++ii)
            for (jj=0; jj<Mask_X; ++jj) {
               pixel= GetMay (Xt+jj, Yt+ii);
               plut= &V_pal256[pixel][0];
               s= *pi++;                /* Элемент маски */
               sr+= (s * *plut++);      /* Суммирование  */
               sg+= (s * *plut++);      /* по цветам с   */
               sb+= (s * *plut++);      /* весами маски  */
            }
         sr /= Mask_sum; sg /= Mask_sum;  sb /= Mask_sum;
/* Поиск элемента ТЦ, наиболее подходящего для данных R,G,B */
         ii= V_clrint (sr, sg, sb);
         PutMay (Xn_target+(Xt-Xn_source)+X_centr,
                 Yn_target+(Yt-Yn_source)+Y_centr, ii);
      }
   }
}  /* V_fltr0 */


/*---------------------------------------------------- V_fltr1
 * Фильтрует изображение в прямоугольной области,
 * работая с буферами строк
 * msknum              = 0-5 - номер маски фильтра
 * Xn_source,Yn_source - окно исходного изображения
 * Xk_source,Xk_source
 * Xn_target,Yn_target - верхний левый угол результата
 */
void V_fltr1 (msknum,Xn_source,Yn_source,Xk_source,Yk_source,
              Xn_target,Yn_target)
int  msknum,Xn_source,Yn_source,Xk_source,Yk_source,
     Xn_target,Yn_target;
{
   char *plut;          /* Указатель палитры */
   int  *pi;            /* Тек указат маски  */
   int  pixel;          /* Пиксел исх изображения */
   int  *Maska,         /* Указатель маски */
        Mask_Y,Mask_X,  /* Размеры маски   */
        X_centr,Y_centr,/* Центр маски     */
        Mask_sum,       /* Сумма элементов */
        Xk,             /* Предельные положения маски */
        Yk,             /* в исходной области */
        Dx_source,      /* Размер строки исх изображения */
        Ystr,           /* Y тек читаемой строки изображ */
        s, sr, sg, sb,  /* Скаляры для суммир в маской   */
        ii, jj,
        Xt, Yt;
   char *ps, *sbuf, *pt, *tbuf, *ptstr[8];

   Dx_source= Xk_source-Xn_source+1;

/* Запрос параметров маски */
   Maska=  Mask_bg[msknum];             /* Указатель маски */
   Mask_Y= Mask_X= Mask_ln[msknum];     /* Размеры маски   */
   X_centr= Mask_X / 2;                 /* Центр маски     */
   Y_centr= Mask_Y / 2;
   Mask_sum= Mask_vl[msknum];           /* Сумма элементов */

/* Предельные положения маски в исходной области */
   Xk= Xk_source+1-Mask_X;
   Yk= Yk_source+1-Mask_Y;

/* Заказ буферов */
   if ((sbuf= malloc (Dx_source * Mask_Y)) == NULL) goto all;
   if ((tbuf= malloc (Dx_source)) == NULL)
      goto fr_sbuf;

/*------- Фильтрация с использованием буферов строк --------*/

/* Подготовка массива указателей на строки
 *  ptstr[0] --> последняя строка
 *  ptstr[1] --> строка 0
 *  ptstr[2] --> строка 1
 *  и т.д.
 */
   ps= sbuf;  ii= Mask_Y;  jj= 1;
   do {
      ptstr[jj]= ps;  ps+= Dx_source;
      if (++jj == Mask_Y) jj= 0;
   } while (--ii > 0);

/* Начальное чтение Mask_Y - 1 строк */
   Ystr= Yn_source;
   for (ii=1; ii<Mask_Y; ++ii)
      GetStr (ptstr[ii], Ystr++, Xn_source, Xk_source);

   for (Yt= Yn_source; Yt<=Yk; ++Yt) {

/* Запрос следующей строки и циклический сдвиг указателей */
      GetStr (ps= ptstr[0], Ystr++, Xn_source, Xk_source);
      jj= Mask_Y-1;
      for (ii=0; ii<jj; ++ii) ptstr[ii]= ptstr[ii+1];
      ptstr[jj]= ps;

      pt= tbuf;
      for (Xt=Xn_source; Xt<=Xk; ++Xt) {
         pi= Maska; sr=0; sg=0; sb=0;   /* Суммированные RGB*/
         for (ii=0; ii<Mask_Y; ++ii) {
            ps= ptstr[ii] + (Xt-Xn_source);
            for (jj=0; jj<Mask_X; ++jj) {
               plut= &V_pal256[*ps++ & 255][0];
               s= *pi++;                /* Элемент маски */
               sr+= (s * *plut++);      /* Суммирование  */
               sg+= (s * *plut++);      /* по цветам с   */
               sb+= (s * *plut++);      /* весами маски  */
            }
         }
         sr /= Mask_sum; sg /= Mask_sum;  sb /= Mask_sum;
/* Поиск элемента ТЦ, наиболее подходящего для данных R,G,B */
         *pt++= V_clrint (sr, sg, sb);
      }
      PutStr (tbuf,                     /* Запись строки */
              Yn_target + Y_centr + (Yt-Yn_source) ,
              Xn_target + X_centr,
              Xn_target + X_centr + (--pt - tbuf));
   }
   free (tbuf);
fr_sbuf:
   free (sbuf);
all:;
}  /* V_fltr1 */


/*---------------------------------------------------- V_fltr2
 * Усредняет картину по маске с понижением разрешения,
 * работая прямо с видеопамятью
 * msknum              = 0-5 - номер маски фильтра
 * Xn_source,Yn_source - окно исходного изображения
 * Xk_source,Xk_source
 * Xn_target,Yn_target - верхний левый угол результата
 */
void V_fltr2 (msknum,Xn_source,Yn_source,Xk_source,Yk_source,
              Xn_target,Yn_target)
int  msknum,Xn_source,Yn_source,Xk_source,Yk_source,
     Xn_target,Yn_target;
{
   char *plut;          /* Указатель палитры */
   int  *pi;            /* Тек указат маски  */
   int  pixel;          /* Пиксел исх изображения */
   int  *Maska,         /* Указатель маски */
        Mask_Y,Mask_X,  /* Размеры маски   */
        X_centr,Y_centr,/* Центр маски     */
        Mask_sum,       /* Сумма элементов */
        Xk,             /* Предельные положения маски */
        Yk,             /* в исходной области */
        s, sr, sg, sb,  /* Скаляры для суммир в маской   */
        Xr,Yr,          /* Координаты пиксела результата */
        Sm,             /* Сдвиг маски для обраб след точки */
        ii, jj,
        Xt, Yt;

/* Запрос параметров маски */
   Maska=  Mask_bg[msknum];             /* Указатель маски */
   Mask_Y= Mask_X= Mask_ln[msknum];     /* Размеры маски   */
   X_centr= Mask_X / 2;                 /* Центр маски     */
   Y_centr= Mask_Y / 2;
   Mask_sum= Mask_vl[msknum];           /* Сумма элементов */

/* Предельные положения маски в исходной области */
   Xk= Xk_source+1-Mask_X;
   Yk= Yk_source+1-Mask_Y;

   Yt= Yn_source;
   Yr= Yn_target+Y_centr;
   Sm= Mask_st[msknum];                 /* Шаг усреднения*/
   while (Yt <= Yk) {
      Xt=Xn_source;  Xr= Xn_target+X_centr;
      while (Xt <= Xk) {
         pi= Maska; sr=0; sg=0; sb=0;   /* Суммированные RGB*/
         for (ii=0; ii<Mask_Y; ++ii)
            for (jj=0; jj<Mask_X; ++jj) {
               pixel= GetMay (Xt+jj, Yt+ii);
               plut= &V_pal256[pixel][0];
               s= *pi++;                /* Элемент маски */
               sr+= (s * *plut++);      /* Суммирование  */
               sg+= (s * *plut++);      /* по цветам с   */
               sb+= (s * *plut++);      /* весами маски  */
            }
         sr /= Mask_sum; sg /= Mask_sum;  sb /= Mask_sum;
/* Поиск элемента ТЦ, наиболее подходящего для данных R,G,B */
         ii= V_clrint (sr, sg, sb);
         PutMay (Xr++, Yr, ii);
         Xt+= Sm;
      }
      Yt+= Sm;  ++Yr;
   }
}  /* V_fltr2 */


/*---------------------------------------------------- V_fltr3
 * Усредняет картину по маске с понижением разрешения,
 * работая с буферами строк
 * msknum              = 0-5 - номер маски фильтра
 * Xn_source,Yn_source - окно исходного изображения
 * Xk_source,Xk_source
 * Xn_target,Yn_target - верхний левый угол результата
 */
void V_fltr3 (msknum,Xn_source,Yn_source,Xk_source,Yk_source,
              Xn_target,Yn_target)
int  msknum,Xn_source,Yn_source,Xk_source,Yk_source,
     Xn_target,Yn_target;
{
   char *plut;          /* Указатель палитры */
   int  *pi;            /* Тек указат маски  */
   int  pixel;          /* Пиксел исх изображения */
   int  *Maska,         /* Указатель маски */
        Mask_Y,Mask_X,  /* Размеры маски   */
        X_centr,Y_centr,/* Центр маски     */
        Mask_sum,       /* Сумма элементов */
        Xk,             /* Предельные положения маски */
        Yk,             /* в исходной области */
        Dx_source,      /* Размер строки исх изображения */
        s, sr, sg, sb,  /* Скаляры для суммир в маской   */
        Xr,Yr,          /* Координаты пиксела результата */
        Sm,             /* Сдвиг маски для обраб след точки */
        ii, jj,
        Xt, Yt;
   char *ps, *sbuf, *pt, *tbuf, *ptstr[8];


   Dx_source= Xk_source-Xn_source+1;

/* Запрос параметров маски */
   Maska=  Mask_bg[msknum];             /* Указатель маски */
   Mask_Y= Mask_X= Mask_ln[msknum];     /* Размеры маски   */
   X_centr= Mask_X / 2;                 /* Центр маски     */
   Y_centr= Mask_Y / 2;
   Mask_sum= Mask_vl[msknum];           /* Сумма элементов */

/* Предельные положения маски в исходной области */
   Xk= Xk_source+1-Mask_X;
   Yk= Yk_source+1-Mask_Y;

/* Заказ буферов */
   if ((sbuf= malloc (Dx_source * Mask_Y)) == NULL) goto all;
   if ((tbuf= malloc (Dx_source/Mask_st[msknum]+16)) == NULL)
      goto fr_sbuf;

/* Подготовка массива указателей на строки
 *  ptstr[0] --> строка 0
 *  ptstr[1] --> строка 1
 *  ptstr[2] --> строка 2
 *  и т.д.
 */
   ps= sbuf;
   for (ii=0; ii<Mask_Y; ++ii) {
      ptstr[ii]= ps;  ps+= Dx_source;
   }

   Yt= Yn_source;
   Yr= Yn_target+Y_centr;
   Sm= Mask_st[msknum];                 /* Шаг усреднения*/
   while (Yt <= Yk) {
      for (ii=0; ii<Mask_Y; ++ii)       /* Чтен исх строк */
         GetStr (ptstr[ii], Yt+ii, Xn_source, Xk_source);
      Xt=Xn_source;  pt= tbuf;
      while (Xt <= Xk) {
         pi= Maska; sr=0; sg=0; sb=0;   /* Суммированные RGB*/
         for (ii=0; ii<Mask_Y; ++ii) {
            ps= ptstr[ii] + (Xt-Xn_source);
            for (jj=0; jj<Mask_X; ++jj) {
               plut= &V_pal256[*ps++ & 255][0];
               s= *pi++;                /* Элемент маски */
               sr+= (s * *plut++);      /* Суммирование  */
               sg+= (s * *plut++);      /* по цветам с   */
               sb+= (s * *plut++);      /* весами маски  */
            }
         }
         sr /= Mask_sum; sg /= Mask_sum;  sb /= Mask_sum;
/* Поиск элемента ТЦ, наиболее подходящего для данных R,G,B */
         *pt++= V_clrint (sr, sg, sb);
         Xt+= Sm;
      }
      PutStr (tbuf,Yr++,                /* Запись строки */
              Xn_target+X_centr,
              Xn_target+X_centr + (--pt - tbuf));
      Yt+= Sm;
   }
   free (tbuf);
fr_sbuf:
   free (sbuf);
all:;
}  /* V_fltr3 */


/*================================================== T_FILTR.C
 *
 * ТЕСТ ФИЛЬТРАЦИИ
 *
 * Программа вначале строит два смещенных вектора
 * большими пикселами, затем последовательно для каждой
 * из пяти масок:
 * - фильтрует с непосредственным доступом к видеопамяти
 * - фильтрует с буферизацией растровых строк
 * - формирует усредненную картинку меньшего разрешения
 *   с непосредственным доступом к видеопамяти
 * - формирует усредненную картинку меньшего разрешения
 *   с буферизацией растровых строк
 *
 * После вывода очередной картинки ждет нажатия любой клавиши
 *
 * Виды масок:
 *   0: 1 1   1: 1 1 1   2: 1 1 1   3: 1 2 1
 *      1 1      1 1 1      1 2 1      2 4 2
 *               1 1 1      1 1 1      1 2 1
 *
 *  4: 1 1 1 1   5: 1 2  3  4  3 2 1
 *     1 1 1 1      2 4  6  8  6 4 2
 *     1 1 1 1      3 6  9 12  9 6 5
 *     1 1 1 1      4 8 12 16 12 8 4
 *                  3 6  9 12  9 6 5
 *                  2 4  6  8  6 4 2
 *                  1 2  3  4  3 2 1
 */

#include "V_VECTOR.C"
#include "VGA_256.C"
#include "V_FILTR.C"

#include <conio.h>
#include <graphics.h>
#include <stdio.h>

#define VECTOR 0  /* 0/1 - фикс вектор/ввод координат */

/*------------------------------------------------------- Grid
 * Строит сетку 10*10
 */

void Grid (void)
{  int Xn,Yn,Xk,Yk;
   setcolor (170);
   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 Filtr */

void main (void)
{
   int  ii, jj,
        mov_lin,                /* 0/1 - позиционир/отрезок */
        Xn,Yn,Xk,Yk,            /* Координаты отрезка       */
        fon=   140;             /* Индекс фона              */
   int  gdriver= DETECT, gmode;
   int  Xn_source, Yn_source,   /* Фильтруемая область      */
        Xk_source, Yk_source,
        Dx_source;
   int  Xn_target, Yn_target,   /* Результаты фильтрации    */
        Xk_target, Yk_target;
   int  msknum;                 /* Номер текущей маски  */
   char *ps;

   V_ini256 (&gdriver, &gmode, "");

   ps= (char *)V_pal256;
   for (ii=0; ii<=255; ++ii) {          /* Ч/б палитра    */
      jj= ii / 4;
      *ps++= jj; *ps++= jj; *ps++= jj;
      setrgbpalette (ii, jj, jj, jj);
   }
   setbkcolor(fon);                     /* Очистка экрана */
   cleardevice();
   Xk= getmaxx(); Yk= getmaxy();

/* Начальные установки для фильтрации */
   Xn_source= 0;                        /* Исходная область */
   Yn_source= 0;
   Xk_source= (Xk + 1)/2 - 1;
   Yk_source= Yk;
   Xn_target= Xk_source + 1;            /* Результ. область */
   Yn_target= 0;
   Xk_target= Xk;
   Yk_target= Yk_source;

   Dx_source= Xk_source-Xn_source+1;    /* X-размер исходной*/

#if VECTOR
   Grid ();
   mov_lin= 1;  Xn= 0;  Yn= 0;  Xk= 0;  Yk= 0;
   for (;;) {
      gotoxy (1, 1);
      printf("                                       \r");
      printf("mov_lin Xk Yk= (%d %d %d) ? ", mov_lin, Xk, Yk);
      scanf ("%d%d%d", &mov_lin, &Xk, &Yk);
      if (mov_lin < 0) cleardevice(); else
      if (!mov_lin) Grid (); else {
         if (mov_lin & 1) V_DDA (0, 0, Xk, Yk);
         if (mov_lin & 2) V_Bre (0, 0, Xk, Yk);
      }
   }
#else
   Xk= Dx_source / Pix_X - 1;
   Yk= (Yk_source-Yn_source+1) / Pix_Y - 1;
   V_DDA (Xn_source, Yn_source,    Xk, Yk-17);
   V_Bre (Xn_source, Yn_source+17, Xk, Yk);
   getch();
#endif

   ii= 0xF;     /* Обе фильтрации и оба сжатия */

   setfillstyle (SOLID_FILL, fon);

   for (msknum=0; msknum<6; ++msknum) {
      if (ii & 1) {     /* Фильтрация из видеоозу */
         bar (Xn_target, Yn_target, Xk_target, Yk_target);
         V_fltr0 (msknum,Xn_source,Yn_source,
                  Xk_source,Yk_source,Xn_target,Yn_target);
        getch ();
      }
      if (ii & 2) {     /* Фильтрация из буферов */
         bar (Xn_target, Yn_target, Xk_target, Yk_target);
         V_fltr1 (msknum,Xn_source,Yn_source,
                  Xk_source,Yk_source,Xn_target,Yn_target);
         getch ();
      }
      if (ii & 4) {     /* Сжатие из из видеоозу */
         bar (Xn_target, Yn_target, Xk_target, Yk_target);
         V_fltr2 (msknum,Xn_source,Yn_source,
                  Xk_source,Yk_source,Xn_target,Yn_target);
        getch ();
      }
      if (ii & 8) {     /* Сжатие из буферов */
         bar (Xn_target, Yn_target, Xk_target, Yk_target);
         V_fltr3 (msknum,Xn_source,Yn_source,
                  Xk_source,Yk_source,Xn_target,Yn_target);
         getch ();
      }
   }
   closegraph();
}  /* main */