Войти
ПрограммированиеФорумФизика

Помогите обобщить GJK-EPA/GJK-SAP на n-мерный случай...?

Advanced: Тема повышенной сложности или важная.

#0
0:29, 22 июля 2018

Короче мне нужно обобщить GJK-EPA на n-мерное  пространство?
Основная проблема у меня на данный момент в том что каждый раз когда я беру следующие направления для поиска следующей самой дальней точки (SupportPoint(Dir)) , то мне нужно использовать оператор CrossProduct чтоб сформировать все нужные направления для поиска конечного симплекса.  А дело в том что чем больше степеней свободы у пространства , тем от большего количества векторов надо для  CrossProduct. Например в 3-мерном пространстве CrossProduct зависит от двух векторов c=CrossProduct(a,b) , это потому что в 3-мерном пространстве могут быть только три вектора которые ортогональны друг к другу (c=CrossProduct(a,b) , a , b ) .! А вот например в 4-мерном пространстве могут быть 4-ортогональных друг к другу вектора , поетому в 4-мерном пространстве CrossProduct зависит от трёх векторов d=CrossProduct(a,b,c) , так как у 4-мерном пространстве есть 4-ортогональных друг к другу вектора (d=CrossProduct(a,b,c) , a , b , c ) ... Ну и.т.д !
А по скольку CrossProduct почти самый важный оператор для поиска последующей итерационой информации, от него зависит взятия всех нормалей (FaceNormal , EdgeToEdgeNormal) которые нужны для поиска конечного симпликса , то есть это значит что  и сам симплекс тоже должен быть обобщоный на n-мерное прстранство, например  в 3-мерном пространстве в симплекса должно быть 3-точки , а в 4-мерном пространстве в симплекса должно быть 4-точки .и.т.д в N-simplex должно быть (N-1) точек .
Причём все эти точки имеют розмерность N.
Где N-количество стипиней свободы текущего пространства !
Вопрос как мне адекватно сделать N-simplex?
Вот простой Пример что мне Нужно
FaceNormal = CrossProduct( Simplex.a , Simplex.b ,Simplex.c ......)!

Кароче помогите кодом , или хотябы советом. Мне нужна любая информация по данному вопросу...?


#1
5:33, 22 июля 2018

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

#2
12:45, 22 июля 2018

> CrossProduct
https://en.wikipedia.org/wiki/Levi-Civita_symbol

#3
12:50, 22 июля 2018

Suslik
Вроде довольно очевидно, что werasaimon о том обобщении, где
[cht]\operatorname{Cross}(a^{(1)},\;\dots,\;a^{(n)})_i=\varepsilon_{i j_1 \dots j_n} a^{(1)}_{j_1} \dots a^{(n)}_{j_n}[/cht]
которое тривиально строится для любой размерности. Здесь [cht]\varepsilon[/cht] -абсолютно антисимметричный тензор.

#4
13:11, 22 июля 2018

FordPerfect
Delfigamer
здорово, конечно, но какое это отношение имеет к GJK в более высоких размерностях? про EPA мне даже думать страшно.

и ещё вопросик, который меня больше всего волнует: нафига?

#5
22:52, 22 июля 2018

FordPerfect
Delfigamer
Верно !

Suslik
> векторное произведеие вообще-то определено только для трёхмерного и, кажется,
> семимерного пространства, оно вообще не обобщается тривиальным образом на
> остальные размерности.

Я обобщяю  CrossProduct  просто делая абсолютно кососиметричную матрицу соотвествущего ранга и розмерности потом умножаю на эту матрицу нужный мне вектор чтоб получить нужный CrossProduct  , и это подходить для любой розмерности n-space  , как и написал FordPerfect и Delfigamer . И мне это кажеться совершено очевидно !

Suslik
>но для GJK оно вообще не нужно, там нужны только
> операции с симплексами в общем виде. но чтобы их реализовать в общем виде,
чтоб сделать эти самые опирации с симплексом, просто необходимо так или иначе использовать  обобщоный CrossProduct, ибо как ты будешь строить FaceNormal на
N-симплексе с n-точек в n-мерном пространстве ? А делать раслоения на нижние измирения не эффективно.!

> не воровать код, который всегда оптимизируется под 2д/3д, а для начала
> разобраться, как вообще алгоритм работает. так что пролетаешь.
Я прекрасно знаю как работает GJK-EPA/GJK-SAP , если бы я незнал то даже не брался за их обобщения! И вообще это как тупо!

#6
22:58, 22 июля 2018

Suslik
> здорово, конечно, но какое это отношение имеет к GJK в более высоких
> размерностях? про EPA мне даже думать страшно.
Самое прямое , он нужен чтоб сделать те самые операции с симплексами в общем виде  сделать обобщёными на n-мерное прстранство!


Suslik
> и ещё вопросик, который меня больше всего волнует: нафига?
Хммм , дествительно зачем делать алгоритм для проверки колизии в  n-мерном пространстве.  Может для проверки колизии в n-мерном пространстве !

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

Тема в архиве.