Алгоритм отсечения Сазерленда-Коэна основан на разбиении отрезка.
В этом алгоритме отрезок разбивается сторонами окна. Каждая из пары получившихся частей отрезка сохраняется или отбрасывается в результате анализа кодов её концевых точек (рис.11). Если P1P2 разбивается левой стороной окна, то получается два новых отрезка – P1P1’ и P1’P2. Ключом к алгоритму Сазерленда-Коэна является информация о том, что одна из концевых точек отрезка лежит вне окна. Поэтому тот отрезок, который заключен между этой точкой и точкой пересечения, можно отвергнуть как невидимый. Фактически это означает замену исходной концевой точки на точку пересечения. Содержание алгоритма формулируется так.
Для каждой стороны окна выполнить:
- для каждого отрезка P1P2 определить, не является ли он полностью видимым или может быть тривиально отвергнут, как невидимый;
- если P1 вне окна, то продолжить выполнение, иначе поменять P1 и P2 местами;
- заменить P1 на точку пересечения отрезка P1P2 со стороной окна.
В предыдущем алгоритме требовалось вычислить пересечение отрезка со стороной окна. Можно избежать непосредственного вычисления, если реализовать двоичный поиск такого пересечения путем деления отрезка его средней точкой (рис.12). Алгоритм, основанный на этой идее и являющийся частным случаем алгоритма Сазерленда-Коэна, был предложен Спруллом и Сазерлендом для аппаратной реализации.
В алгоритме используются коды концевых точек отрезка и проверки, выявляющие полную видимость отрезков (a), и тривиально невидимых (b). Те отрезки, которые с помощью таких простых проверок нельзя отнести к одной из двух категорий (c, g, f), разбиваются на две равные части. Затем те же проверки применяются к каждой из половин до тех пор, пока не будет обнаружено пересечение со стороной окна или длина разделенного отрезка не станет пренебрежимо малой, т.е. пока он не выродится в точку. После вырождения определяется видимость полученной точки. В результате процесс обнаружения пересечения сводится к двоичному поиску. Данный алгоритм можно записать следующим образом.
Для каждой концевой точки отрезка:
- если концевая точка видима, то она будет наиболее удаленной видимой точкой. Процесс завершен. Иначе – продолжить;
- если отрезок тривиально характеризуется как невидимый, то выходная информация не формируется. Процесс завершен. Иначе – продолжить;
- грубо оценить наиболее удаленную видимую точку путем деления отрезка P1P2 средней точкой Pm. Применить вышеизложенные тесты к двум частям P1Pm и PmP2. Если PmP2 тривиально отвергается как невидимый, то средняя точка дает верхнюю оценку для наиболее удаленной видимой точки. Продолжить процедуру с отрезком P1Pm. Иначе - средняя точка дает оценку снизу для наиболее удаленной видимой точки. Продолжить процедуру с P2Pm. Если отрезок становится настолько мал, что его средняя точка совпадает с его концами с машинной или предельно заданной точностью, то надо оценить её видимость и закончить процесс.
В описанных выше алгоритмах предполагалось, что отсекающее окно является координатно-ориентированным прямоугольником. Однако во многих случаях окно не таково. Кирус и Бек предложили алгоритм отсечения окном произвольной выпуклой формы.
Прежде чем описывать алгоритм Кируса-Бека рассмотрим отсечение параметрически заданного отрезка прямоугольным окном. Параметрическое уравнение отрезка P1P2 имеет вид:
P(t)=P1+(P2– P1)t, 0≤t≤1, (1)
где t – параметр. Параметрическое описание отрезка не зависит от выбора системы координат. Это свойство делает параметрическое представление особенно полезным для определения пересечения отрезка со стороной произвольного выпуклого многоугольника.
В двумерной декартовой системе координат уравнение (1) сводится к паре одномерных параметрических уравнений вида:
0≤t≤1. (2)
x(t)=x1+(x2– x1)t,
y(t)=y1+(y2– y1)t,
В случае прямоугольного отсекающего окна одна из координат пересечения отрезка с каждой стороной известна. Необходимо вычислить только вторую координату. Из уравнения (1) получаем:
t=(P(t)–P1)/(P2– P1).
А из уравнения (2) следует, что значения t, соответствующие пересечениям со сторонами окна, равны:
- для левой стороны t=(xл–x1)/(x2–x1), 0≤t≤1,
- для правой стороны t=(xп–x1)/(x2–x1), 0≤t≤1,
- для нижней стороны t=(yн–y1)/(y2–y1), 0≤t≤1,
- для верхней стороны t=(yв–y1)/(y2–y1), 0≤t≤1.
Здесь через xл, xп, yн, yв обозначены координаты левой, правой, нижней и верхней сторон окна. Если решения этих уравнений дают значение t за пределами интервала 0≤t≤1, то такие решения отбрасываются, поскольку они соответствуют точкам, лежащим вне заданного отрезка.
5.5. Алгоритм Кируса–Бека
Для создания надежного алгоритма отсечения необходим хороший метод определения местоположения относительно окна (внутри, на границе, вне его) точки, принадлежащей отрезку. Для этой цели в алгоритме Кируса–Бека используется вектор нормали (рис.13).
Возьмем выпуклую отсекающую область R. Доказано, что внутренняя нормаль n в произвольной точке a, лежащей на границе R, удовлетворяет условию:
n(b–a)≥0, (3)
где b – любая точка на границе R, т.к. cos Q всегда положителен.
Возвращаясь к определению пересечения отрезка со стороной окна, вновь возьмем параметрическое представление отрезка P1P2 уравнением (1). Если f – граничная точка выпуклой области R, а n – внутренняя нормаль к одной из ограничивающих эту область плоскостей, то для любой конкретной величины t, т.е. для любой точки отрезка P1P2, из условия n(P(t)–f)<0 следует, что вектор P(t)–f направлен вовне области R. Из условия n(P(t)–f)<0 следует, что вектор P(t)–f принадлежит плоскости, которая проходит через f и перпендикулярна нормали. Из условия n(P(t)–f)>0 следует, что вектор направлен внутрь R. Из всех этих условий, взятых вместе, следует, что бесконечная прямая пересекает замкнутую выпуклую область в двух точках. Далее, пусть эти две точки не принадлежат одной граничной плоскости или ребру. Тогда уравнение n(P(t)–f)=0 имеет только одно решение. Если точка f лежит на той граничной плоскости или ребре, для которых n является внутренней нормалью, то точка на отрезке P(t) будет точка пересечения этого отрезка с указанной граничной плоскостью.
Таким образом запишем формализованный алгоритм Кируса–Бека:
P(t)=P1+(P2–P1)t, 0≤t≤1, (4)
ni(P(t)–fi), i=1, 2, 3,… (5)
Решение уравнения будет положительно, равно нулю или отрицательно - в зависимости от того, будет ли избранная точка отрезка лежать с внутренней стороны границы, на самой границе или с ее внешней стороны. Подстановка (4) в (5) дает условие пересечения отрезка с границей области:
ni(P1+(P2–P1)t–fi)=0 или ni(P1-fi) + ni(P2-P1)t = 0.
Вектор (P2–P1) определяет ориентацию отрезка, а вектор (P1–fi) пропорционален расстоянию от первого конца отрезка до избранной граничной точки. Обозначим через D=P2–P1 директрису или ориентацию отрезка, а через Wi=P1–fi - некий весовой множитель. Тогда получаем уравнение:
t(ni*D)+Wi*ni=0
Если Wi*ni<0, то эта точка вне окна. Если Wi*ni=0, то эта точка на границе. Если Wi*ni>0, то эта точка внутри окна. Последнее уравнение используется для получения значений t соответствующих пересечениям отрезка с каждой стороной окна. Если значение t лежит за пределом интервала 0≤t≤1, то оно игнорируется.
x(t)=x1+(x2– x1)t,
