Разбиение картинной плоскости

Разбиение картинной плоскости


На принципах разбиения картинной плоскости основан ряд алгоритмов. Этот прием используется и для улучшения работы других алгоритмов. Например, с помощью разбиения можно сократить количество проверок в алгоритме Робертса. Для этого картинная плоскость разбивается на равные клетки, для каждой клетки составляется список граней, проекции которых попадают в данную клетку. Для определения таких проекций они вписываются в прямоугольник, затем фиксируются клетки, занятые этим прямоугольником. Для произвольного ребра ищутся все клетки, ку¬да попадает проекция данного ребра. В итоге рассматриваются только грани, попавшие в список данных клеток.
Оценим выгоду. При прямом переборе оценка количества операций O(N2), при разбиении - O(N). Однако, требуется память для хранения информации о клетках, в которые попадает проекция ребра.
На этих же принципах основан алгоритм Варнака. Картинная плоскость разбивается на 4 равные части. При этом возможны следующие случаи:
• область пуста (в нее не попадает ни одной проекции), следовательно она закрашивается цветом фона;
• область целиком занята проекцией одной грани, следовательно она закрашивается цветом грани;
• не выполняется ни одно из вышеуказанных условий, область разбивается на части, анализ повторяется.
Очевидно, разбиение имеет смысл проводить до тех пор, пока размер области превышает один пиксел. Для части размером в 1 пиксел принимается специальное решение, например, закраска цветом ближайшей грани. Возможны и иные правила анализа активной области.
МЕТОДОД ДВОИЧНОГО РАЗБИЕНИЯ ПРОСТРАНСТВА

В основе - известный прием дихотомии (половинного деления). Пространство делится плоскостью на два полупространства. Далее используется исходная эвристика №2 (п. 6.5.1). Внутри каждого полупространства разбиение повторяется. Можно также секущую плоскость провес через произвольно выбранную грань (модификация алгоритма). Фактически строится двоичное дерево, узла! которого являются грани. Древовидные структуры достаточно легко программируются с помощью списков объектно-ориентированного подхода. Объект - грань, методы - различные виды прохода по дереву (получить следующий выше/нижележащий элемент, получить следующий элемент на том же уровне соседней ветви и т.д
Как выбрать грани для разбиения? Существует два основных критерия:
• получить как можно более сбалансированное дерево;
• минимизировать количество разбиений.
Эти критерии обычно являются взаимно исключающими, требуется компромисс.
Алгоритм работает в объектном пространстве. Его сильная сторона - независимость от положения центра проектирования (точки наблюдения). Одну и ту же сцену можно перерисовывать для разных точек наблюдение
К методам упорядочения относится также МЕТОД ПЛАВАЮЩЕГО ГОРИЗОНТА. В отличие от вышеизложенных, в этом методе сначала выводятся ближние к наблюдателю фрагменты. Пусть требуется получи каркасное изображение гладкой поверхности. Для изображения проекции ребра на картинную плоскость и пользуется растровый алгоритм, например, алгоритм Брезенхейма. При выводе очередной точки проекции видимость анализируется с учетом нижней и верхней границ уже полученной части изображения. Эти границы и зывают соответственно нижним и верхним плавающим горизонтом, т.к. в процессе работы алгоритма их пол жение меняется. Горизонты можно представить как 2 целочисленных массива. В процессе работы изображения достраивается вне области, где оно уже построено.