29. Удаление невидимых линий и поверхностей в пространстве изображений. Алгоритм Варнока (разбиение окнами): последовательность действий и основные принципы.

• Работает в пространстве изображений

Основная идея алгоритма Варнока:

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

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

Не существой единой версии алгоритма

Пример

Нужно изобразить те элементы, которые являются видимыми.

Суть в том, что мы будем делить окно до того момента, пока не сможем точно сказать что хотим изобразить.

Отсекатель - окно. Закрашиваем вершину многоугольника.

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

В более сложных версиях, ставится задача определения что изображать в очередном окне > 1 пикселя.
Может работать как с ребрами, так и с поверхностями. Самый простой вариант делить на 4 прямоугольных окна.

Можно устранить лестничный эффект! Продолжаем делить на части, меньшее пикселя и усреднить найденные характеристики.

Классификация многоугольников

Способы расположения многоугольников относительно окна

• Внешний - целиком вне окна
• Внутренний - целиком внутри окна
• Пересекающий - пересекает границу окна
• Охватывающий - окно находится целиком внутри многоугольника
• С окном связано несколько многоугольников

Правила обработки окна

1. Если все многоугольники сцены являются внешними: окно закрасить цветом фона
2. Если внутри окна только один многоугольник: площадь окна вне него заполняется фоновым цветом, а сам многоугольник - своим цветом (растровая развертка).
3. Если многоугольник, связанный с окном, является пересекающим – отсечение по границе окна и п. 2
4. Если окно охвачено ровно одним многоугольником: залить окно цветом многоугольника
5. Если с окном связано несколько многоугольников, но ближе всех прочих к наблюдателю расположен охватывающий: заполнить окно цветом охватывающего многоугольника

Методы определения

• Внутренний - габаритная проверка. Многоугольник может быть любой.
• Внешнний (не для всех) - габаритная проверка. Не распознает огибающие окна.

• Тест на пересечение. Посдтавляем все вершины окна во всех уравнения прямых, задающих ребра многоугольника. Если знак пробной функции не зависит от выбора вершины окна - значит нет точек пересечения. Если пересечение возможно, находится проверяется принадлежность (РЕБРУ, а не продолжению!)

• Бесконечная прямая. Проводим луч из любой точки окна, считаем количество пересечений. Если четное - внешний, иначе - охватывающий. Если луч проходит через вершину многоугольника: считаем касание как 2 пересечения, протыкание как одно.

• Подсчет угла. Обход по ребрам многоугольника. Суммируем углы, образованные лучами (в лююбой точке окна можно начать их) и проходящими через концы ребер. Если сумма = 0 - внешний. Сумма = +- 360 * n охватывает окно n раз. (эксперты уточните)

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

Сумма разностей октантов = 0 - внешний, +- 8n - охватывающий.

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

Возможные оптимизации

• Сортировка многоугольнико по z
• Хранение информации. Например если для окна данный многоугольник охватывающий - запомнить и не проверять на подокнах (подонках).
• Списки охватывающих, пересекающих и внутренних (запоминаем на каком уровне они появились, для обхода по дереву окон пригодится)

Следующий вопрос: 30. Типы многоугольников, анализируемых в алгоритме Варнока. Методы их идентификации.

Предыдущий вопрос: 28. Алгоритм Робертса. Удаление отрезков, экранируемых другими телами.