Интернет магазин китайских планшетных компьютеров

Компьютеры - Двоичное разбиение пространства - Применение

Сортировка объектов в порядке удаления от наблюдателя

При сортировке объектов в порядке удаления от наблюдателя с помощью BSP-дерева исследуются взаимное расположение вектора и точки наблюдения и нормалей разбивающих плоскостей. Если нормаль разбивающей плоскости и вектор наблюдения сонаправлены, то фронтальное поддерево находится от наблюдателя дальше, чем оборотное, в противном случае оборотное поддерево находится от наблюдателя дальше, чем фронтальное. При этом, если разбивающая плоскость находится сзади наблюдателя, то сама плоскость, а также фронтальное или оборотное поддерево может быть не видны полностью. Рекурсивный алгоритм сортировки полигонов с помощью BSP-дерева следующий:

Процедура ОбойтиУзел
  Если Узел <> ПустойУказатель
    Если ВекторыСонаправлены
      Если СкалярноеПроизведение >= 0
        // Плоскость находится сзади наблюдателя, наблюдатель видит только фронтальное поддерево
        ОбойтиУзел;
      Иначе
        // Плоскость находится спереди наблюдателя, 
        // фронтальное поддерево находится дальше оборотного
        ОбойтиУзел;
        ДобавитьПолигонВСписокОтображения;
        ОбойтиУзел;
      КонецЕсли;
    Иначе
      Если СкалярноеПроизведение >= 0
        // Плоскость находится спереди наблюдателя,
        // оборотное поддерево находится дальше фронтального
        ОбойтиУзел;
        ДобавитьПолигонВСписокОтображения;
        ОбойтиУзел;
      Иначе
        // Плоскость находится сзади наблюдателя, наблюдатель видит только оборотное поддерево
        ОбойтиУзел;
      КонецЕсли;
    КонецЕсли;
  КонецЕсли;
Конец;

Этот алгоритм можно оптимизировать, если учесть, что для некоторого набора полигонов дерево имеет вырожденную структуру, в том случае, когда для каждого полигона из этого набора все оставшиеся лежат только с фронтальной или только с оборотной стороны. Именно так сделал Джон Кармак в движке DOOM.

Алгорим для ускорения из рекурсивного может быть преобразован в итеративный.

Отсечение невидимых поверхностей

Отсечение невидимых поверхностей реализуется путем введения дополнительной информации в BSP-дерево, такой как рамки. Рамки — это прямоугольники или параллелепипеды, окружности или сферы, которые ограничивают область расположения полигонов некоторого поддерева. Таким образом, каждый узел имеет две рамки. Поддерево гарантированно невидимо, если зрительная пирамида не пересекается с ограничивающим объектом. Обратное неверно. Однако прямого утверждения достаточно, чтобы отсечь обработку существенного количества объектов.

Выбор геометрических объектов, которыми представлены рамки, исходит из простоты алгоритма проверки пересечения зрительной пирамиды с рамкой.

Поиск столкновений

При поиске столкновений BSP-дерево используется для поиска плоскости, расположенной ближе всего к объекту. Чаще всего границы объекта задаются ограничиващей сферой для упрощения вычислений. Выполняется обход BSP-дерева от корня до плоскости, расположенной ближе всего к объекту. При этом, если не обнаруживается пересечений ограничивающей сферы ни с одной плоскостью, то столкновения нет, в противном случае — есть.

Пример:

Процедура ПоискСтолкновения
  Если Узел <> ПустойУказатель
    Если Расстояние > Объект.РадиусОграничивающейСферы
      Если СкалярноеПроизведение >= 0
        // Объект находится с фронтальной стороны разбивающей плоскости,
        // обходим только фронтальное поддерево
        ПоискСтолкновения;
      Иначе
        // Объект находится с обратной стороны разбивающей плоскости, 
        // обходим только оборотное поддерево
        ПоискСтолкновения;
      КонецЕсли;
    Иначе
      Вернуть ЕстьСтолкновение;
    КонецЕсли;
  Иначе
    Вернуть НетСтолкновения;
  КонецЕсли;
Конец;

Алгорим для ускорения из рекурсивного может быть преобразован в итеративный.