Ограничивающий объем в компьютерной графике

Введение

Закрытый объем, полностью содержащий объединение набора объектов.

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

Применение

Ограничивающие объемы чаще всего используются для ускорения определенных видов проверок. В трассировке лучей ограничивающие объемы используются в тестах пересечения лучей, а во многих алгоритмах рендеринга – для проверок на вхождение во фрустум обзора. Если луч или фрустум обзора не пересекают ограничивающий объем, то они не могут пересечь и содержащийся в нем объект, что позволяет выполнить тривиальное отклонение. Аналогично, если фрустум обзора полностью содержит ограничивающий объем, его содержимое можно принять без дальнейших проверок. Эти тесты пересечения формируют список объектов, которые необходимо "отобразить" (рендерить; растрировать). При обнаружении столкновений, если два ограничивающих объема не пересекаются, содержащиеся в них объекты не могут столкнуться. Проверка на пересечение с ограничивающим объемом обычно намного быстрее, чем проверка на пересечение с самим объектом, из-за более простой геометрии ограничивающего объема. Это связано с тем, что "объект" обычно состоит из многоугольников или структур данных, которые приводятся к полигональным аппроксимациям. В любом случае, вычислительно неэффективно проверять каждый многоугольник на пересечение с объемом видимости, если объект не виден. (Объекты на экране должны быть "отсечены" по экрану, независимо от того, видны их поверхности.) Для получения ограничивающих объемов сложных объектов распространенным способом является разбиение объектов/сцены с использованием графа сцены или, более конкретно, иерархии ограничивающих объемов, например, деревьев OBB. Основная идея заключается в организации сцены в древовидную структуру, где корень охватывает всю сцену, а каждый лист содержит меньшую подчасть. В компьютерном стереовидении ограничивающий объем, восстановленный из силуэтов объекта, известен как "визуальная оболочка".

Общие типы

Выбор типа ограничивающего объема для конкретного приложения определяется множеством факторов: вычислительные затраты на вычисление ограничивающего объема для объекта, стоимость его обновления в приложениях, где объекты могут перемещаться или изменять форму или размер, стоимость определения пересечений и требуемая точность теста на пересечение. Точность теста на пересечение связана с количеством пространства внутри ограничивающего объема, не занятого ограничиваемым объектом, которое называется пустым пространством. Более сложные ограничивающие объемы обычно обеспечивают меньшее пустое пространство, но требуют больших вычислительных затрат. Часто используют несколько типов в сочетании, например, недорогой для быстрой, но приблизительной проверки в сочетании с более точным, но и более дорогим типом. Все рассматриваемые здесь типы дают выпуклые ограничивающие объемы. Если ограничиваемый объект известен как выпуклый, это не является ограничением. Если требуются невыпуклые ограничивающие объемы, их можно представить как объединение нескольких выпуклых ограничивающих объемов. К сожалению, тесты на пересечение быстро становятся дороже по мере усложнения ограничивающих объемов. Ограничивающая коробка или минимальная ограничивающая коробка (MBB) — это кубоид или, в 2D, прямоугольник, содержащий объект. В динамическом моделировании ограничивающие коробки предпочтительнее других форм ограничивающих объемов, таких как ограничивающие сферы или цилиндры, для объектов, имеющих примерно кубическую форму, когда тест на пересечение должен быть достаточно точным. Преимущество очевидно, например, для объектов, опирающихся на другие, таких как автомобиль, стоящий на земле: ограничивающая сфера может показать, что автомобиль потенциально пересекается с землей, что потребует более дорогой проверки фактической модели автомобиля; ограничивающая коробка сразу же покажет, что автомобиль не пересекается с землей, что позволит избежать более дорогой проверки. Минимальный ограничивающий прямоугольник (MBR) — наименьший AABB в 2D — часто используется в описании географических (или "геопространственных") элементов данных, служа упрощенным представлением пространственного охвата набора данных (см. геопространственные метаданные) для целей поиска данных (включая пространственные запросы, если применимо) и отображения. Он также является основным компонентом метода R-дерева пространственной индексации. Во многих приложениях ограничивающая коробка выровнена по осям системы координат, и в этом случае она известна как ограничивающая коробка с выровненными осями (AABB). Чтобы отличить общий случай от AABB, произвольную ограничивающую коробку иногда называют ориентированной ограничивающей коробкой (OBB) или OOBB, когда используется локальная система координат существующего объекта. AABB намного проще проверять на пересечение, чем OBB, но у них есть недостаток: при вращении модели их нельзя просто вращать вместе с ней, их необходимо пересчитывать. Ограничивающая капсула — это сфера, "проведенная" по прямой линии (то есть объем, занимаемый сферой при движении по прямолинейному сегменту), содержащая объект. Капсулы можно представить радиусом сферы и сегментом, по которому она перемещается. Она имеет свойства, схожие с цилиндром, но ее проще использовать, поскольку тест на пересечение проще. Капсула и другой объект пересекаются, если расстояние между определяющим сегментом капсулы и какой-либо точкой другого объекта меньше радиуса капсулы. Например, две капсулы пересекаются, если расстояние между их сегментами меньше суммы их радиусов. Это справедливо для произвольно повернутых капсул, поэтому они более предпочтительны, чем цилиндры, на практике. Ограничивающий цилиндр — это цилиндр, содержащий объект. В большинстве приложений ось цилиндра выровнена с вертикальным направлением сцены. Цилиндры подходят для 3D-объектов, которые могут вращаться только вокруг вертикальной оси, но не вокруг других осей, и в противном случае ограничены только перемещением. Два вертикальных цилиндра, выровненных по оси, пересекаются, когда одновременно их проекции на вертикальную ось пересекаются (это два отрезка прямых), а также их проекции на горизонтальную плоскость (два круговых диска). Оба теста просты в реализации. В видеоиграх ограничивающие цилиндры часто используются в качестве ограничивающих объемов для людей, стоящих прямо. Ограничивающий эллипсоид — это эллипсоид, содержащий объект. Эллипсоиды обычно обеспечивают более плотное прилегание, чем сфера. Пересечения с эллипсоидами выполняются путем масштабирования другого объекта вдоль главных осей эллипсоида на величину, равную обратной величине радиусов эллипсоида, тем самым сводя задачу к пересечению масштабированного объекта с единичной сферой. Следует соблюдать осторожность, чтобы избежать проблем, если применяемое масштабирование вносит искажение. Искажение может сделать использование эллипсоидов непрактичным в определенных случаях, например, при столкновении двух произвольных эллипсоидов. Ограничивающая сфера — это сфера, содержащая объект. В 2D-графике это круг. Ограничивающие сферы представляются центром и радиусом. Они очень быстро проверяются на столкновение друг с другом: две сферы пересекаются, когда расстояние между их центрами не превышает сумму их радиусов. Это делает ограничивающие сферы подходящими для объектов, которые могут перемещаться в любом количестве измерений. Ограничивающая плоскость — это объем, который проецируется на протяженность по оси и может рассматриваться как плоскость, ограниченная двумя плоскостями. Ограничивающая коробка является пересечением ортогонально ориентированных ограничивающих плоскостей. Ограничивающие плоскости использовались для ускорения трассировки лучей.

The choice of the type of bounding volume for a given application is determined by a variety of factors: the computational cost of computing a bounding volume for an object, the cost of updating it in applications in which the objects can move or change shape or size, the cost of determining intersections, and the desired precision of the intersection test. The precision of the intersection test is related to the amount of space within the bounding volume not associated with the bounded object, called void space. Sophisticated bounding volumes generally allow for less void space but are more computationally expensive. It is common to use several types in conjunction, such as a cheap one for a quick but rough test in conjunction with a more precise but also more expensive type. The types treated here all give convex bounding volumes. If the object being bounded is known to be convex, this is not a restriction. If non convex bounding volumes are required, an approach is to represent them as a union of a number of convex bounding volumes. Unfortunately, intersection tests become quickly more expensive as the bounding boxes become more sophisticated. A bounding box or minimum bounding box (MBB) is a cuboid, or in 2 D a rectangle, containing the object. In dynamical simulation, bounding boxes are preferred to other shapes of bounding volume such as bounding spheres or cylinders for objects that are roughly cuboid in shape when the intersection test needs to be fairly accurate. The benefit is obvious, for example, for objects that rest upon other, such as a car resting on the ground: a bounding sphere would show the car as possibly intersecting with the ground, which then would need to be rejected by a more expensive test of the actual model of the car; a bounding box immediately shows the car as not intersecting with the ground, saving the more expensive test. A minimum bounding rectangle (MBR) – the least AABB in 2 D – is frequently used in the description of geographic (or "geospatial") data items, serving as a simplified proxy for a dataset's spatial extent (see geospatial metadata) for the purpose of data search (including spatial queries as applicable) and display. It is also a basic component of the R tree method of spatial indexing. In many applications the bounding box is aligned with the axes of the co ordinate system, and it is then known as an axis aligned bounding box (AABB). To distinguish the general case from an AABB, an arbitrary bounding box is sometimes called an oriented bounding box (OBB), or an OOBB when an existing object's local coordinate system is used. AABBs are much simpler to test for intersection than OBBs, but have the disadvantage that when the model is rotated they cannot be simply rotated with it, but need to be recomputed. A bounding capsule is a swept sphere (i. e. the volume that a sphere takes as it moves along a straight line segment) containing the object. Capsules can be represented by the radius of the swept sphere and the segment that the sphere is swept across). It has traits similar to a cylinder, but is easier to use, because the intersection test is simpler. A capsule and another object intersect if the distance between the capsule's defining segment and some feature of the other object is smaller than the capsule's radius. For example, two capsules intersect if the distance between the capsules' segments is smaller than the sum of their radii. This holds for arbitrarily rotated capsules, which is why they're more appealing than cylinders in practice. A bounding cylinder is a cylinder containing the object. In most applications the axis of the cylinder is aligned with the vertical direction of the scene. Cylinders are appropriate for 3 D objects that can only rotate about a vertical axis but not about other axes, and are otherwise constrained to move by translation only. Two vertical axis aligned cylinders intersect when, simultaneously, their projections on the vertical axis intersect – which are two line segments – as well their projections on the horizontal plane – two circular disks. Both are easy to test. In video games, bounding cylinders are often used as bounding volumes for people standing upright. A bounding ellipsoid is an ellipsoid containing the object. Ellipsoids usually provide tighter fitting than a sphere. Intersections with ellipsoids are done by scaling the other object along the principal axes of the ellipsoid by an amount equal to the multiplicative inverse of the radii of the ellipsoid, thus reducing the problem to intersecting the scaled object with a unit sphere. Care should be taken to avoid problems if the applied scaling introduces skew. Skew can make the usage of ellipsoids impractical in certain cases, for example collision between two arbitrary ellipsoids. A bounding sphere is a sphere containing the object. In 2 D graphics, this is a circle. Bounding spheres are represented by centre and radius. They are very quick to test for collision with each other: two spheres intersect when the distance between their centres does not exceed the sum of their radii. This makes bounding spheres appropriate for objects that can move in any number of dimensions. A bounding slab is the volume that projects to an extent on an axis, and can be thought of as the slab bounded between two planes. A bounding box is the intersection of orthogonally oriented bounding slabs. Bounding slabs have been used to speed up ray tracing

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