2009年1月23日 星期五

又多了個小外甥

今天才寫,有點晚了。

一月十五日,老妹生了第二胎,是個3240克的健康胖小子。

本來,還想著要他跟姐姐一樣過完年才出來,不過這小子的確跟姐姐一樣,也是大約37週就把媽媽的營養吃完,準備出來。

也好,兩人的生日都是正月十五,姐姐是農曆,弟弟是國曆。

看起來黑黑的,似乎又是個小黑皮。

這個胖小子,也是妹妹的夫家期盼了很久的男丁,上頭已經有三個姐姐了。

昨天老妹家裡在幫小娃娃取名字,剛好在MSN上撞見,我就跟著參考了意見。

「宗」: 不要,太菜市場了。

「宸」: 網路上查了字典,這個字好。辰是龍,屋頂下的龍,表示這個字是帝王的住所,也可以引申為帝王的意思。

「菘」: 看起來不錯,仔細一查,哇咧,原來這個植物就是「白菜」。算了,還是不要這個字吧。

「瑋」、「瑜」、「瑄」: 都不錯,都是「美玉」。不過就是有點像女生的名字,轉念一想,周瑜也用這個名字啊,還好啦。

最後選了「宸瑋」兩個字。很不錯吧,帝王的美玉。

小娃娃才出生一個星期,會不會對他期望太高了? 哈....

老妹照了幾張照片,不過都有點糊,還是小小張的看就好,放大看會更糊。

照片 001

照片 002

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

2009年1月6日 星期二

數學才是王道

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

把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的軸向。