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

Ответ 1

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

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

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

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

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

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

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

Ответ 2

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

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

Ответ 3

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

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

Ответ 4

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

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) Обратите внимание: каждый объект имеет свою собственную систему координат, чтобы легко представлять движение, но для их сравнения вам необходимо повернуть их в общую систему координат, которая также может быть системой координат экрана. (Отметим, однако, что разные системы координат фиксированы в пространстве и не перемещаются с тетраэдрами.) Поэтому определим матрицы вращения и применим их к каждой траектории (т.е. Точки и КМ каждого из тетраэдров).

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

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

Ответ 5

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

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

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

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

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

Ответ 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) то первый раз пересечения происходит в точках /times (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)

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

Ответ 7

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

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

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