04. Разложение в растр по методу ЦДА - p1xelse/CG GitHub Wiki

Процесс нахождения пикселей, аппроксимирующих заданные отрезок, называется разложением в растр.

1. Отрезки должны начинаться и заканчивать в заданных точках. Отрезки должны выглядеть как прямые.
   Выполнено не может быть в полной мере из-за особенностей строения дисплеев, можно лишь добиться визуального восприятия. (Применяя методы устранения ступенчатости)

2. Интенсивность вдоль отрезка должна быть постоянной и не зависеть от длины и наклона. (удовлетворяют также только горизонтальные, вертикальные и наклоненные под углом в 45 отрезки. Однако вертикальные и горизонтальные отрезки по сравнению с отрезками, расположенными под 45 , будут выглядеть ярче, так как расстояние между соседними пикселами у них меньше, чем у наклонных отрезков.)

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

3. Быстродействие алгоритмов.
   Данное требование сводится к оптимизации работы с арифметикой. (Использование целочисленных данных)

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

Куров не давал, но вот псевдокод из Роджерса:

Позиция = начало

Шаг = приращение

1. Блок выборки;

Если позиция - конец < EPS, тогда 4 пункт

Если позиция > конец, тогда пункт 2

Если позиция < конец, тогда пункт 3

2. Позиция = позиция - шаг; goto 1;
3. Позиция = позиция + шаг; goto 1;
4. Конец

Алгоритм цифрового дифференциального анализатора (ЦДА) - использует достаточно общий принцип, известный в математике: изучение какого-либо явления на основе дифференциального уравнения или системы таких уравнений, описывающей это явление. Поскольку прямая линия на плоскости описывается уравнением вида AX+BY+C=0, где A, B, C - коэффициенты этого уравнения, то производная dY/dX является постоянной. Заменив дифференциалы конечными разностями, получим:

, где Xн, Yн и Xк, Yк - координаты начальной и конечной точек отрезка

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

Подставив dY из (1), получим нужную ординату пикселя. Остается определить величину приращения X. В рассматриваемых здесь алгоритмах большее из приращений (X или Y) выбирается в качестве единицы растра, а приращение вдоль другой координатной оси подлежит определению. Если же поступить по-другому (меньшее из приращений взять равным единице), то отрезок на экране может получиться «дырявым», то есть состоящим из отдельных точек, не расположенных вплотную друг к другу.

1. Ввод исходных данных об отрезке.
2. Проверка вырожденности отрезка, если вырожден, то высвечивание точки и переход к 7.
3. dx = Xк-Xн, dy = Yк-Yн
4. Δx = |dx|, Δy = |dy|
5. Если Δx > Δy,
       то l = Δx
       иначе l = Δy
6. dx = dx/l, dy = dy/l.
7. X=Xн, Y=Yн
8. Цикл от i=1 до i=l+1 с шагом 1.

• Высвечивание точки с текущими координатами (E(X), E(Y)). E() - округление до ближайшего целого
• Вычисление координат следующей точки: X=X+dx, Y=Y+dy.

9. Конец