Трёхмерная компьютерная графика (стр. 6 из 12)
необходимо решать задачу о поиске точек пересечения сегментов текущей и предшествующей кривых.
Существует несколько методов получения точек пересечения кривых. На растровых дисплеях значение координаты x можно увеличивать на 1, начиная с xn или xm (рис. 3.6,а). Значение у, соответствующее текущему значению координаты х в пространстве изображения, получается путем добавления к значению у, соответствующему предыдущему значению координаты x, вертикального приращения Dy вдоль заданной кривой. Затем определяется видимостьновой точки с координатами (x + 1, y + Dy). Если эта точка видима, то активируется связанный с ней пиксел. Если невидима, то пиксел не активируется, а x увеличивается на 1. Этот процесс продолжается до тех пор, пока не встретится xn+k или xm+k. Пересечения для растровых дисплеев определяются изложенным методом с достаточной точностью. Близкий и даже более элегантный метод определения пересечений основан на двоичном поиске.
Точное значение точки пересечения двух прямолинейных отрезков, которые интерполируют текущую и предшествующую кривые, между точками (xn, yn) и (xn+k, yn+k ) (рис. 3.6) задается формулами:
где
а индексы cи p соответствуют текущей и предшествующей кривым. Полученный результат показан на рис. 3.6,b. Теперь алгоритм излагается более формально.
Если на текущей плоскости при некотором заданном значении x соответствующее значение y на кривой больше максимумаили меньше минимума по y для всех предыдущих кривых приэтом x, то текущая кривая видима. В противном случае онаневидима.
Если на участке от предыдущего (xn) до текущего (xn+k) значения x видимость кривой изменяется, то вычисляется точкапересечения (xi).
Если на участке от xn до xn+k сегмент кривой полностью видим, то он изображается целиком; если он стал невидимым, то изображается фрагмент от xn до xi; если же он стал видимым, то изображается фрагмент от xi до xn+k.
Заполнить массивы верхнего и нижнего плавающих горизонтов.
Изложенный алгоритм приводит к некоторым дефектам, когда кривая, лежащая в одной из более удаленных от точки наблюдения плоскостей, появляется слева или справа из-под множества кривых, лежащих в плоскостях, которые ближе к указанной точке наблюдения. Этот эффект продемонстрирован на рис. 3.7, где уже обработанные плоскости n - 1 и n расположены ближе к точке наблюдения. На рисунке показано, что получается при обработке плоскости n + 1. После обработки кривых n - 1 и n верхний горизонт для значений x = 0 и 1 равен начальному значению у; для значений x от 2 до 17 он равен ординатам кривой n; а для значений 18, 19, 20 - ординатам кривой n - 1. Нижний горизонт для значений x= 0 и 1 равен начальному значению у; для значений x = 2, 3, 4 – ординатамкривой n; а для значений x от 5 до 20 - ординатам кривой n - 1. При обработке текущей кривой (n + 1) алгоритм объявляет ее видимой при x = 4. Это показано сплошной линией на рис. 3.7.
3.7 Эффект зазубренного ребра
Аналогичный эффект возникает и справа при x = 18. Такой эффект приводит к появлению зазубренных боковых ребер. Проблема с зазубренностью боковых ребер решается включением в массивы верхнего и нижнего горизонтов ординат, соответствующих штриховым линиям на рис. 3.7. Это можно выполнить эффективно, создав ложные боковые ребра. Приведем алгоритм, реализующий эту идею для обеих ребер.
Обработка левого бокового ребра:
Если Pnявляется первой точкой на первой кривой, то запомним Pn в качестве Pn-1и закончим заполнение. В противном случае создадим ребро, соединяющее Pn и Pn-1.
Занесем в массивы верхнего и нижнего горизонтов ординаты этого ребра и запомним Pn в качестве Pn-1.
Обработка правого бокового ребра:
Если Pn является последней точкой на первой кривой, то запомним Pn в качестве Pn-1 и закончим заполнение. В противном случае создадим ребро, соединяющее Pn и Pn-1.
Занесем в массивы верхнего и нижнего горизонтов ординаты этого ребра и запомним Pn в качестве Pn-1.
Теперь полный алгоритм выглядит так:
Для каждой плоскости z = const.
Обработать левое боковое ребро.
Для каждой точки, лежащей на кривой из текущей плоскости:
Если при некотором заданном значении x соответствующее значение у на кривой больше максимума или меньше минимума по у для всех предыдущих кривых при этом x, то кривая видима (в этой точке). В противном случае она невидима.
Если на сегменте от предыдущего (xn) до текущего(xn+k)значения x видимость кривой изменяется, то вычисляется пересечение (xi).
Если на участке от xn до (xn+k) сегмент кривой полностью видим, то он изображается целиком; если он cтал невидимым, то изображается его кусок от xn до xi; если же он стал видимым, то изображается его кусок от xi до xn+k.
Заполнить массивы верхнего и нижнего плавающих горизонтов.
Обработать правое боковое ребро.
Если функция содержит очень острые участки (пики), то приведенный алгоритм может дать некорректные результаты. Во избежании этого если встречаются узкие участки, то функцию следует вычислять в большем числе точек.
3.8 Функция y = (1/5) sin x cos z - (3/2) cos (7a/4) * exp (-a), a = (x -p)2 + (z -p)2, изображённая в интервале (0, 2p) с помощью алгоритма плавающего горизонта
На рис. 3.8 показан типичный результат работы алгоритма плавающего горизонта. Запись этого алгоритма приводиться ниже.
Алгоритм плавающего горизонта
Гэкран – разрешение экрана в горизонтальном направлении
Вэкран – разрешение экрана в вертикальном направлении
Верх – массив, содержащий координаты верхнего горизонта
Низ – массив, содержащий координаты нижнего горизонта
Y – текущее значение функции y = f ( x, z ) при z = const
Тфлаг – флаг видимости для текущей точки
Пфлаг – флаг видимости для предыдущей точки, равный
0 = невидима
1 = видима и выше верхнего горизонта
-1 = видима и ниже нижнего горизонта
Draw – графическая команда, которая чертит видимую линию между точками, заданными их координатами.
Xmin, Xmax – минимальная и максимальная абсциссы функции
Xшаг – шаг приращения вдоль оси x
Zmin, Zmax – минимальная и максимальная аппликата функции
Zшаг – шаг между плоскостями z = const
Dimension Верх (Гэкран), Низ (Гэкран)
инициализация переменных
Xлевое = -1; Yлевое = -1; Xправое = -1; Yправое = -1
инициализация массивов горизонтов
Верх = 0
Низ = Вэкран
Вычисление функции на каждой плоскости z = const, начиная с ближайшей к наблюдателю плоскости Zmax
for z = Zmax to Zmin step- Zшаг
инициализация предыдущих значений по x и y:Xпред иYпред
Xпред = Xmin
Yпред = f (Xmin, z)
если используется видовое преобразование, то его нужно применить кXпред, Yпред, z в данной точке
обработка левого бокового ребра
callОбрребра (Xпред, Yпред, Xлев, Yлев; Верх, Низ)
call Видимость (Xпред, Yпред, Верх, Низ; Пфлаг)
для каждой точки на кривой, лежащей в плоскости z = const
for x = Xmin to Xmax step Xшаг
y = f (x, z)
если используется видовое преобразование, то его нужно применить к данной точке
проверка видимости текущей точки и заполнение соответствующего массива горизонта
callВидимость (x, y, Верх, Низ; Тфлаг)
ifТфлаг = Пфлаг then
if (Тфлаг = 1)or (Тфлаг = -1) then
Draw (Xпред, Yпред, x, y)
callГоризонт (Xпред, Yпред, x, y; Верх, Низ)
endif
если видимость изменилась, то вычисляется пересечение и заполняется массив горизонта
else
ifТфлаг = 0 then
ifПфлаг = 1 then
callПересечение (Xпред, Yпред, x, y, Верх; Xi, Yi)
else
callПересечение (Xпред, Yпред, x, y, Низ; Xi, Yi)
end if
Draw (Xпред, Yпред, Xi, Yi)
сallГоризонт (Xпред, Yпред, Xi, Yi, Верх, Низ)
else
ifТфлаг = 1 then
ifПфлаг = 0 then
callПересечение (Xпред, Yпред, x, y, Верх; Xi, Yi)
Draw (Xi, Yi, x, y)
сallГоризонт (Xi, Yi, x, y; Верх, Низ)
else
callПересечение (Xпред, Yпред, x, y, Низ; Xi, Yi)
Draw (Xпред, Yпред, Xi, Yi)
callГоризонт (Xпред, Yпред, Xi, Yi; Верх, Низ)
callПересечение (Xпред, Yпред, x, y, Верх; Xi, Yi)
Draw (Xi, Yi, x, y)
callГоризонт (Xi, Yi, x, y; Верх, Низ)
end if
else
ifПфлаг = 0 then
callПересечение (Xпред, Yпред, x, y, Верх; Xi, Yi)
Draw (Xi, Yi, x, y)
callГоризонт (Xi, Yi, x, y; Верх, Низ)
else
callПересечение (Xпред, Yпред, x, y, Верх; Xi, Yi)