2009年1月13日 星期二

Finding Oriented Bounding Box

前一陣子發現計算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長寬高。

7 則留言:

xinxin 提到...

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

藍斯洛 提到...

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

xinxin 提到...

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

匿名 提到...

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

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

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

感謝

藍斯洛 提到...

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

匿名 提到...

感謝藍斯洛大大的指導

Losa 提到...

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