楊玉婷，康厚良

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

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

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

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

1 基于入口的可見性算法

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

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

2 入口算法解析

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

圖2 由若干房間組成的室內(nèi)場(chǎng)景的單元?jiǎng)澐?/p>

2.1 基于傳統(tǒng)入口的可見性計(jì)算

根據(jù)實(shí)現(xiàn)方法的不同，基于傳統(tǒng)入口的可見性計(jì)算可分為基于單元-單元(cell-to-cell)的可見性計(jì)算及渲染和基于材質(zhì)(texture based)的入口渲染?；趩卧?單元的可見性計(jì)算及渲染從室內(nèi)場(chǎng)景的結(jié)構(gòu)出發(fā)，當(dāng)視點(diǎn)所在單元中的入口可見時(shí)，與該入口相連接的鄰接單元可見，然后再將該可見的相鄰單元作為當(dāng)前單元，判斷該單元中是否存在可見入口和其他相鄰單元。如果入口不可見，則該入口及與它相連的鄰接單元都將全部被剔除。該算法采用的是線性遞歸的方式。而基于材質(zhì)的入口渲染是將與該入口相連的單元在不同視點(diǎn)角度的渲染圖片事先存儲(chǔ)起來，當(dāng)該入口可見時(shí)，根據(jù)當(dāng)前視點(diǎn)的位置將對(duì)應(yīng)圖片填充到入口上的方法。該方法避免在運(yùn)行時(shí)圖形引擎對(duì)相鄰單元的可見性計(jì)算和渲染。

2.1.1 基于單元-單元的可見性計(jì)算及渲染

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

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

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

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

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

Teller等提出的算法是在預(yù)處理階段、脫機(jī)狀態(tài)下進(jìn)行的。但是，當(dāng)建筑物包含大量多邊形時(shí)，該算法將在預(yù)處理階段耗費(fèi)大量時(shí)間，不適合用于實(shí)時(shí)的交互式情況。另外，該算法雖然考慮了顯示幀之間的關(guān)聯(lián)性，但是并沒有給出詳細(xì)可行的方法。

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

2.1.2 使用入口材質(zhì)的渲染算法

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

圖4 使用入口材質(zhì)的渲染算法

該算法的具體內(nèi)容包括:

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

2)形變。當(dāng)視點(diǎn)與入口的垂直距離達(dá)到一個(gè)臨界值(觀察者即將穿越入口)時(shí)，則對(duì)入口的渲染將從渲染入口材質(zhì)轉(zhuǎn)變?yōu)閷?duì)入口所連接的鄰接單元中可見部分的渲染，由于這種切換會(huì)帶來一些突變問題，因此Aliaga采用一種透視形變［5］理論的推論方法，使切換過程變得平滑。

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

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

2.2 任意入口的渲染算法

2.2.1 任意入口的渲染

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

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

但是，任意入口的使用將會(huì)給相鄰可見單元的可見性計(jì)算帶來很大難度，因?yàn)槿我馊肟诳赡艽嬖谌我舛鄠€(gè)面，無法使用傳統(tǒng)的可見性算法來篩選相鄰單元中的可見物體，因此Nick等采用了基于深度緩存、stencil緩存和alpha測(cè)試的片元篩選技術(shù)(fragment culling technique)來實(shí)現(xiàn)可見性計(jì)算，其思路是:首先對(duì)多邊形進(jìn)行光柵化，產(chǎn)生對(duì)應(yīng)的片元，然后利用alpha測(cè)試確定片元的可見性。

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

2.2.2 鏡面入口

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

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

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

3 傳統(tǒng)入口與任意入口的比較

3.1 傳統(tǒng)入口技術(shù)的特點(diǎn)

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

3.2 任意入口技術(shù)的特點(diǎn)

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

4 需要進(jìn)一步研究的若干關(guān)鍵問題

針對(duì)大規(guī)模復(fù)雜的室內(nèi)場(chǎng)景的基于入口技術(shù)的可見性計(jì)算問題，國(guó)內(nèi)外眾多研究者從各自的應(yīng)用背景出發(fā)提出了許多算法，并取得了很多突破性的進(jìn)展，但是仍然存在一些問題需要深入研究，主要總結(jié)如下:

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

2)基于入口的可見性計(jì)算研究大多數(shù)仍停留于對(duì)室內(nèi)場(chǎng)景的處理，而在室外場(chǎng)景中的應(yīng)用，以及對(duì)室內(nèi)外場(chǎng)景中的入口算法的討論仍然較少。

［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］普建濤，查紅彬.大規(guī)模復(fù)雜場(chǎng)景的可見性問題研究［J］.計(jì)算機(jī)研究與發(fā)展，2005，42(2):236-246.

［17］吳玲達(dá)，高宇，魏迎梅.大規(guī)模復(fù)雜場(chǎng)景交互繪制技術(shù)綜述［J］.計(jì)算機(jī)研究與發(fā)展，2007，44(9):1579-1587.