Назначение генератора векторов - соединение двух точек изображения отрезком прямой.
Далее будут рассмотрены четыре алгоритма:
Перед рассмотрением конкретных алгоритмов сформулируем общие требования к изображению отрезка:
Ни одно из этих условий не может быть точно выполнено на растровом дисплее в силу того, что изображение строится из пикселов конечных размеров, а именно:
Объективное улучшение аппроксимации достигается увеличением разрешения дисплея, но в силу существенных технологических проблем разрешение для растровых систем приемлемой скорости разрешение составляет порядка 1280×1024.
Субъективное улучшение аппроксимации основано на психофизиологических особенностях зрения и, в частности, может достигаться просто уменьшением размеров экрана. Другие способы субъективного улучшения качества аппроксимации основаны на различных программных ухищрениях по "размыванию" резких границ изображения.
Далее будут рассмотрены три алгоритма генерации отрезка.
С помощью ЦДА решается дифференциальное уравнение отрезка, имеющее вид:
|
где Py = Yk - Yn - приращение координат отрезка по оси Y, а Px = Xk - Xn - приращение координат отрезка по оси X.
При этом ЦДА формирует дискретную аппроксимацию непрерывного решения этого дифференциального уравнения.
В обычном ЦДА, используемом, как правило, в векторных устройствах, тем или иным образом определяется количество узлов N, используемых для аппроксимации отрезка. Затем за N циклов вычисляются координаты очередных узлов:
|
|
Получаемые значения Xi, Yi преобразуются в целочисленные значения координаты очередного подсвечиваемого пиксела либо округлением, либо отбрасыванием дробной части.
Генератор векторов, использующий этот алгоритм, имеет тот недостаток, что точки могут прописываться дважды, что увеличивает время построения.
Кроме того из-за независимого вычисления обеих координат нет предпочтительных направлений и построенные отрезки кажутся не очень красивыми.
Аппаратная реализация этого алгоритма изложена в пункте 8.1 первой части курса.
Субъективно лучше смотрятся вектора с единичным шагом по большей относительной координате (несимметричный ЦДА). Для Px > Py (при Px, Py > 0) это означает, что координата по X направлению должна увеличиться на 1 Px раз, а координата по Y-направлению должна также Px раз увеличиться, но на Py/Px.
Т.е. количество узлов аппроксимации берется равным числу пикселов вдоль наибольшего приращения.
Для генерации отрезка из точки (x1,y1) в точку (x2,y2) в первом октанте (Px і Py і 0) алгоритм несимметричного ЦДА имеет вид:
Пример генерации отрезка по алгоритму несимметричного ЦДА приведен на рис. .
В Приложении 2 приведена программа V_DDA, реализующая данный алгоритм.
Так как приращения координат, как правило, не являются целой степенью двойки, то в ЦДА-алгоритме (см. предыдущий пункт) требуется выполнение деления, что не всегда желательно, особенно при аппаратной реализации.
Брезенхем в работе [] предложил алгоритм, не требующий деления, как и в алгоритме несимметричного ЦДА, но обеспечивающий минимизацию отклонения сгенерированного образа от истинного отрезка, как в алгоритме обычного ЦДА. Основная идея алгоритма состоит в том, что если угловой коэффициент прямой < 1/2, то естественно точку, следующую за точкой (0,0), поставить в позицию (1,0) (рис. а), а если угловой коэффициент > 1/2, то - в позицию (1,1) (рис. б). Для принятия решения куда заносить очередной пиксел вводится величина отклонения Е точной позиции от середины между двумя возможными растровыми точками в направлении наименьшей относительной координаты. Знак Е используется как критерий для выбора ближайшей растровой точки.
Если Е < 0, то точное Y-значение округляется до последнего меньшего целочисленного значения Y, т.е. Y-координата не меняется по сравнению с предыдущей точкой. В противном случае Y увеличивается на 1.
Для вычисления Е без ограничения общности упрощающе положим, что рассматриваемый вектор начинается в точке (0,0) и проходит через точку (4, 1.5) (см. рис. 0.3в), т.е. имеет положительный наклон меньший 1.
Из рис. 0.3в видно, отклонение для первого шага:
|
поэтому для занесения пиксела выбирается точка (1,0).
Отклонение для второго шага вычисляется добавлением приращения Y-координаты для следующей X-позиции (см. рис. 0.3в):
|
поэтому для занесения пиксела выбирается точка (2,1). Так как отклонение считается от Y-координаты, которая теперь увеличилась на 1, то из накопленного отклонения для вычисления последующих отклонений надо вычесть 1:
|
Отклонение для третьего шага:
|
поэтому для занесения пиксела выбирается точка (3,1).
Суммируя и обозначая большими буквами растровые точки, а маленькими - точки вектора, получаем:
|
Возможны случаи:
| Е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 для генерации по алгоритму несимметричного ЦДА. Из сравнения рисунков видно, что результаты различны.
В Приложении 2 приведена программа V_BRE, реализующая описанный выше алгоритм.
Разработаны алгоритмы цифрового генератора для окружностей и других конических сечений.
Выше было отмечено, что растровая генерация отрезков имеет следующие
недостатки:
· неточное расположение начала и конца,
· ступенчатый вид отрезка,
· яркость зависит от наклона и длины.
Ясно, что первый недостаток не может быть устранен программным путем. Неравномерность яркости обычно не слишком заметна и может быть скомпенсирована очевидным образом, требующим, в общем случае, вещественной арифметики, но в связи с реально небольшим количеством различимых уровней яркости достаточно обойтись целочисленным приближением, причем очень грубым.
Наиболее заметно ухудшает качество изображения ступенчатость. Имеется следующие способы борьбы со ступенчатостью :
· увеличение пространственного разрешения за счет усовершенствования
аппаратуры,
· трактовка пиксела не как точки, а как площадки конечного размера,
яркость которой зависит от размера площади пиксела, занятой
изображением отрезка,
· "размывание" резкой границы, за счет частичной подсветки
пикселов, примыкающих к формируемому отрезку. Понятно, что при
этом ухудшается пространственное разрешение изображения.
В данном пункте мы рассмотрим модифицированный алгоритм Брезенхема, трактующий пиксел как конечную площадку. В следующем пункте будет рассмотрен общий подход, использующий низкочастотную фильтрацию для "размывания" границ изображения.
Основная идея алгоритма состоит в том, чтобы для ребер многоугольника устанавливать яркость пиксела пропорционально площади пиксела, попавшей внутрь многоугольника.
На рис. приведена иллюстрация построения ребра многоугольника с тангенсом угла наклона 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.
Если теперь в исходном алгоритме Брезенхема (см. 0.2.2) заменить отклонение E на E' = E + (1-t), то 0 Ј E' Ј 1) и значение E' будет давать значение той части площади пиксела, которая находится внутри многоугольника.
Выполняя преобразование над значением отклонения для первого шага (см. 0.2.2) получим, что начальное значение станет равным 1/2. Максимальное значение отклонения E'max, при превышении которого производится увеличение Y-координаты занесения пикселов, станет равным (1 - t).
Для того, чтобы оперировать не дробной частью максимальной интенсивности, а непосредственно ее значениями достаточно домножить на полное число уровней интенсивности 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) {
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, реализующая модифицированный алгоритм Брезенхема для генерации ребра заполненного многоугольника и пригодная для любого октанта.
Мы здесь рассмотрим методы, основанные на "размывании" границы.
Один из них заключается в том, что изображение строится с большим пространственным разрешением, чем позволяет дисплей. При выводе на экран атрибуты пиксела экрана вычисляются усреднением по группе пикселов изображения, построенного с большим разрешением. Т.е. пикселы изображения рассматриваются как подпикселы соответствующих пикселов экрана. Усредняющая маска перемещается по изображению с шагами, равными ее размеру.
Другой метод заключается в усреднении изображения без изменения его разрешения. В этом случае усредняющая маска перемещается по изображению с единичными шагами.
Очевидно, что первый метод должен давать более качественное изображение, но при больших затратах ресурсов. Для усреднения предложены различные маски ([,]).
Простейшее усреднение - равномерное (рис. ). Улучшить усреднение можно за счет использования весов, задающих влияние отдельных подпикселов на атрибут пиксела экрана (см. рис. ).
Эти массивы должны быть пронормированы для получения единичного коэффициента передачи, чтобы не вызывать неправильного смещения средней яркости изображения. Нормирующий коэффициент равен 1 / (сумму членов массива).
Ясно, что эти преобразования, примененные изображению зашумленному случайными импульсными помехами, будут подавлять шум. Это так называемые низкочастотные фильтры.
В Приложении 3 приведено несколько процедур фильтрации, реализующих оба рассмотренных метода - с понижением и без понижения разрешения.
|
|
 |
