TW201234314A - Micropolygon splatting - Google Patents

Description

201234314 六、發明說明： 【發明所屬技術領】 發明領域 本發明基本上係有關圖形處理技術，並更特別係有關 顯現微多邊形之技術。 發明背景 本發明基本上係有關圖形處理技術，並更特別係有關 顯現微多邊形之技術。 係可將一個幾何基元劃分成更小的基元數次’直到其 螢幕空間大小夠小為止，並在各個階段發生平截頭體淘汰 (frustum culling)。此外，在一個螢幕的各個地磚内，係可 完成14些基元之從前到後的整理，並且係可相對於一個階 層深度緩衝@對各個基元作包藏淘汰(Qedusi()n eulled)。劃 分迴圈會-直被執行’直到輸人基元已經被切分成許多小 部份’並且各個部份的絲空間延伸係小於受使用者控制 的臨界值為止。 接下來會發生切塊動作，其中，各個子基元會被一致 地鑲嵌到被稱為微多邊形的為子像素大小之四邊形或三角 形的個網格巾。各個微多邊形會被做視野平截頭體和背 面淘汰。-個微多邊形是小於像素的一個顯現基元。其可， 例如，為一個四角形或三角形。 可能會發生移位映對行為，當中，係對網格中的每個 頂點執行移位遮掩器（shader)。 201234314 【發明内容：！ 發明概要 依據本發明之一實施例，係特地提出一種方法，其包含 下列步驟：藉由將一個網目細分直到多邊形邊緣短於一個 預定長度為止，因而產生數個微多邊形，來適應性地鑲嵌； 以及藉由鋪接而顯現該等微多邊形。 依據本發明之另一實施例，係特地提出一種儲存有指令 的非暫時性電腦可讀媒體，該等指令會使一個電腦能夠進 行下列步驟：藉由將一個網目細分直到多邊形邊緣短於一 個預定長度為止，因而產生數個微多邊形，來適應性地鑲 嵌；以及藉由鋪接而顯現該等微多邊形。 依據本發明之又一實施例，係特地提出一種設備，其包 含：一個處理器，用以藉由藉著將一個網目細分直到多邊 形邊緣短於一個預定長度為止作適應性鑲嵌，而產生數個 微多邊形，並用以藉由鋪接而顯現該等微多邊形；以及耦 接至該處理器的一個儲存體。 圖式簡單說明 第1圖是本發明的一個實施例之流程圖； 第2圖是對一個三角形的描繪，它的一個頂點和形心都 在同一個像素内。此例示展示出一個限制事例的幾何組 態，當中形心和一個頂點都在此像素内； 第3圖是依據一個實施例的對局部平面表面近似之描 繪，用於終止針對一個給定像素的最靠近鋪塊（splat); 第4圖是依據一個實施例的對局部曲率表面近似之描 201234314 繪’用於終止針對一個給定像素的最靠近鋪塊； 第5圖是對本發明的一個實施例之概略描繪；並且 第6圖是對〜個三角形扇的描繪，其具有位於像素中心 的一個共享頂點。

C 較佳實施例之詳細說明 依據一些實施例，具高精細度的幾何，例如對頭髮的 描繪’係可藉由鑲嵌直到三㈣小^能夠使用像素大小的 鋪塊為止來顯H些實施财，係可避免定界框運算、 二角形設立、和栅格化。 在電腦圖形中，較高階的基元常常會被鎮嵌到較小的 顯示基Μ ’典型上是三㈣。對於複雜幾何物件的一種 替代表示型態是高度密集點雲，其為，例如，31)掃描器的 本地輸出。鋪接（splatting)是—種用來從點雲基元近似地 顯現—個表面的技術，其中’在顯現時，各個分立的點係 精由-個局部表面核心而被延伸。與同一個像素重疊的數 =核心會在訊框緩衝器中被—起作平均，以使得可將此點 Γ顯現為像是·'個表面模型。在設計核心上係有特別留 思’以使得在賴現喊面上沒有任何孔洞。 我們的铺接方法係使用-種簡化的核心，其並不對重 疊的樣本作平均，而是簡單地窝 被判定是可讓子像素看見的話。若㈣塊 取代於倚賴進階的過濾器 核心，我們的技術係類似於黎曼積分 其中每個子像素都有—個常數 201234314 較高品質，係使用較多的子像素。 嵌器會2實施例中’係實施適應性鎮嵌和鋪接。一個鑲 於-個=形中，直到各個薇三角形都小 ^牛為止。廷些微三角形接著被饋入到一個鋪 ’此鋪接器會將他們鋪接到-個訊框緩衝器中。若 或’、他微多邊形頂點的形d被投影到螢幕上 和:會ϋί素或子像素中，則此像素或子像素的顏色 ®此’此微多邊形的形心必須被運算。 接，:了，於微多邊形形心將表面向下鑲嵌到能夠保證舖 在-的大小m崎緣長度條件。 ,ν 邊緣長度小於-個像素側邊長度的四 二二：=個!Γ中心的一個三角形之形心將會 ά。ί此表面本身衫含有任何裂縫， 任何料=為㈣的鋪接途徑將因而覆蓋此表面且沒有 命。 〜種類型的鑲嵌是-個適應性鑲嵌器的使 四刀之二像素邊緣長度是從識出此事導出，即 i形1=緣需要被鎮嵌至的最長的邊緣長度係在當—個三 個“ /表示’逼近零時獲得。因此，另外兩 -形邊緣會具有相同的長度丨 :乎僅與此像素之+心作幾乎沒有_。請參=;會 在這個事例中，+ p可弟j圖， 在y座標上的形心是(0叫+1)/3。若此點會是 201234314 在此像素内，則下式必需為真：（〇+1+1)/3=ι/2 ,這表示1必 須等於此像素側邊長度的四分之三。所以，如果此表面被 適應性地鑲嵌而使得各個微三角形邊緣等於〇 7 5個像素， 那麼以形d基礎的難途徑就會覆蓋此表面而沒有任何 裂縫。 若此像素被一個經鑲嵌表面完全覆蓋，則在一些實施 例中可緩和導算。為了導出緩和鑲嵌邊界，射使用具有 位在像素之中心之共享頂點的一個三角形扇之範例。若此 經鑲嵌表面具水密性，則這些三角形中的至少一個之形心 必須是在此像素内。假設一個經鑲嵌表面的一個領域頂點 係位在此像素的中心。我們搜尋與此頂點連接的具有位在 此像素之區域内之形心的一個三角形之最大側邊長度。若 兩個關聯邊緣之長度為長度條件所容許，則任何一個所連 接二角形的從此頂點到形心的最大距離都會被獲得。此長 度係以L表示。假設有八個長度L的邊緣連接到中心頂點， 其中有一個向下指，並且各個邊緣之間夾45度，如於第6圖 中所示。從像素中心到各個這八個三角形之形心的謝比雪 夫（Chebyshev)距離為L(1 + 1/V2)/3。若謝比雪夫距離小於 像素之側邊長度的一半，那麼形心便是在此像素内。因此， 長度條件必須為L< 一個像素之側邊長度的3/(2+V2)，以使 此像素能夠包括一個形心。從此構型擾亂任何頂點都會降 低最小謝比雪夫距離；因此上面所導出的長度條件是一個 最大值。我們推測，這是通用最大值。 對於具有多於三個頂點的多邊形而言，最大謝比雪夫 201234314 距離也是以類似構型獲得，但其中各個三角形是以多的邊 緣沿著中心至三角形形心向量之主轴而延伸。例如，對於 四邊形而言’最大邊緣長度是l<；2/(2+V2)，且對於五邊形 而言’最大邊緣長度是5/(8+2V2)。 配合適應性鑲嵌，只能在參數表面為連續而使得當參 數域減少時此表面部份在螢幕上的投影也減少的時候保證 對一個邊緣長度條件之滿足。係可在鑲嵌期間識別出這不 為真的事例’並且可藉由透過内插法插入額外鋪塊來處置。 在一些實施例中’係可全然避免柵格化，取而代之地 寫出覆蓋單-個向量的鋪塊。所以，三角形建立變得更為 谷易’並且可全然免除對於小三角形的相對昂貴且無效率 的栅格化。 -貫&例中’不能滿足邊緣長度條件的表面會被 栅格化而不被鋪接。栅格化所需的完全三肖形建立僅針對 被栅格化的表面進行。 因此，請參考第1圖，由方塊10所指 出的此序列的第一 步驟係要遞迴地細分網目直到—個微三角形的三個經投 i移位之長度在長度上都小於0.75個像素 。此長度臨 亦為個像素之側邊長度的3/(2+V2)，或是-些其他 二導出的長度。那麼’如於方塊12中所指出的，可運 舁出這些頂點的顏色。 _ 接下來’請參考方塊16，可從三角 形的三個頂點顏色 ^ 此二角形之形心處的顏色和深度。 .t T可進仃對此像素鋪塊的z測試，如於方塊18中 所指出的。在一此實 —耳苑例中’顏色和深度可被寫至最靠近 201234314 形心的像素，如於方塊20所指出的。 在—些實施例中，於上文中所描述的這個序列係可實 施在軟體、硬體餘體中’例如形驅動器。在軟體 實施例中，其係可藉由儲存在一個非暫時性電腦可讀媒 體，例如一個磁性、光學、或半導體儲存裝置，上的—連 _指令來實施。這-連串指令係可由任何以處理器為 的裝置實施。 為便說明，我們以-個像素井（沖e/讀）來表示像 素的視野平截賴。手邊的這個問題是要狀微多邊形的 在像素井内的哪些鋪塊對像素顏色有貢獻。針對各個微多 邊形，在模型視野投影轉換之後，在螢幕空間中會藉由， 例如，使用對樣本位置的—個查詢表，而產生—種靠近— 致分佈的點樣本，以使得每個像素都至少有—個鋪塊。為 了於抗混淆，這些像素井係被簡單地細分成數個子像素。 -個樣本只會影響—個（子）像素，並且在此樣本被界定 為最靠近者的情況下，它會填滿這整個（子）像素。在我 們以恒常鋪接（"__咖~)來表示的技術中，具有 最小Z座標的樣本會被選丨，而*管其在此像素相的x、y 位置其他途包括平面近似、和局部曲率近似。 這係可在像素粒度或在子像素層級完成，但為求明 晰在γ文中係對這個每一像素—個樣本的事例作論述。 在平面近似中，—個碟片係以由樣本點及其導數所界 定的有限範圍而被附接在各個鋪塊周圍’如於第3圖中所 示。此圖示出-列像素井的—個扣剖面圖，所以這些碟片 201234314 是被畫為從鋪塊位置突出的線條。在像素中心的深度值被 運算為此碟片和穿過此像素之中心的一個射線之交點。若 在此碟片之座標系統中所量測到的至像素中心之距離大於 一個給定臨界值，則深度值便被近似為在此碟片之邊緣的 一個夾鉗值。此夾鉗行為係例示在第3圖中。 要估算碟片之範圍的臨界值，係可使用一個局部二階 導數。對於具有較高曲率的區域而言，此局部平面近似是 一個粗略表示型態，並且代表碟片的半徑可能會被縮短。 例如’必須要注意就位在一個平面表面後的小型球面。若 不使碟片之範圍對曲率作適應，則來自於這個球面的剪影 之樣本可肖b會錯誤地成為透過這個平面表面而可見的。鑲 嵌·器可能已經將表面曲率納入考量，以提供大小平均的三 角形，並且若可獲得的話，係可使用局部曲率來估算碟片 半徑的較佳臨界值。 在局部曲率表面估算中，係可在代數適入微多邊形之 形心時使用局部球形表面近似，如於第4圖中所示。對各個 樣本點給定—個球面切線，則可對局部表面行為作近似。 概念上，係在各個鋪塊後附接一個球面，並且此球面的法 線係與樣本點的表面法線對齊。現在，在視野方向中形成 一道射線，通過像素中心。可採用此射線和球面的交點深 度作為此樣本的深度值。若沒有這樣的交點，則可替代性 地使用此球面的最大深度。 係可藉由下至像素大小之基元地鑲嵌和評估表面移位 遮掩器來達到多重取樣。—旦達到那個臨界值些實施 201234314 例係可彼接著簡單地以顏色和螢幕空間中之頂點位置(x y) 之内插，而對此三角形進行一致的平坦鑲嵌，直到這些邊 緣長度都小於0.75個子像素或者是某些其他保守邊緣長度 條件為止。所以，我們可以使用一種劃分與切塊鑲嵌途徑， 直到這些微三角形已相當小為止，並接著在這些三角形中 以内插法進行鑲嵌。 在跳過栅格化並以單一像素鋪接取代柵格化的數個實 施例中，係可避免大部分的三角形設立和所有的實際柵格 化處理程序。此外，係可將像素遮掩和頂點遮掩合併到單 -個遮掩器中’在-些實施例中，這可簡化規劃動作。 在並行栅格化器中，係可能會因為有複數個微多邊形 在同-個像素結束而發生像素寫入衝突。在剪影邊緣、或 是當在榮幕空間中重疊的兩個補片在同—批中被作可視度 測試時’可能會發生衝突。在—些實施财，針對競爭的 微多邊形而在行進中將對同—個子像素位置的寫入最小化 是很重要的。配合難技術，有複數個樣本想要更新同一 個子樣本的㈣崎商，並且較_職， 一個微多邊形的複數個鋪塊可能會影響同-個子像辛。、^ 或者是，可藉由在微多邊作適應來減少此影響。 塊，或者甚至是在不同的數個較個微多邊形内的鋪 減少寫入衝突。㈣，現今階基元上，作並行化來 ό 寫入衝突的硬體支援，所以2 Γ中已有對於處置類似 置的。 們將這個預期為是很易於處 201234314 大體而言，是會希望取得比遮掩樣本更多的可視性樣 本’以使得可對每個微多邊形或微多邊形頂點作一次遮掩 器評估。可接著產生鋪塊'將其分散在此微多邊形上，這 些鋪塊可係全都共享同一個遮掩值，或者是從頂點作内插 的一個遮掩值。透過内插法所得到的近似遮掩結果比起進 行疋全遮掩來說較不昂貴。因此，係可在使運算可視性處 於高比例的同時使遮掩率降低。 示於第5圖中的運算系統130可包括一個硬驅動機134 和一個可移除媒體136，可移除媒體136藉由一個匯流排1〇4 耦接至一個晶片組核心邏輯11〇。係可使一個鍵盤和滑鼠 12〇，或其他習知部件，經由一個匯流排105耦接至圖形處 理器112，以及使其耦接至主要或主機處理器1〇〇。圖形處 理器112可亦藉由一個匯流排1〇6而耦接至一個訊框緩衝器 114。訊框緩衝器Π4可藉由—個匯流排1〇7耦接至一個顯示 螢幕118。在-個實施例中’―個圖形處理器112可為使用 單指令多資料（single inStruction muhiple ㈣ SIMD)架 構的一個多緒式多核心並行處理器β 在-個軟體實作的事例中，係可將相關碼儲存在任何 適當的半導體、磁性、或光學記憶體中，包括主要記憶體 132或在關形處理器㈣任何可用記憶體。因此，在一個 實施例中，用來進行第1圖之序列的碼可係儲存在一個機器 或電腦可讀媒體，例如記憶體132或圖形處理㈣2,中， 並且在-個實施例中，係可由處理器丨⑻或圖形處理器ιΐ2 執行》 12 201234314 第1圖是一個流程圖。在一些實施例中，繪示於此流程 圖中的序列係可被實施在硬體、軟體或韌體中。在一個軟 體實施例中，係可使用一個非暫時性電腦可讀媒體，例如 一個半導體裝置、一個磁性記憶體、或一個光學記憶體來 儲存指令，且其係可由一個處理器執行，以實施示於第1圖 中的序列。 於本文中所描述的圖形處理技術係可在各種硬體架構 中實施。例如，係可將圖形功能整合在一個晶片組中。或 者是，係可使用一個分立圖形處理器。再舉另一個實施例， 這些圖形功能係可由一個一般用途處理器實施，包括多核 心處理器。 於本說明書通篇中對於「一個實施例」或「一實施例」 的指涉係指配合此實施例所描述的此特定特徵、結構或特 性係包括在涵蓋於本發明内的至少一個實作中。因此，「一 個實施例」或「在一實施例中」等詞語的出現並不必然係 指同一個實施例。此外，這些特定特徵、結構或特性係可 以與所例示之特定實施例不同的其他適當的形式制定，並 且所有的這些形式都可係涵蓋於本申請案之申請專利範圍 内。 雖然已針對有限數量的實施例來說明本發明，熟於此 技者會可識出從中而生的許多修改體和變異體。係意欲要 使後附申請專利範圍涵蓋落於本發明之真實精神與範疇内 的所有這些修改體和變異體。 c圖式簡單說明3 13 201234314 第1圖是本發明的一個實施例之流程圖； 第2圖是對一個三角形的描繪，它的一個頂點和形心都 在同一個像素内。此例示展示出一個限制事例的幾何組 態，當中形心和一個頂點都在此像素内； 第3圖是依據一個實施例的對局部平面表面近似之描 繪，用於終止針對一個給定像素的最靠近鋪塊（splat); 第4圖是依據一個實施例的對局部曲率表面近似之描 繪，用於終止針對一個給定像素的最靠近鋪塊； 第5圖是對本發明的一個實施例之概略描繪；並且 第6圖是對一個三角形扇的描繪，其具有位於像素中心 的一個共享頂點。 【主要元件符號說明】 118.··顯示螢幕 120.. .鍵盤和滑鼠 130.. .運算系統 132.. .記憶體 134.. .硬驅動機 136.. .可移除媒體 10〜20...方塊 100.. .主要或主機處理器 104〜107...匯流排 110.. .晶片組核心邏輯 112.. .圖形處理器 114.. .訊框緩衝器 14

Claims (1)

1. 201234314 七、申請專利範圍： 1. 一種方法，其包含下列步驟： 藉由將一個網目細分直到多邊形邊緣短於一個預 定長度為止，因而產生數個微多邊形，來適應性地鑲嵌 (tessellating);以及 藉由鋪接而顯現該等微多邊形。 2. 如申請專利範圍第1項之方法，其包含下列步驟： 鑲嵌三角形，直到該等邊緣在長度上短於 3/(2+sqrt(2))個像素為止。 3. 如申請專利範圍第1項之方法，其包含下列步驟： 鑲嵌三角形，直到該等邊緣在長度上短於0.75個像 素為止。 4. 如申請專利範圍第1項之方法，其包含下列步驟： 鑲嵌四角形，直到該等邊緣在長度上短於 2/(2+sqrt(2))個像素為止。 5. 如申請專利範圍第1項之方法，其包含下列步驟： 當底下的表面區域並不連續時取代於鋪接而柵格 化（rasterizing)基元。 6. 如申請專利範圍第1項之方法，其包含下列步驟： 利用内插法來進一步地鑲嵌一個微多邊形。 7. 如申請專利範圍第6項之方法，其包含下列步驟： 使用對樣本位置的一個查詢表，以及 每像素提供至少一個鋪塊。 〇 8. 如申請專利範圍第1項之方法，其包含下列步驟： 15 運算-個三角形的形心。 9·如申請專利範圍 判定⑽第項之方法，其包含下列步驟： 疋〜形心是否係在— 10.如申請專利範圍第 。。 當該形心是在-個像=其包含下列步驟： -如申請專利範圍第方素；3時更新一個像素緩衝器。 4||ffiT 負之方法，其包含下列步驟： 利用平面表面近似來判定可視性。 12.如申請專利範固 弟1項之方法，其包含下列步驟： 利用局部曲率表面近似來判定可視性。 洁存有& 7㈣暫時性電腦可讀雜，該 使一個電腦能夠進行下列步驟： 々會 —藉由將—個網目細分直到多邊形邊緣短於1 &長度為止’因而產生數個微多邊形，來適應@ 嵌；以及 疋镇 藉由鋪接而顯現該等微多邊形。 14·如申料利範圍第13項之舰，其進-倾存有用於 列步驟的指令： T 鎮嵌三角形，直到該等邊緣在長度上翅於 3/(2+Sqrt(2))個像素為止。 15. 如申請專利範圍第13項之媒體，其進一步儲存有用於下 列步驟的指令： 鑲嵌三角形，直到該等邊緣在長度上短於0.75個像 素為止。 16. 如申請專利範圍第13項之媒體，其進一步儲存有用於下 16 201234314 列步驟的指令： 鑲嵌四角形，直到該等邊緣在長度上短於 2/(2+sqrt(2))個像素為止。 17. 如申請專利範圍第13項之媒體，其進一步儲存有用於下 列步驟的指令： 當底下的表面區域並不連續時取代於鋪接而柵格 化基元。 18. 如申請專利範圍第13項之媒體，其進一步儲存有用於下 列步驟的指令： 利用内插法來進一步地鑲嵌一個微多邊形。 19. 如申請專利範圍第18項之媒體，其進一步儲存有用於下 列步驟的指令： 使用對樣本位置的一個查詢表；以及 每像素提供至少一個鋪塊。 20. 如申請專利範圍第13項之媒體，其進一步儲存有用於下 列步驟的指令： 運算一個三角形的形心。 21. 如申請專利範圍第20項之媒體，其進一步儲存有用於下 列步驟的指令： 判定該形心是否係在一個像素内。 22. 如申請專利範圍第21項之媒體，其進一步儲存有用於下 列步驟的指令： 當一個形心是在該像素内時更新一個像素緩衝器。 23. 如申請專利範圍第13項之媒體，其進一步儲存有用於下 17 201234314 24. 25. 26. 27. 28. 29. 30. 列步驟的指令： 利用平面表面近似來判定可視性。 如申清專利fe圍第13項之媒體，其進—步儲存有用於下 列步驟的指令： 利用局部曲率表面近似來判定可視性。 一種設備，其包含： 個處理器’用以藉由藉著將一個網目細分直到多 邊形邊緣短於一個預定長度為止作適應性鑲嵌，而產生 數個微多邊形，並用以藉由鋪接而顯現該等微多邊形； 以及 耦接至該處理器的一個儲存體。 如申凊專利範圍第25項之設備，該處理器係用於鑲嵌三 角形’直到該等邊緣在長度上短於3/(2+sqrt(2))個像素 為止。 如申請專利範圍第26項之設備，該處理器係用於鑲嵌三 角形’直到該等邊緣在長度上短於0.75個像素為止。 如申請專利範圍第26項之設備，該處理器係用於鑲嵌四 角形，直到該等邊緣在長度上短於2/(2+sqrt(2》個像素 為止。 如申請專利範圍第25項之設備，該處理器係用於利用内 插法來進一步地鑲嵌一個微多邊形。 如申請專利範圍第29項之設備，該處理器係用於使用對 樣本位置的一個查詢表，並係用於每像素提供至少一個 鋪塊。