Алгоритм с сортировкой по глубине

Алгоритм плавающего горизонта для отрисовки поверхностей

Алгоритм Робертса для многогранников

Вход: векторная модель объектов и положение камеры.

Выход: набор отрезков, которые надо нарисовать - удаляются невидимые грани (в экранных координатах).

Алгоритм:

1 Изначально множество отрезков пустое.

2 Для каждой грани вычисляется нормаль (векторное произведение двух её сторон) и с её помощью определяем ориентацию грани (направлена к нам “лицом” или нет). Обходим точки в направлении по часовой стрелке.

3 Из рассмотрения удаляются грани, нормаль которых “отвернута” от камеры: если скалярное произведение нормали на направление камеры (n, (0,0,1)) > 0, то угол острый, и грань не видна.

4 Все видимые грани сортируются в порядке удаления от камеры.

5 В цикле рассматриваются грани с самой дальней до самой ближней: для каждой грани просматривается множество уже накопленных отрезков (алгоритмом двумерного отсечения):

a Если отрезок полностью внутри грани, то он удаляется из результирующего множества

b Если отрезок полностью вне грани, то он остается в результате.

c Если отрезок пересекается с гранью, то он удаляется из множества, но вместо него добавляется видимая часть

После этого все ребра грани добавляются в множество, и берется следующая грань.

Проблема в двойном цикле: из-за этого низкое быстродействие.

Алгоритм:

1 Инициализируются массивы y_max[x] и y_min[x].

2 Рисуется y = f(x, z_n) — это самая ближняя линия.

3 Цикл по z в порядке удаления от камеры

○ Цикл по x:

■ Вычисляется y = f(x, z) и проверяется:

● Если y > y_max[x], то изменяем y_max[x] и рисуем точку (x, y, z).

● Если y < y_min[x], то изменяем y_min[x] и рисуем точку (x, y, z).

● Иначе точка не рисуется

Главный недостаток алгоритма — его узкая специализированность.

Вход: векторная модель (параметры сцены, расположение камеры).

Выход: растр.

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

Недостатки:

● Низкая скорость, т. к. один и тот же пиксель перерисовывается несколько раз.

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