На рис. 13.8, б показано состояние дерева после добавления к нему еще семи ребер, обозначенных числами от двух до восьми. Ребро 2 лежит во внутреннем полупространстве ребра 1, поэтому оно вставляется в поддерево insideOnes. Ребро 3 лежит во внутренних полупространствах ребер 1 и 2, поэтому оно размещено именно так, как показано на рисунке. (Проверьте это!) Ребро 4 на рисунке не приведено; покажите сами, куда оно должно идти.
Когда мы добавляем ребро 9, происходит нечто новое. Это ребро лежит во внешнем полупространстве ребра 1, но сразу в обоих полупространствах ребра 5. Поэтому оно разбивается (split) ребром 5 на
Удаление невидимых поверхностей
два ребра - 9а и 96 (см. рис. 13.7); для каждого из этих кусков ребра 9 находится свое место вниз по дереву. Ребро 9а лежит во внутреннем полупространстве ребра 5, поэтому оно идет налево и проверяется относительно ребер 6 и 7; ребро 9Ь лежит во внешнем полупространстве ребра 5, но во внутреннем - ребра 8. Ребра 10 и 11 вставляются аналогично, но для них разбиения не требуется. (Как будет выглядеть результирующее дерево?)
Рис. 13.8. Построение BSP-дерева (двумерный случай)
BSP-дерево составляет список ребер специальным способом, поэтому для любого ребра можно сразу сказать (по его положению на дереве), в какой «части» пространства оно расположено (например, ребро 6 лежит во внешнем полупространстве ребра 1 и во внутреннем - ребра 5). Структура такого дерева никоим образом не зависит от положения глаза.
Отметим, что порядок, в котором ребра добавляются к дереву, сильно влияет на «форму» этого дерева. При некоторых вариантах выбора порядка ребер дерево выглядит «полным» (full) и «низкорослым» (shallow) (число узлов от корня до самого глубокого листа невелико), а другой выбор порядка ребер приводит к «тощему» и «глубокому» дереву. Низкорослые деревья более эффективны при обработке. Наихудший случай формы BSP-дерева - одиночная цепочка сверху донизу.
BSP-деревья для трехмерных сцен