КГ Лекция 09. Отсечение отрезка. Простой алгоритм отсечения.

Общие сведения об отсечении

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

Для отсечения необходимо знать:

• Геометрические характеристики отсекаемых объектов.
• Геометрические характеристики отсекателя.

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

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

Отсекатели:

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

Объекты:

• Видимый объект - объект, целиком лежащий в области.
• Невидимый объект - объект, не лежащий в области.
• Частично видимый объект - объект, частично лежащий в пределах отсекателя.

Применение:

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

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

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

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

Поскольку отсечение выполняется достаточно часто в машинной графике, то актуальным является вопрос обеспечения высокой эффективности работы этих алгоритмов. Часто большое количество исследуемых точек и отрезков реальной сцены лежит полностью в пределах окна или полностью за пределами окна. Поэтому желательно быстро определять такие точки и отрезки. Точки, лежащие целиком внутри окна, удовлетворяют условию Xл <= X <= Xп и Yн <= Y <= Yв, где (X,Y) - координаты точки. Считается, что точки, лежащие на границе окна, принадлежат внутренней области окна.

Здесь через Xл, Xп, Yв, Yн обозначены координаты X и Y левого и правого, верхнего и нижнего краев окна соответственно.

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

• отрезок ab лежит внутри отсекающего окна является видимым.
• отрезки cd, ef - частично видимые, не все концы отрезка лежат внутри
• отрезок gh - частично-видимый, хотя его оба конца не лежат внутри окна, т.е. необязательно лежит целиком вне окна
• отрезки ij - лежат только либо справа, слева, выше или ниже окна, то отрезки целиком вне окна => невидимые
• отрезок kl - лежит и справа и сверху, и является тоже невидимым

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

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

AB - какой-то отрезок => A(Xa, Ya), B(Xb, Yb)
1. Определение полностью видимости отрезка:
   если (Xa < Xлев) or (Xb > Xправ) то переход п.2;
   если (Xb < Xлев) or (Xa > Xправ) то переход п.2;
   если (Ya < Yниз) or (Yb > Yвверх) то переход п.2;
   если (Yb < Yниз) or (Ya > Yвверх) то переход п.2;
   иначе отрезок видим, переходим к п.3.
2. Определение полностью невидимости отрезка:
   если (Xa < Xлев) and (Xb < Xлев) то переход п.3;
   если (Xa > Xправ) and (Xb > Xправ) то переход п.3;
   если (Ya < Yниз) and (Yb < Yниз) то переход п.3;
   если (Yb > Yвверх) and (Ya > Yвверх) то переход п.3;
   иначе отрезок частично видим или является невидимым
   (требуется дополнительный анализ, т.е. определить пересечения отрезка с окном).
3. Конец

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

Выше тесты видимости или невидимости отрезков можно формировать, используя метод Д.Коэна и А.Сазерленда. В этом методе для определения принадлежности ребра той из девяти областей вводится четырех разрядный (битовый) код. Коды этих областей:

Биты этого кода заполняются по следующему правилу (первым считается крайний правый бит):

• T1 = 1, если точка лежит левее окна X < Xлeв, и 0 в противном случае;
• T2 = 1, если точка лежит правее окна X > Xправ, и 0 в противном случае;
• T3 = 1, если точка лежит ниже окна Y < Yниз, и 0 в противном случае;
• T4 = 1, если точка лежит выше окна Y > Yвверх, и 0 в противном случае;

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

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

Пример:

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

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

Точки пересечения этой прямой со сторонами кона имеют следующие координаты:

Y = m*(Xл - X1) + Y1  , m != inf       (с левой границей, Xл)
Y = m*(Xп - X1) + Y1  , m != inf       (с правой границей, Xп)                                   
X =(1 / m)*(Yн - Y1) + X1  , m != 0    (с нижней границей, Yн)
X =(1 / m)*(Yв - Y1) + X1  , m != 0    (с верхней границей, Yв).

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

Простой алгоритм отсечения отрезка

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

1. Ввод координат отсекателя Xл, Xп, Yн, Yв.
2. Ввод координат концов P1(X1, Y1), P2(X2, Y2)
3. Вычисление кодов концов отрезка T1, T2.
   Вычисление сумм концов концов отрезка S1, S2.
4. Установка признака видимости отрезка pr=1 (pr=1 отрезок видимый, pr=-1 - невидимый)
5. Задание начального значения тангенса угла наклона отрезка m=10^30 
   (большое число, вначале предполагается, что отрезок вертикальный).
6. Проверка полной видимости отрезка:
   если (S1 == 0)&(S2 == 0) == истина, то отрезок видимый;
    выполняется в этом случае следующие действия:
    - занесение в результат координат концов отрезка R1 = P1
                                                     R2 = P2
    - переход к п.31
7. Вычисление логического произведения кодов конца отрезка PL
8. Проверка тривиальной невидимости отрезка:  
   если PL != 0, то отрезок невидим. 
   - В этом случае установка признака pr = -1
   - переход к п. 31.
9. Проверка видимости первого конца отрезка:
   если S1 == 0 (первый конец видим), то выполнение следующих действий: 
   - R1 = P1 (занесение  этой вершины в результат), 
   - Q = P2 (занесение координат другой вершины в рабочую переменную Q), 
   - i = 2 (номер шага отсечения), 
   - переход к п.15.
10. Проверка видимости первого конца отрезка:
    если S2 == 0 (второй конец видим), то выполнение следующих действий: 
    - R1 = P2 (занесение  этой вершины в результат), 
    - Q = P1 (занесение координат другой вершины в рабочую переменную Q), 
    - i = 2 (номер шага отсечения), 
    - переход к п.15.
11. Установка начального значения шага отсечения i = 0.
12. Вычисление текущего номера шага отсечения i = i + 1.
13. Проверка завершения процедуры отсечения: 
    если i > 2, то переход к п.31.
14. Занесение  в  рабочую  переменную  Q координат i-ой вершины Q = Pi.
15. Определение   расположения   отрезка:   
    если  X2 == X1 (отрезок вертикальный),  то переход к п.23  
    (не  может  быть пересечения с левой и правой границами отсекателя).
16. Вычисление тангенса угла наклона отрезка: m = (Y2 - Y1)/(X2 - X1).
17. Проверка возможности пересечения с  левой  границей отсекателя: 
    если Qx > Xл (пересечения нет), то переход к п.20.
18. Вычисление  ординаты  точки  пересечения отрезка с левой границей отсекателя: 
    Yр = m*(Xл - Qx) + Qy.
19. Проверка корректности найденного пересечения: 
    если (Yр >= Yн)&(Yp <= Yв) == истина (пересечение корректное), то выполнение следующих действий:  
    - Ri..x = Xл,
    - Ri..y = Yр (занесение полученных координат в результат), 
    - переход к п.12.
20. Проверка возможности пересечения отрезка  с  правой границей отсекателя:
    если  Qx < Xп (пересечения  нет),  то переход к п.23.
21. Вычисление  ординаты  точки  пересечения  с  правой границей: 
    Yр = m*(Xп - Qx) + Qy.
22. Проверка корректности найденного пересечения:  
    если  (Yр >= Yн)& (Yр <= Yв) == истина  (пересечение корректно),  то выполнение следующих действий:
    - Ri.x = Xп, ( занесение полученных координат в  результат ),  
    - переход  к п.12.
23. Проверка  горизонтальности  отрезка:  
    если m == 0,  то переход к п.12.
24. Проверка возможности пересечения с верхней границей отсекателя: 
    если Qy < Yв (пересечения нет), то переход к п.27.
25. Вычисление  абсциссы  точки  пересечения  с верхней границей: 
    Xр = (Yв - Qy)/m + Qx.
26. Проверка корректности найденного пересечения: 
    если (Xр >= Xл)&(Xр <= Xп) == истина  (пересечение  корректно),  то выполнение следующих действий:  
    - Ri.x = Xр;  
    - Ri.y = Yв  (занесение полученных координат в результат); 
    - переход к п. 12.
27. Проверка возможности пересечения с нижней  границей отсекателя: 
    если  Qx > Yн (пересечения нет),  то переход к п. 30 (вершина невидима  и  ни  одно  пересечение  не  является корректным, следовательно, отрезок невидим).
28. Вычисление  абсциссы  точки  пересечения  с  нижней границей: 
    Xр = (Yн - Qy)/m + Qx. 
29. Проверка корректности найденного пересечения: 
    (Xр >= Xл)&(Xр <= Xп) == истина  (пересечение  корректно), то выполнение следующих действий: 
    - Ri.x = Xр;  
    - Ri.y = Yв (занесение полученных координат в результат); 
    - переход к п. 12.
30. Установка признака видимости pr= -1 (отрезок невидим полностью, так как ни одно пересечение не оказалось корректным).
31. Проверка признака видимости:   
    если pr=1, то вычерчивание отрезка R1R2.
32. Конец.

Диаграмма (Курова)

Вопросы

Как в простом алгоритме определяется невидимость отрезков? (объяснить на примере)

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

В каком случае ищется пересечение с очередной границей отсекателя?

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

Надо ли особым образом обрабатывать вертикальные и горизонтальные отрезки?

Вертикальные отрезки требуют особой обработки при поиске точек пересечения с отсекателем. Если отрезок невертикальный: при поиске точек пересечения используется тангенс угла наклона прямой, содержащей отрезок. Если отрезок вертикальный: при таком же подходе получим деление на ноль при вычислении тангенса угла наклона. Поэтому проверяем отрезок на вертикальность перед вычислением тангенса угла наклона, и если отрезок вертикальный - находим точки пересечения с верхней и нижней границами отсекателя как (x_отр, y_верх) и (x_отр, y_низ). Горизонтальные отрезки не требуют особого подхода.

Если суммы кодов концов отрезка отличны от нуля, какой вывод о расположении отрезка можно сделать?

В таком случае отрезок может быть частично видимым, или вообще не видимым, как в примерах выше

Чем данный алгоритм отличается от алгоритма Сазерленда-Коэна?

В простом алгоритме после нахождения точки пересечения отрезка с границей отсекателя проводится проверка на корректность найденного пересечения. Если пересечение корректно, то считается, что одна точка видимой части отрезка найдена и дальше надо находить вторую точку видимой части отрезка.

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

В чем различие простого от средней точки?

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