Алгоритм Варнока

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

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

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

Назовем многоугольник:

- внешним, если он находится целиком вне окна;

- внутренним, если внутри окна;

- пересекающим, если пересекает границу окна;

- охватывающим, если окно целиком внутри него.

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

Для каждого окна:

- если все многоугольники являются внешними по отношению к окну, то это окно изображается с фоновой интенсивностью без дальнейшего разбиения;

- если внутри окна находится только один многоугольник, то площадь окна вне этого многоугольника заполняется фоновым значением интенсивности или цвета, а сам многоугольник заполняется соответствующим значением интенсивности или цвета;

- если только один многоугольник пересекает окно, то площадь окна вне многоугольника заполняется фоновым значением интенсивности или цвета, а та часть пересекающего многоугольника, которая попала внутрь окна, заполняется соответствующей ему значением интенсивности цвета;

- если окно охвачено только одним многоугольником, и если в

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

многоугольнику;

- если найден по крайней мере один охватывающий

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

- в противном случае производится разбиение окна.

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