Ограничивающий объем - Bounding volume

3D-модель с ограничивающей рамкой, нарисованной пунктирными линиями.

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

Ограничивающий объем для набора объектов также является ограничивающим объемом для отдельного объекта, состоящего из их объединения, и наоборот. Следовательно, можно ограничить описание случаем одного объекта, который предполагается непустым и ограниченным (конечным).

Использует

Граничные объемы чаще всего используются для ускорения определенных видов тестов.

При трассировке лучей ограничивающие объемы используются в тестах на пересечение лучей , а во многих алгоритмах рендеринга они используются для просмотра тестов усеченной пирамиды . Если луч или усеченная пирамида обзора не пересекают ограничивающий объем, он не может пересекать содержащийся внутри объект, допуская тривиальное отклонение . Точно так же, если усеченная пирамида содержит весь ограничивающий объем, содержимое может быть тривиально принято без дополнительных тестов. Эти тесты пересечения создают список объектов, которые должны быть «отображены» (визуализированы; растрированы ).

При обнаружении столкновений , когда два ограничивающих объема не пересекаются, содержащиеся объекты не могут столкнуться.

Тестирование ограничивающего объема обычно намного быстрее, чем тестирование самого объекта из-за более простой геометрии ограничивающего объема. Это связано с тем, что «объект» обычно состоит из многоугольников или структур данных, которые сводятся к многоугольному приближению. В любом случае, если объект не виден, проверка каждого многоугольника относительно объема обзора является затратной с точки зрения вычислений. (Экранные объекты должны быть «привязаны» к экрану, независимо от того, видны ли их поверхности на самом деле.)

Чтобы получить ограничивающие объемы сложных объектов, распространенным способом является разбиение объектов / сцены с использованием графа сцены или, более конкретно, иерархии ограничивающих объемов , например, OBB-деревьев . Основная идея состоит в том, чтобы организовать сцену в виде древовидной структуры, в которой корень включает всю сцену, а каждый лист содержит меньшую часть.

Общие типы

Выбор типа ограничивающего объема для данного приложения определяется множеством факторов: вычислительными затратами на вычисление ограничивающего объема для объекта, стоимостью его обновления в приложениях, в которых объекты могут перемещаться или изменять форму или размер. , стоимость определения пересечений и желаемая точность теста пересечения. Точность теста на пересечение зависит от количества пространства в ограничивающем объеме, не связанного с ограниченным объектом, называемого пустым пространством . Сложные ограничивающие объемы обычно позволяют использовать меньше пустого пространства, но требуют больших вычислительных затрат. Обычно используют несколько типов вместе, например, дешевый для быстрого, но грубого теста в сочетании с более точным, но также более дорогим типом.

Все рассматриваемые здесь типы дают выпуклые ограничивающие объемы. Если известно, что ограничиваемый объект выпуклый, это не ограничение. Если требуются невыпуклые ограничивающие объемы, можно представить их как объединение ряда выпуклых ограничивающих объемов. К сожалению, тесты на пересечение быстро становятся более дорогими, поскольку ограничивающие рамки становятся более сложными.

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

Во многих приложениях ограничивающая рамка выровнена по осям системы координат, и тогда она известна как выровненная по оси ограничительная рамка ( AABB ). Чтобы отличить общий случай от AABB, произвольный ограничивающий прямоугольник иногда называют ориентированным ограничивающим прямоугольником ( OBB ) или OOBB, когда используется локальная система координат существующего объекта . AABB намного проще проверить на пересечение, чем OBB, но у них есть недостаток, заключающийся в том, что при повороте модели их нельзя просто повернуть вместе с ней, а их необходимо пересчитывать.

Ограничивающая капсула является охватили сферу (т.е. объема , что сфера занимает , как она двигается вдоль отрезка прямой линии) , содержащего объект. Капсулы могут быть представлены радиусом охватываемой сферы и сегментом, по которому распространяется сфера). Он имеет черты, похожие на цилиндр, но его проще использовать, потому что тест на пересечение проще. Капсула и другой объект пересекаются, если расстояние между определяющим сегментом капсулы и какой-либо особенностью другого объекта меньше, чем радиус капсулы. Например, две капсулы пересекаются, если расстояние между сегментами капсул меньше суммы их радиусов. Это справедливо для произвольно повернутых капсул, поэтому на практике они более привлекательны, чем цилиндры.

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

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

Ограничивающая сфера представляет собой сферу , содержащую объект. В 2-D графике это круг . Ограничивающие сферы представлены центром и радиусом. Их очень быстро проверяют на столкновение друг с другом: две сферы пересекаются, когда расстояние между их центрами не превышает сумму их радиусов. Это делает ограничивающие сферы подходящими для объектов, которые могут двигаться в любом количестве измерений.

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

Ограничивающий треугольник в 2-D является весьма полезным для ускорения теста вырезанного или видимости кривого B-сплайн. См. "Алгоритмы обрезки окружностей и B-сплайнов" в разделе "Отсечение" (компьютерная графика) для примера использования.

Выпуклая оболочка является наименьшим выпуклым объем , содержащий объект. Если объект представляет собой объединение конечного множества точек, его выпуклая оболочка является многогранником.

Дискретный ориентированный многогранник ( ДОФ ) обобщает ограничивающий прямоугольник. K-DOP - это логическое пересечение экстентов по k направлениям. Таким образом, k -DOP является булевым пересечением k ограничивающих плит и представляет собой выпуклый многогранник, содержащий объект (в 2-D - многоугольник , в 3-D - многогранник ). Двухмерный прямоугольник - это особый случай двухмерного изображения объекта, а трехмерный блок - это особый случай трехмерного изображения объекта. В общем, оси DOP не обязательно должны быть ортогональными, и осей может быть больше, чем размеров пространства. Например, трехмерный блок со скошенными кромками и углами может быть построен как 13-DOP. Фактическое количество граней может быть меньше 2 k, если некоторые грани становятся вырожденными, сокращаются до ребра или вершины.

Минимальный ограничивающий прямоугольник или MBR - наименее АА в 2-D - часто используются в описании географических (или «геопространственных») элементов данных, служащим в качестве упрощенной прокси - сервера для пространственной протяженности набора данных (см геопространственных метаданных ) для целей поиска данных (включая пространственные запросы, если применимо) и отображения. Это также базовый компонент метода пространственного индексирования R-tree .

Основные проверки перекрестков

Для некоторых типов ограничивающего объема (OBB и выпуклые многогранники) эффективной проверкой является проверка теоремы о разделяющей оси . Идея здесь в том, что если существует ось, по которой объекты не перекрываются, то объекты не пересекаются. Обычно проверяемые оси - это оси основных осей для объемов (оси единиц в случае AABB или 3 базовые оси от каждого OBB в случае OBB). Часто за этим следует также проверка перекрестных произведений предыдущих осей (по одной оси от каждого объекта).

В случае AABB эти тесты становятся простым набором тестов на перекрытие с точки зрения единичных осей. Для того АА определяются M , N против одного определяемого O , P , они не пересекается , если ( М _х > Р _х ) или ( О _й > Н _х ) или ( М _у > Р _у ) или ( О _у > Н _у ) или ( M _z > P _z ) или ( O _z > N _z ).

AABB также может быть спроецирован вдоль оси, например, если он имеет края длиной L и центрирован в C , и проецируется вдоль оси N:, и или , и где m и n - минимальная и максимальная протяженность. .
${\ displaystyle r = 0.5L_ {x} | N_ {x} | + 0.5L_ {y} | N_ {y} | + 0.5L_ {z} | N_ {z} | \,}$ ${\ displaystyle b = C * N \,}$ ${\ displaystyle b = C_ {x} N_ {x} + C_ {y} N_ {y} + C_ {z} N_ {z} \,}$ ${\ Displaystyle м = ш, п = б + г \,}$

OBB похож в этом отношении, но немного сложнее. Для OBB с L и C, как указано выше, и с I , J и K в качестве основных осей OBB, тогда:

{\ displaystyle r = 0,5L_ {x} | N * I | + 0,5L_ {y} | N * J | + 0,5L_ {z} | N * K | \,}

{\ Displaystyle м = С * Nr {\ mbox {и}} п = С * N + г \,}

Для диапазонов m , n и o , p можно сказать, что они не пересекаются, если m > p или o > n . Таким образом, проецируя диапазоны 2 OBB вдоль осей I, J и K каждого OBB и проверяя на непересечение, можно обнаружить непересечение. Дополнительно проверяя произведения этих осей (I ₀ × I ₁ , I ₀ × J ₁ , ...), можно быть более уверенным, что пересечение невозможно.

Эта концепция определения непересечения с помощью проекции оси также распространяется на выпуклые многогранники, однако при этом нормали каждой многогранной грани используются вместо базовых осей, а пределы основываются на минимальном и максимальном скалярных произведениях каждой вершины. против топоров. Обратите внимание, что это описание предполагает, что проверки выполняются в мировом пространстве.

Пересечение двух k -DOP может быть вычислено очень аналогично AABB: для каждой ориентации вы просто проверяете два соответствующих интервала двух DOP. Таким образом, точно так же, как DOP является обобщением AABB, тест на пересечение является обобщением теста на перекрытие AABB. Сложность проверки перекрытия двух DOP составляет $O (k)$ . Однако это предполагает, что оба DOP даны относительно одного и того же набора ориентаций. Если один из них повернуть, это уже неверно. В этом случае один относительно простой способ проверить два DOP на пересечение - это окружить повернутый один другой, наименьший охватывающий DOP, который ориентирован относительно ориентации первого DOP . Процедура для этого немного сложнее, но в конечном итоге также сводится к умножению матрицы на вектор сложности $O ($ $k$ $)$ . ${\ displaystyle D ^ {1}, D ^ {2}}$ ${\ displaystyle D ^ {2}}$ ${\ Displaystyle {\ тильда {D}} ^ {2}}$ ${\ displaystyle D ^ {1}}$

Смотрите также

Ссылки

внешние ссылки

Иллюстрация нескольких DOP для одной модели с сайта epicgames.com

Languages

In other projects