TWI283835B - An adaptive method and apparatus for generating shadow using shadow volume - Google Patents

Description

1283835 ^ 九、發明說明： 【發明所屬之技術領域】 本發明係關於-陰影空間演算方法與妓，_是關於能調 適性使用深度通過演算法與深度失敗演算法的陰影空間演 • 與裝置。 / 【先前技術】 〜在三維麟㈣統巾，陰影的靖需要額外的技術來處理， _ 簡單地說就是減出位於陰影巾的㈣像素，這些技術包含有险 影空間(shadow V〇lume)、陰影映射(shad〇w咖卯㈣等^ =影空_方法主要是將陰影輯_空間定義成陰影空 間’來欺晝面上哪些部份是位於陰影空間内。如第—a圖所示， 線由統A照射，而遮蔽❹阻檔在其中，因此光線被遮 由物B所遮蔽的顧即為陰影空間s，陰影空間s可以用正面 t^face)與背面(backface)來界定。當晝面上的一物件〇要投 ^ G上時，可峨察出只有位置D與位置E間的部份 疋位在陰影空間S之内，其餘部份是位於陰影空間之外。 度的金面卜性 "中衣而在三維度影像投影在二維 二维要注意三維度影像中各物件_位置關係， 在被面部份的影像。因此三維度物件 在—：=:=== 1283835 Γ會，因此__錄各像素目前所顯示的深 又為此夠峋楚描述，被描繪物件相對於— %物件上)與被投影像素所顯示之在二中^二 ==度與，度。因此當待測:度=受=: 需要改為1 貞皮^像素目讀顯示位置的前面，被投影像素 物件’並顺影像素相應之受測深度需以 空間中i 此當某—個像素所相應之待測深度位於陰影 、門中時’轉素必需要被赌影色來鱗。 以是-般深度測試絲略深度測試， ι ς 2 “粗略深度測試可 時，則相畋王：又失敗’並且當取大待淨梅度小於最小受測深度 試之結果為全深度通過。如果粗略深度測試之 :=士王，敗或全深度通過時，則粗略深度測試之結果為 測粗略深度測試之結果為無法判定，則再以-般深度 在執行上述之三維度物件投影於二維度晝面的過財， 疋先將三維度物件以複數個多邊形來定義，再以多邊形 ^ ，之深度測試。_地’雜影空間也是舰定義成複數個 ，，包含有代表正面的正面多邊形與代表f面的背面多邊形 ，找出哪些制深度位於正面多邊與背面多邊形所界定之陰影空 6 1283835 • 因為利用光線追蹤技術來產生陰影的方法相當耗時，尤其是 在多個遮蔽物與多個光源之下，因此需要比較有效率的方法來處 理。模版(stencil)陰影空間方法是採用更新模版緩衝區來執行一= 簡單進/出計算的方法以簡易這樣的作業，它係採用執行在陰影空 . ，之正面(front-face)與背面(back-face)多邊形的深度測試來= - 定在陰影中的像素。例如，在模版陰影空間方法的實施上，模版 緩衝區的值係依據正面多邊形與背面多邊形的深度測試來被遞增 或遞減，因此如果最後的模版值為0，則像素不在陰影中。曰 、在陰影空間的深度測試中，受測深度大於待測深度的情形稱 為賴通過，反之被稱為深度失敗。據此，模版緩衝區的更新規 則上主要分為兩種陰影空間演算法，一為深度通過(Z pass)演算 法，另一則為深度失敗(Z fail)演算法。深度通過演算法是只對深 度，過來更新模版緩衝區，當深度通過的是正面多邊形時，模版 緩衝區的值會被遞增，並且#深度通過的是背面多邊形時，模版 緩衝區的值會被遞減。反之，深度失敗演算法是只對深度失敗來 •更新模版緩衝區，當深度失敗的是正面多邊形時，模版緩衝區的 值^皮遞減’並且當深度失敗岐背面多邊形時，模版緩衝區的 ^ - B圖與第—c ®所示係分麟深度通過演算法與深度 失敗演算法的示意圖。光源A的照射因遮蔽物B、c與d的阻二 ^成了:個陰影空間，物件Ε與F分別落在陰影空間之内與之 外度通過演算法時，相應於E，點的模板值為+ 1 + 1=2，、位 ' 門中’並且相應於p點的模版值為+1+1小K，位於陰 7 1283835 ，間之外:E’點與F，點的模版值共被更新過6次。相對地，在 深度失敗演算法時，減於E，點賴板值為+1_1 + 1小2，位於 陰影空間中，並且相應於F，點的模版值為〇，位於陰影空間之和 E，點與賴版值共被更新過4次。顯然地，上叙視角以深 度失敗演算Ϊ較為適用，可見以相同的視角觀看時，採用不同的 陰影空間演算法能得到相同的結果，可是卻導致不同的運算量。 此二:g視纽㈣所相的景像也會不同，因此翻的陰影空 間演算法也有可能不同。例如在第一 D圖的j點來觀看，原本在 第- C圖所看到的E，點與F，點已被遮住，變成看到 f 點。以深度失敗演算法需要更新7次，分別為e，點需要3，次^ f 點需要4次。_度通過演算法需要更新 3次，m需要〇次。據此，以深度通過演算法較為f要 、第一 E圖舉例了在數個連續的圖幅(frame)中以深度通過與 /木度失敗對模版值更新次數的相對義，有的圖幅深度通過的更 新次數比好，有顧酶度失敗的更新次數比較多。如果全部 以深度失敗演算法將會有許多圖幅不適用，因此f要—種新的設 計來減少模版值的更新次數。 觀察上述例子’可以發現雖然深度通過演算法與深度失敗演 算法所得出的結論都相同，但是運算量卻有差異，也就是說因視 者觀看方向料同，兩者的·量也柯。在應紅—般是在深 度通過决算法或深度失敗演算法兩者中選擇一個，因此運算成本 與更新模版緩衝區的頻寬很容易因觀看角度的不同而變得很大， 因此需要一種解決的方法，來以適合的深度測試進行運算。 1-283835 【發明内容】 本^目的係在深度測辦_深度通稍深度失敗的 里、、間較小者來決定下一圖幅的深度空間演算法。 本發明之另—目的雜深度職時統計全深度通過與 =敗的數里’依據兩者間較小者來決定下—圖幅的深度空間演^ 據此，本發明提出一種陰影空間演算方法與裝置。在 幅彩現陰影空間時’藉由統計深度通過與深度失敗的 = ^以，通過演算法與深度失敗演算法間分別運算於此圖幅= ^康此，便可以依據其中較佳者來做為下—圖幅的陰影空間演 异法。 、 【實施方式】 本無明在此所&相方向為—種調適性陰影空間演算法之 影產生裝置與方法。為了能徹底地瞭解本發明，將在下列的^ 中提出詳盡的結構。顯然地’本發_施行並未岐於^置 之技藝者所熟習的特殊細節。另—方面，科周知的組成或g 步驟並未ί述於細節巾，㈣免造成本發明不必要之關:= 明的較佳貫施例會評細描述如下，然而除了這些詳細描述之 本發，還可以廣泛地施行雜他的實施射，且本發明的範圍不 受限定，其以之後的發明範圍為準。 1283835 算法(shadow volume如伽)包含深度通過 Z pass 法與深度失敗(z fa触紐。在複數個 f)中’可能__藉由深度通 ==會有比較好的效能，而有的圖幅藉由深度失敗會U乂 ===果只用—種陰影空間演算法來決定像素中的陰 影區域，可能導致效能變差。

在稷數個連續圖幅中，可能包含—個或—個以上的場景 fcene)，在相同的場景的圖幅所呈現的物件大致都差不多，尤其 是背景部份。軸場景_，但是因她看方向的不同，圖幅^ 見的物件及相關的陰影也會有所不同’僅管如此，在相同場 厅、中差別並不大’因此如果在—圖幅所適用於深度 ^過^寅算法，、在下-圖幅也適㈣可能性會比深度失敗演算法 ^喜亦然。在之後的描述中，陰影空_前面多邊形與背面 夕邊形被統稱為陰影空間多邊形。 • 以/二_根據本發明之—具體實施例之流程示賴。由先前 付可知y邊形包含一般影像物件的多邊形與陰影空間的多邊 ，兩者疋在不同階段被描繪’先是—般物件的多邊形，然後是 f影空間的多邊形。首先，流程由步驟200開始，在步驟201對 Γ度=累4值、珠度失敗累計值與預設陰影空間演算法初始 /、陰〜1間’冑算法係由深度通過演算法與深度失敗演算法 .中預設-個。接下來步驟2_始描繪第—個多邊形，描纷之流 開始是由步驟203判斷是否所有多邊形尚未描繪完畢。如 果尚未描繪完畢，由步驟咖靖是縣陰影_多邊形。如果 1283835 空間多邊形，啦步驟2〇5來彩現錯形、進^e 由步驟2〇1: 描纷。反之，如果為陰影空間多邊形，則 測試、累加、、ί見^邊Γ深度值、進行一般深度測試/粗略深度 行下—多邊形的描繪。另外，在步驟_ 過累計射尚未麟，則由步驟 _是否深度通 敗累計值，目ir度失敗累計值。如果深度通過累計值大於深度失 失敗°，再*1步驟2G9決定τ—®幅之陰影·演算法為深度 :驟211進行下一圖幅的初始化。如果深度通過累計 於冰度失敗累計值，則由步驟210決定 旦; =為深度通過，再由步驟211進行下一圖幅的二 ’ ’被描_巾時被指定為下-圖幅，並麟度失敗累 計值與預設陰料間法會被初始化(如設定為Q)。 ，、 據此，翏考第二圖，本發明之另一具體實施例係一種調適性 • 陰衫工間，貝算法之陰影產生方法。首先，如步驟310所示，彩現 圖巾:之所有物件，其中每一物件係以複數個多邊形來表示，該 圖幅係被彩現於複數個像素，這些像素可以是被儲存在繪圖緩衝 區(frame buffer)中。接下來，如步驟320所示，以一預設之陰 影空間演算法彩現-圖幅之陰影空間並同時統計一深度通過統計 值與一洙度失敗統計值。最後，如步驟33〇所示，在預設之陰影 空間演算法對該圖幅彩現陰影空間後，依據該深度通過統計值與 该深度失敗統計健-深度通過演算法與—深度失敗演算法中選 . 擇一種做為該預設之陰影空間演算法。因此在下一圖幅重新執行 11 1283835 步驟310與步驟32〇 所選之陰影空間演算法來彩丄影】二依照本圖幅在步驟咖 據此，如第四圖所示，本發明之一且 ^來儲翻應崎—個賴 ΐί=32=_251，___ 仰是 可以是複數㈣*的任何—侧幅赌資料。其帽述之®幅251 圖一〇% 圖幅25中的任何—個，此圖幅251之下一個 圖^元^二述以下一圖幅252來表示，下一圖幅252係由綠 ^ H .. 魏圖幅251之後依據下一圖幅描述資料232所彩 320所示，繪圖單元24依據一命令242從陰 之一深度通過演算模式244與一深度失敗演 ，選擇—個來更新模版緩衝區22,繪圖單元24係藉 以=工間〉寅算邏輯更新模版緩衝·以的模版值來界定 二二n i y>相對於一觀看方向的一陰影區域脱2，並且同時統計 冰度通顧推247與—深度失敗統計值·，相應於下一圖 田、^52的〒令242係由選擇單元26依據深度通過統計值247 ”深度失敗統計值249來產生，如步驟33◦所示。 ，米度通過演算模式244被選擇時，陰影空間演算邏輯241 ^深度通過演算法來決定陰影區域2512，相反地，當深度失敗 ’、算模式246被選擇時，陰影空間演算邏輯24土係以深度失敗演 12 1283835 ίΐΐ決定陰影區域2512。陰影區域2512為圖幅251中位於 陰像賴合，此陰影_ 2512係械類版緩衝方區 22中不為〇的模版值，陰影區域2512帽有的像素係 疋24以陰影色彩現來產生陰影效果。 口早 251 249 此外’繪圖單元24係利用深度測試(z test)來更新圖幅 之像素的魏，射深魏過辑值247與 係在進行深勤懷_針賊生。 、^指

物？!單元26依據深度通職計值247與深度失敗統計值 249來產生下一圖幅之命令如。亦即選擇單元％齡比較 失敗統計值249，選出兩者中較小者所 相應的陰鼻模式。例如當繪圖單元24在彩現下一圖幅

=2時，下一圖幅之命令262會被選擇單元％做為為本圖幅: 中ί 261，並且被送至_單元24以成為命令242。另外，選 擇單元26可以疋硬體或軟n ’例如(但不受限於卜邏輯電路或選 自下列群組之-的軟體：驅動程式(driver)、軟體朗程式呼 面(Software AP)。 1 上述第二圖之粗略深度測試之結果可為全深度通過、全深度 失敗與無法判定中其巾—種。在深度職在上述步驟咖與步驟 2〇H，或是在步驟32°中’可以是只用粗略深度測試，或只用 般未度貝K式’也可以是先以粗略深度測試，當粗略深度測試之 結果為無法顺時，再制深度測試。 13 1283835 其=上述之彩現_幅之所有物件的過 相應於母-個像素之—職^錢並更新 過程中包含更新她於每—轉素之陰影空間的 以界定位於圖幅之陰侧_像素。模版值與=== I應之模版 外，麵娜贿咖細嶋彡^ς== 深度值進彳爾顺，__試之_=對相應之 值0 來二卜二：—Β圖中，有兩種多邊形’-為陰影空間多邊 形’為叙物體多邊形(即E、F)，當一 時，應該是位於-祕㈣知、, ^邊形被衫現 nt 邊形W面的像素㈣被累計至深度通 值。因此虽每—個陰影空間多邊形被彩現完時，深度通過 統計值累計了每-個陰影空間多邊形深度通過的像素數量，並且 ^度j統計值累計了每—個陰影空間多邊形深度失敗的像素數 里。再者，上述之深度通過演算法係對每—個陰影 度通過的像細械之觀錢新，並且上叙深度失 係對每-嫌料._失_像麵械之模紐更新了 據此相車乂於第一 D圖與第五圖，可以發現本發明所採用的 陰影空間演算法適用的圖幅數量多於先前技術所適用的數量。顧 然地本發明可隨著連咖幅_容而適度修正，_減少對模 版缓衝區的存取次數。此外，在步驟33Q與選擇裝置巾，亦可以 是當深度失敗統計健深度通過統計值_差值超過—門护限值 時’才重設預設之深度空間演算法，以減少深度空間演算二的變 1283835 化量。 顯然地，依照上面實施例中的描述，本發明可能有許多的修 正與差異。因此需要在其附加的權利要求項之範圍内加以理解， 除了上述詳細的描述外，本發明還可以廣泛地在其他的實施例中 施行。上述聽本發明之較佳實_而已，並翻雜定本發明 之申請專娜圍；凡其它未麟本發明所揭私精神 等效改變或修飾，均應包含在下述申請專利範圍内。

15 1283835 _ 【圖式簡單說明】 第一A圖至第一E係先前技術之示意圖； 第二圖係本發明之一具體實施例之流程示意圖； 第三圖係本發明之另一具體實施例之流程示意圖； 第四圖係本發明之再一具體實施例之功能方塊示意圖； 第五圖係本發明相較於第一 E圖之優缺點比較圖。. 【主要元件符號說明】 A光源 B遮蔽物 E’、F’受測位置 e’、f受測位置 G平面 Η視者’ I視者 〇物件 S陰影空間 > 22模版緩衝區 23圖幅描述資料群組 231圖幅描述資料 24繪圖單元 241陰影空間演算邏輯 242命令 244深度通過演算模式 246深度失敗演算模式 16 1283835 " 247深度通過統計值 249深度失敗統計值 25複數個連續圖幅 251圖幅 • 2512陰影區域， 252下一圖幅 26選擇單元 261本圖幅之命令 k 262下一圖幅之命令（第四圖中無262)

17

Claims (1)

1. J283835

   十、申請專利範圍： L :種具有調適性陰影空間·邏輯的_裝置，該具有調雜 陰影空間演算邏輯的繪圖裝置包含·· ^會’元，該繪圖單元係以複數個像素來彩現㈣㈣一圖 包含在以—職之陰影空_算法對_幅彩現陰影空 曰時亡计-?度通過(Zpass)值與一深度失敗(ζ_值；以及 =擇單70，該選擇單元係於繪圖單元以該預設之陰影空間 =^對該_彩現陰影空間後，依據該深度通過統計值與該深 ίίΐϊ雜從—深度通過法與—深度失敗演算法中選擇一 種做為該預設之陰影空間演算法。 2· 範Γί2項所述ί具有調適性陰影空間演算邏輯 ^ 、中上述之選擇單兀係-軟體，該軟體係選自下 且之-：驅動程式、軟體應用程式啤叫界面(s〇ftware AP) 〇 3· 範1項所述之具有調適性陰影空間演算邏輯 述之_單祕含記錄並更新相應於每一 =ΙΓ；:深度值與—模版值，其中該模版值係用以界定位 於該圖幅之陰影空間内的像素。 4 項所述之具有調適性陰影Π寅算邏輯 ==:△繪圖單元對該陰影空間的彩現包含以 形對該複數個像素所相應之該深度值進 仃一冰度啦’以更新該複數個像素所相應之該模版值，其中 I 1283835 月曰修(tiiE替換頁 該複數個陰影空間多邊形係用以呈現陰影空， 5.如申請專利範圍第4項所述之具有調適 =裝置’其中上述之深度測試包含一粗演算邏輯 般^測試’該—般深度測試係以單一像素逐與--粗略深_試細轉料_區塊來_進試，該 2、、會圖裝置，其中上述之粗略深度測 、异邏： 素為全深度通過、全深度失敗與無法判定中的!^塊之該像 7.==利範圍第6項所述之具有調適性陰影空間演算邏輯 則該區塊之該像素糾進行—般随測試。U匈疋時 8· 第3項所述之具有調適性陰影空間演算邏輯 2繪圖裝置’其中上述之繪圖單元更包含在該深度測試中，對 母-個陰影空間多邊形深度通過之像素數量累計以統計出該 深度通過統計值’並且對每一個陰影空間多邊形深度失敗的像 素數量累計以統計出該深度失敗統計值。 9·如申請專利範圍第3項所述之具有調適性陰影空間演算邏輯 的繪圖裝置，其中上述之深度通過演算法係對每一個陰影空間 多邊形深度通過的該像素所相應之該模版值更新，並且該深度 通過演算法係對每一個陰影空間多邊形深度失敗的該像素戶^ i i 96. 1.26 y 年月日修正替換頁 1283835 相應之該模版值更新。 10·如申請專利範圍第1項所述之具有調適性陰影空間演算邏輯 的繪圖裝置’其中上述之選擇單元係在該深度通過統計值大於 該深度失敗統計值時選擇以該深度失敗演算法做為該預射之 陰影空間演算法’並且在該深度通過統計值不大於該深度失敗 統计值時選擇以該深度通過演算法做為該預射之陰影空間演 算法。 、

   11· — 種調適性陰影空間演算法之陰職生方法，該調適性陰影空 間演算法之陰影產生方法包含： 彩現-圖幅之所有物件，其中每一物件係以複數個多邊形來 表不，該圖幅係被彩現於複數個像素； 士以-預設之陰影空間演算法彩現一圖幅之陰影空間並同時統 汁一深度通過統計值與一深度失敗統計值；以及

   在該預設之陰影空間演算法對該圖幅彩現陰影空間後 該深度通職計值無深度失敗統計值從通過演算法盘一 深度失敗演算法中選擇-種做為該預設之陰影空㈣算法。” 12. 如申請專利範圍第u項所述之調適性陰影 產生方法’其巾上述之彩現該圖幅迅/ 錄並更新相應於每-個該像素之一深度 1 物件的過程中包含記 13. 如申請專利範圍第12項所述之調適性陰影空間演算法 產生方法，其中上述之以該預設之陰影空_算法彩現該= 20

   1283835 之陰影空間的過程中包含更新相應於每一個該像素之一模版 值’其中該模版值係用以界定位於該圖幅之陰影空間内的像 素0 14·如申請專利範圍第13項所述之調適性陰影空間演算法之陰影 產生方法，其中上述之對該陰影空間的彩現包含以該複數個陰 影空間多邊形對該複數個像素所相應之該深度值進行一深度 測試’以更新該複數個像素所相應之該模版值。 15·如申請專利範圍第14項所述之調適性陰影空間演算法之陰影 產生方法’其中上述之深度測試包含一粗略深度測試與--般 深度測試，該-般深度職係以單—像素逐—進行戦 略深度測試係以複數個像素為一區塊來同時進行測試。 像素 16=:=第15項所述之調適性陰影空間演算法之陰影 產生方法’其中上述之粗略深度戦之結果係全區塊之談 為全深度通過、全深度失敗與無法判定中的—種。“ 17·=申清專利範圍第16項所述之調適性陰影空間演算法 產生方法，其中上述之粗略深度測試之 切 該區塊之該像素另外進行-般深度測試。'去判疋時，則 ,8ΗΞΞΞΞΞ 1283835

   每-個陰影空間多邊形深度失敗的像素數量累計以統計出該 深度失敗統計值。 19.ΐΙ j利ΓΓ第13項所述之調適性陰影空間演算法之陰影 述之深度通频算雜對每—嫌影空間多 ί ϊ 卿狀軸雜㈣，並城深度通 應之該模版值更新 ^异法騎母—個_如多_深歧朗

   22