Это математический метод удаления линий в объектном пространстве. Алгоритм прежде всего удаляет из каждого тела те ребра или грани, которые экранируются самим телом. Затем каждое из видимых ребер каждого тела сравнивается с каждым из оставшихся тел для определения того, какая его часть или части, если таковые есть, экранируются этими телами. В связи с этим вычислительная трудоемкость алгоритма растет теоретически как квадрат числа объектов. Это в сочетании с ростом интереса к растровым дисплеям, работающим в пространстве изображения, привело к снижению интереса к алгоритму Робертса. Однако математические методы, используемые в этом алгоритме, просты, мощны и точны.
В алгоритме Робертса требуется, чтобы все изображаемые тела или объекты были выпуклыми. Невыпуклые тела должны быть разбиты на выпуклые части. Требования выпуклости являются принципиальным ограничением алгоритма Робертса.
Алгоритм Робертса делится на три этапа:
1) каждое тело анализируется индивидуально с целью удаления нелицевых (невидимых) плоскостей;
2) проверяется экранирование оставшихся в каждом теле ребер всеми другими телами с целью обнаружения их невидимых отрезков;
3) вычисляются отрезки, образующие новые ребра при протыкании телами друг друга.
В данном алгоритме предполагается, что тела состоят из плоских граней, которые в свою очередь состоят из ребер, а ребра - из отдельных вершин. Все вершины, ребра и грани связаны с конкретным телом.
Основные идеи, на которые опирается алгоритм Варнока, обладают большей общностью. Они основываются на гипотезе о способе обработки информации, содержащейся в сцене, глазом и мозгом человека. Эта гипотеза заключается в том, что тратится очень мало времени и усилий на обработку тех областей, которые содержат мало информации. Большая часть времени и труда затрачивается на области с высоким информационным содержимым. В алгоритме Варнока делается попытка извлечения преимущества из того факта, что большие области изображения однородны. Такое свойство известно, как когерентность, т.е. смежные области (пиксели) вдоль обеих осей x и y имею тенденцию к однородности.
Поскольку алгоритм Варнока нацелен на обработку картинки, он работает в пространстве изображения. В пространстве изображения рассматривается окно и решается вопрос о том, пусто ли окно, или его содержимое достаточно просто для визуализации. Если это не так, то окно разбивается на фрагменты до тех пор, пока содержимое подокна не станет достаточно простым для визуализации или его размер не достигнет требуемого предела разрешения.
Конкретная реализация алгоритма Варнока зависит от метода разбиения окна и от деталей критерия, используемого для того, чтобы решить, является ли содержимое окна достаточно простым. В оригинальной версии окно разбивалось на четыре одинаковых подокна. Существует несколько методов расположения элементов относительно окна.
Назовем многоугольник:
- внешним, если он находится целиком вне окна;
- внутренним, если внутри окна;
- пересекающим, если пересекает границу окна;
- охватывающим, если окно целиком внутри него.
Используя эти определения можно предложить следующие правила обработки окна, объединим их в алгоритм.
Для каждого окна:
- если все многоугольники являются внешними по отношению к окну, то это окно изображается с фоновой интенсивностью без дальнейшего разбиения;
- если внутри окна находится только один многоугольник, то площадь окна вне этого многоугольника заполняется фоновым значением интенсивности или цвета, а сам многоугольник заполняется соответствующим значением интенсивности или цвета;
- если только один многоугольник пересекает окно, то площадь окна вне многоугольника заполняется фоновым значением интенсивности или цвета, а та часть пересекающего многоугольника, которая попала внутрь окна, заполняется соответствующей ему значением интенсивности цвета;
- если окно охвачено только одним многоугольником, и если в окне нет других многоугольников, то окно заполняется значением интенсивности или цвета, соответствующему охватывающему многоугольнику;
- если найден по крайней мере один охватывающий многоугольник и если он расположен ближе других к точке наблюдения, то окно заполняется значением интенсивности или цвета, которые соответствуют охватывающему многоугольнику;
- в противном случае производится разбиение окна.
Первые четыре из этих критериев касаются ситуаций, в которых участвуют один многоугольник и окно. Они используются для сокращения числа разбиений. Пятое правило является ключом к решению задачи об удалении невидимых поверхностей. В нем идет речь о поиске такого охватывающего многоугольника, который находился бы ближе к точке наблюдения, чем все остальные многоугольники, связанные с этим окном. Очевидно, что этот многоугольник будет закрывать или экранировать все остальные многоугольники, связанные с окном. Поэтому в сцене будут фигурировать его визуальные характеристики.
6.4. Алгоритм Вейлера–Азертона
Вейлер и Азертон попытались минимизировать число шагов в алгоритме разбиения Варнока. Выходными данными этого алгоритма, который для достижения необходимой точности работает в пространстве объекта, служат многоугольники. Поэтому алгоритм можно легко использовать для удаления как невидимых линий, так и невидимых поверхностей. Алгоритм удаления невидимых линий состоит из четырех шагов:
1) предварительная сортировка по глубине;
2) отсечение по границе ближайшего к наблюдателю многоугольника, называемое сортировкой многоугольников на плоскости;
3) удаление многоугольников, экранированных многоугольником, ближайшим к точке наблюдения;
4) если требуется, то производится рекурсивное подразбиение и окончательная сортировка для устранение всех неопределенностей.
Предварительная сортировка по глубине нужна для формирования списка приблизительных приоритетов. Предположим, что точка наблюдения расположена в бесконечности на положительной полуоси z, тогда ближайшим к ней и первым в списке будет тот многоугольник, который обладает вершиной с максимальной координатой z.
В качестве отсекающего многоугольника используется копия первого многоугольника из предварительного списка приоритетов по глубине. Отсекаться будут остающиеся в этом списке многоугольники, включая 1-й многоугольник. Вводятся два списка: внутренний и внешний. С помощью алгоритма отсечения Вейлера–Азертона все многоугольники отсекаются по границам отсекающего многоугольника. Та часть каждого отсекаемого многоугольника, которая оказывается внутри отсекающего, если она имеется, попадает во внутренний список. Оставшаяся часть попадает во внешний список. Этот этап является сортировкой на плоскости или xy-сортировкой. Теперь сравниваются глубины каждого многоугольника из внутреннего списка с глубиной отсекающего многоугольника. С использованием координат (x,y) вершин отсекаемых многоугольников и уравнений несущих плоскостей вычисляются глубины (координаты z) каждой вершины. Затем они сравниваются с минимальной координатой z (zc min) для отсекающего многоугольника. Если глубина ни одной из этих вершин не будет больше zcmin, то все многоугольники из внутреннего списка экранируются отсекающим многоугольником. Эти многоугольники удаляются, и изображается внутренний список. Заметим, что во внутреннем списке остался лишь отсекающий многоугольник. Работа алгоритма затем продолжается с внешним списком. Если координата z какого-либо многоугольника из внутреннего списка окажется больше, чем zc min, то такой многоугольник по крайней мере частично экранирует отсекающий многоугольник. В подобном случае результат предварительной сортировки по глубине ошибочен. Поэтому алгоритм рекурсивно подразделяет плоскость (x,y), используя многоугольник, нарушивший порядок, в качестве нового отсекающего многоугольника. Отсечению подлежат многоугольники из внутреннего списка, причём старый отсекающий многоугольник теперь сам будет подвергнут отсечению новым отсекающим многоугольником. Подчеркнём, что новый отсекающий многоугольник является копией исходного многоугольника, а не его остатка после первого сечения.
