Разработка физики для игр
GameDev.ru / Сообщества / Физика для игр / Статьи / Collision Detection для геометрий, заданных SupportMapping'ом

Collision Detection для геометрий, заданных SupportMapping'ом

Автор:

О чём эта статья
В этой статье я расскажу о самом общем способе задания произвольной выпуклой геометрии, о Support Mapping'е, и о своём эксклюзивном алгоритме Collision Detection'а для них, который вы всегда можете посмотреть в действии в моих двигах - Destruction 3d и Destruction 2d.


Support Mapping
Итак начнём. Что же такое саппорт мэппинг? Прежде всего, это очень удобный способ для хранения и работы с выпуклыми телами, вне зависимости от размерности пространства - 2d или 3d. Задать геометрию A саппорт мэппингом SMap - это значит сопоставить каждому направлению v её экстремальную точку p. На математическом языке можно записать как:
SMap(v) = p : p in A, p * v = max
А на человеческом, геометрия должна знать, какая её точка "самая далёкая" в каждом направлении. Проиллюстрирую на примерах эллипса и прямоугольника, где стрелками показаны направления, а кружочками тех же цветов - экстремальные вертексы, им соответствующие.
Изображение

Операции с саппорт мэппингом
Если у нас есть геометрии A и B, заданные соответственно мэппингами SMapa и SMapb, то, различным образом их комбинируя, мы можем задавать мэппинг SMapc и соответвующую ему геометрию C. Вот несколько примеров:

* SMapc(v) = - SMapa(-v)
Это - отражение геометрии относительно начала координат
Изображение

* SMapc(v) = (SMapa(v) * v > SMapb(v) * v) ? SMapa(v) : SMapb(v);
Фактически, выбор "самой дальней" в направлении v точки из двух саппорт мэппингов
Выпуклая оболочка(convex hull) геометий A и B
Изображение

* SMapc(v) = SMapa(v) + SMapb(v)
Сумма Минковского двух геометрий. Очень важный математический объект, вся полезность которого будет раскрыта далее
Изображение

Нахождение Penetration Depth вектора
Определим разницу Минковского(Minkowsky difference) как сумму одной геометрии и инвертированной другой:
SMapcso(v) = SMapa(v) + (- SMapb(-v)) = SMapa(v) - SMapb(-v)

Геометрия, которую пораждает мэппинг SMapcso, называется Configuration Space Obstacle(CSO) и обладает интересными и крайне полезными для нас свойствами:

  • если CSO содержит начало координат, то две геометрии пересекаются.
  • если геометрии пересекаются незначительно, то начало координат находится близко к поверхности CSO
  • пересечение луча выходящего из начала координат с CSO - это вектор, называемый Directional Penetration Depth(DPD) - минимальное расстояние, на которое нужно раздвинуть геометрии вдоль этого луча, чтобы они перестали пересекаться
  • минимальный из всех существующих Directional Penetration Depth векторов называется просто Penetration Depth(PD) и обозначает минимальное смещение, на которое нужно переместить одну из геометрий, чтобы они перестали пересекаться

    Чтобы "прочувствовать" свойства CSO, советую глянуть джава апплеты на этом саете

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

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

    1) Изначально значение PD инициализируется каким-то "не слишком далёким" значением, к примеру, центральной разницей двух геометрий или значением PD с предыдущего кадра нашей физической симуляции, назовём этот вектор pd. В ходе работы алгоритма он будет итеративно приближаться к реальному значению PD.

    2) Далее находится такой вектор v, что:
    SMapcso(v) = DPD(pd);
    То есть саппорт пойнт CSO в направлении v совпадает с DPD в направлении pd:
    Изображение
    На рисунке фиолетовым цветом обозначена CSO. Красным - начало координат. Жёлтым - текущий вектор pd. Зелёным - искомый вектор v
    и выполняется вышеизложенное требование:
    OA = SMapcso(v) = DPD(pd);

    3) Если угол между вектором pd и v меньше некоего порогового значения, скажем, 1e-3fрад, то возвращаем значение PD = pd и выходим, иначе присваем pd = v и идём снова выполнять пункт 2

    Выполняя вот такую последовательность действий, алгоритм очень быстро(1-5 итераций) сходится к такому направлению pd, что луч, выпущенный из начала координат в этом направлении, пересекает CSO под прямым углом. При малых взаимопроникновениях(начало координат находится очень близко к CSO) таких направления всего два - интересующий нас PD и направление, примерно ему противоположенное, на обратной стороне CSO. Алгоритм теоретически может сойтись к этой точке, если pd инициализировать каким-то слишком "левым" значением, но лично мне это ни разу не удавалось :)

    Также может быть следующий случай:
    Изображение, когда алгоритм сойдётся к любому из жёлтых направлений. Какзалось бы, одно из этих направлений - это неверное направление PD! Но прелесть в том, что для реальной физической симуляции совершенно неважно, какое из них выбрать - их DID'ы примерно одинакового порядка малости.

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

    И всё было бы просто замечательно, если б не один вопрос - а как же искать такое хитрое направление v из пункта 2? К сожалению, на момент написания статьи я всё ещё не разглашаю 3д версию этого алгоритма, но 2д постараюсь изложить.

    Нахождение вспомогательной задачи из пункта 2
    Для нахождения вспомогательного вектора v для направления pd, вновь используем итеративный подход:

    1) инициализируем вектор v каким-то значением, к примеру, текущим значнием pd

    2) Ищем пересечение плоскости, касающейся CSO в точке S = SMap(v) (v обозначен зелёным) c вектором pd(обозначен жёлтым), и точку пересечения обозначим как A(синяя).
    Изображение
    Если вектор OA противоположенно направлен вектору pd, то тела не пересекаются, прекращаем работу алгоритма. Иначе следуем далее.

    3) если вектор SA по модулю меньше некоторого малого значения(скажем, 1e-4f), то возвращаем текущий вектор v, иначе прибавляем к текущему вектору v вектор SA, умноженный на малую величину eps, нормализуем результат и возвращаемся к пункту 2)
    ремарка:
    здесь можно сделать чуть более хитрый termination condition, чтобы алгоритм не "скакал" с одной вершины многогранника на другую:
    возвращать результат можно в случае, если мы не можем укоротить вектор OA, скажем, четыре итерации подряд

    Значение eps характеризует скорость сходимости этого алгоритма - при слишком маленьких eps он будет сходиться долго, а при слишком больших - "скакать" вокруг искомого значения, что может вызвать ещё более долгую сходимость. Сейчас я не буду останавливаться на методах оценки требуемого значния eps, оставлю эту увлекательную задачу читателю подумать на досуге :)

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

  • Страницы: 1 2 Следующая »

    6 сентября 2008

    #collision detection, #manifold generation, #support mapping


    Обновление: 7 ноября 2011

    2001—2018 © GameDev.ru — Разработка игр