數學才是王道  

Posted by 藍斯洛 in

話說,元旦連續假日,大家都放假了,我還要上班。

把Code拿出來看看,想說處理一下引擎裡Bounding Box的計算。

找了一些Open Source的參考Code來看,想看看有沒有什麼比較有效率的演算方式來計算Bounding Box。

然後,我就愣住了。

眼前的這個演算法,把所有頂點的資料拿去算一個covariance matrix,再用這個matrix求解eigen vector以及eigen value,然後....就算出了包圍所有頂點的最佳的Oriented Bounding Box。eigen vector是OBB的三個軸向。用找到的三個軸向,來計算OBB的軸半徑。

我傻眼了。

eigen vector有那麼神嗎? 連這個都能算。還有covariance matrix究竟是什麼東西啊?

開始研究了幾天,總算是比較清楚整個運算的來龍去脈。

有時間整理出來的話,再拿來分享好了。

簡單的說,covariance matrix計算(x,y,z)數據的變異量以及彼此之間的影響,例如,x軸方向的數據,在y軸數據變動時,所受到的影響,這東西可以從最小平方差的總和,以偏微分取極值的方式導出類似的計算。

接下來這樣想,假設我們已經知道了OBB的三個軸向,我們就可以將所有的頂點(x,y,z),轉成在OBB座標系中的頂點(x',y',z'),而以(x',y',z')所計算得的covariance matrix,兩個不同的軸向(x'與y'或是 y'與z'等等...)之間的互相變異量應該是最小的,滿足這樣條件的三個軸向,就是最佳的OBB軸向。

這些計算一直演算下來,就出現了eigen value problem,所以最後eigen vector又出來幫忙,解決了問題。

好,結論。

結論就是....

數學才是王道啊!!

==========================================

Update: 原來還是看錯了,對應eigen vector的eigen value並不是軸半徑,covariance matrix只用來取得OBB的軸向。

This entry was posted on 2009年1月6日 星期二 at 星期二, 1月 06, 2009 and is filed under . You can follow any responses to this entry through the comments feed .

4 意見

喔喔喔!數學是大好物啊! XD

好久沒見到 Eigenvalue 和 Eigenvector 這兩個名詞了。以前上線性代數課程的時候有學過,不過現在已經忘得差不多了,期待你的心得分享~

2009年1月7日 上午9:27

藍斯洛你好啊!來個招呼先 :D
以往接觸過的數學,現在才知道它的用處哩。
那麼喜歡遊戲編程的網主也一定會喜歡數學的。加油啊~

2009年1月15日 上午10:57
匿名  

學數學就是為了偷吃步
這是我念數學系的感想

2009年1月18日 下午4:57
WeCan  

這部份我覺得跟圖形識別有點像
你可以參考看看圖形識別的書
同樣會透過 covariance matrix、
eigen vector、eigen value
來對一大筆資料做分析運算

2009年1月19日 上午9:41

張貼留言