碰撞检测技术——凸包的建立
-ZH1110
实时碰撞检测是机器人、动画仿真、虚拟现实等领域中一个非常关键的问题，其基本任务是确定两个或多个物体彼此之间是否发生接触或穿透。
多面体尤其是凸体良好的空间结构特性如空间连贯性可被利用来优化碰撞检测的效率。因此，基于多面体，尤其是基于凸体的碰撞检测算法一直是碰撞检测算法中的一个研究重点
一般的AABB,OBB树由于包围较松散，会产生较多的节点，我们选择研究凸包包围体,其包围物体紧密,但相互之间的求交计算更复杂
1．包围球的球心求法
设物体顶点坐标所含最大最小值分别为：xmax,xmin,ymax,ymin,zmax,zmin,则球心坐标为：
|
2．包围球半径的求法 r=
|
 |
2.凸包 凸包概念:点集Q的凸包(convex hull)是指一个最小凸多边形，满足Q中的点或者在多边形边上或者在其内。下图中由红色线段表示的多边形就是点集Q={p0,p1,...p12}的凸包。
平面凸包的求法：
凸包最常用的凸包算法是Graham扫描法和Jarvis步进法。
对于一个有三个或以上点的点集Q，过程如下：
计算点集最右边的点为凸包的顶点的起点，如上图的P3点。
Do
For i = 0 To 总顶点数
计算有向向量P3->Pi
If 其余顶点全部在有向向量P3->Pi的左侧或右侧，则Pi点为凸包的下一顶点
Pi点加入凸包列表
GoTo 1
End If
Next
Exit
Do
1:
Loop
此过程执行后，点按极角自动顺时针或逆时针排序，只需要按任意两点的次序就可以了。而左侧或右侧的判断可以用前述的矢量点积性质实现。
