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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Сумма Минковского из X и Y представляет собой множество всех х + у для х ∈ X и Y ∈ Y .

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

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

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

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

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

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

Мы не можем вычислить все x - y для x ∈ X и y ∈ 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Набор млн на большинство элементов. convexHullАлгоритм имеет сложность , которая зависит от алгоритма, используемым , и вы можете стремиться к O (к логу (к)) , где к является размером множества точек, так что в нашем случае мы получаем O (млн журнала (млн) ) . containsАлгоритм имеет сложность, линейно с числом ребер (в 2D) или лицо (в 3D) выпуклой оболочки, так что это действительно зависит от ваших исходных форм, но это будет не больше , чем O (млн) .

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

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

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

и, как вы указали на своих снимках, эти тела по мере движения проникают через области (или объемы):

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

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

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

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

Рассматривая B как неподвижен в своей собственной системе отсчета, вы только вычислить объем, А метет через , как она движется во время ДТ с его относительной скорости об - об _B .

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

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

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

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

Столкновение может произойти только в том случае, возможно , что ограничивающая круг А встречаются у 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;

}

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

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

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

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

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);
}

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

Теорема об отдельной оси

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

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

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

Реализовано это выглядит так:

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
}

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

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

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

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

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

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