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

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

F (x,y,z) = 0

Такие задачи возникают во многих приложениях математики, физики, техники и т.д. На основе этого алгоритма получаются так называемые каркасные или скелетные изображения трехмерного объекта на плоском (двумерном) экране. Впоследствии, эти изображения «обрастают плотью» при помощи алгоритмов закраски.

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

Рис. 1.1. Результат работы алгоритма плавающего горизонта при пересечении одной последовательностью секущих плоскостей

Данный метод заключается к сведению двумерной задачи к трехмерной путем пересечения исходной поверхности последовательностью параллельных секущих плоскостей, имеющих постоянные значения координат X, Y или Z. Пример для Z = const показан на рис. 1.3.

Рис. 1.2. Результат работы алгоритма плавающего горизонта при перекрестной штриховке

При этом, функция F(x,y,z) = 0 сводится к последовательности кривых, лежащих в каждой из параллельных секущих плоскостей. В случае Z = const на каждой из заданных параллельных секущих плоскостей это, функция:

y = f(x,z)

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

Если спроецировать полученные кривые на плоскость XY (Z = 0), (рис. 1.5), то мы получим «основу» для алгоритма плавающего горизонта.

Алгоритм сначала упорядочивает плоскости Z = const по возрастанию расстояния до них от точки наблюдения (предполагается, что она находится в бесконечности на оси Z). Затем для каждой плоскости, начиная с ближайшей к точке наблюдения, строится кривая, лежащая на ней, то есть для каждого X определяется Y. И алгоритм удаления невидимых линий и поверхностей заключается в следующем:

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

Рис. 1.3. Секущие плоскости с постоянной координатой

Рис. 1.4. Кривые в секущих плоскостях с постоянной координатой Z

Рис. 1.5. Проекция кривых на плоскость XY (z = 0)

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

Алгоритм работает, пока какая-нибудь из кривых не окажется ниже самой первой (рис. 1.6). Следовательно, «включаем» и нижний горизонт, который опускается вниз по ходу работы алгоритма (тонет). Нижний горизонт реализуется при помощи второго массива, который содержит минимальное значение Y для каждого значения X.

Рис. 1.6. Обработка нижней стороны проекции

Алгоритм прост и эффективен, однако, следует учесть и некоторые нестандартные ситуации.

Ранее предполагалось, что значение функции Y известно для всех значений X. Но, в некоторых приложениях, известны только несколько точек, а остальная функция «достраивается» c помощью линейной интерполяции. В данном случае, при изменении видимости не всегда возможно поддерживать правильные значения верхнего и нижнего горизонтов. На рис. 1.7, a кривая a – является «текущей» линией, а кривая b – «последующей». Причем, значения Y известны только в точках X = A, B, C, D и E, остальные значения получены с помощью линейной интерполяции.

Если операция по заполнению массивов горизонтов проводится после проверки видимости, то на участке от B до C кривая b объявляется невидимой, так как точка с координатой X = C невидима, а от D до E – видимой, так как точка с координатой X= E видима (рис. 1.7, б).

Следовательно, необходимо решать задачу поиска точек пересечения сегментов «текущей» и «последующей» кривых. Один из методов – добавлять единицу к значению X (то есть, брать следующую точку растра) и проверять видимость, другой - использовать метод деления пополам для нахождения точек пересечения.

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

Еще один нежелательный эффект – эффект зазубренного ребра, когда кривая, лежащая в одной из более удаленных от точки наблюдения плоскостей, появляется слева или справа из-под множества кривых, лежащих в плоскостях, которые ближе к указанной точке наблюдения. Пусть ранее были построены кривые a и b (рис. 1.9, а).

После обработки кривых верхний горизонт от точки x = A до точки x = C будет принадлежать кривой b и, далее, до точки x = D – кривой a. Нижний горизонт от точки x = A до точки x = B будет принадлежать кривой b и, далее, до точки x = D – кривой a. Необходимо определить видимость новой кривой c (рис. 1.9, б).

В данном случае, она объявляется видимой до точки B (ниже нижнего горизонта), от точки E до точки F и от точки C до точки G (выше верхнего горизонта). Однако, на самом деле участки от H до B и от C до I невидимы (рис. 1.9, в).

Следовательно, необходимо включить в массивы горизонтов значения Y для боковых ребер. Причем эти ребра можно не изображать (рис. 1.10а), а можно и изобразить (рис. 1.10, б).

Рис. 1.7. Эффект пересекающихся кривых при интерполяции значения функции

Рис. 1.8. Эффект «острых участков»

Рис. 1.9. Эффект зазубренного ребра

В приведенном выше алгоритме функция y = f(x,z) рассматривалась при z = const. Но, часто, удобнее вычерчивать кривые, полагая постоянными как z, так и x. При этом возникает, так называемый, эффект перекрестной штриховки (рис. 1.2). При этом это не наложение для двух плоскостей, а более сложный алгоритм. Более подробно о нем можно узнать в [1, 6].

Рис. 1.10. Устранение эффекта зазубренного ребра