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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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