Двумерное отсечение

Отсекающие окна задаются левым (Л), правым (П), нижним (Н), верхним (В) двухмерными ребрами (рис. 10). Регулярным отсекающим окном является прямоугольник, стороны которого параллельны осям координат объектного пространства или осям координат экрана. Целью алгоритма отсечения является определение тех точек, отрезков или их частей, которые лежат внутри отсекающего окна. Эти точки, отрезки или их части остаются для визуализации. А все остальные отбрасываются.

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

Xл< =X< =Yп,

Yн< =Y< =Yв,

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

Отрезок лежит внутри окна и, следовательно, является видимым, если обе его концевые точки лежат внутри окна, например, отрезок ab на рис. 10. Если обе его концевые точки лежат справа, слева, выше, ниже окна, то этот отрезок лежит целиком вне окна, а значит невидим. Проверка последнего условия устранить все отрезки ij, но не устранит все отрезки gh и kL, которые видимы частично, либо полностью невидимы.

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

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