681.327.22(07)
Р851
N 2469
ГОСУДАРСТВЕННЫЙ КОМИТЕТ РОССИЙСКОЙ ФЕДЕРАЦИИ ПО ВЫСШЕМУ ОБРАЗОВАНИЮ
ТАГАНРОГСКИЙ ГОСУДАРСТВЕННЫЙ РАДИОТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ
Руководство к лабораторной работе Задачи двумерного отсечения по курсу
Компьютерная графика
Для студентов специальности 22.01, 22.04
ФАВТ
Таганрог 1996
УДК 681.327.22.(07)
Составитель В.В.Селянкин
Руководство к лабораторной работе "Задачи двумерного отсечения" по курсу "Компьютерная графика”. Таганрог,: ТРТУ, 1996, 36 с.
Данное руководство продолжает серию методических разработок лабораторного практикума по курсу "Компьютерная графика" и предназначено для изучения двумерной задачи отсечения. В работе рассматривается набор методов и алгоритмов решения задачи отсечения и фрагментов программ по их реализации. При этом дается анализ эффективности этих методов и оценка их преимуществ и недостатков.
Кроме того, в руководстве даны варианты заданий к лабораторной работе, определен порядок ее выполнения. Руководство рассчитано на студентов дневного и заочного обучения специальностей 22.04,	22.01, а также на студентов родственных
специальностей, изучающих компьютерную графику.
-Ил. 30. Библиогр.: 10 назв.
Рецензент Н.И.Витиска, докт. техн, наук, профессор кафедры "Информатика" ТПГИ
ВВЕДЕНИЕ
В предыдущих • выпусках метрических указаний к. лабораторным работам были рассмотрены работы по изучению модуля Graph системы программирования Turbo-Pascal с элементами построения простейших изображений, а также алгоритмы растровой графики. В данной работе предлагается для изучения задача двумерного отсечения.
Задача отсечения решает вопрос выделения' части некоторого изображения. При построении сложных изображений эта задача выступает инструментом при удалении невидимых линий и поверхностей. Кроме этого, задача отсечения решает вопросы определения пересечения фигур, объемных тел, многогранников. В общем случае вопросы отсечения решают задачи как плоских-так и объемных изображений. Основное требование к алгоритмам обеспечение приемлемой -скорости обработки изображений, желательно в реальном масштабе времени. С этой целью возможны аппаратная/ и микропрограммная реализация алгоритмов. Решение задачи отсечения предполагает использование регулярных .отсекающих окон в виде прямоугольника, квадрата, куба, параллелепипеда и нерегулярных произвольной формы.
1. ОТСЕЧЕНИЕ ОТРЕЗКОВ РЕГУЛЯРНЫМ ОКНОМ
1.1. Определение полной видимости и полной невидимости отрезков
Рассмотрим задачу отсечения для регулярного окна в виде прямоугольника со сторонами (ребрами), обозначаемыми символами Л, П, В, Н для левой, правой, верхней и ппжйей сторон
*3
соответственно. ’ Целью отсечения является , определение тех Точек, отрезков пли iix частей, которые лежат внутри отсекающего окняд-Зти элементы, изображения являются видимыми в окне, и они остаются дЛя визуализации, а остальные Элементы отсекаются.
Обычно при решении задачи отсечения щриходится иметь дело с большим числом элементов изображения. В связи с этим важное' значение приобретает возможность отбрасывания большого числа элементов изображения с минимальными'затратами машинного времени за счет выявления у них некоторых характерных особенностей.
Рассмотрим возможные варианты расположения элементов изображения по отношению к отсекающему окну (рис. 0. Точки, лежащие внутр'и окна, являются видимыми и удовлетворяют условию
X л < X < Хй , ун '< у < ,ув
Знак равенства указывает на то, • что граничные точки также входят в видимую область. Если оба конца отрезка лежат внутри
отсекающего окна, то отрезок целиком, находится внутри его (например, отрезок Р Р ). Обратное утверждение в общем^случае неверно. Если оба конца отрезка лежат снаружи, то отрезок может быть водностью невидимым (отрезки Р5 Pg , Р7 Pg ) или видимым
частично (Р>, Р10).
Если один конец отрезка находится внутри, а второй - снаружи, то отрезок будет частично видимым (отрезок Р3 Р4).. Если оба конца отрезка лежат вне отсекающего окна, причем таким образом, что они расположены слева или справа, -иЛи выше, или ниже ребер отсекающего окна, то отрезок будет полностью невидимым.
В соответствии с изложенным можно сформулировать простые условия определения полной видимости-невидимости отрезка Р1Р2, заданного координатами (x-f, yi) и (х2, уг).
Условие полной видимости -
(хл < X! < хп) & (хл < х2 < Хп) & (уя < У1 < ув) & (у„ < У2 < Ув).
Z
Условие полной невидимости -
((xj < Хл) & <Х2 < хл)) V ((Х! > хп) & (х2 > хп)) V
'V (<У1 < ун) & (у2 < Ун)) V <(У1 > ув) & ( У2 > ув)). ,
Если условие полной видимости не выполняется, ‘ то отрезок является либо полностью невидимым, либо невидимым частично. Если при этом не выполняется еще и условие полной невидимости, то отрезок либо полностью невидим, либо частично. Это связано с тем, что условие полной невидимости выделяет только часть невидимых отрезков тех, что располагаются целиком по одну сторону грани, являющейся продолжением некоторого ребра отсекающего окна. Таким образом, два указанных условия позволяют относительно простой процедурой выявить все видимые отрезки и часть невидимых. Другая часть полностью невидимых .отрезков, не выявленных применением второго условия, определяется общим алгоритмом задачи, отсечения. Теперь рассмотрим содержание этого алгоритма.
1.2. Задача отсечения отрезка с произвольным'расположением
Данный алгоритм применяется к отрезкам, для которых не выполняются условия полной видимости-невидимости. На рис.2 покан пример расположения такого отрезка. Для выделения видимой части отрезка необходимо найти точки пересечения’ его со сторонами отсекающего окна. В общем случае неизвестно, с какими сторонами окна пересекается заданный отрезок, поэтому следует определить его пересения со всеми сторонами окна, а затем выделить интересующие нас точки. Для решения этой задачи следует определить пересения
5
прямой, продолжающей отрезок Р1Р2, с прямыми, продолжающими ребра отсекающего окна (гранями отсекающего окна).
Уравнение прямой для отрезкаР1Р2 имеет вид
У-У1 _ Х-Х, У2 -У1 . х2-х1 ’ где Xj, у, - координаты концов отрезка,	’
х, у - координаты текущей точки отрезка. Пересечение этой прямой с продолжениями сторон отсекающего окна имеет следующие
6
Х2 - X,	*
точка 1: (	^Уп~У^+Х}, УЛ, У2 * Л i
У2	”1 '
точка 2: (Хл, ----- (Хд-Х^+ур,,
-X»	*
х2
Х2 -- X,	. '	'
точка 3: (у Гу' (У^У^+Х^ У*} ’ У** УГ
точка 4: (Хп,	(Xn-X^+yj) , Х2 * Xj .	'
Х2 Xj	„	.
После нахождения четырех точек пересечения необходимо выделить среди них те, которые принадлежат отсекающему, окну. Для этого достаточно’проверить для 1 и 3 точекусловие Хл < X < X п, а для точек 2 и 4 - условие у н у < ув, т.к.'координаты Хл, Хп, у„, ув нет необходимости проверять. Этим условиям отвечают точки 2 и 3.
В случае расположения отрезка таким образом, что одна его концевая точка располагается внутри окна, а вторая - снаружи; необходимо проверить координаты точек пересечения 1, 2, 3, 4 на принадлежность их прямоугольнику, построенному на отрезке Р]Р2 как на его диагонали (рис.4), т.е. выполнить проверку условия
( хР1 < х < хР2) & (уР1<у< уР2).
Кроме случаев рассмотренных выше, следует учитывать возможность' особого (граничного) -варианта расположения отрезка, при котором Он’располагается по горизонтали,-вертикали или проходит через вершину отсекающего окна. Для анализа этих случаев требуются
Несложные дополнительные проверки. '	. .	. .
1.3.	Алгоритм Сазерленда-Коэна отсечения отрезка регулярным окном
Приведенный выше подход может быть положен в основу разработки алгоритмов, детализирующих его реализацию в различных вариантах. В качестве примера рассмотрим одну из таких модификаций, носящюю название алгоритма Сазерленда-Коэна.
Идея алгоритма заключается в том, чтожаждая грань отсекающего окна делит плоскость на две полуплоскости - внутреннюю, содержащую отсекающее окно, и внешнюю. В свою очередь отрезок. в точке пересечения с гранью окна'также делится на две части, которые располагаются во внешней и внутренней полуплоскостях. Часть отрезка, расположенная во внешней полуплоскости, в соответствии с
	-	7
алгоритмом отбрасывается, как заведомо невидимая. Алгоритм можно сформулировать в следующем виде.
1.	Для отрезка PiPj проверяется выполнение условий полной видимости и Полной невидимости. Если выполняется одно из условий, то Отрезок является либо полностью видимым, либо невидимым и работа алгоритма заканчивается.
2.	Если точка Р| находится во внутренней полуплоскости, то обозначения концевых точек Р1Р2 меняются местами.
3.	Точка Р| заменяется на пересечение отрезка РД’г с очередной границей <жна. Переход к п. 1.
Реализация алгоритма требует детализации двух операций -определение внутренней и внешней полуплоскостей и нахождение точек пересечения с границами отсекающего окна. Задачу с -полуплоскостями можно решить на оенбве учета наименования ребра, для которого решается эта-задача. Так, для левого ребра внутренняя полуплоскость располагается правее и отбрасывать следует ту часть отрезка, для концевой точки Р которой выполняется условие Хр < Хл. Аналогично решается задача и Для других ребер окна. Точки пересечения определяются как это было показано в разделе 1.2.
। Для повышения эффективности алгоритма можно использовать специальный четырехбитовый код признака М(Р) точки Р, который имеет следующий вид.
| Л | П j В 1 Н t
Соответствующий бит равен единице, если по отношению к этой грани точка находится во внешней полуплоскости. При таком подходе плоскость разбивается на 9 областей. На рис. 5 показаны эти области с соответствующими кодами признаков.
1010	0010	оно
1000	6000	0100
1001	0001	0101
Рис. 5
8
В соответствии с этим точка, расположенная внутри отсекающего окна, имееТхкод признака М(Р) = 0 и является видимой. Условие полной видимости отрезка Р^Р2 с использованием кода признака примет вид
(M(Pj) = 0) & (М(Р2) = О).
Аналогично строится условие полной невидимости этого отрезка.
(M(Pi) & М(Р2» * 0.
Первое условие представляет собой логическое выражение , а второе - логическую операцию над кодами.
С целью повышения эффективности алгоритма можно также использовать параметрическую форму представления отрезков, которая облегчает проверку их располрженпя. Координаты текущей точки Р(х,у) отрезка Р^Р2 в параметрической форме записываются следующим образом:	-
х = xt+ (х2 - Xj) *.t,
У = У1+ <У2 - У1) * t,
где t G [0,1], т.е. параметр t принимает значения в интервале от 0 до 1. ' '
Тогда пересечение прямой, продолжайощей отрезок PjP2, с Левой гранью отсекающего окна дает значение	'
/ *
X -X]  t =------- ,		•
-	х2-*1 .
где t.= 1л при х = хл - для левой грани, t = tri при х = хп - для правой грани.	.
Аналогично можно получить•значения параметра t для верхней и нижней граней
= ZzZl
' У2 л ’ "
где t = tB при у = ув - для верхней грани, t = tH при у = ун - для нижней грани.
9
Если выполняется условие 0 < t < 1, то точка пересечения принадлежит отрезку Pi Pj, в противном случае - нет. z '	\
2. ЗАДАЧА ОТСЕЧЕНИЯ ОТРЕЗКОВ МНОГОУГОЛЬНИКОМ
2.1. Постановка задачи.
Проверка видимости и невидимости отрезков
В качестве отсекающего окна при решении задачи отсечения может использоваться произвольный многоугольник. Простейшим вариантом такого многоугольника может служить прямоугольное окно с неортогональными сторонами по отношению к осям координат.
Алгоритмы отсечения для выпуклых и невыпуклых многоугольников в общем случае различаются. Рассмотрим общие подходы к решению задачи отсечения для выпуклых многоугольников.
Пусть выпуклый многоугольник задан последовательностью х вершин, указанных в порядке обхода его по часовой стрелке - А], Аз, Ап. Для выпуклого многоугольника также можно сформулировать условия полной видимости и полной невидимости отрезков. Как и для регулярного окна, условием полной видимости отрезка является расположение обеих его концевых точек внутри многоугольника. Принадлежность точки внутренней области многоугольникка определяется обходом его сторон по часовой стрелке. Если при этом обходе точка расположена справа по отношению всех ребер многоугольника, то точка принадлежит внутренней его области. Формально процедура обхода и выяснения расположения точки относительно ребер 'многоугольника выполняется вычислением определителей, составленных для всех ребер многоугольника, для которых должйо выполняться следующее условие
X	хм	ХАМ
У.	У Al	Уа+1
W	W ™ Л1	
.где х,у - координаты анализируемой точки,
^Ai> Уаь xAi+b УА1+1 ' координаты концов ребра А, A^f многоугольника,
W, WAi, Wah-i - множители однородных координат.
ю
Более компактно это условие записывается в векторной форме
|Л4,.Д,,|<0, i = 1,2. ...\ п-1;	< °,
где Р, А - вектор-столбцы. однородных координат соответствующих точек.
Таким образом, для определения принадлежности точки области многоугольника необходимо вычислить п определителей третьего порядка, а для отрезка - 2п определителей. В связи с тем, что даже для небольших п это может представлять достаточно трудоемкую операцию, то целесообразно отказаться от проверки условия полной видимости отрезка,, перенеся ее решение на процедуру анализа расположения отрезка в общем случае.
Случай полной невидимости отрезка проверяется также как и для регулярного окна. В соответствии с этпм отрезок должен располагаться полностью по одну сторону (внешнюю) от прямой, продолжающей сторону многоугольника (рис. 6).
Здесь показаны случаи расположения трех отрезков PjPa, Р3Р4, Р,-Рн полностью с внешней стороны граней -щрямых, продолжающих ребра А4А5, А1А2 , А2А3 соответственно и являющихся поэтому невидимыми для данного многоугольника. Однако, отрезок РуРи, являясь полностью невидимым, не ' удовлетворяет условию расположения его с одной стороны какой-либо грани, а следовательно,
11
не может быть выявлен как невидимый с помощью проверки условии, аналогичных гем, что были рассмотрены в подразделе 1.1. Однак-о, в отличие от случая регулярного окна, здесь требуется определить наличие расположения по внешнюю сторону грани обеих точек отрезка • по крайней мере одного ребра многоугольника, т.е. в общем случае это сводится также к вычислению 2п определителей- третьего порядка. Поэтому для многоугольника обычно полную невидимость отрезка определяют относительно регулярного окна,- которое-'. образуется сторонами с координатами .	'	-
хл ~ xmin> хп — '''ших-	У в — Утах> Ун — У min-
Здесь min и max относятся ,к минимальным п максимальным координатам вершин многоугольника (рис. 7).
Рис. 7 *
Естественно, при этом упрощении .часть полностью невидимых отрезков, которые могли бы быть выявленными проверкой условия невидимости для многоугольника, будет отброшено. В общем случае эта часть отрезков невелика и выигрыш во времени компенсирует эту потерю.
Та часть отрезков, которая не была выявлена как видимая или невидимая, подвергается анализу общим алгоритмом задачи отсечения.
12-
2.2. Общий алгоритм отсечеция отрезка выпуклым многоугольником ,
Общий алгоритм решения задачи '"отсечения базируется на определении точки пересечения отрезка Р1Р2, для которого решается эта задача, с ребром многоугольника. С этой целью определим положение всех вершин многоугольника относительно прямой, продолжающей отрезок PjP2 путем вычисления следующих определителей третьего порядка
' Si = |AiP1P2| ,	1 = 1,2, ... , п. 
Значения п определителей Sj могут быть больше, меньше нуля или равны ему. Все возможные сочетания этих значений разобьем на два случая. .
Первый случай: все значения определителей Sj имеют один знак или равны нулю, т.е. вершины расположены по одну сторону отрезка Р1Р2 • или лежат на нем. Тогда возможны следующие варианты.
Вариант 1.1. Все значения S, не равны нулю (Sj 0) - отрезок полностью невидим (все вершины расположены по одну сторону отрезка и не соприкасаются с ним).
Вариант 1.2. Одно значение определителя Sj равно нулю (S, - 0) -прямая, продолжающая отрезок PiP2 проходит через вершину A,. S этом случае надо решить задачу принадлежности этой вершины отрезку Р1Р2 путем определения принадлежности вершины Аг внутренней области регулярного окна в виде прямоугольника, построенного на диагонали PjP2. Если она принадлежит отрезку, то у этого отрезка видимой является только точка Ар
Вариант 1.3- Два значения определителя равны нулю (St = 0 и Sj = 0) - прямая, продолжающая отрезок PiP2, совпадает с гранью ребра AiAj. Здесь необходимо исследовать взаимное расположение отрезка PjP2 и ребра AjAj. При этом возможны варианты полной видимости отрезка, когда
xmin (Р1Р2) > xmin (AjAj)
и Xmax (Р1Р2) < Xmax (А^), а также полной невидимости, когда либо
Хгпах (Р1Р2) < xmin (A^j), „ либо
xmin (Р1Р2) > Xmax (AjAj).
13
В случае выполнение равенства, в приведенных выше условиях, будет видна только одна точка отрезка Р1Р2 - точка Р2 = Aj или точка Pi = Aj соответственно. Кроме этого возможны и частичные перекрытия отрезков, что можно выяснить аналогичными'сравнениями координат. Причем здесь приведен анализ точек по координатам х.' Но 'можно выполнить исследования и по координатам у.	•
Второй случай: определители S; имеют разные знаки, т.е. прямая, продолжающая отрезок Р1Р2, пересекает многоугольник. При этом^ пересечение возможно только в двух точках. Так как многоугольник выпуклый, то при последовательном обходе его вершин знаки определителей S, могут менять свое значение на противоположное только два раза. Пусть эта смена знака происходит для смежных пар вершин Aj и Aj +i, At и Ak+i (рис. 8 ).
- Для определения видимой части отрезка Р1Р2 необходимо определить положение точек Р| и Р2 относительно отрезков AjAj +i, AkAk+i. Для этого требуется выполнить анализ четырех определителей при обходе ребер многоугольника по часовой стрелке:
Sij = |Pi Aj Aj+11, S2j = |₽2 Aj Aj+11,
SncHPiAkAkj.fi, ,. S2k = |p2 Ak Ak+11.
Если определитель меньше нуля, то. соответствующая точка отрезка лежит справа от ребра, т.е. внутри многоугольника. При значении определителя больше нуля точка находится слева во внешней по отношению к многоугольнику области. Равенство определителя 14	.
нулю говорит о нахождении точки на. соответствующем ребре многоугольника. '	•	\	
Рассмотрение всех возможных . сочетаний значений этих определителей дает 64 варианта.(43 ). Исключение случая нахождения концевой точки отрезка на одном из ребер'многоугольника существенно уменьшает  число вариантов до 16. Однако практически достаточно рассмотреть только четыре из них. Рассмотрим эти варианты.
Вариант 1. Отрезок лежит вне многоугольника. В этом случае он полностью невидим. Данное расположение отрезка соответствует следующим сочетаниям знаков определителей
	Sij		 Slk	s2i	
Случай 1.1.	 +		+	
.Случай 1.2.	-		-	+
Эти случаи показаны на рис. 9. Случай 1.1’ соответствует положению отрезка слева от многоугольника, а 1.2. - справа. Следует отметить, что ориентация отрезка на противоположное не влияет на результат его невидимости.
Вариант 2. Отрезок лежит полностью внутри многоугольника. В этом случае отрезок является полностью видимым. Схема этого случая приведена на рис. 10.	• '
15
Рис. 10
Знаки определителей будут иметь следующий вид.
	Sit'	Sik	S2i	S2k
Случай 2.1.				-
Вариант 3. Точки Pf, Р2 лежат по разные стороны многоугольника. В этом случае отрезок является частично видимым. Поэтому следует определить две точки пересечения отрезка с ребрами многоугольника. Видимая часть.отрезка будет находиться между„ними (рис. И).
Рис. И г	Л
Знаки определителей для этого случая приводятся ниже. При этом изменение ориентации отрезка на противоположный дает тайое же изменение знаков.
	Sn	Sik	S2i	. S2k
Случай 3.1.	+			
Случай 3.2.	-	+	+ >	•-
16
Вариант 4. Один конец отрезка находится вйутри многоугольника, другой снаружи. При этом отрезок также является частично видимым - между точкой пересечения отрезка с ребром многоугольника и концевой точкой отрезка, расположенной внутри отсекающего многоугольника (рис. 12).
Рис. 12
Знаки определителей для этих случаев имеют следующий вид.
	Sli	Slk	- S2i	S2k
Случай 4.1.	-	+		
Случай 4.2.	+ .,	-	-	-
Случай 4.3.	-	-	-	+ ' \
Случай 4.4.	- •	-	• +	-
17
В соответствии с рассмотренными вариантами можно построить общий алгоритм определения видимой части отрезка.	\
2.3. Алгоритм Кируса-Бека отсечения отрезка выпуклым окном
Повышение быстродействия алгоритмов отсечения возможно за счет использования более эффективного метода определения местоположения точки отрезка относительно отсекающего окна. Такой метод заложен в алгоритме Кнруса-Бека. Он использует для решения этой, задачи вектор нормали к ребрам многоугольника. При этом выпуклый многоугольник представляется как область пересечений полуплоскостей, ограниченных прямыми, проходящими через ребра многоугольника (рис. 13).
Внутренней нормалью к ребру многоугольника называется единичный вектор перпендикулярный к этом)' ребру и направленный внутрь многоугольника. Обозначим внутреннюю нормаль ребра AjAi+f через П{ (I = 1,2,...,п). Если ( - некоторая точка, лежащая на ребре многоугольника; п - внутренняя нормаль к этому ребру, а Р -некоторая точка, полуплоскости, то знак скалярного произведения нормали и вектора из точки 1 в точку Р •определяет положение точки относительно грани, содержащей данное ребро (рис. 14).
V = п * (Р Ф).
18
Если взять точку f, совпадающую с вершиной.многоугольника, то можно рассмотреть следующие три характерных случая расположения точки Р, принадлежащей отрезку Р1Р2 (рис. 15).
Первый случай - угол между векторами п и (P-f) больше 90°:
V = п * (Р - f) < 0, а > ТС /2.
Второй случай - угол между векторами п и (P-f) равен 90°:
V = п *. (Р - f) = 0, а = ТС/2.
Третий случай - угол между векторами п и (P-f) меньше 90°:
Для построения алгоритма, здесь используется параметрическая запись прямой, продолжающей 01 резок !\Р>.
а
P(t) = Pj + (P2 Pi> * t, /где t - параметр, определяющий положение’точки на прямой.
При значениях
О < t < 1
точка принадлежит отрезку PtP2. Если t < 0, то точка лежит левее точки Pj, а при t > 1 - правее Р2.
В соответствии с этим для tomi.ii пересечения прямой с ребром многоугольника (второй случаи р.к положения точки Р) можно вычислить параметр t, заменяя, точку f на вершину многоугольника А,:
Щ * (Р< + (Р2 ’ Pl) * t  А-,) = 0.
Из этого выражения после преобразований получаем значение параметра.
_ П‘ ’
~ л;*(Л-Л)‘
Выполним анализ полученного выражения. Для этого рассмотрим . случай равенства нулю знаменателя. Это возможно, когда Р2 = Pi или же в случае расположения отрезка PjP2 параллельно ребру многоугольника (угол# между векторами п и. PjP2 равен ТГ/2). Совпадение точек концов отрезка дает вырожденный случай, который не входит в рассмотрение задачи отсечения отрезка. При параллельном расположении отрезка возможны три варианта его видимости, определяемые из анализа числителя:	,
4) гц * (Pj - Aj) < 0. В этом случае точка *Pf находится вне отсекающего многоугольника (# >.7Г/2), а следовательно, и точка Р2; поэтому отрезок будет полностью невидимым;
1. i»i * (Pj - АД = 0. Точка Pi находится на границе отсекающего окна; значит отрезок лежит на грани данного ребра многоугольника, и для выделения видимой части отрезка следует найти общую часть отрезка и ребра;
2. п, * (Pj - А,) > 0. Точка Pi находится внутри отсекающего окна; в данном случае рассматриваемое ребро не влияет на видимость отрезка. •
В' случае неравенства нулю знаменателя, значение t дает точку пересечения прямой, продолжающей отрезок, и грани ребра. При 20
значениях t < 0 или t, > 1 точка пересечения находится за пределами отрезка Р1₽2- Тогда при t < 0 данное ребро не влияет на видимосч отрезка (рис. 16).
Рис. 16
При t > 1 отрезок полностью невидим, так как точка пересечёни> ' находится правее отрезка'(рис. 17).
Если ориентацию отрезка поменять на противоположную (поменять местами точки Pj и Р2), то рассмотренные последние два случая также поменяются местами.
Рассмотрим теперь случай 0 < t < 1. Здесь также возможны два варианта (рис. 18).	.	‘
21
Рис. 18
В первом случае (рис. 18а) видимым является отрезок Р₽2, во втором (рис. 18b) отрезок PPj. По этому поводу говорят, что отрезок укорачивается снизу или сверху соответственно.
Прямая, продолжающая отрезок PiP2, может пересечь многоугольник только в двух местах. Однако решение уравнения для t относительно всех ребер даст множество решений в интервале 0 < t < 1, из которых следует выбрать необходимые. Для этого все решения разбиваются нА две группы, которые называются нижней и верхней, в зависимости . от того, к какой точке отрезка ближе расположено г рассматриваемое решение - к началу или концу отрезка соответственно. После разбиения решений выделяют наибольшее значение из нижней группы t„, наименьшее - из верхней tB, которые рассматриваются,' как возможные ограничения, снизу и сверху. Если окажется, что tH > tB, то отрезок является полностью невидимым.
На основании описанного алгоритма можно составить программу.
2.4. Отсечение отрезка невыпуклым многоугольником
Отсечение отрезка невыпуклым многоугольником во многом совпадает с алгоритмом для выпуклого многоугольника. Сначала вычисляются определители
Si = |AiP1P2|, i = 1,2, ... , n, которые выявляют расположение вершин многоугольника А( относительно прямой, продолжающей отрезок PiP2- Первый случай, когда все определители имеют один знак или равны нулю, полностью совпадает с предыдущим алгоритмом,.а во втором случае, при наличии определителей разного знака, . следу.ёт выявить ребра, которые пересекает прямая, продолжающая отрезок PjP2- Эти ребра имеют в 22
своих вершинах определители Sj разного знака (рис. 19): AjAj, А3А/
А5А6, А7А8.	.	•
Для определения видимых частей отрезка необходимо:
- найти точки пересечения прямой, продолжающей отрезок, с ребрами многоугольника;
выделить нечетные интервалы, принадлежащие области многоугольника;
- определить принадлежность этих интервалов отрезку.
Точки пересечения находятся методикой определения пересечения отрезка (в данном случае ребра многоугольника) и прямой, продолжающей отрезок Pi₽2- Нечетные интервалы находятся выбором произвольной точки на прямой, продолжающей отрезок, лежащий вне многоугольника и' движением по этой прямой до пересечений ,с ребрами. За первым, третьим и так далее пересечениями лежат нечетные интервалы. После этого необходимо выяснить, какие части этих интервалов совпадают с отрезком, которые и будут являться видимой частью данного отрезка.
3. ОТСЕЧЕНИЕ МНОГОУГОЛЬНИКОВ
3.1. Постановка задачи
Задачу отсечения многоугольников можно рассматривать как 'задачу отсечения отрезков (ребер многоугольников), составляющих этот многоугольник. Однако при этом результат отсечения даст набор несвязанных видимых частей ребер многоугольника, которые не составляют замкнутую область, что является недопустимым’ для
23
решения некоторых задач, например, для заливки части многоугольника. На рис. 20 показан результат работы алгоритма отсечения для невыпуклого многоугольника, который содержит набор несвязанных отрезков ребер (выделены жирным шрифтом). Они не составляют никакой замкнутой области. При изменении постановки ши можно получить две замкнутые области В1 и В2 путем добавления отрезков (сплошные отрезки, совпадающие с ребрами отсекающего окна).
3.2. Алгоритм Сазерленда-Ходжмена отсечения многоугольников выпуклым окном
Рассмотрим решение задачи отсечения многоугольников выпуклым окном по алгоритму Сазерленда-Ходжмена. Идея алгоритма основывается на последовательном отсечении многоугольника полуплоскостями, образованными гранями выпуклой отсекающей области. На рис. 21 показан процесс последовательного' отсечения левой, верхней,, правой и нижней гранями соответствующих ребер отсекающего окна. Отсечение каждой полуплоскостью выполняется путем обхода вершин многоугольника и анализа положения вершин относительно отсекающей полуплоскости. В результате обхода порождается новая последовательность вершин многоугольника, соответствующая многоугольнику, полученному лосле отсечения очередной полуплоскостью. При этом каждая вершина исходного многоугольника может быть заменена на 0, 1 или 2 вершины в новой последовательности. Эта замена выполняется следующим образом.
24
e)	f)
Рис. 21
При обходе вершин многсДтольника переход от вершины А>-1 вершине А-, может иметь четыре различные варианты взаимного расположения ребра многоугольника п отсекающей полуплоскости. Рассмотрим эти варианты.
Обе вершины А;д и А; находятся вне полуплоскости (рис.22). В этом случае . при обходе этого ребра в результирующую последовательность не передается ни одна вершина.
25
Обе вершины Aj.t и Aj находятся внутри полуплоскости (рис.23).
В результирующую последовательность передается вершина А).
Одна вершина Aj_t находится снаружи, а другая А, - внутри полуплоскости (рис. 24).
В этом случае в результирующую последовательность пере даются точки Р п А,. Этот случай называется вхождением в полуплоскость.
Одна вершина Aj.i находится внутри, а другая А; - снаружи полуплоскости (рис.25). В результирующую последовательность передается точка Р.
26
Начало работы алгоритма начинается с определения видимости первой вершины многоугольника. Если она является видимой, то. вершину помещают в результирующую последовательность, г противном случае - нет. При обработке последней пары вершин А,Л,А] случае входа или выхода из полуплоскости в результирующую последовательность передается точка Р пересечения ребра AnAt с гранью полуплоскости. В соответствии с изложенным выше можно , построить алгоритм решения задачи отсечения многоугольников выпуклым окном.
Для отсечения невыпуклых многоугольников выпуклым многоугольником можно применять аналогичную процедуру, однако при этом следует учитывать возможность появления лишних- ребер в результирующей последовательности, если отсекаемая область состоит' из несвязных частей.
3.3.	Алгоритм Вейлера-Азертона отсечения многоугольников невыпуклым окном
Предлагаемый алгоритм позволяет отсекать один невыпуклый многоугольник другим, в. общем случае тоже невыпуклым. При этом каждый многоугольник может содержать дыры (отверстия). Идея алгоритма заключается в последовательном обходе вершин многоугольника. При входе в отсекающее окно обход выполняется по ребрам отсекаемого (обрабатываемого) многоугольника, при выходе -по ребрам отсекающего окна9 до прихода в следующую точку пересечения многоугольников. Алгоритм предусматривает формирование контуров обхода обрабатываемого и отсекающего многоугольников с указанием точек их пересечения. Рассмотрим
'	27
пример работы алгоритма отсечения многоугольника (рис. 26). На рисунке жирной линией обозначен обрабатываемый многоугольник А1А2А3А4А5А16, а отсекающее окно - многоугольник С1С2С3С4 - тонкой линией. Для организации работы алгоритма необходимо отметить точки пересече1[ия ребер многоугольников.
На рисунке они обозначены как Ij, I2, I3, I4, I5, Ig, h, Is- Эти точки пересечения следует разделить на две группы - на точки входа в' отсекающую область (Ij, I4, I5, Ig ) и на точки выхода из нее (I2, I3, Ig, I7). Поиск отсекаемых областей выполняется по контурам многоугольников, составленных в виде цепочек последовательностей, составленных из вершин многоугольников и точек пересечения, полученных обходом многоугольников по часовой стрелке. Движение начинается из любой точки входа ио часовой стрелке, расположенной на обрабатываемом многоугольнике до прихода в точку выхода. После этого выполняется переход на отсекающий многоугольник, по которому движение производится до прихода во входную точку. Затем выполняется аналогичный переход на обрабатываемый многоугольник. Эта процедура выполняется до возврата в точку, с которой начиналось движение. Если при этом будут пройдены все точки пересечения, то процесс заканчивается. В противном случае снова выбирается одна из оставшихся входных точек, и процедура повторяется по описанному алгоритму. Покажем это на примере многоугольников, представленных на рис. 26. Контурные цепочки расположены в виде двух столбцов, а последовательность их обхода обозначена стрелками. В результате обхода получены два-контура отсеченных областей: К I3 I4 I2 Ij и I5 Ig ls 17 С4 I5 (рис. 27).
28
Полученные области можно проверить по рис. 26.
3.4.	Алгоритм Вейлера-Азертона для внешних • отсекаемых областей
Данный метод пригоден и для выделения внешних отсекаемых областей. В этом случае следует внести следующие коррективы в процедуру выделения.
Рис 28
Начинать движение по ребрам многоугольников необходимо с точки выхода, а движение но ребрам отсекающего многоугольника выполнить против часовой стрелки. Покажем это на предыдущем 29
примере (рис. 26). В результате обхода (рис. 28) ребер многоугольников, начиная с точек пересечения, получены три внешних отсекаемых области -I3A2I4I3, IgAjlglg и I2A3I5C4I7A5A6AJ1I2. •а.
3.5.	Алгоритм Вейлера-Азертона для многоугольников с дырами
При наличии отверстий (дыр/ в многоугольниках к внешним контурам добавляются внутренние в Последовательности обхода против часовой стрелки. Рассмотрим работу алгоритма на следующем примере (рис. 29).
Точки пересечения многоугольников, как и прежде, разделим на два множества - точки входа 1§, I4, (б, I.2> ho и точки выхода I5, I3, Ig, I7. Расположим две црследовательности вершин и точек пересечения для обрабатываемого и отсекающего; многоугольников в виде двух столбцов. При этом вверху располагаются внешние, а внизу -внутренние контура этих многоугольников (рис. 30). В результате обхода контуров получаем область отсечения Ig Ij I2 А9 I9 С5 Cg 1щ I7 Ig. , При этом часть точек пересечения многоугольников не попала в отсеченную область, * поэтому процесс поиска областей отсечения необходимо продолжить. *	. 
30
Рис. 30
Аналогичный обход последовательностей вершин и точек пересечений обоих многоугольников, например, с точки входа, I4, даст следующую область - I4 A3 I5 С3 Ig I3 I4. В результате выполненных действий выделены две .отсекаемые области и, т.к. исчерпаны все точки пересечений, алгоритм на этом закончен.
4.	НОРМАЛИ К РЕБРАМ И ВЫПУКЛОСТЬ МНОГОУГОЛЬНИКОВ
4.1.	Вычисление внутренней нормали
Для организации работы; по алгоритму Кируса-Бека требуется вычислять внутреннюю нормаль к ребрам многоугольника, которая представляет собой единичный ректор, перпендикулярный, к ребру инаправленный во внутреннюю область Многоугольника. Вычисление нормали П; для ребра A,Aj+i ' можно выполнить  операцией поворота единичного вектора данного ребра на угол (- 90°):
31
пг = R(-90°) * e(Ai),
где R(-90°) - матрица поворота,
e(Aj) - единичный вектор ребра AjAi+1.
Матрицу поворота в однородных координатах можно вычислить , совании матрицы преобразований R(<p):
( cos ср
sin ф
И(ф) = | - sin ф cos ф I О О
О
О I
1 J
I О
После подстановки значения угла ф получаем матрицу
( 0 -1 О
И(ф) =	| 1	0	0 |
к О О 1 ) .
Единичный вектор е(А[) можно вычислить из выражения
(А, - Ai+1) = e(Aj) «| Aj - Aj+i | ,
где | А; - Ai+1 | - модуль вектора (Aj - Aj+t). В соответствии с этим можно записать для единичного вектора:
e(Ai) = (Ai - Aj+i)/ | Ai -Ai+1;| .
При этом вектор ребра Представляет собой вектор-строку
( xi+1 - Xi yi+i - yi w > ,
а модуль ребра вычисляется как
| А, - Ai+i | = (xi+i - Xj)2 + (yi+1у,) 2
4.2.	Проверка выпуклости многоугольников
Проверка выпуклости многругольника выполняется путем вычисления определителей третьего порядка вида
32
Si I Aj+2 A, Aj4-i I ,
позволяющих определить взаимное ' положение вершины Ai+2 относительно ребра A, Aj+f. Если S, < 0, то вершина лежит справа от ребра при обходе многоугольника по часовой стрелке. Знак этого определителя относится к вершине А,*]. Вычислив определители для всех ребер многоугольника по их знакам определяют выпуклость данного многоугольника: если знаки имеют значение “минув”, то многоугольник является выпуклым. При невыполнении этого условия многоугольник является невыпуклым, а число положительных знаков определяет число вершин нарушающих выпуклость многоугольника. При обходе многоугольника против часовой стрелки знаки определителей и условия выпуклости принимают противоположный смысл.
Если ставится задача разбиения невыпуклого многоугольника на выпуклые части, то это можно сделать продлением одного из смежных ребер вершины. нарушающей выпуклость многоугольника, до пересечения с ребром многоугольника. Каждая такая опсраци уменьшает число вершин, нарушающих выпуклость многоугольника, ио крайней мере, на одну. Для полного разбиения многоугольника требуется число операций не превосходящее числа вершин, нарушающих его выпуклость.
5.	ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ И ВАРИАНТЫ ЗАДАНИЙ
Задание по данной лабораторной работе может варьироваться по сложности в зависимости от задачи, поставленной преподавателем. Оно может включать следующие элементы:
1.	Определение видимости-невидимости отрезка для регулярного окна по его координатам.
2.	Определение видимости-невидимости отрезка для регулярного окна но четырехбитовым кодам признаков.
3.	Определение видимости-невидимости отрезка для выпуклого многоугольника по его координатам.
4.	Определение видимости-невидимости отрезка для выпуклого многоугольника по координатам- путем замены многоугольника регулярным окном по минимаксным координатам его ребер.
5.	Общий алгоритм отсечения отрезка регулярным окном.
6.	Алгоритм Сазерленда-Коэна отсечения отрезка регулярным окном.
33
7. Алгоритм Кируса-Бека отсечеппя отрезка выпуклым Mlioroyi О.ТЬПИКОМ.
8. Алгоритм отсечения отрезка нсвыпуклым многоугольником.
9. Алгоритм Сазерленда-Ходжмена отсечения многоугольника.
10.	Алгоритм . фугим.	Вейлера-Азертона	отсечен,	одного	многоугол bi 111 ка
и.	Алгоритм другим для	Вейлера-Азертона отсечения внешней отсекаемой области.		одного	многоугольника
12.	Алгоритм	Вейлера-Азертона	отсечения	ОДНО1|О	многоугольника
другим при наличии в них дыр.
13.	Вычисление'нормали.
14.	Определение выпуклости многоугольников.
15.	Разбиение невыпуклых многоугольников на выпуклые части.
Отчет должен содержать задание, изложение алгоритмов решения поставленных задач, описание программы, в которую могут входить данные о структуре программы,4 об исходных и результирующих данных, требования к аппаратному и -программному обеспечению, результаты тестирования (отладки) программы, инструкция пользователю, описание сеанса работы с программой и листинг.
ЛИТЕРАТУРА
1.	Роджерс Д. Алгоритмические основы машинной графики.-М.: Мир, 1989. 504 с.
2.	Павлидис Т. Алгоритмы машинной графики и обработки изображений,- М.: Радио и связь, 1986.
3.	Фоли. Дж., А. вэн Дэм. Основы интерактивной машинной графики. Кн.1,- М.: Мир, 1985.
4.	Фоли Дж., А. вэн Дэм. Основы интерактивной машинной графики. Кн.2,- М.: Мир, 1985.
> 5. .Аммерал Л. Принципы программирования в машинной графике/ Пер. с англ. М.: "Сол Систем", 1992.
6.	Аммерал Л. Машинная графика на персональных компьютерах/ Пер. с англ. М/. "Сол Систем", 1992.
7.	Аммерал Л. Интерактивная трехмерная машинная графика/ Пер. с англ. М.: "Сол Систем", 1992.,
8.	Аммерал Л. Программирование графики на Турбо Си/ Пер. с англ. М.: "Сол Систем", 1992.
9.	Начала компьютерной графики; Под ред. Шикнна Е.В. М/. "Диалог-МИФИ", 1993. 138 с.
10.	Шпкин Е.В., Боресков.А,В. -Компьютерная графика. Динамика, реалистические изображения. М.:"Диалог-МИФИ", 1995. 287 с.
34
СОДЕРЖАНИЕ
Введение
1.	Отсечение отрезков регулярным окном '
1.1.	Определение полной видимости и полной невидимости отрезков
1.2.	Задача отсечения отрезка с произвольным расположением
1.3.	Алгоритм Сазерленда-Коэна отсечения отрезка регулярным окном
2.	Задача отсечения отрезков многоугольником
2.1.	Постановка задачи. Проверка видимости и невидимости отрезков
2.2.	Общий алгоритм отсечения отрезка выпуклым многоугольником
2.3.	Алгоритм Кируса-Бека отсечения отрезка выпуклым окном
2.4.	Отсечение отрезка невыпуклым многоугольником
3.	Отсечение многоугольников
3.1.	Постановка задачи
3.2.	Алгоритм Сазерленда-Ходжмена отсечения многоугольников выпуклым окном
3.3.	Алгоритм Вей лера -Азертона отсечения многоугольников невыпуклым окном
3.4.	Алгоритм Бейлера-Азертона для внешних отсекаемых областей
3.5.	Алгоритм Вей лера-Азертона для многоугольников с дырами
4.	Нормали к ребрам и выпуклость многоугольников
4.1.	Вычисление внутренней нормали
4.2.	Проверка выпуклости многоугольников
5.	Порядок выполнения работы и варианты заданий
Литература
35