Лабораторная работа № 6. Реализация двумерного алгоритма отсечения отрезков Сазерленда-Коэна
Цель работы: Закрепить лекционный материал по изучению материала темы "Отсечение". Реализовать двумерный алгоритм Сазерленда - Коэна для отсечения отрезка окном прямоугольной формы.
Краткие теоретические сведения
Необходимость отсечь выводимое изображение по границам некоторой области (окна) встречается довольно часто, особенно в многооконных диалоговых графических системах. В простейших случаях в качестве отсекающей области выступает прямоугольник. Существует много алгоритмов отсечения для 2D- и 3D-случаев, ориентированных как на программную, так и аппаратную реализацию. Рассмотрим простой и эффективный алгоритм отсечения отрезков границами произвольного прямоугольника. Вся плоскость вывода разбивается прямыми, образующими прямоугольник на девять подплоскостей; каждой из них присваивается четырехбитовый код, в котором единица
в нулевом бите означает, что конец отрезка лежит левее окна,
в первом бите - выше окна,
во втором бите - правее окна,
в третьем бите - ниже окна.
Например, если один конец отсекаемого отрезка лежит в правом верхнем относительно окна углу экрана, он получает код этого угла равный 0110 по схеме:
Описание алгоритма Сазерленда - Коэна:
Дано: прямоугольное окно с координатами (xl,ya),(xr,yb) верхнего левого и нижнего правого углов прямоугольника; отрезок с координатами концов (x1,y1) и (x2,y2).
Найти: новые координаты отрезка (x1,y1) и нарисовать его целиком или частично в случае попадания в область окна и не рисовать в противном случае.
1. Присвоить коды (р1 и р2) концам отрезка.
2. Если отрезок полностью невидим(p1 and p2 <> 0), идти к 9, иначе идти к 3.
3. Если отрезок видим полностью (p1 = 0 and p2 = 0) - нарисовать его (провести линию от точки с координатами (х1,y1) до точки - (x2,y2) и идти к 9, иначе идти к 4.
4. Если р1=0 - поменять местами точки (x1,y1) и (x2,y2),чтобы обработка шла каждый раз с точки, находящейся вне окна: х=х1,х1=х2,х2=х,y=y1,y1=y2,y2=y,p1=p2 и идти к 5, иначе идти к 5.
5. Если точка (x1,y1) - слева от окна - найти ее новые координаты по формулам: y1=y1+(y2-y1)*(xl-х1)/(х2-х1), x1=xl и идти к 1, иначе идти к 6.
6. Если точка (x1,y1) - выше окна - найти ее новые координаты по формулам: х1=х1+(х2-х1)*(ya-y1)/(y2-y1), y1=ya и идти к 1, иначе идти к 7.
7. Если точка (x1,y1)- справа от окна - найти ее новые координаты по формулам: y1=y1+(y2-y1)*(xr-х1)/(х2-х1), х1=xr и идти к 1, иначе идти к 8.
8. Если точка (x1,y1) - ниже окна - найти ее новые координаты по формулам: х1=х1+(х2-х1)*(yb-y1)/(y2-y1),y1=yb и идти к 1, иначе идти к 1.
9. Закончить.
Присваивание кода точке с координатами (x,y) (пункт 1 данного алгоритма) можно выполнить, например, следующей программой:
function kod(x,y,xl,ya,xr,yb:integer):byte;
var
kp:byte;
begin
kp:=0;
if x<xl kp:=kp or $01;
if y<ya kp:=kp or $02;
if x>xr kp:=kp or $04;
if y>yb kp:=kp or $08;
kod:=kp
end;
Здесь (xl,ya),(xr,yb) - координаты левого верхнего и правого нижнего углов окна, kod - результирующий код.
Задание на лабораторную работу
Написать на языке PASCAL программу, реализующую алгоритм Сазерленда-Коэна, отсекающий отрезок по границам прямоугольного окна. Для показа результатов работы программы нарисовать на экране окно прямоугольной формы. Задав координаты окна и отрезка, продемонстрировать отсечение отрезка по границам окна. Рассмотреть все возможные случаи расположения отрезка относительно окна.
Дополнительно
Для демонстрации работы алгоритма использовать мышь.
Требования к защите лабораторной работы
Защита лабораторной работы состоит из демонстрации преподавателю результатов выполнения задания на лабораторную работу и ответов на задаваемые преподавателем вопросы по ходу демонстрации.
Требования к отчету
Отчет выполняется на отдельных листах формата А4. Содержит титульный лист с названием работы, оформленный согласно требованиям кафедры, распечатку программы результат выполнения заданий лабораторной работы с обязательными комментариями.
Вопросы для самоподготовки:
1. Что такое отсечение и для чего оно применяется?
2. Какие алгоритмы отсечения Вы знаете?
3. Что является границей отсечения для 2D- 3D- случаев?
4. Можно ли реализовать отсечение аппаратно, если можно, то в каких случаях это делают?
Литература
7. Роджерс, Д. Ф. Алгоритмические основы машинной графики [текст] / Д. Ф. Роджерс; пер. с англ. С. А. Вичеса и др.; Под ред. Ю. М. Баяковского, В. А. Галактионова. - М.: Мир, 1989. - 503c.
8. Шикин, Е. В. Компьютерная графика: Динамика, реалист. изображения [текст] / Е. В. Шикин, А. В. Боресков. - М.: ДИАЛОГ-МИФИ, 1996. - 287c.: ил.