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

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

F(x,y,z)=0,

часто встречаемых в математике, физике, технике.

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

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

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

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

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

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