Алгоритм определения видимости ребер произвольного многогранника.

Алгоритм Аппеля.

Определение нелицевых граней.

Рассмотрим многогранник и решим задачу видимости аналогично задаче освещенности, рассмотренной ранее.

Если вектор нормали какой-то грани Ни составляет с Л, задающим направление проецирования тупой угол, то эта грань видна и называется лицевой.

При параллельном проецировании скалярное произведение (n,l)<=0

В случае когда угол - острый, грань не видна и не лицевая.

При центральном проецировании с центром в C вектор проецирования для точки P l = c-p (разность векторов)

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

Для выпуклого многогранника удаление невидимых граней решает задачу невидимых рёбер.

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

Удаление невидимых рёбер.

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

1) отбрасываются все рёбра обе образующие грани которых - нелицевые.

2) Проверяется каждое из оставшихся рёбер со всеми гранями многогранника на закрывание. Возможны 3 случая.

А - грань не закрывает ребро

Б - грань полностью закрывает ребро – ребро удалено из списка видимых

В - частично, разбиение на части видимые части ставятся на место прежнего ребра.

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

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

Каждая точка видима только тогда, когда её количественная невидимость =0.

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

Например: ABCC'D'DEE'A'A

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

А) Строится контурная линия

Б) Берётся вершина и определяется её количественная невидимость

В) Просматривается изменение количественной невидимости вдоль каждого из рёбер выходящего из этой точки. Рёбра проверяются на прохождение контурной линии и в соответствующих точках количественная невидимость изменяется. Те рёбра у которых кн=0 изображаются.

Г) Выполняется переход к следующей вершине и возврат к Б

Д) если ребро выходит из вершины, принадлежащей контурной линии, проверяется, не закрывается ли это ребро одной из граней (Дд")

Так как у реальных многогранников количество ребер в контурной линии намного меньше общего числа ребер то алгоритм Аппеля более эффективен, чем алгоритм Робертса.