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

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

F(x, у, z) = 0.

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

Рис. 7.2. Секущие плоскости Рис. 7.3. Плоские кривые в секущих плоскостях

 

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

у = f(x, z) или х = g (у, z),

где z постоянно на каждой из заданных параллельных плоскостей.

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

Рис. 7.4. Проекция кривых на плоскость XOY

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

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

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

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

Алгоритм Варнока

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

. В алгоритме Варнока каждое окно разбивалось на четыре одинаковых подокна.

На рис. 7.5. показан результат простейшей реализации алгоритма Варнока. Здесь окно, содержимое которого слишком сложно изображать, разбито на четыре одинаковых подокна. Окно, в котором что-то есть, подразбивается далее то тех пор, пока не будет достигнут предел разрешения экрана. На рис. 7.5, a показана сцена, состоящая из двух простых многоугольников. На рис. 7.5,b показан результат после удаления невидимых линий. Заметим, что горизонтальный прямоугольник частично экранирован вертикальным. На рис. 7.5., c и d показан процесс разбиения окон на экране с разрешением 256х256. Поскольку 256 = 2^{^8}, требуется не более восьми шагов разбиения для достижения предела разрешения экрана. Пусть подокна рассматриваются в следующем порядке: нижнее левое, нижнее правое, верхнее левое, верхнее правое. Будем обозначать подокна цифрой и буквой,' цифра – это номер шага разбиения, а буква – номер квадранта. Тогда для окна 1а подокна 2а, 4а, 4с, 5а, 5b оказываются пустыми и изображаются с фоновой интенсивностью в процессе разбиения. Первым подокном, содержимое которого не пусто на уровне пикселей, оказывается 8а. Теперь необходимо решить вопрос о том, какой алгоритм желательно применить: удаления невидимых линий или удаления невидимых поверхностей. Если желательно применить алгоритм удаления невидимых линий, то пиксель, соответствующий подокну 8а, активируется, поскольку через него проходят видимые ребра. В результате получается изображение видимых ребер многоугольников в виде последовательности точек размером с пиксель каждая (рис. 7.5., е).

Следующее рассмотрение окна, помеченного как 8d на рис. 7.5., d, лучше всего проиллюстрирует различие между реализациями алгоритмов удаления невидимых линий и поверхностей. В случае удаления невидимых линий окно 8d размером с пиксель не содержит ребер ни одного многоугольника сцены. Следовательно, оно объявляется пустым и изображается с фоновой интенсивностью или цветом. Для алгоритма удаления невидимых поверхностей проверяется охват этого окна каждым многоугольником сцены. Если такой охват обнаружен, то среди охватывающих пиксель многоугольников выбирается ближайший к точке наблюдения на направлении наблюдения, проходящем через данный пиксель. Проверка проводится относительно центра пикселя. Затем этот пиксель изображается с интенсивностью или цветом ближайшего многоугольника. Если охватывающие многоугольники не найдены, то окно размером с пиксель пусто. Поэтому оно изображается с фоновым цветом или интенсивностью. Окно 8d охвачено вертикальным прямоугольником. Поэтому оно изображается с цветом или интенсивностью этого многоугольника. Соответствующий результат показан на рис. 7.5., f.

Возвратившись к рассмотрению окна 8а на рис. 7.5., d, покажем, как включить в алгоритм удаления невидимых поверхностей устранение лестничного эффекта. Разбиение этого окна дает четыре подокна с размерами, меньшими, чем размеры пикселя. Только одно из этих подокон – правое верхнее – охвачено многоугольником. Три других пусты. Усреднение результатов для этих четырех подпикселей показывает, что окно 8а размером с пиксель нужно изображать с интенсивностью, равной одной четверти интенсивности прямоугольника. Аналогично пиксель 8Ь следует высвечивать с интенсивностью, равной половине интенсивности прямоугольника. Конечно, окна размером с пиксель можно разбивать более одного раза, чтобы произвести взвешенное усреднение характеристик.