В компьютерной графике и вычислительной геометрии ограничивающий объем (или ограничивающая область ) для набора объектов — это замкнутая область , которая полностью содержит объединение объектов в наборе. Ограничивающие объемы используются для повышения эффективности геометрических операций, например, путем использования простых областей, имеющих более простые способы проверки на перекрытие .
Ограничивающий объем для множества объектов является также ограничивающим объемом для отдельного объекта, состоящего из их объединения, и наоборот. Поэтому можно ограничиться случаем отдельного объекта, который предполагается непустым и ограниченным (конечным).
Ограничивающие объемы чаще всего используются для ускорения определенных видов испытаний.
В трассировке лучей ограничивающие объемы используются в тестах пересечения лучей , а во многих алгоритмах рендеринга они используются для тестов просмотра усеченной пирамиды . Если луч или усеченная пирамида не пересекает ограничивающий объем, он не может пересекать содержащийся в нем объект, что позволяет тривиальное отклонение . Аналогично, если усеченная пирамида содержит весь ограничивающий объем, содержимое может быть тривиально принято без дополнительных тестов. Эти тесты пересечения создают список объектов, которые должны быть «отображены» (отрисованы; растеризованы ).
При обнаружении столкновений , когда два ограничивающих объема не пересекаются, содержащиеся в них объекты не могут столкнуться.
Тестирование по ограничивающему объему обычно выполняется намного быстрее, чем тестирование по самому объекту, из-за более простой геометрии ограничивающего объема. Это происходит потому, что «объект» обычно состоит из полигонов или структур данных, которые сводятся к полигональным приближениям. В любом случае, тестировать каждый полигон по объему представления, если объект не виден, является расточительным с точки зрения вычислений. (Экранные объекты должны быть «обрезаны» по экрану, независимо от того, видны ли их поверхности на самом деле.)
Чтобы получить ограничивающие объемы сложных объектов, распространенным способом является разбиение объектов/сцены с использованием графа сцены или, более конкретно, иерархии ограничивающих объемов , например, деревьев OBB . Основная идея этого заключается в организации сцены в древовидной структуре, где корень включает всю сцену, а каждый лист содержит меньшую подчасть. [1]
В компьютерном стереозрении ограничивающий объем, реконструированный из силуэтов объекта, называется « визуальной оболочкой ». [2]
Выбор типа ограничивающего объема для данного приложения определяется множеством факторов: вычислительная стоимость вычисления ограничивающего объема для объекта, стоимость его обновления в приложениях, в которых объекты могут перемещаться или менять форму или размер, стоимость определения пересечений и желаемая точность теста пересечения. Точность теста пересечения связана с объемом пространства внутри ограничивающего объема, не связанного с ограниченным объектом, называемого пустотным пространством . Сложные ограничивающие объемы обычно допускают меньше пустотного пространства, но являются более вычислительно затратными. Обычно несколько типов используются совместно, например, дешевый для быстрого, но грубого теста в сочетании с более точным, но и более дорогим типом.
Все рассматриваемые здесь типы дают выпуклые ограничивающие объемы. Если известно, что ограничиваемый объект является выпуклым, это не является ограничением. Если требуются невыпуклые ограничивающие объемы, подход состоит в том, чтобы представить их как объединение нескольких выпуклых ограничивающих объемов. К сожалению, тесты пересечения быстро становятся более дорогими по мере того, как ограничивающие прямоугольники становятся более сложными.
Ограничивающий ящик или минимальный ограничивающий ящик ( MBB ) — это кубоид , или в 2D прямоугольник , содержащий объект. В динамическом моделировании ограничивающие ящики предпочтительнее других форм ограничивающего объема, таких как ограничивающие сферы или цилиндры, для объектов, которые имеют приблизительно кубоидную форму, когда тест на пересечение должен быть достаточно точным. Преимущество очевидно, например, для объектов, которые покоятся на других, таких как автомобиль, стоящий на земле: ограничивающая сфера показала бы, что автомобиль, возможно, пересекается с землей, что затем должно было бы быть отклонено более дорогим тестом фактической модели автомобиля; ограничивающий ящик немедленно показывает, что автомобиль не пересекается с землей, что экономит более дорогой тест.
Минимальный ограничивающий прямоугольник ( MBR ) – наименьший AABB в 2-D – часто используется в описании географических (или «геопространственных») элементов данных, выступая в качестве упрощенного прокси для пространственной протяженности набора данных (см. геопространственные метаданные ) с целью поиска данных (включая пространственные запросы, если применимо) и отображения. Он также является базовым компонентом метода R -tree пространственного индексирования .
Во многих приложениях ограничивающая рамка выровнена с осями системы координат, и тогда она известна как ограничивающая рамка, выровненная по осям (AABB ). Чтобы отличить общий случай от AABB, произвольный ограничивающий прямоугольник иногда называюториентированным ограничивающим прямоугольником(OBB ) илиOOBB , когда используется локальная система координатсуществующего объекта. AABB гораздо проще проверить на пересечение, чем OBB, но у них есть недостаток: когда модель поворачивается, их нельзя просто повернуть вместе с ней, а нужно пересчитать.
АОграничивающая капсула — это сфера, охватываемая стрелой (т. е. объем, который сфера занимает при движении вдоль прямолинейного сегмента), содержащая объект. Капсулы могут быть представлены радиусом сферы, охватываемой стрелой, и сегментом, который сфера охватывает). Она имеет черты, похожие на цилиндр, но ее проще использовать, поскольку тест на пересечение проще. Капсула и другой объект пересекаются, если расстояние между определяющим сегментом капсулы и некоторой особенностью другого объекта меньше радиуса капсулы. Например, две капсулы пересекаются, если расстояние между сегментами капсул меньше суммы их радиусов. Это справедливо для произвольно повернутых капсул, поэтому на практике они более привлекательны, чем цилиндры.
Аограничивающий цилиндр — этоцилиндр,содержащий объект. В большинстве приложений ось цилиндра выровнена с вертикальным направлением сцены. Цилиндры подходят для трехмерных объектов, которые могут вращаться только вокруг вертикальной оси, но не вокруг других осей, и в противном случае ограничены перемещением только путем трансляции. Два выровненных по вертикальной оси цилиндра пересекаются, когда одновременно пересекаются их проекции на вертикальную ось — которые являются двумя отрезками линии — а также их проекции на горизонтальную плоскость — два круглых диска. Оба варианта легко проверить. Ввидеоиграхограничивающие цилиндры часто используются в качестве ограничивающих объемов для людей, стоящих прямо.
АОграничивающий эллипсоид — этоэллипсоид, содержащий объект. Эллипсоиды обычно обеспечивают более плотное прилегание, чем сфера. Пересечения с эллипсоидами выполняются путем масштабирования другого объекта вдольглавных осейэллипсоида на величину, равнуюмультипликативной обратной величинерадиусов эллипсоида, таким образом сводя задачу к пересечению масштабированного объекта сединичной сферой. Следует проявлять осторожность, чтобы избежать проблем, если применяемое масштабирование вносит перекос. Перекос может сделать использование эллипсоидов непрактичным в определенных случаях, например, при столкновении двух произвольных эллипсоидов.
Ограничивающая сфера — это сфера , содержащая объект. В 2-D графике это окружность . Ограничивающие сферы представлены центром и радиусом. Их очень быстро проверяют на столкновение друг с другом: две сферы пересекаются, когда расстояние между их центрами не превышает суммы их радиусов. Это делает ограничивающие сферы подходящими для объектов, которые могут двигаться в любом количестве измерений.
АОграничивающая плита — это объем, который проецируется на ось, и может рассматриваться как плита,ограниченнаядвумя плоскостями. Ограничивающий ящик — это пересечение ортогонально ориентированных ограничивающих плит. Ограничивающие плиты использовались для ускорениятрассировки лучей[3]
АОграничивающий треугольник в 2-D весьма полезен для ускорения теста отсечения или видимости кривой B-сплайна. См."Алгоритмы отсечения окружности и B-сплайнов"в теме Отсечения (компьютерная графика) для примера использования.
Выпуклая оболочка — это наименьший выпуклый объем, содержащий объект. Если объект является объединением конечного множества точек, его выпуклая оболочка — многогранник.
АДискретный ориентированный многогранник (DOP) обобщает ограничивающий параллелепипед. K-DOP — это булево пересечение экстентов вдольkнаправлений. Таким образом,k-DOP — это булево пересечениеkограничивающих плит и является выпуклыммногогранником,содержащим объект (в 2-D многоугольник;в 3-Dмногогранник). Двумерный прямоугольник — это частный случай 2-DOP, а трехмерный параллелепипед — частный случай 3-DOP. В общем случае оси DOP не обязательно должны быть ортогональными, и осей может быть больше, чем измерений пространства. Например, трехмерный параллелепипед, скошенный по всем ребрам и углам, может быть построен как 13-DOP. Фактическое количество граней может быть меньше, чем 2 раза поk,если некоторые грани вырождаются, сжимаются до ребра или вершины.
Для некоторых типов ограничивающего объема (OBB и выпуклые многогранники) эффективной проверкой является проверка теоремы о разделяющей оси . Идея здесь заключается в том, что если существует ось, по которой объекты не перекрываются, то объекты не пересекаются. Обычно проверяемые оси — это оси основных осей для объемов (единичные оси в случае AABB или 3 базовые оси от каждого OBB в случае OBB). Часто за этим следует также проверка перекрестных произведений предыдущих осей (одна ось от каждого объекта).
В случае AABB эти тесты становятся простым набором тестов перекрытия в терминах единичных осей. Для AABB , определенного M , N, против определенного O , P они не пересекаются, если ( M x > P x ) или ( O x > N x ) или ( M y > P y ) или ( O y > N y ) или ( M z > P z ) или ( O z > N z ).
AABB также можно спроецировать вдоль оси, например, если он имеет ребра длиной L и центрирован в точке C , и проецируется вдоль оси N: , и или , и
где m и n — минимальная и максимальная протяженность.
OBB в этом отношении похож, но немного сложнее. Для OBB с L и C, как указано выше, и с I , J и K в качестве базовых осей OBB, тогда:
Для диапазонов m , n и o , p можно сказать, что они не пересекаются, если m > p или o > n . Таким образом, проецируя диапазоны 2 OBB вдоль осей I, J и K каждого OBB и проверяя на непересечение, можно обнаружить непересечение. Дополнительно проверяя вдоль перекрестных произведений этих осей (I 0 ×I 1 , I 0 ×J 1 , ...) можно быть более уверенным, что пересечение невозможно.
Эта концепция определения непересечения с помощью использования проекции осей также распространяется на выпуклые многогранники, однако с использованием нормалей каждой многогранной грани вместо базовых осей, и с экстентами, основанными на минимальном и максимальном скалярном произведении каждой вершины на оси. Обратите внимание, что это описание предполагает, что проверки выполняются в мировом пространстве.
Пересечение двух k -DOP может быть вычислено очень похоже на AABB: для каждой ориентации вы просто проверяете два соответствующих интервала двух DOP. Таким образом, так же, как DOP являются обобщением AABB, тест пересечения является обобщением теста перекрытия AABB. Сложность теста перекрытия двух DOP составляет O( k ) . Однако это предполагает, что оба DOP заданы относительно одного и того же набора ориентаций. Если один из них повернут, это уже не так. В этом случае один относительно простой способ проверить два DOP на пересечение — это охватить повернутую, , другим, наименьшим охватывающим DOP , который ориентирован относительно ориентаций первого DOP . Процедура для этого немного сложнее, но в конечном итоге сводится к умножению матрицы на вектор со сложностью O( k ) . [4]
