Just a Computer Graphics Studio & My Life

摩頓碼 (Morton Code)

摩頓碼 (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)" (1)

  1. […] UB树的核心在于多维数据的降维方法,也就是Z-order curve,这里我参考了这篇文章和WikiPedia条目,简单来说就是将多维数据的二进制码交叉存储达到降维的目的。 […]

    喜歡

發表留言

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

您的留言將使用 WordPress.com 帳號。 登出 / 變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 / 變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 / 變更 )

Google+ photo

您的留言將使用 Google+ 帳號。 登出 / 變更 )

連結到 %s

標籤雲

%d 位部落客按了讚: