碰撞检测算法
kaifeng.zhu
我所能想到的是遍历场景中的任意两个物体，根据它们的线形速度和旋转速度，列出方程组求解碰撞时间，有解并且解大于零说明它们俩可能发生碰撞。
但这种方法好像计算复杂度太高了…
Milo Yip
detection (CCD)。你所描述的是CCD。
DCC的壞處是，高速物體可能會穿越物體。
然而，正常情況下是不需要n*(n-1)次檢測。在進行精確的物體對物體檢測(narrow phase)之前，會先進行粗略的檢測(broad phase)。
以CCD來說，可以用swept volume描述一毎物體在某時間區段內的體積，然後利用swept-and-prune等方法去進行broad
phase，找出有機會碰撞的物體對。
narrow phase方面，除了編寫每種形狀組合的碰撞檢測(如球體對球體、球體對長方體、長方體對長方體等)，當中可能會使用separating
axis theorem(SAT)。另外還可使用Gilbert–Johnson–Keerthi(GJK)算法。但這些自法都是針對凸形狀而設，凹的形狀通常要分解成凸形狀的集合。
以下是一些相關的書籍:
http://book.douban.com/subject/2586364/
http://book.douban.com/subject/5489586/
http://book.douban.com/subject/1427606/
2011/11/7 kaifeng.zhu <caf...@gmail.com>:
> 常见的碰撞检测算法有哪些？各有什么优缺点？
>
> 我所能想到的是遍历场景中的任意两个物体，根据它们的线形速度和旋转速度，列出方程组求解碰撞时间，有解并且解大于零说明它们俩可能发生碰撞。
> 但这种方法好像计算复杂度太高了…
>
--
Milo Yip
http://www.cnblogs.com/miloyip/
http://weibo.com/miloyip/
http://twitter.com/miloyip/
Milo Yip
DCC -> DCD
phase -> phrase
swept-and-prune -> sweep-and-prune
2011/11/7 Milo Yip <mil...@gmail.com>:
> 碰撞檢測基本可分為兩種: discrete collision detection(DCD) 和 continuous collision
> detection (CCD)。你所描述的是CCD。
>
> DCC的壞處是，高速物體可能會穿越物體。
>
> 然而，正常情況下是不需要n*(n-1)次檢測。在進行精確的物體對物體檢測(narrow phase)之前，會先進行粗略的檢測(broad phase)。
>
> 以CCD來說，可以用swept volume描述一毎物體在某時間區段內的體積，然後利用swept-and-prune等方法去進行broad
> phase，找出有機會碰撞的物體對。
>
> narrow phase方面，除了編寫每種形狀組合的碰撞檢測(如球體對球體、球體對長方體、長方體對長方體等)，當中可能會使用separating
> axis theorem(SAT)。另外還可使用Gilbert–Johnson–Keerthi(GJK)算法。但這些自法都是針對凸形狀而設，凹的形狀通常要分解成凸形狀的集合。
>
> 以下是一些相關的書籍:
> http://book.douban.com/subject/2586364/
> http://book.douban.com/subject/5489586/
> http://book.douban.com/subject/1427606/
--