Face *tree - NULL: // create an empty BSP tree // создаем пустое BSP-дерево for(i - 0: i < NumFaces: i++)
tree - insertBSP(&faces[1]. &tree):Когда в дерево вставляется грань faces[i] (без разбиения), то устанавливаются только указатели ее потомков; при этом грань faces[i] находится одновременно в массиве faces[] и в дереве. Если грань faces[i] подлежит разбиению, то создаются две новые грани (как обсуждалось в тематическом задании 13.2), которые добавляются в дерево.
Листинг 13.10. Подпрограмма добавления грани в BSP-дерево
void insertBSPCFace& *Root. Face* face) {// insert face into subtree whose root is *Root. // добавляем грань в поддерево с корнем *Root
if(lface) return: // nothing to insert // добавлять нечего
Face inFace. outFace: // hold the two pieces of the face // удерживаем два куска грани
if(tree is empty so far)продолжение^
Удаление невидимых поверхностей
Листинг 13.10 (продолжение)
// дерево до сих пор пусто
{attach the face to the tree II присоединяем грань к дереву return:
}
switch(FaceWithP1ane(face. Rott. inFace. outFace) {case -1: // face lies inside plane // грань лежит с внутренней стороны плоскости
insertBSPCface into insideOnes subtree):break: // грань в поддерево insideOnes
case 1: // face lies outside plane // грань лежит с внешней стороны плоскости
insertBSPCface into outsideOnes subree): break: // грань в поддерево outsideOnes
case 0: // face was split // произошло разбиение грани
insertBSPO'nFace into the insideOnes subtree): II inFace в поддерево insideOnes
insertBSPCoutFace into the outsideOnes subtree);break; // outFace в поддерево outsideOnes }
}В листинге 13.10 приведена подпрограмма, предназначенная для добавления грани в BSP-дерево; при необходимости эту подпрограмму можно скорректировать с целью исправления каких-либо дефектов. Функция FaceWithPlane()(cM. тематическое задание 13.2) используется для определения того, с какой стороны плоскости лежит грань; при необходимости эта функция разбивает грань на две части, добавляя их к нижней части дерева.