Замечание. Если проверяемая грань лежит в плоскости разбиения, то ее можно поместить в любую из частей. Существуют варианты метода, которые с каждым узлом дерева связывают список граней, лежащих в разбивающей плоскости. Алгоритм построения BSP-дерева очень похож на известный метод быстрой сортировки Хоара и реализуется следующим фрагментом кода.
BSPNode * buildBSPTree ( const Array& facets ) {
BSPNode * root = new BSPNode; // create root node Facet * part = (Facet *) facets [0]; // use 1st facet Array left, right;
Facet * fi,*f2;
root -> facet = part;
root -> n = part -> n;
root -> d = part -> n & part -> p [0];
for (int i = 1; i < facets.getCount (); i++ ) {
Facet * f = (Facet *) facets [i];
switch ( classifyFacet (root, f)) {Компьютерная графика. Полигональные модели
ujl!
case IN_ PLANE: // can put in any part case INjPOSITIVE: // facet lies in + left.insert (f); break;
case INJMEGATIVE: // facet lies in -right.insert (f); break;
default: // tplit facet
splitFacet {root, f, &f 1, &f2 ); left.insert (f1 ); right.insert (f2 ); break;
}
}
root->left = (left. getCount ()>0 ? buildBSPTree (left) : NULL ); root->right = (right. getCount ()>0 ? buildBSPTree (right) : NULL );
return root;
}При этом предполагается, что каждая грань описывается следующим классом
class Facet {
int count; // # of vertices
Vector3D n; //normal to facet
Vector3D p [MAX_PO!NTS]; // list of vertices
Facet ( Vector3D \ int);
};Для построения очередного разбиения приведенная выше функция использует самую первую грань из переданного списка. На самом деле в качестве разбивающей грани можно выбирать любую грань.
Получающиеся деревья сильно зависят от выбора разбивающих граней. На рис. 10.36 приведено дерево для сцены с рис. 10.34 с другим порядком выбора разбивающих граней. Обратите внимание на отсутствие разбиения граней в этом случае.
Для классификации граней относительно плоскости можно воспользоваться следующей функцией (для учета ошибок округления в ней используется малая величина EPS).