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

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

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

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

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

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

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

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

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