Лекция №9. Растровые алгоритмы (Алгоритм Брезенхейма, алгоритм Сазерленда Кохена) План
Download 157.5 Kb.
|
№9 Растровый алгоритм 5 стр
- Bu sahifa navigatsiya:
- Алгоритм Сазерленда - Коэна деление отрезка Литература Растровый алгоритм Брезенхейма
- 2.Алгоритм Сазерленда - Коэна деление отрезка
- 3.Литература
|
Лекция №9. Растровые алгоритмы (Алгоритм Брезенхейма, алгоритм Сазерленда – Кохена) План Растровый алгоритм Брезенхейма; Алгоритм Сазерленда - Коэна деление отрезка Литература Растровый алгоритм Брезенхейма Одним из важных понятий растровой графики является понятие связности – возможность соединения двух соседних пикселов. 4 - Связность. Пикселы P1=(x1,y1) и P2=(x2,y2) считаются соседними, если выполнено |x1-x2|+|y1-y2|≤1 (рис. 1) Рис.1. 4 - Связность. Рис.2. 8 - Связность. 8 - Связность. Пикселы P1=(x1,y1) и P2=(x2,y2) считаются соседними, если выполнено |x1-x2|≤1, |y1-y2|≤1 (Рис.2.) Отметим что понятие 4-связности силнее, чем 8-связность, т.е. любые два 4-связных пиксела являются 8-связными, обратное не всегда верно. #include #include #include void brezline(int x1,int y1,int x2,int y2,int c) { int dx,dy,d,d1,d2,x,y; dx=x2-x1; dy=y2-y1; d=2*dy-dx; d1=2*dy; d2=2*(dy-dx); x=x1; y=y1; putpixel(x,y,c); while (x if (d<0) d=d+d1; else { y=y++; d=d+d2; } putpixel(x,y,c); }} void main() {int gd=0,gm; initgraph(&gd,&gm,"c:\\borlandc\\bgi"); brezline(100,100,200,200,10); getch(); closegraph(); } 2.Алгоритм Сазерленда - Коэна деление отрезка В компьютерной графике часто приходится решать задачу выделения некоторой области изображаемой сцены, причем задача эта может решаться как в применении к плоской области (если сцена уже спроецирована на картинную плоскость), так и к трехмерной. Алгоритмы отсечения применяются для удаления невидимых поверхностей и линий, для построения теней, при формировании текстур. Отсекаемая область может быть как правильной формы (прямоугольник или параллелепипед со сторонами, параллельными осям координат или координатным плоскостям), так и неправильной (произвольный многоугольник или многогранник). Для того чтобы эти алгоритмы можно было использовать в задачах изображения динамичных сцен, они должны быть эффективными в отношении времени вычислений. Мы рассмотрим несколько наиболее часто применяемых алгоритмов. Рассмотрим плоскую сцену, состоящую из отрезков различной длины и направлений, в которой надо выделить часть, находящуюся внутри прямоугольника. Прямоугольник задан списком ребер: Пусть концы отрезка заданы точками и . Первый шаг алгоритма нацелен на то, чтобы выявить полностью видимые и полностью невидимые отрезки. Отрезок целиком принадлежит выделяемой (клиппируемой) области, если оба его конца удовлетворяют условиям (5.1). Рис. 3. Коды Сазерленда-Коэна для областей Отрезок полностью невидим, если оба его конца лежат справа от ребра ; слева от ребра ; снизу от ребра ; сверху от ребра . Во всех остальных случаях отрезок может (но не обязан) пересекать прямоугольное окно. Для выполнения анализа полной видимости или невидимости отрезка А.Сазерленд и Д.Коэн предложили следующий алгоритм. Прямые, которым принадлежат ребра прямоугольника, разбивают плоскость на девять областей, каждой из которых присваивается четырехразрядный код. Каждый бит этого кода "отвечает" за одну из прямых: 1-й (старший) бит - за прямую , 2-й - за прямую , 3-й - за , 4-й - за . Если в коде области какой-либо бит установлен в 1, то это означает, что она отделена от окна соответствующей прямой. Схема идентификации областей приведена на рис. 3.. Концевым точкам отрезков сцены теперь можно присвоить коды в зависимости от расположения точек. Ясно, что если коды обоих концов отрезка равны нулю, то отрезок полностью лежит внутри окна. Для дальнейшего анализа воспользуемся операцией логического умножения кодов (поразрядное логическое "И"). Тогда таблица истинности для кодов, согласно схеме на рис. 3, будет выглядеть следующим образом: Значения истинности для логического умножения кодов областей (Таблица 1.)
Из сопоставления таблицы с рисунком видно, что если произведение кодов концов отрезка принимает значение T В самом общем случае существуют две точки пересечения отрезка с ребрами, и эти две точки принимаются за новые концевые точки изображаемого отрезка. Но сначала можно выделить некоторые более простые частные случаи, поиск пересечений для которых является более эффективным. Прежде всего это горизонтальные и вертикальные отрезки, для которых поиск точки пересечения тривиален. Далее, если код одного из концов отрезка равен нулю, то существует только одно пересечение этого отрезка с ребром (или с двумя ребрами, если отрезок проходит через угловую точку окна). На рис. 4 приведена общая блок-схема алгоритма отсечения для одного произвольно направленного отрезка. Рис. 4. Блок-схема алгоритма Сазерленда-Коэна В блок-схеме используются следующие соглашения и обозначения: входными данными являются точки , массив координат окна ; на выходе получаем новые концевые точки , а также значение переменной IsVisible (0 - отрезок видимый); Используются следующие вспомогательные функции: GetCode(r) - определение кода точки; Intersec0(r1,l) - поиск пересечения отрезка со сторонами окна при условии, что обе точки лежат вне окна; если пересечения нет, устанавливает переменную IsVisible в 0; Intersec(r1,l) - поиск пересечения отрезка со сторонами окна при условии, что точка r1 лежит в окне; C1, C2 - коды точек r1, r2. В приведенном алгоритме теперь остается только детализовать функции Intersec0 и Intersec, эффективность работы которых является ключевым моментом. Рассмотрим один из методов поиска пересечений, который использует параметрическое уравнение прямой, проходящей через точки : или в координатном виде Попробуем определить точку пересечения отрезка с верхней границей окна. Поскольку эта граница описывается соотношениями то условие пересечения с ней клиппируемого отрезка выглядит следующим образом: 3.Литература 1. Шикин Е.В., Боресков А.В. Компьютерная графика. Динамика, реалистические изображения. М. 1996. 288 с. 2. Порев В.Н. Компьютерная графика. СПб. 2004. 432 с. 3. Donald Hearn, M. Pauline Baker. Computer graphics. C version. 2-d edition. 4. David Salomon. The Computer Graphics Manual. Volume 1. Download 157.5 Kb. Do'stlaringiz bilan baham: 
|