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



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

23 января 2011


Оглавление:
1. Двоичное разбиение пространства
2. Построение дерева
3. Применение



это структура данных, используемая в трехмерной графике. Аббревиатура BSP означает Binary Space Partition — двоичное разбиение пространства. BSP-дерево используется для эффективного выполнения следующих операций:

  • Сортировки визуальных объектов в порядке удаления от наблюдателя;
  • Обнаружение столкновений.

BSP-деревья были впервые применены специалистами компании Lucas Arts в начале 80-х годов. Популярность у разработчиков они завоевали благодаря компании id Software, разработавшей движки Doom и Quake.

Обзор

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

  1. Скалярное произведение больше 0 — точка лежит с фронтальной стороны плоскости;
  2. Скалярное произведение равно 0 — точка лежит на плоскости;
  3. Скалярное произведение меньше 0 — точка лежит с обратной стороны плоскости.

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



Просмотров: 1620


<<< Графический метод решения задачи линейного программирования
Диаграмма Вороного >>>