Методическое пособие по курсу "Интерактивные графические системы". Найханов В.В - 39 стр.

            3.3.5 Метод двоичного разбиения пространства

      Существует другой, крайне элегантный способ упорядочивания
граней.
      Рассмотрим некоторую плоскость в объектном пространстве. Она
разбивает множество всех граней на два непересекающихся множества
(кластера), в зависимости от того, в каком полупространстве относительно
плоскости эти грани лежат (будем считать, что плоскость не пересекает ни
одну из этих граней).
      При этом очевидно, что ни одна из граней, лежащих в
полупространстве, не содержащем наблюдателя, не может закрывать собой
ни одну из граней, лежащих в том же полупространстве, что и наблюдатель.
Тем самым сначала необходимо вывести грани из дальнего кластера, а затем
уже и из ближнего.
      Применим подобную технику для упорядочения граней внутри
каждого кластера. Для этого построим разбиение граней каждого кластера
на два множества очередной плоскостью; а затем для вновь полученных
граней повторим процесс разбиения, и будем поступать так до тех пор, пока
в каждом получившемся кластере останется не более одной грани.
      Обычно в качестве разбивающей плоскости рассматривается
плоскость, проходящая через одну из граней (на самом деле при этом
множество всех граней разбивается на 4 класса - лежащих на плоскости,
пересекающих ее, лежащих в положительном полупространстве и лежащие
в отрицательном полупространстве относительно этой плоскости). Все
грани, пересекаемые плоскостью, разобьем вдоль этой плоскости.
      В результате мы приходим к дереву разбиения пространства (Binary
Space Partitioning), узлами которого являются грани.
      Процесс построения дерева заключается в выборе грани, проведении
через нее плоскости и разбиении множества всех граней. В этом процессе
присутствует определенный произвол в выборе очередной грани.
Существует два основных критерия для выбора:
      • получить как можно более сбалансированное дерево;
      • минимизировать количество разбиений.
      К     сожалению,      эти    критерии,    как  правило,   являются
взаимоисключающими, поэтому выбирается некоторый компромиссный
вариант.
      После того как дерево построено, осуществляется построение
изображения в зависимости от используемого проектирования.
      Одним из основных преимуществ этого метода является его полная
независимость от положения центра проектирования, что делает его крайне
удобным для построения серий изображений одной и той же сцены из
разных точек наблюдения.