Popov_vorobev

свойство Interval, выставляя положительное значение для запуска, и 0 для остановки. Все действия, которые необходимо выполнять по истечении определенного промежутка времени, прописываются

вобработчике события OnTimer.

Впрактической части был довольно подробно описан принцип работы наиболее простой версии приложения, необходимой для получения студентом минимального положительного балла. Для получения высоких баллов предлагается реализовать приложение,

вкотором пользователь сможет задавать так же координату z вершин многоугольников. Чтобы объекты находились в пространстве

впроизвольном положении, а не строго параллельно фронтальной плоскости.

20

Лабораторная работа № 3

Отсечение отрезков. Реализация алгоритма Сазерленда-Коэна

Теоретическая часть

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

В данном случае на плоской сцене расположены отрезки различной длины и направлений. В результате действия алгоритма, на сцене должны остаться только те части отрезков, которые находятся внутри прямоугольника. Прямоугольник задан списком ре-

бер (<top>, <bottom>, <left>, <right>), а точнее координатами двух его вершин: верхней левой и правой нижней. Отрезки также задаются координатами концевых точек (рис. 8).

Таким образом, точки отрезка, находящиеся внутри прямоугольника удовлетворяют условию:

xl ≤ x ≤ xr и yb ≤ y ≤ y

(1),

21

где x и y — координаты концевых точек отрезка, (xl, yt) — координаты левой верхней вершины прямоугольника, (xr, yb) — координаты правой нижней вершины прямоугольника.

Рис. 8. Положение отрезков относительно прямоугольной области

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

слева от ребра l(x1 <xl, x2 <xl); справа от ребра r(x1 > xr, x2 > xr);

снизу от ребра b(y1 < yb, y2 < yb); сверху от ребра t(y1 > yt, y2 > yt).

Во всех остальных случаях отрезок может пересекать или не пересекать прямоугольное окно.

Ещё в 1968 году Айвен Сазерленд и Дэн Коэн разработали алгоритм, позволяющий легко определять случаи полной видимости и невидимости отрезков. Всю рабочую область, на которой происходит отсечение, они предложили разбить на девять частей продленными сторонами прямоугольника, и назначить каждой этой части некоторый четырехразрядный код (рис. 9). Эти коды должны присваиваться концевым точкам отрезка в начале работы алгоритма. Каждый бит этих кодов связан с определенной прямой. Первый (старший) бит связан с прямой T, второй — с прямой B, третий — с прямой R, четвертый — с прямой L. Единица в разряде

22

ставится в том случае, если точка отделена от видимой области соответствующей прямой.

		L							R			1010
	1001					1000
													T
						0000						0010
	0001
														B
							0100						0110
		0101

Рис. 9. Четырехзначные коды

Рассмотрим небольшой пример.

Ниже представлена координатная плоскость, на которой имеется некоторая прямоугольная область, заданная координатами левой верхней (xtl, ytl) и правой нижней (xbr, ybr) вершин и точка, у которой также известны координаты(x, y) (рис. 10).

7

6

5

4

3

2

1

0, 0

1

2

3

4

5

6

7

8

9

Рис. 10. Положение точки относительно области отсечения

23

Для того чтобы определить код точки, нам необходимо поочередно произвести 4 сравнения:

y < ytl → старший бит равен нулю; y > ybr→ второй бит равен нулю; x < xbr→ младший бит равен нулю; x < xtl → третий бит равен единице;

Код точки равен 0001, что соответствует рисунку 9. Точка отделена от прямоугольной области только левой стороной.

В случае работы с отрезком, эти действия производятся для двух точек. И это является первым шагом алгоритма.

После того как кодыполучены, возникает одна изтрех ситуаций.

1.Оба кода содержат только нули, то есть отрезок полностью лежит внутри окна, следовательно, он должен быть полностью отрисован.

2.Разряд, содержащий единицу, у обоих кодов совпадает. Это означает, что отрезок отделен от видимой области одной стороной и будет полностью невидим.

3.Если ни один из первых двух пунктов не выполняется, то отрезок может (хотя и не обязательно) пересекать видимую область. Следовательно, необходимость в отсечении имеется.

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

Если определить тривиальную видимость или невидимость отрезка не удалось, необходимо найти точки пересечения отрезка с гранями прямоугольника, для этого используется уравнением прямой, проходящей через две заданные несовпадающие точки,

(x – x1)/ (x2 – x1)=(y – y1)/(y2 – y1),

где (x1, y1) и (x2, y2) — координаты концевых точек отрезка.

Как писалось ранее, координаты верхней левой и нижней правой вершин прямоугольника обозначаем(xtl, ytl) (xbr, ybr).

Дальше поочередно проверяем описанные выше условия, и если из какого-то из них следует, что точка отрезка отделена от видимой области соответствующей прямой, то точка переносится на эту прямую.

24

Если конечная точка отрезка лежит левее окна, то её необходимо переместить к его левой границе:

x1 = xtl;

y1 = y1 + (y2 — y1) (xtl — x1)/(x2 — x1).

Если выше окна:

y1 = ytl;

x1 = x1 + (x2 — x1) (ytl — y1)/(y2 — y1).

Если правее окна:

x1 = xbr;

y1 = y1+(y2 — y1) (xbr — x1)/(x2 — x1).

Если ниже окна:

y1 = ybr;

x1 = x1 + (x2 — x1) (ybr — y1)/(y2 — y1).

После того как все четыре условия проверены, координатам отрезка присваиваются новые значения. И алгоритм переходит к первому шагу. Так происходит до тех пор, пока на втором шаге не выяснится, что отрезок уже полностью лежит внутри прямоугольника или уже точно не попадает в видимую область. На рис. 11 и 12 изображены примеры того, как отрезок последовательно отсекается. В первом случае, после двух переносов каждой из вершин, отрезок оказывается полностью в видимой области. Во втором случае, после двух переносов одной вершины и одного переноса другой, отрезок оказывается полностью отделен нижней стороной прямоугольника.

Рис. 11. Отрезок пересекает область отсечения

25

Рис. 12. Отрезок вне области отсечения

Практическая часть

Итак, выше был представлен некоторый теоретический материал по теме. Суть же лабораторной работы состоит в программной реализации алгоритма Сазерленда-Коэна. Для этой реализации студент может использовать любой объектно-ориентированный язык программирования высокого уровня и, соответственно, любую среду разработки. Но, в данном методическом пособии некоторые практические моменты будут объяснены на примере языка

Delphi.

Конечно, целью методического пособия не является демонстрация готового программного кода, но некоторые моменты стоит пояснить.

Как показала практика, у многих студентов возникают проблемы с присваиванием кодов точкам и проверкой этих кодов на наличие совпадающих разрядов. Решить эту задачу можно разными способами, вплоть до создания для каждой точки отдельного массива и дальнейшей проверки его элементов. Этот способ далеко не самый рациональный. Для способа, который мы будем здесь рассматривать, необходимо вспомнить задачу перевода чисел из двоичной системы счисления в десятичную. Решается эта задача путем сложения цифр в разрядах двоичного числа, умноженных на основание двоичной системы счисления в степени, соответствующей текущему разряду.

Простой пример:

01012 = 0 · 23 + 1 · 22 + 0 · 21 + 1 · 20 = 0 + 4 + 0 + 1 = 5.

26

Таким образом, код каждой точки может быть представлен целочисленной переменной типа Byte. Необходимо написать функцию, которой в качестве входных данных будут передаваться координаты точки, а возвращать она будет код этой точки.

Выглядеть это может примерно так: functionPointCode(x, y:integer):integer; varres:integer;

begin res:=0;

if (x<RectX1) then res:= res+1; if (y<RectY1) then res:= res+8; if (x>RectX2) then res:= res+2; if (y>RectY2) then res:= res+4; result:=res;

end;

Этот небольшой и, на первый взгляд, простой фрагмент кода требует ряда пояснений. RectX1, RectY1 иRectX2, RectY2 — цело-

численные переменные, в которых хранятся координаты вершин прямоугольника. Очень важно строго определить, какая пара переменных, для какой вершины прямоугольника предназначена. Когда пользователь рисует прямоугольник, он может делать это слева направо, справа налево, снизу вверх, сверху вниз, в общем, по-разному. И если в программе координаты вершинам присваиваются сразу при обработке событий MouseDown и MouseUp, компонента рисования, то в ходе работы алгоритма отсечения могут возникать ошибки. Поэтому первым действием, после того, как пользователь нарисовал прямоугольник, должна быть проверка координат, и в случае необходимости, их перестановка таким образом, чтобы одна пара переменных отвечала за верхнюю левую вершину, а вторая — за правую нижнюю.

Второй момент, который тоже важно отметить — это то, что в компоненте TImage (по крайней мере, в версиях вплоть до Delphi 2010), координаты точек просчитываются от верхнего левого угла (рис. 13). В теоретической части мы рассматривали координатные оси, которые начинались в левом нижнем углу.

27

0, 0

Рис. 13. Координаты точек компонента TImage

Итак, вернемся к представленной выше функции. Изначально переменной, которую будет возвращать функция, присваивается значение «ноль». Затем проверяются четыре условия. Если координата x точки, для которой мы определяем код, меньше координаты x левой стороны прямоугольника, значит, эта точка отделяется от видимой области левой стороной, и младший бит её кода должен быть равен единице, то есть прибавляем к нашему результату 2°. Если координата y точки меньше координаты y верхней стороны прямоугольника (учитываем направление координатных прямых, рисунок 13), то старший (четвертый) бит должен быть равен единице. Следовательно, к результату мы прибавляем 23. И т.д.

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

Пусть LineBegin, LineEnd — переменные, в которые мы будем записывать коды:

var

LineBegin, LineEnd: Byte;

…

Условие, при котором отрезок полностью находится внутри:

If ((LineBegin=0)and(LineEnd=0)) then begin

…

28

end;

Условие, при котором отрезок лежит полностью снаружи:

If ((LineBegin and LineEnd)<>0) then begin

…

end;

Здесь применяется логический оператор «and». Если у двух чисел единица совпадает хоть в одном разряде, то результат этой операции будет отличен от нуля.

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

Что касается требований, то приложение обязательно должно содержать поле графического ввода, на котором пользователь будет рисовать прямоугольную область и отсекаемый отрезок, кнопку очистки и кнопку запуска алгоритма. Такжестудент может добавить какието дополнительные элементы, если посчитает это необходимым. На рис. 14 и15 изображен пример окна готового приложения.

Рис. 14. Окно приложения

29