close

Вход

Забыли?

вход по аккаунту

?

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

код для вставкиСкачать
Программные продукты и системы / Software & Systems
УДК 004.921
DOI: 10.15827/0236-235X.112.105-109
№ 4 (112), 2015
Дата подачи статьи: 27.07.15
ОПРЕДЕЛЕНИЕ КОЛЛИЗИЙ АППРОКСИМИРУЮЩИХ СФЕР
И ПРЯМОУГОЛЬНЫХ ПАРАЛЛЕЛЕПИПЕДОВ
В СИСТЕМАХ ТРЕХМЕРНОГО МОДЕЛИРОВАНИЯ
(Исследования выполнены при поддержке РФФИ, грант № 13-07-00708)
А.М. Трушин, научный сотрудник, leha_trushin@mail.ru
(ФНЦ НИИСИ РАН, Нахимовский просп., 36, корп. 1, г. Москва, 117218, Россия)
В системах трехмерного моделирования виртуальные объекты могут сталкиваться друг с другом. Определение
таких столкновений (коллизий) является неотъемлемой частью любого физического движка. Для физических движков
важнейшую роль играет скорость их расчетов. Для поддержки режима реального времени расчеты одного кадра моделирования не должны превышать 40 мс для обеспечения визуализации не менее 25 кадров в секунду, поэтому к
системе расчета динамики в целом и к определениям коллизий в частности предъявляется требование разработки
быстрых и эффективных алгоритмов. Определение коллизий объектов произвольной формы – трудная задача, имеющая высокую вычислительную сложность, поэтому широко применяется метод определения коллизий при помощи
аппроксимирующих контейнеров. В этом случае формы виртуальных объектов описываются (аппроксимируются) различными геометрическими примитивами и задача определения коллизий самих объектов сводится к определению
коллизий их аппроксимирующих контейнеров. Широкое распространение получили такие примитивы, как прямоугольные параллелепипеды и сферы. Алгоритмы определения коллизий бывают априорными и апостериорными.
Априорные алгоритмы предсказывают коллизии тел, а апостериорные определяют коллизии уже по факту пересечения самих объектов. При этом априорные алгоритмы в общем случае обладают значительно большей вычислительной
сложностью ввиду большего объема входных данных. В связи с этим в физических движках, ориентированных на
моделирование динамики в режиме реального времени, в основном используются апостериорные алгоритмы определения коллизий. Настоящая работа посвящена разработке быстрых и эффективных апостериорных алгоритмов определения коллизий сфер между собой и сфер с прямоугольными параллелепипедами.
Ключевые слова: определение коллизий, аппроксимирующие контейнеры, моделирование динамики.
К важнейшим задачам при моделировании динамики трехмерных виртуальных объектов (тел)
относятся определение и обработка их столкновений (коллизий) [1]. Определение коллизий объектов произвольных форм является вычислительно
сложной задачей [2], поэтому широкое распространение получил метод определения коллизий, при
котором каждый динамический объект окружается
(аппроксимируется) одним или несколькими геометрическими контейнерами (параллелепипедами,
сферами и т.д.) [3]. Тогда моделирование столкновения двух тел заключается в определении параметров (точки, глубины и нормали) коллизии аппроксимирующих контейнеров двух объектов и в
задании реакции тел на это столкновение.
Алгоритмы определения коллизий делятся на
два вида: априорные и апостериорные [4]. Априорные алгоритмы предсказывают столкновения тел,
апостериорные определяют коллизию объектов
уже по факту их столкновения. В общем случае
априорные алгоритмы обладают большей точностью вычисления информации о коллизии, но их
существенным недостатком является большая вычислительная сложность, связанная с большим
объемом входных данных (положение и ориентация объектов, а также их физические параметры:
скорость, сила, моменты и т.д.). В связи с этим системы динамики, основанные на априорных определениях коллизий, работают в режиме реального
времени (не менее 25 шагов моделирования в секунду) лишь для небольшого числа виртуальных
объектов. Для апостериорных алгоритмов опреде-
ления коллизий входной объем данных сводится
только к положению и ориентации объектов.
В настоящей работе рассматриваются методы
апостериорного определения коллизий двух сфер
и сферы с прямоугольным параллелепипедом
(боксом). Коллизии боксов между собой рассмотрены в [5].
Понятие коллизии
В данной работе будут использоваться правосторонние системы координат. Для каждого аппроксимирующего контейнера задается матрица
перехода из его локальной системы координат в
мировую [6]. Первые три столбца этой матрицы задают ориентацию тела, а четвертый – положение
начала локальной системы координат тела в мировой системе координат.
Обозначим радиус сферы через r, а начало ее
локальной системы координат расположим в центре сферы.
Размеры бокса задаются величинами l (половина длины), w (половина ширины) и h (высота).
Начало локальной системы координат расположим
в центре нижней грани бокса так, что ось x направлена параллельно ребру бокса, задающему его
длину, ось y – ширину, а ось z – высоту.
Под определением коллизии пары аппроксимирующих контейнеров понимается определение
факта их пересечения и, в случае его наличия, вычисление точки коллизии, нормали расталкивания
и глубины коллизии.
105
Программные продукты и системы / Software & Systems
№ 4 (112), 2015
Точка, нормаль и глубина коллизии. В качестве
первого объекта коллизии всегда будем рассматривать сферу, а вторым объектом будет либо сфера,
либо бокс. Определим точку коллизии как точку
поверхности второго объекта, наиболее близкую к
центру первого. Под нормалью коллизии будем
подразумевать единичный вектор, направленный
вдоль прямой, проходящей через точку контакта и
центр первого объекта, и указывающий направление расталкивания для первого объекта. Глубина
коллизии – это расстояние, на которое точка коллизии проникла в первый объект вдоль нормали.
Обозначим через P точку коллизии. Пусть O1 и
O2 – положение центров первого и второго объектов в мировой системе координат, а M1 и M2 – соответствующие матрицы перехода. Если вторым
объектом является сфера, то ее центр задается четвертым столбцом матрицы M2, если же бокс, то к
координате z четвертого столбца надо прибавить
h/2 (так как начало системы координат бокса располагается в центре нижнего основания). Тогда
нормаль коллизии определим вектором
(O2 O1 , PO1 ) PO1
,
(1)
N
(O2 O1 , PO1 ) PO1
а глубину коллизии величиной
D  r1  ( N , PO1 ) .
(2)
Fig. 1.Two spheres intersection
Две сферы пересекаются тогда и только тогда,
когда сумма их радиусов больше или равна расстоянию между их центрами (см. рис. 1), то есть |O1 –
O2| <= r1 + r2.
Если сферы пересекаются, то точка коллизии
лежит на поверхности второй сферы на прямой, соOO
единяющей их центры: P  O2  r2 2 1 .
| O2 O1 |
Проверим совпадение направления нормали (1)
с направлением вектора O2 O1 , который и будет
вектором, задающим правильное направление
для расталкивания первого объекта. Рассмотрим два случая: центр O1 находится вне второй сферы (рис. 1а) и центр O1 находится внутри
второй сферы (рис. 1б). В первом случае векторы
PO1 и O2O1 направлены в одну сторону, поэто-
(O2O1 , PO1 )  0
и,
следовательно,
вектор
(O2O1 , PO1 ) PO1 также совпадает по направлению
с вектором O2 O1 , то есть направление нормали
верное. Во втором случае вектор PO1 направлен противоположно вектору
(O2O1 , PO1 )  0 .
106
Произведение
б) Центр первой сферы лежит внутри второй
Рис. 1. Пересечение двух сфер
Определение коллизии
двух сфер
му
а) Центр первой сферы лежит вне второй
O2O1 , поэтому
(O2O1 , PO1 ) PO1
даст вектор, совпадающий по направлению с вектором O2 O1 , то есть нормаль направлена верно.
Тогда из (2) получаем, что глубина коллизии в
первом случае будет D  r1  ( N , PO1 )  r1  | PO1 | , а
во втором – D  r1  ( N , PO1 )  r1  | PO1 | .
Определение коллизии сферы
с прямоугольным параллелепипедом
Для определения коллизии сферы и бокса обозначим через Q точку на поверхности бокса, ближайшую к центру сферы. Рассмотрим всевозможные варианты расположения центра сферы относительно бокса (см. рис. 2).
1. Центр сферы расположен точно над одной из
граней бокса. Тогда точкой Q является конец перпендикуляра, опущенного из центра сферы к этой
грани (точка Q1 на рисунке 2).
2. Центр сферы расположен по диагонали от одного из ребер бокса, то есть вне двух соседних граней, содержащих это ребро. Тогда точкой Q является конец перпендикуляра, опущенного из центра
сферы к этому ребру бокса (точка Q2 на рисунке 2).
3. Центр сферы расположен по диагонали от одной из вершин бокса, то есть вне трех соседних гра-
Программные продукты и системы / Software & Systems
Рис. 2. Ближайшая к центру сферы точка
на поверхности бокса
Fig. 2. A point on the box surface, which is the closest
to the sphere center
ней, содержащих эту вершину. Тогда точкой Q будет эта вершина бокса (точка Q3 на рисунке 2).
4. Центр сферы лежит внутри бокса. Тогда точкой Q является конец перпендикуляра, опущенного
из центра сферы к ближайшей грани бокса (точка
Q4 на рисунке 2).
Обозначим через E1 систему координат сферы,
а через E2 систему координат бокса. Рассмотрим
достаточно быстрый алгоритм, позволяющий определить положение центра сферы относительно
бокса. Причем, если центр сферы лежит вне бокса,
алгоритм сразу вычисляет точку Q. Суть алгоритма
– перевод вектора O2 O1 из мировой системы координат в систему E2 и его покомпонентное сравнение с полуразмерами бокса. Обозначим совокупность координат вектора O2 O1 в системе коорди-
№ 4 (112), 2015
иначе, если uE 2 .z  h 2 , то
u E 2 .z  h 2 .
Если выполняется хотя бы одно из данных условий, значит, центр сферы лежит вне бокса. Тогда
точка Q в системе координат E2 будет
QE 2  O2 E 2  uE 2 , а в мировой Q  M 2 (O2 E 2  uE 2 ) 
 O2  M 2uE 2 .
Если не выполнилось ни одно из условий, значит, центр сферы лежит внутри бокса. Рассмотрим
отдельно оба случая.
Центр сферы лежит вне бокса. Сфера и бокс
пересекаются тогда и только тогда, когда радиус
сферы больше расстояния от ее центра О1 до точки
Q, то есть |O1 – Q|  r1.
Если сфера и бокс пересекаются, точка коллизии Р будет совпадать с Q. Ясно, что соответствующие координаты векторов O2 O1 и PO1 в
системе E2 имеют одинаковые знаки, поэтому
(O2O1 , PO1 )  0 . Тогда из (1) следует, что N совпадет по направлению с PO1 (то есть будет соответствовать направлению расталкивания сферы), а
из (2) получаем D  r1  ( N , PO1 )  r1  | PO1 | .
Центр сферы лежит внутри бокса. В этом
случае вектор uE 2 будет соединять центр бокса с
центром сферы (см. рис. 3).
нат E2 через uE 2 . Получим uE 2  M 21 (O1  O2 ) .
Тогда с использованием компонент x, y и z вектора uE 2 алгоритм будет следующим.
Если uE 2 .x   l 2 , то
uE 2 .x   l 2 ,
иначе, если uE 2 .x  l 2 , то
u E 2 .x  l 2 .
Рис. 3. Кратчайшее расстояние от центра сферы
до одной из граней бокса
Fig. 3. A shortcut from the sphere center to one
of the box faces
Если uE 2 . y   w 2 , то
uE 2 . y   w 2 ,
иначе, если uE 2 . y  w 2 , то
uE 2 .y  w 2 .
Если uE 2 .z   h 2 , то
uE 2 .z   h 2 ,
Вычислим направление d и расстояние min от
центра сферы до ближайшей грани бокса:
min  l 2  | uE 2 .x | , d  (uE 2 .x 0 0)T .
Если min  w 2  | uE 2 . y | , то
min  w 2  | uE 2 . y | , d  (0 uE 2 .y 0)T .
107
Программные продукты и системы / Software & Systems
№ 4 (112), 2015
Если min  h 2  | uE 2 .z | , то
min  h 2  | uE 2 .z | ,
d  (0 0 uE 2 .z)T .
Тогда
точка
коллизии
d
.
P  O1  min
|d |
Проверим, что направление
нормали (1) будет противоположно
направлению вектора PO1 , то есть
будет правильным для расталкивания первого объекта. Ясно, что косинус угла между векторами O2 O1
и PO1
отрицательный, то есть
Следовательно,
(O2O1 , PO1 )  0 .
направление нормали будет противоположно направлению PO1 . Тогда из (2) получаем, что в этом случае
глубина
коллизии
D  r1  ( N , PO1 )  r1  | PO1 | .
В заключение отметим, что рассмотренные алгоритмы определения коллизий двух сфер между
собой и сферы с прямоугольным
параллелепипедом позволяют вычислять информацию о коллизиях
с небольшой вычислительной
сложностью. Вместе с обработкой
коллизий, описанной в [7], это позволяет моделировать динамику в
режиме реального времени большого (вплоть до нескольких тысяч)
количества виртуальных объектов.
Данные алгоритмы были реализованы в рамках динамической библиотеки, входящей в состав сущеРис. 4. Множество тел друг на друге в состоянии покоя
ствующей системы трехмерного
Fig. 4. Many motionless objects one on another
моделирования виртуальных объектов. За счет наличия в этой системе модуля визуализации [8, 9]
Система динамики в примере покоя объектов
реализованные алгоритмы были проверены на
друг на друге показала убедительные результаты
наборе тестовых сцен, имитирующих различные
времени расчетов. На просчет одного шага моделиситуации при столкновении виртуальных объекрования при наличии незначительного дрожания
тов. Особое внимание было уделено сложной в
объектов уходит не более 3 мс. В течение небольплане моделирования динамики ситуации покоя
шого количества шагов моделирования объекты
множества тел друг на друге (см. рис. 4). Сложперестают дрожать и переходят в статическое поность такой ситуации при моделировании диналожение, при котором определение и обработка их
мики в том, что на тела постоянно действует сила
коллизий прекращаются и на просчет одного шага
тяжести. Таким образом, тела постоянно стремятся
моделирования уходит менее 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).
108
Программные продукты и системы / Software & Systems
№ 4 (112), 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://users.soe.ucsc.edu/~pang/161/w06/notes/cms98.pdf (дата обращения: 10.07.2015).
3. Bounding volume. URL: https://en.wikipedia.org/wiki/Bounding_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/wiki/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-journal.org/2014-5/index2139.html?lang=ru
(дата
обращения:
10.07.2015).
DOI: 10.15827/0236-235X.112.105-109
Received 27.07.15
COLLISION DETECTION FOR BOUNDING SPHERES AND RECTANGULAR PARALLELEPIPEDS
IN 3D MODELING SYSTEMS
(The research has been supported by RFBR, grant no. 15-07-04544)
Trushin A.M., Research Associate, leha_trushin@mail.ru;
(SRISA RAS, Nakhimovsky Ave. 36/1, Moscow, 117218, Russian Federation)
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.
Keywords: collision detection, bounding volumes, dynamics modeling.
References
1. Moore M., Wilhelms J. Collision Detection and Response for Computer Animation. Computer Graphics. 1998, vol.
22, no. 4, pp. 289–298. Available at: http://www.cs.princeton.edu/courses/archive/spring01/cs598b/papers/moore88.pdf (accessed July 10, 2015).
2. Ming C. Lin, Gottschalk S. Collision detection between geometric models: a survey. Proc. of IMA Conf. on Mathematics of Surfaces. 1998, vol. 1, pp. 602–608. Available at: https://users.soe.ucsc.edu/~pang/161/w06/notes/cms98.pdf (accessed
July 10, 2015).
3. Bounding volume. Wikipedia. The Free Encyclopedia. Available at: https://en.wikipedia.org/wiki/Bounding_volume
(accessed July 10, 2015).
4. Ericson C. Real-Time Collision Detection. CRC Press, 2004, 594 p. Available at: https://books.google.
ru/books?id=WGpL6Sk9qNAC (accessed July 10, 2015).
5. Mikhaylyuk M.V., Trushin A.M. Computation of rectangular parallelepipeds collision detection in dynamics. Trudy
NIISI RAN [Pros. of SRISA RAS]. Moscow, 2012, vol. 2, no. 2, pp. 51–59 (in Russ).
6. Transformation matrix. Wikipedia. The Free Encyclopedia. Available at: https://en.wikipedia.org/wiki/Transformation_matrix (accessed July 10, 2015).
7. Trushin A.M. Collision response of virtual objects using the method of sequential impulses. Trudy NIISI RAN [Pros.
of SRISA RAS]. Moscow, 2014, vol. 4, no. 2, pp. 95–105 (in Russ).
8. Mikhaylyuk M.V., Torgashev M.A. “GLView” visualization system for simulation complexes and virtual reality systems. Vestnik RAEN [Bulletin of RANS]. 2011 no. 2, pp. 20–28 (in Russ).
9. Mikhaylyuk M.V., Torgashev M.A. Real-time visualization of controlled objects’ dynamics. Nauchnaya vizualizatsiya
[Scientific Visualization]. 2014, vol. 6, no. 5, pp. 69–80 (in Russ). Available at: http://sv-journal.org/2014-5/index2139.html?lang=ru (accessed July 10, 2015).
109
1/--страниц
Пожаловаться на содержимое документа