可重建幾何陰影圖方法

2023-10-08 12:28:14

專利名稱：：可重建幾何陰影圖方法
技術領域：
：本發明是有關於一種圖形處理，且特別是有關於一種陰影繪圖。
背景技術：
：在計算機繪圖中，陰影圖(Shadowmapping)以及陰影錐(shadowvolumes)是二種常用的實時(real-time)陰影技術。陰影錐是FrankCrow在1977年所提出的技術，使用幾何方法計算3維(3-D)物體遮光區域。此算法利用模板緩存(stencilbuffer)來計算某一像素(測試像素)是否在陰影中。陰影錐的主要優點是對於像素是準確的，反之陰影圖的準確性需視紋理存儲器(texturememory)大小以及如何投影陰影而定。陰影錐技術需要大量的硬體填繪時間，而其執行速度往往會比陰影圖技術要慢，尤其是大規模複雜幾何場景。陰影圖是將陰影加入3-D計算機圖像中的技術，其由LanceWilliams在1978#是出。此算法被廣泛應用於預先描繪(pre-rendered)場景，以及實時(real-time)的應用中。通過光源觀察點比4交遮光物與測試像素的深度，亦即測試對光源而言某個測試像素是否可見，以便建立遮光物的陰影。陰影圖是一種簡單有效的圖像空間方法(imagespacemethod)。陰影圖是陰影表現方法其中之一，其常常應用在高速需求上。然而，其遇到了鋸齒問題(aliasingerror)以及深度偏移問題(depthbiasissues)。解決這兩個缺點是陰影表現
技術領域：
的研究課題。在陰影圖中的鋸齒錯誤可以分為二類透視鋸齒錯誤(perspectivealiasingerrors)以及投影銀齒錯誤(projectivealiasingerrors)。在陰影邊緣放大時會發生透視鋸齒錯誤。當光線幾乎平行幾何表面且延伸超出深度範圍時，就會發生投影鋸齒錯誤。大部分陰影圖技術的另一個問題是深度偏移問題。為了避免錯誤的"自陰影"(self-shadowing)問題，William揭露一種常數深度偏移^支術，其在與真實表面(truesurface)比較之前便將其加入深度釆樣中。不幸地，太多的偏移可能會導致錯誤的"無陰影"(non-shadowing,看起來像是遮光物浮在光線4妻收物的上方)而使陰影后退太遠。實際上，直接地決定偏移值是非常難的，並且無法在每一個場景找出一個通用可接受的值。
發明內容本發明提供一種可重建幾何陰影圖方法，以降低"透視鋸齒，，(perspectivealiasing)與"投影鋸齒，，(projectivealiasing)這二種鋸齒錯誤，並解決深度偏移而引起的錯誤"自陰影"(falseself-shadowing)與4晉i吳"無陰f》"(falsenon-shadowing)等問題的課題。本發明提出一種可重建幾何陰影圖方法。首先以光源為觀察點，儲存物體前表面(fonrt-facing)的多個遮光幾^T形的幾何信息。將測試4象素進行一致性測試，以使^人多個遮光幾何形中找出相對應於測試像素的遮光幾何形。其中遮光幾4可形具有遮光點；以光源為，見察點，此測試^象素與該遮光點重疊。4吏用上述遮光幾何形的幾何信息以及測試像素的位置信息，重建遮光點的深度值。最後比較遮光點的深度值與測試像素的深度值，以完成測試像素的陰影判斷。在本發明的一實施例中，上述的幾何信息可以包括所述幾何形的頂點坐標或者圖形索引。上述一致性測試可以包括下述步驟。首先選擇所述幾何形其中之一，然後讀取所選擇幾何形的幾何信息，其幾何信息中包括該幾何形的頂點坐標(Vo.X,v。.y，v。.z)、(vpx,v!.y，v,.z)以及(v2.x,v2.y，v2.z)。接下來計算等式[p.xp.yl]=[w,formulaseeoriginaldocumentpage6,以求耳又遮光點的重心坐標丫直(Wl,w2,w3);其中(p.x,p.y，p.z)為觀'J試4象素的坐標。依4居遮光點的重心坐標值(Wnw2,w3)判斷所選才奪的幾何形是否為一致的。若所選擇的幾何形判斷結果為一致的，則該幾〗可形為遮光幾何形。在本發明的一實施例中，上述重建遮光點深度值的步驟包括計算等式r.z-[w,,,以求耳又該遮光點的深度值T.z。在本發明的一實施例中，上述重建遮光點深度值的步驟包v0.xV0Jrv0.x1——1v0.z括計算等式T.z==h，w2，w3]承V,.xv，Ji*h.x1*v>2,xv2._yiv2.xv2.y1v2.zv0.xr_1v0.z1承v2.xv2)1v2.z，以求取遮光點的深度^f直T.z。括在本發明的一實施例中，上述重建遮光點深度值的步驟包formulaseeoriginaldocumentpage6，以J^耳又遮光點本發明因以光源為觀察點儲存物體的前表面多個幾何形的幾何信息，因此可以使用該測試像素的位置信息以及所儲存的幾何信息，重建遮光點的深度值。獲得遮光點的深度值後，便可以比較遮光點與測試像素二者的深度值，以完成該測試像素的陰影判斷。本發明所述的可重建幾何陰影圖方法，通過減低透視鋸齒與投影鋸齒，可以產生精確的陰影邊緣。圖l是依照本發明實施例說明一種可重建幾何陰影圖方法的流程圖。圖2是依照本發明實施例說明陰影圖、物體表面(部分)與測試像素的空間關係。圖3A說明二個相鄰接三角形TR0與TR1。圖3B說明在圖3A中三角形TR0與TR1的光柵化區域AR0與AR1。圖3C是依照本發明說明二種採樣模板的圖樣範例。圖4A說明標準陰影圖所產生的投影鋸齒錯誤。圖4B是依照本發明實施例說明可重建幾何陰影圖所產生的投影鋸齒結果。圖5A說明標準陰影圖以常數深度偏移技術(深度偏移值le-3)所產生的測試場景。圖5B說明標準陰影圖以常數深度偏移技術(深度偏移值le-6)所產生的測試場景。圖5C是依照本發明實施例說明可重建幾何陰影圖(深度偏移值le-6)所產生的圖形深度偏移測試場景。具體實施方式為讓本發明的上述特徵和優點能更明顯易懂，下文特舉較佳實施例，並配合所附圖式，作詳細i兌明如下。本領域技術人員可以參照以下實施例來實現本發明。當然，下述實施例亦可以電腦程式的形式實現，並利用計算機可讀取儲存介質儲存該電腦程式，以利計算機執行可重建幾何陰影圖的方法。圖l是依照本發明實施例說明一種可重建幾何陰影圖方法的流程圖。本實施例可以處理多個光源。為能簡單清楚說明本實施例，以下將以單一光源為例來說明可重建幾何陰影圖的方法。在計算機所繪製的圖形中，物體表面可以由多個幾何形(例如三角形或其他幾何形)所構成。本實施例將假設物體表面是由多個三角形所構成。本領域普通技術人員可以任何技術繪製上述物體表面。圖2依照本發明實施例說明陰影圖、物體表面(部分)與測試4象素的空間關係。從光源觀點光源〗現察點(light'spointofview)可以糹會出i為景。以，存、光源(pointlightsource)而言，jt匕觀察點可以是透一見投影(perspectiveprojection)。對於指向性光源(directionallight)而言,可以使用正交投影(orthographicprojection)。如圖2所示，遮光物體表面包4舌三角形TR0、TR1、TR2與TR3。從上述繪製中，會擷取每一個遮光三角形(occludingtriangles)TR0TR3的信息，並將其存放在幾何陰影圖(geometryshadowmaps)中。亦即，以光源觀點光源為觀察點，-賭存某一物體的前表面的多個幾何形的幾何信息(步驟S110)。於本實施例中，上述幾詞M言息可以包括各個幾4可形的頂點坐標，例如遮光三角形TR0TR3的頂點坐標或者包括各個幾何形的圖形索引。在光源觀察點的規範視體(lightcanonicalviewvolume)與光源碎見點空間(lightviewspace)中，此三角形的線性特性可以讓我們以在點光源(和指向性光源一樣)下重建這些遮光三角形。接下來進行步驟S120，將測試像素進行一致性測試，以從所有幾何形中找出一遮光幾何形。其中，該遮光幾4可形具有遮光點(以光源為觀察點的幾何陰影圖中，該測試像素與該遮光點重疊)。步-驟S120可以應用幾何陰影圖(geometryshadowmaps)從攝影觀察點(cameraviewpoint)繪製場景。此處理具有三個主要構件。對於物體的每一個測試〗象素(testingpixel,例如圖2中的測試像素P)而言，首先要找出從光源所看到像素的坐標(p.x,p.y,p.z)。坐標(p.x,p.y,p.z)的x與y值對應於在幾何圖紋理(geometrymaptexture)中的位置，並JM皮4吏用於三角形一致性測試(triangleconsistencytests)以侵_找出遮光三角形。上述步驟S120可以找出測試像素P的遮光三角形是TR0。接下來進行步驟S130,使用遮光幾何形的幾何信息以及測試像素的位置信息，重建遮光點的深度值。也就是使用步驟S110所儲存的幾何信息來重建像素P的遮光點深度值(例如圖2中遮光點Pd的深度值)。接下來進行步驟S140，比較遮光點Pd的深度值與測試像素P的深度值，以完成測試像素P的陰影判斷。對照於遮光三角形TRO的重建深度值，測試像素P的z值(深度值，得自光源觀察點的>見範牙見體(lightcanonicalviewvolume))卄誇#皮測i式，以完成測試像素P的陰影判斷。最後，繪出在陰影中或是在光亮中的所測試像素。若有多個光源，則對每一個光源使用各自不同的幾何陰影圖。本領域普通技術人員可以依照上述說明而實現本實施例。以下將說明圖l中各步驟的詳細實施範例，然而本發明的實現方式不應以此受限。圖2說明從光的觀察—見空間的點光源轉換至光源觀察點的規範視體中的指向性光源。假設在光源觀察點的規範視體中的場景是由四個相鄰三角形TR0、TR1、TR2與TR3所組成。首先(步驟S110)，三角形TR0TR3分別被投影(projected)與光柵化(rasterized)至幾何陰影圖中其對應的區域AR0、AR1、AR2與AR3。在各區域AR0AR3中的每一個紋理元素(texel)包含其對應三角形的幾何信息(本實施例中為頂點坐標)，例如在區域AR0中的紋理元素包含三角形TR0的頂點坐標(vo.x，v。.y,Vo.z)、(Vpx,v卜y,v卜z)以及(v2.x,v2.y,v2.z)。步驟S110除了將幾何信息儲存在陰影圖外(現有技術儲存在陰影圖的是深度值，而不是幾何信息)，步驟S110的操作幾乎等同於標準陰影圖。對於點光源而言將場景轉換至光源觀察點的規範視體(lightcanonicalviewvolume)，然後在其陰影圖的光柵化區域儲存了三角形的三個頂點坐標。另一個方式可以從相鄰接的三角形獲得坐標頂點。例如在圖2中，與三角形TRO相鄰接的三角形TR1、TR2與TR3的6個頂點坐標均被儲存在三角形TR0的光柵化區域。對於指向性光源而言，則儲存指定"處理中"光源觀察點的規範視體空間的頂點坐標，此觀察點空間的光線平行於z軸。接下來，在可視空間(eyespace)中的可見4象素(visiblepixel)P被轉換至光源觀察點的規範視體坐標(p.x,p.y，p.z)。步驟S120所述一致性測試可能包括選l奪幾何形(例如三角形TR0TR3)其中之一。步驟S120可能包括讀取所選擇幾何形的幾何信息(例如，若選擇三角形TRO,則從幾何陰影圖讀取區域ARO的幾何信息)。上述幾何信息中可以包括幾何形的頂點坐標，例如三角形TR0的頂點坐標(vo.x，vo.y,v。.z)、(VlX，v!.y,Vi.z)以及(v2.x，v2.y,v2.z)。以二維(2-D)坐標(p.x,p.y),可以找出幾何陰影圖中對應的採樣點T。在此步驟S120可能包括計算等式l:formulaseeoriginaldocumentpage11以求:f又對應於三角形TRO頂點的遮光點Pd的三維(3-D)重心坐標虧直(w!,w2，w3)。依才居遮光點Pd的重心坐才示<直(w!,w2,w3)判斷所選擇的幾何形(三角形TRO)是否為一致的。對於每一個可見像素P,遮光三角形TRO需要被正確定位，以便接下來可以從儲存在幾何陰影圖的幾何信息重建此遮光點Pd的深度值。此處理便是所謂三角形"一致性測試"。然而，具有觀'Ji式4象素坐才示(x,y)的採才羊糹丈J裡圖(samplingtexturemaps)不一定能返回有關擋住該測試像素P的三角形TRO的信息。若從等式l所計算獲得的三個重心坐標值(wl5w2，W3)是在[0,1〗範圍中(意思是此三角形擋住了該測試像素)，便稱此三角形測試是一致的(consistent)。否則此觀'j試是不一致的(inconsistent)。若所選#^的幾何形判斷結果為一致的，則幾何形(三角形TR0)為測試^象素P的遮光幾何形。由於陰影圖的有限解析度，可能導致三角形測試的不一致結果。若紋理貼圖的解析度比較低，則更有可能讓三角形測試結果變得不一致。圖3A說明二個相鄰接三角形TR0與TR1，而三角形TR0與TR1為有限解析度。圖3B說明在圖3A中三角形TR0與TR1的光柵化區域AR0與AR1。在有限解析度之下，區域ARO為三角形TRO的光柵化區域，而區域AR1是三角形TR1的光柵化區域。點T是採樣點(sampledpoint),其具有與所測試可見像素P相同的(x,y)坐標。然而通過採樣點T,本實施例所存取者為帶有三角形TR0幾何信息的紋理元素A。如圖3B所示，採樣點T本來應該在三角形TR1的光4冊化區域內，然而三角形TR0的信息可能會因為有限解析度而導致錯誤的深度值重建(錯將釆樣點T視為三角形TR0的遮光點)。圖3B中採樣點T，亦有相似問題。以相鄰接三角形的幾何信息，通過採樣對應點T可以找出擋住所測試像素P的遮光三角形。然而，當二個相鄰區域被光柵化，鄰接三角形的幾何信息便可能會不能使用。為了解決這個問題，本實施例增加釆樣點以包含更多三角形的幾何信息，因此也增加了找出一致的三角形測試的機會。圖3C是依照本發明說明二種採樣才莫板(samplingkernels)T與T，的圖樣範例。若所測試像素P被多層幾何表面所擋住，此模板亦可排序所有一致三角形測試的深度結果，並且取其最小值作為遮光點的最終深度值。以採樣模板T的圖樣為例，除了存取帶有區域ARO信息的紋理元素來計算採樣點T之外，更存取帶有區域ARO信息的紋理元素來計算採樣點T2的深度值，存取帶有區域AR2信息的紋理元素來計算釆樣點T1的深度值，以及存取帶有區域AR1信息的紋理元素來計算採樣點T3與T4的深度值。接下來排序所有一致三角形測試的深度結果(T、Tl、T2、T3與T4的深度值)，並且取其最小值作為遮光點Pd的最終深度值。對於準確性而言，選擇適當的模板圖樣是很重要的。相較於較小模板圖樣而言，大一點的模板圖樣常常提供較高準確性。然而，包含許多採樣點的較大模板可能不利於性能。圖3C所示的特殊模板圖樣可以較少的採樣而實現相近的準確性。通過設定某一測試像素的三角形一致性測試總量，更可以減少採樣數對於所測試的像素P,當紋理解析度是臨界的(subcritical，其將導致一些遮光三角形無法存入陰影圖)，這些對應三角形測試必定不一致。基於此，這些三角形測試便依照到中央三角形的加權距離的順序而被排序，以便使用對應於"最近距離，，(closest-distance)權重值三角形信息來進行重建。當合理的假設重建遮光點是在"最近距離"三角形的相同平面，此經計算獲得的加權距離可以是歐幾裡德幾何學(Euclidean)的計算方法。在獲得了正確的三角形信息後，所測試像素的遮光點深度值可以^皮重建。經由三角形插值(triangleinterpolation),遮光三角形TR0中遮光點Pd的深度值可以^皮重建。在從等式l計算出上述權重值後，步驟S130中遮光點Pd的深度值T.z可以利用下式重建formulaseeoriginaldocumentpage13(等式2)或者，結合等式1與等式2，可以獲得等式3:formulaseeoriginaldocumentpage13(等式3)v2.xv2.y1步驟S130中遮光點Pd的深度值T.z可以利用等式3重建。在上述等式3中必須進行3x3矩陣的逆運算。目前圖形處理單元(GraphicsProcessingUnit,GPU)硬體並未直接支持3x3矩陣的逆運算。因此我們必須將其分解成一些通常的算術邏輯運算單元(arithmeticandlogicunit,ALU)指令。然而，ALU指令集並不能保證精確性，而且可能會對逆運算結果引入更多相關的誤差而影響到最終的重建深度值。為了改善上述問題，本實施例將等式3改寫為下述等效的等式formulaseeoriginaldocumentpage14因此，步驟S130中遮光點Pd的深度值T.z亦可以利用等式4重建。最後通過比較遮光點Pd與像素P的光源規範視體深度值(canonicalvolumedepthvalues),亦即t匕4交T.z與p.z,可以冗成像素P的陰影判斷(步驟S140)。圖4A說明標準陰影圖所產生的投影鋸齒錯誤。圖4A顯示的場景是懸浮在底平面上方的一塊四邊形板，因此四邊形板在底平面形成一帶狀陰影。圖4A左下角顯示所述帶狀陰影的局部放大圖。從圖4A可以很明顯看出，傳統標準陰影圖所產生的投影鋸齒錯誤是很明顯的。相較於圖4A,圖4B是依照本發明實施例說明可重建幾何陰影圖所產生的投影鋸齒結果。亦即，圖4B使用了上述本發明實施例所介紹的新算法可重建幾何陰影圖(ReconstructableGeometryShadowMap,RGSM),做為鋸齒問題的解決方案。圖4B顯示的場景與圖4A相同。/人圖4B可以4艮明顯看出，本發明實施例所使用的RGSM算法所產生的投影鋸齒錯誤很明顯的得到大幅度的改善。大部分陰影圖技術的另一個問題是深度偏移問題。圖5A、5B與5C的圖形深度偏移測試的場景相同，均是房子與欄杆。圖5A說明標準陰影圖以常數深度偏移技術(深度偏移值le-3)所產生的測試場景，以避免錯誤的自身陰影(self-shadowing)問題。亦即，其在與真實表面(truesurface)比較之前便將深度偏移值加入深度採樣中。由於圖5A的深度偏移值過大，導致錯誤的"無陰影"(non-shadowing,看起來像是遮光物浮在光線接收物的上方)現象而使陰影后退太遠。實際上，直接地決定偏移值是非常難的，並且無法在每一個場景找出一個可接受的值。例如，圖5B說明標準陰影圖以常數深度偏移技術(深度偏移值le-6)所產生的測試場景。為了改善錯誤的"無陰影"現象而使用較小的深度偏移值(le-6),雖然改善了"無陰影"現象，卻產生了錯誤的"自陰影"(self-shadowing)問題(如圖5B所示)。圖5C是依照本發明實施例說明可重建幾何陰影圖所產生的圖形深度偏移測試場景。亦即，圖5C使用了上述本發明實施例所介紹的RGSM算法做為深度偏移問題的解決方案。圖5C的深度偏移值與圖5B相同，均是le-6。從圖5C可以很明顯看出，本發明實施例所使用的RGSM算法可以使用極小的深度偏移值，而不會產生錯誤的"自陰影"問題。綜上所述，本實施例可以保證像素級別的(pixel-wise)深度準確性，具有下列優點1.通過減低透視鋸齒與投影鋸齒，其可以產生精確的陰影邊緣。其更可以在動態場景中移除陰影邊緣"抖動"(jittering)現象。2.比起其他的陰影圖技術，本實施例可以具有很小的深度偏移值。通過設定單一且固定的偏移值，使用RGSM的程序設計者可以符合大部分應用的需求，並且產生正確圖像而避免錯誤的"自陰影，，(falseself-shadowing)或是錯誤的"無陰影"(falsenon-shadowing)問題。3.在相同輸出陰影品質與高速執行的前提下，其只使用標準陰影圖的少量存儲器空間。以上所述〗又為本發明較佳實施例，然其並非用以限定本發明的範圍，任何熟悉本項技術的人員，在不脫離本發明的精神和範圍內，可在此基礎上做進一步的改進和變化，因此本發明的保護範圍當以本申請的權利要求書所界定的範圍為準。附圖中符號的簡單說明如下A、B:紋理元素AR0、AR1、AR2、AR3:幾何陰影圖中的只於應區域P:測試<象素Pd:遮光點S110S140:依照本發明實施例說明可重建幾何陰影圖方法的各步驟權利要求1.一種可重建幾何陰影圖方法，其特徵在於，包括以一光源為觀察點，儲存一物體前表面的多個遮光幾何形的幾何信息；將一測試像素進行一致性測試，以從所述多個遮光幾何形中找出相對應於該測試象素的一遮光幾何形；重建一遮光點的深度值；以及完成該測試像素的陰影判斷。2.根據權利要求l所述的可重建幾何陰影圖方法，其特徵在於，所述幾何形包括三角形。3.根據權利要求l所述的可重建幾何陰影圖方法，其特徵在於，所述幾何信息包括所述幾何形的頂點坐標或幾何索引。4.根據權利要求l所述的可重建幾何陰影圖方法，其特徵在於，該測試-像素的坐標為(p.x，p.y,p.z)，而該一致性測試包括選擇所述幾何形其中之一；讀取所選4奪的該幾何形的幾何信息，該幾何信息中包括該幾4可形的頂點坐才示(v。.x,v。.y,v。.z)、(v!.x,v.y，v!.z)以及(v2.x,formulaseeoriginaldocumentpage2以求取該遮光點的重心坐才示^f直(Wi，w2,w3);依據該遮光點的重心坐標值(W!,W2,W3)判斷所選才奪的該幾何形是否為一致的；以及若所選擇的該幾何形判斷結果為一致的，則該幾何形為該遮光幾何形。5.根據權利要求4所述的可重建幾何陰影圖方法，其特徵在於，重建該遮光點的深度值包括計算等式formulaseeoriginaldocumentpage3,以求耳又該遮光點的深度值T.z。6.根據權利要求4所述的可重建幾何陰影圖方法，其特徵在於，重建該遮光點的深度值包括formulaseeoriginaldocumentpage3計算等式formulaseeoriginaldocumentpage3，以求耳又該遮光點的-果度Y直T.z。formulaseeoriginaldocumentpage37.根據權利要求4所述的可重建幾何陰影圖方法，其特徵在於，重建該遮光點的深度值包括計算等式T.zformulaseeoriginaldocumentpage3，以求耳又該遮光點的深度值T.z。8.根據權利要求l所述的可重建幾何陰影圖方法，其特徵在於，該遮光幾何形具有該遮光點；以該光源為觀察點，該測試像素與該遮光點重疊。9.根據權利要求l所述的可重建幾何陰影圖方法，其特徵在於，重建該遮光點的深度值需要利用該遮光幾何形的幾何信息以及該測試像素的位置信息。10.根據權利要求l所述的可重建幾何陰影圖方法，其特徵在於，完成該測試像素的陰影判斷是通過比較該遮光點的深度值與該測試像素的深度值。全文摘要本發明提供一種可重建幾何陰影圖方法。標準陰影圖提供了在場景中快速且合適的繪製陰影的方法。本發明提供了新的算法可重建幾何陰影圖，本發明通過使用了深度值而達成上述目標，此深度值是通過由幾何表面真實重建的，代替從深度貼圖點採樣的方法。同時，比起可以設定常數偏移值的大部分陰影圖技術，此可重建幾何陰影圖算法使用較小的深度偏移值而能產生正確的圖像而沒有錯誤的「自陰影」或錯誤的「無陰影」。本發明所述的可重建幾何陰影圖方法，通過減低透視鋸齒與投影鋸齒，可以產生精確的陰影邊緣。文檔編號G06T15/50GK101271588SQ20081009613公開日2008年9月24日申請日期2008年5月6日優先權日2007年10月26日發明者戴慶華,楊寶光申請人:威盛電子股份有限公司