Нетрудно сразу же распространить все вышеизложенное на сцены, составленные из трехмерных полигональных сеток. Рассмотрим блок, изображенный на рис. 13.9, а. Каждая из его восьми граней пронумерована и показаны их внешние нормали. На рис. 13.9, «'приведена другая проекция того же самого блока. Если грани вставляются в BSP-дерево в порядке 1,2.....8, то образуется дерево, показанное на рис. 13.9, е. Каждая из граней «находит» свой путь вниз ПО дереву точно так же, как и в двумерном случае: если она лежит во внешнем полупространстве узловой грани, то она идет В поддерево outsideOnes и т. д. Грань 7 разбивается на грани 7а и 76 плоскостью грани 3 (пунктирная линия на рисунке). Грань 8 также разбивается на две части. (Существует ли такой порядок добавления граней, при котором не нужно ни одного разбиения граней?) В тематическом задании 13.2 рассказывается о разбиении граней с большими подробностями.
Рис. 13.9. Построение BSP-дерева (трехмерный случай)
13.3. HSR-методы со списками приоритетов Построение самого BSP-дерева рассматривается в программе тематического задания 13.3. А мы посмотрим, как использовать BSP-дерево для корректного рисования сцены.
Обход дерева (для рисования всех граней)
Для рисования всех граней сцены в нужной последовательности каждый узел посещается в определенном порядке и производится визуализация грани, содержащейся в этом узле. (Если это нелицевая грань, то рисование может быть пропущено.)
Как же устанавливается порядок, в котором рисуются грани? Это зависит от положения «глаза» камеры. Рассмотрим произвольную грань F дерева; предположим для определенности, что глаз камеры лежит во внешнем полупространстве грани F. Это означает, что все грани поддерева insideOn.es грани F лежат по другую сторону F относительно глаза, поэтому ни одна из них не может закрывать грань F в принципе. Следовательно, мы рисуем все грани поддерева insideOnes грани F, после чего рисуем саму грань F (она может быть нарисована поверх некоторых из этих граней). Теперь можно рисовать и все грани поддерева outsideOnes грани F, будучи уверенными, что они не лежат позади какой-либо из уже нарисованных граней.