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

Алгоритм плавающего горизонта применяется для визуализации явно заданных поверхностей. Поверхности задаются функциями вида: F(x, у, z) = 0. Подобные функции часто встречаются в математике, технике, естественных науках и других дисциплинах.

Алгоритм работает в пространстве изображения. Главная идея метода заключается в сведении трехмерной задачи к двумерной путем пересечения исходной поверхности последовательностью параллельных секущих плоскостей. Для удобства вычислений секущие плоскости берутся параллельными одной из плоскостей проходящих через координатные оси (x=0,y=0 или z=0). Уравнения сечений поверхности плоскостями получаются подстановкой соответствующих констант в уравнение поверхности. Пример, для случая секущих параллельных плоскости XOY, показан на рис. 8.3. Уравнения сечений определятся как F(x, у, C₀+n*d) = 0 или y = f(x, C₀+n*d), где C₀ – константа, задающая первую секущую плоскость z=C₀, n – номер секущей плоскости, а d-постоянный шаг по координате z между секущими.

Рисунок 8.3 Сечение поверхности набором плоскостей

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

Рисунок 8.4 Проецирование сечений

Если спроецировать полученные кривые на плоскость z=0, как показано на рисунке 8.4, то сразу становится ясна идея алгоритма удаления невидимых участков исходной поверхности. Рассмотрим сечения по мере удаления их от наблюдателя. Очевидно, что если точка принадлежащая сечению с большим расположена ниже какой либо соответствующей (с такой же координатой X) точки сечений с меньшим номером, то эта точка не будет видна наблюдателю.

Алгоритм удаления невидимых линий для случая секущих плоскостей параллельных XOY сводится к следующим действиям:

Выбираем шаг между секущими плоскостями и их количество. Определяем координату Z для каждой плоскости.

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

Если на текущей плоскости при некотором заданном значении х соответствующее значение у на кривой больше значения у для всех предыдущих кривых при этом значении х, то текущая кривая видима в этой точке; в противном случае она невидима. Невидимые участки показаны пунктиром на рисунке 8.4.

Реализация данного алгоритма достаточно проста. Для хранения максимальных значений у при каждом значении х используется массив, количество элементов которого равно числу различимых точек сечения (разрешению) по оси х в пространстве изображения. Значения, хранящиеся в этом массиве, представляют собой текущие значения “горизонта”. В начале массив заполняется точками ближайшего к наблюдателю сечения. Если при рассмотрении последующих сечений встречается некоторая точка с координатой x_j для которой yj больше значения хранимого в соответствующей ячейке массива, то данная точка видима и значения ее координаты у заносится в массив. Таким образом, при рассмотрении каждой очередной кривой горизонт “всплывает”. Фактически этот алгоритм удаления невидимых линий работает каждый раз с одной линией.

Алгоритм работает очень хорошо до тех пор, пока какая-нибудь очередная кривая не окажется ниже самой первой из кривых (сечений). Подобные кривые, естественно, видимы и представляют собой нижнюю сторону исходной поверхности, однако алгоритм будет считать их невидимыми.

Для устранения данного недостатка в алгоритм включается еще одна линия горизонта - «нижний горизонт», который опускается вниз по ходу работы алгоритма. Он также реализуется при помощи массива, длина которого равна числу различимых точек по оси х в пространстве изображения. Этот массив содержит наименьшие значения у для каждого значения х. В начале работы массив инициализируется точками ближайшего к наблюдателю сечения. Условие видимости точки становится следующим:

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

Поиск по сайту: