5.6. Внутреннее и внешнее отсечение

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

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

5.7. Определение факта выпуклости многоугольника

Для работы с алгоритмом Кируса–Бека надо прежде всего убедиться, что окно является выпуклым, а потом вычислить внутренние нормали к каждой его стороне. Факт выпуклости или невыпуклости окна можно установить путем вычисления векторных произведений его смежных сторон (рис.14).

Выводы, которые можно сделать из анализов знаков этих произведений:

• все знаки равны нулю – многоугольник вырождается в отрезок;

• есть как положительные, так и отрицательные знаки – многоугольник не выпуклый;

• все знаки неотрицательные – многоугольник выпуклый, а внутренние нормали ориентированны влево от его контура;

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

5.8. Разбиение невыпуклых многоугольников

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

• для каждой i-й вершины многоугольника надо так ее перенести, чтобы она совпадала с началом координат;

• повернуть многоугольник относительно координат по часовой стрелке так, чтобы (i+1)-я его вершина оказалась на положительной полуоси x (рис.15);

• п роанализировать знак ординаты (i+2)-й вершины, если он неотрицателен, то многоугольник выпуклый в (i+1)-й вершине, если отрицательный – невыпуклый, разбить его;

• многоугольник разрезается вдоль положительной полуоси x, т.е. находятся все его такие стороны, которые пересекаются с осью x, образуется два новых многоугольника: один состоит из вершин лежащих выше оси x и ближайшей к началу координат точки пересечения с x>xi+1, второй – из вершин лежащих ниже оси x.

Когда после поворота его вершина V₂ совпадет с началом координат, V₃ ляжет на положительной оси x, знак ординаты V₄ будет отрицательным, значит многоугольник невыпуклый. Разрезание его осью x дает многоугольник V₃V₄V₅ ниже оси x и V₂V₅V₁ – выше оси x (рис.15).

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

5.9. Трехмерное отсечение

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

Как и при двумерном отсечении, отрезки, полностью видимые или тривиально невидимые, можно идентифицировать с использованием обобщения кодов концевых точек Коэна-Сазерленда. В трехмерном случае используется 6-битовый код. Самый правый бит кода – первый. В биты кода заносятся единицы с помощью обобщения двумерной процедуры:

• в первый бит, если конец ребра левее объема;

• во второй бит, если конец ребра правее объема;

• в третий бит, если конец ребра ниже объема;

• в четвертый бит, если конец ребра выше объема;

• в пятый бит, если конец ребра ближе объема;

• в шестой бит, если конец ребра дальше объема.

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

Поиск кодов точки пересечения относительно отсекающего прямоугольного параллелепипеда является прямым обобщением соответствующего двумерного алгоритма. Двумерный алгоритм разбиения средней точкой, рассмотренный ранее, непосредственно обобщается на случай трех измерений. При программной реализации этого алгоритма нужно изменить размерности массивов. В двухмерном варианте алгоритма Кируса-Бека на форму отсекателя не накладывалось никаких ограничений, за исключением выпуклости. Поэтому и в трехмерном варианте отсекатель может быть произвольным выпуклым объемом. Все векторы будут иметь по 3 компоненты (x,y,z).