Столкновение шара с мячом - обнаружение и обработка - PullRequest
258 голосов
/ 06 декабря 2008

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

alt text

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

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

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

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

alt text

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

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


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

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


Успех!

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

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

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

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. Кроме того, он пропускает проверку столкновения с собой).

Затем в моем классе с мячом у меня есть методы 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));

}

Исходный код: Полный исходный код для шарового коллайдера.

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

Ответы [ 11 ]

112 голосов
/ 06 декабря 2008

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

В Википедии есть довольно хорошее резюме всего процесса . Для шаров любой массы новые скорости могут быть вычислены с использованием уравнений (где 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;
}

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

48 голосов
/ 19 декабря 2008

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

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

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

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

20 голосов
/ 06 декабря 2008

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

Читать дальше Разделение двоичного пространства а также Quadtrees

13 голосов
/ 06 декабря 2008

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

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

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

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

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

10 голосов
/ 06 декабря 2008

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

7 голосов
/ 06 декабря 2008

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

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

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

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

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

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

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

6 голосов
/ 12 декабря 2008

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

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

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

Редактировать: Обновлена ​​ссылка

3 голосов
/ 22 июля 2011

Это KineticModel является реализацией процитированного подхода в Java.

3 голосов
/ 13 мая 2010

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

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

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

3 голосов
/ 06 декабря 2008

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

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

Добавьте метод к вашему классу мяча:

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]
            }
        }
    }
}
...