跳到主要內容

臺灣博碩士論文加值系統

(44.201.99.222) 您好!臺灣時間:2022/12/04 01:07
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:王瑞龍
研究生(外文):Wang, Jui-Lung
論文名稱:任意運動中的多面體物件之近似與精確碰撞偵測
論文名稱(外文):Approximate and exact collision detection among polyhedral objects in arbitrary motion
指導教授:范欽雄范欽雄引用關係
指導教授(外文):Chin-Shyurng Fahn
學位類別:碩士
校院名稱:國立台灣工業技術學院
系所名稱:電機工程技術研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:1997
畢業學年度:85
語文別:中文
論文頁數:55
中文關鍵詞:碰撞偵測計算機圖學虛擬實境
外文關鍵詞:collision detectioncomputer graphicsvirtual reality
相關次數:
  • 被引用被引用:1
  • 點閱點閱:275
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
本論文提出在電腦系統所模擬的三度空間圖形環境中之物件間的碰撞
偵測演算法。在此環境中,所有物件係由凸多邊形所構成之凸或凹多面體
,它們能進行任意平移或且旋轉的運動。我們的演算法可直接使用於這些
多面體,且在實際的應用上,必須有兩種不同的解決方法,即為離散時間
與連續時間的碰撞偵測,其中前者能夠於固定的時間點偵測碰撞事件之發
生位置,而後者能夠於一個時間的區格內決定碰撞事件之近似發生時間與
位置。 首先,我們使用"空間劃分"(space cell)的方法來局部搜尋物
件與物件間之碰撞事件,它是將三度空間分割為較小之隔間(cell),然後
,針對運動物件所處的隔間中做物件與物件間的碰撞偵測,以減少物件間
之偵測次數。接著,一個"方位─仰角映射"(azimuth-elevation map)的
方法被提出來,它係藉由事先將物件的頂點以球體座標值做排序,來快速
地選擇在物件重疊區域中之多邊形。其後,利用外接箱體(bounding box)
的方式,提出一個"分割並解決"(divide-and-conquer)的方法,以降低需
要做多邊形交錯測試之多邊形的數量。為了處理離散時間與連續時間之碰
撞偵測, 我們提出了兩個多邊形交錯測試的方法,它們皆使用階層的實
現方式以精簡不必要之計算。 所有的實驗係在Pentium Pro-180配
備64M RAM之個人電腦上,使用微軟Visual C/C++4.0編譯器於微軟
Windows NT 4.0作業系統下完成。如文中之實驗所示,空間劃分的方法之
時間複雜度係隨物件之數量呈現近似線性地增長。當外接球體(bounding
sphere)能簡潔地包住物件所佔用之空間時,則方位─仰角映射的方法將
較所有多邊形皆對重疊區域做測試的方法為快,而分割並解決的方法也能
夠節省大量的計算時間。最後,我們驗證了所提出之連續時間的碰撞偵測
演算法,並將它和離散時間的碰撞偵測演算法做比較,以瞭解它所需要的
計算量。截至目前為止,本論文所提出的方法之實驗結果令人鼓舞。
This thesis presents the algorithms for collision detection in
a 3-Dgraphical environment simulated by a computer system, where
all the objectsare represented as polyhedral ones and perform
arbitrary translating and/orrotating motions. These algorithms
can be directly used for both convex andconcave objects which
consist of convex polygons. In the realisticapplications, there
require two kinds of solutions: time-interrupted andtime-
continuous collision detection; the former can detect the exact
positionof a collision event at a fixed time step, and the
latter can determine bothapproximate time and position of a
collision event. The algorithms first localize the object-to-
object collision events by the"space cell" method which divides
the 3-D environment into small cells. Inthis manner, only those
cells that intersect moving objects are examined inorder to
reduce the number of testing a pair of bounding volumes
surroundingthe objects. An azimuth-elevation map method is then
proposed to quicklyselect the polygons in the overlap region
between two candidate objects bypresorting their vertices in the
spherical coordinates system. Afterperforming that, a divide-
and-conquer method which takes advantage of thebounding box
representation is presented to moderate the number of
thepolygons needed to be checked by a polygon-to-polygon
intersection test. Todeal with the time-interrupted and time-
continuous collision detection, twopolygon-to-polygon
intersection testing methods based on a hierarchicalscheme are
developed to reduce unnecessary computation. All the
experiments are made by using the Microsoft Visual C/C++
4.0compiler under the operation system Microsoft Windows NT 4.0
of a personalcomputer with a Pentium Pro-180 CPU and 64M RAM. As
shown in the experiments,the time complexity of the space cell
method grows near linearly as theamount of objects increases.
When the bounding sphere of an object exactlyembraces its
occupied space, the azimuth-elevation map method is
moreefficient than the enumerative method for selecting all the
polygons withinor across the overlap region. The divide-and-
conquer method can economizelots of computing time as the
experiments reveal. The time-continuouscollision detection
algorithm is successfully verified, and also compared withthe
time-interrupted collision detection one to understand its
computationloading. So far, all the experimental results from
our proposed methods arevery encouraging.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關期刊