При обходе дерева (листьев) в порядке front-to-back все лицевые грани каждого листа (порядок граней внутри листа неважен, так как каждый лист - выпуклый многогранник) выводятся в s-буфер.
Таким образом, в конце обхода дерева получается готовый s-буфер, содержащий разложение всего экрана на горизонтальные отрезки, упорядоченные сверху вниз и слева направо. После этого по построенному s-буферу осуществляется рисование статической сцены. При этом повторный вывод в один и тот же пиксел экрана полностью исключается.
Приведем алгоритм, строящий изображение статической части сцены (всех BSP-моделей), используя соответствующие структуры рак-файла, int BSPFile :: isSurfaceFrontFacing ( Surfaced surface ) const
{
return planes [surface.planeNum].normal & loc ) >= 0;
}
nt BSPFile :: isLeafVisible (int leaf) const
{
int v = curLeaf -> visList; // start of visibility list for curLeaf
for (register int i = 1; i < numLeaves; i++ ) if ( visLists [v] == 0 )
{
i += 8 * visLists [v +1]; v++;
}
else
{
for (register int bit = 0x80; bit > 0; bit »= 1, i++ ) if ((i == leaf) && ( visLists [v] & bit)) return 1;
}
return 0;
}
int BSPFile :: viewerlnFront ( Plane& plane ) const {
return ( plane.normal & loc ) >= plane.dist;
}
void BSPFile :: traverseBSPTree (long node ) {
Plane * plane = &planes [nodes [node].planeNum]; if ( node & 0x8000 ) // is it a leaf
if ( curLeaf == NULL )
curLeaf = &leaves [-node]; if (isLeafVisible ( -node ))Компьютерная графика. Полигональные модели
visLeaves.insert ( &leaves [-node]); return;
}
// check whether node lies // in viewing frustrum if (IboxInFrustrum ( nodes [node].boundBox )) return;
if ( viewerlnFront (*plane )) {
traverseBSPTree ( nodes [nodej.front); traverseBSPTree ( nodes [node].back );
}
else
{
traverseBSPTree ( nodes [node].back ); traverseBSPTree ( nodes [nodej.front);
}
}
void BSPFile :: renderLeaf ( BSPLeaf& leaf) {
if (IboxInFrustrum (leaf.boundBox )) return;
int firstSurface = leaf.firstSurface;
int lastSurface = leaf.firstSurface + leaf.nuymSurfaces -1;