Отсечение невидимых частей объектов(Clipping)

мирового координатного пространства. Окно вывода (экран монитора, активное окно, вывод на

печать и т.п.) – область вывода на физическом устройстве

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

интерактивных графических приложений.
Поэтому как 2D, так и 3D алгоритмы отсечения реализуются аппаратными или микропрограммными средствами.

отсечения – определить те точки, отрезки (части отрезков), которые лежат

внутри окна вывода.
Эти точки, отрезки (части отрезков) остаются для визуализации, а все остальное отбрасывается.

физической системы координат. Например, осям координат экрана.

Некоторые из них полностью лежат внутри области экрана, другие целиком

вне ее, а некоторые пересекают границу экрана.
Алгоритм Сазерленда-Коэна позволяет найти полностью видимые и отсекать полностью невидимые отрезки.

код1 & код2 = 0000.
Тривиально невидимый - код1 & код2

≠ 0000.
Неопределенный - код1 ≠ 0000, код2 ≠ 0000,
код1 & код2 = 0000.
Алгоритм работает в пространстве изображений(растровый), т.к. важно свести задачу к двоичному виду(реализовано аппаратно или микропрограммно), а не к решению геометрической задачи поиска точки пересечения отрезков на основе системы линейных уравнений, X=x1 + t(x2-x1)
Y=y1 + t(y2-y1).

окно вывода, которые нельзя принять за видимые или полностью отбросить.
Последовательно

определяется средняя точка при делении отрезка пополам до тех пор, пока одна из частей отрезка не будет принята целиком(если есть пересечение), а другая часть – целиком отброшена.
Максимально необходимое число делений = максимальному числу двоичных разрядов, используемых для представления координат u и v.

границы окна вывода

объема являются:
Усеченная пирамида,
Прямоугольный параллелепипед.
Как и 2d отсечении, отрезки, которые полностью

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

координат, то нужно проявить осторожность, если при этом производится еще

и проецирование. Отрезок может «заворачиваться» в бесконечности так, что внутри видимого объема(если он не ограничен дальней плоскостью) будут видны сразу обе части отрезка.
Джим Блинн доказал, что отсечение всех отрезков до завершения процедуры перспективного проецирования(присутствует деление всех координат на на значение однородной координаты), удаляет части отрезков, которые «возвращаются» из бесконечности.
Лианг и Барский получили корректный результат отсечения отрезков в однородной системе координат, используя усеченную пирамиду видимости.
Доказано, что и к отсекающему объему, и к отрезку перед проецированием можно применить любое аффинное преобразование(т.е. повороты, переносы и т.п.)

можно рассматривать как набор отрезков.
Однако, если замкнутый многоугольник отсекается, как

набор отрезков, то части исходного объекта могут превратиться в один или более открытых многоугольников.
Если многоугольники являются сплошными областями(а не заштрихованными), то необходимо, чтобы замкнутость сохранялась и у результата. Например, отрезки (a,b) и (c,d) должны быть добавлены к описанию видимой части многоугольника.

b

a

d

c

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

многоугольников отсекается последовательно относительно одной прямой(одна из сторон окна видимости).
Исходный многоугольник задается списком вершин - P1, P2,…,Pn, который порождает список его ребер - P1 P2,…, Pn-1Pn, PnP1.
Этот алгоритм способен отсекать любой многоугольник, выпуклый\невыпуклый, плоский\неплоский, относительно окна видимости, являющегося выпуклым многоугольником.
Порядок отсечения
многоугольника разными сторонами
окна непринципиален.