КГ Лекция 03. Растровая графика. Базовые алгоритмы машинной графики. Построение отрезков.
Алгоритмы нижнего уровня -> Алгоритмы среднего уровня (построение плоских изображений) -> Алгоритмы верхнего уровня (удаление невидимого, построение реалистичного изображения)
Процесс определения пикселей, наилучшим образом аппроксимирующих заданный отрезок. Простейшие случаи – горизонтальный, вертикальный и под 45°. В большинстве случаев проявляется лестничный (ступенчатый) эффект.
Общие требования:
- Отрезок должен выглядеть как отрезок прямой, начинаться и заканчиваться в заданных точках
- Интенсивность (яркость) вдоль отрезка должна быть постоянной. Отрезки, имеющие разные углы наклона, должны быть одной интенсивности. Восприятие человека зависит не только от интенсивности свечения объекта, но и от расстояния между светящимися объектами //чтобы удовлетворить этому требованию, надо высвечивать точки с переменной интенсивностью от расстояния – потребует дополнительных вычислений, без особой нужды не используется
- Алгоритмы (особенно нижнего уровня) должны работать быстро
Все алгоритмы имеют пошаговый характер – на очередном шаге высвечиваем пиксель, и производим вычисления, используемые в следующем шаге.
позиция = начало
шаг = приращение
1. if позиция - конец < точность then 4
if позиция > конец then 2
if позиция < конец then 3
2. позиция = позиция - шаг
go to 1
3. позиция = позиция + шаг
go to 1
4. finish
Простой алгоритм разложения отрезка в растр, описанный дальше применяют пошаговый метод.
К базовым алгоритмам или алгоритмам нижнего уровня относят алгоритмы, позволяющие вычерчивать основные геометрические фигуры (отрезки, окружности, эллипсы и т.д.), а также выполнять такие операции, как закраска сплошных областей и отсечение отрезков и многоугольников. Обычно часть из этих алгоритмов реализуется в качестве примитивов в графических библиотеках языков высокого уровня.
Эти алгоритмы используются в алгоритмах более высокого уровня (или верхнего), к которым относят построение трехмерных и реалистических изображений. Основные алгоритмы высокого уровня рассмотрены авторами в методическом пособии по выполнению курсовой работы по "Машинной графике".
Решение поставленной задачи очевидно лишь для трех типов отрезков:
- горизонтальных
- вертикальных
- наклоненных под углом в 45
Перед рассмотрением алгоритмов построения отрезков необходимо сформулировать наиболее общие и простые требования, предъявляемые к таким алгоритмам.
- Во-первых, отрезки должны выглядеть прямыми; начинаться и заканчиваться в заданных точках.
- Во-вторых, яркость вдоль отрезка должна быть постоянной и не зависеть от длины и наклона.
- В-третьих, алгоритмы должны работать быстро.
- Первое требование в силу дискретной природы растрового дисплея выполнено всегда быть не может. Можно лишь добиться того, что визуально (человеческим глазом) отрезок будет восприниматься прямым. Решение этой задачи может достигаться путем увеличения разрешающей способности экрана дисплея и применения методов устранения ступенчатости.
- Второму требованию удовлетворяют также только горизонтальные, вертикальные и наклоненные под углом в 45 отрезки. Однако вертикальные и горизонтальные отрезки по сравнению с отрезками, расположенными под 45 , будут выглядеть ярче, так как расстояние между соседними пикселями у них меньше, чем у наклонных отрезков. Обеспечение постоянной яркости вдоль отрезка требует высвечивания очередного пикселя яркостью, зависящей от расстояния между пикселями, вычисление которого производится с использованием операций извлечения квадратного корня и умножения (возводить в квадрат лучше путем умножения числа самого на себя). Использование этих операций существенно замедляет работу алгоритма, поэтому второе требование остается, как правило, невыполненным.
- Удовлетворение третьего требования достигается путем сведения к минимуму вычислительных операций, использования операций над целочисленными данными, а также реализацией алгоритмов на аппаратном или микропрограммном уровне.
- Многие алгоритмы вычерчивания отрезков и кривых используют пошаговый принцип, суть которого состоит в том, что координаты высвечиваемого пикселя определяются каждый раз на очередном шаге вычислений, а не вычисляются заранее для всех пикселей. Результат вычислений на текущем шаге зависит от результатов, полученных на предыдущем шаге.
Использует достаточно общий принцип, известный в математике: изучение какого-либо явления на основе дифференциального уравнения или системы таких уравнений, описывающей это явление.
Поскольку прямая задана каноническим уравнением Ax + By + C = 0, то производная dy / dx = const.
dy Yк - Yн
-- = -------
dx Xк - Xн
где Xн,Yн и Xк,Yк - координаты начальной и конечной точек отрезка.
Ордината очередного пикселя Yi+1 может быть вычислена по
известной ординате предыдущего пикселя Yi следующим образом:
Y_i+1 = Y_i + delta_y = Y_i + dy/dx * delta_x
delta_x = 1, a delta_y высчитывается и округляется. Однако delta_x следует выбирать не всегда – вначале нужно ответить на вопрос, как наклонён отрезок. Если угол наклона <45, то |dX| = 1, если > то |dY| = 1
Остается определить величину приращения X. В рассматриваемых здесь алгоритмах большее из приращений ( X или Y) выбирается в качестве единицы растра, а приращение вдоль другой координатной оси подлежит определению. Если же поступить по-другому (меньшее из приращений взять равным единице), то отрезок на экране может получиться "дырявым", то есть состоящим из отдельных точек, не расположенных вплотную друг к другу.
1. Ввод исходных данных Xн,Yн,Xк,Yк
2. Проверка вырожденности отрезка.
Если отрезок вырожден, то высвечивание
точки и переход к п.7
3. Вычисление
L = |Xк - Xн|, если |Xк - Xн| > |Yк - Yн|
|Yк - Yн|, если |Yк - Yн| > |Xк - Xн|
4. Вычисление
dX = (Xк - Xн) / L
dY = (Yк - Yн) / L
5. Задание координатам текущей точки
начальных значений:
X = Xн
Y = Yн
6. Цикл от i = 1 до i = L + 1 с шагом 1:
a. Высвечивание точки с текущими координатами:
Plot(E(X), E(Y)),
где E - операция округления до
ближайшего целого);
b. Вычисление координат следующей точки:
X = X + dX
Y = Y + dY.
7. Конец.
- Работает с целочисленной арифметикой (координаты текущей точки).
- Работает медленнее за счет операции округления.
Работа алгоритма Брезенхема основывается на использовании понятия ошибка. Ошибкой здесь называется расстояние между действительным положением отрезка и ближайшим пикселем сетки растра, который аппроксимирует отрезок на очередном шаге.
На каждом шаге вычисляется величина ошибки и в зависимости от полученного значения выбирается пиксель, ближе расположенный к идеальному отрезку. Поскольку при реализации алгоритма на ЭВМ удобнее анализировать не само значение ошибки, а ее знак, то истинное значение ошибки смещается на -0,5.
Пусть f - значение ошибки на очередном i-м шаге, Yu - ордината идеального отрезка, а Yi - ордината пикселя, выбранного для аппроксимации отрезка на том же i-м шаге, m - тангенс угла наклона отрезка.
Поскольку на первом шаге высвечивается пиксел с начальными координатами, то для него f=0, поэтому задаваемое предварительно значение f = m - 0,5 является фактически ошибкой для следующего шага. Приведем
основные расчетные соотношения, используемые в алгоритме.
Как и в предыдущем алгоритме, большее по модулю из приращений принимается равным шагу растра, то есть единице, причем знак приращения совпадает со знаком разности конечной и начальной координат отрезка:
X = sign(Xк - Xн), если |X| > |Y|
Y = sign(Yк - Yн), если |Y| > |X|
Sign возвращает -1, 0, 1 (зависит от знака отрц., нулевое, полож.)
Значение другой координат для следующего шага определяется как Y = Y + m, поскольку приращение ординаты совпадает
с величиной одного катета прямоугольного треугольника, а другой катет равен шагу сетки растра, то есть единице.
Ошибка на очередном шаге вычисляется как
f_i+1 = Yu_i+1 - Y_i+1 = Yu_i + m - Y_i+1 = f_i + m (если Y_i+1 = Y_i)
(Поскольку в алгоритме и программе не надо сохранять значения ошибок для всех шагов, то последнее выражение можно записать как f = f + m).
В зависимости от полученного значения ошибки выбирается пиксель с той же ординатой (при f < 0) или пиксель с ординатой, на единицу большей, чем у предыдущего пикселя (при f > 0).
Поскольку предварительное значение ошибки вычисляется заранее, то есть f+m вычислено на предыдущем шаге, то во втором случае останется только вычесть единицу из значения ошибки: f = f - 1.
Важно: 0≤ f_i≤ 1, если f < 0.5, то ордината пикселя не меняется, y_i+1 = y_i . Если f > 0.5, то выбирается верхний пиксель y_i = y_i+1.
1. Ввод исходных данных Xн,Yн,Xк,Yк.
2. Проверка вырожденности отрезка. Если отрезок
вырожденный, то высвечивается точка и
осуществляется переход к п.11.
3. Вычисление приращений:
dX = Xк - Xн
dY = Yк - Yн
4. Вычисление шага изменения каждой координаты пиксела:
SX = sign(dX)
SY = sign(dY)
5. Вычисление модулей приращения координат:
dX = |dX|
dY = |dY|
6. Вычисление модуля тангенса угла наклона отрезка:
m = dY / dX
7. Анализ вычисленного значения m и обмен местами dX и dY при m > 1:
если m > 1, то выполнить
W = dX
dX = dY
dY = W
m = 1 / m
fl = 1
если m < 1, то fl=0
(fl - флаг, определяющий факт обмена местами координат).
8. Инициализация начального значения ошибки:
f = m - 0,5
9. Инициализация начальных значений координат текущего пикселя:
X = Xн
Y = Yн
10. Цикл от i = 1 до i = dX + 1 с шагом 1:
a. Высвечивание точки с координатами (X,Y).
b. Вычисление координат и ошибки для следующего пикселя:
Если f > 0, то
если fl = 1, то X = X + SX
иначе Y = Y + SY;
корректировка ошибки f = f - 1
Если f < 0, то
если fl = 1, то Y = Y + SY
иначе X = X + SX
Вычисление ошибки f = f + m
11. Конец
- Не все переменные являются переменными целого типа (f, m -действительные).
Приведенный алгоритм легко преобразуется к целочисленному варианту. Для этого выражение запишем в виде:
f = m - 0,5
на
f = dY/dX - 1/2
и, умножив обе части этого равенства на 2dX, получим:
2dX * f = 2dY - dX.
Обозначив fl = 2dX * f, окончательно получим:
fl = 2dY - dX
(В соответствии с этим выражением должно вычисляться теперь начальное значение ошибки в п.8 алгоритма). Тогда подсчет нового значения ошибки в п.10 "действительного" алгоритма будет производиться по формулам:
fl = fl + 2dY
fl = fl - 2dX
Конечный результат (*) - изменения:
1. Ввод исходных данных Xн,Yн,Xк,Yк.
2. Проверка вырожденности отрезка. Если отрезок
вырожденный, то высвечивается точка и
осуществляется переход к п.11.
3. Вычисление приращений:
dX = Xк - Xн
dY = Yк - Yн
4. Вычисление шага изменения каждой координаты пиксела:
SX = sign(dX)
SY = sign(dY)
5. Вычисление модулей приращения координат:
dX = |dX|
dY = |dY|
6. Вычисление модуля тангенса угла наклона отрезка:
m = dY / dX
7. Анализ вычисленного значения m и обмен местами dX и dY при m > 1:
если m > 1, то выполнить
W = dX
dX = dY
dY = W
m = 1 / m
fl = 1
если m < 1, то fl=0
(fl - флаг, определяющий факт обмена местами координат).
8. Инициализация начального значения ошибки:
f = 2dy - dx (*)
9. Инициализация начальных значений координат текущего пикселя:
X = Xн
Y = Yн
10. Цикл от i = 1 до i = dX + 1 с шагом 1:
a. Высвечивание точки с координатами (X,Y).
b. Вычисление координат и ошибки для следующего пикселя:
Если f > 0, то
если fl = 1, то X = X + SX
иначе Y = Y + SY;
корректировка ошибки f = f - 2dx (*)
Если f < 0, то
если fl = 1, то Y = Y + SY
иначе X = X + SX
Вычисление ошибки f = f + 2dy (*)
11. Конец
Принципиально устранить ступенчатость (лестничный эффект) невозможно. Однако применением специальных методов можно добиться того, что визуально ступеньки будут слабо заметны или практически незаметны. Излагаемый здесь способ устранения ступенчатости рассматривает пиксель не как математическую точку, а как некоторую конечную область.
При наличии нескольких оттенков цвета внешний вид отрезка улучшается путем размывания его краев. Для этого интенсивность пикселя устанавливается пропорционально площади части пиксела, находящейся под отрезком. Поэтому необходимо получить выражения для вычисления этой площади.
Отрезок, тангенс угла наклона m которого лежит в диапазоне 0 < m < 1 (как было указано ранее, все отрезки приводятся к такому виду), может при данном значении абсциссы пересечь один или два пиксела.
Важно: Используется при отображении рёбер многоугольника, который закрашивается. Идея состоит в сглаживании резких переходов от ступени к ступени. Сглаживание основывается на том, что каждый пиксель высвечивается со своим уровнем интенсивности. Уровень выбирается пропорционально площади части пикселя. 1 пиксель – квадрат с единичной стороной, а не математическая точка.
В первом случае искомая площадь находится как сумма площадей прямоугольника S1 и треугольника S2:
S = S1 + S2 = Y_i * 1 + 1 * m/2 = Y_i + m/2
где Y_i- расстояние между нижней левой вершиной пикселя и точкой пересечения отрезка с левой границей пикселя.
Если отрезок пересекает два пикселя, то площадь части нижнего пикселя (S4) может быть найдена как разность площади всего пикселя и площади треугольника S3:
(1 - Y_i)(1 - Y_i)
S4 = 1 - S3 = 1 - ----------------
2m
где 1 - Y_i - длина одного катета, (1 - Y_i)/m - длина другого катета.
Площадь S5 части верхнего пикселя - треугольника равна:
( 1 - Y_I) ( 1 - Y_I)
S5 = (1 - -------) * (1 - -------) * m/2
( m ) ( m )
Практика показывает, что учет площади S5 позволяет более реалистично представить отрезок, поэтому найдем сумму площадей S4 и S5:
S = S4 + S5 = Yi + m/2
Таким образом, в обоих случаях площадь вычисляется по одной и той же формуле.
- В качестве ошибки в данном алгоритме принимается часть площади пиксела, находящаяся под отрезком, то есть
Yi + m/2. Вычислим значение ошибки при переходе к соседнему пикселу. Если ордината соседнего пикселя не увеличивается, то площадь, находящаяся под отрезком, увеличивается на величину площади прямоугольника со сторонами 1 иm, то естьf = f + m. - Если же ордината соседнего пикселя увеличивается на единицу, то вычисленная доля площади пикселя будет содержать и площадь пикселя, через который отрезок не проходит, следовательно, необходимо вычесть величину площади пикселя, то есть единицу:
f = f + m - 1.
Поскольку доля площади не может быть отрицательной величиной, то по сравнению с ранее рассмотренными алгоритмами Брезенхема необходимо скорректировать величину ошибки, прибавив к ней величину W = 1 - m. При этом начальное значение ошибки будет равно f= m - 0,5 + 1 - m = 0,5, а значение ошибки будет лежать в диапазоне 0 < f < 1
Первый пиксель отрезка будет, таким образом, всегда высвечиваться интенсивностью, равной половине максимальной. Для более реалистичного изображения это значение можно изменить.
Можно сразу получить не дробное значение максимальной интенсивности, а ее непосредственное значение, если умножить на максимальное количество уровней интенсивности следующие величины: тангенс угла наклона m, коэффициент W, ошибку f.
1. Ввод исходных данных Xн,Yн,Xк,Yк.
2. Проверка вырожденности отрезка. Если отрезок
вырожденный, то высвечивается точка и
осуществляется переход к п.13.
3. Вычисление приращений:
dX = Xк - Xн
dY = Yк - Yн
4. Вычисление шага изменения каждой координаты пиксела:
SX = sign(dX)
SY = sign(dY)
5. Вычисление модулей приращения координат:
dX = |dX|
dY = |dY|
6. Вычисление модуля тангенса угла наклона отрезка:
m = dY / dX
7. Анализ вычисленного значения m и обмен местами dX и dY при m > 1:
если m > 1, то выполнить
p = dX
dX = dY
dY = p
m = 1 / m
fl = 1
если m < 1, то fl=0
(fl - флаг, определяющий факт обмена местами координат).
8. Инициализация начального значения ошибки:
f = I / 2 (I - количество уровней интенсивности)
9. Инициализация начальных значений координат текущего пикселя:
X = Xн
Y = Yн
10. Вычисление скорректированного значения тангенса угла наклона m = mI и коэффициента W = I - m.
11. Высвечивание пиксела с координатами (X,Y) и интенсивностью E(f).
12. Цикл от i = 1 до i = dX + 1 с шагом 1:
a. Вычисление координат и ошибки для следующего пикселя:
Если f < W, то
если fl = 0, то X = X + SX
ecли fl = 1, то Y = Y + SY;
корректировка ошибки f = f + m
Если f > W, то
X = X + SX
Y = Y + SY
f = f - W
b. Высвечивание точки с координатами (X,Y) и интенсивностью E(f).
13. Конец
Как понял берем с интернета, но суть надо будет объяснить.