В компьютерной графике часто приходится решать задачу выделения некоторой области изображаемой сцены, причем задача эта может решаться как в применении к плоской области (если сцена уже спроецирована на картинную плоскость), так и к трехмерной. Алгоритмы отсечения применяются для удаления невидимых поверхностей и линий, для построения теней, при формировании текстур. Отсекаемая область может быть как правильной формы (прямоугольник или параллелепипед со сторонами, параллельными осям координат или координатным плоскостям), так и неправильной (произвольный многоугольник или многогранник). Для того чтобы эти алгоритмы можно было использовать в задачах изображения динамичных сцен, они должны быть эффективными в отношении времени вычислений. Мы рассмотрим несколько наиболее часто применяемых алгоритмов.
Рассмотрим плоскую сцену, состоящую из отрезков различной длины и направлений, в которой надо выделить часть, находящуюся внутри прямоугольника. Прямоугольник задан списком ребер: <top>, <bottom>, <left>, <right>, отрезки также задаются координатами концевых точек. Область, отсекаемая окном (с учетом его границы), состоит из точек $$(x,y)$$, удовлетворяющих соотношениям$$x_l\le x\le x_r, \quad y_b\le y\le y_t.$$ Пусть концы отрезка заданы точками $$(x_1,y_1)$$ и $$(x_2,y_2)$$. Первый шаг алгоритма нацелен на то, чтобы выявить полностью видимые и полностью невидимые отрезки. Отрезок целиком принадлежит выделяемой (клиппируемой) области, если оба его конца удовлетворяют условиям (5.1).
(рис 5.1) Коды Сазерленда-Коэна для областейОтрезок полностью невидим, если оба его конца лежат
Во всех остальных случаях отрезок может (но не обязан) пересекать прямоугольное окно.
Для выполнения анализа полной видимости или невидимости отрезка А.Сазерленд и Д.Коэн предложили следующий алгоритм. Прямые, которым принадлежат ребра прямоугольника, разбивают плоскость на девять областей, каждой из которых присваивается четырехразрядный код. Каждый бит этого кода "отвечает" за одну из прямых: 1-й (старший) бит - за прямую $$t$$, 2-й - за прямую $$b$$, 3-й - за $$r$$, 4-й - за $$l$$. Если в коде области какой-либо бит установлен в 1, то это означает, что она отделена от окна соответствующей прямой. Схема идентификации областей приведена на рис. 5.1.
Концевым точкам отрезков сцены теперь можно присвоить коды в зависимости от расположения точек. Ясно, что если коды обоих концов отрезка равны нулю, то отрезок полностью лежит внутри окна. Для дальнейшего анализа воспользуемся операцией логического умножения кодов (поразрядное логическое "И"). Тогда таблица истинности для кодов, согласно схеме на рис. 5.1, будет выглядеть следующим образом:
| $$C_1$$ | $$C_2$$ | $$C_3$$ | $$C_4$$ | $$C_{13}$$ | $$C_{14}$$ | $$C_{23}$$ | $$C_{24}$$ | |
| $$C_1$$ | T | F | F | F | T | T | F | F |
| $$C_2$$ | F | T | F | F | F | F | T | T |
| $$C_3$$ | F | F | T | F | T | F | T | F |
| $$C_4$$ | F | F | F | T | F | T | F | T |
| $$C_{13}$$ | T | F | T | F | T | T | T | F |
| $$C_{14}$$ | T | F | F | T | T | T | F | T |
| $$C_{23}$$ | F | T | T | F | T | F | T | T |
| $$C_{24}$$ | F | T | F | T | F | T | T | T |
Из сопоставления таблицы с рисунком видно, что если произведение кодов концов отрезка принимает значение <True>, то отрезок целиком лежит по одну сторону какой-то из прямых, причем внешнюю сторону по отношению к окну, следовательно, он полностью невидим. Во всех остальных случаях отрезок может частично лежать внутри окна, поэтому для определения их видимой части надо решать задачу о пересечении отрезков с ребрами окна. При этом желательно по возможности сократить число перебираемых пар "отрезок-ребро".
В самом общем случае существуют две точки пересечения отрезка с ребрами, и эти две точки принимаются за новые концевые точки изображаемого отрезка. Но сначала можно выделить некоторые более простые частные случаи, поиск пересечений для которых является более эффективным. Прежде всего это горизонтальные и вертикальные отрезки, для которых поиск точки пересечения тривиален. Далее, если код одного из концов отрезка равен нулю, то существует только одно пересечение этого отрезка с ребром (или с двумя ребрами, если отрезок проходит через угловую точку окна). На рис. 5.2 приведена общая блок-схема алгоритма отсечения для одного произвольно направленного отрезка.
(рис 5.2) Блок-схема алгоритма Сазерленда-КоэнаВ блок-схеме используются следующие соглашения и обозначения:
GetCode(r) - определение кода точки;
Intersec0(r1,l) - поиск пересечения отрезка со сторонами окна при условии, что обе точки лежат вне окна; если пересечения нет, устанавливает переменную IsVisible в 0;
Intersec(r1,l) - поиск пересечения отрезка со сторонами окна при условии, что точка r1 лежит в окне;
C1, C2 - коды точек r1, r2.
В приведенном алгоритме теперь остается только детализовать функции Intersec0 и Intersec, эффективность работы которых является ключевым моментом. Рассмотрим один из методов поиска пересечений, который использует параметрическое уравнение прямой, проходящей через точки $$\overrightarrow{r}_1=(x_1,y_1), \; \overrightarrow{r}_2=(x_2,y_2)$$:$$\overrightarrow{r}=\overrightarrow{r}_1+s(\overrightarrow{r}_2-\overrightarrow{r_1}), \quad s\in[-\infty,+\infty],$$ или в координатном виде$$x=x_1+sl_x, \quad y=y_1+sl_y, \quad l_x=x_2-x_1, \quad l_y=y_2-y_1.$$ Попробуем определить точку пересечения отрезка с верхней границей окна. Поскольку эта граница описывается соотношениями$$L\le x\le R, \quad y=T,$$ то условие пересечения с ней клиппируемого отрезка выглядит следующим образом:$$s_T=\frac{T-y_1}{l_y}, \quad L\le x_1+s_T l_x \le R.$$
Аналогично выглядят формулы и для остальных границ окна. Если точка $$\overrightarrow{r}_1$$ расположена внутри окна, то, в зависимости от знака $$l_y$$, следует искать пересечение либо с верхней, либо с нижней границей окна. При отсутствии таковых отыскиваются пересечения с левой или правой стороной окна. Но прежде чем перебирать эти варианты, необходимо исключить случаи горизонтальных $$(l_y=0)$$ и вертикальных $$(l_x=0)$$ направлений отрезка. В первом случае точками пересечения с правой или левой границей (в зависимости от знака $$l_x$$ ) могут быть $$(L,y_1)$$ или $$(R,y_1)$$, а во втором - $$(x_1, B)$$ или $$(x_1,T)$$.
Этот алгоритм реализован в виде функции Intersec, блок-схема которой приведена на рис. 5.3.
Теперь рассмотрим случай, когда ни один из концов отрезка не лежит внутри окна. Здесь мы можем найти первую точку пересечения, заменить ею один из концов отрезка и использовать предыдущий алгоритм нахождения второй точки. Заметим, что в данном случае первый шаг не всегда кончается успешно, поскольку предварительный анализ не позволяет полностью исключить все невидимые отрезки. Как и в предыдущем алгоритме, сначала выполняется проверка на горизонтальное и вертикальное направления отрезка. Поскольку часть отрезков мы уже исключили из рассмотрения благодаря предварительному анализу, то для этих простых ситуаций остаются только две возможности, приведенные на рис. 5.4. Здесь точки пересечения определяются совершенно очевидным образом, причем сразу обе.
Затем последовательно рассматриваются четыре случая расположения точки $$\overrightarrow{r}_1$$ относительно прямых, ограничивающих окно. Если в каком-то из вариантов будет найдена точка пересечения, то анализ прекращается, точка $$\overrightarrow{r}_1$$ заменяется новой точкой и вызывается функция Intersec. В случае же, когда все четыре варианта не дали положительного результата, переменной IsVisible присваивается значение 0. Алгоритм реализуется функцией Intersec0 (блок-схема на рис. 5.5).
Предложенная реализация алгоритма отсечения не является единственной в своем роде. Существуют и другие подходы, в частности использование метода деления отрезка пополам для поиска точек пересечения и выявления видимой части отрезка. Такой вариант алгоритма был предложен Сазерлендом и Спрулом для аппаратной реализации, но он может быть реализован и на программном уровне, хотя при этом эффективность его будет ниже, чем у предыдущего. В нем нет прямого вычисления координат новой точки по явным алгебраическим соотношениям. Поиск осуществляется итерационным методом, в котором на каждом шаге для отрезка, "подозреваемого" в частичной видимости, находится его средняя точка, определяется ее код, затем из двух отрезков оставляются либо оба (если они оба не окажутся полностью невидимыми), либо только один, после чего операции продолжаются с новыми отрезками. Ситуация, когда дальнейшему дроблению подвергаются сразу два вновь полученных отрезка, может возникнуть только на первом итерационном шаге в тех случаях, когда исходный отрезок имеет две точки пересечения с границами окна. На последующих итерационных шагах количество анализируемых отрезков уже не будет увеличиваться. Процесс продолжается до тех пор, пока длина очередного отрезка не станет меньше наперед заданной точности. После этого найденная точка проверяется на предмет пересечения со стороной окна. На рис. 5.6 приведены три варианта отрезков, предварительный анализ которых не классифицирует их как полностью невидимые, и показан первый итерационный шаг. Отрезок a после первого деления дает два частично видимых отрезка, после чего ищутся две точки пересечения. В остальных случаях остается лишь один из двух отрезков, причем в случае отрезка c точка пересечения со стороной окна отсутствует, т.е. обнаруживается полная невидимость отрезка. По сути дела общий алгоритм, показанный на рис. 5.3, сохраняется, изменяется лишь метод поиска точки пересечения.
(рис 5.4) Блок-схема функции Intersec(рис 5.3) Отрезки параллельны сторонам окна
(рис 5.6) Блок-схема функции Intrsec0(рис 5.5) Произвольное расположение отрезковВо многих задачах компьютерной графики часто приходится иметь дело с отсечением не только простым прямоугольным окном, но и окном достаточно произвольной геометрии. В частности, такие задачи могут возникнуть при использовании перспективных проекций трехмерных сцен, но не только в этих случаях. Поэтому актуальной является задача отсечения выпуклым многоугольником. Ясно, что простой анализ с помощью кодов Сазерленда-Коэна в такой ситуации неприменим. Здесь нужен надежный и достаточно эффективный алгоритм нахождения точки пересечения двух произвольно ориентированных отрезков, а также алгоритм определения местоположения точки относительно многоугольника (внутри, снаружи или на границе).
Рассмотрим задачу о пересечении отрезка с концами $$\overrightarrow{r}_1=(x_1,y_1), \; \overrightarrow{r}_2=(x_2,y_2)$$ с выпуклым
многоугольником, заданным списком ребер. Ребро может быть задано в
виде пары точек из множества вершин многоугольника $$R=(\overrightarrow{p},\overrightarrow{q}), \; \overrightarrow{p}=(p_x,p_y), \; \overrightarrow{q}=(q_x,q_y)$$ (рис. 5.7).
То обстоятельство, что многоугольник выпуклый, является очень
существенным: это позволяет использовать достаточно простой алгоритм,
использующий внутренние нормали к его сторонам. Под внутренней
нормалью понимается вектор, перпендикулярный стороне и направленный
внутрь многоугольника. Как и в предыдущем алгоритме, воспользуемся
параметрическим уравнением прямой, проходящей через концы отрезка: $$\overrightarrow{r}=\overrightarrow{r}_1+s(\overrightarrow{r}_2-\overrightarrow{r}_1)$$.
Если при некотором значении параметра $$s_0$$ эта прямая пересекается с
прямой, проходящей через точки $$\overrightarrow{p}, \overrightarrow{q}$$, то вектор, соединяющий
произвольную точку ребра с точкой $$\overrightarrow{r}_0=\overrightarrow{r}_1+s_0(\overrightarrow{r}_2-\overrightarrow{r}_1)$$, будет перпендикулярен вектору
нормали. Следовательно,
(рис 5.7) Пересечение отрезка многоугольникомКонечно, использование этой формулы предполагает, что $$d\equiv((\overrightarrow{r}_2-\overrightarrow{r}_1)\cdot\overrightarrow{n})\ne 0$$, т.е. что отрезок не параллелен стороне многоугольника, но этот случай рассматривается отдельно. Найденная точка принадлежит отрезку при условии $$0\le s_0\le 1$$. Условие принадлежности этой точки ребру многоугольника также можно выразить через скалярное произведение, так как векторы $$\overrightarrow{p}-\overrightarrow{r}_0$$ и $$\overrightarrow{r}_0-\overrightarrow{q}$$ в этом случае должны быть одинаково направленными, т.е. $$((\overrightarrow{p}-\overrightarrow{r}_0)\cdot(\overrightarrow{r}_0-\overrightarrow{q}))\ge 0$$.
Для каждого отрезка возможны три случая взаимного расположения с многоугольником:
В каждом из этих вариантов для нахождения пересечения отрезка с окном необходимо уметь определять принадлежность точки выпуклому многоугольнику. Из рис. 5.7 видно, что если для любой точки $$\overrightarrow{g}$$, принадлежащей многоугольнику (или его границе), и произвольной точки ребра $$\overrightarrow{f}$$ построить вектор $$\overrightarrow{m}=\overrightarrow{g}-\overrightarrow{f}$$, то выполняется условие $$(\overrightarrow{m}\cdot\overrightarrow{n}\ge 0)$$, поскольку угол между векторами не может превышать 90 $$\deg$$. Таким образом, если данное условие выполняется для всех ребер многоугольника, то точка является внутренней.
Таким образом, алгоритм отсечения отрезка начинается с анализа расположения концов отрезка по отношению к окну. Если обе точки лежат внутри окна, то отрезок полностью видимый, и дальнейший поиск прекращается. Если только одна из точек лежит внутри окна, то имеет место случай II, и предстоит найти одну точку пересечения. И, наконец, если обе точки лежат вне окна, то существуют либо две точки пересечения (отрезок пересекает две границы окна), либо ни одной (отрезок полностью невидим). Впрочем, две точки пересечения могут совпадать (если отрезок проходит через вершину многоугольника), но этот случай в дополнительном анализе не нуждается.
Далее выполняется цикл по всем ребрам многоугольника с целью нахождения точек пересечения. Для каждого ребра перед началом поиска пересечения необходимо проверить, не параллельно ли оно с отрезком. Если это так, то можно вычислить расстояние от одного из концов отрезка до прямой, проходящей через ребро $$d=((\overrightarrow{r}_1-\overrightarrow{p})\cdot\overrightarrow{n})$$. При $$d=0$$ отрезок лежит на прямой, и остается определить взаимное расположение концов отрезка и концов ребра, что можно сделать простым покоординатным сравнением. При $$d\ne 0$$ отрезок не имеет общих точек с данным ребром.
От задачи отсечения отрезков можно перейти к более сложной: клиппирование произвольных многоугольников. Если многоугольник невыпуклый, то в результате пересечения даже с прямоугольным окном может получиться несколько не связанных между собой фигур, как это показано на рис. 5.8.
(рис 5.8) Отсечение невыпуклого многоугольникаКогда стоит задача штрихования замкнутой области одновременно с задачей отсечения, то важно правильно определить принадлежность вновь полученных фигур внутренней или внешней части исходного многоугольника. Пусть исходный многоугольник задан упорядоченным списком вершин $$\{\overrightarrow{p}_1,\overrightarrow{p}_2,\ldots,\overrightarrow{p}_n$$, соответствующих ребрам $$(\overrightarrow{p}_1,\overrightarrow{p}_2),(\overrightarrow{p}_2,\overrightarrow{p}_3),\ldots,(\overrightarrow{p}_{n-1},\overrightarrow{p}_n),(\overrightarrow{p}_n,\overrightarrow{p}_1)$$. Для отсечения такого многоугольника прямоугольным окном можно применить алгоритм, предложенный Сазерлендом и Ходжменом. Идея его заключается в последовательном отсечении части многоугольника прямыми, соответствующими сторонам окна. Результатом его работы является упорядоченный список вершин, лежащих в видимой части окна. На каждом шаге алгоритма образуется некоторая промежуточная фигура, также представленная упорядоченным списком вершин и ребер. Пример таких последовательных отсечений показан на рис. 5.9. В процессе отсечения последовательно обходится список вершин, причем каждая очередная точка за исключением первой рассматривается как конечная точка ребра, начальной точкой которого является предшествующая точка из списка. Порядок, в котором рассматриваются стороны окна, не имеет значения. В процессе обхода формируется список новых вершин многоугольника.
(рис 5.9) Последовательные шаги клиппирования произвольного многоугольникаНа первом шаге для первой вершины в списке определяется ее принадлежность видимой области. Если она видима, то она становится первой точкой первого обрабатываемого ребра и заносится в список новых вершин. Если же она невидима, то в список новых вершин не заносится, но все равно становится первой точкой ребра.
Для анализируемого ребра возможны четыре случая расположения относительно окна.
В этом алгоритме постоянно приходится определять видимость точки по отношению к конкретному ребру отсекающего окна. Окно также можно задать в виде упорядоченного списка вершин. Если обход вершин окна осуществляется по часовой стрелке, то его внутренняя область будет расположена по правую сторону от границы. При этом расположение точки $$\overrightarrow{p}$$ относительно прямой, которой принадлежит ребро, можно устанавливать различными способами:
Наиболее просто эти алгоритмы реализуются в случае отсечения прямоугольным окном со сторонами, параллельными осям координат.
В компьютерной графике часто приходится решать задачу выделения некоторой области изображаемой сцены, причем задача эта может решаться как в применении к плоской области (если сцена уже спроецирована на картинную плоскость), так и к трехмерной. Алгоритмы отсечения применяются для удаления невидимых поверхностей и линий, для построения теней, при формировании текстур. Отсекаемая область может быть как правильной формы (прямоугольник или параллелепипед со сторонами, параллельными осям координат или координатным плоскостям), так и неправильной (произвольный многоугольник или многогранник). Для того чтобы эти алгоритмы можно было использовать в задачах изображения динамичных сцен, они должны быть эффективными в отношении времени вычислений. Мы рассмотрим несколько наиболее часто применяемых алгоритмов.
Рассмотрим плоскую сцену, состоящую из отрезков различной длины и направлений, в которой надо выделить часть, находящуюся внутри прямоугольника. Прямоугольник задан списком ребер: <top>, <bottom>, <left>, <right>, отрезки также задаются координатами концевых точек. Область, отсекаемая окном (с учетом его границы), состоит из точек $$(x,y)$$, удовлетворяющих соотношениям$$x_l\le x\le x_r, \quad y_b\le y\le y_t.$$ Пусть концы отрезка заданы точками $$(x_1,y_1)$$ и $$(x_2,y_2)$$. Первый шаг алгоритма нацелен на то, чтобы выявить полностью видимые и полностью невидимые отрезки. Отрезок целиком принадлежит выделяемой (клиппируемой) области, если оба его конца удовлетворяют условиям (5.1).
(рис 5.1) Коды Сазерленда-Коэна для областейОтрезок полностью невидим, если оба его конца лежат
Во всех остальных случаях отрезок может (но не обязан) пересекать прямоугольное окно.
Для выполнения анализа полной видимости или невидимости отрезка А.Сазерленд и Д.Коэн предложили следующий алгоритм. Прямые, которым принадлежат ребра прямоугольника, разбивают плоскость на девять областей, каждой из которых присваивается четырехразрядный код. Каждый бит этого кода "отвечает" за одну из прямых: 1-й (старший) бит - за прямую $$t$$, 2-й - за прямую $$b$$, 3-й - за $$r$$, 4-й - за $$l$$. Если в коде области какой-либо бит установлен в 1, то это означает, что она отделена от окна соответствующей прямой. Схема идентификации областей приведена на рис. 5.1.
Концевым точкам отрезков сцены теперь можно присвоить коды в зависимости от расположения точек. Ясно, что если коды обоих концов отрезка равны нулю, то отрезок полностью лежит внутри окна. Для дальнейшего анализа воспользуемся операцией логического умножения кодов (поразрядное логическое "И"). Тогда таблица истинности для кодов, согласно схеме на рис. 5.1, будет выглядеть следующим образом:
| $$C_1$$ | $$C_2$$ | $$C_3$$ | $$C_4$$ | $$C_{13}$$ | $$C_{14}$$ | $$C_{23}$$ | $$C_{24}$$ | |
| $$C_1$$ | T | F | F | F | T | T | F | F |
| $$C_2$$ | F | T | F | F | F | F | T | T |
| $$C_3$$ | F | F | T | F | T | F | T | F |
| $$C_4$$ | F | F | F | T | F | T | F | T |
| $$C_{13}$$ | T | F | T | F | T | T | T | F |
| $$C_{14}$$ | T | F | F | T | T | T | F | T |
| $$C_{23}$$ | F | T | T | F | T | F | T | T |
| $$C_{24}$$ | F | T | F | T | F | T | T | T |
Из сопоставления таблицы с рисунком видно, что если произведение кодов концов отрезка принимает значение <True>, то отрезок целиком лежит по одну сторону какой-то из прямых, причем внешнюю сторону по отношению к окну, следовательно, он полностью невидим. Во всех остальных случаях отрезок может частично лежать внутри окна, поэтому для определения их видимой части надо решать задачу о пересечении отрезков с ребрами окна. При этом желательно по возможности сократить число перебираемых пар "отрезок-ребро".
В самом общем случае существуют две точки пересечения отрезка с ребрами, и эти две точки принимаются за новые концевые точки изображаемого отрезка. Но сначала можно выделить некоторые более простые частные случаи, поиск пересечений для которых является более эффективным. Прежде всего это горизонтальные и вертикальные отрезки, для которых поиск точки пересечения тривиален. Далее, если код одного из концов отрезка равен нулю, то существует только одно пересечение этого отрезка с ребром (или с двумя ребрами, если отрезок проходит через угловую точку окна). На рис. 5.2 приведена общая блок-схема алгоритма отсечения для одного произвольно направленного отрезка.
(рис 5.2) Блок-схема алгоритма Сазерленда-КоэнаВ блок-схеме используются следующие соглашения и обозначения:
GetCode(r) - определение кода точки;
Intersec0(r1,l) - поиск пересечения отрезка со сторонами окна при условии, что обе точки лежат вне окна; если пересечения нет, устанавливает переменную IsVisible в 0;
Intersec(r1,l) - поиск пересечения отрезка со сторонами окна при условии, что точка r1 лежит в окне;
C1, C2 - коды точек r1, r2.
В приведенном алгоритме теперь остается только детализовать функции Intersec0 и Intersec, эффективность работы которых является ключевым моментом. Рассмотрим один из методов поиска пересечений, который использует параметрическое уравнение прямой, проходящей через точки $$\overrightarrow{r}_1=(x_1,y_1), \; \overrightarrow{r}_2=(x_2,y_2)$$:$$\overrightarrow{r}=\overrightarrow{r}_1+s(\overrightarrow{r}_2-\overrightarrow{r_1}), \quad s\in[-\infty,+\infty],$$ или в координатном виде$$x=x_1+sl_x, \quad y=y_1+sl_y, \quad l_x=x_2-x_1, \quad l_y=y_2-y_1.$$ Попробуем определить точку пересечения отрезка с верхней границей окна. Поскольку эта граница описывается соотношениями$$L\le x\le R, \quad y=T,$$ то условие пересечения с ней клиппируемого отрезка выглядит следующим образом:$$s_T=\frac{T-y_1}{l_y}, \quad L\le x_1+s_T l_x \le R.$$
Аналогично выглядят формулы и для остальных границ окна. Если точка $$\overrightarrow{r}_1$$ расположена внутри окна, то, в зависимости от знака $$l_y$$, следует искать пересечение либо с верхней, либо с нижней границей окна. При отсутствии таковых отыскиваются пересечения с левой или правой стороной окна. Но прежде чем перебирать эти варианты, необходимо исключить случаи горизонтальных $$(l_y=0)$$ и вертикальных $$(l_x=0)$$ направлений отрезка. В первом случае точками пересечения с правой или левой границей (в зависимости от знака $$l_x$$ ) могут быть $$(L,y_1)$$ или $$(R,y_1)$$, а во втором - $$(x_1, B)$$ или $$(x_1,T)$$.
Этот алгоритм реализован в виде функции Intersec, блок-схема которой приведена на рис. 5.3.
Теперь рассмотрим случай, когда ни один из концов отрезка не лежит внутри окна. Здесь мы можем найти первую точку пересечения, заменить ею один из концов отрезка и использовать предыдущий алгоритм нахождения второй точки. Заметим, что в данном случае первый шаг не всегда кончается успешно, поскольку предварительный анализ не позволяет полностью исключить все невидимые отрезки. Как и в предыдущем алгоритме, сначала выполняется проверка на горизонтальное и вертикальное направления отрезка. Поскольку часть отрезков мы уже исключили из рассмотрения благодаря предварительному анализу, то для этих простых ситуаций остаются только две возможности, приведенные на рис. 5.4. Здесь точки пересечения определяются совершенно очевидным образом, причем сразу обе.
Затем последовательно рассматриваются четыре случая расположения точки $$\overrightarrow{r}_1$$ относительно прямых, ограничивающих окно. Если в каком-то из вариантов будет найдена точка пересечения, то анализ прекращается, точка $$\overrightarrow{r}_1$$ заменяется новой точкой и вызывается функция Intersec. В случае же, когда все четыре варианта не дали положительного результата, переменной IsVisible присваивается значение 0. Алгоритм реализуется функцией Intersec0 (блок-схема на рис. 5.5).
Предложенная реализация алгоритма отсечения не является единственной в своем роде. Существуют и другие подходы, в частности использование метода деления отрезка пополам для поиска точек пересечения и выявления видимой части отрезка. Такой вариант алгоритма был предложен Сазерлендом и Спрулом для аппаратной реализации, но он может быть реализован и на программном уровне, хотя при этом эффективность его будет ниже, чем у предыдущего. В нем нет прямого вычисления координат новой точки по явным алгебраическим соотношениям. Поиск осуществляется итерационным методом, в котором на каждом шаге для отрезка, "подозреваемого" в частичной видимости, находится его средняя точка, определяется ее код, затем из двух отрезков оставляются либо оба (если они оба не окажутся полностью невидимыми), либо только один, после чего операции продолжаются с новыми отрезками. Ситуация, когда дальнейшему дроблению подвергаются сразу два вновь полученных отрезка, может возникнуть только на первом итерационном шаге в тех случаях, когда исходный отрезок имеет две точки пересечения с границами окна. На последующих итерационных шагах количество анализируемых отрезков уже не будет увеличиваться. Процесс продолжается до тех пор, пока длина очередного отрезка не станет меньше наперед заданной точности. После этого найденная точка проверяется на предмет пересечения со стороной окна. На рис. 5.6 приведены три варианта отрезков, предварительный анализ которых не классифицирует их как полностью невидимые, и показан первый итерационный шаг. Отрезок a после первого деления дает два частично видимых отрезка, после чего ищутся две точки пересечения. В остальных случаях остается лишь один из двух отрезков, причем в случае отрезка c точка пересечения со стороной окна отсутствует, т.е. обнаруживается полная невидимость отрезка. По сути дела общий алгоритм, показанный на рис. 5.3, сохраняется, изменяется лишь метод поиска точки пересечения.
(рис 5.4) Блок-схема функции Intersec(рис 5.3) Отрезки параллельны сторонам окна(рис 5.6) Блок-схема функции Intrsec0(рис 5.5) Произвольное расположение отрезковВо многих задачах компьютерной графики часто приходится иметь дело с отсечением не только простым прямоугольным окном, но и окном достаточно произвольной геометрии. В частности, такие задачи могут возникнуть при использовании перспективных проекций трехмерных сцен, но не только в этих случаях. Поэтому актуальной является задача отсечения выпуклым многоугольником. Ясно, что простой анализ с помощью кодов Сазерленда-Коэна в такой ситуации неприменим. Здесь нужен надежный и достаточно эффективный алгоритм нахождения точки пересечения двух произвольно ориентированных отрезков, а также алгоритм определения местоположения точки относительно многоугольника (внутри, снаружи или на границе).
Рассмотрим задачу о пересечении отрезка с концами $$\overrightarrow{r}_1=(x_1,y_1), \; \overrightarrow{r}_2=(x_2,y_2)$$ с выпуклым
многоугольником, заданным списком ребер. Ребро может быть задано в
виде пары точек из множества вершин многоугольника $$R=(\overrightarrow{p},\overrightarrow{q}), \; \overrightarrow{p}=(p_x,p_y), \; \overrightarrow{q}=(q_x,q_y)$$ (рис. 5.7).
То обстоятельство, что многоугольник выпуклый, является очень
существенным: это позволяет использовать достаточно простой алгоритм,
использующий внутренние нормали к его сторонам. Под внутренней
нормалью понимается вектор, перпендикулярный стороне и направленный
внутрь многоугольника. Как и в предыдущем алгоритме, воспользуемся
параметрическим уравнением прямой, проходящей через концы отрезка: $$\overrightarrow{r}=\overrightarrow{r}_1+s(\overrightarrow{r}_2-\overrightarrow{r}_1)$$.
Если при некотором значении параметра $$s_0$$ эта прямая пересекается с
прямой, проходящей через точки $$\overrightarrow{p}, \overrightarrow{q}$$, то вектор, соединяющий
произвольную точку ребра с точкой $$\overrightarrow{r}_0=\overrightarrow{r}_1+s_0(\overrightarrow{r}_2-\overrightarrow{r}_1)$$, будет перпендикулярен вектору
нормали. Следовательно,
(рис 5.7) Пересечение отрезка многоугольникомКонечно, использование этой формулы предполагает, что $$d\equiv((\overrightarrow{r}_2-\overrightarrow{r}_1)\cdot\overrightarrow{n})\ne 0$$, т.е. что отрезок не параллелен стороне многоугольника, но этот случай рассматривается отдельно. Найденная точка принадлежит отрезку при условии $$0\le s_0\le 1$$. Условие принадлежности этой точки ребру многоугольника также можно выразить через скалярное произведение, так как векторы $$\overrightarrow{p}-\overrightarrow{r}_0$$ и $$\overrightarrow{r}_0-\overrightarrow{q}$$ в этом случае должны быть одинаково направленными, т.е. $$((\overrightarrow{p}-\overrightarrow{r}_0)\cdot(\overrightarrow{r}_0-\overrightarrow{q}))\ge 0$$.
Для каждого отрезка возможны три случая взаимного расположения с многоугольником:
В каждом из этих вариантов для нахождения пересечения отрезка с окном необходимо уметь определять принадлежность точки выпуклому многоугольнику. Из рис. 5.7 видно, что если для любой точки $$\overrightarrow{g}$$, принадлежащей многоугольнику (или его границе), и произвольной точки ребра $$\overrightarrow{f}$$ построить вектор $$\overrightarrow{m}=\overrightarrow{g}-\overrightarrow{f}$$, то выполняется условие $$(\overrightarrow{m}\cdot\overrightarrow{n}\ge 0)$$, поскольку угол между векторами не может превышать 90 $$\deg$$. Таким образом, если данное условие выполняется для всех ребер многоугольника, то точка является внутренней.
Таким образом, алгоритм отсечения отрезка начинается с анализа расположения концов отрезка по отношению к окну. Если обе точки лежат внутри окна, то отрезок полностью видимый, и дальнейший поиск прекращается. Если только одна из точек лежит внутри окна, то имеет место случай II, и предстоит найти одну точку пересечения. И, наконец, если обе точки лежат вне окна, то существуют либо две точки пересечения (отрезок пересекает две границы окна), либо ни одной (отрезок полностью невидим). Впрочем, две точки пересечения могут совпадать (если отрезок проходит через вершину многоугольника), но этот случай в дополнительном анализе не нуждается.
Далее выполняется цикл по всем ребрам многоугольника с целью нахождения точек пересечения. Для каждого ребра перед началом поиска пересечения необходимо проверить, не параллельно ли оно с отрезком. Если это так, то можно вычислить расстояние от одного из концов отрезка до прямой, проходящей через ребро $$d=((\overrightarrow{r}_1-\overrightarrow{p})\cdot\overrightarrow{n})$$. При $$d=0$$ отрезок лежит на прямой, и остается определить взаимное расположение концов отрезка и концов ребра, что можно сделать простым покоординатным сравнением. При $$d\ne 0$$ отрезок не имеет общих точек с данным ребром.
От задачи отсечения отрезков можно перейти к более сложной: клиппирование произвольных многоугольников. Если многоугольник невыпуклый, то в результате пересечения даже с прямоугольным окном может получиться несколько не связанных между собой фигур, как это показано на рис. 5.8.
(рис 5.8) Отсечение невыпуклого многоугольникаКогда стоит задача штрихования замкнутой области одновременно с задачей отсечения, то важно правильно определить принадлежность вновь полученных фигур внутренней или внешней части исходного многоугольника. Пусть исходный многоугольник задан упорядоченным списком вершин $$\{\overrightarrow{p}_1,\overrightarrow{p}_2,\ldots,\overrightarrow{p}_n$$, соответствующих ребрам $$(\overrightarrow{p}_1,\overrightarrow{p}_2),(\overrightarrow{p}_2,\overrightarrow{p}_3),\ldots,(\overrightarrow{p}_{n-1},\overrightarrow{p}_n),(\overrightarrow{p}_n,\overrightarrow{p}_1)$$. Для отсечения такого многоугольника прямоугольным окном можно применить алгоритм, предложенный Сазерлендом и Ходжменом. Идея его заключается в последовательном отсечении части многоугольника прямыми, соответствующими сторонам окна. Результатом его работы является упорядоченный список вершин, лежащих в видимой части окна. На каждом шаге алгоритма образуется некоторая промежуточная фигура, также представленная упорядоченным списком вершин и ребер. Пример таких последовательных отсечений показан на рис. 5.9. В процессе отсечения последовательно обходится список вершин, причем каждая очередная точка за исключением первой рассматривается как конечная точка ребра, начальной точкой которого является предшествующая точка из списка. Порядок, в котором рассматриваются стороны окна, не имеет значения. В процессе обхода формируется список новых вершин многоугольника.
(рис 5.9) Последовательные шаги клиппирования произвольного многоугольникаНа первом шаге для первой вершины в списке определяется ее принадлежность видимой области. Если она видима, то она становится первой точкой первого обрабатываемого ребра и заносится в список новых вершин. Если же она невидима, то в список новых вершин не заносится, но все равно становится первой точкой ребра.
Для анализируемого ребра возможны четыре случая расположения относительно окна.
В этом алгоритме постоянно приходится определять видимость точки по отношению к конкретному ребру отсекающего окна. Окно также можно задать в виде упорядоченного списка вершин. Если обход вершин окна осуществляется по часовой стрелке, то его внутренняя область будет расположена по правую сторону от границы. При этом расположение точки $$\overrightarrow{p}$$ относительно прямой, которой принадлежит ребро, можно устанавливать различными способами:
Наиболее просто эти алгоритмы реализуются в случае отсечения прямоугольным окном со сторонами, параллельными осям координат.
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.