На правах рекламы:
ISSN 0236-235X (P)
ISSN 2311-2735 (E)

Авторитетность издания

ВАК - К1
RSCI, ядро РИНЦ

Добавить в закладки

Следующий номер на сайте

2
Ожидается:
16 Июня 2024

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

Collision detection for bounding spheres and rectangular parallelepipeds in 3d modeling systems
Дата подачи статьи: 27.07.2015
УДК: 004.921
Статья опубликована в выпуске журнала № 4 за 2015 год. [ на стр. 105-109 ]
Аннотация:В системах трехмерного моделирования виртуальные объекты могут сталкиваться друг с другом. Определение таких столкновений (коллизий) является неотъемлемой частью любого физического движка. Для физических движков важнейшую роль играет скорость их расчетов. Для поддержки режима реального времени расчеты одного кадра моделирования не должны превышать 40 мс для обеспечения визуализации не менее 25 кадров в секунду, поэтому к системе расчета динамики в целом и к определениям коллизий в частности предъявляется требование разработки быстрых и эффективных алгоритмов. Определение коллизий объектов произвольной формы – трудная задача, имеющая высокую вычислительную сложность, поэтому широко применяется метод определения коллизий при помощи аппроксимирующих контейнеров. В этом случае формы виртуальных объектов описываются (аппроксимируются) различными геометрическими примитивами и задача определения коллизий самих объектов сводится к определению коллизий их аппроксимирующих контейнеров. Широкое распространение получили такие примитивы, как прямоугольные параллелепипеды и сферы. Алгоритмы определения коллизий бывают априорными и апостериорными. Априорные алгоритмы предсказывают коллизии тел, а апостериорные определяют коллизии уже по факту пересечения самих объектов. При этом априорные алгоритмы в общем случае обладают значительно большей вычислительной сложностью ввиду большего объема входных данных. В связи с этим в физических движках, ориентированных на моделирование динамики в режиме реального времени, в основном используются апостериорные алгоритмы определения коллизий. Настоящая работа посвящена разработке быстрых и эффективных апостериорных алгоритмов определения коллизий сфер между собой и сфер с прямоугольными параллелепипедами.
Abstract:Virtual objects in 3D modeling systems may collide with each other. Collision detection is an integral part of any physical engine. The speed of calculation is crucial for physical engines. In real -time mode one simulation frame calculations should not exceed 40 ms to visualize at least 25 frames per second. Therefore, there is a need in development of fast and efficient algorithms for the dynamics calculation system and for collision detection in particular. Collision detection of complex shape\'s objects is a difficult task, which has a high computational complexity. Therefore, a method using bounding volumes is widely used. In this case, virtual objects forms are described by as different geometric primitives, and the problem of objects\' collision detection is reduced to the collision detection of their bounding volumes. Such primitives as rectangular parallelepipeds (boxes) and spheres became widespread. Collision detection algorithms may be a priori and a posteriori. A priori algorithms predict collisions of bodies, and a posteriori algorithms detect collisions after actual intersections of the objects. In general, a priori algorithms have much higher computational complexity due to the greater amount of input data. In this regard, physics engines oriented on real-time dynamics modeling basically use a posteriori collision detection algorithms. This work is devoted to the development of fast and efficient algorithms for a posteriori sphere-sphere and sphere-box collision detection.
Авторы: Трушин А.М. (leha_trushin@mail.ru) - ФНЦ НИИСИ РАН (научный сотрудник), Москва, Россия
Ключевые слова: моделирование динамики, аппроксимирующие контейнеры, определение коллизий
Keywords: dynamics modeling, approximating containers, collision detection
Количество просмотров: 6040
Версия для печати
Выпуск в формате PDF (9.58Мб)
Скачать обложку в формате PDF (1.29Мб)

Размер шрифта:       Шрифт:

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

Алгоритмы определения коллизий делятся на два вида: априорные и апостериорные [4]. Априорные алгоритмы предсказывают столкновения тел, апостериорные определяют коллизию объектов уже по факту их столкновения. В общем случае априорные алгоритмы обладают большей точностью вычисления информации о коллизии, но их существенным недостатком является большая вычислительная сложность, связанная с большим объемом входных данных (положение и ориентация объектов, а также их физические параметры: скорость, сила, моменты и т.д.). В связи с этим системы динамики, основанные на априорных определениях коллизий, работают в режиме реального времени (не менее 25 шагов моделирования в секунду) лишь для небольшого числа виртуальных объектов. Для апостериорных алгоритмов опреде- ления коллизий входной объем данных сводится только к положению и ориентации объектов.

В настоящей работе рассматриваются методы апостериорного определения коллизий двух сфер и сферы с прямоугольным параллелепипедом (боксом). Коллизии боксов между собой рассмотрены в [5].

Понятие коллизии

В данной работе будут использоваться правосторонние системы координат. Для каждого ап­проксимирующего контейнера задается матрица перехода из его локальной системы координат в мировую [6]. Первые три столбца этой матрицы задают ориентацию тела, а четвертый – положение начала локальной системы координат тела в мировой системе координат.

Обозначим радиус сферы через r, а начало ее локальной системы координат расположим в центре сферы.

Размеры бокса задаются величинами l (половина длины), w (половина ширины) и h (высота). Начало локальной системы координат расположим в центре нижней грани бокса так, что ось x направлена параллельно ребру бокса, задающему его длину, ось y – ширину, а ось z – высоту.

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

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

Обозначим через P точку коллизии. Пусть O1 и O2 – положение центров первого и второго объектов в мировой системе координат, а M1 и M2 – соответствующие матрицы перехода. Если вторым объектом является сфера, то ее центр задается четвертым столбцом матрицы M2, если же бокс, то к координате z четвертого столбца надо прибавить h/2 (так как начало системы координат бокса распо­ла­гается в центре нижнего основания). Тогда нормаль коллизии определим вектором

,                                        (1)

а глубину коллизии величиной

.                                                 (2)

Определение коллизии двух сфер

Две сферы пересекаются тогда и только тогда, когда сумма их радиусов больше или равна расстоянию между их центрами (см. рис. 1), то есть |O1 – O2| <= r1 + r2.

Если сферы пересекаются, то точка коллизии лежит на поверхности второй сферы на прямой, соединяющей их центры: .

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

Тогда из (2) получаем, что глубина коллизии в первом случае будет , а во втором – .

Определение коллизии сферы с прямоугольным параллелепипедом

Для определения коллизии сферы и бокса обозначим через Q точку на поверхности бокса, ближайшую к центру сферы. Рассмотрим всевозможные варианты расположения центра сферы относительно бокса (см. рис. 2).

1. Центр сферы расположен точно над одной из граней бокса. Тогда точкой Q является конец перпендикуляра, опущенного из центра сферы к этой грани (точка Q1 на рисунке 2).

2. Центр сферы расположен по диагонали от одного из ребер бокса, то есть вне двух соседних граней, содержащих это ребро. Тогда точкой Q является конец перпендикуляра, опущенного из центра сферы к этому ребру бокса (точка Q2 на рисунке 2).

3. Центр сферы расположен по диагонали от одной из вершин бокса, то есть вне трех соседних граней, содержащих эту вершину. Тогда точкой Q будет эта вершина бокса (точка Q3 на рисунке 2).

4. Центр сферы лежит внутри бокса. Тогда точкой Q является конец перпендикуляра, опущенного из центра сферы к ближайшей грани бокса (точка Q4 на рисунке 2).

Обозначим через E1 систему координат сферы, а через E2 систему координат бокса. Рассмотрим достаточно быстрый алгоритм, позволяющий определить положение центра сферы относительно бокса. Причем, если центр сферы лежит вне бокса, алгоритм сразу вычисляет точку Q. Суть алгоритма – перевод вектора  из мировой системы координат в систему E2 и его покомпонентное сравнение с полуразмерами бокса. Обозначим совокупность координат вектора  в системе координат E2 через . Получим .

Тогда с использованием компонент x, y и z вектора  алгоритм будет следующим.

Если , то

,

иначе, если , то

.

Если , то

,

иначе, если , то

.

Если , то

,

иначе, если , то

.

Если выполняется хотя бы одно из данных условий, значит, центр сферы лежит вне бокса. Тогда точка Q в системе координат E2 будет , а в мировой  .

Если не выполнилось ни одно из условий, значит, центр сферы лежит внутри бокса. Рассмотрим отдельно оба случая.

Центр сферы лежит вне бокса. Сфера и бокс пересекаются тогда и только тогда, когда радиус сферы больше расстояния от ее центра О1 до точки Q, то есть |O1 – Q| £ r1.

Если сфера и бокс пересекаются, точка кол- лизии Р будет совпадать с Q. Ясно, что соответствующие координаты векторов  и  в системе E2 имеют одинаковые знаки, поэтому . Тогда из (1) следует, что  совпадет по направлению с  (то есть будет соответствовать направлению расталкивания сферы), а из (2) получаем

Центр сферы лежит внутри бокса. В этом случае вектор  будет соединять центр бокса с центром сферы (см. рис. 3).

Вычислим направление  и расстояние min от центра сферы до ближайшей грани бокса:

,.

Если , то

, .

Если , то

,

.

Тогда точка коллизии .

Проверим, что направление нормали (1) будет противоположно направлению вектора , то есть будет правильным для расталкивания первого объекта. Ясно, что косинус угла между векторами  и  отрицательный, то есть . Следовательно, направление нормали будет противоположно направлению . Тогда из (2) получаем, что в этом случае глубина коллизии .

В заключение отметим, что рассмотренные алгоритмы определения коллизий двух сфер между собой и сферы с прямоугольным параллелепипедом позволяют вычислять информацию о коллизиях с небольшой вычислительной сложностью. Вместе с обработкой коллизий, описанной в [7], это позволяет моделировать динамику в режиме реального времени большого (вплоть до нескольких тысяч) количества виртуальных объектов. Данные алгоритмы были реализованы в рамках динамической библиотеки, входящей в состав существующей системы трехмерного моделирования виртуальных объектов. За счет наличия в этой системе модуля визуализации [8, 9] реализованные алгоритмы были проверены на наборе тестовых сцен, имитирующих различные ситуации при столкновении виртуальных объектов. Особое внимание было уделено сложной в плане моделирования динамики ситуации покоя множества тел друг на друге (см. рис. 4). Сложность такой ситуации при моделировании динамики в том, что на тела постоянно действует сила тяжести. Таким образом, тела постоянно стремятся проникать друг в друга, а подсистема определения и обработки коллизий этому противодействует. До тех пор, пока в этой подсистеме получаемые расчеты по обработке коллизий не полностью удовлетворяют условию покоя всех тел одновременно, объекты совершают небольшие движения вверх-вниз (подрагивают).

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

Литература

1.     Moore M., Wilhelms J. Collision Detection and Response for Computer Animation. Computer Graphics, 1998, vol. 22, no. 4, pp. 289–298; URL: http://www.cs.princeton.edu/courses/archive/ spring01/cs598b/papers/moore88.pdf (дата обращения: 10.07.2015).

2.     Ming C. Lin, Gottschalk S. Collision detection between geometric models: a survey. Proc. of IMA conference on mathematics of surfaces. 1998, vol. 1, pp. 602–608; URL: https://us­ers.soe.ucsc.edu/~pang/161/w06/notes/cms98.pdf (дата обращения: 10.07.2015).

3.     Bounding volume. URL: https://en.wikipedia.org/wiki/Bo­unding_volume (дата обращения: 10.07.2015).

4.     Ericson C. Real-Time Collision Detection. CRC Press, 2004, 594 p.; URL: https://books.google.ru/books?id=WGpL6 Sk9qNAC (дата обращения: 10.07.2015).

5.     Михайлюк М.В., Трушин А.М. Расчет коллизий прямоугольных параллелепипедов в задачах динамики // Труды НИИСИ РАН. Т. 2. № 2. Обработка изображений, моделирование и визуализация: теоретические и прикладные аспекты. 2012. С. 51–59.

6.     Transformation matrix. URL: https://en.wikipedia.org/wi­ki/Transformation_matrix (дата обращения: 10.07.2015).

7.     Трушин А.М. Обработка коллизий виртуальных объектов с помощью метода последовательных импульсов // Труды НИИСИ РАН. Т. 4. № 2. Математическое и компьютерное моделирование сложных систем: теоретические и прикладные аспекты. 2014. С. 95–105.

8.     Михайлюк М.В., Торгашев М.А. Система «GLVIEW» визуализации для моделирующих комплексов и систем виртуальной реальности // Вестн. РАЕН. 2011. № 2. C. 20–28.

9.     Михайлюк М.В., Торгашев М.А. Визуализация динамики объектов управления в реальном времени // Научная визуализация. 2014. Т. 6. № 5. C. 69–80; URL: http://sv-jour­nal.org/2014-5/index2139.html?lang=ru (дата обращения: 10.07.2015).


Постоянный адрес статьи:
http://swsys.ru/index.php?page=article&id=4077&lang=
Версия для печати
Выпуск в формате PDF (9.58Мб)
Скачать обложку в формате PDF (1.29Мб)
Статья опубликована в выпуске журнала № 4 за 2015 год. [ на стр. 105-109 ]

Возможно, Вас заинтересуют следующие статьи схожих тематик: