13.2. Отсечение нелицевых граней

Рассмотрим многогранник, для каждой грани которого задан единичный вектор внешней нормали (рис. 13.2.1.). Несложно заметить, что если вектор нормали грани n составляет с вектором l, задающим направление проектирования, тупой угол (вектор нормали направлен от наблюдателя), то эта грань заведомо не может быть видна. Такие грани называются нелицевыми. Если соответствующий угол является острым, грань называется лицевой. При параллельном проектировании условие на угол, для того чтобы грань была видна, можно записать в виде неравенства (n, l) ≤ 0, поскольку направление проектирования от грани не зависит. При центральном проектировании с центром в точке с вектор проектирования для точки р будет равен l = с - р.

Для определения того, является заданная грань лицевой или нет, достаточно взять произвольную точку p этой грани и проверить выполнение условия (n, l) ≤ 0.

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

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

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

Рис. 13.2.1. Многогранник, с заданными для каждой грани, векторами l,n.

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

Ребра между нелицевыми гранями также всегда не видны. Однако ребро между лицевой и нелицевой гранями вполне может быть и видимым.

13.3. Алгоритм Робертса

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

Сначала отбрасываются все ребра, обе определяющие грани которых являются нелицевыми (ни одно из таких ребер заведомо не видно). Следующим шагом является проверка на закрывание каждого из оставшихся pебер со всеми лицевыми гранями многогранника. Возможны следующие случаи:

• грань ребра не закрывает (рис. 13.3.1 а);

Рис. 13.3.1 Варианты расположения ребра и грани.

• грань полностью закрывает ребро (тогда оно удаляется из списка рассматриваемых ребер) (рис. 13.3.1 б);

• грань частично закрывает ребро (в этом случае ребро разбивается на несколько частей, видимыми из которых являются не более двух; само ребро удаляется из списка, но в список проверенных ребер добавляются те его части, которые данной гранью не закрываются) (рис. 13.3.1 в).

Рассмотрим, как осуществляются эти проверки.

Пусть задано ребро АВ, где точка А имеет координаты (x_a, y_a), а точка В – (х_b, у_b).

Прямая, проходящая через отрезок АВ, задается уравнениями

причем сам отрезок соответствует значениям параметра

Данную прямую можно задать неявным образом как

где

.

Предположим, что проекция грани задается набором проекций вершин Р₁, ..., P_k с координатами (х_i,у_i), i = 1,...,n. Обозначим через F_i значение функции F в точке P_i и рассмотрим i-й отрезок проекции грани Р_i, Р_i+1. Этот отрезок пересекает прямую АВ тогда и только тогда, когда функция F принимает значения разных знаков на концах этого отрезка, а именно при

Случай, когда

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

Точка пересечения определяется соотношениями

где

Отсюда легко находится значение параметра t:

Возможны следующие случаи:

1. Отрезок не имеет пересечения с проекцией грани, кроме, быть может, одной точки. Это может иметь место, когда     • прямая АВ не пересекает ребра проекции (рис. 13.3.2, а);

• прямая АВ пересекает ребра проекций в двух точках t₁ и t₂, но либо t₁<0, t₂<0, либо t₁ > 1, t₂ > 1 (рис. 13.3.2, б);

• прямая АВ проходит через одну вершину, не задевая внутренности треугольника (рис. 13.3.2, в).

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

Рис. 13.3.2. Пример пересечения отрезка с проекциями граней.

2. Проекция ребра полностью содержится внутри проекции грани (рис. 13.3.3, а). Тогда есть две точки пересечения прямой АВ и границы грани и t₁ < 0 < 1 < t₂. Если грань, лежит ближе к картинной плоскости, чем ребро, то ребро полностью невидимо и удаляется.

3. Прямая АВ пересекает ребра проекции грани в двух точках и либо t₁< 0 ≤t₂ ≤ 1,  либо  0 < t₁ ≤ 1 < t₂ (рис. 13.3.3. б и в).

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

а)                      б)                                в)                                 г)

Рис. 13.3.3. Пример пересечения отрезка с проекциями граней.

4. Прямая АВ пересекает ребра проекции грани в двух точках, причем (рис. 13.3.3 г) 0 < t₁ < t₂ < 1.

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

Для определения того, что лежит ближе к картинной плоскости – отрезок АВ (проекция которого лежит в проекции грани) или сама грань, через эту грань проводится плоскость

 (n – нормальный вектор грани), разбивающая все пространство на два полупространства. Если оба конца отрезка АВ лежат в том же полупространстве, в котором находится и наблюдатель, то отрезок лежит ближе к грани; если оба конца находятся в другом полупространстве, то отрезок лежит дальше. Случай, когда концы лежат в разных полупространствах, здесь невозможен (это означало бы, что отрезок АВ пересекает внутреннюю часть грани).

Если общее количество граней равно n, то временные затраты для данного алгоритма составляют О(n²).

Количество проверок можно заметно сократить, если воспользоваться разбиением картинной плоскости.

Разобьем видимую часть картинной плоскости (экран) на N₁ · N₂ равных частей (клеток) и для каждой клетки А_ij построим список всех лицевых граней, чьи проекции имеют с данной клеткой непустое пересечение.

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

В качестве шага разбиения обычно выбирается О(l), где l – характерный размер ребра в сцене. Для любого ребра количество проверяемых граней практически не зависит от общего числа граней и совокупные временные затраты алгоритма на проверку пересечений составляют О(n), где n – количество ребер в сцене.

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