Программирование игр, создание игрового движка, OpenGL, DirectX, физика, форум
GameDev.ru / Программирование / Форум / Нужен GJK_distance_of_closest_points_in_3D

Нужен GJK_distance_of_closest_points_in_3D

werasaimonПостоялецwww13 фев. 20188:29#0
Нужен GJK algorithm distance of closest points in 3D . Этот GJK должен искать критические ( ближайшие ) точки между парой геометрий тогда когда нет коллизии , ну то бишь тогда когда сума простра́нства минко́вского пары геометрий не содержыт внутри себя начало координат (нет коллизии).
А верней GJK должен искать критический симплекс c наружы CSO  , и уже относительно его просчитывать барицентрические  координаты для критических точек ?
Я понимаю что это почти тоже самое что обычный  GJK будет искать критический симплекс критический симплекс для EPA , только это будет дороже , и снаружи CSO  !?

P.S: GJK-EPA меня не интересует , мне надо именно GJK-Distance 3D , может кто подскажет где подглядеть код ?
А если у вас есть готовая реализация GJK-Distance 3D на любом языке программирования , то поделитесь ?  А то мне очень лень самому это писать !

CSO (  Configuration Space Obstacle  )
EPA  (  Expanding Polytope Algorithm )
GJK  (  Gilbert–Johnson–Keerthi          )
CCD ( Continuous Collision Detection )


P.S: Кстати кто то знает что это за люди  Gilbert , Johnson , Keerthi , в интернете про них 0% инфы , особенно меня интересует это имя  Gilbert ?

Правка: 13 фев. 2018 9:06

SuslikМодераторwww13 фев. 201810:01#1
werasaimon
gjk есть в буллете, код которого ты давно подворовываешь. ищи внимательнее.

Правка: 13 фев. 2018 10:02

nonamezeroxПостоялецwww13 фев. 201810:16#2
Кстати кто то знает что это за люди  Gilbert , Johnson , Keerthi

http://www.keerthis.com/

http://www.cs.columbia.edu/2016/david-johnson-in-memoriam/

https://aero.engin.umich.edu/people/elmer-gilbert/

werasaimonПостоялецwww14 фев. 20180:28#3
Suslik
> gjk есть в буллете, код которого ты давно подворовываешь. ищи внимательнее.
>
я знаю , я уже взял gjk с буллета ! Что поделаешь люблю я этот SDK!.
Но сейчас мне нужно не много другое , мне нужно максимально простая примитивная реализация gjk-distance , для исследования!?

P.S вот чего я не могу понять в структуре MinkowskiDiffe в Bullet'e зачемь так заморачиваться с композицией переобразовании в support mapping .
Вот так это делаеться в Bullet : 
Support0( dir )
{
  shape0->support( dir ) 
}

Support1( dir )
{
    transform0.inverse() * transform1 * shape1->support ( dir *
    transform0.basis() * transform1.basis().transpose() )
}

Support(dir)
{
    Support1(dir) - Support(-dir)
}


https://github.com/bulletphysics/bullet3/blob/master/src/BulletCo… n/btGjkEpa3.h
---------------------------------------------------------------------------------------
Вот так это делаю я:
Support0( dir )
{
  transform0 * shape0->support( transform0.basis().transpose() * dir ) 
}

Support1( dir )
{
transform1 *  shape1->support ( transform1.basis().transpose() * dir )
}

Support( dir )
{
    Support1(dir) - Support(-dir)
}


Другими словами почему support mapping в Bullet'e находиттся в локальном пространстве transform0 , а не так как у меня сразу в глобальном пространстве . Видь так как у меня , мы сразу на выходе получаем критические точки(ближайшие) в глобальном пространстве.  И их не нужно дополнительно умножать на transform0 как это делаеться в Bullet !
Первый и второй подход работают абсолютно одинаково , видь это одно и тоже ! В чём же смысел подхода bullet'a ..?

nonamezerox
О спасибо , очень интиресно !

Правка: 14 фев. 2018 0:36

SuslikМодераторwww14 фев. 20181:56#4
werasaimon
> Другими словами почему support mapping в Bullet'e находиттся в локальном
> пространстве transform0 , а не так как у меня сразу в глобальном пространстве .
> Видь так как у меня , мы сразу на выходе получаем критические точки(ближайшие)
> в глобальном пространстве.  И их не нужно дополнительно умножать на transform0
> как это делаеться в Bullet !
> Первый и второй подход работают абсолютно одинаково , видь это одно и тоже ! В
> чём же смысел подхода bullet'a ..?
то есть из-за того, что такую мелочь в их реализации не можешь под себя настроить, ищешь другую релизацию? мде.

по поводу вопроса — возможно, они ищут контакты в системе координат одного из тел, потому что так лучше работает их temporal coherence.

werasaimonПостоялецwww15 фев. 20180:53#5
Suslik
> то есть из-за того, что такую мелочь в их реализации не можешь под себя
> настроить, ищешь другую релизацию? мде.
Почему ? Я всё замечательно настроил под себя. И всё норм работает  ! Мне просто нужен был чистый gjk без всяких там коллизий, для исследования . 
Видь изначально gjk был придуман для нахождения минимального расстояния между выпуклыми шейпами .
Ну собственно я уже извлек  чистый  gjk из реализации bullet'a .!

кстати моя реализация GJK-EPA почти на 5-7% быстрей , и иногда находит SeparationAxis  точней чем gjk-epa в bullet"e .
но это скорей всего и за неправильной дефектной настройкой gjk-epa в bullet

P.S: Просто я очень ленивый , и думал что кто даст уже готовый код !
P.S: в физике и математики мелочей не бывает, важно всё, каждый болтик!


Suslik
> по поводу вопроса — возможно, они ищут контакты в системе координат одного из
> тел, потому что так лучше работает их temporal coherence.
Наверно я делаю что то не так , но по моему опыту
temporal coherence почему-то работает абсолютно идентично что в первом что во втором варианте ?
Да и в самом bullet'e есть функции где используется второй вариант !
P.S: как вообще статические преобразования могут влиять на  temporal coherence ?

Правка: 15 фев. 2018 13:00

werasaimonПостоялецwww19 фев. 20186:02#6
Написал gjk-epa , очень просто для восприятия https://github.com/werasaimon/gjk-epa?files=1
Может кому пригиодиться..!
SuslikМодераторwww19 фев. 20187:39#7
werasaimon
> Написал gjk-epa , очень просто для восприятия
> https://github.com/werasaimon/gjk-epa?files=1
это вообще не EPA. это кривая реализация обычного GJK. совет — для обычного GJK едва ли не самая главная фишка — это termination condition. имеет смысл подумать, как его сформулировать лучше, чем abs(dist - prevDist) < eps.

Правка: 19 фев. 2018 7:40

werasaimonПостоялецwww19 фев. 201820:55#8
Suslik
> это вообще не EPA. это кривая реализация обычного GJK. совет — для обычного GJK
> едва ли не самая главная фишка — это termination condition. имеет смысл
> подумать, как его сформулировать лучше, чем abs(dist - prevDist) < eps.

А что при такой реплизации abs(dist - prevDist) < eps  , GJK может не там закончиться  ?
А почему не EPA, вроде как penetration-collision и axisSeparation ищет EPA ,  или я что-то путаю ?

P.S:  не всё таки у меня в коде именно gjk-epa http://www.dyn4j.org/2010/05/epa-expanding-polytope-algorithm/

Правка: 20 фев. 2018 14:09

/ Форум / Программирование игр / Физика

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