以階層式碰撞預測為基礎之多邊形物體的連續時間碰撞偵測

Abstract

虛擬實境要能讓人有真實的感覺，就必須盡可能地把真實環境的種種特性 模擬出來。就模擬動態的環境而言，模擬移動物體的碰撞是最主要的部分 ，而其中碰撞偵測是其核心。因為碰撞會影響到物體的運動軌跡，所以當 碰撞的形況發生在模擬真實世界的系統中時，系統必需能夠偵測出來並且 修正這兩個物體的移動方向。過去碰撞模擬的研究多集中於離散時間的碰 撞偵測，但此類的方法無法模擬所有可能發的碰撞，所以本篇論文，我們 提出考量連續時間之一碰撞偵測系統。因為是以連續時間為基礎，所以不 會有在離散時間偵測法中遺漏掉碰撞的情形發生。為了有效執行碰撞偵測 的工作，我們亦提出階層式的碰撞預測架構。以bounding sphere為基礎 ，對於物體或組成物體的多邊形群間的碰撞，先以包含它們的bounding spheres作碰撞計算，再以此結果作為真正碰撞的預估，如此可以化簡掉 大量的真正之碰撞計算。我們另外亦提出一些技巧，加速碰撞偵測的效率 。 The detection of collision among moving objects is one of the major tasks in the dynamic simulation environment. The prior researches mostly focus on discrete-time solutions. This paper provides a continuous-time collision detection structure, which can simulate the collision among objects more precisely. Since the continuous-time collision detection is computationally exhaustive, we propose the hierarchical collision prediction scheme. The bounding spheres, which bound the whole/partial boundary of objects, can be substituted for the original objects to do the collision detection. So the collision time of two bounding spheres can be regarded as the predicted collision time of the two respective objects. Then with a sequence of the predicted collision times, we just calculate the most possible colliding object pairs, saving much calculation time. Since an object can be subdivided as a set of sub-objects, the collision calculation between two objects can be considered as a set of collision calculation of among these sub-objects. Therefore the collision prediction scheme can be applied to the calculation of one object pair, with the aid of hierarchical bounding spheres of objects which are constructed by subdividing objects recursively, and then finding the bounding spheres for each sub- objects in each level.