• 专利附录
  • 专利说明
  • 权利要求
  • 类似技术
  • 同族专利
  • 引用文献
  • 法律状态
  • 优先权
    • 专利摘要:
    一行星尺度物件繪製系統可提供由一些鄰接面構成而具有不同細節層級的複數個球面網目拓撲。可在連續的細節層級下提供該等面之曲面細分。該網目拓撲中之在不同位置及細節層級下的幾何資料可以是可被隨機存取的。在某些實施例中，可以四分樹組織該等幾何資料。可以自下層向上之方式形成一分層四分樹資料結構，其中係由先前子層構成之根節點形成各連續較高之父層。可以自上而下之方式隨機地存取該四分樹結構。
    公开号:TW201301196A
    申请号:TW100148028
    申请日:2011-12-22
    公开日:2013-01-01
    发明作者:Wei Sun
    申请人:Intel Corp；
    IPC主号:G06T17-00
    专利说明:
    行星尺度之物件繪製
    本發明係大致有關行星尺度物件繪製(planetary scale object rendering)。在本說明書的用法中，行星尺度物件繪製涉及繪製在尺度上至少有100,000倍差異的物件。
    在諸如Google地球(Google Earth)中使用行星物件繪製時，使用者可觀看整個地球，且可看到某一層級的解析度，然後可有效地放大到地球上的一特定區域，且可看到與該較小面積有關的一較大解析度。因此，Google地球可讓使用者選擇要觀看的一些特定區域、以及要觀看那些區域中之多少區域，且系統因而決定該使用者可看到的解析度。
    行星觀看器(planetary viewer)可提供顯現各種科學資料之便利平台，且可提供個人、社會、及大眾傳播媒體之便利平台。行星觀看器亦可被用於導航、生態管理(eco-management)、地理監督及規劃(geographical oversight and planning)、環境科學、緊急事件規劃及回應、以及娛樂。
    即時在高精確度下繪製諸如地球等的一行星尺度物件對三維幾何處理是一大挑戰，這是因為觀看距離及觀看面積有很大的變化，且因為需要即時擷取非常大量的其中包括地表高度(surface elevation)資料之二維資料。例如，行星觀看器可能觀看接近到一公尺的區域，且可能觀看遙遠到幾萬公里的區域，其中觀看面積可能小到一平方公尺且大到整個半球。
    根據本發明的某些實施例，行星物件是地球或另一行星，但是可將本發明應用於任何行星尺度物件(大於100,000倍的尺度)。在一實施例中，行星被近似為一完美的球體。此種方式可簡化取樣及內插，且較易於計算曲面法線(surface normal)。
    在一實施例中，可具有複數個固定或預定離散細節層級球面網目拓撲。例如，在一實施例中，以一些球面網目拓撲實施的八個離散細節層級可自一最粗糙的細節層級延伸到一最精細的細節層級。在一實施例中，該最粗糙的細節層級是每一曲面片(patch)有1667×1667公里，且該最精細的細節層級是13.02×13.02平方公里。在本說明書的用法中，面是一球面網目拓撲上的四邊形區域(除了面是三角形時的極區之外)，而該四邊形區域代表實際幾何物件上的一曲面片。
    請參閱第1圖，用來實施一預定數目的離散細節層級的複數個球面網目拓撲中之三個球面網目拓撲10可被用於一實施例。只示出三個拓撲，用以例示自左至右的漸增細節層級。每一網目拓撲包含被理想化及簡化為平面之複數個面12。因此，每一網目拓撲係由代表特定解析度的複數個平面所構成。每一鄰接平面代表實際球面物件的被稱為曲面片之一具有大致類似的尺寸及形狀的球面(亦即，非平面)部分。
    在某些實施例中，針對網目拓撲及拓撲資料而以一些連續細節層級增補有由該等網目拓撲實施之該等固定或離散細節層級。在某些實施例中，有效率的資料結構可被用於快速網路傳輸、快速硬碟輸入/輸出(Input/Output；簡稱I/O)、以及有效續的記憶體快取。
    請參閱第2圖，在一實施例中，用於行星尺度物件繪製的一幾何處理管線開始時，係如方塊14所示，產生一些階層式網目模型。該等階層式網目模型是第1圖所示之預定數目的離散細節層級。雖然提供了使用八個網目模型的一例子，但是可根據該處理系統的能力而選擇網目模型的數目。
    在某些實施例中，不儲存該等網目拓撲，這是因為該等網目拓撲將具有不適合本地儲存之容量。將耗用兩個32位元浮點值於儲存每一頂點的地理位置(亦即，經度及緯度)，將耗用一個32位元整數作為每一頂點的索引，將耗用一個32位元整數作為每一邊的索引，將耗用一個32位元整數作為每一面的索引，且將耗用額外的索引複製於儲存連接資訊。並不儲存任何該資訊，而是替代地在需要時產生該資訊。
    在一實施例中，針對m個離散細節層級(Level Of Detail；簡稱LOD)而使用m個階層式網目模型(例如，m=8)，其中每一LOD l之取樣為其鄰接較粗糙的LOD l-1之取樣的兩倍。為了不需要儲存這些模型(最精細的LOD大約有5百萬的頂點)，小心地建立這些LOD的頂點、邊、及面之索引，因而可於需要時計算出任何LOD的頂點、邊、及面之位置及連接性。
    一般而言，觀看者愈接近一特定曲面片，該觀看者預期將看到愈多的細節，反之亦然。高度範圍(range of elevation)與該等預定網目LOD中之每一預定網目LOD之間有一相關性，且根據該相關性而選擇最適當的LOD網目拓撲。基本上，使用者離得愈遠，將選擇愈粗糙的網目。係由觀看點的高度h決定對LOD的選擇。每一LOD係與一最小高度臨界值相關聯。選擇一適當的LOD(l ＊)，使。
    執行一曲面細分(tessellation)，以便決定每一曲面片內之樣本點的數目，且以一些較小的三角形對該曲面片執行三角剖分(triangulate)，以便得到一連續的細節層級。在曲面細分之前，先移除該觀看者確定看不到的各曲面片，以便減少計算成本。看不到的曲面片移除包含兩個步驟：背面剔除(back face culling)以及視錐體消除(view frustum culling)。
    第2圖中示出階層式背面剔除16。該背面剔除根據離開觀看者有多遠，而移除球面網目中背向該觀看者的背面上之各面。基本上，觀看者與曲面片愈接近，該觀看者看到愈少的正面。看不到的面被剔除，以便簡化計算。因為每一更詳細的網目拓撲沿著每一經度及緯度方向在每兩個頂點之間增加一個額外的頂點，而使該更詳細的網目拓撲之樣本為其前一網目拓撲之樣本的兩倍，所以在一實施例中，只需要檢查次一較精細的LOD中位於該較粗糙的LOD的邊界上之被加入的頂點之背面剔除。因此，並不對具有二次演算法複雜性O(n2)的被選擇之LOD直接執行背面剔除，而是藉由測試最粗糙的LOD上的所有頂點之可見性，然後遞增地測試每一鄰接之較精細的LOD上的各被加入之邊界頂點，一直測試到該被選擇之LOD為止，而以階層方式執行背面剔除。該階層式背面剔除具有線性演算法複雜性O(n)，因而其在背面剔除之執行速度遠較該二次演算法複雜性快速。
    背面剔除產生了一正面網目，而只有在觀看點改變時才需要更新該正面網目。開關17上的檢查決定觀看點是否改變，因而將決定是否需要執行階層式背面剔除以便更新該正面網目。然後實施視錐體消除，以便產生只包含有可能在視錐體內之面的一最小網目。在視錐體消除18中，決定三維空間中之視錐體。該三維視錐體根據觀看者所選擇的觀看位置、高度、及視角而指示該頂點可看到的部分。不與該視錐體相交的各曲面片可被移除，以便簡化計算。
    背面剔除及視錐體消除要求每一曲面片的最大及最小高度值，以供可見性評估。階層式背面剔除16使用來自提取最大HQT方塊34之最大高度資料。視錐體消除18使用來自方塊32之最小高度以及來自方塊34之最大高度。高度資料的完整檔案可被編碼成最大高度、最小高度、及平均高度資料。在某些實施例中，可自諸如美國航太總署(NASA)的全球數位高度圖(Global Digital Elevation Map；簡稱GDEM)等的公用資源取得該高度資料。
    一旦減少了表面之後，次一步驟是執行實際的曲面細分。該步驟涉及曲面細分度量22的調用，而曲面細分度量22基本上是用來決定每一曲面片需要多少樣本點之體系。如第3圖所示，沿著該被選擇的曲面片之外的邊E且在該曲面片P之內增加樣本。由曲面細分度量22決定這些樣本或樣本點S的數目。然後，一旦選擇了該等樣本之後，該等樣本點即被連接到最終將被傳送到繪製器之各三角形T。
    一旦選擇了一網目拓撲之後，可在該拓撲內之相關的各曲面片中加入更多的細節。每一曲面片是四個頂點及四個邊構成之一個四邊形。在一實施例中，可簡化該模型而使用一平坦的曲面片。
    曲面片曲面細分20將該等樣本加入該等邊及該曲面片之內，且將該等點連接成將被傳送到該繪製器之一些三角形。曲面片評估24使用位移映射(displacement mapping)計算該等樣本點中之每一樣本點的位置及法線向量。
    位移映射是自一粗糙的網目LOD至一精細的詳細網目LOD之調整。在一實施例中，位移映射是自完美球體至真實世界中之實際高度拓撲的調整。因此，如第4圖所示，半徑為R的球體上的每一點P正在沿著該球體的一法線n而被一距離D調整到地球的曲面上之實際位置S。可使用位移映射技術決定該新的曲面位置及法線向量nS。
    因此，回到曲面細分度量22，該曲面細分度量決定曲面片的曲面細分解析度，亦即，曲面片中需要多少的樣本點S才能得到所需的連續細節層級。沿著一曲面片的邊之曲面細分解析度以及該曲面片內部的曲面細分解析度決定該曲面片的曲面細分解析度。
    沿著一曲面片的一邊之曲面細分解析度決定該曲面片的該邊上所需的樣本點之數目。根據一些因素計算一邊應被分成多少個線段，而執行上述的決定。
    第一因素是至所考慮的該邊之觀看距離。點Pc1及Pc2是一曲面片的一邊位移該曲面片的平均高度且被轉換至相機座標系之端點。因為係在相機座標系中決定這些這些端點，所以該等端點對應於自觀看點至該邊之觀看距離。該曲面細分度量將該等觀看距離之平均值決定為該第一因素。
    第二因素是視角。由視角決定螢幕上的邊之大小，因而根據視角，沿著長邊出現的邊可能需要較多的點。將該等端點被正規化，然後被執行點乘積(dot product)，以便提供該視角之餘弦值。當該視角是小視角時，該餘弦值是大的，而且如果該餘弦值是在邊曲面細分方程式T(e)之分母，則樣本的數目將是較少的。
    次一因素是平坦度誤差εflat。如果邊較不平坦，則將需要更多的點才能精確地描繪該邊。該平坦度誤差因素考慮到因使用被選擇的LOD網目近似該球體而產生的誤差、以及由於高度改變的量而產生的誤差。在一實施例中，可將經驗上的一比例因數λ用來結合該等兩個誤差項。
    次一因素考慮到視域(view port)的X及Y方向尺寸(Fx及Fy)。視域愈大，需要愈多的細節。
    被稱為k的次一因素是用來將該曲面細分度量方程式的結果轉換為適當的範圍之一固定比例因數。
    然後，該曲面細分度量T(e)決定每一邊應被分成多少線段： Pc1及Pc2是一邊的兩個端點位移了該曲面片的平均高度且被轉換為相機的座標系之後的三維位置。提供了一邊的平均觀看距離。是自該等兩個被正規化的端點的點乘積計算出之視角。
    以被選擇的LOD球面近似誤差以及以該曲面片的最大高度h max(f)與最小高度h min(f)(在一實施例中，係自GDEM高度資料取得該最大高度h max(f)與最小高度h min(f))間之最大高度差異為界限之拓撲不均勻度之加權和，估計該曲面片的平坦度誤差ε flat (f)(亦即，以一平坦面近似一高階球面曲面片的誤差)，如下式所示：
    於選擇一LOD時，根據該LOD網目的一平坦面與其對應的完美球體曲面片間之最大距離誤差，而預先計算該LOD之球面近似誤差，如下式所示： 其中R是該行星的半徑，且θ l 是沿著該LOD涵蓋的一單一面的經度或緯度方向之角度。
    一旦決定了一曲面片的每一邊的曲面細分解析度T(e)之後，計算該曲面片的所有邊的曲面細分解析度之平均值，即可得到該曲面片的內部(亦即，非邊的)點之曲面細分解析度T(f)：
    可重新調整每一外邊上的曲面細分解析度，使各鄰接曲面片間之邊是一致的，而避免諸如邊緣裂縫(edge cracking)等的視覺假影(visual artifact)。因此，計算兩個鄰接曲面片的共同邊決定之平均值，而得到該共同邊的實際曲面細分解析度T(e)：
    四個或更多個可看到的曲面片可共用各曲面片角上的頂點。共用每一頂點的所有曲面片之平均曲面細分解析度決定該頂點的曲面細分解析度T(v)：
    該頂點曲面細分解析度不被用於曲面細分，但是被用來決定所要使用的拓撲資料之解析度。
    在一實施例中，係以浮點值執行前文中之曲面細分解析度T(f)、T(e)、及T(v)的所有計算。可能以一整數及一分數結束之T(f)、T(e)、或T(v)的最後結果被進位到係為2的乘冪之次一較高整數。
    因此，在一實施例中，如第2圖所示，該曲面細分度量使用最大高度資料、最小高度資料、及平均高度資料。請注意，角點Pc1及Pc2不是該平坦曲面片的原始角點，而實際上是針對高度的被調整後之點(被該曲面片的平均高度調整之點)。因此，需要高度資料，以便進行該調整。
    如果有一具有計算出的曲面細分解析度之曲面片，則一曲面細分器產生具有uv座標及三角形連接性之一些次取樣點(sub-sampling point)。在一實施例中，最大曲面細分解析度是512，等同於九個額外的LOD。
    最後，在曲面片評估期間，以位移映射高度資料計算該等被曲面細分的點之位置及法線向量，且該等位置及法線向量被傳送到繪製引擎。
    在每一新被決定的樣本點上，使用高度資料的位移映射計算該樣本點的三維位置及曲面法線向量。曲面細分曲面片評估24為每一曲面片產生該曲面片的該等樣本點之一列表的三維位置座標、一列表的三維法線向量、以及一列表的用來代表三角形連接性之索引(方塊26)。在一實施例中，然後將該列表的位置、法線向量、及索引傳送到OpenGL後端繪製器28，以供繪製。
    該階層式背面剔除、視錐體消除、曲面細分度量、及曲面片評估都使用高度資料。主從式非同步資料提取系統可即時擷取該資料。
    於階層式背面剔除、視錐體消除、曲面細分度量計算、及曲面片評估期間需要高度資料時，幾何處理管線(第2圖)檢查資料用戶端40之快取記憶體38。如果無法取得所需的資料，則該幾何處理管線送回快取記憶體38中可取得的最佳資料，且恢復處理。同時，資料用戶端40將對該所需資料的查詢經由網路50而傳送到資料伺服器52。
    一旦接收到一查詢之後，伺服器52自硬碟92載入該查詢中指定的對應類型之高度資料54、56、58、或60(第8圖)，且將該資料經由網路50而傳送到用戶端40，同時將該資料的一拷貝儲存在其本身的快取記憶體62。一旦該用戶端自該伺服器接收到該資料之後，該用戶端將該資料儲存在用戶端快取記憶體38，因而該資料以後可供幾何處理使用。
    階層式背面剔除、視錐體消除、及曲面細分度量計算需要基於曲面片的最大、最小、及平均高度值，而曲面片評估需要用於位移映射之詳細高度資料。對該大規模的資料進行即時擷取需要一有效率的壓縮/解壓縮體系。
    可將一階層式無損壓縮演算法於離線時應用於高度資料，以便產生該幾何處理管線的不同部分所需之不同類型的高度資料。該等所產生的資料被儲存在階層式四分樹資料結構。運行時間的階層式無損解壓縮可在任何解析度下迅速地存取任何相關區域中之不同類型的高度資料。該階層式資料結構對該伺服器上的硬碟輸入/輸出、該伺服器與該用戶端間之網路傳輸、以及該伺服器及該用戶端上的記憶體快取可能是有效率的。
    哈爾小波(Haar wavelet)的計算快速，但是無法得到高壓縮比。在一實施例中，哈爾轉換及位元包裝(bit packing)的一組合被用於隨機資料存取及壓縮。有效率的資料結構、檔案格式、以及每一執行緒的快取階層被設計成即使在低壓縮比下也能提供快速且可擴展的資料編碼及擷取解決方案。
    基本二維哈爾轉換涉及四個2×2樣板與原始資料間之卷積(convolution)，而相同的轉換再加上一比例因數可恢復該原始資料。
    其中
    哈爾轉換本質上是一平均及差分運算(differencing operation)。如第7圖所示，使用階層式四分樹配置而以遞迴方式施加時，哈爾轉換專注在資料中之低頻成分，而使哈爾轉換特別適用於輕量的位元包裝壓縮方法。
    哈爾轉換可被直接用來將階層式基於曲面片之平均值編碼。但是很不幸，哈爾轉換無法被用來將階層式基於曲面片之最大值或最小值編碼。在某些實施例中，為了達到此一目的，可使用一最大值及最小值轉換，而延伸了哈爾轉換的結構。可以下文所示之方式對2×2資料網格執行一個二維最大值轉換而得到一個新的資料網格：
    1.找出最大值。
    2.交換與x00間之位置，以便保證在新網格的左上角。例如，如果，則交換x01與x00間之位置，使。
    3.對最大值執行差分運算。
    4.將的原始位置位元串接到X11。例如，如果，則將二進位數"01"串接到X11。
    逆最大值轉換是直接明瞭的：
    1.自X11提取的原始位置二進位數"ij"。
    2.恢復數值。
    3.交換與，而恢復位置。
    該最大值轉換本質上是一最大化及差分運算。當使用第7圖所示之相同階層而以遞迴方式施加時，該最大值轉換專注在資料中之低頻成分，且適用於位元包裝壓縮方法。
    在有統一的階層式架構之相同效益下，稍微修改該最大化及差分運算，即可易於將該最大值轉換修改成最小化轉換。可以下文所示之方式對2×2資料網格執行一個二維最小值轉換而得到一個新的資料網格：
    1.找出最小值。
    2.交換與x00間之位置，以便保證在新網格的左上角。例如，如果，則交換x01與x00間之位置，使。
    3.對最小值執行差分運算。
    4.將的原始位置位元串接到X11。例如，如果，則將二進位數"01"串接到X11。
    逆最小值轉換是直接明瞭的：
    1.自X11提取的原始位置二進位數"ij"。
    2.恢復數值。
    3.交換與，而恢復位置。
    四分樹單元是4層級的哈爾、最大值、或最小值轉換的結果，該轉換將一個16×16二維資料網格之4個LOD編碼。假定每一資料條目有32位元以便涵蓋高度值範圍，且使用壓縮時，則一個四分樹單元的大小不會超過1千位元組。該大小接近網路傳輸的最佳大小，這是因為一網路封包的典型大小是稍微超過1千位元組。
    如第6圖所示，係以自下而上之方式建構四分樹的多層階層。獨立地以遞迴哈爾、最大值、或最小值轉換將下層上的所有四分樹編碼。將每一16×16四分樹聚集在一起，且將該等四分樹的根節點值用來作為輸入，而將該等四分樹的父層四分樹編碼。請注意，子層四分樹的該等根節點值係在其父層四分樹中被複製，且此種方式提供了兩種效益。第一，於擷取單一資料點時，不需要將一個以上的四分樹解碼。第二，不需要儲存具有相同資料的四分樹，這是因為可自該四分樹的父層四分樹擷取該等值。每一個四分樹包含用來指示該父層四分樹的每一子層四分樹是否存在以及若該子層四分樹存在則該父層四分樹的資料被儲存在硬碟何處之資訊。此種方式避免不必要的資料提取，且將運行時間的硬碟搜尋最少化，而解加速了硬碟的輸入/輸出。
    可將該多層四分樹階層擴展到任何數目的LOD。如第5圖所示，為了將基於曲面片的平均值、最大值、及最小值編碼，將該四分樹階層的網格對準該等離散LOD網目模型。在一實施例中，兩層的四分樹涵蓋了8個離散LOD的基於曲面片之平均值、最大值、及最小值資料。可增加層的數目，以便匹配任何特定數目的離散LOD。
    為了將用於位移映射的詳細拓撲資料編碼，四分樹階層自對應於兩個半球的頂層上之兩個四分樹開始，且大量產生子四分樹，直到涵蓋了原始資料的最高解析度為止。在一實施例中，使用等同於20個LOD之5層的四分樹，以便涵蓋來自NASA的ASTER全球數位高度圖(GDEM)資料，該GDEM資料具有空間位置的30米解析度以及高度的1米解析度。請注意，在一實施例中，該四分樹階層的網格並未對準離散LOD網目模型。此種方式被設計成利用該四分樹階層對異質解析度的資料之固有可擴縮性，這是因為可易於以在不同解析度下而具有不同資料之四分樹取代任何子集的四分樹。此種方式是特別適用的，這是因為諸如地球等的一行星之拓撲資料通常在不同的區域中呈現不同的解析度。
    一旦建構了該四分樹階層之後，叢集自共同父層四分樹衍生的每個3層(或在基於曲面片的數值編碼中為最大數目的層)之四分樹。自該叢集中之所有四分樹收集統計資料，以便計算一位元長度表，該位元長度表記錄了該叢集中之所有四分樹的每一16×16資料條目所需的最大數目之位元。然後根據所產生的該位元長度表而以位元包裝法壓縮該叢集中之所有的四分樹，且將該等被壓縮的四分樹儲存在一檔案中。該位元長度表被儲存在該叢集的根四分樹，以供用於資料擷取期間的解壓縮。
    第5圖示出該四分樹階層之離線建構管線。原始GDEM檔案被傳送到哈爾轉換70a。該等原始GDEM檔案也被傳送到一最小值轉換70b及一最大值轉換70c。然後，在每一種情形中，在方塊72中執行位元包裝，以便產生適當的檔案76。為了將基於曲面片的平均值、最小值、及最大值編碼，將自該等原始GDEM檔案載入的資料配置成對準該等離散細節層級網目模型，以便產生與該等離散細節層級對準的四分樹階層。為了將詳細拓撲資料編碼，自該等原始GDEM檔案載入的資料可對準或可不對準該等離散細節層級網目模型。
    該3層的選擇被以經驗方式決定為將位元包裝壓縮比最大化與將位元長度表的儲存最小化間之一折衷。改善壓縮比且不會顯著地增加位元長度表的儲存容量之一種較佳方式將是整個四分樹階層執行一適應性叢集，以便提取用於位元包裝的最有代表性之位元長度型樣。
    為了保證行星繪製的即時效能，第8圖示出被用於運行時間的非同步資料提取之一主從式分割系統及其管線。
    當用用戶端40被啟動時，一初始提取(第2圖中之方塊13)將查詢傳送到伺服器52，以便載入被以前文所述之方式編碼的最大值、最小值、平均值、及資料四分樹階層之頂層。
    在伺服器52端，一組伺服器快取記憶體管理執行緒93監聽來自用戶端的查詢88。當接收到一查詢時，一伺服器快取記憶體管理執行緒先在菱形80中檢查伺服器快取記憶體62。如果該被要求的四分樹已經存在於該快取記憶體，則在方塊86中將該四分樹連同其對應的位元長度表組合成一網路資料封包90，且將該資料封包90經由網路50而傳送到用戶端40。否則，該伺服器快取記憶體管理執行緒根據可自其快取記憶體中之父層四分樹可取得的資訊而找出該四分樹，且自硬碟92載入該四分樹(方塊82)。然後在方塊86中組合該四分樹，且將該四分樹傳送到用戶端40。在方塊84中，將該被編碼的四分樹之一拷貝儲存在伺服器快取記憶體62，以供下次查詢相同的資料時之快速擷取。
    在繪製用戶端40的處理器上，有兩組執行緒，亦即，幾何處理執行緒94及用戶端快取記憶體管理執行緒151。當自該伺服器接收一資料封包90時，一全域快取記憶體管理執行緒自該封包提取該被編碼的四分樹，且在方塊150中根據伴隨該四分樹的位元長度表而拆卸該四分樹的資料位元。然後在方塊152中，將該被拆卸的四分樹儲存在一全域快取記憶體38b。
    在幾何處理期間需要高度資料(不論是基於曲面片的最大值、最小值、平均值、或詳細資料值)時，幾何處理執行緒94決定該資料的地理位置(亦即，經度及緯度)及解析度154，且自其本地快取記憶體38a提取對應的原始資料四分樹。如果可取得該等原始資料四分樹，則執行三線性內插156，以便計算幾何處理所需的實際值。如果在菱形158中之檢查決定被要求的四分樹不在該本地快取記憶體，則該幾何處理執行緒在菱形160中檢查全域快取記憶體38b。如果可取得該四分樹，則在方塊162中將逆哈爾、最大值、或最小值轉換施加到來自該全域快取記憶體之被拆卸的四分樹，且在方塊164諸中將該四分樹原始資料的4個LOD儲存在該執行緒的本地快取記憶體38a。如果該被要求的四分樹不在該全域快取記憶體，則將一查詢166傳送到伺服器52。同時，在方塊168中擷取該全域快取記憶體中具有最高解析度之可取得的最佳四分樹，在方塊162中對該四分樹執行逆轉換，且在方塊164中將該被逆轉換的四分樹複製到該執行緒的本地快取記憶體38a，且對所產生的該原始資料繼續執行進一步的幾何處理。
    保持在該伺服器上將資料編碼且以一種分散方式在用戶端的不同階段上解碼之理由是儘量保持最小的儲存容量且將運行時間的計算成本最小化。當該用戶端上的該全域快取記憶體被多個執行緒共用時，鎖定是必要的，以避免競爭的狀況，這就是一基於執行緒的本地快取記憶體被用來減輕鎖定競爭問題之原因。連同資料分幅(data tiling)，基於執行緒的本地快取記憶體層將減少存取次數的額外效益提供給系統記憶體，且改善了中央處理單元(CPU)上的硬體快取記憶體效率。為了利用第6圖所示之四分樹階層，當一個四分樹被要求且被儲存在快取記憶體時，該四分樹的所有父層四分樹也都被擷取且被儲存在快取記憶體。此種方式加速了對鄰近四分樹的檔案資訊、存在資訊、及位元長度表之擷取，這是因為有需要鄰近區域中之資料的很大改變。
    可以一些伺服器機器構成的一雲端取代該伺服器，其中係以一種隨機分佈之方式將被編碼的高度資料儲存在該等伺服器機器中之每一伺服器機器，以便加速資料擷取期間的網路回應。可根據來自滑鼠及鍵盤輸入的使用者互動，而將一預先提取機制加入該系統，以便進一步改善資料擷取速度。可將前文所述之該等壓縮及解壓縮演算法以及資料結構應用於諸如地形紋理(terrain texture)資料等的任何大型二維資料集，以供即時擷取。
    在某些實施例中，係在一CPU中執行前文所述之幾何處理。在一實施例中，可使用傳統的技術而在一圖形處理單元(Graphics Processing Unit；簡稱GPU)中執行光影(lighting)及陰影(shading)。
    第9圖所示之電腦系統130可包含被一匯流排104耦合到一晶片組核心邏輯110之一硬碟機134及一抽取式媒體136。一鍵盤及滑鼠120或其他傳統的組件可經由匯流排108而被耦合到該晶片組核心邏輯。在一實施例中，該核心邏輯可經由一匯流排105而被耦合到一圖形處理器112，且可被耦合到一主或主機處理器100。在某些實施例中，該主機處理器可具有多緒執行(multi-threading)、單一指令多重資料(Single Instruction Multiple Data；簡稱SIMD)、以及雙精確度、較寬的進階向量擴充指令集(Advanced Vector Extension；簡稱AVX)能力。在一實施例中，該主機處理器執行本發明述及的幾何處理。在另一實施例中，圖形處理器亦可與該主機處理器伺服器整合。圖形處理器112亦可被一匯流排106耦合到一圖框緩衝器114。圖框緩衝器114可被一匯流排107耦合到一顯示螢幕118。在一實施例中，圖形處理器112可以是使用單一指令多重資料(Single Instruction Multiple Data；簡稱SIMD)架構之一多執行緒及多核心的平行處理器。在一實施例中，該圖形處理器可被用於陰影及光影。
    在一軟體實施之情形中，可將相關的程式碼139儲存在任何適當的半導體、磁性、或光學記憶體，其中包括主記憶體132或該圖形處理器內之任何可用的記憶體。因此，在一實施例中，可將被用來執行第2及8圖所示序列之碼儲存在諸如記憶體132或圖形處理器112等的一非暫時性機器或電腦可讀取的媒體，且在一實施例中，可由處理器100或圖形處理器112執行該程式碼。
    第2及8圖是流程圖。在某些實施例中，可以硬體、軟體、或韌體實施這些流程圖所示之該等序列。在一軟體實施例中，可將諸如一半導體記憶體、一磁性記憶體、或一光學記憶體等的一非短暫性電腦可讀取的媒體用來儲存指令，且該等指令可被一處理器執行，而執行第2及8圖所示之該等序列。
    可以各種硬體架構實施本發明述及的該等圖形處理技術。例如，可將圖形功能整合在一晶片組內。或者，可使用一分立式圖形處理器。作為又一實施例，可以其中包括多核心處理器之一般用途處理器實施該等圖形功能。
    在本說明書中提及"一個實施例"或"一實施例"時，意指參照該實施例而述及的一特定特徵、結構、或特性被包含在本發明所包含的至少一實施例中。因此，出現詞語"一實施例"或"在一實施例中"時，不必然都參照到相同的實施例。此外，可以所示特定實施例以外的其他適當形式實施該等特定特徵、結構、或特性，且所有此類形式可被包含在本申請案的申請專利範圍內。
    雖然已以與有限數目的實施例有關之方式說明了本發明，但是熟悉此項技術者將可了解本發明的許多修改及變化。後附的申請專利範圍將涵蓋在本發明的真實精神及範圍內之所有此類修改及變化。
    10‧‧‧球面網目拓撲
    12‧‧‧面
    16‧‧‧階層式背面剔除
    17‧‧‧開關
    18‧‧‧視錐體消除
    34‧‧‧提取最大HQT區塊
    32‧‧‧提取最小HQT區塊
    22‧‧‧鑲嵌度量
    20‧‧‧曲面片曲面細分
    24‧‧‧曲面片評估
    28‧‧‧OpenGL後端繪製器
    38,62‧‧‧快取記憶體
    40‧‧‧用戶端
    50‧‧‧網路
    52‧‧‧伺服器
    92‧‧‧硬碟
    54,56,58,60‧‧‧高度資料
    70a‧‧‧哈爾轉換
    70b‧‧‧最小值轉換
    70c‧‧‧最大值轉換
    76‧‧‧檔案
    13‧‧‧初始提取
    93‧‧‧伺服器快取記憶體管理執行緒
    88,166‧‧‧查詢
    90‧‧‧資料封包
    94‧‧‧幾何處理執行緒
    151‧‧‧用戶端快取記憶體管理執行緒
    38b‧‧‧全域快取記憶體
    154‧‧‧地理位置及解析度
    38a‧‧‧本地快取記憶體
    156‧‧‧三線性內插
    130‧‧‧電腦系統
    104,105,106,107,108‧‧‧匯流排
    110‧‧‧晶片組核心邏輯
    134‧‧‧硬碟機
    136‧‧‧抽取式媒體
    120‧‧‧鍵盤及滑鼠
    112‧‧‧圖形處理器
    100‧‧‧主處理器
    114‧‧‧圖框緩衝器
    118‧‧‧顯示螢幕
    132‧‧‧主記憶體
    139‧‧‧程式碼
    第1圖是一實施例中之複數個網目拓撲中之三個網目拓撲之一透視圖；第2圖是根據一實施例的一幾何處理管線之一流程圖；第3圖示出根據一實施例之曲面片曲面細分(patch tessellation)；第4圖是根據一實施例的位移映射之圖形；第5圖是根據一實施例的離線處理之一流程圖；第6圖是一實施例中之一四分樹階層之一配置；第7圖示出一實施例中之一階層式四分樹；第8圖是根據一實施例的拓撲資料的運行時間擷取之一流程圖；以及第9圖是一實施例中之硬體圖形。
    10‧‧‧球面網目拓撲
    12‧‧‧面
    权利要求:
    Claims (30)
    [1] 一種方法，包含：提供具有不同細節層級的複數個可被選擇之網目拓撲，每一網目拓撲係被一些鄰接面所構成；以及對一被選擇的網目拓撲之該等面啟用連續層級的曲面細分(tessellation)。
    [2] 如申請專利範圍第1項之方法，包含對一網目拓撲中之不同位置及細節層級的幾何資料啟用隨機存取。
    [3] 如申請專利範圍第2項之方法，包含組織各四分樹中之幾何資料，其中每一四分樹包含少於1千位元組的資料。
    [4] 如申請專利範圍第3項之方法，包含以自底層向上之方式自該等四分樹建構一分層四分樹資料結構，每一連續較高之父層由先前子層構成之根節點形成。
    [5] 如申請專利範圍第4項之方法，包含以自上而下之方式存取該結構。
    [6] 如申請專利範圍第5項之方法，包含將與該等四分樹的子層四分樹有關之資訊放置到該等四分樹中。
    [7] 如申請專利範圍第1項之方法，包含結合觀看距離、視角、平坦度誤差、及視域尺寸，而計算曲面細分解析度。
    [8] 如申請專利範圍第7項之方法，包含使用球面近似誤差及拓撲不均勻度誤差計算平坦度誤差。
    [9] 如申請專利範圍第1項之方法，包含使用適應性叢集提取代表性的位元長度表以供位元包裝壓縮。
    [10] 如申請專利範圍第9項之方法，包含將階層式哈爾轉換應用於階層式最大值及最小值轉換，且因而將一統一的四分樹階層式資料結構用於資料壓縮/解壓縮。
    [11] 一種儲存指令之非暫時性電腦可讀取的媒體，該等指令使一處理器能夠執行：選擇不同細節層級下的複數個網目拓撲中之一網目拓撲；以及隨機地存取一網目拓撲中在不同位置及細節層級下的幾何資料。
    [12] 如申請專利範圍第11項之媒體，進一步儲存了指令以執行提供具有不同細節層級的複數個可被選擇之網目拓撲，每一網目拓撲係被一些鄰接面所構成，且對一被選擇的網目拓撲之該等面啟用連續層級的曲面細分。
    [13] 如申請專利範圍第12項之媒體，進一步儲存了指令以執行組織各四分樹中之幾何資料，其中每一四分樹包含少於1千位元組的資料。
    [14] 如申請專利範圍第13項之媒體，進一步儲存了指令以自底層向上之方式自該等四分樹建構一分層四分樹資料結構，每一連續較高之父層由先前子層構成之根節點形成。
    [15] 如申請專利範圍第14項之媒體，進一步儲存了指令以自上而下之方式存取該結構。
    [16] 如申請專利範圍第15項之媒體，進一步儲存了指令以將與該等四分樹的子層四分樹有關之資訊放置到該等四分樹中。
    [17] 如申請專利範圍第11項之媒體，進一步儲存了指令以結合觀看距離、視角、平坦度誤差、及視域尺寸，而計算曲面細分解析度。
    [18] 如申請專利範圍第17項之媒體，進一步儲存了指令以使用球面近似誤差及拓撲不均勻度誤差計算平坦度誤差。
    [19] 如申請專利範圍第11項之媒體，進一步儲存了指令以使用適應性叢集提取代表性的位元長度表以供位元包裝壓縮。
    [20] 如申請專利範圍第19項之媒體，進一步儲存了指令以將階層式哈爾轉換應用於階層式最大值及最小值轉換，且因而將一統一的四分樹階層式資料結構用於資料壓縮/解壓縮。
    [21] 一種裝置，包含：一處理器，用以自四分樹的底層向上之方式建構一分層四分樹資料結構，每一連續較高之父層由先前子層構成之根節點形成；以及被耦合到該處理器之一儲存器。
    [22] 如申請專利範圍第21項之裝置，其中該處理器提供具有不同細節層級的複數個可被選擇之網目拓撲，每一網目拓撲係被一些鄰接面所構成，且對一被選擇的網目拓撲之該等面啟用連續層級的曲面細分。
    [23] 如申請專利範圍第22項之裝置，其中該處理器對一網目拓撲中之不同位置及細節層級下的幾何資料啟用隨機存取。
    [24] 如申請專利範圍第23項之裝置，其中該處理器組織包含少於1千位元組的資料的各四分樹中之幾何資料。
    [25] 如申請專利範圍第21項之裝置，其中該處理器以自上而下之方式存取該結構。
    [26] 如申請專利範圍第25項之裝置，其中該處理器將與該等四分樹的子層四分樹有關之資訊載入該等四分樹中。
    [27] 如申請專利範圍第22項之裝置，其中該處理器結合觀看距離、視角、平坦度誤差、及視域尺寸，而計算曲面細分解析度。
    [28] 如申請專利範圍第27項之裝置，其中該處理器使用球面近似誤差及拓撲不均勻度誤差計算平坦度誤差。
    [29] 如申請專利範圍第22項之裝置，其中該處理器使用適應性叢集提取代表性的位元長度表以供位元包裝壓縮。
    [30] 如申請專利範圍第29項之裝置，其中該處理器將階層式哈爾轉換應用於階層式最大值及最小值轉換，且因而將一統一的四分樹階層式資料結構用於資料壓縮/解壓縮。
    类似技术:
    公开号 | 公开日 | 专利标题
    TWI502547B|2015-10-01|行星尺度之物件繪製之方法及裝置
    Cignoni et al.2003|BDAM—Batched Dynamic Adaptive Meshes for high performance terrain visualization
    US7940279B2|2011-05-10|System and method for rendering of texel imagery
    Gobbetti et al.2004|Layered point clouds: a simple and efficient multiresolution structure for distributing and rendering gigantic point-sampled models
    Richter et al.2015|Out-of-core visualization of classified 3d point clouds
    US20040217956A1|2004-11-04|Method and system for processing, compressing, streaming, and interactive rendering of 3D color image data
    US20030038798A1|2003-02-27|Method and system for processing, compressing, streaming, and interactive rendering of 3D color image data
    Mahdavi-Amiri et al.2015|Hexagonal connectivity maps for Digital Earth
    CN102509022B|2015-02-18|一种面向虚拟地球的栅格数据快速建库方法
    Lindow et al.2012|Interactive rendering of materials and biological structures on atomic and nanoscopic scale
    Kalaiah et al.2005|Statistical geometry representation for efficient transmission and rendering
    Kopf et al.2020|One shot 3d photography
    Rodriguez et al.2013|Compression-domain seamless multiresolution visualization of gigantic triangle meshes on mobile devices
    Xie et al.2013|Interactive ray casting of geodesic grids
    Liu et al.2015|Graphics processing unit-based dynamic volume rendering for typhoons on a virtual globe
    US10192353B1|2019-01-29|Multiresolution surface representation and compression
    Đurđević et al.2013|HFPaC: GPU friendly height field parallel compression
    Zhang et al.2011|Transmission and visualization of large geographical maps
    Gao et al.2005|A parallel multiresolution volume rendering algorithm for large data visualization
    Jubair et al.2016|Icosahedral Maps for a Multiresolution Representation of Earth Data.
    Zhang et al.2009|Web-based visualization of spatial objects in 3DGIS
    Zhang et al.2005|Effective solutions to a global 3D visual system in networking environments
    Ponchio et al.2008|Interactive rendering of dynamic geometry
    Platings et al.2004|Compression of Large‐Scale Terrain Data for Real‐Time Visualization Using a Tiled Quad Tree
    Cui et al.2013|Animated depth images for interactive remote visualization of time-varying data sets
    同族专利:
    公开号 | 公开日
    US9165403B2|2015-10-20|
    WO2012096790A2|2012-07-19|
    TWI502547B|2015-10-01|
    CN103403769B|2016-06-15|
    WO2012096790A3|2012-10-11|
    CN103403769A|2013-11-20|
    US20120182298A1|2012-07-19|
    引用文献:
    公开号 | 申请日 | 公开日 | 申请人 | 专利标题
    US5602550A|1995-06-19|1997-02-11|Bio-Logic Systems Corp.|Apparatus and method for lossless waveform data compression|
    JPH11191153A|1997-12-26|1999-07-13|Ricoh Co Ltd|ウェーブレット変換係数の符号化方法|
    US6879324B1|1998-07-14|2005-04-12|Microsoft Corporation|Regional progressive meshes|
    US6373489B1|1999-01-12|2002-04-16|Schlumberger Technology Corporation|Scalable visualization for interactive geometry modeling|
    US7139794B2|2000-12-27|2006-11-21|3-D-V-U Israel Ltd.|System and methods for network image delivery with dynamic viewing frustum optimized for limited bandwidth communication channels|
    US7102636B2|2001-03-31|2006-09-05|Intel Corporation|Spatial patches for graphics rendering|
    US7225207B1|2001-10-10|2007-05-29|Google Inc.|Server for geospatially organized flat file data|
    US7215340B2|2002-07-19|2007-05-08|Mitsubishi Electric Research Laboratories, Inc.|Object space EWA splatting of point-based 3D models|
    US7129942B2|2002-12-10|2006-10-31|International Business Machines Corporation|System and method for performing domain decomposition for multiresolution surface analysis|
    CN1273940C|2004-04-12|2006-09-06|浙江大学|一种分级层次化组装式深度拼图集的快速绘制森林方法|
    US7680350B2|2004-05-07|2010-03-16|TerraMetrics, Inc.|Method and system for progressive mesh storage and reconstruction using wavelet-encoded height fields|
    US7536664B2|2004-08-12|2009-05-19|International Business Machines Corporation|Physical design system and method|
    US8884956B2|2006-08-11|2014-11-11|Siemens Product Lifecycle Management Software Inc.|System and method for trimmed surface tessellation|
    US20090157503A1|2007-12-18|2009-06-18|Microsoft Corporation|Pyramidal volumes of advertising space|
    KR101520649B1|2008-01-21|2015-05-15|삼성전자 주식회사|3차원 메쉬 모델에서의 임의 접근 가능한 메쉬 데이터의압축 및 복원 방법 및 시스템|
    US8810590B2|2008-07-11|2014-08-19|Advanced Micro Devices, Inc.|Method and apparatus for spatial binning on a GPU and global path planning to avoid spatially binned objects|
    US8482560B2|2008-12-31|2013-07-09|Intel Corporation|Image forming techniques|
    TWI419514B|2009-02-03|2013-12-11|Inst Information Industry|用於一感測網路之節點裝置、節點數量調整方法及其電腦程式產品|
    TW201042952A|2009-05-20|2010-12-01|Axiomtek Co Ltd|Network device testing system and method thereof|
    US20110310102A1|2010-06-17|2011-12-22|Via Technologies, Inc.|Systems and methods for subdividing and storing vertex data|
    US8463586B2|2010-06-22|2013-06-11|Saudi Arabian Oil Company|Machine, program product, and computer-implemented method to simulate reservoirs as 2.5D unstructured grids|
    US8665266B2|2010-06-23|2014-03-04|The United States Of America, As Represented By The Secretary Of The Navy|Global visualization process terrain database builder|US20070023987A1|2005-05-23|2007-02-01|Kling Daniel H|Folding methods, structures and apparatuses|
    US9098941B2|2012-01-23|2015-08-04|Ayasdi, Inc.|Systems and methods for graphical layout|
    US8830254B2|2012-01-24|2014-09-09|Ayasdi, Inc.|Systems and methods for graph rendering|
    CN103544727B|2013-06-26|2017-02-15|Tcl集团股份有限公司|一种基于预测分支的场景渲染优化方法、系统和移动终端|
    KR102104057B1|2013-07-09|2020-04-23|삼성전자 주식회사|점별로 테셀레이션 팩터를 할당하는 방법과 상기 방법을 수행할 수 있는 장치들|
    KR102053351B1|2013-08-12|2019-12-06|삼성전자주식회사|테셀레이션 데이터 생성 방법과 상기 방법을 수행할 수 있는 장치들|
    KR101555426B1|2014-02-07|2015-09-25|고려대학교 산학협력단|지형 렌더링 방법 및 장치|
    CN103903295B|2014-04-04|2017-01-11|四川川大智胜软件股份有限公司|一种基于InfiniBand实时调度海量高精度三维场景数据的方法|
    GB2526359B|2014-05-23|2020-07-22|Advanced Risc Mach Ltd|Graphics processing systems|
    KR102313020B1|2014-11-27|2021-10-15|삼성전자주식회사|그래픽스 프로세싱 유닛과 이를 포함하는 장치|
    US9978176B2|2015-06-26|2018-05-22|Electronic Arts Inc.|Simplifying small mesh components with redundant backs|
    ITUB20152024A1|2015-07-08|2017-01-08|Nivi Group Spa|Motore grafico per la creazione ed esecuzione di applicazioni con interfacce multisensoriali|
    US10706612B2|2017-04-01|2020-07-07|Intel Corporation|Tile-based immediate mode rendering with early hierarchical-z|
    US10373365B2|2017-04-10|2019-08-06|Intel Corporation|Topology shader technology|
    KR102272569B1|2020-05-26|2021-07-05|한국과학기술원|웨이블릿 기반 변형된 거대 메쉬 데이터의 점진적 고속 재압축 방법 및 그 시스템|
    法律状态:
    优先权:
    申请号 | 申请日 | 专利标题
    US13/007,161|US9165403B2|2011-01-14|2011-01-14|Planetary scale object rendering|
    [返回顶部]