5. Отсечение

Отсечение – процесс выделения некоторой части базы данных, играет важную роль в задачах машинной графики. Алгоритмы отсечения бывают двух- и трёхмерными. Они могут быть реализованы аппаратно или программно. Алгоритмы отсечения, реализованные программно, часто оказываются недостаточно быстродействующими для приложений, ориентированных на процессы, протекающие в реальном времени.

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

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

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

X_лXX_п,

Y_нYY_в.

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

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

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

Простой алгоритм определения видимости

a, b – конечные точки отрезка в координатном пространстве (X, Y)

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

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

if X_а<X_Л or X_а>X_П then 1

if X_b<X_Л or X_b>X_П then 1

if Y_a<Y_Н or Y_a>Y_В then 1

if Y_b<Y_Н or Y_b>Y_В then 1

отрезок полностью видимый

визуализировать отрезок

goto 3

проверить полную невидимость отрезка

если оба конца отрезка лежат слева, справа, сверху или снизу от окна, то факт невидимости отрезка подтверждается

1) if X_а<X_Л and X_b<X_Л then 2

if X_a>X_П and X_b>X_П then 2

if Y_a>Y_В and Y_b>Y_В then 2

if Y_a<Y_Н and Y_b<Y_Н then 2

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

определить пересечения отрезка с окном

2) отрезок невидим

3) переход к следующему отрезку

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