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長寬高。