Алгоритм плавающего горизонта применяется для визуализации явно заданных поверхностей. Поверхности задаются функциями вида: F(x, у, z) = 0. Подобные функции часто встречаются в математике, технике, естественных науках и других дисциплинах.
Алгоритм работает в пространстве изображения. Главная идея метода заключается в сведении трехмерной задачи к двумерной путем пересечения исходной поверхности последовательностью параллельных секущих плоскостей. Для удобства вычислений секущие плоскости берутся параллельными одной из плоскостей проходящих через координатные оси (x=0,y=0 или z=0). Уравнения сечений поверхности плоскостями получаются подстановкой соответствующих констант в уравнение поверхности. Пример, для случая секущих параллельных плоскости XOY, показан на рис. 8.3. Уравнения сечений определятся как F(x, у, C0+n*d) = 0 или y = f(x, C0+n*d), где C0 – константа, задающая первую секущую плоскость z=C0, n – номер секущей плоскости, а d-постоянный шаг по координате z между секущими.
Рисунок 8.3 Сечение поверхности набором плоскостей
Таким образом, поверхность теперь складывается из последовательности кривых, лежащих в каждой из секущих плоскостей. Предполагается, что полученные кривые являются однозначными функциями независимых переменных.
Рисунок 8.4 Проецирование сечений
Если спроецировать полученные кривые на плоскость z=0, как показано на рисунке 8.4, то сразу становится ясна идея алгоритма удаления невидимых участков исходной поверхности. Рассмотрим сечения по мере удаления их от наблюдателя. Очевидно, что если точка принадлежащая сечению с большим расположена ниже какой либо соответствующей (с такой же координатой X) точки сечений с меньшим номером, то эта точка не будет видна наблюдателю.
Алгоритм удаления невидимых линий для случая секущих плоскостей параллельных XOY сводится к следующим действиям:
Выбираем шаг между секущими плоскостями и их количество. Определяем координату Z для каждой плоскости.
Для каждой плоскости, начиная с ближайшей к точке наблюдения, строим лежащую на ней кривую. Выбираем шаг по координате X и для каждого значения координаты хi, в пространстве изображения, определяем соответствующее значение у.
Если на текущей плоскости при некотором заданном значении х соответствующее значение у на кривой больше значения у для всех предыдущих кривых при этом значении х, то текущая кривая видима в этой точке; в противном случае она невидима. Невидимые участки показаны пунктиром на рисунке 8.4.
Реализация данного алгоритма достаточно проста. Для хранения максимальных значений у при каждом значении х используется массив, количество элементов которого равно числу различимых точек сечения (разрешению) по оси х в пространстве изображения. Значения, хранящиеся в этом массиве, представляют собой текущие значения “горизонта”. В начале массив заполняется точками ближайшего к наблюдателю сечения. Если при рассмотрении последующих сечений встречается некоторая точка с координатой xj для которой yj больше значения хранимого в соответствующей ячейке массива, то данная точка видима и значения ее координаты у заносится в массив. Таким образом, при рассмотрении каждой очередной кривой горизонт “всплывает”. Фактически этот алгоритм удаления невидимых линий работает каждый раз с одной линией.
Алгоритм работает очень хорошо до тех пор, пока какая-нибудь очередная кривая не окажется ниже самой первой из кривых (сечений). Подобные кривые, естественно, видимы и представляют собой нижнюю сторону исходной поверхности, однако алгоритм будет считать их невидимыми.
Для устранения данного недостатка в алгоритм включается еще одна линия горизонта - «нижний горизонт», который опускается вниз по ходу работы алгоритма. Он также реализуется при помощи массива, длина которого равна числу различимых точек по оси х в пространстве изображения. Этот массив содержит наименьшие значения у для каждого значения х. В начале работы массив инициализируется точками ближайшего к наблюдателю сечения. Условие видимости точки становится следующим:
если на текущей плоскости при некотором заданном значении х соответствующее значение у на кривой больше максимума или меньше минимума по у для всех предыдущих кривых при этом х, то текущая кривая видима. В противном случае она невидима.