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

Используется чаще всего для удаления невидимых линий трехмерного представления функций, описывающих поверхности в виде:

.

Подобные функции возникают во многих приложениях в математике, технике, естественных науках.

Трехмерная задача сводится к двумерной путем пересечения исходной поверхности последовательностью параллельных секущих плоскостей, имеющих постоянные значения координат x, y или z.

Рис. 12.9

На рисунке показаны параллельные плоскости с . Функция сводится к последовательности кривых, лежащих в каждой из этих параллельных плоскостей, например, к последовательности:

,

где на каждой из заданных параллельных плоскостей.

Поверхность теперь складывается из последовательности кривых, лежащих в каждой из этих плоскостей (см. рис.).

Рис. 12.10

При проецировании кривых на плоскость z=0 (см. рис. 12.10) становится ясна идея алгоритма.

· В начале происходит упорядочивание плоскостей по возрастанию расстояния до них от точки наблюдения.

· Для каждой плоскости, начиная с ближайшей к точке наблюдения, строится кривая, лежащая на ней, то есть для каждого значения x в пространстве изображения определяется соответствующее y.

· Проверка: если на текущей плоскости при некотором значении x соответствующее значение y на кривой больше максимального или меньше минимального по y для всех предыдущих кривых при этом x, то текущая кривая видима, иначе — нет.

Рис. 12.11

Реализация алгоритма достаточна проста. Для хранения максимальных и минимальных значений y при каждом значении x используется два массива, длина которых равна разрешению по x. Значения в этих массивах представляют собой текущие значения верхнего и нижнего плавающего горизонта. По мере рисования каждой очередной кривой этот горизонт «всплывает».

Фактически этот алгоритм работает каждый раз с одной линией.

Алгоритм Робертса

Это математически элегантный алгоритм.

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

Трудоемкость — .

Это в сочетании с распространением растровых дисплеев привело к снижению интереса к этому алгоритму. Но математические методы, используемые в нем, просты, мощны и точны. В последующем введение предварительной сортировки по z снижает трудоемкость.

Необходимо, чтобы все изображаемые тела были выпуклыми. Невыпуклые тела разбиваются на выпуклые части. Выпуклое тело с плоскими гранями представляются набором пересекающихся плоскостей. Уравнение плоскости в пространстве:

.

В матричной форме: , или

— представляет собой плоскость.

Поэтому любое выпуклое тело можно выразить матрицей тела, состоящей из коэффициентов уравнений плоскостей:

.

Каждый столбец содержит коэффициенты одной плоскости. Любая точка пространства в однородных координатах:

.

Если точка S лежит на плоскости, то

.

Если точка S не лежит на плоскости, то знак этого скалярного произведения показывает по какую сторону от плоскости расположена точка. Если точка внутри тела — знак «+», если вне — «–».

Если точка S не лежит на плоскости, то знак этого скалярного произведения показывает по какую сторону от плоскости расположена точка (точка внутри тела — знак «+», точка вне тела — знак «–»).