Граничный объем

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

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

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

Использование

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

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

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

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

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

В компьютерном стереозрении ограничивающий объем, воссозданный из силуэтов объекта, известен как « визуальная оболочка ». ^[2]

Распространенные типы

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

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

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

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

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

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

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

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

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

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

А Ограничивающий треугольник в 2D весьма полезен для ускорения проверки отсечения или видимости кривой 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, в сравнении с AABB, определенным 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:
$r=0.5L_{x}|N_{x}|+0.5L_{y}|N_{y}|+0.5L_{z}|N_{z}|\,$ , и $b=C*N\,$ или $b=C_{x}N_{x}+C_{y}N_{y}+C_{z}N_{z}\,$ , и $m=b-r,n=b+r\,$ где m и n — минимальная и максимальная протяженность.

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

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

m=C*N-r{\mbox{ and }}n=C*N+r\,

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

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

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

См. также

Ссылки

^ Клосовски, Джеймс Т.; Держись, Мартин; Митчелл, Джозеф С.Б .; Совизрал, Генри; Зикан, Карел (1998). «Эффективное обнаружение столкновений с использованием иерархий граничных объемов k-DOP». Транзакции IEEE по визуализации и компьютерной графике . 4 (1): 21–36. дои : 10.1109/2945.675649 .
^ Эрол, Али и др. « Визуальное построение корпуса с использованием адаптивной выборки ». WACV/ДВИЖЕНИЕ. 2005.
^ POV-Ray Документация [1]
^ Г. Захманн: Быстрое обнаружение столкновений с помощью динамически выровненных DOP-деревьев. Учеб. Ежегодного международного симпозиума IEEE по виртуальной реальности (VRAIS, теперь IEEE VR), 1998, стр. 90–97, DOI 10.1109/VRAIS.1998.658428, ISBN 0-8186-8362-7 URL: http://cgvr.informatik.uni-bremen.de/papers/vrais98/vrais98.pdf

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

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

[1] Клосовски, Джеймс Т.; Держись, Мартин; Митчелл, Джозеф С.Б .; Совизрал, Генри; Зикан, Карел (1998). «Эффективное обнаружение столкновений с использованием иерархий граничных объемов k-DOP». Транзакции IEEE по визуализации и компьютерной графике . 4 (1): 21–36. дои : 10.1109/2945.675649 .

[2] Эрол, Али и др. « Визуальное построение корпуса с использованием адаптивной выборки ». WACV/ДВИЖЕНИЕ. 2005.

[3] POV-Ray Документация [1]

[4] Г. Захманн: Быстрое обнаружение столкновений с помощью динамически выровненных DOP-деревьев. Учеб. Ежегодного международного симпозиума IEEE по виртуальной реальности (VRAIS, теперь IEEE VR), 1998, стр. 90–97, DOI 10.1109/VRAIS.1998.658428, ISBN 0-8186-8362-7 URL: http://cgvr.informatik.uni-bremen.de/papers/vrais98/vrais98.pdf

[1]

[2]

[3]

[4]