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

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

F(x,y,z) = 0

Поскольку в приложениях в основном интересуются описанием поверхности, этот алгоритм обычно работает в пространстве изображения. Главная идея данного метода заключается в свведении трехмерной задачи к двумерной путем пересечения исходной поверхности последовательностью параллельных секущих плоскостей, имеющих постоянные значения координат x, y или z. Например, если указанные параллельные плоскости определяются постоянными значениями z. Функция F(x,у,z) = 0 сводится к последовательности кривых, лежащих в каждой из этих параллельных плоскостей, например к последовательности y = f(x,z) или х = g(y,z), где z постоянно на каждой из заданных параллельных плоскостей.

Итак, поверхность теперь складывается из последовательности кривых, лежащих в каждой из этих плоскостей, как показано на рис. 4.2. Здесь предполагается, что полученные кривые являются однозначными функциями независимых переменных. Если спроецировать полученные кривые на плоскость z = 0, то сразу становится ясна идея алгоритма удаления невидимых участков исходной поверхности. Алгоритм сначала упорядочивает плоскости z = const по возрастанию расстояния до них от точки наблюдения. Затем для каждой плоскости, начиная с ближайшей к точке наблюдения, строится кривая, лежащая на ней, т. е. для каждого значения координаты х в пространстве изображения определяется соответствующее значение y. Алгоритм удаления невидимой линии заключается в следующем:

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

 

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

Алгоритм работает очень хорошо до тех пор, пока какая-нибудь очередная кривая не окажется ниже самой первой из кривых, как показано на рис. 4.3. Подобные кривые, естественно, видимы и представляют собой нижнюю сторону исходной поверхности, однако алгоритм будет считать их невидимыми. Нижняя сторона поверхности делается видимой, если модифицировать этот алгоритм, включив в него нижний горизонт, который опускается вниз по ходу работы алгоритма. Это реализуется при помощи второго массива, длина которого равна числу различимых точек по оси х в пространстве изображения. Этот массив содержит наименьшие значения y для каждого значения х. Алгоритм теперь становится таким:
Если на текущей плоскости при некотором заданном значении х соответствующее значение y на кривой больше максимума или меньше минимума по y для всех предыдущих кривых при этом х, то текущая кривая видима. В противном случае она невидима.

 

В изложенном алгоритме предполагается, что значение функции, т. е. y, известно для каждого значения х в пространстве изображения. Однако если для каждого значения х нельзя указать (вычислить) соответствующее ему значение y, то невозможно поддерживать массивы верхнего и нижнего плавающих горизонтов. В таком случае используется линейная интерполяция значений y между известными значениями для того, чтобы заполнить массивы верхнего и нижнего плавающих горизонтов. Если видимость кривой меняется, то метод с такой простой интерполяциеЙ не даст корректного результата. А это может повлечь за собой дополнительные нежелательные эффекты. Следовательно, необходимо решать задачу о поиске точек пересечения сегментов текущей и предшествующей кривых.