if ( back != NULL )
if ( back -> visitlnorder ( visitor ) ) return true;
}
else
{
if ( back != NULL )
if ( back -> visitlnorder ( visitor ) ) return true;
if ( visitor.visit ( this ) ) return true;
if ( front != NULL )
if ( front -> visitlnorder ( visitor ) ) return true;
}return false;
}
bool BspNode :: visitPostorder ( BspNodeVisitor& visitor ) {
if ( !visitor.wantsNode ( this ) ) return true;
int cl = classify ( visitor.getPos () );
if ( cl == IN_BACK ) {
if ( front != NULL )
if ( front -> visitlnorder ( visitor ) ) return true;
if ( visitor.visit ( this ) ) return true;
if ( back != NULL )
if ( back -> visitlnorder ( visitor ) ) return true;
}
else
{
if ( back != NULL )
if ( back -> visitlnorder ( visitor ) ) return true;
if ( visitor.visit ( this ) ) return true;
if ( front != NULL )
if ( front -> visitlnorder ( visitor ) ) return true;
}
return false;
}Для осуществления обхода BSP-дерева в заданном порядке строится экземпляр класса, унаследованного от класса BspVisitor, и у этого объекта вызывается метод visitlnorder или visitPostorder для обхода дерева в заданном порядке.
Процедура построения BSP-дерева достаточно проста: выбирается одна из граней переданного списка (мы будем выбирать грань, минимизирую-
Пишем портальный рендерер (часть II)
щую число разбиений) и производится разбиение всех граней на два множества - множество граней, лежащих в положительном полупространстве (front), и множество граней, лежащих в отрицательном полупространстве (back).
Если грань лежит сразу в обоих полупространствах, то она разбивается на две части, одна из которых лежит в положительном полупространстве, а другая в отрицательном. Для разбиения грани мы будем использовать метод split класса PoIygon3D.
После того как все грани будут разбиты на два множества, осуществляется построение двух BSP-деревьев (по одному на каждое из построенных множеств). Каждое из построенных деревьев становится соответствующим поддеревом строящегося дерева. Реализация этого алгоритма приводится ниже.