ВУЗ:
Составители:
Рубрика:
редной кривой этот горизонт «всплывает». Фактически этот алгоритм удаления невидимых линий работает каждый раз с одной
линией.
Алгоритм работает очень хорошо до тех пор, пока какая-нибудь очередная кривая не окажется ниже самой первой из
кривых.
Подобные кривые, естественно, видимы и представляют собой нижнюю сторону исходной поверхности, однако алго-
ритм будет считать их невидимыми. Нижняя сторона поверхности делается видимой, если модифицировать этот алгоритм,
включив в него нижний горизонт, который опускается вниз по ходу работы алгоритма. Это реализуется при помощи второго
массива, длина которого равна числу различимых точек по оси
x
в пространстве изображения. Этот массив содержит наи-
меньшие значения
y
для каждого значения
x
.
Рис. 7.3. Пример работы алгоритма «плавающего горизонта»
Алгоритм теперь становится таким: если на текущей плоскости при некотором заданном значении
x
соответствующее зна-
чение
y
на кривой больше максимума или меньше минимума по
y
для всех предыдущих кривых при этом
x
, то текущая кривая
видима. В противном случае она невидима.
Пример поверхности функции:
y
= (1/5) sin(
x
) cos(
z
) – (3/2) cos(7
a
/4) ×
e
–
a
,
где
a
= (
x
– π)
2
+ (
z
– π)
2
, изображённой в интервале (0,2π), представлена на рис. 7.3.
8. АЛГОРИТМ УДАЛЕНИЯ НЕВИДИМЫХ ГРАНЕЙ, ИСПОЛЬЗУЮЩИЙ BSP-ДЕРЕВА
В процессе проектирования пространственных (
3D
) объектов, например, изделий машиностроения, архитектурных со-
оружений и т.п., поверхности которых представлены с помощью плоских многоугольников (полигонов), приходится решать
множество задач компьютерной графики, одной из которых является определение видимости полигонов сцены 3
D
объектов
камерой наблюдателя.
В случае обработки неподвижной визуализационной сцены задача удаления невидимых полигонов не является предме-
том детального изучения специалистов в области компьютерной графики из-за того, что нет временных ограничений в реа-
лизации данного процесса. Но как только требуется наблюдать за сценой в динамике, то задаче удаления невидимых поли-
гонов (или их фрагментов) уделяется первостепенное внимание.
Одним из эффективных алгоритмов удаления невидимых граней в режиме реального времени является алгоритм, исполь-
зующий BSP-дерево [26]. Под BSP-деревом понимается пространственное взаимоотношение полигонов 3
D
сцены.
Концептуально BSP-дерево формируется следующим образом. Пусть какая-то плоскость в объектном пространстве
разбивает множество полигонов сцены на два подмножества, и при этом ни один из полигонов не попал под рассечение
плоскостью. Тогда очевидно, что подмножество полигонов, не содержащее наблюдателя, не может экранировать полигоны
из множества с наблюдателем. Если в каждом подмножестве полигонов опять найдем плоскости, не пересекающие внутрен-
ние полигоны, то данные подмножества будут разбиты на две части. Продолжая процесс разбиения подмножеств полигонов,
придём к размеру подмножества в один полигон. Процесс разбиения сцены на подмножества с параллельным формировани-
ем BSP-дерева осуществляется рекурсивно.
Совокупность плоскостей и соответствующих подмножеств дают в результате двоичное дерево разбиения пространст-
ва. Узлами данного дерева будут разбивающие плоскости, а ветви – соответствующие подмножества. Листьями BSP-дерева
будут полигоны объекта визуализации.
На практике в качестве разбивающей плоскости выбирают плоскость, проходящую через один из полигонов. Плоскость
может рассечь несколько полигонов на части, после чего рассеченные полигоны подменяются их составными частями в мо-
дели данных объекта. И полученные таким образом новые полигоны распределяются в соответствующие подмножества
BSP-дерева.
Для определения расположения полигонов по отношению к разбивающей плоскости можно воспользоваться значением
тестовой функции –
TF
(
x
,
y
,
z
), которая имеет вид
TF
=
Ax
+
By
+
Cz
+
D
,
где
A
,
B
,
C
,
D
– коэффициенты уравнения разбивающей плоскости;
x
,
y
,
z
– координаты анализируемой точки в пространстве
сцены.
Если
TF
≥ 0, то это указывает на правое подмножество BSP-дерева, а
TF
< 0 указывает на левое подмножество дерева.
Процесс удаления невидимых полигонов сцены с использованием BSP-дерева для построения итогового изображения
заключается в рекурсивном проходе дерева от «передних» ветвей к «задним» по следующей схеме:
− начиная с корневого узла дерева, определяем положение наблюдаемой камеры относительно рассекающей плоско-
сти полигона данного узла;
− прорисовываем противоположную ветвь, потом полигоны, принадлежащие рассекающей плоскости и, в последнюю
очередь, ветвь, в которой находится наблюдатель;
− рекурсивно повторяем этот процесс для каждого узла BSP-дерева сцены визуализации.
Страницы
- « первая
- ‹ предыдущая
- …
- 29
- 30
- 31
- 32
- 33
- …
- следующая ›
- последняя »
