Алгоритм плавающего горизонта для отрисовки поверхностей
Алгоритм Робертса для многогранников
Вход: векторная модель объектов и положение камеры.
Выход: набор отрезков, которые надо нарисовать - удаляются невидимые грани (в экранных координатах).
Алгоритм:
1 Изначально множество отрезков пустое.
2 Для каждой грани вычисляется нормаль (векторное произведение двух её сторон) и с её помощью определяем ориентацию грани (направлена к нам “лицом” или нет). Обходим точки в направлении по часовой стрелке.
3 Из рассмотрения удаляются грани, нормаль которых “отвернута” от камеры: если скалярное произведение нормали на направление камеры (n, (0,0,1)) > 0, то угол острый, и грань не видна.
4 Все видимые грани сортируются в порядке удаления от камеры.
5 В цикле рассматриваются грани с самой дальней до самой ближней: для каждой грани просматривается множество уже накопленных отрезков (алгоритмом двумерного отсечения):
a Если отрезок полностью внутри грани, то он удаляется из результирующего множества
b Если отрезок полностью вне грани, то он остается в результате.
c Если отрезок пересекается с гранью, то он удаляется из множества, но вместо него добавляется видимая часть
После этого все ребра грани добавляются в множество, и берется следующая грань.
Проблема в двойном цикле: из-за этого низкое быстродействие.
Алгоритм применяется для поверхностей, заданных уравнением y = f(x,z). Поверхность можно задать набором функций y(x) = f(x, zi), i=0..n. Создаются два массива: максимальных и минимальных значений y для каждого x.
Алгоритм:
1 Инициализируются массивы ymax[x] и ymin[x].
2 Рисуется y = f(x, zn) — это самая ближняя линия.
3 Цикл по z в порядке удаления от камеры
○ Цикл по x:
■ Вычисляется y = f(x, z) и проверяется:
● Если y > ymax[x], то изменяем ymax[x] и рисуем точку (x, y, z).
● Если y < ymin[x], то изменяем ymin[x] и рисуем точку (x, y, z).
● Иначе точка не рисуется
Главный недостаток алгоритма — его узкая специализированность.
Вход: векторная модель (параметры сцены, расположение камеры).
Выход: растр.
Для каждой грани вычисляется удалённость (Z). Все грани сортируются по убыванию, и начиная с самой дальней, они рисуются с закраской цветом.
Недостатки:
● Низкая скорость, т. к. один и тот же пиксель перерисовывается несколько раз.
● Иногда невозможно определить, какая грань ближе, а какая дальше (например, пересекающиеся грани будут отрисованы неверно).