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

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

.

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

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

Рис. 12.9

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

,

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

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

Рис. 12.10

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

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

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

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

Рис. 12.11

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

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