Непрерывное обнаружение столкновений между двумя движущимися тетраэдрами

Question

Мой вопрос довольно прост. У меня есть два тетраэдра, каждый с текущим положением, линейной скоростью в пространстве, угловой скоростью и центром масс (фактически, центром вращения).

Имея эти данные, я пытаюсь найти (быстрый) алгоритм, который бы точно определил (1), столкнутся ли они в какой-то момент времени, и если это так, (2) через сколько времени они столкнулись и (3) точка столкновения.

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

Проблема в том, что мне неизвестен какой-либо общедоступный алгоритм треугольник-треугольник CCD (непрерывное обнаружение столкновений), который учитывает самовращение.

Поэтому мне нужен алгоритм, который бы вводил следующие данные:

• данные вершин для трех треугольников
• Положение и центр вращения / масса
• линейная скорость и угловая скорость

И выдаст следующее:

• Есть ли столкновение
• Через сколько времени произошло столкновение
• В какой точке пространства произошло столкновение

Заранее спасибо за помощь.

Answer 1

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

Непрерывное обнаружение столкновений сначала вычисляет объемы, отслеживаемые каждым треугольником за бесконечность времени. Для треугольника, движущегося с постоянной скоростью и без вращения, этот объем может выглядеть как треугольная призма. Затем CCD проверит наличие столкновений между томами и, наконец, отследит, действительно ли треугольники занимали одно и то же время.

Когда вводится угловая скорость, объем, отслеживаемый каждым треугольником, больше не выглядит как призма. Это может выглядеть больше как форма винта, как нить ДНК, или некоторые другие нетривиальные формы, которые вы могли бы получить, вращая треугольник вокруг какой-то произвольной оси, одновременно перетаскивая его. Вычислить форму такого объема нелегко.

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

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

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

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

Answer 2

Вот схема математического подхода в замкнутой форме. Каждый элемент этого будет легко выразить индивидуально, и окончательная комбинация этого будет выражением закрытой формы, если когда-либо можно будет выписать это:

1) Уравнение движения для каждой точки тетраэдра довольно просто в своей собственной системе координат. Движение центра масс (CM) будет просто плавно перемещаться вдоль прямой линии, а угловые точки будут вращаться вокруг оси через CM, предполагаемой здесь как ось z, поэтому уравнение для каждой угловой точки (параметризованное как время t) равно p = v t + x + r (sin (wt + s) i + cos (wt +) s) j ), где v - векторная скорость центра масс; r - радиус проекции на плоскость x-y; i , j и k - единичные векторы x, y и z; и x и s учитывают начальную позицию и фазу вращения при t = 0.

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

3) Теперь у вас есть уравнение для каждой траектории в пределах одной и той же системы координат, и вам нужно найти времена пересечений. Это можно выяснить, проверяя, пересекает ли какой-либо из отрезков линии от точек до CM тетраэдра какой-либо из треугольников другого. Это также имеет выражение в закрытой форме, как можно найти здесь .

Расслоение этих шагов приведёт к ужасно уродливым уравнениям, но их будет не сложно решить вычислительно (хотя при вращении тетраэдров вы должны быть уверены, что не застряли в локальном минимуме). Другой вариант - подключить его к чему-то вроде Mathematica, чтобы выполнить его за вас. (Не все проблемы имеют простые ответы.)

Answer 3

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

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

Answer 4

Я потратил довольно много времени на размышления о геометрических задачах, подобных этой, и кажется, что точные решения, несмотря на их простые утверждения, слишком сложны, чтобы быть практичными даже для аналогичных 2D-случаев.

Но интуитивно я вижу, что такие решения существуют, когда вы рассматриваете линейные скорости перемещения и линейные угловые скорости. Не думайте, что вы найдете ответ в Интернете или в любой книге, потому что то, о чем мы говорим здесь, это особые, но сложные случаи. В любом случае, итеративное решение - это, вероятно, то, что вам нужно - остальной мир этим удовлетворен, так почему бы вам не быть?

Answer 5

Мысли об этом в прошлом, но потеряли интерес ... Лучший способ решить это было бы абстрагировать один объект. Создайте систему координат, где первый тетраэдр является центром (барицентрические координаты или перекошенная система с одной точкой в ​​качестве начала координат) и абстрагируйте вращение, заставив другой тетраэдр вращаться вокруг центра. Это должно дать вам параметрические уравнения, если вы сделаете время поворота времени. Добавьте движение центра масс к первому и его вращение, и вы получите набор уравнений для движения относительно первого (расстояния). Решите для t, где расстояние равно нулю.

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

Примечание: если вы идете по пути перекошенной системы, остерегайтесь ловушек с расстоянием. Вы должны быть в правильном октанте! Этот метод предпочитает векторы и кватернионы, тогда как барицентрические координаты предпочитают матрицы. Так что выбирайте, какая ваша система использует наиболее эффективно.

Answer 6

Ваша задача может быть преобразована в задачу линейного программирования и решена точно.

Сначала предположим, что (p0, p1, p2, p3) - вершины в момент времени t0, а (q0, q1, q2, q3) - вершины в момент времени t1 для первого тетраэдра, затем в 4d пространстве-времени, они заполняют следующий 4d закрытый объем

V = { (r,t) | (r,t) = a0 (p0,t0) + … + a3 (p3,t0) + b0 (q0,t1) + … + b3 (q3,t1) }

Здесь параметры a0 ... a3 и b0 ... b3 находятся в интервале [0,1] и составляют 1:

a0+a1+a2+a3+b0+b1+b2+b3=1

Второй тетраэдр аналогично является выпуклым многоугольником (добавьте ‘ко всему выше, чтобы определить V’ 4d объем для этого движущегося тетраэдра.

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

Если (p0, p1, p2, p3) переместится в (q0, q1, q2, q3) и (p0 ’, p1’, p2 ’, p3’) перемещается в (q0 ’, q1’, q2 ’, q3’) тогда первый раз пересечения происходит в точках / временах (r, t):

Минимизировать t0 * (a0 + a1 + a2 + a3) + t1 * (b0 + b1 + b2 + b3) с учетом

0 <= ak <=1, 0<=bk <=1, 0 <= ak’ <=1, 0<=bk’ <=1, k=0..4
a0*(p0,t0) + … + a3*(p3,t0) + b0*(q0,t1) + … + b3*(q3,t1) 
  = a0’*(p0’,t0) + … + a3’*(p3’,t0) + b0’*(q0’,t1) + … + b3’*(q3’,t1)

Последнее - фактически 4 уравнения, по одному для каждого измерения (r, t). Это всего 20 линейных ограничений из 16 значений ak, bk, ak 'и bk'. Если есть решение, то

(r,t)= a0*(p0,t0) + … + a3*(p3,t0) + b0*(q0,t1) + … + b3*(q3,t1)

является точкой первого пересечения. В противном случае они не пересекаются.

Answer 7

Извините, я не математик и понятия не имею, что такое правильная терминология. Надеюсь, мои плохие слова не слишком скрывают мой смысл.

Выберите произвольный временной шаг.

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

Для временного шага: Если стержень этих границ для любых двух объектов пересекается, сделайте половину шага и начните рекурсию.

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