一種基於視域剔除的複雜室內場景快速繪製方法

2023-06-04 23:18:11

專利名稱：：一種基於視域剔除的複雜室內場景快速繪製方法
技術領域：
：本發明涉及圖形處理和虛擬實境，主要是一種場景圖形引擎快速繪製方法，特別是一種基於室內場景圖結構的圖形引擎快速繪製方法。
背景技術：
：由於計算機繪製的場景日益複雜，為了達到實時的效果，對計算機軟硬體的要求只會越來越高，它要求採用先進的繪製算法來對複雜的場景進行規劃和管理，對場景管理算法進行優化，加快繪製場景的速度，通常圖形質量與計算量是成正比的，計算量越大，圖形的質量也就越好，然而考慮到虛擬實境中實時性的要求，所以不得不在這兩者中均衡考慮，在滿足視覺效果的同時，儘量加快繪製的速度。目前用來加速場景繪製的主要技術有層次細節算法，基於圖像的繪製算法等快速繪製算法，層次細節算法的核心思想是在不影響畫面視覺效果的前題條件下，根據視點距離，逐步簡化場景表面細節來提高繪製的效率。但層次細節LOD轉換時的圖像跳躍比較大，是一種離散的，在離散/連續方面非常欠缺。基於圖像繪製算法利用二維圖像信息來表達和繪製虛擬場景，利用這種方法會有較好的真實感和實時性，因為它來自真實的照片，具有真實感強的圖像，但是它的缺點是缺少交互性。對於一個虛擬實境系統來說，不僅有室外場景，還有相當一部分的室內場景，室內場景通常都有一個特性——場景內部模型相當複雜，並且從觀測者的視點看去只能看到他所處環境內的物體，除非在這個環境中有其它入口可以通往其它環境。由於室內場景的複雜，運用LOD肯定是不現實的，因為都是近距離的模型，而基於圖像的繪製的算法也不能從根本上解決加速繪製的要求，一般針對這樣的室內環境都是運用創建樹結構，但樹結構是相當低效的，因為通過入口觀測者只能看到相鄰環境中非常小的一部分物體。換句話說，樹結構不能很好的處理既有高複雜度又有高阻光度的場景。這個問題常常被稱為"無效渲染"，會花費大量的時間去渲染最終被一堵牆擋住的相鄰房間中的物體。
發明內容本發明的目的在於提供一種基於視域剔除的複雜室內場景快速繪製方法，能大為提高在繪製室內場景時的繪製速度，保證虛擬實境的實時性要求。為達到上述目的，本發明的構思是克服現有圖形引擎快速繪製技術，尤其是在繪製室內場景時的速度不夠，提供了一種基於視域剔除的複雜室內場景快速繪製方法，它考慮了室內場景與室外場景的區別與特點，大大提高了在繪製室內場景時的繪製速度，保證了虛擬實境的實時性要求。根據上述發明構思，本發明採用的技術方案是一種基於視域剔除的複雜室內場景快速繪製方法，其特徵在於首先將場景劃分成區域，用portal入口把相鄰的區域連接起來，再確定視點所在的位置，將該區域模塊所包含的所有幾何模塊與視錐體進行相交檢測，然後進行視域剔除工作，實現複雜室內場景的快速繪製；具體操作步驟如下(1)採用'凸'多邊形作為劃分區域的最小單位；(2)用portal入口把相鄰的區域連接起來；(3)確定視點所在的位置，將攝像機的空間坐標與所有區域依次進行相交判斷，由此確定視點處於哪個區域模塊中；(4)將該區域模塊所包含的所有幾何模塊與視錐體進行相交檢測，完成視域剔除工作；(5)計算可視範圍內的所有Portal,按Portal大小和視點方向重新計算新的視錐體，並與該Portal相連的區域模塊內利用計算的視錐體進行新一輪的視域剔除；如此遞歸下去，直到所有的可視區域模塊都完成了視域剔除，如此獲得的所有幾何節點形成的序列就是需要進行渲染的節點。所述的步驟(1)中的採用'凸'多邊形作為劃分區域中的最小單位中的'凸'表示在區域內的任意兩點間畫一條線段，這條線段不會穿透該區域的任何一個多邊形，而閉合表示從區域內發出一條光線，如果要讓光線射到區域外，則此光線必須要穿透某個區域的多邊形。所述的步驟(2)中的portal入口表示為兩個區域模塊相連接部分的位置和大小。所述的步驟(5)中的按Portal大小和視點方向重新計算新的視錐體，這裡會出現兩種情況，Portal完全/部分處於原視錐體範圍內部，如果完全處於原視錐體內部，那麼只要計算由Portal產生的視錐體為新的視錐體，如果部分處於原視錐體內部，那麼在內部以Portal產生的視錐體為準，而超出原視錐體的部分還是按照原視錐體的邊界進行計算所得。本發明有益的效果是採用Portal入口技術對複雜的室內場景進行管理，基於視域剔除，使得在模型複雜的場景內無需渲染場景中的每個物體，這樣大大提高了渲染了效率，很好的設計了Portal入口，cell區域的數據結構體，而避免了用樹結構產生的"無效渲染"提高內存利用率。圖l本發明的方法流程圖。圖2Portal模型結構圖。圖3視錐體計算示意圖1。圖4視錐體計算示意圖2。圖5測試效果圖。具體實施例方式本發明的一個優選實施例結合如下本複雜室內場景快速繪製方法，共分五步第一步將整個場景劃分成n個區域如圖1所示，在入口技術的概念中整個場景被劃分n個區域(cell)，每個區域都是一個閉合的凸多邊形，這裡"凸"表示在區域內的任意兩點間畫一條線段，這條線段不會穿透該區域的任何一個多邊形，而閉合表示從區域內發出一條光線，如果要讓光線射到區域外，則此光線必須要穿透某個區域的多邊形.因此可以形象地把一個區域看成是一個房間，區域的多邊形構成了房間的牆壁、天花板和地板等(如果要描述一個"凸"的房間，需要將這個房間劃分成若干個"凸"區域，然後用入口將它們連接起來)。兩個鄰近的區域通過入口連接。第二步cell區域結構設計Cdl模塊的劃分是由美工前期確定的，劃分有兩個主要條件，一是模塊內部不能有牆或者其他遮擋體形成較大範圍的遮擋，二是該模塊的形狀必須是凸多面體，而所有的幾何節點將以其所在位置和包圍盒信息對號入座至相應的Cell模塊，兩個Cell模塊將通過窗或門結構進行連通，每個房間就是一個Cell模塊，而連接房間與房間之間的門(窗)就是Portal。在視域剔除前我們就假定所有當前Cell模塊(視點處於的那個Cdl模塊)中的幾何節點都是可見的，而相鄰的Cell模塊中只用那些處於門窗可視範圍內的幾何節點才可見，不相鄰的Cell模塊中的所有幾何節點均不可見。本發明中，設計的Cell數據結構如下ClassCellwstringmName;TPortalListmPortals;TNodeListmNodes;TOBBListmBoxes;boolmlsVisualize;}其中mName是該模塊的名字，也就是引擎中的標識號，mPortals記錄了屬於這個模塊的所有Portal結構，mNodes記錄了位於模塊中的所有幾何節點的信息，mBoxes記錄的是組成這個Cell的所有OBB的序列，由於Cdl其實就是一個個房間，而房間不一定是方方正正的，所以有些情況下需要用多個OBB才能準確的描述一個Cdl，mBoxes就是用來記錄這些OBB的。最後一個布爾變量mlsVisualize是用來記錄該Cell是否可見的。第三步Portal結構設計Portal模型結構如圖2所示，這裡將Portal抽象成一個平面的長方形，所以在數據結構中只要記錄其中心坐標，兩個軸役及軸向長度即可，通過這些參數我們可以計算出Portal四個頂點的坐標值^二屍c-A0H0-^(1)B=Pc+A;030-(2)C=《+A;0H0+(3)=屍c一V^o+(4)式中Pc代表模型的中心坐標mCenter，巧代表兩個方向向量，k代表方向向量上的長度。Portal是從屬於Cell模塊的，也就是說每個Portal有且僅有一個Cell模塊作為其父節點。由於一般來說牆面是有厚度的，所以對於一個連接通道而言在牆的正反面需要兩個Portal,而這兩個Portal模塊就各自需要一個指向對方的指針來說明其連接情況，當然還要考慮到有些時候門窗關閉的情況，我們需要有一個變量來說明Portal的狀態。主要數據結構如下所示ClassPortalTVector3mCentersTVector3mAxes[2];TVector2mExtents;TCdl*mCell;TPortal*mAdjacent;boolmOpen;其中mCenter記錄空間位置的坐標，mAxes記錄兩個方向向量，利用一個二維向量mExtents記錄兩個方向向量上的長度值，mCdl記錄所屬Cell模塊的指針，mAdjacent記錄的是相連的Portal的指針，最後一個布爾向量記錄該Portal得閉合情況。第四步新視錐體生成算法新視錐體的生成分為兩種情況第一種情況是整個Portal完全處於原視錐體範圍內部，在這種情況下，新的視錐體其實就是將原視錐體變窄後的模樣如圖3所示圖中O點代表的是視點(假設視點處於原點上)，粗線條代表的是牆，牆上的缺口就是Portal,可以理解為門或者窗，ABCD表示的是原視錐體，但是對O點來說牆後的物體是不可見的，所以連接OF和OP分別交AD於E點和H點，作FG平行於BC，這樣一個新的視錐體FGHE就生成了，FG為新視錐體的近平面，HE為新視錐體的遠平面，三個方向軸不變。對於O點來說，處於牆另一側的物體只有處在這個新的視錐體內才是可見的。新視錐體將通過如下步驟求得1.首先計算Portal的四個頂點到原視錐體近平面BC的最小距離，也就是求出各點指向B點的向量，然後求出這些向量與BC平面法向量的內積，取出其中的最小值，由圖上可知最後求得的點是F點，最短距離為IK線段所代表的長度，具體公式如下(以F點為例)D=(^3-涼)"(5)式中和^分別代表原點指向B點和F點的向量，巧代表平面法向量。2.由於視點未改變所以新視錐體的三個方向向量以及中心點坐標與原視錐體完全相同，而新的近平面距離(mNear)就等於原近平面距離加上上一步求得的最小值(IK)，遠平面(mFar)距離值保持不變和原值相同。3.新視錐體的左值(mLeft)即圖中FI線段的長度，可以將OF向量內積mAxesO的負向量求得。4.新視錐體的右值(mRight，圖中IG線段長度的)的求解相對複雜，首先需要求得F點和G點在mAxes2向量方向上的差值，然後求得OG在mAxes0向量方向上的投影，利用相互比例進行求解，具體公式如下/G=(^S"0)x(/"a^)/(/"<9"^"2)(6)式中巧。和巧2分別代表mAxes0和mAxes2這兩條向量5.由於圖是俯視圖所以豎直向量無法在圖中表示，但利用同樣的方法可以求得上值(mTop)和下值(mBottom)。第二種情況是Portal部分處於原視錐體範圍內部，在這種情況下，新的視錐體的形狀相當於原視錐體的側邊半部中的一小部分，如圖4是一個新視錐體計算的示意圖此圖和第一種情況唯一的不同是牆面向左平移了一段距離，部分Portal位於視錐體外側，像這樣的情況我們首先連接OP交AD於E，在P點做BC的平行線交AB於G，四邊形AGPE就是新的視錐體，且視點和三個方向向量和原視錐體保持一致。新視錐體通過如下方法可以計算獲得1.首先計算處在視錐體內的Portal頂點到原視錐體近平面BC的距離，由圖上可知需要求解距離的點是P點，最短距離為IP線段所代表的長度，具體公式如下(以P點為例)z)=(^i-5)"(7)式中和分別代表原點指向B點和P點的向量，巧代表平面法向量。2.這一步和第一種情況相同，新的近平面距離(mNear)就等於原近平面距離加上上一步求得的最小值(IP)，遠平面(mFar)距離值保持不變和原值相同。3.新視錐體的右值(mRight)即圖中KI線段長度的負值，可以將OP向量內積mAxesO向量求得(求得直接為負值)。4.由圖上可知新視錐體與原視錐體共用一條左邊，所以他們的左值是相同的，即新視錐體mLeft就等於原視錐體mLeft。5.由於圖是俯視圖所以豎直向量無法在圖中表示，但利用同樣的方法可以求得上值(mTop)和下值(mBottom)。第五步根據生成的新視錐體渲染頂點利用計算的視錐體進行視域剔除，直到所有的可視Cell模塊都完成了視域剔除，如此獲得的所有幾何節點形成的序列就是需要進行渲染的節點。這時渲染的頂點比處理前頂點的個數要少了很多很多，因為有很多頂點都由於Portal產生的視錐體進行了視域剔除而被排除在渲染之外，從而大大提高渲染效率。實驗結果本實驗在vc.net的編譯環境下使用Direct3D渲染某室內場景，按照上述方法場景管理。測試平臺如下表所示表5.1測試平臺tableseeoriginaldocumentpage9基於上述硬體平臺我們對於一個有110個節點、14個Cell模塊、20個Portal模塊的場景進行測試。測試結果對比示於表5.2。表5.2不同情況下渲染速度的比較tableseeoriginaldocumentpage9從測試數據中不難發現，遮擋率越高越能體現Portal算法的優越性，如表第三行所示，在高遮擋的情況下，渲染幀數竟然有2.5倍的提升，使渲染效率有了質的飛躍。測試效果圖如圖5所示。實驗結果表明，本發明的一種基於視域剔除的複雜室內場景快速繪製方法，克服現有圖形引擎繪製技術、尤其是在繪製室內場景時的速度不夠的缺點，提供了一種基於視域剔除的複雜室內場景快速繪製方法，大大提高了在繪製室內場景時的繪製速度，保證了虛擬實境的實時性要求。權利要求1.一種基於視域剔除的複雜室內場景快速繪製方法，其特徵在於首先將場景劃分成區域，同用Portal入口把相鄰的區域連接起來，再確定視點所在的位置，將該區域模塊所包含的所有幾何模塊與視錐體進行相交檢測，然後進行視域剔除工作，實現複雜室內場景的快速繪製；具體操作步驟如下a.採用『凸』多邊形作為劃分區域的最小單位；b.用portal入口把相鄰的區域連接起來；c.確定視點所在的位置，將攝像機的空間坐標與所有區域依次進行相交判斷，由此確定視點處於哪個區域模塊中；d.將該區域模塊所包含的所有幾何模塊與視錐體進行相交檢測，完成視域剔除工作；e.計算可視範圍內的所有Portal，按Portal大小和視點方向重新計算新的視錐體，並與該Portal相連的區域模塊內利用計算的視錐體進行新一輪的視域剔除；f.如此遞歸下去，直到所有的可視區域模塊都完成了視域剔除，如此獲得的所有幾何節點形成的序列就是需要進行渲染的節點。2.根據權利要求1所述的基於視域剔除的複雜室內場景快速繪製方法，其特徵在於所述的步驟(1)中的採用'凸'多邊形作為劃分區域中的最小單位中的'凸'表示在區域內的任意兩點間畫一條線段，這條線段不會穿透該區域的任何一個多邊形，而閉合表示從區域內發出一條光線，如果要讓光線射到區域外，則此光線必須要穿透某個區域的多邊形。3.根據權利要求1所述的基於視域剔除的複雜室內場景快速繪製方法，其特徵在於所述的步驟(2)中的portal入口表示為兩個區域模塊相連接部分的位置和大小。4.根據權利要求1所述的基於視域剔除的複雜室內場景快速繪製方法，其特徵在於所述的步驟(5)中的按Portal大小和視點方向重新計算新的視錐體，這裡會出現兩種情況，Portal完全/部分處於原視錐體範圍內部，如果完全處於原視錐體內部，那麼只要計算由Portal產生的視錐體為新的視錐體，如果部分處於原視錐體內部，那麼在內部以Portal產生的視錐體為準，而超出原視錐體的部分還是按照原視錐體的邊界進行計算所得。全文摘要本發明涉及一種基於視域剔除的複雜室內場景快速繪製方法。本方法首先把整個場景劃分成n個區域，用portal入口把相鄰的區域連接起來，再確定視點所在的位置，將該區域模塊所包含的所有幾何模塊與視錐體進行相交檢測，完成視域剔除工作，最後計算可視範圍內的所有Portal，計算新視錐體，並進行新一輪的視域剔除，如此遞歸下去，得到最終需要渲染的節點。實驗結果表明，採用本發明的室內場景管理方法，在室內遮擋率高時，能夠大大提高渲染效率。文檔編號G06T15/10GK101419721SQ20081020198公開日2009年4月29日申請日期2008年10月30日優先權日2008年10月30日發明者歡丁,萬旺根,餘小清,周俊瑋申請人:上海大學