Just My Life & My Work

摩頓碼 (Morton Code)

2011 年 12 月 06 日

摩頓碼 (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。

分類：

遊戲設計, 計算機圖學, 課業

2 Comments

Comments on: "摩頓碼 (Morton Code)" (2)

  1. 匿名 said:
    2021 年 09 月 29 日 at 02:38:25

    拜讀好文, 特此致謝

    Liked by 1 person

  2. UB-tree and Z-order curve学习 | Cherrot said:
    2012 年 05 月 16 日 at 21:15:02

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

    讚

隨意留個言吧：）～

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

Gravatar
WordPress.com 標誌

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

Twitter picture

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

Facebook照片

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

取消

連結到 %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

標籤雲

%d 位部落客按了讚：