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

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

1. Определение полностью видимого отрезка:

если (X_a<X_л) (X_b>X_л) то переход к п.2;

если (X_b<X_л) (X_b>X_л) то переход к п.2;

если (Y_a<Y_н) (Y_a>Y_в) то переход к п.2;

если (Y_b<Y_н) (Y_b>Y_в) то переход к п.2;

иначе отрезок видим, переход к п.3.

2. Определение полностью невидимого отрезка:

если (X_a<X_л)(X_b<X_л) то переход к п.3 (отрезок невидим);

если (X_a>X_п)(X_b>X_п) то переход к п.3(отрезок невидим);

если (Y_a<Y_н) (Y_b<Y_в) то переход к п.3(отрезок невидим);

если (Y_a>Y_в) (Y_b>Y_в) то переход к п.3(отрезок невидим);

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

3. Конец.

Д.Коэн и А.Сазерленд предложили формализовать описанную процедуру. Для определения принадлежности точки одной из девяти областей, на которые разбивается плоскость продолжениями ребер отсекателя, вводится четырехразрядный (битовый) код (рис.3.6.2). Биты этого кода заполняются по следующему правилу

T₁ =1, если точка лежит левее окна, и 0 в противном случае;

T₂ =1, если точка лежит правее окна, и 0 в противном случае;

T₃ =1, если точка лежит ниже окна, и 0 в противном случае;

T₄ =1, если точка лежит выше окна, и 0 в противном случае.

Первым считается крайний правый бит.

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

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

Y=m(X-X₁)+Y₁ или Y=m(X-X₂)+Y₂, где (X₁,Y₁) и (X₂,Y₂) - координаты двух точек, через которые проходит отрезок, а m=(Y₂ - Y₁)/(X₂- X₁) - тангенс угла наклона отрезка.

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

В итоге координаты искомых точек пересечения отрезка с границами отсекателя находятся из следующих выражеий:

Y= m(X_л-X₁)+Y₁ , m (с левой границей)

Y= m(X_п-X₁)+Y₁ , m (с правой границей) (3.6.1)

X=(1/m)(Y_н-Y₁)+X₁ , m0 (с нижней границей)

X=(1/m)(Y_в-Y₁)+X₁ , m0 (с верхней границей).

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