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

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

F(x, у, z) = 0

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

Главная идея данного метода заключается в сведении трехмерной задачи к двумерной путем пересечения ис­ходной поверхности последовательностью параллельных секущих плоскостей, имеющих постоянные значения координат х, у или z.

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

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

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

Итак, поверхность теперь складывается из последовательности кривых, лежащих в каж­дой из этих плоскостей, как показано на рис. 5.3. Здесь предполагается, что полученные кривые являются однозначными функциями не­зависимых переменных. Если спроецировать полученные кривые на плоскость z = 0, как показано на рис. 5.4, то сразу становится ясна идея алгоритма удаления невидимых участков исходной поверхности.

 

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

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

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

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

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

 

Рис. 4.5 Обработка нижней стороны поверхности

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

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

Полученный результат показан на рис. 5.5b.

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

Изложенный алгоритм приводит к некоторым дефектам, когда кривая, лежащая в одной из более удаленных от точки наблюдения плоскостей, появляется слева или справа из-под множества кривых, лежащих в плоскостях, которые ближе к указанной точке наблю­дения. Этот эффект продемонстрирован на рис. 5.6, где уже обработанные плоскости n-1 и n расположены ближе к точке наблюдения. На рисунке показано, что получается при обработке плоскости n+1. После обработки кривых n-1 и n верхний горизонт для значе­ний x = 0 и 1, равен начальному значению y; для значений x от 2 до 17 он равен ординатам кривой n; а для значений 18, 19, 20 - орди­натам кривой n-1. Нижний горизонт для значений x = 0 и 1 равен начальному значению y; для значений x = 2, 3, 4 - ординатам кривой n; а для значений x от 5 до 20 - ординатам кривой n-1. При обработке текущей кривой (n+1) алгоритм объявляет ее видимой при x = 4. Это показано сплошной линией на рис. 5.6. Аналогичный эффект воз­никает и справа при х = 18. Такой эффект приводит к появлению зазубренных боковых ребер. Проблема с зазуб­ренностью боковых ребер решается включением в массивы верхнего и нижнего горизонтов ординат, соответст­вующих штриховым линиям на рис. 5.6. Это можно выполнить эффективно, создав лож­ные боковые ребра.

 

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

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

На рис. 5.7 показан типичный результат работы алгоритма плавающего горизонта для функции y=(1/5)sin x cos z – (3/2) cos (7a/4) e^(-a), a = (x - p)²+(z - p)², в интервале (0, 2p).

Рис. 4.7 Результат работы алгоритма плавающего горизонта