大規模室內場景入口技術

楊玉婷，康厚良

(云南大學旅游文化學院信息科學與技術系，云南麗江 6 74100)

隨著3D虛擬環境規模的不斷增大、用戶對3D場景渲染質量要求的不斷提高，如何在短時間內渲染具有高分辨率的高質量場景一直是大規模虛擬場景渲染追求的目標。而快速、高質量的場景渲染與可見性計算是密不可分的。可見性計算(visibility culling)指的是，對于給定的場景和觀察視點，通過對遮擋關系進行快速判斷，扔棄大量不需要繪制的圖形對象，降低場景的復雜程度，增加整個場景的真實感，最終實現低負荷繪制與網絡傳輸［1-16］。但是，由于計算精確的可見性集(exact visibility set，EVS)過于復雜，因此大多數的算法都偏向于計算潛在的可見性集(potential visibility set，PVS)。PVS是對EVS的一種保守預測，目的是將所有潛在可見的(即使是目前暫時不可見的)對象都包含在PVS中。

從20世紀70年代開始就提出了各種用于解決可見性計算的方法，其中包括隱藏面消除(HSR)和視錐篩選(view-frustum culling)算法等等。隱藏面消除算法可有效避免對幾何體中不可見面(幾何體的背面)的渲染，而視錐篩選算法則避免了對視錐范圍以外的幾何體的渲染［1］，具體如圖1所示。但是，值得注意的是，雖然HSR和視錐篩選在一定程度上幫助引擎減少了大量的不可見的多邊形和物體，但是對場景中的每一個物體，甚至是對每個物體中的每個多邊形進行可見性計算，其工作量過大，不適于大規模場景PVS的計算，因此，希望能使用一種算法先對場景中大量不可見的物體進行一個粗略的快速剔除，然后再利用HSR和視錐篩選算法細化，從而提高可見性計算的速度。為了實現這一目的，現在主流的有2種處理方法:入口(portal)算法和層次細節(level of detail，LOD)算法［17］。入口算法主要適用于計算大規模室內場景的PVS，而LOD算法適用于大規模室外場景。因此，對適用于大規模室內環境的入口技術進行系統的探究和比較是十分重要的。

圖1 隱藏面消除、視錐篩選和遮擋裁減算法

1 基于入口的可見性算法

大規模室內場景一般由各種房間、走廊、樓梯以及連接它們的門、窗戶等部分組成，當用戶處于其中的某個房間時，很大程度上是無法看到其他房間中的物體的，因此，通過使用基于入口的可見性算法能將不可見的房間以及房間中所包含的物體快速剔除。

基于入口的可見性算法是一種來自于區域的可見性算法(from region visibility)。根據大規模室內場景的結構特點，可以將室內場景劃分為單元(cell)和入口(portal)。一般將房間、走廊、樓梯等作為單元，而連接它們的門和窗戶等作為入口，劃分效果如圖2所示。圖2為由若干房間組成的室內場景，可將場景劃分為6個單元，黑色粗實線表示各單元的邊界，而灰色實線表示連接不同單元的入口，并且只有當入口處于打開狀態時，相鄰房間中的物體才可見。因此，當觀察者處于某一單元中時，只有與該單位相鄰的若干單元是可見的，從而將場景中大量不可見的單元剔除掉。

2 入口算法解析

對入口算法的研究包括對傳統入口(conventional Portals)的研究和對任意入口(arbitrary Por-tals)的研究。傳統入口的研究主要著眼于入口在可見性計算和裁剪方面的特點，因此，為了便于單元的渲染，一般都限制入口必須是凸多邊形，且只能位于單元邊界上等。而任意入口則突破了傳統入口的限制，注重對更一般化的入口的研究，強調入口除了具有加速可見性計算和裁剪的功能外，還可以作為連接任意獨立單元的連接工具，并且入口的形狀可以是任意幾何體，可處于單元的任意位置。

圖2 由若干房間組成的室內場景的單元劃分

2.1 基于傳統入口的可見性計算

根據實現方法的不同，基于傳統入口的可見性計算可分為基于單元-單元(cell-to-cell)的可見性計算及渲染和基于材質(texture based)的入口渲染。基于單元-單元的可見性計算及渲染從室內場景的結構出發，當視點所在單元中的入口可見時，與該入口相連接的鄰接單元可見，然后再將該可見的相鄰單元作為當前單元，判斷該單元中是否存在可見入口和其他相鄰單元。如果入口不可見，則該入口及與它相連的鄰接單元都將全部被剔除。該算法采用的是線性遞歸的方式。而基于材質的入口渲染是將與該入口相連的單元在不同視點角度的渲染圖片事先存儲起來，當該入口可見時，根據當前視點的位置將對應圖片填充到入口上的方法。該方法避免在運行時圖形引擎對相鄰單元的可見性計算和渲染。

2.1.1 基于單元-單元的可見性計算及渲染

Jones［13］作為傳統入口研究的先驅，提出了在建筑物中利用場景劃分來加速可見性計算的理論。在預處理階段，Jones利用凸多邊形入口(convex polygon portal)手動地將室內場景劃分為單獨的凸多面體區域(convex polyhedral regions);然后，在運行時，利用單元鄰接信息和入口的可見性來快速判斷多邊形的可見性。但是，當場景中包含了大量的多邊形時，該方法將變得不實用。

Airey［7-8］和 Teller 等［2］在 Jones 的基礎上對基于入口的可見性計算做了很多基礎工作。Airey提出了2種不同的方法用于計算PVS，同時還提出了一種算法，用于判斷每個入口所指定的模型中的多邊形是否可見。該算法的時間復雜度為O(n3)。另外，還給出了幾種采樣方法，但這些采樣方法均使用“輻射度(ray-shooting)”探尋法來判斷用戶指定區域中的幾何體的可見性，因此無法保證可見性計算結果的完整性。

Teller等［2］在其論文中根據大型室內場景的特點，提出了入口和單元的空間劃分(spatial subdivision)方法，以及基于單元的可見性計算方法。入口和單元的空間劃分思路是:利用BSP樹(binary space partitioning tree，二元空間劃分樹)將室內場景劃分為凸單元(convex cell)，一些不透明的表面，例如墻面等被作為劃分的分隔物，并最終作為單元的邊界，更小的細節場景元素在這一階段的處理中被忽略，而單元間的通道，例如門、窗戶等被作為連接不同單元的入口。如圖2所示。

另外，單元-單元(cell-to-cell)的可見性計算準則為:如果處于單元B中的視點(此時將視點假設為一個點)能到達單元F中的某些點，則說明單元B到單元F是可見的，如圖2所示。也就是說，如果2個單元之間存在一條視線，則該視線一定會穿過連接單元B和單元F的入口。由此可知，對于單元-單元的可見性計算，只需判斷連接2個單元的入口是否可見即可。另外，在交互式穿越階段，單元-單元的可見性計算可通過觀察者的視錐進行動態篩選，即眼睛-單元(eye to cell)的可見性計算，從而進一步縮小場景中PVS的范圍。

根據上述算法可得到場景對應的鄰接圖(adjacency graph)及從視點view出發獲得的穿越樹(stab tree)，如圖3所示。鄰接圖存儲了場景中各個單元的鄰接關系，并規定鄰接圖中的兩個鄰接單元間一定有一個入口實現單元間的連通。鄰接圖中的一個節點表示場景中的一個單元，各個節點除了存儲對應單元中的幾何信息外，還需要存儲單元邊界上的入口信息，以及入口所連接的鄰接單元的信息。穿越樹描述了從處于單元I中的視點出發可觀察到的單元和相關入口的信息，以及這些單元在渲染時的先后關系。穿越樹中的節點存儲的內容與鄰接圖中的類似。注意，此時處于穿越樹中的所有單元，以及連接這些單元的入口均處于視錐范圍內。

Teller等提出的算法是在預處理階段、脫機狀態下進行的。但是，當建筑物包含大量多邊形時，該算法將在預處理階段耗費大量時間，不適合用于實時的交互式情況。另外，該算法雖然考慮了顯示幀之間的關聯性，但是并沒有給出詳細可行的方法。

Jiménez［9］將穿過入口的可見性信息分為 3類:單元-單元(cell-to-cell)、單元-區域(cell-toregion)和單元 -對象(cell-to-object)，并在 Teller的基礎上提出了一種改進算法。該算法在線性空間(line space)中通過入口集來計算PVS。該方法通過visibility skeleton工具對所有可見性可能會發生變化的入口序列進行編碼，并納入圖結構(graph structure)中。該方法可用于計算單元-單元或單元-區域的可見性。Visibility skeleton的核心是line swaths，即臨界線的集合(set of critical lines)、極值穿越線(extremal stabbing lines)，以及場景中所有可見性變化的焦距(foci)。另外，Luebke和Georges［15］對基于入口的可見性計算進行了進一步的優化，其研究重心是運行時的PVS計算，而非在預處理階段。該方法可支持動態場景中的基于入口的渲染技術，但該算法只有當建筑物結構內部存在靜態高遮擋情況時，效果才比較好，否則，計算復雜度將會急劇增長。

2.1.2 使用入口材質的渲染算法

Aliaga等［3］提出了使用入口材質(portal textures)的渲染算法。該算法是在一種替代技術的基礎上提出來的，這種替代技術在3D環境中使用2D材質來替代3D模型，從而達到提高渲染速度的目的［4］。其核心是:在單元劃分模型(cell-partitioned model)中使用材質動態的代替可見的入口，使對多邊形的渲染復雜度降低至只對視點所在的當前單元進行渲染，從而在不影響用戶對鄰近單元瀏覽的同時，大幅提高交互執行的渲染速度，如圖4所示。圖4中的上圖灰色部分顯示的是除了視點所在單元外可能需要渲染的其他鄰接單元，下圖顯示在使用了入口材質后，只有視點所在的單元需要渲染。

圖4 使用入口材質的渲染算法

該算法的具體內容包括:

1)材質采樣。對于每個入口，建模者在入口前在以某個值為半徑的區域內定義一系列的受限視點集(假設入口與模型的地面相垂直)，由此，為每個入口固定了一些具有代表性的、高度相同(假設觀察者的視點高度相同)的視點集，然后通過對基于這些視點的通過入口的可見區域的預計算，得到基于該視點的材質集合。當入口可見時，則根據視點方向選擇相應材質來渲染。

2)形變。當視點與入口的垂直距離達到一個臨界值(觀察者即將穿越入口)時，則對入口的渲染將從渲染入口材質轉變為對入口所連接的鄰接單元中可見部分的渲染，由于這種切換會帶來一些突變問題，因此Aliaga采用一種透視形變［5］理論的推論方法，使切換過程變得平滑。

該方法的不足之處是，首先該算法沒有考慮鏡面問題，并且系統的運行需要專業硬件的支持;其次，入口材質的集合是在預處理階段完成的，而不是在運行過程中動態計算獲得的;最后，為了能更好的解決突變問題，系統中使用了復合材質，從而實現了入口材質的平滑切換，但這同時也導致占用過多內存的問題。

由此產生了一個問題，如果希望入口材質在切換時，突變現象不明顯，則需要使用復合材質，這將意味著要使用更多的圖像來合成，同時占用更多的內存來保存這些圖像;但另一方面，如果切換時對應的復合材質使用的圖像過少，又會導致切換過程中突變現象嚴重的問題。因此，為了能更好的解決突變與內存占用之間的矛盾，Rafferty和 Aliaga［5］提出了基于 3D 圖像(3D Image)的渲染方法。該方法一方面能較好的解決突變的問題，使入口材質能夠進行平滑的切換，另一方面又能大量減少每個入口對大量圖像的需求，節省了內存資源。與前者相比，該系統的處理速度更快，能渲染圖像的更多細節，使顯示效果更佳。但是，該算法仍然未對鏡面問題進行探討。之后，Rafferty和Aliaga［6］使用分層的深度圖像在原有基礎上對原系統中用于替代與入口相連的鄰接單元的可見部分的2D圖像進行了優化，使系統能更好的解決3D形變時所產生的錯誤。

2.2 任意入口的渲染算法

2.2.1 任意入口的渲染

任意入口指的是更一般化的入口，即從入口本身的特點出發來發掘入口可提供的功能。Luebke和Georges［14］認為場景中的入口和單元不應該只僅僅用于提高可見性計算和加速渲染，同時還應該可以在場景中被添加或移動，而場景中單元的邊界也應該可以被修改或移動。Tyberghein在其開源游戲引擎——Crystal Space3d［10］中設計并實現了類似于任意入口的形變入口(transformative portal)，該入口可用作獨立單元的連接工具，從而將若干小場景拼接成大型場景。該系統中的每個入口都包含一個將入口轉換到目標單元所在位置的形變矩陣，同時還允許入口放置于單元中的任意位置，而不一定只能位于單元的邊界上。

Nick 等［11］對傳統入口(conventional portal)和任意入口(Arbitrary portal)進行了比較，闡述了傳統入口之所以有眾多限制是為了能更好的配合幾何裁減和加速渲染，還特別指出傳統入口只能位于單元邊界是為了只渲染入口所連接的目標單元，而避免對入口所在單元進行額外的可見性計算。同時，提出了任意入口的典型特性，首先入口表面可以是任意表面;其次，入口可以位于單元中的任意位置，并且可與其他單元中處于任意位置的入口相連。

但是，任意入口的使用將會給相鄰可見單元的可見性計算帶來很大難度，因為任意入口可能存在任意多個面，無法使用傳統的可見性算法來篩選相鄰單元中的可見物體，因此Nick等采用了基于深度緩存、stencil緩存和alpha測試的片元篩選技術(fragment culling technique)來實現可見性計算，其思路是:首先對多邊形進行光柵化，產生對應的片元，然后利用alpha測試確定片元的可見性。

在此基礎上，Nick等［12］對任意入口進行了擴展——由于場景中，一般是將場景中的門或窗戶作為入口，而這些實物都是具有一定厚度的幾何體，因此提出了更符合場景特點的、具有一定厚度的、可用于連接單元的復雜入口(complex portal)，并描述了用于處理復雜入口渲染的基于圖像空間(image-space)的算法，最終提供了通過利用復雜入口來連接不同單元，從而組成動態、靈活場景的框架體系。該復雜入口的核心是:首先，入口可定義為形變(transformative)的、非凸的和非平面的;其次，單元包含數據，入口可用于連接不同單元;最后，使用基于圖像空間(image-space)的渲染算法來處理可見性計算。基于圖像空間的渲染算法的基本思路是:為屏幕空間(screen-space)中可見區域(visible volume)中的每個屏幕像素點定義2個深度值。第1個是近深度值(near-depth value)，當某個片元的深度值比該值小時，則穿過入口后是不可見的。第2個是遠深度值(far-depth value)，任何深度值比它大的片元都將被它遮擋而被剔除。

2.2.2 鏡面入口

任意入口的另一個重要應用是鏡面入口(mirror portals)，也就是說，使用入口來模擬鏡面的效果。Teller［15］認為可將入口所在單元作為源單元(source cell)，然后使入口與源單元進行二次連接，即入口的自連接;之后，將該單元中通過入口可見的對象反射給入口，即對該單元進行二次渲染，由此來實現通過入口對鏡面效果的模擬。但是在對單元進行二次渲染之前，需要對單元中的幾何體進行反射轉換。圖5顯示了鏡面入口及單元-入口圖。

Luebke 和 Georages［14］對鏡面入口(mirror portals)也進行了深入討論，例如，放置在任意位置的鏡面的處理問題及多個鏡面的反射問題等等，但在實現鏡面入口時，由于需要在渲染系統中加入額外的裁減處理，因此只實現了對處于單元邊界上的單一鏡面入口的渲染，但是未討論動態的、完全遞歸的鏡面問題。Tyberghein［10］和 Nick 等［12］則都認為鏡面入口是任意入口的一種自連接，是任意入口的一種特殊情況，而將鏡面入口歸為任意入口的一個子類。

圖5 鏡面入口及單元-入口

3 傳統入口與任意入口的比較

3.1 傳統入口技術的特點

入口一般用于大規模室內場景的可見性計算。入口是有方向性、且只能處于單元邊界處的凸平面多邊形，另外，2個入口間不允許交叉。一般將單元中的門或窗戶設置為入口。單元是由入口劃分而成的凸多面體區域，一般將室內獨立的房間作為單個單元。對于任意相鄰單元，只有通過入口，處于某個單元中的觀察者才能看到相鄰單元，否則不可見。另外，2個相鄰單元一般都具有公共頂點或公共邊。

3.2 任意入口技術的特點

入口除了用于可見性計算外，還可以作為獨立場景/單元間的連接工具，或模擬鏡面效果等。入口的外形無硬性限制，可定義為任意幾何形狀。定義好的入口可放置在單元的任意位置，并且應該支持在運行時對入口的動態修改，包括入口位置的移動、單元中入口的增加/減少等。在對大規模室內場景的處理過程中，可利用入口將場景分為各個獨立單元。也可以先定義各個獨立單元，然后通過使用入口連接各個獨立單元來組成大型室內場景，并且在運行時允許對單元邊界的修改，例如，單元邊界的移動等等。入口支持自連接，用于實現對鏡面的模擬。

4 需要進一步研究的若干關鍵問題

針對大規模復雜的室內場景的基于入口技術的可見性計算問題，國內外眾多研究者從各自的應用背景出發提出了許多算法，并取得了很多突破性的進展，但是仍然存在一些問題需要深入研究，主要總結如下:

1)對鏡面入口的研究仍然停留在對基本鏡面入口的探討，而對同一單元中，多鏡面反射遞歸問題的討論仍然較少。

2)基于入口的可見性計算研究大多數仍停留于對室內場景的處理，而在室外場景中的應用，以及對室內外場景中的入口算法的討論仍然較少。

［1］Cohen-Or D，Chrysanthou Y，Silva C，et al.A Survey of Visibility for Walkthrough Applications［J］.IEEE Transactions on Visualization and Computer Graphics，2003，9(3):412-431.

［2］Teller S J，Sequin C H.Visibility Preprocess for interactively walkthroughs［C］//Proceeding of 1991 the 18thannual conference on Computer graphics and Interactive techniques.New York:ACM press，1991:61-69.

［3］Aliaga D G，Lastra A A.Architectural Walkthroughs U-sing Portal Textures［C］//Proceeding of 1997 the 8thconference on Visualization.Los Alamitos:IEEE Computer Society press，1997:355-362.

［4］Paulo Maciel and Peter Shirley.Visual Navigation of Large Environments Using Textured Clusters［C］//Proceeding of the 1995 Symposium on Interactive 3D Graphics.New York:ACM press，1995:95-102.

［5］Matthew M R，Daniel G A.3D Image Warping in Architectural Walkthroughs［C］//Proceeding of the 1998 Virtual Reality Annual International Symposium.Washington-D C:IEEE Computer Society press，1998:228-233.

［6］Matthew M R，Daniel G A.Images for Accelerating Architectural Walkthroughs［J］.Computer Graphics＆ Applications，1998，18(6):38-45.

［7］Airey J M.Increasing Update Rates in the Building Walkthrough system with Automatic Model-Space Subdivision and Potentially Visible Set Calculations［D］.Chappel Hill:University of North Carolina，1991.

［8］Airey J M，Rohlf J H，Brooks Jr F P.Towards Image Realism with Interactive Update Rates in Complex Virtual Building Environments［C］//Proceeding of the 1990 Symposium on Interactive 3D Graphics.New York:ACM press，1990，24(2):41-50.

［9］Jimenez W F H，Esperan?a C，Antonio A F O.Efficient Algorithms for Computing Conservative Portal Visibility Information ［J］.Computer Graphics Forum，2000，19(3):489-498.

［10］Tyberghein J.Crystal Space 3D Engine［EB/OL］.［2011-9-16］.http://crystal.sourceforge.net.

［11］Lowe N，Datta A.A Fragment Culling Technique for Rendering Arbitrary Portals［C］//Proceedings of the 1st international conference on Computational science.Berlin:Springer-Verlag press，2003:915-924.

［12］Lowe N，Datta A.A New Technique for Rendering Complex Portals［J］.IEEE Transaction on Visualization and Computer Graphics，2005，11(1):81-90.

［13］Jones C B.A New Approach to the‘Hidden Line’Problem ［J］.Computer Journal，1971，14(3):232-237.

［14］Luebke D，Georges C.Portals and mirrors:Simple，fast evaluation of potentially visible sets［C］//Proceeding of the 1995 Symposium on Interactive 3D Graphics.New York:ACM press，1995:105-106.

［15］Teller，Seth J.Visibility Computations in Densely Occluded Polyhedral Environments［D］.Berkeley:University of California.Computer Science Division(EECS)，1992.

［16］普建濤，查紅彬.大規模復雜場景的可見性問題研究［J］.計算機研究與發展，2005，42(2):236-246.

［17］吳玲達，高宇，魏迎梅.大規模復雜場景交互繪制技術綜述［J］.計算機研究與發展，2007，44(9):1579-1587.