ВУЗ:
Составители:
Рубрика:
При построении BSP-дерева в качестве корневого узла может быть выбран любой полигон сцены, но исследование по-
казало, что в зависимости от того, какой полигон выбран, вид дерева меняется, что в конечном итоге сказывается на процес-
се обработки дерева при построении изображения.
В процессе работ построения BSP-деревьев 3D сцен выявилось, что стремление получить сбалансированное дерево
сцены визуализации, как правило, приводит к разрастанию модели данных сцены за счёт деления полигонов на составные
части секущими плоскостями узловых полигонов дерева.
Для получения некоторого компромисса между сбалансированностью BSP-дерева сцены и небольшим количеством
возможных рассечений полигонов в работе предлагается следующая методика.
Сформируем таблицу состояний для каждого полигона анализируемой 3
D
сцены со следующими параметрами:
− количество полигонов сцены, находящихся левее данного [«–»];
− количество полигонов сцены, находящихся правее данного [«+»];
− количество пересечений полигонов сцены с плоскостью данного полигона [«Кол. пересечений»];
− значение разности по модулю первого и второго параметра [abs(«–» – «+»)].
Последний параметр таблицы указывает на сбалансированность дерева. При минимальном значении этого поля раз-
ность между количеством полигонов правой части дерева и левой минимальна.
Понятие «левее» и «правее» для расположения полигонов чисто условное, так как на самом деле здесь играет роль зна-
ка пробной функции секущей плоскости, куда подставляем координаты вершин анализируемых полигонов.
Для каждого подмножества полигонов сцены строим подобные таблицы, из которых выбираем полигон с минимальным
значением поля – [abs(«–» – «+»)] и минимальным значением поля – [«Кол. пересечений»]. Подобные полигоны будут яв-
ляться узловыми полигонами строящегося BSP-дерева анализируемой сцены. Процесс разбиения полигонов на подмножест-
ва завершается, когда в таблице состояний находятся всего два полигона.
Рассмотрим некоторый пример 3
D
сцены, состоящей из четырёх полигонов: 1, 2, 3 и 4 (рис. 8.1).
Рис. 8.1. Пример пространственной сцены
Построим BSP-дерево данной сцены. Для организации верхнего уровня BSP-дерева заполним таблицу состояний полиго-
нов в сцене (табл. 8.1).
Таблица 8.1
№ полигона «–» «+» Кол. пересечений abs(«–» – «+»)
1 0 3 0 3
2 2 3 2 1
3 2 1 0 1
4 3 0 0 3
В этой таблице выделяем полигоны с минимальным значением поля – [abs(«–» – «+»] и выбираем из них тот, для кото-
рого количество пересечений минимальное. В данном примере наиболее близко для корневого сегмента BSP-дерева подхо-
дят полигоны 2 и 3. С точки зрения балансировки дерева вариант с корневым полигоном 2 наиболее предпочтителен, но в
этом случае приходится разбивать два полигона (1 и 3) на части, поэтому выбираем полигон 3, так как количество пересече-
ний равно нулю.
При появлении в таблице полигонов с одинаковыми значениями четвертого параметра – [abs(«–» – «+»)] выбираем из
этого списка полигон, для которого значение поля – [«Кол. пересечений»] минимальное.
Подобные таблицы строятся для каждого левого и правого подмножества полигонов относительно выбранного полиго-
на строящегося дерева. И по аналогичной схеме определяется внутренний узловой полигон. В данном случае в левом под-
множестве останется полигон 1 и 2, а в правом 4. Для полигонов 1 и 2 опять строим таблицу состояний (табл. 8.2).
Таблица 8.2
Y
X
Z
Страницы
- « первая
- ‹ предыдущая
- …
- 30
- 31
- 32
- 33
- 34
- …
- следующая ›
- последняя »
