Для установки нажмите кнопочку Установить расширение. И это всё.

Исходный код расширения WIKI 2 регулярно проверяется специалистами Mozilla Foundation, Google и Apple. Вы также можете это сделать в любой момент.

4,5
Келли Слэйтон
Мои поздравления с отличным проектом... что за великолепная идея!
Александр Григорьевский
Я использую WIKI 2 каждый день
и почти забыл как выглядит оригинальная Википедия.
Статистика
На русском, статей
Улучшено за 24 ч.
Добавлено за 24 ч.
Что мы делаем. Каждая страница проходит через несколько сотен совершенствующих техник. Совершенно та же Википедия. Только лучше.
.
Лео
Ньютон
Яркие
Мягкие

Двоичное разбиение пространства

Из Википедии — свободной энциклопедии

Двоичное разбиение пространства (англ. binary space partitioning) — метод рекурсивного разбиения евклидова пространства в выпуклые множества и гиперплоскости. В результате объекты получают представление в виде структуры данных, называемой BSP-деревом.

BSP-дерево используется для эффективного выполнения следующих операций в трёхмерной компьютерной графике:

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

Обзор

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

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

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

Построение дерева

Пример построения 1. A — корень и набор отрезков на плоскости целиком.2. A делится на B и C.3. B делится на D и E.4. D делится на полностью выпуклые F и G, которые и становятся листьями дерева.
Пример построения
1. A — корень и набор отрезков на плоскости целиком.
2. A делится на B и C.
3. B делится на D и E.
4. D делится на полностью выпуклые F и G, которые и становятся листьями дерева.

Вышеприведенное определение описывает только свойства BSP-дерева, но не говорит как его построить. Как правило, BSP-дерево строится для набора отрезков на плоскости или полигонов в пространстве, представляющих некоторую фигуру или сцену. Рассмотрим алгоритм построения BSP-дерева для набора полигонов в пространстве:

  1. Если заданное множество полигонов пустое, то закончить алгоритм;
  2. Для заданного множества полигонов выбрать разбивающую плоскость S;
  3. Рассечь все полигоны, пересекающиеся с S;
  4. Отнести все полигоны, находящиеся с фронтальной стороны S, к фронтальному поддереву F, а все полигоны, находящиеся с обратной стороны S, к оборотному поддереву B;
  5. Выполнить алгоритм рекурсивно для множества полигонов фронтального поддерева F;
  6. Выполнить алгоритм рекурсивно для множества полигонов оборотного поддерева B.

Выбор разбивающей плоскости

Разбивающая плоскость выбирается таким образом, чтобы сбалансировать дерево, то есть чтобы число полигонов во фронтальном и оборотном поддереве было приблизительно одинаково:

min(|N(Fi) — N(Bi)|)

где N(Fi) — число полигонов с фронтальной стороны некоторой разбивающей плоскости i, N(Bi) — число полигонов с оборотной стороны разбивающей плоскости i.

Применение

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

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

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

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

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

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

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

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

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

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

Пример:

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

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

Литература

Ссылки

Эта страница в последний раз была отредактирована 30 сентября 2021 в 10:31.
Как только страница обновилась в Википедии она обновляется в Вики 2.
Обычно почти сразу, изредка в течении часа.
Основа этой страницы находится в Википедии. Текст доступен по лицензии CC BY-SA 3.0 Unported License. Нетекстовые медиаданные доступны под собственными лицензиями. Wikipedia® — зарегистрированный товарный знак организации Wikimedia Foundation, Inc. WIKI 2 является независимой компанией и не аффилирована с Фондом Викимедиа (Wikimedia Foundation).