Алгоритмы Варнака и Робертса

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

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

Алгоритм работает в пространстве изображения и анализирует область на экране дисплея (окно) на наличие в них видимых элементов. Если в окне нет изображения, то оно просто закрашивается фоном. Если же в окне имеется элемент, то проверяется достаточно ли он прост для визуализации. Если объект сложный, то окно разбивается на более мелкие, для каждого из которых выполняется тест на отсутствие и/или простоту изображения. Рекурсивный процесс разбиения может продолжаться до тех пор пока не будет достигнут предел разрешения экрана.

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

Рис: Соотношения между окном экрана (сплошная рамка) и многоугольником (штриховая рамка)

В четырех случаях можно сразу принять решение о правилах закраски области экрана:

 все многоугольники сцены - внешние по отношению к окну. В этом случае окно закрашивается фоном;

 имеется всего один внутренний или пересекающий многоугольник. В этом случае все окно закрашивается фоном и затем часть окна, соответствующая внутреннему или пересекающему окну закрашивается цветом многоугольника;

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

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

Алгоритм Аппеля (метод трассировки лучей)

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

1. Построим список контурных линий

2. Возьмем произвольную вершину, принадлежащую контурной линии.

3. Построим все выходящими из вершины ребра, образованные двумя лицевыми гранями.

4. Выберем из списка контурных линий ребро, выходящее из данной вершины

5. Определим количественную невидимость ребра

6. Если ребро не пересекается другими контурными линиями

   1. Если количественная невидимость равна 0, то строим ребро

   2. Переходим в конечную точку ребра.

   3. Переходим на п. 3

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

   1. Ищем точку пересечения с контурной линией

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

      1. Если она равна 0, то строим отрезок

      2. Иначе пропускаем отрезок

   3. Вычисли количественную невидимость отрезка после пересечения

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

      2. Иначе уменьшаем на 1

      3. Если количественная невидимость отрезка равна 0, то строим отрезок

   4. Перейдем в конечную точку ребра

   5. Переход на п.3