Удаление невидимых линий и поверхностей

Задача состоит в том, чтобы определить, какие части объектов, спроектированных на картинную плоскость (экран), будут видны, а какие – заслонены другими объектами. Методы различаются по следующим параметрам:

· Способу представления объектов (Brep, CSG)

· Способу визуализации сцены (каркасное или сплошное)

· Пространству, в котором проводится анализ видимости (объектное или картинная плоскость)

· Виду получаемого результата (непрерывный (участки ребер) или дискретный (пиксели))

Самый простой непрерывный метод удаления невидимых линий это перебор ребер всех объектов и сравнение их со всеми остальными объектами, такой алгоритм требует времени O(N²). Дискретные методы требуют времени O(CN), С – кол-во пикселей на экране (300 000).

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

· Когерентность в картинной плоскости, если данный пиксель соответствует определенной грани, то и соседние пиксели скорее всего соответствуют этой грани.

· Когерентность в объектном пространстве, если данный объект виден (невиден), то и соседние, скорее всего, видны (невидны).

· Когерентность во времени, если данный объект виден (невиден) на текущем кадре, то и на следующем кадре он, скорее всего, будет виден (невиден).

Алгоритм плавающего горизонта

Этот алгоритм применяют для удаления невидимых линий в параллельных проекциях графика функции двух переменных. Функция задана в виде Z=F(X,Y). Это может быть как аналитически заданная функция, так и любая другая (например, задана карта высот для некоторых точек, а промежуточные значения – получаются линейной интерполяцией).

Самый простой алгоритм рисования графика – выбрать некоторый шаг сетки вдоль осей X и Y, рассчитать точки для узлов такой сетки, и вывести их на экран. При этом, чтобы не было разрывов, можно выводить не точки, а отрезки между соседними узлами сетки. Можно заметить, что все отрезки в одном ряде узлов сетки вдоль оси OX будут лежать в одной вертикальной плоскости. Плоскости всех таких рядов будут параллельны, а значит, отрезок из более дальней от наблюдателя плоскости никогда не загородит отрезок из более близкой.

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

Алгоритм работает в картинной плоскости и является дискретным.

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

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

Void PP(x,y) { if (y<MinHor[x]) MinHor[x]=y; else

if (y>MaxHor[x]) MaxHor [x]=y; else return;... }