Столкновение шара с мячом - обнаружение и обработка

С помощью сообщества Stack Overflow я написал довольно простой, но увлекательный симулятор физики.

альтернативный текст

Вы щелкаете мышью и запускаете шар. Он будет подпрыгивать и в конце концов остановится на «полу».

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

Я думаю, мой вопрос состоит из двух частей:

  1. Каков наилучший метод обнаружения столкновения шара с мячом?
    У меня просто есть петля O (n ^ 2), которая перебирает каждый шар и проверяет каждый другой шар, чтобы увидеть, перекрывается ли его радиус?
  2. Какие уравнения я использую, чтобы справиться с столкновениями шара с шаром? Физика 101
    Как это влияет на скорость вращения двух шаров по векторам x / y? В каком направлении движутся два мяча? Как я могу применить это к каждому шару?

альтернативный текст

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

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


Изменить: ресурсы, которые я нашел полезными

2d Физика шаров с векторами: 2-мерные столкновения без тригонометрии.pdf
2d Пример обнаружения столкновений шаров: добавление обнаружения столкновений


Успех!

У меня есть обнаружение столкновения мяча и реакция работает отлично!

Соответствующий код:

Обнаружение столкновения:

for (int i = 0; i < ballCount; i++)  
{  
    for (int j = i + 1; j < ballCount; j++)  
    {  
        if (balls[i].colliding(balls[j]))  
        {
            balls[i].resolveCollision(balls[j]);
        }
    }
}

Это будет проверять наличие столкновений между каждым мячом, но пропустить лишние проверки (если вам нужно проверить, сталкивается ли шар 1 с шаром 2, вам не нужно проверять, сталкивается ли шар 2 с шаром 1. Кроме того, он пропускает проверку на столкновения с самим собой. ).

Затем в моем классе Ball у меня есть методы colliding () и resolCollision ():

public boolean colliding(Ball ball)
{
    float xd = position.getX() - ball.position.getX();
    float yd = position.getY() - ball.position.getY();

    float sumRadius = getRadius() + ball.getRadius();
    float sqrRadius = sumRadius * sumRadius;

    float distSqr = (xd * xd) + (yd * yd);

    if (distSqr <= sqrRadius)
    {
        return true;
    }

    return false;
}

public void resolveCollision(Ball ball)
{
    // get the mtd
    Vector2d delta = (position.subtract(ball.position));
    float d = delta.getLength();
    // minimum translation distance to push balls apart after intersecting
    Vector2d mtd = delta.multiply(((getRadius() + ball.getRadius())-d)/d); 


    // resolve intersection --
    // inverse mass quantities
    float im1 = 1 / getMass(); 
    float im2 = 1 / ball.getMass();

    // push-pull them apart based off their mass
    position = position.add(mtd.multiply(im1 / (im1 + im2)));
    ball.position = ball.position.subtract(mtd.multiply(im2 / (im1 + im2)));

    // impact speed
    Vector2d v = (this.velocity.subtract(ball.velocity));
    float vn = v.dot(mtd.normalize());

    // sphere intersecting but moving away from each other already
    if (vn > 0.0f) return;

    // collision impulse
    float i = (-(1.0f + Constants.restitution) * vn) / (im1 + im2);
    Vector2d impulse = mtd.normalize().multiply(i);

    // change in momentum
    this.velocity = this.velocity.add(impulse.multiply(im1));
    ball.velocity = ball.velocity.subtract(impulse.multiply(im2));

}

Исходный код: полный исходный код для коллайдера.

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

6.12.2008 03:24:00
Я не думаю, что этот алгоритм достаточно хорош, потому что если ваши шары движутся слишком быстро (например: быстрее, чем 2 * радиус за кадр, один шар может пройти через другой шар без каких-либо столкновений.
Benji Mizrahi 10.09.2009 22:58:54
@Simulcal не могли бы вы загрузить свой исходный код снова (все ссылки на filedropper.com, похоже, не работают). Также не могли бы вы выложить pdf-файл, который вы получили с [geocities.com/vobarian/2dcollisions/2dcollisions.pdf], поскольку geocities недавно
bguiz 4.11.2009 09:58:43
Вот ссылка на последнюю версию BallBounce, над которой я работал: dl.dropbox.com/u/638285/ballbounce.rar
mmcdole 13.11.2009 05:53:35
@ Для всех, кто внес свой вклад: не могли бы вы пролить свет на преобразование этого движка в 3D. Как этот замечательный движок может работать и в Java3D.
static void main 20.05.2011 14:08:17
Линия Vector2d impulse = mtd.multiply(i);должна быть * нормализованным вектором mtd. Что-то вроде:Vector2d impulse = mtd.normalize().multiply(i);
klenwell 26.11.2012 20:30:09
11 ОТВЕТОВ
РЕШЕНИЕ

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

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

v_ {1} = \ frac {u_ {1} (m_ {1} -m_ {2}) + 2m_ {2} u_ {2}} {m_ {1} + m_ {2}}

v_ {2} = \ frac {u_ {2} (m_ {2} -m_ {1}) + 2m_ {1} u_ {1}} {m_ {1} + m_ {2}}

Если шары имеют одинаковую массу, то скорости просто переключаются. Вот код, который я написал, который делает нечто подобное:

void Simulation::collide(Storage::Iterator a, Storage::Iterator b)
{
    // Check whether there actually was a collision
    if (a == b)
        return;

    Vector collision = a.position() - b.position();
    double distance = collision.length();
    if (distance == 0.0) {              // hack to avoid div by zero
        collision = Vector(1.0, 0.0);
        distance = 1.0;
    }
    if (distance > 1.0)
        return;

    // Get the components of the velocity vectors which are parallel to the collision.
    // The perpendicular component remains the same for both fish
    collision = collision / distance;
    double aci = a.velocity().dot(collision);
    double bci = b.velocity().dot(collision);

    // Solve for the new velocities using the 1-dimensional elastic collision equations.
    // Turns out it's really simple when the masses are the same.
    double acf = bci;
    double bcf = aci;

    // Replace the collision velocity components with the new ones
    a.velocity() += (acf - aci) * collision;
    b.velocity() += (bcf - bci) * collision;
}

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

117
8.02.2017 14:09:20
Допустим, массы двух шаров не равны. Как это влияет на изменение вектора между шарами?
mmcdole 6.12.2008 03:53:33
С 12 класса прошло некоторое время, но я думаю, что они получают отношение импульса, соответствующее соотношению масс.
Ryan Fox 6.12.2008 03:59:44
@ Джей, просто чтобы подчеркнуть ... что одно изображение уравнения, которое вы добавили, предназначено для одномерного столкновения, а не для двухмерного.
mmcdole 6.12.2008 05:44:04
@simucal. не правда ... вы и v векторы в этом уравнении. То есть они имеют компоненты x, y (и z).
Andrew Rollings 6.12.2008 14:34:12
@ Simucal, вы правы, они для одномерного случая. Для большего количества измерений просто используйте компоненты скорости, которые соответствуют столкновению (aci, bci в коде). Другие компоненты ортогональны к столкновению и не изменятся, поэтому вам не нужно беспокоиться о них.
Jay Conrod 6.12.2008 15:40:41

Хороший способ уменьшить количество проверок столкновений - разбить экран на несколько частей. Затем вы сравниваете только каждый шарик с шариками в одном разделе.

10
6.12.2008 03:39:25
Исправление: вам нужно проверить наличие столкновений с одинаковыми соседними участками
rint 14.09.2016 14:16:49

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

Читайте о разделах двоичного пространства и Quadtrees

20
6.12.2008 03:43:14
Вместо разделения пространства, не будет ли лучше работать алгоритм очистки и сокращения ? шары движутся быстро, поэтому любое разбиение придется часто обновлять, что приводит к накладным расходам. Развертка и сокращение могут найти все конфликтующие пары в O (n log n) без каких-либо временных структур данных. Вот хороший учебник для основ
HugoRune 14.06.2012 22:45:29

В качестве пояснения к предложению Райана Фокса разделить экран на регионы и проверять только столкновения внутри регионов ...

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

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

Решением этой проблемы является наложение второй сетки с вертикальным и горизонтальным смещением на 0,5 единицы относительно первой.

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

13
6.12.2008 04:21:33
+1 за более точное решение и противостоять трусливому гонщику
Steven A. Lowe 6.12.2008 06:29:24
это хорошая идея. Я сделал это один раз, и я проверил текущую ячейку и все соседние ячейки, но ваш метод более эффективен. Другой способ, о котором я только что подумал, - проверить текущую ячейку, а затем проверить, пересекается ли она с текущими границами ячеек, и, если это так, проверить объекты в соседней ячейке ТА.
LoveMeSomeCode 27.07.2009 22:24:49

У вас есть два простых способа сделать это. Джей накрыл точный способ проверки из центра мяча.

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

Добавьте метод в свой класс ball:

public Rectangle getBoundingRect()
{
   int ballHeight = (int)Ball.Height * 0.80f;
   int ballWidth = (int)Ball.Width * 0.80f;
   int x = Ball.X - ballWidth / 2;
   int y = Ball.Y - ballHeight / 2;

   return new Rectangle(x,y,ballHeight,ballWidth);
}

Тогда в вашем цикле:

// Checks every ball against every other ball. 
// For best results, split it into quadrants like Ryan suggested. 
// I didn't do that for simplicity here.
for (int i = 0; i < balls.count; i++)
{
    Rectangle r1 = balls[i].getBoundingRect();

    for (int k = 0; k < balls.count; k++)
    {

        if (balls[i] != balls[k])
        {
            Rectangle r2 = balls[k].getBoundingRect();

            if (r1.Intersects(r2))
            {
                 // balls[i] collided with balls[k]
            }
        }
    }
}
3
6.12.2008 15:37:51
Это заставило бы шары переходить друг в друга на 20% при горизонтальных и вертикальных столкновениях. Можно также использовать круглые ограничивающие рамки, поскольку разница в эффективности незначительна. Кроме того, (x-width)/2должно быть x-width/2.
Markus Jarderot 6.12.2008 13:05:34
Хороший вызов на опечатку старшинства. Вы обнаружите, что большинство 2D-игр используют прямоугольные ограничивающие рамки на непрямоугольных формах, потому что это быстро, и пользователь почти никогда не замечает.
FlySwat 6.12.2008 15:38:43
Вы можете сделать прямоугольную ограничивающую рамку, затем, если она имеет удар, отметьте круглую ограничивающую рамку.
Brad Gilbert 6.12.2008 15:51:52
@ Джонатан Холланд, ваш внутренний цикл должен быть для (int k = i + 1; ...) Это избавит от всех лишних проверок. (т.е. проверка на столкновение с самим собой и проверка столкновения ball1 с ball2, затем ball2 с ball1).
mmcdole 6.12.2008 16:39:19
На самом деле квадратная ограничивающая рамка, вероятно, будет хуже с точки зрения производительности, чем круговая ограничивающая рамка (при условии, что вы уже оптимизировали квадратный корень)
Ponkadoodle 6.07.2010 03:01:48

Я вижу здесь одну вещь для оптимизации.

Хотя я согласен, что шары попадают, когда расстояние является суммой их радиусов, никогда не следует рассчитывать это расстояние! Скорее, рассчитайте его квадрат и работайте с ним таким образом. Там нет причин для этой дорогой операции с квадратным корнем.

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

Что касается O (n ^ 2), все, что вы можете сделать, это минимизировать стоимость отклонения пропущенных:

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

2) Что-то, что может стоить сделать: разделите экран на несколько зон, но линии должны быть нечеткими - шары на краю зоны указаны как находящиеся во всех соответствующих (может быть 4) зонах. Я бы использовал сетку 4х4, сохраняя зоны в битах. Если AND из зон двух шаров возвращает ноль, конец теста.

3) Как я уже говорил, не делайте квадратный корень.

7
6.12.2008 05:45:27
Спасибо за информацию о кончике квадратного корня. Не знал о его дорогой природе по сравнению с площадью.
mmcdole 6.12.2008 06:02:35
Другой оптимизацией было бы найти шары, которых нет рядом с другими шарами. Это будет работать надежно, только если скорости шариков ограничены.
Brad Gilbert 6.12.2008 15:50:14
Я не согласен на поиск изолированных шаров. Это так же дорого, как обнаружение столкновения. Чтобы улучшить вещи, вам нужно что-то меньше, чем O (n) для рассматриваемого мяча.
Loren Pechtel 7.12.2008 02:25:24

Я нашел отличную страницу с информацией об обнаружении столкновений и реакции в 2D.

http://www.metanetsoftware.com/technique.html

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

Изменить: Обновленная ссылка

6
16.05.2010 19:15:05

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

  • Если скорость мяча слишком высока, вы можете пропустить столкновение.

А также, почти в 100% случаев ваши новые скорости будут неправильными. Ну не скорости , а позиции . Вы должны рассчитать новые скорости точно в правильном месте. В противном случае вы просто сдвигаете шары на небольшую величину «ошибки», которая доступна из предыдущего дискретного шага.

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

48
19.12.2008 09:44:04
Если смещение позиций включено timeframelength*speed/2, то позиции будут статистически фиксированы.
Nakilon 7.10.2011 07:02:38
@Nakilon: нет, это помогает только в некоторых случаях, но обычно можно пропустить столкновение. И вероятность пропустить столкновение увеличивается с размером длины таймфрейма. Кстати, похоже, что Алеф продемонстрировал правильное решение (хотя я просто просмотрел его).
avp 11.10.2011 21:43:05
@avp, я не о том, если скорость мяча слишком высока, вы можете пропустить столкновение. , но по поводу ваших новых должностей будет неправильно . Из-за столкновения обнаруживается немного позже, чем они действительно столкнулись, если вычесть timeframelength*speed/2из этой позиции, точность увеличится вдвое.
Nakilon 12.10.2011 00:05:27

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

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

Да, это два теста, но в целом он будет быстрее.

3
13.05.2010 16:57:44
Тебе не нужен триг. bool is_overlapping(int x1, int y1, int r1, int x2, int y2, int r2) { return (x2-x1)*(x2-x1)+(y2-y1)*(y2-y1)<(r1+r2)*(r1+r2); }
Ponkadoodle 6.07.2010 03:05:38

Это KineticModelреализация цитируемого подхода в Java.

3
2.09.2011 17:29:59

Я реализовал этот код в JavaScript, используя элемент HTML Canvas, и он производил прекрасное моделирование со скоростью 60 кадров в секунду. Я начал симуляцию с набора из дюжины шаров в случайных положениях и скоростях. Я обнаружил, что при более высоких скоростях скользящее столкновение между маленьким и большим шариками приводило к тому, что маленький шарик прилипал к краю большего шарика, и перед разделением перемещался на угол около 90 градусов вокруг большого шарика. (Интересно, наблюдал ли кто-нибудь еще такое поведение?)

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

dot_velocity = ball_1.velocity.dot(ball_2.velocity);
mtd_factor = 1. + 0.5 * Math.abs(dot_velocity * Math.sin(collision_angle));
mtd.multplyScalar(mtd_factor);

Я проверил, что до и после этого исправления полная кинетическая энергия была сохранена для каждого столкновения. Значение 0.5 в mtd_factor было приблизительно минимальным значением, которое всегда вызывало отделение шариков после столкновения.

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

2
6.10.2013 00:53:26
грех (..) не дешевая функция
PaulHK 21.06.2017 13:03:28