Шар к коллизии шара - обнаружение и обработка

Question

Шар к коллизии шара - обнаружение и обработка

262

graphics language-agnostic collision-detection physics

задан 17 revs, 8 users 38% 2 February 2019 в 09:47

9 ответов

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

, Если скорость шара слишком высока, можно пропустить коллизию.

И также, почти в 100% случаев Ваши новые скорости будут неправильными. Ну, не скорости , но положения . Необходимо вычислить новые скорости точно в корректном месте. Иначе Вы просто смещаете шары на некотором небольшом "ошибочном" количестве, которое доступно от предыдущего дискретного шага.

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

48

ответ дан avp 23 November 2019 в 02:34

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

Read на Двоичное Пространство, Делящее и Деревья квадрантов

20

ответ дан grepsedawk 23 November 2019 в 02:34

Как разъяснение к предложению Ryan Fox для разделения экрана на регионы, и только проверяющий на коллизии в регионах...

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

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

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

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

13

ответ дан Andrew Rollings 23 November 2019 в 02:34

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

10

ответ дан Ryan Fox 23 November 2019 в 02:34

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

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

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

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

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

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

3), Поскольку я упомянул, не делайте квадратного корня.

7

ответ дан Loren Pechtel 23 November 2019 в 02:34

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

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

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

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

6

ответ дан Markus Jarderot 23 November 2019 в 02:34

У Вас есть два простых способа сделать это. Сойка покрыла точный способ проверить от центра шара.

более легкий путь состоит в том, чтобы использовать прямоугольную ограничительную рамку, установить размер Вашего поля, чтобы быть 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]
            }
        }
    }
}

3

ответ дан FlySwat 23 November 2019 в 02:34

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

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

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

3

ответ дан 23 November 2019 в 02:34

Другие вопросы по тегам:

graphics language-agnostic collision-detection physics

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

score 116 · Accepted Answer

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

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

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