Растровая графика. Генерация линий

Сентябрь 5, 2022

Главная
Алгебра
Растровая графика. Генерация линий

Содержание

2. Растровые алгоритмы В большинстве случаев графические устройства, такие как монитор или принтер являются растровыми, то есть
3. Понятие связности Важным понятием для растровой сетки является понятие связности - возможность соединения двух пикселов растровой
4. 4-связность и 8-связность 4-связность – пикселы считаются соседними при выполнении условия |x1-x2|+|y1-y2|≤1 т.е. возможны перемещения по
5. Построение отрезков Рассмотрим следующую задачу. Требуется построить на пиксельной сетке (растровое) изображение отрезка, соединяющего точки (x1,y1)
6. Цифровой Дифференциальный Анализатор (ЦДА) Один из методов разложения отрезка в растр состоит в решении дифференциального уравнения,
7. Реализация ЦДА Len = max(abs(x2 - x1), abs(y2 - y1)); dx = (x2 - x1) /
8. Пример работы ЦДА x1 = 0 y1 = 0 x2 = -8 y2 = -4 Len
9. Алгоритм Брезенхема Этот алгоритм, разработанный Джеком Е. Брезенхэмом (Jack E. Bresenham) в 1962 году в компании
10. Шаг алгоритма Брезенхема Рассмотрим случай, когда dx>dy, тогда при построении 8-связной линии можно в качестве соседних
11. Реализация алгоритма Брезенхема void LineBrez(HDC hdc, int x1, int y1, int x2, int y2) { int
12. Что можно улучшить В процессе работы алгоритма наблюдаются вычисления с вещественными величинами. Заметим, что они касаются
13. Реализация целочисленного алгоритма void LineBrez2(HDC hdc, int x1, int y1, int x2, int y2) { int
14. Алгоритм для произвольной прямой Можно избавиться от предположения о том, что угол наклона прямой от 0
15. Резюме по алгоритму Брезенхема для прямой Алгоритм простой для реализации Все вычисления в целочисленной арифметике Допускает
16. ЗАДАЧИ Задано окно координатами своих вершин. В нем заданы две точки. Нарисовать отрезок их соединяющий методом
17. ТЕСТЫ Связность может быть типа 2 3 6 8 Цифровой дифференциальный анализатор - Это метод разложения
19. Скачать презентацию

Слайд 2

Растровые алгоритмы
В большинстве случаев графические устройства, такие как монитор или принтер

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

Слайд 3

Понятие связности
Важным понятием для растровой сетки является понятие связности - возможность

соединения двух пикселов растровой линией, т.е. последовательным набором пикселов.
При этом возникает вопрос, когда пикселы (x1, y1) и (x2, y2) можно считать соседними.
В этом вопросе используют два подхода.

Слайд 4

4-связность и 8-связность
4-связность – пикселы считаются соседними при выполнении условия
|x1-x2|+|y1-y2|≤1

т.е. возможны перемещения по вертикали и горизонтали.

8-связность – пикселы считаются соседними при выполнении условия
|x1-x2|≤1 & |y1-y2|≤1
т.е. возможны перемещения по всем 8 направлениям.

Слайд 5

Построение отрезков
Рассмотрим следующую задачу. Требуется построить на пиксельной сетке (растровое) изображение

отрезка, соединяющего точки (x1,y1) и (x2,y2).
Стандартными требованиями к алгоритмам вычерчивания линий являются следующие:
Отрезки должны выглядеть прямыми и начинаться и заканчиваться в заданных точках;
Яркость должна быть постоянна и независима от наклона;
Скорость рисования должна быть максимальна.

Слайд 6

Цифровой Дифференциальный Анализатор (ЦДА)
Один из методов разложения отрезка в растр состоит

в решении дифференциального уравнения, описывающего этот процесс.
Для прямой линии имеем
dy / dx = const или Δy / Δx = (y2 - y1) / (x2 - x1)
Решение предсталяется в виде
yi+1 = yi + Δy
yi+1 = yi + Δx (y2 - y1) / (x2 - x1)
В простом ЦДА либо Δx, либо Δy (большее из приращений) выбирается в качестве единицы растра.

Слайд 7

Реализация ЦДА
Len = max(abs(x2 - x1), abs(y2 - y1));
dx = (x2

- x1) / Len; dy = (y2 - y1) / Len;
x = x1 + 0.5 * Sign(dx); y = y1 + 0.5 * Sign(dy);
for (int i=0; i{ SetPixel(hdc, x, y, 0);
x+=dx; y+=dy;
}
Здесь Sign - функция, возвращающая -1, 0, 1 для отрицательного, нулевого и положительного аргумента соответственно.

Слайд 8

Пример работы ЦДА
x1 = 0
y1 = 0
x2 = -8
y2 = -4
Len

= 8
dx = -1
dy = -0,5
x = -0,5
y = -0,5

Рассмотрим работу ЦДА для отрезка (0,0) (-8,-4)

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

Слайд 9

Алгоритм Брезенхема
Этот алгоритм, разработанный Джеком Е. Брезенхэмом (Jack E. Bresenham) в

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

Слайд 10

Шаг алгоритма Брезенхема
Рассмотрим случай, когда dx>dy, тогда при построении 8-связной линии

можно в качестве соседних точек брать только две справа.

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

Слайд 11

Реализация алгоритма Брезенхема
void LineBrez(HDC hdc, int x1, int y1, int x2,

int y2)
{ int dx=x2-x1, dy=y2-y1, x=x1, y=y1;
double D=double(dy)/dx, e=0;
SetPixel(hdc, x, y, 0);
for (x++; x { e+=D;
if (e>0.5) {e--; y++;}
SetPixel(hdc, x, y, 0);
}
}

Слайд 12

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

что они касаются только переменных D и e. При этом, эти переменные не связаны непосредственно с координатами x и y.
В знаменателях вещественных переменных имеем dx и 2. Умножим на них все, что связано с D и e.
Получим целочисленный вариант реализации.

Слайд 13

Реализация целочисленного алгоритма
void LineBrez2(HDC hdc, int x1, int y1, int x2,

int y2)
{ int dx=x2-x1, dy=y2-y1, x=x1, y=y1;
int D=dy*2, e=-dx;
SetPixel(hdc, x, y, 0);
for (x++; x { e+=D;
if (e>0) {e-=2*dx; y++;}
SetPixel(hdc, x, y, 0);
}
}

Слайд 14

Алгоритм для произвольной прямой
Можно избавиться от предположения о том, что угол

наклона прямой от 0 до π/4.
При больших углах необходимо на каждом шаге цикла менять координату y, подбирая при этом x исходя из величины ошибки.
Необходимо рассматривать направление движения по x и по y в зависимости от знаков dx и dy.
В итоге имеем целочисленный алгоритм.

Слайд 15

Резюме по алгоритму Брезенхема для прямой
Алгоритм простой для реализации
Все вычисления в

целочисленной арифметике
Допускает аппаратную реализацию
Дает идеальное растровое приближение реальной прямой
Легко модифицируется для случаев 4-связной и 8-связной линии

Слайд 16

ЗАДАЧИ
Задано окно координатами своих вершин. В нем заданы две точки. Нарисовать

отрезок их соединяющий методом цифрового дифференциального анализатора.
В условиях предыдущей задачи нарисовать отрезок методом Брезенхема.
Визуализировать процесс построения отрезка методом ЦДА. Нарисовать сетку пикселей и показывать каждый шаг алгоритма с возможным и реальным выбором следующего пикселя. Использовать связность типа 4.
Визуализировать процесс построения отрезка методом ЦДА. Нарисовать сетку пикселей и показывать каждый шаг алгоритма с возможным и реальным выбором следующего пикселя. Использовать связность типа 8.
Визуализировать процесс построения отрезка методом Брезенхема. Нарисовать сетку пикселей и показывать каждый шаг алгоритма с возможным и реальным выбором следующего пикселя. Использовать связность типа 4 (8).

Слайд 17

ТЕСТЫ
Связность может быть типа
2
3
6
8
Цифровой дифференциальный анализатор -
Это метод разложения отрезка в

растр путем решения дифференциального уравнения
Это решение задачи Коши численными методами
Анализ решения дифференциального уравнения
Метод построения произвольной линии
Алгоритм Брезенхема построения прямой лучше метода ЦДА ,так как
позволяет получить приближение идеальной прямой точками растровой сетки
все точки лежат с одной стороны от реального отрезка
можно использовать связность типа 8
не требуется решать дифференциальное уравнение

Растровая графика. Генерация линий

Содержание

Растровые алгоритмыВ большинстве случаев графические устройства, такие как монитор или принтер

Понятие связностиВажным понятием для растровой сетки является понятие связности - возможность

4-связность и 8-связность4-связность – пикселы считаются соседними при выполнении условия |x1-x2|+|y1-y2|≤1

Построение отрезковРассмотрим следующую задачу. Требуется построить на пиксельной сетке (растровое) изображение

Цифровой Дифференциальный Анализатор (ЦДА)Один из методов разложения отрезка в растр состоит

Реализация ЦДАLen = max(abs(x2 - x1), abs(y2 - y1));dx = (x2

Пример работы ЦДАx1 = 0y1 = 0x2 = -8y2 = -4Len

Алгоритм БрезенхемаЭтот алгоритм, разработанный Джеком Е. Брезенхэмом (Jack E. Bresenham) в

Шаг алгоритма БрезенхемаРассмотрим случай, когда dx>dy, тогда при построении 8-связной линии

Реализация алгоритма Брезенхемаvoid LineBrez(HDC hdc, int x1, int y1, int x2,

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

Реализация целочисленного алгоритмаvoid LineBrez2(HDC hdc, int x1, int y1, int x2,

Алгоритм для произвольной прямойМожно избавиться от предположения о том, что угол

Резюме по алгоритму Брезенхема для прямойАлгоритм простой для реализацииВсе вычисления в

ЗАДАЧИЗадано окно координатами своих вершин. В нем заданы две точки. Нарисовать

ТЕСТЫСвязность может быть типа2368Цифровой дифференциальный анализатор -Это метод разложения отрезка в

Похожие презентации