防碰撞偵測之硬體設計與實現

Design and Implementation of ASIC for Anti-collision Detection

凃咨宸(Tzu-Chen Tu)

指導教授 ： 朱元三

國立中正大學/工學院/電機工程學系/碩士(2014年)

摘要

碰撞偵測有很多不同的應用，包括物理模擬、機器人、固體模型和虛擬實境等等，碰撞偵測的目標是判斷在三維空間裡兩個物件是否相交，就算現在的電腦已經比以前的電腦快了千百倍，碰撞偵測仍然是一大挑戰，特別是在三維空間裡，需要複雜的結構和演算法去處理龐大的資料運算。以往的碰撞偵測受限於CPU的執行速度而採取預先模擬，花費大量的時間而且難以達到即時偵測。
本篇論文利用碰撞偵測演算法將防碰撞偵測系統中需要大量運算的三角形碰撞偵測區塊實現在積體電路上，將能有效降低整個碰撞偵測系統的運算時間，達到即時防碰撞偵測系統。為了改良硬體的運算時間，本篇論文簡化了投影定理，再加上分離軸的選擇策略，將有效降低硬體部分的運算時間。

關鍵字

分離軸的選擇策略 ； 投影定理 ； 積體電路 ； 碰撞偵測

並列摘要

Collision detection is fundamental to many varied applications, including physical simulations, robotics, solid modeling, virtual reality and etc. The goal is to determine whether two objects in three dimension space intersect or not. Even though computers today are over a thousand times faster, collision detection is a key challenge to deal with such large data sets with complicated structures and algorithms. Collision detection is limited by the execution speed of the CPU and take pre-simulation, spend a lot of time and hard to achieve real time-time detection.
This theses uses collision detection algorithm to implement the triangle collision detection block on integrated circuit which needs a lot of computing in anti-collision detection system. It will be able to effectively reduce the collision detecting time to achieve real-time anti-collision detection system. This these simplifies the projection theorem and provides a strategy for selecting separating axis. It will effectively reduces the computing time for hardware design.

並列關鍵字

strategy for separating axis selecting ； projection theorem ； integrated circuit ； collision detection

參考文獻

[2] T. Möller, “A fast triangle-triangle intersection test,” Journal of Graphics Tools, vol. 2, no. 2, pp. 25–30, 1997.

[3] Held, “A collision of efficient and reliable intersection tests,” Journal of Graphics Tools, vol. 2, no. 4, pp. 31–44, 1997.

[4] P. Guigue and O. Devillers, “Fast and robust triangle-triangle overlap test using orientation predicates,” journal of graphics, gpu, and game tools, vol. 8, no. 1, pp. 25–42, 2003.

[5] A. T. Oren Tropp and I. Shimshoni, “A fast triangle to triangle intersection test for collision detection,” 2006.

[6] J.-W. Chang and M.-S. Kim, “Efficient triangle–triangle intersection test for obb-based collision detection,” Computers and Graphics, no. 33, p. 235–240, 2009.