29 30. Алгоритм Варнока (разбиение окнами). - p1xelse/CG GitHub Wiki

Алгоритм Варнока решает задачу удаление невидимых ребер и поверхностей в пространстве изображений.

Идея алгоритма

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

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

Простейший пример

Имеется прямоугольник и треугольник.

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

Для окна размером с экран не можем сказать что надо изобразить. Когда не можем дать ответ, то окно делим на части.

Вместо одного окна 4 окна меньших размеров.Задача не упростилась.

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

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

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

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

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

Для устранения лестничного эффекта можно продолжить деление на части, меньшие размера пикселя, и усреднить найденные характеристики. Например, в пикселе была найдена часть многоугольника. Разобьем пиксель на 4 части и выясним, что многоугольник лежит только в одной четверти (в прочих пусто). значит, необходимо закрасить пиксель с интенсивностью, равной 1/4.

Классификация многоугольников, рассматриваемых в алгоритме Варнока:

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

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

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

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

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

внутренний - габаритная проверка (с прямоугольной оболочкой)Многоугольник может быть и выпуклый и невыпулый. x_min >= x_left & x_max <= x_right & y_min >= y_down & y_max <= y_up Если с окном связан один многоугольник, то
внешний (не все) - габаритная проверка (с прямоугольной оболочкой) x_max < x_left || x_min > x_right | y_max < y_down | y_min > y_up этот тест не распознает внешние многоугольники, которые огибают окно (картинка)

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

сумма = 0: многоугольник внешний

сумма = +-360*n - охватывает окно.... n раз))) что бы это ни значило ( в Роджерсе пометка, что многоугольник без самопересечений может охватить только 1 раз)

при этом необязательна высокая точность вычислений. будет достаточно считать только целые октанты (углы по 45). для каждого ребра считаем разность номеров октантов, в которых лежат его концы (нумерация от 0 до 7, если получаем разность по модулю больше 4 - (a -= 8) или (a += 8)).

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

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

оптимизации

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