一種樹葉漸進簡化方法
2023-06-04 06:04:16
專利名稱：：一種樹葉漸進簡化方法
技術領域：
：本發明屬於計算機圖形學與數字農林學相結合的交叉學科的
技術領域：
，涉及植物場景的繪製，尤其涉及一種樹葉漸進簡化方法。10
背景技術：
在城市可視化，電腦遊戲等應用中，往往涉及到許多室外場景，如果忽略隨處可見的植物的繪製，渲染結果會顯得非常不真實，這是計算機圖形學家和用戶都無法容忍的。而在植物建模以及植物生長模擬方面，人們早已展開深入的研究。到目前為止，已有許多成熟的系統，並有相15應軟體，例如法國的AMAP，加拿大的L-系統，德國的Xfrog等。這些軟體都能生成非常逼真的植物模型(見圖2)。但是植物，特別是樹木，通常由很多細枝還有數不清的葉子組成，並且枝和葉的拓撲結構都非常複雜。因此這類物體通常需要數量龐大的多邊形來進行描述。而繪製時間和物體的多邊形數量是正比關係，所以在目前的硬體條件下，實現這20類場景的實時繪製還是計算機圖形學中的一個難題。為了實現植物場景,特別是森林的實時繪製，人們陸續提出了各種算法。主要有基於圖像的繪製算法，點繪製算法和層次細節算法(LOD)。基於圖像的繪製算法通常在預處理中確定一系列採樣視點，在每一個視點方向，對植物體進行繪製，並把繪製結果作為紋理圖保存下來。25而在實時繪製時，根據當前視點信息，找到與其最鄰近的採樣視點，然後對這些採樣視點相對應的紋理圖像進行插值，插值得到的圖像即作為當前視點的渲染結果圖像。在所有算法中，這種算法繪製速度最快，且繪製時間與植物場景的幾何複雜度無關。但是這種方法需要很大的內存來存儲各採樣視點的紋理圖像，並且因為缺少植物的幾何信息，繪製近結果圖。點繪製算法是在對距離較遠的植物進行繪製時採取的一種策略當植物距離視點足夠遠時，它採用線表示枝條，而用點表示葉子，從而提高了繪製速度。對於近距離的植物，為保證渲染質量，則釆用它的原始5模型，即多邊形表示。因此點繪製算法只對距離較遠的植物的繪製有效，並且通常在對簡單矮小的植物，如草本植物，花卉等進行繪製，效果比較好，見圖4點繪製算法用於植物的結果圖。多邊形，特別是三角形模型一直是計算機圖形學的主流模型，因此人們在面片簡化方面研究很深入，提出了很多成熟的層次細節算法，如iovertexdecimation,edgecollapse,vertexclustering等。但由於樹木特殊的屬性，這些算法通常可以用於樹幹的簡化，對於樹葉部分，則會產生錯誤的結果。2002年，Remolar等人首次提出了針對樹葉的簡化算法一FSA算法。該算法能不斷減少用於表示樹葉的多邊形的數目，並同時保持樹冠外形。它假設樹葉由四邊形表示，然後不斷地進行leafcollapseis操作，即用一個新的四邊形代替原來的兩個四邊形，見圖5FSA算法中的leafcollapse示意圖，新產生的四邊形的面積大小和合併前的兩個四邊形的面積大小近似。採用該算法對樹模型進行簡化的結果，見圖6FSA算法結果圖。但FSA算法存在很多缺陷(l)不能保證leafcollapse中生成的四邊形的面積的正確性，會出現新生成的四邊形的面積比原四邊形20面積小的情況，這是不合理的。(2)只採用了兩項相似度指標，由它們選取的四邊形對經常相距很遠，並不適合做leafcollapse操作，因為它們會產生細長的四邊形。(3)FSA不是視點相關的算法，它不能明確得出當前視點下處於不同位置的樹木的細節層次。(4)FSA只能處理具有四邊形狀的葉子，而常見的樹葉的形狀一般都比四邊形複雜，因此FSA25應用範圍很局限。除了上面三種主要的方法，人們還試圖用別的方法實現實時的目的。例如最近有人在植物繪製中引入了幾何壓縮的方法。其中Pieire-MarieGandoin等人提出了一種無損壓縮算法，主要通過兩種常見的面片簡化操作edgecollapse和vertexsplit來改變點線面的拓撲連接關係，然30後對種拓撲連接關係的變化進行編碼。這種方法是漸進的，並能用於non-manifold的物體。該方法用於壓縮樹木時的結果，見圖7Pierre-MarieGandoin等人的壓縮方法的結果圖。但由於該壓縮方法不考慮植物特殊的拓撲結構，因此會產生視覺效果合理但違背植物學原理的結果。
發明內容常見的樹葉的形狀通常都比較複雜，而現有的樹葉簡化方法只能簡化四邊形狀的樹葉，應用範圍非常狹窄，另外現有方法不能根據視點自動選擇細節層次，為解決這些問題，本發明目的要解決的技術問題是如io何簡化各種樹木的樹葉部分，以建立樹葉的多解析度表示，以及繪製時如何選擇合適的解析度表示代替樹葉的完整表示，為此，本發明將要提供一種樹葉漸進簡化方法。為了實現上述目的，本發明提供一種樹葉漸進簡化方法，把描述複雜樹葉的面片分解成一組相互獨立的三角形或四邊形；然後迭代地對三15角形或四邊形葉片進行合併操作，即兩個四邊形，或兩個三角形，或一個四邊形一個三角形合併成一個新的四邊形，這個新的四邊形在位置，所佔空間以及顏色屬性與其所合併前的三角形或四邊形的相關屬性保持一致，因此能不斷地減少描述樹葉的多邊形的數目，但是在視覺效果上保持樹冠外形不變；而在每一次迭代中，通過六個相似度指標線性組成20的相似度函數，選取最相似最適合合併的兩個多邊形以減少誤差，保證簡化質量；簡化過程中所有的信息最終都保存在硬碟中，實時繪製時，則根據當前視點的信息和硬碟中的記錄確定不同位置的樹木的細節層次，並把相應的幾何信息送往CPU進行繪製。一、葉片合併和新葉片的構造25FSA算法提出了葉片合併的概念，即兩個四邊形合併成一個新的四邊形，並且這個新的四邊形與參與合併的兩個四邊形在顏色，空間位置等屬性上保持一致。但FSA只能對兩個四邊形進行合併操作，並且合併後生成的新的四邊形的不能保證其面積屬性的正確性。本方法繼承了FSA算法的所有優點，同時對它進行了推廣和改進，使其可以處理兩個30四邊形，或兩個三角形，或一個四邊形和一個三角形的合併操作，見圖8葉片合併示意圖。這樣就擴大了本方法的應用範圍，使它不僅能簡化四邊形形狀的樹葉，還能對其它形狀的樹葉進行簡化，如針葉狀葉子。合併過程中將生成一個新的四邊形來代替參與合併的兩個多邊形，本方法提出的確定該四邊形四個頂點的方法能避免FSA算法可能出現5的錯誤，更好的保持合併前後位置，面積等屬性的一致性，以保證更好的簡化效果。所述葉片合併中生成的新的四邊形的四個頂點的確定方法步驟包括首先在參與合併的兩個多邊形的所有頂點中找出距離最遠的兩個10頂點，分別記為頂點A和頂點B;總頂點數可以是6個(對應兩個三角形)，或7個(對應一個三角形和一個四邊形)，或8個(對應兩個四邊形)。然後再在剩餘的頂點中找出到頂點A，頂點B兩點距離之和最大的一個頂點，記作頂點C;15接著再在剩餘頂點中找出到頂點A、頂點B、頂點C三點距離之和最大的一個頂點，記作頂點D;隨後對頂點C，頂點D坐標進行變換調整，最終使得頂點A、頂點B、頂點C、頂點D處於同一平面上，這樣確定的四邊形就是共面的，不會出現扭曲的現象。20最後確定各頂點對應的法向量，其中頂點A、頂點B處的法向量保持原來的不變，而四邊形在頂點C、頂點D兩點的法向量需要原對應法向量經過同上的共面變換才能得到。二、相似度函數251描述樹葉的多邊形的屬性所述描述樹葉多邊形，是判斷兩個多邊形(四邊形或三角形)是否適合合併，本方法描述樹葉的多邊形的五種屬性為，分別為直徑，寬度，法向量，面積和合併年齡。所述描述樹葉多邊形的直徑和寬度，將一個多邊形的所有頂點記作30Z，d(;c,力表示兩頂點x和;;之間的Hausdorff(豪斯多夫)距離，則該多邊形的直徑定義為D(JQ=max(c/0，力;weI)而寬度定義為=maxW(Jc,力;;c，yeInd(x，力*Z)(I))5這兩個屬性描述了多邊形的大概形狀和各個頂點大致分布情況。所述面積記錄了對應多邊形的面積大小。所述法向量為對應多邊形所在平面的單位法向，它反映了多邊形的朝向，並且它和面積屬性一起反映了樹葉顏色在空間的分布情況。所述合併年齡，葉片合併操作前，將描述樹葉的多邊形稱之為原始10多邊形，則多邊形的合併年齡記錄了被該多邊形代替的原始多邊形的數目，即表示了在生成該多邊形的過程中，參與合併的原始多邊形的總數目，而原始多邊形的合併年齡設置為l。所述合併年齡通常和面積保持一致，一般來說，合併年齡大時，面積也會很大。152相似度指標根據以上定義的多邊形的五種屬性，本方法提出了六項相似度指標來分別判斷兩個多邊形在各屬性上的相似程度。這六項相似度指標包括法向相似度，空間位置的相似度，葉面積相似度，直徑相似度，合併年齡20相似度以及直徑懲罰。它們的含義和定義如下(1)法向相似度&衡量兩個多邊形的共面程度。表達式為S(w)=l-|〈W(X)，,|其中W(Z)和W(r)分別表示兩個多邊形的法向量，〈*,*〉求兩個向量的內積。這樣得到的S，(x,力的值會在0和1之間，並且兩多邊形越共面，S,(;c,力25的值越小。公式中的絕對值運算是必要的，因為葉子是兩面的，正反兩個方向都可以作為葉子的法向。(2)空間位置的相似度S2表示了兩多邊形之間距離的遠近程度。公式採用了Hausdorff(豪斯多夫)距離，並通過歸一化運算使得值域為[G，1]。具體公式如下30S2(義，J0-minW(A,A);A其中i^,為樹冠的直徑，即為樹葉包圍盒的直徑，因為它的值是兩個多邊形的最大可能距離值，所以用它來歸一化Hausdorff(豪斯多夫)距離可保證值域範圍為0，1。在葉片合併操作剛開始進行時，&(^)遠遠小於l，隨後會慢慢增大，並且&(l,:r)值越小，表明兩多邊形靠得越近。5(3)葉面積相似度S3衡量兩個多邊形的面積大小的接近程度。通常認為具有相近面積大小的兩個多邊形比面積大小相差很大的兩個多邊形更適合進行葉片合併操作。具體公式為&(m=[草)-草)]2/[草)2+單)2]其中J("，j(y)分別為兩個多邊形的面積大小。&(^的值同樣屬於10[O，l]範圍。(4)直徑相似度S4描述了葉片合併操作前後葉子形狀的變形程度。公式表示如下&(y)=1-+Z)(J)]/[2*D(Xy)]其中和Z)(y)分別表示兩多邊形的直徑值，這兩個多邊形合併後15會產生一個新的四邊形，該四邊形的直徑即為D(U)。根據前面提到的直徑的定義，設丄-X門y，則可得到Z)(U)-max^(x,力;x,3/e丄)。同樣S4(jr,:r)e(0,1)。(5)合併年齡相似度Ss，一個多邊形的合併年齡值代表著被它替代即簡化的原始多邊形的數目，通常認為將具有相近年齡的葉對更適合20合併，並且對年齡小的葉對應該比年齡大的葉對優先合併。綜合這兩個觀點，可得到下面的公式&(U)=[G(Z)+G(力+|G(X)_/W』其中G(Z)和G(力分別為兩多邊形的合併年齡。7V^為葉片合併操作進行前，描述所有樹葉的原始多邊形的數目，它的作用在於限定&(x,r)在(0,1)25範圍內取值。(6)直徑懲罰S6，先對尺寸小的葉對應該比尺寸大的葉對先合併，因為前者合併產生的誤差相對後者來說要小一些。具體公式如下其中D(Z)，Z)(y)和"^的含義和定義都與前面一致。^(X，J0的值也在30(O,l)範圍內。相似度函數根據以上六項相似度指標，本方法提出了一個相似度函數來衡量兩個多邊形的相似程度，從而在每次迭代中找出最適合進行葉片合併操作的5多邊形對。該相似度函數綜合了各項因素，並且給不同的因素賦予不同的權重，這樣就能更科學，更合理地選取多邊形對。而多邊形對的選擇直接關係到簡化質量，相對以往的樹葉簡化算法，本方法能夠取得更好，更準確的結果。相似度函數的具體表達式如下JO=(Z，y)+(X,J7)+A:3S3(X,JOio其中^>0,且*1+&+&+&+&+&=1。通過測試圖9相似度函數的係數取值實驗，當&=0.0375,/t2=0.3125，yfc3=0.0375，、=0.0375，A:5=0.2875和^=0.2875時，對常見的樹葉進行簡化時都能取得較好的結果。三、與視點相關的細節層次模型樹葉簡化過程是漸進的，並且每一步的信息都將保存在硬碟中。這15些信息包括多邊形的幾何數據信息，對應的屬性值，如多邊形的直徑，寬度等，還有簡化關係，如多邊形A和B合併後變成C(可認為C是A，B的父親，而A和B是C的兒子)。繪製時，則把這些記錄讀入內存，並根據當前視點的信息，來確定不同位置的樹木的細節層次。通常人們根據簡化誤差來確定物體的細節層次，但是對於樹葉這類特殊的物體，20計算葉片合併操作前後的誤差非常困難。為此本方法進行了簡化，採用多邊形的其中一個屬性值一直徑和用戶給定的象素誤差，代替簡化誤差以方便快捷地確定各樹木的細節層次。這種簡化是有合理的，因為繪製的最終結果是圖片形式，因此可知其細節層次的選擇和圖片大小彼此是相關的，而直徑的投影值可作為圖片大小的一個衡量值。給定一個像素25誤差，可由當前視點和待繪製的樹木的關係轉換得到空間誤差值，然後遍歷待繪製樹木的記錄，得到所有直徑不大於空間誤差即大小合適的樹葉，這些樹葉即為當前視點下需繪製的樹葉，並且一旦父葉被選中，它所有的子孫都不被送去繪製。圖l是本發明方法具體的流程2是現有技術AMAP、L系統和Xfrog生成的植物模型圖3是現有技術基於圖像的算法用於繪製森林時的結果圖圖4是現有技術點繪製算法用於植物的結果圖圖5是現有技術FSA算法中的Ieafcollapse示意圖圖6是現有技術FSA算法結果7是現有技術Pierre-MarieGandoin等人的壓縮方法的結果8是本發明葉片合併示意9是本發明相似度函數的係數取值實驗圖10是本發明簡化針葉的結果ll是本發明LOD模型圖12是簡化模型和原始模型的效果比較圖13a-d是利用本發明幾種常見樹木的樹葉簡化前後對比14是利用本發明森林場景的繪製結果圖具體實施方式下面將結合附圖對本發明加以詳細說明，應指出的是，所描述的實20施例僅旨在便於對本發明的理解，而對其不起任何限定作用。本發明方法的核心在於葉片合併方法和相似度函數的定義。它們直接影響著簡化質量。圖l給出了整個方法的流程，方法具體包括九個步步驟1:首先輸入三維樹模型，提取樹葉部分信息，並把這些信息25保存下來；步驟2:判斷樹葉的形狀是否為複雜，若是則執行步驟3;若否執行步驟4;步驟3:分解具有複雜形狀的樹葉，把描述複雜樹葉的面片分解成一組相互獨立的三角形或四邊形；30步驟4:計算所有多邊形對的相似度函數值；步驟5:找出最適合合併的多邊形對，即相似度函數值最小的多邊形對，這一對多邊形即認為是最相似，合併所產生的視覺誤差最小的兩個多邊形；步驟6:對多邊形對進行葉片合併操作，確定新產生的四邊形的四5個頂點的坐標位置；返回步驟4，並更新相似度，循環直至所有樹葉都合併到一個四邊形；步驟7:構成新生成的四邊形信息組；步驟8:構建樹葉的多解析度模型，保存樹葉簡化過程中的所有信息到硬碟中；10步驟9:實時繪製時，根據當前視點信息和簡化記錄，確定不同位置的樹木的細節層次，並把相應的幾何數據送往CPU，當視點改變時，重新確定各樹木的細節層次並重新繪製。一、實驗結果與結論用C語言實現了本發明所描述的方法，並用於了幾種常見樹木的樹15葉的簡化。所有的實驗都是在一臺P42.4G、512MB內存、作業系統為Windows2000的PC機上完成的，顯示部分使用了標準的OpenGL圖形函數庫。表l列出了實驗中所用到的所有樹木的信息，包括樹木的名稱，年齡，原始模型用來描述樹葉的多邊形的數目。20表l:實驗數據信息tableseeoriginaldocumentpage15附圖9為相似度函數的係數取值實驗結果圖。6項係數的取值直接影響著本樹葉簡化方法的質量和準確度。從圖中可以看出，當法向相似度)fc,取值很大時，會破壞樹葉的原始分布，產生極差的結果；當葉面積相似度係數*3起主導作用時，會生成許多變形的葉子；當直徑相似度系5數*4起主導作用時，會在樹冠的輪廓面上產生很大的葉子，因此不能保證樹冠外形不變;而當空間位置的相似度係數^，合併年齡相似度係數^以及直徑懲罰係數&起主導作用時，能取得很好的簡化效果，基本保持樹冠的形狀。通過該實驗，最終確定各係數的值為、=0.0375"2=0.3125，0.0375，yfc4=0.0375，0.2875，0.2875。10本方法推廣了FSA算法，應用範圍得到了擴展，可以簡化各種常見的樹葉，如具有三角形形狀的針葉。附圖10即是對一針葉模型一一棵高度為9.2461米的25歲樟子松的樹葉進行簡化的結果圖。該實驗中，樟子松到視點的距離為75.1414米。從左到右，第一幅圖為原始模型，後面五幅為簡化模型。圖片下面顯示了相應的樹葉多邊形的數目(第二行)、15壓縮模型後佔原數據的百分比(第三行)、以及壓縮率(第四行)。可以看出本方法的壓縮效果，並且壓縮率很高時，簡化結果依然能很好的保持樹冠的外形。附圖11給出了是一棵2.9米高的Makamik山楂樹的LOD模型。由近及遠，處於6個不同位置的山楂樹的細節層次不同。離視點遠越，20樹葉的細節越粗略，但卻能保持視覺效果。附圖l2為簡化模型和原始模型的視覺效果比較圖。釆用丁香樹模型。其中編號為1，3，5的模型為三個細節層次不同的簡化模型，簡化模型與模型的百分比分別為46.1%，63.8%和84.8%;而2，4，6為原始模型。為了比較簡化模型和原始模型的視覺效果，這些模型被分為了25三組，l和2為第一組，3和4為第二組，5和6為第三組。同組中的兩棵樹與視點的關係保持一致，並且這三組到視點的距離分別為78.43米，58.52米，38.56米。結果可見每一組中的兩棵樹具有相似的視覺效果。附圖13a-d為地中海白松，白楊樹，Siberian山楂樹和銀楓的簡化前後的對比圖。其中圖13a為地中海白松45歲，圖13b為白楊樹12歲，30圖13為Siberian山楂樹20歲，圖13d為銀楓15歲。圖中第一列為原始模型，第二列為簡化模型；在此，這四個模型的壓縮信息為各個簡化模型佔原模型百分比分別是2.38°/。，20%，10.7%和9.03%，對應的壓縮率分別是42.00，5.00，34和11.08。附圖14是對秋季花園裡的樹木進行繪製的結果圖。其中包括四種不5同的樹松樹，冬青樹，山楂樹和銀楓樹。並且除了冬青樹，其餘三種樹木的樹葉都不是四邊形表示的。本發明的方法有三處體現了特色和創新。一是處理複雜形狀的樹葉時，把描述樹葉的面片進行分解，產生一組相互獨立的三角形或四邊形;10二是提出了三角形對的合併，以及三角形，四邊形兩混合形體的合併方法；三是提出了一個全面考慮各種因素的相似度函數，能更科學，合理地選取待合併的葉對，提高簡化結果的質量。採用本發明的方法簡化樹木的樹葉，建立了樹葉的多解析度表示，以及繪製時選擇合適的解析度表示代替樹葉的完整表示，解決了現有技術樹葉簡化算法只能簡化四邊15形狀的樹葉，應用範圍非常狹窄，以及不能根據視點自動確定細節層次等問題。通過測試，本發明的方法確實能夠有效簡化具有不同形狀的樹葉，甚至花朵。它能不斷地減少樹葉的數目，同時保持樹冠外形不變。並且即使壓縮率很高時，仍能保持這一性質。而在實時繪製時，它能根據樹20木與當前視點的關係，自動確定該樹木合適的細節層次。主要用於城市可視化，園林設計，飛行模擬，虛擬實境和電腦遊戲中，以及輔助農林學家可視化其研究對象。上面的描述是用於實現本發明及其實施例，本發明的範圍不應由該25描述來限定。本領域的技術人員應該理解，在不脫離本發明的範圍的任何修改或局部替換，均屬於本發明權利要求來限定的範圍。權利要求1、一種樹葉漸進簡化方法，其特徵在於面片分解步驟把描述複雜樹葉的面片分解成一組相互獨立的三角形或四邊形；葉片合併步驟迭代地對三角形或四邊形葉片進行合併操作，合併成一個新的四邊形，新的四邊形在位置、所佔空間以及顏色屬性與其所取締的三角形或四邊形的相關屬性保持一致，能不斷地減少描述樹葉的多邊形的數目，而在視覺效果上保持樹冠外形不變；相似度處理步驟在每一次迭代中，通過六個相似度指標線性組成的相似度函數，選取最相似、最適合合併的兩個多邊形；實時繪製步驟根據當前視點的信息和硬碟中的記錄確定不同位置的樹木的細節層次，把相應的幾何信息送往CPU進行繪製。2、如權利要求l所述樹葉漸進簡化方法，其特徵在於所述葉片合15並中生成的新的四邊形的四個頂點的確定方法步驟包括在參與合併的兩個多邊形的所有頂點中找出距離最遠的兩個頂點，分別記為頂點A和頂點B;在剩餘的頂點中找出到頂點A，頂點B兩點距離之和最大的一個頂點，記作頂點C;20在剩餘頂點中找出到頂點A,頂點B，頂點C三點距離之和最大的一個頂點，記作頂點D;對頂點C,頂點D坐標進行共面變換調整，使得頂點A、頂點B、頂點C、頂點D處於同一平面上，即使新生成的四邊形共面；最後確定各頂點對應的法向量，其中頂點A、頂點B處的法向量保25持原來的不變，四邊形在頂點C、頂點D兩點的法向量需要頂點C、頂點D原對應法向量經過所述的共面變換得到。3、如權利要求1所述樹葉漸進簡化方法，其特徵在於所述葉片合併，對於兩個三角形，總頂點數選擇6個。4、如權利要求1所述樹葉漸進簡化方法，其特徵在於所述葉片合30並，對於一個三角形和一個四邊形，總頂點數選擇7個。5、如權利要求1所述樹葉漸進簡化方法，其特徵在於所述葉片合併操作，對於兩個四邊形，總頂點數選擇8個。6、如權利要求1所述樹葉漸進簡化方法，其特徵在於所述描述樹葉多邊形，是判斷兩個多邊形是否適合合併，描述樹葉多邊形的屬性分5別為直徑、寬度、法向量、面積和合併年齡。7、如權利要求6所述樹葉漸進簡化方法，其特徵在於所述描述樹葉多邊形的直徑和寬度，將多邊形的所有頂點記作X，d(x,力表示兩頂點;c和y之間的豪斯多夫距離，則該多邊形的直徑定義為Z)(I)=max(d0，力;x,>'eZ)io而寬度定義為『(義)=max(c/0,力;;c,:FeJTnd(;c,力#Z)(X))所述樹葉多邊形直徑、寬度的描述了多邊形的大概形狀和各個頂點大致分布情況。8、如權利要求6所述樹葉漸進簡化方法，其特徵在於所述面積，15是記錄對應多邊形的面積大小。9、如權利要求6所述樹葉漸進簡化方法，其特徵在於所述法向量為對應多邊形所在平面的單位法向，它反映多邊形的朝向，並且它和面積屬性一起反映了樹葉顏色在空間的分布情況。10、如權利要求6所述樹葉漸進簡化方法，其特徵在於所述合併20年齡，在葉片合併操作前，將描述樹葉的多邊形稱之為原始多邊形，則多邊形的合併年齡記錄被該多邊形代替的原始多邊形的數目，所述數目表示在生成該多邊形的過程中，參與合併的原始多邊形的總數目，原始多邊形的合併年齡設置為l。11、如權利要求10所述樹葉漸進簡化方法，其特徵在於所述合併25年齡通常和面積保持一致。12、如權利要求1所述樹葉漸進簡化方法，其特徵在於所述相似度，根據多邊形的屬性和相似度指標分別判斷兩個多邊形在各屬性上的相似程度，相似度指標包括法向相似度、空間位置的相似度、葉面積相似度、直徑相似度、合併年齡相似度以及直徑懲罰。3013、如權利要求12所述樹葉漸進簡化方法，其特徵在於所述法向相似度Si，法向相似度Si衡量兩個多邊形的共面程度，其表達式為-其中iv(;n和iv(r)分別表示兩個多邊形的法向量，〈*,*〉求兩個向量的內積；得到S,(x,力的值在0和1之間，並且兩多邊形越共面，S,(;c，力的5值越小。14、如權利要求12所述樹葉漸進簡化方法,其特徵在於所述空間位置的相似度S2，用空間位置的相似度S2表示兩多邊形之間距離的遠近程度，基於所述豪斯多夫距離，並通過歸一化運算使得值域為[G，U，其表達式為formulaseeoriginaldocumentpage4其中D^為樹冠的直徑，用來做歸一化處理。15、如權利要求12所述樹葉漸進簡化方法，其特徵在於所述葉面積相似度S3，葉面積相似度衡量S3兩個多邊形的面積大小的接近程度，相近面積大小的兩個多邊形比面積大小相差很大的兩個多邊形更適合進15行葉片合併操作，其表達式為w)=[単)-,)]2/[草)2+,)2]其中j(z)，力oo分別為兩個多邊形的面積大小，&(^)的值同樣屬於[O，l]範圍。16、如權利要求12所述樹葉漸進簡化方法，其特徵在於所述直徑20相似度S4，直徑相似度S4描述葉片合併操作前後葉子形狀的變形程度，其表達式為-s4(z,r)=1-[Z)(Z)+網]/[2*y)]其中和Z)(y)分別表示兩多邊形的直徑值，這兩個多邊形合併後產生一個新的四邊形，該四邊形的直徑即為D(u);根據所述的直徑，25設i:-義ni7，得到Z)(U)-max(dO，力;;c,:^丄)，同樣&(U)e(0,1)。17、如權利要求12所述樹葉漸進簡化方法，其特徵在於合併年齡相似度Ss，將具有相近年齡的葉對進行合併，並且對年齡小的葉對比年齡大的葉對優先合併，其表達式為formulaseeoriginaldocumentpage430其中g(JO和g(力分別為兩多邊形的合併年齡，a^^為葉片合併操作進行前，描述所有樹葉的原始多邊形的數目，它的作用在於限定&(U)在(O,l)範圍內取值。18、如權利要求12所述樹葉漸進簡化方法，其特徵在於所述直徑懲罰S6，先對尺寸小的葉對合併，再對尺寸大的葉對合併，其表達式為&(")=,)+網]/[21]&(X,y)的值在(0,1)範圍內。19、如權利要求12所述樹葉漸進簡化方法，其特徵在於所述相似度函數，根據相似度指標，來衡量兩個多邊形的相似程度，從而在每次迭代中找出最適合進行葉片合併操作的多邊形對，該相似度函數綜合了各項因素，並且給不同的因素賦予不同的權重，S6其表達式為y)=&(x,r)+(義,;r)+(x,+、&(z,+W(")+AA(x,:r)其中^>0，且A;,+A;2+A:3+A:4+A5+A:6=1。20、如權利要求1所述樹葉漸進簡化方法，其特徵在於所述與視點相關的細節層次模型，將樹葉簡化過程的每一步信息保存在硬碟中，繪製時，把樹葉簡化過程記錄讀入內存，並根據當前視點的信息，確定不同位置的樹木的細節層次，採用多邊形的其中一個屬性值一直徑和用戶給定的象素誤差確定各樹木的細節層次，繪製結果為圖片形式，其細節層次的選擇和圖片大小彼此相關，用直徑作為圖片大小的一個衡量值；給定一個像素誤差，由當前視點和待繪製的樹木的關係轉換得到空間誤差值，然後遍歷待繪製樹木的記錄，得到所有直徑不大於空間誤差即大小合適的樹葉，這些樹葉即為當前視點下需繪製的樹葉，並且一旦父葉被選中，它所有的子孫都不被送去繪製。21、如權利要求1所述的樹葉漸進簡化方法，其特徵在於所述葉片合併和相似度處理具體步驟包括步驟1:首先輸入三維樹模型，提取樹葉部分信息，並把這些信息保存下來；步驟2:判斷樹葉的形狀是否為複雜，若是則執行步驟3;若否執行步驟3:分解具有複雜形狀的樹葉，把描述複雜樹葉的面片分解成一組相互獨立的三角形或四邊形；步驟4:計算所有多邊形對的相似度函數值；步驟5:找出最適合合併的多邊形對，即相似度函數值最小的多邊5形對，這一對多邊形即認為是最相似，合併所產生的視覺誤差最小的兩個多邊形；步驟6:對多邊形對進行葉片合併操作，確定新產生的四邊形的四個頂點的坐標位置；返回步驟4，並更新相似度，循環直至所有樹葉都合併到一個四邊形；10步驟7:構成新生成的四邊形信息組；步驟8:構建樹葉的多解析度模型，保存樹葉簡化過程中的所有信息到硬碟中；步驟9:實時繪製時，根據當前視點信息和簡化記錄，確定不同位置的樹木的細節層次，並把相應的幾何數據送往GPU，當視點改變時，15重新確定各樹木的細節層次並重新繪製。全文摘要本發明公開一種樹葉漸進簡化方法，通過迭代地合併葉片多邊形，並使新四邊形葉片保持被其取締的葉對的形狀、顏色等屬性，而每一次迭代採用六項有權重的相似度指標選取最合適的葉對做合併操作；對於複雜葉片，則先將葉片分解成一組三角或四邊形，然後再進行合併操作；整個葉片減化過程在預處理完成並存在硬碟中，實時繪製時根據視點離樹木的距離，選擇合適的細節層次代替樹葉的完整的描述。本發明能有效簡化不同形狀的樹葉、花朵，在簡化過程中保持樹冠外形不變。並且即使壓縮率很高時，仍能保持冠層的形狀。主要用於城市可視化，園林設計，飛行模擬，虛擬實境和電腦遊戲中，以及輔助農林學家可視化其研究對象。文檔編號G06T15/10GK101114383SQ20061009957公開日2008年1月30日申請日期2006年7月28日優先權日2006年7月28日發明者張曉鵬,鄧擎瓊申請人:中國科學院自動化研究所