04. Разложение в растр по методу ЦДА - chrislvt/CG GitHub Wiki
Процесс нахождения пикселей, аппроксимирующих заданные отрезок, называется разложением в растр.
-
Отрезки должны начинаться и заканчивать в заданных точках. Отрезки должны выглядеть как прямые.
Выполнено не может быть в полной мере из-за особенностей строения дисплеев, можно лишь добиться визуального восприятия. (Применяя методы устранения ступенчатости) -
Интенсивность вдоль отрезка должна быть постоянной и не зависеть от длины и наклона. (удовлетворяют также только горизонтальные, вертикальные и наклоненные под углом в 45 отрезки. Однако вертикальные и горизонтальные отрезки по сравнению с отрезками, расположенными под 45 , будут выглядеть ярче, так как расстояние между соседними пикселами у них меньше, чем у наклонных отрезков.)
Обеспечение постоянной интенсивности вдоль отрезка требует высвечивания очередного пикселя интенсивностью, зависящей от расстояния между пикселями, вычисление которого производится с извлечением квадратного корня и умножения, что существенно замедляет работу.
-
Быстродействие алгоритмов.
Данное требование сводится к оптимизации работы с арифметикой. (Использование целочисленных данных)
Многие алгоритмы вычерчивания отрезков и кривых используют пошаговый принцип, суть которого состоит в том, что координаты высвечиваемого пикселя определяются каждый раз на очередном шаге вычислений, а не вычисляются заранее для всех пикселей. Результат вычислений на текущем шаге зависит от результатов, полученных на предыдущем шаге.
Куров не давал, но вот псевдокод из Роджерса:
Позиция = начало
Шаг = приращение
- Блок выборки;
Если позиция - конец < EPS, тогда 4 пункт
Если позиция > конец, тогда пункт 2
Если позиция < конец, тогда пункт 3
- Позиция = позиция - шаг; goto 1;
- Позиция = позиция + шаг; goto 1;
- Конец
Алгоритм цифрового дифференциального анализатора (ЦДА) - использует достаточно общий принцип, известный в математике: изучение какого-либо явления на основе дифференциального уравнения или системы таких уравнений, описывающей это явление. Поскольку прямая линия на плоскости описывается уравнением вида AX+BY+C=0, где A, B, C - коэффициенты этого уравнения, то производная dY/dX является постоянной. Заменив дифференциалы конечными разностями, получим:
, где Xн, Yн и Xк, Yк - координаты начальной и конечной точек отрезкаОрдината очередного пикселя может быть вычислена по известной ординате предыдущего пикселя следующим образом:
Подставив dY из (1), получим нужную ординату пикселя. Остается определить величину приращения X. В рассматриваемых здесь алгоритмах большее из приращений (X или Y) выбирается в качестве единицы растра, а приращение вдоль другой координатной оси подлежит определению. Если же поступить по-другому (меньшее из приращений взять равным единице), то отрезок на экране может получиться «дырявым», то есть состоящим из отдельных точек, не расположенных вплотную друг к другу.
- Ввод исходных данных об отрезке.
- Проверка вырожденности отрезка, если вырожден, то высвечивание точки и переход к 7.
- dx = Xк-Xн, dy = Yк-Yн
- Δx = |dx|, Δy = |dy|
- Если Δx > Δy,
то l = Δx
иначе l = Δy - dx = dx/l, dy = dy/l.
- X=Xн, Y=Yн
- Цикл от i=1 до i=l+1 с шагом 1.
- Высвечивание точки с текущими координатами (E(X), E(Y)).
E() - округление до ближайшего целого
- Вычисление координат следующей точки: X=X+dx, Y=Y+dy.
- Конец