Геометрия (задачки)

[Igors]

Ну это просто решается в системе центра масс..

Шо за система  

Код

C++ (Qt)
bool BallsCollided( Ball & ball1, Ball & ball2 )
{
    QVector3D r0 = ball1.pos - ball2.pos;
    QVector3D u = ball1.speed - ball2.speed;
 
    float u2 = u.lengthSquared();
    float r0u = QVector3D::dotProduct(r0, u);
 
    float rho2 = r0.lengthSquared() - r0u*r0u/u2;
 
    return (rho2 < 4*Ball::radius * Ball::radius);
}
 

Посчитаем тестовый пример (на бумажке)

Код

C++ (Qt)
Ball b1, b2;
 
// первый шарик справа и движется вправо
b1.position = QVector3D(1, 0, 0):
b1.speed = QVector3D(1, 0, 0):
 
// а второй стоит в (0, 0, 0)
b2.position = QVector3D(0, 0, 0):
b2.speed = QVector3D(0, 0, 0):
 
Ball::radius = 0.4f;
bool collided = BallCollided(b1, b2);

Тогда все получается по единичке, а rho2 = 0. Так что, выходит пересеклись? Где-то перемудрили, надо было потратиться на нормализацию

[Igors]

По поводу пересечения шариков: ну а почему не просто так

Код

C++ (Qt)
bool BallsCollided( Ball & b1, Ball & b2 )
{
    if ((b1.position - b2.position).length() > Ball::radius * 2)  // не пересеклись?
     return false;
 
// пересеклись, считаем новые скорости
 
    return true;
}
 

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

Такая проверка не то чтобы "неправильна", но не учитывает крайних случаев. Напр мы симулируем движение 2 шариков

Код

C++ (Qt)
while (true) {
  BallsCollided(b1, b2);
  b1.position += b1.speed * dt;   // часто для простоты dt = 1
  b2.position += b2.speed * dt; 
}

И тут можно получить по дюнделю
а) пересечение состоялось, но на след итерации оно еще есть (шарики удаляются друг от друга слишком медленно)
b) наоборот, скорости слишком велики, и шарики "проскочили" сквозь друг друга
с) или шарики уж "слишком пересеклись", может "слились"

В общем, есть такое словечко "робостный".

[m_ax]

Шо за система  

Ландау, Лифшиц 1 том..

 

Посчитаем тестовый пример (на бумажке)

Да, сорри, забыл условие проверить.. Теперь всё ок

Код

C++ (Qt)
bool BallsCollided( Ball & ball1, Ball & ball2 )
{
    QVector3D r0 = ball1.pos - ball2.pos;
    QVector3D u = ball1.speed - ball2.speed;
 
    float u2 = u.lengthSquared();
    float r0u = QVector3D::dotProduct(r0, u);
 
    float rho2 = r0.lengthSquared() - r0u*r0u/u2;
 
    return (rho2 < 4.0*Ball::radius * Ball::radius) & (r0u < 0.0f);
}
 

По поводу пересечения шариков: ну а почему не просто так

Это вообще что??  
Как я понял из условия задачи: В некоторый момент времени нам были даны координаты и скорости шаров.  Вопрос: Столкнутся ли они в будущем? Всё.
Та формула/функция, что я привёл однозначно на этот вопрос отвечает.)
Могу, конечно, её расшифровать/вывести..  

Ну и скорости после столкновения тоже легко вычисляются..

[Igors]

Как я понял из условия задачи: В некоторый момент времени нам были даны координаты и скорости шаров.  Вопрос: Столкнутся ли они в будущем? Всё.

Ну как всегда, сами напутаете - а я виноват Я писал

// Если шарики столкнулись то вернуть true
// и рассчитать новые скорости шариков

А Ваша ф-ция возвращает true если вообще столкновение будет (может через год). Какой смысл это считать? Практически нужно знать что они уже столкнулись или столкнутся в течение заданного интервала времени dt (шага симуляции), который часто опускается для простоты (dt = 1). Т.е. если столкновения нет, то просто прибавляем скорость к позиции

Код

C++ (Qt)
ball.position += ball.speed;
 

Могу, конечно, её расшифровать/вывести..  

Ну давайте повыводим, я начну

QVector3D position1 = ball1.position + ball1.speed * t;  // закон движения первого шарика
QVector3D position2 = ball2.position + ball2.speed * t;  // закон движения второго шарика

QVector3D diff = position1 - position2;   // вектор центр-центр шариков

шарики точно столкнулись (т.е. без проникновения) если
float dist = diff.lengthSquared() = QVector3D::dotProduct(diff, diff) = 4 * Ball::radius * Ball::radius;

Нужно найти t при котором это равенство выполняется (если такое t существует)

Присмотримся к вектору diff

QVector3D origin = ball1.position - ball2.position;
QVector3D direction = ball1.speed - ball2.speed;
diff = origin + direction * t;

Так это же ур-е луча выходящего из точки origin в напр-и direction. Оказывается задачка-то сводится к хорошо известной "пересечение луча со сферой", в данном случае центр сферы в (0, 0, 0) и радиус = 2 * Ball::radius. Вот мы и прорвались к "готовым проверенным решениям"!

Впрочем в данном случае проще самому. Можно действовать чисто "алгеброй" (формулы) расписав dot(diff, diff), тогда все вектора обратятся в числа, и дело сведется к школьному ур-ю параболы a * t * t + b * t + c = 0. Но мне больше нравится "по чертежу", просто дважды применив теорему Пифагора. Как вижу, m_ax тоже предпочитает этот способ, передаю ему слово

[m_ax]

Ну как всегда, сами напутаете - а я виноват

Конечно. Нужно корректно ставить задачу.
Сейчас выясняется что есть ещё и шаг dt и т.д. и т.п..

Практически нужно знать что они уже столкнулись или столкнутся в течение заданного интервала времени dt

Ну и в чём проблема тогда? Скорость сближения/разбегания известна, относительное расстояние известно..
Странные у Вас какие то задачки..) 

[Igors]

Конечно. Нужно корректно ставить задачу.
Сейчас выясняется что есть ещё и шаг dt и т.д. и т.п..

Задачи "столкнутся ли (когда-нибудь) шарики" не ставилось. Но если вы/мы ее решаем, то рез-т должен быть "когда столкнутся" (через какое время), тогда в этом есть смысл. А чтобы ф-ция вернула да/нет это найденное время должно c чем-то сравниваться. В общем, dt возникает по Вашей же инициативе.

Ну и в чём проблема тогда? Скорость сближения/разбегания известна, относительное расстояние известно..

В упор не вижу никакого "относительного расстояния" в Вашем коде.

[Igors]

Мда, никаких пояснений не дождесся  А попробуешь спросить - получишь томом Ландау по рогам. Неужели все так сложно? Попробую-ка я. Вот чертеж (аттач). Известно AC (расстояние между центрами) и направление AB (разница скоростей).

Код

C++ (Qt)
bool BallsCollded( Ball & b1, Ball & b2, float dt = 1.0f )
{
// находим напр-е AB
  QVector3D vecAB = b1.speed - b2.speed;
  float curSpeed = vecAB.length();
 
// убедимся что разница скоростей достаточно велика 
  const double minSpeed = 1.0e-7;
  if (curSpeed < minSpeed) return false;
  vecAB /= curSpeed;
 
// находим длину AB как проекцию AC на напр-е AB
 QVector3D vecAC = b1.position - b2.position;
 float lenAB = QVector3D::dotProduct(vecAC, vecAB);
 
// если lenAB отрицательна, то шары расходятся
 if (lenAB <= 0) return false;
 
// по теореме Пифагора находим квадрат длины катета BC
 float lenBC2 = vecAC.lengthSquared() - lenAB * lenAB;
 
// если lenBC2 < квадрата (двойного) радиуса, то шарики никогда не пересекутся
 float R2 = Ball:radius * Ball:radius * 4;
 if (lenBC2 > R2) return false;
 
// из тр-ка DBC найдем длину BD
 float lenBD = sqrt(R2 - lenBC2);
 
// длина AD = время первого касания
 float t0 = lenAB - lenBD;
 
// успеют ли шарики столкнуться за время dt ?
 if (t0 * dt > curSpeed) return false;
 
// столкнулись, рассчитываем новые скорости
  ...
  return true;
}
 

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

Впрочем вопрос "когда столкнутся" не стоял, требовалось посчитать новые скорости если столкнулись. Все помнят как на уроках физики сталкивались тележки, ну и там "закон сохранения импульса" и все такое. Вспоминать все эти подробности совершенно необязательно. Две (одинаковых) тележки столкнулись - и обе поехали в обратные стороны. Первая стоит, вторая на нее наезжает - тогда первая поедет, вторая остановится. Выходит что если тележки одинаковы - они просто меняютcя (или обмениваются) скоростями.

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

[ssoft]

Как я понял из условия задачи: В некоторый момент времени нам были даны координаты и скорости шаров.  Вопрос: Столкнутся ли они в будущем? Всё.

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

Функция расстояния между двумя движущимися объектами выглядит так (выводится из теоремы косинусов)

ρ^2=(S_1-V_1∙t)^2+(S_2-V_2∙t)^2-2∙(S_1-V_1∙t)∙(S_2-V_2∙t)∙cos⁡〖α_12 〗



где

S₁ - расстояние от центра первого шара до точки пересечения траекторий;
S₂ - расстояние от центра второго шара до точки пересечения траекторий;
V₁ - скорость движения первого шара к точке пересечения траекторий (может быть отрицательной);
V₂ - скорость движения второго шара к точке пересечения траекторий (может быть отрицательной);
α₁₂ – внутренний угол треугольника между траекториями в месте их пересечения
t - момент времени

Зная расстояние, можно найти соответствующие моменты времени. Нужно решить квадратное уравнение относительно t: если корней нет - сближения на заданное расстояние не будет, если корни есть, то интересует ближайший (момент сближения).

Зная момент времени, можно рассчитать взаимное положение шаров в пространстве в момент удара (углы, направления движения и т.п.) и рассчитать "по законам сохранения импульса" новые характеристики движения шаров.

[ssoft]

Мда, никаких пояснений не дождесся   А попробуешь спросить - получишь томом Ландау по рогам. Неужели все так сложно? Попробую-ка я. Вот чертеж (аттач). Известно AC (расстояние между центрами) и направление AB (разница скоростей).
...

Геометрическое решение в относительном движении тоже правильное

Смущает только

Код

C++ (Qt)
// длина AD = время первого касания
 float t0 = lenAB - lenBD;
 
// успеют ли шарики столкнуться за время dt ?
 if (t0 * dt > curSpeed) return false;
 

Наверное, в соответствии с единицами измерения должно быть

Код

C++ (Qt)
// длина AD = время первого касания
 float lenAD = lenAB - lenBD;
 
// успеют ли шарики столкнуться за время dt ?
 if ( lenAD > curSpeed * dt ) return false;
 

[Igors]

но решение такой задачи на плоскости не сложное

А зачем ограничивать задачу 2D и связываться c S1 и S2? Если хотелось решать квадратное ур-е

#define DOT(a, b) QVector3D::dotProduct(a, b)

QVector3D origin = ball1.position - ball2.position;
QVector3D direction = ball1.speed - ball2.speed;
QVector3D diff = origin + direction * t;

// исходное ур-е
DOT(diff, diff) = 4 * radius * radius;

// тогда  для ур-я
a * t * t + b * t + c = 0;

Коэффициенты
a = DOT(direction, direction);   // или  direction.lengthSquared();
b = DOT(origin, direction) * 2;
c = DOT(origin, origin) - 4 * radius * radius;

Зная момент времени, можно рассчитать взаимное положение шаров в пространстве в момент удара (углы, направления движения и т.п.) и рассчитать "по законам сохранения импульса" новые характеристики движения шаров.

Как будто достаточно произнести 3 магических слова "закон сохранения импульса" - и все решится  И почему никто не скажет

И что с того закона? Новые скорости-то как считать?

Увы, непосредственность и свежесть мысли новичка быстро теряются с накоплением "опыта"

Наверное, в соответствии с единицами измерения должно быть

Да, верно

[ssoft]

Как будто достаточно произнести 3 магических слова "закон сохранения импульса" - и все решится  И почему никто не скажет

И что с того закона? Новые скорости-то как считать?

Увы, непосредственность и свежесть мысли новичка быстро теряются с накоплением "опыта"

Я думал, все знают как  ).

Для определения компонент новых векторов необходимо принять во внимание два уравнения:

- закон сохранения импульса (векторное уравнение)

m1*v1 + m2*v2 = const

- закон сохранения энергии

0.5 * m1*v1^2  + 0.5 * m2*v2^2 = const

В случае абсолютно упругого столкновения решением является

u1 = -v1 + 2 * (m1*v1 + m2*v2) / (m1 + m2);
u2 = -v2 + 2 * (m1*v1 + m2*v2) / (m1 + m2);

где
m - массы шаров
v - векторы скоростей до столкновения
u - векторы скоростей после столкновения

При равенстве масс, формулы упрощаются до неприличия

u1 = v2;
u2 = v1;

[ssoft]

Да забыл пояснить, что при нецентральном столкновении вышеописанные формулы работают с компонентами проекций векторов скоростей шаров на проходящую через их центры линию.

[Igors]

При равенстве масс, формулы упрощаются до неприличия

u1 = v2;
u2 = v1;

Об этом я уже сообщил выше 

Да забыл пояснить, что при нецентральном столкновении вышеописанные формулы работают с компонентами проекций векторов скоростей шаров на проходящую через их центры линию.

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

[Igors]

21) Вот эти "столбы света" (аттач) выглядят очень привлекательно. Как их делают?

[Igors]

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