Обнаружение столкновения шестиугольника для быстро движущихся объектов?

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

BoundingBox Collision Fail

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

Hexagon Collision Win

Итак, моя идея, вместо того, чтобы расширять точку, почему бы не расширить прямоугольник? Это приводит к шестиугольнику.

Теперь, пока все хорошо. Но как я могу проверить, пересекаются ли два гексагона такого типа? Обратите внимание, что это очень специфические версии шестиугольника.

Спецификации шестиугольника

Бонусный вопрос : Можно ли вычислить, где именно (или, вернее, после того, сколько времени) произошло столкновение? Это может быть очень полезно для определения того, что на самом деле произошло, например, где и с какой мощностью и для имитации того, как они перемещались за время между столкновением и концом кадра.

39 голосов | спросил API-Beast 20 Maypm13 2013, 19:17:10

6 ответов


33

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

Вот ваши прямоугольники A и B со скоростями vA и vB. Обратите внимание, что vA и vB не являются фактически скоростями, они являются расстоянием , перемещенным в течение одного кадра.

step 1

Теперь заменим прямоугольник B точкой P и прямоугольником A с прямоугольником C = A + (- B), который имеет размеры сумму размерностей A и B. Сложительные свойства Минковского указывают, что столкновение между точкой и новый прямоугольник возникает тогда и только тогда, когда происходит столкновение между двумя исходными двумя прямоугольниками:

step 2

Но если прямоугольник C движется вдоль вектора vA, а точка P движется вдоль вектора vB, простое изменение отсчета говорит нам, что это то же самое, как если прямоугольник C был неподвижен, а точка P перемещалась вдоль вектора vB-vA:

step 3

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

Последний шаг - вернуться к правильной системе отсчета. Просто разделите расстояние, пройденное точкой до кругового пересечения по длине вектора vB-vA, и вы получите значение s, чтобы 0 < s < 1. Коллизия происходит в момент s * T, где T - это продолжительность вашего фрейма.

Комментарий madshogo :
Одно ОГРОМНОЕ преимущество этой методики над тем, что есть в собственном ответе г-на Зверя, заключается в том, что если поворота нет, тогда «вычитание Минковского» A + (- B) может быть вычислено один раз для всех последующих временные шаги

Итак, единственный алгоритм, требующий времени во всем этом (сумма Минковского, сложность O (mn) , где m - число вершин в A и n количество вершин в B ) можно использовать только один раз, эффективно делая обнаружение столкновений постоянной проблемой!

Позже вы можете выбросить сумму, если вы точно знаете, что A и B находятся в разных частях вашей сцены (вашей квадранты?) и выиграли ' t больше сталкиваются.

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

Кроме того, для прямоугольников с выравниванием по осям A + (- B) можно вычислить гораздо проще, чем фактически вычислять все суммы, вершину по вершине. Просто разверните A , добавив высоту B к ее высоте и ширине B к ее ширине (пополам с каждой стороны).

Но все это работает, только если ни A , ни B не вращаются, и если оба они выпуклые. Если есть вращение или если вы используете вогнутые фигуры, тогда вы должны использовать swept объемы /области.
конец комментария

ответил sam hocevar 22 Maypm13 2013, 20:38:04
16

Прежде всего, в случае прямоугольников, выровненных по оси, ответ Кевина Рида является лучшим и алгоритм является самым быстрым.

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


Как в общем случае сказать, пересекаются ли две выпуклые формы?

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

Предположим, что X и Y - две выпуклые формы. Они пересекаются тогда и только тогда, когда они имеют общую точку, т. Е. Существует точка x & в; X и точка y & in; Y такой, что x = y . Если вы рассматриваете пространство как векторное пространство, то это означает выражение x - y = 0 . И теперь мы добираемся до этого бизнеса Минковского:

сумма Минковски X и Y - это набор всех x + y для x & in; X и y & in; Y .


Пример для X и Y


X, Y и их сумма Минковского, X + Y

Предположим, что (- Y) - это набор всех -y для y & in; Y , то, учитывая предыдущий параграф, X и Y пересекаются тогда и только тогда, когда X + (-Y) содержит 0 , то есть начало .

Боковое замечание: зачем писать X + (-Y) вместо X - Y ? Ну, потому что в математике есть операция, называемая разницей Минковского A и B , которая иногда записывается X - Y , но не имеет ничего общего с делать с набором всех x - y для x & in; X и y & in; Y (реальная разница Минковского немного сложнее).

Итак, мы хотели бы вычислить сумму Минковского X и -Y и выяснить, содержит ли она начало. Происхождение не является особенным по сравнению с любой другой точкой, поэтому, чтобы выяснить, находится ли происхождение в пределах определенного домена, мы используем алгоритм, который мог бы рассказать нам, принадлежит ли какая-либо точка к этой области.

Сумма Минковского X и Y имеет классное свойство, то есть если X и Y выпуклы, то X + Y тоже. И найти, принадлежит ли точка к выпуклому множеству, much проще, чем если бы этот набор не был (как известно, выпуклым).

Мы не можем вычислить все x - y для x & in; X и y & in; Y , потому что существует бесконечность таких точек x и y , поэтому, надеюсь, поскольку X , Y и X + Y являются выпуклыми, мы можем просто использовать «самые внешние» точки, определяющие формы X и Y , которые являются их вершинами , и мы получим внешние точки X + Y , а также еще несколько.

Эти дополнительные точки «окружены» самыми удаленными из X + Y , так что они не способствуют определению вновь полученной выпуклой формы. Мы говорим, что они не определяют « выпуклый корпус » из набора точек. Итак, что мы делаем, так это то, что мы избавляемся от них в процессе подготовки к окончательному алгоритму, который говорит нам, является ли начало в выпуклой оболочке.


Выпуклая оболочка X + Y. Мы удалили «внутренние» вершины.

Итак, получим

Первый, наивный алгоритм

boolean intersect(Shape X, Shape Y) {

  SetOfVertices minkowski = new SetOfVertices();
  for (Vertice x in X) {
    for (Vertice y in Y) {
      minkowski.addVertice(x-y);
    }
  }
  return contains(convexHull(minkowski), Vector2D(0,0));

}

Очевидно, что у циклов есть сложность O (mn) , где m и n - количество вершин каждой формы. Набор minkoswki содержит максимум mn . Алгоритм convexHull имеет сложность, которая зависит от используемого вами алгоритма , и вы можете нацелиться на O (k log (k)) , где k - размер набора точек, поэтому в нашем случае мы получаем O (mn войти (тп)) . Алгоритм contains имеет сложность, которая линейна с количеством ребер (в 2D) или гранями (в 3D) выпуклой оболочки, поэтому она действительно зависит от ваших исходных фигур, но она не будет больше O (mn) .

Я дам вам google для contains алгоритм для выпуклых фигур, он довольно распространенный. Я могу поместить его здесь, если у меня есть время.


Но это обнаружение конфликтов, которое мы делаем, поэтому мы можем оптимизировать это много

Мы первоначально имели два тела A и B , перемещающиеся без вращения во время timestep dt (из того, что я могу сказать, посмотрев ваши фотографии ). Назовем v A и v B соответствующие скорости A и B , которые являются постоянными во время нашей временной отметки длительности dt . Мы получаем следующее:

и, как вы указываете на своих снимках, эти тела прокручивают области (или томов в 3D) при перемещении:

, и они заканчиваются как A ' и B' после отметки времени.

Чтобы применить наш наивный алгоритм здесь, нам нужно было бы вычислить только точечные объемы. Но мы этого не делаем.

В системе отсчета B B не двигается (Дух!). И A имеет определенную скорость относительно B , которую вы получаете путем вычисления v A - v B (вы можете сделать обратное, вычислить относительную скорость B в кадре A ).

Относительное движение

Слева направо: скорости в базовой системе отсчета; относительные скорости; вычисление относительных скоростей.

Рассматривая B как неподвижный в своем собственном референтном кадре, , вам нужно только вычислить том, который A проскальзывает, когда он перемещается во время dt с его относительной скоростью v A - v B .

Это уменьшает количество вершин, которые будут использоваться в вычислении суммы Минковского (иногда сильно).

Другая возможная оптимизация находится в точке, где вы вычисляете объем, охваченный одним из тел, скажем, A. Вам не нужно переводить все вершины, составляющие A. Только те, которые принадлежат ребрам (грани в 3D), внешняя нормальная «лицо» - направление подметания. Разумеется, вы заметили, что уже когда вы вычисляли ваши охваченные области для квадратов. Вы можете определить, является ли нормаль к направлению подметания, используя его точечный продукт с направлением подметания, которое должно быть положительным.

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

Предположим, вы знаете радиусы A и B в отношении своих центровмасса (то есть расстояние между центром масс и самой удаленной от него вершиной), например:

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

Это не очень хорошо работает с формами, которые довольно длинны, но в случае квадратов или других таких фигур, это очень хорошая эвристика , чтобы исключить столкновение .

Теорема о разделительной оси, применяемая к B , и объем, охваченный A , однако, говорит вам, происходит ли столкновение. Сложность связанного алгоритма линейна с суммой чисел вершин каждой выпуклой формы, но она менее волшебна, когда приходит время, чтобы фактически справиться с столкновением.

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

boolean mayCollide(Body A, Body B) {

  Vector2D relativeVelocity = A.velocity - B.velocity;
  if (radiiHeuristic(A, B, relativeVelocity)) {
    return false; // there is a separating axis between them
  }

  Volume sweptA = sweptVolume(A, relativeVelocity);
  return contains(convexHull(minkowskiMinus(sweptA, B)), Vector2D(0,0));

}

boolean radiiHeuristic(A, B, relativeVelocity)) {
  // the code here
}

Volume convexHull(SetOfVertices s) {
  // the code here
}

boolean contains(Volume v, Vector2D p) {
  // the code here
}

SetOfVertices minkowskiMinus(Body X, Body Y) {

  SetOfVertices result = new SetOfVertices();
  for (Vertice x in X) {
    for (Vertice y in Y) {
      result.addVertice(x-y);
    }
  }
  return result;

}
ответил jrsala 23 Maypm13 2013, 17:13:10
2

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

Два прямоугольника с осевой ориентацией перекрываются тогда и только тогда, когда их координатные диапазоны X перекрываются, а их координаты Y-координат перекрываются. (Это можно рассматривать как частный случай теоремы о разделительной оси). То есть, если вы проецируете прямоугольники на оси X и Y, вы уменьшили проблему до двух пересечений линий.

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

ответил Kevin Reid 20 Maypm13 2013, 20:43:26
1

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

function objectsWillCollide(object1,object2) {
    var lineA, lineB, lineC, lineD;
    //get projected paths of objects and store them in the 'line' variables

    var AC = lineCollision(lineA,lineC);
    var AD = lineCollision(lineA,lineD);
    var BC = lineCollision(lineB,lineC);
    var BD = lineCollision(lineB,lineD);
    var objectToObjectCollision = rectangleCollision(object1.getRectangle(), object2.getRectangle());

    return (AC || AD || BC || BD || objectToObjectCollision);
}

Иллюстрация путей и конечных состояний объектов

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

ответил eazimmerman 20 Maypm13 2013, 19:44:17
0

Теорема о независимой оси

Теорема о отдельной оси говорит «Если мы можем найти ось, на которой две выпуклые формы не пересекаются, то две формы не пересекаются« или более практичны для IT:

«Две выпуклые формы только пересекаются, если они пересекаются на всех возможных осях».

Для выровненных по оси прямоугольников имеется ровно две возможные оси: x и y. Но теорема не ограничивается прямоугольниками, она может применяться к любой выпуклой форме, просто добавляя другие оси, на которых могут пересекаться фигуры. Для получения дополнительной информации о теме ознакомьтесь с этим руководством разработчика N: http: //www .metanetsoftware.com /техника /tutorialA.html # раздел1

Реализован он выглядит следующим образом:

axes = [... possible axes ...];
collision = true;
for every index i of axes
{
  range1[i] = shape1.getRangeOnAxis(axes[i]);
  range2[i] = shape2.getRangeOnAxis(axes[i]);
  rangeIntersection[i] = range1[i].intersectionWith(range2[i]);
  if(rangeIntersection[i].length() <= 0)
  {
    collision = false;
    break;
  }
}

Оси могут быть представлены как нормированные векторы.

Диапазон - это 1-мерная линия. Старт должен быть установлен на наименьшую проецируемую точку, заканчивая наибольшую прогнозируемую точку.

Применяя его к прямоугольному прямоугольнику

Шестиугольник в вопросе создается путем «подметания» AABB объекта. Подметание добавляет ровно одну возможную ось столкновений в любую форму: вектор движения.

shape1 = sweep(originalShape1, movementVectorOfShape1);
shape2 = sweep(originalShape2, movementVectorOfShape2);

axes[0] = vector2f(1.0, 0.0); // X-Axis
axes[1] = vector2f(0.0, 1.0); // Y-Axis
axes[2] = movementVectorOfShape1.normalized();
axes[3] = movementVectorOfShape2.normalized();

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

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


Бонус: где происходит волшебство.

Как я сказал, единственными дополнительными осями являются векторы движения. Движение - это время, умноженное на скорость, поэтому в некотором смысле это не просто оси пространства, а - оси времени.

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

shapeRange1 = originalShape1.getRangeOnAxis(axes[2]);
shapeRange2 = originalShape2.getRangeOnAxis(axes[3]);
// Project them on a scale from 0-1 so we can compare the time ranges
timeFrame1 = (rangeIntersection[2] - shapeRange1.center())/movementVectorOfShape1.project(axes[2]);
timeFrame2 = (rangeIntersection[3] - shapeRange2.center())/movementVectorOfShape2.project(axes[3]);
timeIntersection = timeFrame1.intersectionWith(timeFrame2);

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

if(collision)
{
  [... timeIntersection = see above ...]
  if(timeIntersection.length() <= 0)
    collision = false;
  else
    collisionTime = timeIntersection.start; // 0: Start of the frame, 1: End of the frame
}

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

ответил API-Beast 24 Maypm13 2013, 16:51:25
-2

Пока области охвата закрыты (без пробелов на границе, образованных краевыми линиями), будет работать следующее (просто уменьшите свои тесты на столкновение до линейных и точечных /точечных):

  1. Связать ли их края? (линейные коллизии) Проверьте, не пересекается ли какая-либо граничная линия пересеченной области с любым крайняя линия другой области охвата. Каждая зона охвата имеет 6 сторон.

  2. Маленькая внутри большой? (Используйте ориентированные по осям фигуры (point-rect & point-tri)) Переориентируйте (поверните) области охвата, чтобы больший     выравнивание по оси и проверка того, является ли меньшая внутренняя (путем проверки того, находятся ли какие-либо угловые точки (должны быть все или нет) в пределах области, охваченной по оси). Это делается разложением шестнадцатеричного на трис и прямоугольники.

Какой тест вы выполняете в первую очередь, зависит от вероятности каждого из них (чаще всего встречающегося в первую очередь).

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

ответил axon 23 Mayam13 2013, 03:21:37

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132