12.6. Сравнительная характеристика алгоритмов
Таблица 12.1
Алгоритм |
Число граней |
||
100 |
2500 |
60000 |
|
Сортировка по глубине |
1 |
10 |
507 |
z-буфер |
54 |
54 |
54 |
Построчное сканирование |
5 |
21 |
100 |
Разбиение области |
11 |
64 |
307 |
12.7. Алгоритм плавающего горизонта
Используется чаще всего для удаления невидимых линий трехмерного представления функций, описывающих поверхности в виде:
.
Подобные функции возникают во многих приложениях в математике, технике, естественных науках.
Трехмерная задача сводится к двумерной путем пересечения исходной поверхности последовательностью параллельных секущих плоскостей, имеющих постоянные значения координат x, y или z.
Рис. 12.9
На
рисунке показаны параллельные плоскости
с
.
Функция
сводится к последовательности кривых,
лежащих в каждой из этих параллельных
плоскостей, например, к последовательности:
,
где на каждой из заданных параллельных плоскостей.
Поверхность теперь складывается из последовательности кривых, лежащих в каждой из этих плоскостей (см. рис.).
Рис. 12.10
При проецировании кривых на плоскость z=0 (см. рис. 12.10) становится ясна идея алгоритма.
В начале происходит упорядочивание плоскостей
по возрастанию расстояния до них от
точки наблюдения.Для каждой плоскости, начиная с ближайшей к точке наблюдения, строится кривая, лежащая на ней, то есть для каждого значения x в пространстве изображения определяется соответствующее y.
Проверка: если на текущей плоскости при некотором значении x соответствующее значение y на кривой больше максимального или меньше минимального по y для всех предыдущих кривых при этом x, то текущая кривая видима, иначе — нет.
Рис. 12.11
Реализация алгоритма достаточна проста. Для хранения максимальных и минимальных значений y при каждом значении x используется два массива, длина которых равна разрешению по x. Значения в этих массивах представляют собой текущие значения верхнего и нижнего плавающего горизонта. По мере рисования каждой очередной кривой этот горизонт «всплывает».
Фактически этот алгоритм работает каждый раз с одной линией.
12.8. Алгоритм Робертса
Это математически элегантный алгоритм.
Вначале удаляются из каждого тела те ребра или грани, которые экранируются самим телом. Затем каждое из видимых ребер каждого тела сравнивается с каждым из оставшихся тел для определения того, какая его часть или части экранируются этими телами.
Трудоемкость
—
.
Это в сочетании с распространением растровых дисплеев привело к снижению интереса к этому алгоритму. Но математические методы, используемые в нем, просты, мощны и точны. В последующем введение предварительной сортировки по z снижает трудоемкость.
Необходимо, чтобы все изображаемые тела были выпуклыми. Невыпуклые тела разбиваются на выпуклые части. Выпуклое тело с плоскими гранями представляются набором пересекающихся плоскостей. Уравнение плоскости в пространстве:
.
В
матричной форме:
,
или
— представляет
собой плоскость.
Поэтому любое выпуклое тело можно выразить матрицей тела, состоящей из коэффициентов уравнений плоскостей:
.
Каждый столбец содержит коэффициенты одной плоскости. Любая точка пространства в однородных координатах:
.
Если точка S лежит на плоскости, то
.
Если точка S не лежит на плоскости, то знак этого скалярного произведения показывает по какую сторону от плоскости расположена точка. Если точка внутри тела — знак «+», если вне — «–».
Если точка S не лежит на плоскости, то знак этого скалярного произведения показывает по какую сторону от плоскости расположена точка (точка внутри тела — знак «+», точка вне тела — знак «–»).