摩頓碼 (Morton Code)用來實做LBVH(可見包圍體階層 (Bounding Volume Hierarchies)),又稱做Z-order Curve,因為它找grid的方式是以Z形追蹤,概念相當簡單,用圖來解釋更清楚。
上圖以Z形(左上→右上→左下→右下)分別代表1*1、2*2、4*4、8*8平方單位。
摩頓碼 (Morton Code)以2D來解釋,將x和y的index轉換成2進位,然後以交叉(yxyxyx…)的方式結合成新的2進位,看下圖較清楚:
藍色數字代表x軸,紅色數字代表y軸,grid裡的2進位為x和y2進位交叉所構成!grid有灰色以Z形表示追蹤路徑,若將grid的2進位數字轉為10進位數字,會是0、1、…、63的數列,如下圖:
暫且不管線段有何意義,是不是覺得很有意思呢!?若要知道線段代表何意,可參考WiKi – Z-order curve。
用在3D也是同樣以Z形追蹤,xyz軸2進位交叉(zyxzyxzyx…),如下圖4*4*4與8*8*8立方單位:
此圖作者相當聰明,3D不好畫圖,便以顏色和透明度來表示先後順序,從紅、橙、…到紫。
參考:WiKi – Bounding volume hierarchy、WiKi – Z-order curve。
Comments on: "摩頓碼 (Morton Code)" (2)
拜讀好文, 特此致謝
讚Liked by 1 person
[…] UB树的核心在于多维数据的降维方法,也就是Z-order curve,这里我参考了这篇文章和WikiPedia条目,简单来说就是将多维数据的二进制码交叉存储达到降维的目的。 […]
讚讚