Finding Oriented Bounding Box  

Posted by 藍斯洛 in

前一陣子發現計算OBB的演算法,研究了幾天,本以為大致都了解了,但深入去思考推導之後,卻才發現,原來我是錯得離譜,Totally Wrong!! (翻譯叫做 "一整個錯!!")

於是又從頭開始,一步一步從數學的角度來看。

觀念還是一樣,把美術模型的每一個頂點,都當做是取樣點,然後用Least Square Fit的方法,找出OBB需要的中心點以及三個軸向。

OBB的中心點取得,根據的是偏微分取極值的方法,三個軸向呢,則是用Principal Axis的概念,從Eigen vector來取得。

底下是兩個參考資料。

http://mathworld.wolfram.com/LeastSquaresFitting.html

http://www.geometrictools.com/Documentation/LeastSquaresFitting.pdf

這個推導,背後的數學有點小複雜,不過,大概都是些矩陣向量的運算概念。

最後呢,得到一個取得OBB的步驟。

1. 先建立一個可以解出Eigen value, Eigen vector的函式庫(或者去抄一個)

2. 把所有頂點座標加起來,找出平均值,就是OBB的中心。

3. 對於每一個頂點,計算與中心點在 x,y,z 三個方向的誤差值 X,Y,Z ,取得兩兩相乘的值,XX, XY, XZ, YY, YZ, ZZ,把每個頂點所算出來的這六個值,全部加起來平均。然後塞到一個3x3的矩陣內。

4. 把這個矩陣丟給Eigen System求解,拿回三個Eigen vector。

5. 用這三個Eigen vector得到的座標系統,轉換原來的頂點,找出在這個座標系統中的Box長寬高。

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

7 意見

xinxin  

求推荐求Eigen vector的函数库 - -

2009年3月8日 上午9:34

hmm....
我知道的是,Ogre的數學函式庫裡,有這一組Eigen System可以使用。

2009年3月12日 上午9:26
xinxin  

55我快崩溃了....什么JACOBI呀QR的Hessenberg的都用过了....对偏离坐标轴一定角度的方体状就是包围不好....继续尝试ING

2009年3月15日 下午2:36
匿名  

請問關於第三個步驟 -> 把每個頂點所算出來的這六個值,全部加起來平均。然後塞到一個3x3的矩陣內

這個矩陣內的元素對應到哪些值?
六個值要怎麼放?多出來的三個值怎麼填?

另外請問2D的話矩陣要怎麼作?

感謝

2010年2月23日 下午4:03

這個3x3的陣列是這樣,橫向第一列放的是XX, XY, XZ, 第二列放 XY, YY, YZ, 第三列放 XZ, YZ, ZZ,這是個對稱矩陣,所以只需要六個值。
至於2D的狀況,就根本不需要這麼做。只要用最小平方根的方法,就可以找出一條直線,也就是Box的其中一個軸。

2010年2月24日 上午9:22
匿名  

感謝藍斯洛大大的指導

2010年2月24日 上午10:04

这里三轴的计算应该使用PCA方法,即:
1.根据坐标值均值得到中点
2.根据中点坐标得到各点偏差阵X
3.X乘以X转置得到样本协方差矩阵
4.用特征值分析得到三个坐标轴

2011年8月1日 下午12:04

張貼留言