Fast collision detection for non-deformable rigid bodies. From Jiggle Engine.

Автор: Иннокентий

<Innochenti> Значит так.
<Innochenti> при инициализации создается 3d сетка вокруг объекта, по сути bbox, только состоящий из cells(3д клеток)
<Innochenti> размерность такой сетки должна быть n >= 2
<kas> угу
<Innochenti> потом рассчитываем площадку каждой cell по формуле: dS = (max - min)/n
<Innochenti> ну фактически координаты каждой клетки dx,dy,dz. Затем, необходимо в пространстве bbox'а, рассчитать нормали  и  расстояния от поверхности объекта до границы BBOX'а
<Innochenti> ведь, нам надо считать контакт, а контакт это тройка понятий - глубина, нормаль, точка контакта.
<Innochenti> значит как считаем:
<Innochenti> for i,j,k to n,n,n
<Innochenti> pos = vector( minX + i*dx, minY + i*dy, minZ + i*dz )
<Innochenti> например, объект сферка
<Innochenti> т.е. x^2+y^2+z^2 = R^2
<kas> это точка контакта?
<kas> pos
<Innochenti> это точка в bbox
<kas> или
<Innochenti> min, max - BBOX
<kas> всё, понял, да
<Innochenti> поэтому что бы проверить лежит ли этот pos вне  сферы, надо
<Innochenti> проверить явл. ли x^2/R^2+y^2/R^2+z^2/R^2 > 1
<Innochenti> угу?
<kas> ага
<Innochenti> где x,y,z = это pos
<kas> вопрос, нафик для сферы ббоксы, если можно сразу? :)
<Innochenti> ну, я для примеру взял
<Innochenti> что бы проще
<Innochenti> ну дык вот, расстояние можно найти как dist = dist_closest_tr( pos, vector(R,R,R), closest_vert );
<kas> ага
<Innochenti> фанкшин dist_closest_tr вычисляет dist между pos и vector(R,R,R), при этом находит ближайший вершину между ними
<Innochenti> ну, а что бы найти нормаль, надо (closest - pos)/dist
<Innochenti> таким образом
<Innochenti> ты бегаешь по этим i,j,k bboxa
<Innochenti> и смотришь, если внутри то знак dist +, иначе -
<Innochenti> и одновременно вычисляешь dist и нормаль.
<Innochenti> это все делается на этапе инициализации.
<kas> клйово
<Innochenti> Шаги понятны?
<kas> ага
<Innochenti> счастье в чем.
<Innochenti> в инициализации ты хранишь n точке меша
<Innochenti> т.е. для сферки например, точек 16
<Innochenti> это надо, что бы потом проверять эти точки для collision
<kas> а потом можно быстро определять, да
<Innochenti> ну дык, поехали дальше
<Innochenti> когда уже идет проверка коллизий
<Innochenti> надо один объект перевести в пространство другого
<Innochenti> Position pos1 = body0->get_inv_orientation() *
<Innochenti>            (orig_pos1 - body0->get_position());
<Innochenti> затем black magic
<Innochenti>  Scalar fi = (pos[0] - m_min_x) / m_dx;
<Innochenti>  Scalar fj = (pos[1] - m_min_y) / m_dy;
<Innochenti>  Scalar fk = (pos[2] - m_min_z) / m_dz;
<Innochenti> ищем индексы в bbox
<Innochenti> int ii0 = (int) floor(fi);
<Innochenti>    int ij0 = (int) floor(fj);
<Innochenti>    int ik0 = (int) floor(fk);
<Innochenti> угу?
<kas> ммм
<Innochenti> т.е. какие cells будут участвовать в коллизии
<kas> пагади
<kas> счас дай я подумаю
<Innochenti> ну в первом коде ты получал floating координаты, во втором из них индексы в сетки
<Innochenti> а что бы получить позицию в сетке надо
<Innochenti>    Scalar x = fi - ii0;
<Innochenti>    Scalar y = fj - ij0;
<Innochenti>    Scalar z = fk - ik0;
<Innochenti> угу?
<kas> пагади
<kas> а pos ето кто?
<Innochenti> pos = body0->get_inv_orientation() *
<Innochenti>  (orig_pos1 - body0->get_position());
<Innochenti> всмысле тот который был pos1 ;) ну pos вообщем
<kas> ммм
<Innochenti> т.е. положение в пространстве первого объекта, а иначе как сетку юзать, если они в разных пространствах
<kas> ето центр тел получаецо?
<Innochenti> ну, просто позиция объекта.
<kas> ок
<Innochenti> ну дык вот.
<Innochenti> зная индексы сетки в которые попал pos объекта1
<Innochenti> и соответственно координаты этого pos в этой сетки
<Innochenti> мы, можем интерполировать между соседними cells
<Innochenti> и получать необходимые dists и normals
<Innochenti> а точка контакта будет равна orig_pos1 + normal * (0.5f * dist);
<Innochenti> все.
<kas> ээээ
<Innochenti> т.е. чем больше размерность сетки, тем точнее контакт
<kas> а, так мы каждую точки сетки преобразовываем
<Innochenti> ну вот вроде и фсе.
<Innochenti> быстрая зараза
<Innochenti> недостатки:
<Innochenti> для non-deformable тел
<Innochenti> т.е. только rigid :(
<Innochenti> можно конечно сетку пересчитывать, но это.. сам понимаешь..
<kas> ну, если тела редко деформируются
<kas> то сетку пересчитывать можно
<kas> клйовый метод
<kas> я как раз чото типа кармагедона хочу делать
<kas> :)
<Innochenti> плюсы:
<Innochenti> можно хранить карты dist'ов как 3d тексы
<Innochenti> и нормалей.
<Innochenti> но это такое дело..
<kas> ну, в плюсах исчо видимо мегаскорость
<kas> а пейпер есть какой-нить?
<Innochenti> deformed-distance-fields-for.pdf

18 января 2006