Если же, напротив, глаз камеры расположен во внутреннем полупространстве грани F, то мы вначале рисуем все грани поддерева outsideOnes, затем - саму грань F, а затем уже все грани из поддерева insideOnes грани F. Заметим, однако, что в данном случае грань Fвсегда является «нелицевой гранью» (почему?), поэтому фактически она не рисуется (за исключением случая, когда имеется необходимость рисовать задние грани).
Вышеприведенное рассмотрение, в сущности, устанавливает правило рисования каждого поддерева для дерева; таким образом, мы получаем следующий рекурсивный метод для рисования всей сцены: для того чтобы нарисовать сцену целиком, нужно нарисовать одно Поддерево корня (его выбор определяется расположением глаза), затем сам корень и, наконец, второе поддерево корня. Ниже приводится псевдокод, составленный в соответствии с этим правилом: То draw the faces stored in the BSP tree with root F.
// Для рисования граней, находящихся в BSP-дереве с корней F.
if (the eye is in the "outside" half-space of face F)// глаз лежит во «внешнем» полупространстве грани F
{draw all faces in the inside subtree of F: // рисуем все грани внутреннего поддерева грани F
draw F; // рисуем F
draw all faces in the outside subtree of F: // рисуем все грани внешнего поддерева грани F }
else
// the eye is on the "inside" of F// глаз расположен во «внутреннем» полупространстве F
{draw all faces in the outside subtree of F; // рисуем все грани внешнего полупространства F
if (you want to draw back faces), draw F: // если нужно рисовать нелицевые грани, то рисуем F:
draw all faces in the inside subtree of F; // рисуем все грани внутреннего поддерева грани F: }
В этом псевдокоде можно узнать «симметричный обход» («inorder traversal») двоичного дерева [Kruse, 128], где порядок обхода каждого поддерева определяется положением глаза относительно грани этого поддерева.
Удаление невидимых поверхностей
Для трехмерной сцены, изображенной на рис. 13.9, а, дерево с рис. 13.9, в можно обойти по вышеприведенной схеме, и блок будет нарисован правильно. На рис. 13.10, а стрелками показан порядок посещения узлов BSP-дерева, изображенного на рис. 13.9, в, - для конкретного вида блока, который приведен на рис. 13.9, а. Те грани, которые на рисунках бив подчеркнуты, являются нелицевыми и действительно не рисуются. (Убедитесь в том, что все грани рисуются правильно.)