GJK碰撞检测算法的研究及改进，朱鹏程，孙劲光，碰撞检测是机器人、动画仿真与虚拟现实等领域中一个非常关键的问题,其基本任务是确定两个或多个物体彼此之间是否发生接触或穿透.�

GJK碰撞检测算法的研究及改进.doc

它使用 GJK 算法在多面体的 minkowsky 负和上找到最接近原点的点。 然后它使用重心坐标来找到属于 minkowsky 负和上选定点的那些多面体上的点。 Casey Muratori 制作的视频以及 Matthew Sheen 在 matlabcentral 上制作的 GJK 碰撞检测的实现对我了解我在做什么有很大帮助。 https://mollyrocket.com/849 https://www.mathworks.com/matlabcentral/fileexchange/57907-fast-3d-collision-detection-gjk-algorithm

gjk.c –平原C的Gilbert-Johnson-Keerthi 这是在普通C语言中粗略但快速地实现GJK冲突检测算法的功能。只有一个C文件，少于200行，没有依赖关系。 目前处于2D模式，即将推出完整的3D版本。此2D版本使用Minkowski求和，并在Minkowski空间中构建一个三角形单形，以判断两个任意凸多边形是否发生碰撞。 3D版本将大致相同，但将在3维Minkowski空间内构建一个四面体单形。 它当前仅指示是否存在碰撞。 距离和接触点的C代码即将推出。 免责声明 他妈的许可证和版权。 我这样做是出于学习目的，这是公共知识，任何用法都是完全免费的。 使用范例 这是的示例案例的。 将两个测试的多边形定义为纯C矢量结构类型的数组。 GJK的这种实现实际上并不关心数组中顶点的顺序，因为它将所有点集都视为凸多边形。 struct _vec2 { float x; float

GJK (Gilbert-Johnson-Keerthi) 碰撞检测算法在 MATLAB 中的实现。 GJK.m 函数获取形状顶点数据并返回两个形状是否穿透。 仅适用于凸形物体！ MAIN_example.m 对两个多面体进行动画处理，并在两者相互碰撞时停止。

openGJK {#mainpage} openGJK库使用Gilbert-Johnson-Keerthi（GJK）算法来计算凸多边形之间的最小距离。 该实现遵循“ ”中的描述，并已在Unix和Windows系统上针对C，C＃和Matlab程序进行了测试。 该库为研究人员提供了一种开箱即用的工具：您可以将其导入程序中，并用它来测量3D中两个凸多面体之间的距离。 它所需要的只是描述两个物体的顶点的坐标。 该库并未针对生产进行优化，但确实提供了全面而强大的实现。 对于大多数应用程序来说，它足够快，您也可以从此处构建以适合您自己的应用程序。 例如，openGJK不适用于增量版本，也不适用于NURBS，但它为此类特定应用程序提供了一个很好的起点。 入门 使用openGJK非常简单。 本指南将帮助您开始编译和使用openGJK。 我什么时候应该使用openGJK？ OpenGJK在设计时充分考虑了准确性和鲁棒性，适用于工程仿真。 该库的好用法包括有限元方法（FEM）和离散元方法（DEM）。 基本上，openGJK可以测量任何凸多面体之间的距离。 例如： 线段 三角形 四面体 立方体。

该存储库实现了GJK算法的新版本，可以计算3D中两个凸体之间的最小距离。 它所需要的只是[N x 3]矩阵中物体的坐标，其中N是定义物体的点数。 example2_mex / runme.m中提供了一个示例。 通过运行此文件，Matlab将编译一个MEX函数，此后称为。 要编译MEX函数，您需要C / C ++编译器，请参考Matlab文档或在下面留下评论。 感谢Chan Kwanyuan Chan给Windows用户的提示： Matlab用户需要在运行example2_mex / runme.m文件之前设置MinGW-w64 C / C ++编译器。 有关编译和相关设置过程的更多信息，请访问： https : //www.mathworks.com/matlabcentral/fileexchange/52848-matlab-support-for-mingw-w64-cc

实现的gjk算法，同时计算了epa穿插距离，碰撞两点。 放在这里，供大家和自己以后用

GJK计算碰撞代码的应用 //----------------------------------------------------------------------------- // Torque 3D // Copyright (C) GarageGames.com, Inc. // // The core algorithms in this file are based on code written // by G. van den Bergen for his interference detection library, // "SOLID 2.0" //----------------------------------------------------------------------------- #include "core/dataChunker.h" #include "collision/collision.h" #include "sceneGraph/sceneObject.h" #include "collision/convex.h" #include "collision/gjk.h" //---------------------------------------------------------------------------- static F32 rel_error = 1E-5f; // relative error in the computed distance static F32 sTolerance = 1E-3f; // Distance tolerance static F32 sEpsilon2 = 1E-20f; // Zero length vector static U32 sIteration = 15; // Stuck in a loop? S32 num_iterations = 0; S32 num_irregularities = 0; //---------------------------------------------------------------------------- GjkCollisionState::GjkCollisionState() { a = b = 0; } GjkCollisionState::~GjkCollisionState() { } //---------------------------------------------------------------------------- void GjkCollisionState::swap() { Convex* t = a; a = b; b = t; CollisionStateList* l = mLista; mLista = mListb; mListb = l; v.neg(); } //---------------------------------------------------------------------------- void GjkCollisionState::compute_det() { // Dot new point with current set for (int i = 0, bit = 1; i < 4; ++i, bit <<=1) if (bits & bit) dp[i][last] = dp[last][i] = mDot(y[i], y[last]); dp[last][last] = mDot(y[last], y[last]); // Calulate the determinent det[last_bit][last] = 1; for (int j = 0, sj = 1; j < 4; ++j, sj <<= 1) { if (bits & sj) { int s2 = sj | last_bit; det[s2][j] = dp[last][last] - dp[last][j]; det[s2][last] = dp[j][j] - dp[j][last]; for (int k = 0, sk = 1; k < j; ++k, sk <<= 1) { if (bits & sk) { int s3 = sk | s2; det[s3][k] = det[s2][j] * (dp[j][j] - dp[j][k]) + det[s2][last] * (dp[last][j] - dp[last][k]); det[s3][j] = det[sk | last_bit][k] * (dp[k][k] - dp[k][j]) + det[sk | last_bit][last] * (dp[last][k] - dp[last][j]); det[s3][last] = det[sk | sj][k] * (dp[k][k] - dp[k][last]) + det[sk | sj][j] * (dp[j][k] - dp[j][last]); } } } } if (all_bits == 15) { det[15][0] = det[14][1] * (dp[1][1] - dp[1][0]) + det[14][2] * (dp[2][1] - dp[2][0]) + det[14][3] * (dp[3][1] - dp[3][0]); det[15][1] = det[13][0] * (dp[0][0] - dp[0][1]) + det[13][2] * (dp[2][0] - dp[2][1]) + det[13][3] * (dp[3][0] - dp[3][1]); det[15][2] = det[11][0] * (dp[0][0] - dp[0][2]) + det[11][1] * (dp[1][0] - dp[1][2]) + det[11][3] * (dp[3][0] - dp[3][2]); det[15][3] = det[7][0] * (dp[0][0] - dp[0][3]) + det[7][1] * (dp[1][0] - dp[1][3]) + det[7][2] * (dp[2][0] - dp[2][3]); } } //---------------------------------------------------------------------------- inline void GjkCollisionState::compute_vector(int bits, VectorF& v) { F32 sum = 0; v.set(0, 0, 0); for (int i = 0, bit = 1; i < 4; ++i, bit <<= 1) { if (bits & bit) { sum += det[bits][i]; v += y[i] * det[bits][i]; } } v *= 1 / sum; } //---------------------------------------------------------------------------- inline bool GjkCollisionState::valid(int s) { for (int i = 0, bit = 1; i < 4; ++i, bit <<= 1) { if (all_bits & bit) { if (s & bit) { if (det[s][i] <= 0) return false; } else if (det[s | bit][i] > 0) return false; } } return true; } //---------------------------------------------------------------------------- inline bool GjkCollisionState::closest(VectorF& v) { compute_det(); for (int s = bits; s; --s) { if ((s & bits) == s) { if (valid(s | last_bit)) { bits = s | last_bit; if (bits != 15) compute_vector(bits, v); return true; } } } if (valid(last_bit)) { bits = last_bit; v = y[last]; return true; } return false; } //---------------------------------------------------------------------------- inline bool GjkCollisionState::degenerate(const VectorF& w) { for (int i = 0, bit = 1; i < 4; ++i, bit <<= 1) if ((all_bits & bit) && y[i] == w) return true; return false; } //---------------------------------------------------------------------------- inline void GjkCollisionState::nextBit() { last = 0; last_bit = 1; while (bits & last_bit) { ++last; last_bit <<= 1; } } //---------------------------------------------------------------------------- //---------------------------------------------------------------------------- //---------------------------------------------------------------------------- void GjkCollisionState::set(Convex* aa, Convex* bb, const MatrixF& a2w, const MatrixF& b2w) { a = aa; b = bb; bits = 0; all_bits = 0; reset(a2w,b2w); // link mLista = CollisionStateList::alloc(); mLista->mState = this; mListb = CollisionStateList::alloc(); mListb->mState = this; } //---------------------------------------------------------------------------- void GjkCollisionState::reset(const MatrixF& a2w, const MatrixF& b2w) { VectorF zero(0,0,0),sa,sb; a2w.mulP(a->support(zero),&sa); b2w.mulP(b->support(zero),&sb); v = sa - sb; dist = v.len(); } //---------------------------------------------------------------------------- void GjkCollisionState::getCollisionInfo(const MatrixF& mat, Collision* info) { AssertFatal(false, "GjkCollisionState::getCollisionInfo() - There remain scaling problems here."); // This assumes that the shapes do not intersect Point3F pa,pb; if (bits) { getClosestPoints(pa,pb); mat.mulP(pa,&info->point); b->getTransform().mulP(pb,&pa); info->normal = info->point - pa; } else { mat.mulP(p[last],&info->point); info->normal = v; } info->normal.normalize(); info->object = b->getObject(); } void GjkCollisionState::getClosestPoints(Point3F& p1, Point3F& p2) { F32 sum = 0; p1.set(0, 0, 0); p2.set(0, 0, 0); for (int i = 0, bit = 1; i < 4; ++i, bit <<= 1) { if (bits & bit) { sum += det[bits][i]; p1 += p[i] * det[bits][i]; p2 += q[i] * det[bits][i]; } } F32 s = 1 / sum; p1 *= s; p2 *= s; } //---------------------------------------------------------------------------- bool GjkCollisionState::intersect(const MatrixF& a2w, const MatrixF& b2w) { num_iterations = 0; MatrixF w2a,w2b; w2a = a2w; w2b = b2w; w2a.inverse(); w2b.inverse(); reset(a2w,b2w); bits = 0; all_bits = 0; do { nextBit(); VectorF va,sa; w2a.mulV(-v,&va); p[last] = a->support(va); a2w.mulP(p[last],&sa); VectorF vb,sb; w2b.mulV(v,&vb); q[last] = b->support(vb); b2w.mulP(q[last],&sb); VectorF w = sa - sb; if (mDot(v,w) > 0) return false; if (degenerate(w)) { ++num_irregularities; return false; } y[last] = w; all_bits = bits | last_bit; ++num_iterations; if (!closest(v) || num_iterations > sIteration) { ++num_irregularities; return false; } } while (bits < 15 && v.lenSquared() > sEpsilon2); return true; } F32 GjkCollisionState::distance(const MatrixF& a2w, const MatrixF& b2w, const F32 dontCareDist, const MatrixF* _w2a, const MatrixF* _w2b) { num_iterations = 0; MatrixF w2a,w2b; if (_w2a == NULL || _w2b == NULL) { w2a = a2w; w2b = b2w; w2a.inverse(); w2b.inverse(); } else { w2a = *_w2a; w2b = *_w2b; } reset(a2w,b2w); bits = 0; all_bits = 0; F32 mu = 0; do { nextBit(); VectorF va,sa; w2a.mulV(-v,&va); p[last] = a->support(va); a2w.mulP(p[last],&sa); VectorF vb,sb; w2b.mulV(v,&vb); q[last] = b->support(vb); b2w.mulP(q[last],&sb); VectorF w = sa - sb; F32 nm = mDot(v, w) / dist; if (nm > mu) mu = nm; if (mu > dontCareDist) return mu; if (mFabs(dist - mu) <= dist * rel_error) return dist; ++num_iterations; if (degenerate(w) || num_iterations > sIteration) { ++num_irregularities; return dist; } y[last] = w; all_bits = bits | last_bit; if (!closest(v)) { ++num_irregularities; return dist; } dist = v.len(); } while (bits < 15 && dist > sTolerance) ; if (bits == 15 && mu <= 0) dist = 0; return dist; }