24. Алгоритм плавающего горизонта. - p1xelse/CG GitHub Wiki
-
Поверхность задаётся уравнением F(x, y, z) = 0 (или аналогичным y = f(x, z)).
-
Поверхность рассекается плоскостями, перпендикулярными OZ. В каждом сечении получается кривая вида y = f(x, z = const) или x = q(y, z = const)
-
Полученные кривые можно спроектировать на плоскость XOY, изображая видимые части каждой прямой
-
Изображение нужно строить, начиная с кривой, полученной в ближайшем к точке обзора сечении.
Для первых двух кривых вопрос видимости тривиален. Для всех последующих надо решать задачу видимости точек кривой.
Важно отметить, что эти плоскости располагаются в заранее заданном диапазоне и рассматриваются с также заранее определённым постоянным шагом.
-
Формируется два горизонта - верхний и нижний.
-
Горизонты - массивы размерности ширины экрана. Верхний горизонт состоит из участков с наибольшим значением ординаты, нижний - из участков с наименьшим. Таким образом, массив максимальных (минимальных) значений ординат можно назвать верхним (нижним) горизонтом.
По сути, вся работа алгоритма сводится к вычислению значений y = f(x, z) для каждой из точек и сравнениям y(x) > y_max(x), y(x) < y_min(x). При выполнении условия соответствующее значение обновляется и кривая воспринимается как видимая.
Стоит сказать, что мы работаем не с кривой напрямую: мы рассматриваем набор точек (x; y) для фиксированного z, (причём по оси x мы идём в заданном диапазоне с заранее определённым постоянным шагом), и соединяем их отрезками.
Тем самым, мы производим интерполяцию кривой линейным сплайном. Иными словами, изображаем мы ломаную, созданную из этих точек.
Однако, если мы будем рассматривать только видимость каждой из точек, мы можем получить описанную ниже ситуацию: в том случае, если кривая меняет свою видимость между "опорными" точками, мы можем либо изобразить невидимую часть отрезка видимой или наоборот. В этом случае необходимо определять пересечение.
1) Для каждой плоскости z = const:
1. Обработать левое боковое ребро.
2. Для каждой точки текущей кривой P:
2.1 Определить видимость точки P
2.2 Если видимость изменилась:
2.2.1 Найти точку пересечения кривой с горизонтом.
2.3 Если текущий сегмент видим:
2.3.1 Изобразить его полностью.
2.4 Если видимость изменилась:
2.5 Если текущая точка невидима:
2.5.1 Изобразить участок от пересечения до точки
2.6 Если текущая точка видима:
2.6.1 Изобразить участок от точки до пересечения
2.7 Обработать правое боковое ребро, обновить массивы верхнего и нижнего горизонтов
Обработка боковых рёбер:
Q - переменная, хранящая крайнюю точку предыдущей кривой
P - первая (для левого бокового ребра) или последняя
(для правого бокового ребра) точка текущей кривой
Если текущая кривая не первая:
Изобразить ребро (P; Q)
Q = P
Подобная ситуация возникает, когда размер "скачка" функции оказывается меньше шага по X или Z. Тогда он может быть просто не отображён
- width - разрешение экрана по горизонтали
- height - разрешение экрана по вертикали
- top - верхний горизонт, bottom - нижний горизонт
- y - текущее значение функции y = f(x, z) при z = const
- t_flag - флаг видимости текущей точки
-
p_flag - флаг видимости предыдущей точки
(0 - невидима, -1 - ниже bottom, 1 - выше top)
subroutine Видимость (x, y, top, bottom, t_flag)
# Флаг видимости в 0, если точка невидима
if (y < top[x] && y > bottom[x])
t_flag = 0
# Флаг видимости в 1, если точка видима сверху от верхнего горизонта
if (y >= top[x])
t_flag = 1
# Флаг видимости в -1, если точка видима снизу от нижнего горизонта
if (y <= bottom[x])
t_flag = -1
return
subroutine ОбрРебра (x, y, x_edge, y_edge, bottom, top)
# В том случае, если это не первое ребро первой плоскости, соединяем концы отрезком
if (x_edge != -1)
call Горизонт(x_edge, y_edge, x, y, top, bottom)
# Запоминаем текущий конец как предыдущий
x_edge = x
y_edge = y
subroutine Горизонт (x1, y1, x2, y2, bottom, top)
# В случае вертикальности линии обновляем массивы согласно концам отрезка
if (x2 - x1 == 0)
top[x2] = max(top[x2], y2)
bottom[x2] = min(bottom[x2], y2)
else
# Иначе вычисляем тангенс угла наклона и идём от начала линии до конца,
# Обновляя массив горизонтов для каждой вычисленной точки
m = (y2 - y1) / (x2 - x1)
for (x = x1; x <= x2; x++)
y = m * (x - x1) + y1
top[x] = max(top[x], y)
bottom[x] = min(bottom[x], y)
return
subroutine Пересечение (x1, y1, x2, y2, horizon, x_i, y_i)
# В случае вертикальности пересечение - (x2, horizon[x2])
if (x2 - x1 == 0)
x_i = x2
y_i = horizon[x2]
else
# Вычисляем тангенс угла наклона
m = (y2 - y1) / (x2 - x1)
# y_sign - знак видимости следующей точки
y_sign = sign(y1 + m - horizon[x1 + 1])
c_sign = y_sign
# Запоминаем следующую точку
y_i = y1 + m
x_i = x1 + 1
# Итерируем, пока не найдём смену знака
while (c_sign == y_sign)
y_i = x_i + m
x_i++
c_sign = sign(y_i - horizon[x_i])
# Если начало выше конца, текущей точкой делаем начало
if |y_i - m - horizon[x_i-1]| <= |y_i - horizon[x_i]|
y_i = y_i - m
x_i--
return
- x_min, x_max - минимальная и максимальная абсцисса
- x_step - шаг по оси абсцисс
- z_min, z_max - минимальная и максимальная аппликата
- z_step - шаг по оси аппликат
# Инициализируем горизонты и крайние точки
init top[width], bottom[width]
x_left = -1, y_left = -1
x_right = -1, y_right = -1
# Заполняем горизонты
for (x = 0; x < width; x++)
top[x] = 0
bottom[x] = height
# Идём в сторону увеличения расстояния
for (z = z_max; z >= z_min; z--)
x_pr = x_min
y_pr = f(x_min, z)
# Обрабатываем левое боковое ребро
call ОбрРебра(x_pr, y_pr, x_left, y_left, top, bottom)
call Видимость(x_pr, y_pr, top, bottom, p_flag)
for (x = x_min; x <= x_max; x++)
y = f(x, z)
# Преобразования над изображением (повороты, переносы и т.д.) происходят здесь
call Видимость(x, y, top, bottom, t_flag)
# Если обе точки видимы, просто рисуем отрезок и меняем горизонты
if (t_flag == p_flag)
draw(x_pr, y_pr, x, y)
call Горизонт(x_pr, y_pr, x, y, top, bottom)
# Если невидима первая точка
else if (t_flag == 0)
# В случае видимости второй ищем пересечение сверху
if (p_flag == 1)
call Пересечение(x_pr, y_pr, x, y, top, bottom, x_i, y_i)
else
# Иначе возможно пересечение снизу
call Пересечение(x_pr, y_pr, x, y, bottom, top, x_i, y_i)
# Изображаем результирующий отрезок
draw(x_pr, y_pr, x, y)
call Горизонт(x_pr, y_pr, x_i, y_i, top, bottom)
else
# Если видима только вторая точка
if (t_flag == 1)
if (p_flag == 0)
# Находим пересечение с верхним горизонтом и рисуем от этого пересечения
call Пересечение(x_pr, y_pr, x, y, top, x_i, y_i)
draw(x_i, y_i, x, y)
call Горизонт(x_i, y_i, x, y, top, bottom)
else
# Иначе ищем пересечение и рисуем от него
call Пересечение(x_pr, y_pr, x, y, bottom, x_i, y_i)
draw(x_pr, y_pr, x_i, y_i)
call Горизонт(x_pr, y_pr, x_i, y_i, top, bottom)
call Пересечение(x_pr, y_pr, x, y, top, x_i, y_i)
draw(x_i, y_i, x_pr, y_pr)
call Горизонт(x_i, y_i, x, y, top, bottom)
Если вторая точка невидима
else
# В этом случае рисуем пересечение с верхним горизонтом
if (p_flag == 0)
call Пересечение(x_pr, y_pr, x, y, top, x_i, y_i)
draw(x_i, y_i, x, y)
call Горизонт(x_i, y_i, x, y, top, bottom)
else
# Иначе ищем пересечение и рисуем от него
call Пересечение(x_pr, y_pr, x, y, top, x_i, y_i)
draw(x_pr, y_pr, x_i, y_i)
call Горизонт(x_pr, y_pr, x_i, y_i, top, bottom)
call Пересечение(x_pr, y_pr, x, y, bottom, x_i, y_i)
draw(x_i, y_i, x, y)
call Горизонт(x_i, y_i, x, y, top, bottom)
# Обновляем флаг точки и саму точку
p_flag = t_flag
y_pr = y
x_pr = x
# Обрабатываем правое ребро
call ОбрРебра(x, y, x_right, y_right, top, bottom)
return
Алгоритм предназначен для удаления невидимых линий в трёхмерном представлении функции.
Алгоритм называется именно так по той причине, что мы
решаем задачу определения видимости с использованием двух массивов
- верхнего и нижнего - называемых горизонтами.
Эти массивы содержат значения максимальных и минимальных, соответственно,
значений, для каждого из рассматриваемых пикселов.
При анализе каждой новой плоскости значения могут меняться,
если участки кривой будут лежать выше верхней границы или ниже нижней
для какой-либо из точек. Именно поэтому горизонты будут "плавать"
Идея алгоритма заключается в том,
чтобы свести решение трёхмерной задачи к решению
ряда двухмерных. Для этого исходная поверхность
пересекается с рядом параллельных секущих плоскостей
вида x = const , y = const или z = const.
Плоскости обрабатываются в порядке удаления от
точки обзора, для каждой из плоскости получившаяся
кривая изображается с помощью набора точек,
соединяемых прямыми линиями. Во время этого анализа
отрезки проверяются на видимость
и меняют массивы горизонтов в случае видимости.
Шаг можно задать произвольно. Поиск пересечений осуществляется
в том случае, если видимость концов отрезка различна. В этом случае
на отрезке имеется точка, по прохождении которой видимость точек
отрезка меняется.
Для её нахождения можно пройти по отрезку в от
начальной точки до отрезка, и определив первую точку,
имеющую отличную от начала отрезка видимость
1) Алгоритм не может отображать поверхности, для которых y = f(x, z) не является функцией (то есть, можно найти несколько значений y для этих x и z). 2) Если функция содержит пики (очень острые участки), то алгоритм может давать некорректные результаты при малом шаге. Если для корректного изображения требуется шаг, меньший, чем разрешающая способность экрана, то видимыми могут считаться некоторые невидимые отрезки. 3) Алгоритм хранит горизонты и постоянно их обновляет, из-за этого он недостаточно быстродействующий. 4) При любом изменении угла обзора происходит полный перерасчет.
Для улучшения визуальных характеристик полученного результата, чтобы пользователю было лучше видно и удобнее опознать поверхность. На глаз изображение может не восприниматься как поверхность. Качество изображения улучшится если начальные и конечные точки каждой кривой соединить друг с другом (отрезками).