Далее для каждого из получившихся множеств, которые не являются одним выпуклым многоугольником, повторяем описанную процедуру.
В результате мы получаем разбиение всей сцены на набор SubSector и соответствующее двоичное дерево, узлами которого являются прямые, производящие разбиение, а листьями - выпуклые многоугольники - SubSector. Связь этого метода с классическим BSP-деревом несомненна. В получившемся дереве все узлы нумеруются начиная с нуля, так что корень дерева имеет наибольший номер. Листьям дерева присваиваются номера соответствующих SubSector, где (чтобы его можно было отличить от узла) устанавливается старший бит (0x8000).
Границами каждого SubSector в общем случае являются части отрезков, называемые сегментами (Seg). При этом все сегменты упорядочиваются так, чтобы при их последовательном обходе соответствующий SubSector всегда находился справа. Приведем список Seg для сцены с рис. 13.15: [5, 4], [4, 1], [1, 0], [0, ,5], [1,4], [4,3], [3,2], 2,1].
Для сцены с рис. 13.17 возникают следующие сегменты: [7, 5], [5, 4], [4, 3], [3, 2], [6, 7], [2, 1], [1, 0], [0, 6]. Обратите внимание на отсутствие сегмента между точками 2 и 7.
Для упорядочения всех SubSector используется рекурсивная процедура, полностью аналогичная процедуре вывода BSP-деревьев.
void drawNode ( unsigned node ) {
if ( node & 0x8000 ) // if it's a ssector - draw it drawSubSector ( node & 0x7FFF );
else
if ( viewerOnRight ( node )) {
drawNode ( Nodes [node].rightNode ); drawNode ( Nodes [nodej.leftNode );
}
else
r
t
drawNode ( Nodes [node].leftNode ); drawNode ( Nodes [nodej.rightNode );
}
}
fCJ] a.Компьютерная графика. Полигональные модели Данная процедура обеспечивает вывод всех SubSector в порядке front-to-back, причем первым будет выведен тот SubSector, где находится игрок. Для вывода всей сцены достаточно вызвать drawNode с номером корневого узла дерева.
Поскольку каждый SubSector является выпуклым многоугольником, то никакого специального упорядочения ограничивающих его отрезков не требуется, достаточно только отбросить нелицевые отрезки.