1、圖形并行繪制與多屏顯示技術繪制 對于真實感圖形繪制而言，指用數學模型模擬客觀世界中物體與可見光的相互作用生成真實感圖象的過程。對于非真實感圖形繪制而言，指用數學模型或算法生成具有藝術風格的圖象的過程。 數學模型算法集合軟件包驅動程序硬件產生調用應用圖形繪制的工業化過程圖形繪制的工業化過程高端應用n需要高分辨率的場合，例如使用一個44的屏幕拼接實現4096 * 4096分辨率的大屏幕；n巨型幾何場景，如場景數據規模超過10M數量級以上的三角形面片n反走樣，例如33 走樣，計算量增加9倍之多n大紋理數據量，利用并行/分布圖形繪制可以滿足紋理數據過大的問題，例如地球數據模型等n科學計算領域，例如有限

2、元計算，計算量非常大，一般使用大規模并行計算或者大規模分布計算環境，希望能夠集中顯示高端應用：超高分辨率科學計算可視化孤立系統性能的限制ncompute-limited：產生幾何數據的能力ngraphics-limited：圖形計算能力ninterface-limited：幾何指令發射能力nresolution-limited：顯示分辨率追求高性能繪制n利用某些CPU的SIMD擴展指令集能使幾何變換速度提高2030nAGP總線規范n不斷進步的ASIC硬件技術等n繪制流水線技術n多條流水線并行技術非并行手段并行手段經典的繪制流水線ModelingTransformationsBackfaceCu

3、llingLightingCalculationsViewingTransformationClippingRasterizationZ-bufferCompare &StoreGeometry PhaseRasterization Phase多條流水線并行繪制及其分類方式預變換和分布圖元分布屏幕坐標圖元圖像合成GRGRGRGGGGGRRRGRGRGRGSort-firstSort-middleSort-last 按照圖形對象的分布方式可分為sort-first、sort-middle、sort-last三種。Sort-first 輸出圖像被劃分為一些不相交的區域，如小矩形或連續的掃描

4、線，每條繪制流水線負責一個或多個區域 圖元在進入流水線之前，先進行必要的計算以確定其覆蓋的區域，這種計算被稱為“預變換” 通常方法為算出圖元在屏幕上的外包圍盒（bounding box）并進行比較 一個圖元有可能覆蓋多個區域而進入多條流水線 子圖像（subimage）拼接為最終圖像GGGG預變換和分布圖元RRRRSort-first優缺點 各條流水線完整而獨立，且相對sort-middle和sort-last需要的通訊帶寬較小 有利于構建集群式或異構的并行繪制系統，如WireGL 預變換與部分幾何變換單元的計算重復，是一個不可避免的開銷 對負載平衡敏感Sort-middle 輸出圖像被劃分成一

5、系列區域，并由多個子圖像拼接而成 ,同sort-first 不同的是圖元不考慮視點關系、任意地（比如按輪轉序）進入各個幾何變換單元 幾何變換之后，圖元被轉換成了2D屏幕座標，再根據屏幕座標被傳送到正確的光柵化單元GGRRGRGR分布屏幕圖元亂序進入Sort-middle優缺點 幾何轉換和光柵化一般總是由不同的處理單元來處理，sort-middle在G、R之間打斷流水線的方式是最“自然”的 直觀和常用，有利模塊化地實現 G與R的兩兩之間都需通訊，隨著處理單元的數目增多，通訊開銷將呈幾何級數增長 對負載平衡敏感 Sort-last 圖元任意地進入各條流水線，并獨立完成幾何變換和掃描轉換 一直計算到

6、光柵化的最后一步：可見性判斷（visibility） 每條流水線都產生了包含部分圖元的完整分辨率的象素（樣本） 在合成單元（compositing processor）進行深度合成或alpha混合，輸出最終圖像 GGGGRRRR圖像深度合成亂序進入Sort-last優缺點 簡明 ，易于利用已有的系統模塊（尤其是硬件）實現 其性能不受圖元分布的影響，對負載平衡不敏感 圖像合成步驟易成為系統瓶頸 并行圖形繪制的三種實現方式n基于ASIC技術的硬件實現nsort-middle的InfiniteRealitynsort-last的Pixel-Flown基于并行計算機的實現n基于共享內存并行機的sort

7、-last系統Parallel-Mesan基于分布式內存消息傳遞并行機的sort-middle系統PGLn基于集群機的實現nsort-first的WireGLnsort-last的Sepiansort-first/sort-last混合型的AnyGLWireGLnSiggraph 2001 by Stanford University n解決了分布并行圖形系統系統關鍵問題：指令編碼傳輸和狀態跟蹤 n第一個基于sort-first體系結構并且獨立于硬件平臺的圖形集群繪制系統 n第一次對所有關鍵技術問題提出了完整、實際的解決方案 WireGL系統WireGL的后續：ChromiumnSiggrap

8、h 2002n明確地提出了“流處理” 的概念，圖形繪制過程被看作數據流在SPU（Stream Process Unit）間流動的過程 n各種類型SPU的連接組合可以生成各種結構的并行繪制系統 Chromium：繪制指令分布多屏幕拼接輸出的SPU組合 ApplicationTile sortChromium ServerRenderChromium ServerChromium ServerRenderChromium ServerRenderRender. . .應用程序GNodeRNodeCNodeDNode應用程序GNodeRNode應用程序GNodeRNode應用程序GNodeRNode

9、CNodeDNode網絡網絡網絡立即模式并行繪制系統AnyGL立即模式并行繪制系統AnyGLnAnyGL實現了大規模混合分布圖形體系結構，實現了sort-first與sort-last的混合分布圖形體系結構，解決了分布圖形計算的可擴展性問題，系統節點數目不受限制 nAnyGL實現了一個分布的虛擬并行圖形流水線，可劃分為四類邏輯節點：幾何數據分配節點，幾何圖形繪制節點，深度圖像合成節點和圖形顯示節點。AnyGL允許一個物理節點支持多個多種類型的邏輯節點，能夠利用SMP系統的多圖形加速卡實現并行計算。 并行圖形繪制方法分類的新思路:兩種API應用程序應用程序立即模式繪制器立即模式繪制器應用程序應用

10、程序保留模式繪制器保留模式繪制器進程A進程A進程B進程B(a) 立即模式API(b) 保留模式API模型數據模型數據并行圖形繪制方法分類的新思路：兩種并行繪制體系結構進程D進程D進程C進程C應用程序應用程序立即模式繪制器立即模式繪制器應用程序應用程序保留模式繪制器保留模式繪制器進程A進程A進程B進程B局域網局域網(a) 立即模式并行繪制(b) 保留模式并行繪制模型數據模型數據并行圖形繪制方法分類的新思路n傳統上圖形繪制API分為立即模式和保留模式兩種 n立即模式系統數據存儲于客戶端，保留模式系統數據存儲于服務器端n并行繪制系統可分為立即模式并行繪制系統和保留模式并行繪制系統 客戶節點繪制節點幾

11、何數據歸屬判斷數據調整負載平衡顯示設備對象分布策略拼接輸出幾何數據幾何數據幾何數據繪制節點繪制節點繪制節點保留模式并行繪制系統的構架保留模式系統的數據分布存儲立即模式并行繪制系統： 數據集中幾何指令分布，對網絡帶寬高度依賴，網絡帶寬和歸屬計算易成為系統瓶頸 數據都在客戶端，每繪制一幀，所有幾何數據就作為指令的參數分布到服務器上，服務器繪制完畢，即將數據丟棄，繪制下一幀時重復同樣的過程 結構缺乏彈性，無法有效利用圖形應用程序的幀間相似性 對策n交互式圖形應用程序普遍存在幀間相似性（frame-to-frame coherence），完全突兀的幀是少的，理論上兩幀之間只需進行少量的數據調整 n保留

12、模式系統中幾何數據分布于繪制節點n只要能實現一種數據分布幀間調整的系統構架，就可能降低網絡數據流量，避免帶寬瓶頸系統流程n客戶端讀入幾何數據集G，對G進行剖分并構造Cell結構 n在繪制第一幀之前，客戶端以Cell為單位作歸屬判斷，并根據歸屬關系將Cells分布到各個繪制節點 n繪制第一幀 n如用戶改變視角，客戶端計算新的幾何變換矩陣并發指令到各個繪制節點，不重發G 5.繪制節點根據新的變換矩陣對本機所擁有的圖元作歸屬判斷。若某一圖元歸屬于另一繪制節點，則將此圖元發送到該繪制節點。若某一圖元不再歸屬于本繪制節點，則將其刪除。多個繪制節點之間發送和接收圖元的過程稱為調整（adjust）。調整之后

13、，每個繪制節點都擁有且只擁有歸屬于它的圖元 6.繪制新的幀 ApplicationAFServerAFServerAFServerAFServerAF ProtocolAF ClientAPI callingimage outputAF Protocol communication原型系統結構多機加速和調整率調整率c：通過網絡的數據量和全部數據量之比保留模式并行繪制系統受控的歸屬判斷n立即模式并行繪制通過傳送幾何指令包分布繪制任務n由于立即模式并行繪制系統不擁有數據，幾何數據發射的順序完全由應用程序決定，而后者的行為是不可預測的n如果應用程序發射的幾何數據在空間排列上是混亂的，可能使外包圍盒過

14、大，導致不必要的傳輸和繪制開銷 123456123465(a) 理想情況(b) 不利情況對策n保留摸索并行繪制系統擁有特殊的優勢：對數據的控制能力n對模型數據進行預處理，對模型進行剖分，生成緊湊的外包圍盒n按合理的順序發射數據n可降低圖元歸屬于多個繪制服務器的概率。 Dragon模型的box剖分Ball：比Box更進一步nBall = (Pcenter, R, Geometry) nPcenter為中心點，R為半徑，Geometry為Ball內的幾何圖元數據 n一個Ball包含了空間上相近的一組幾何元素 n與立方體外包圍盒相比，Ball定義了一個球，能更快的進行歸屬判斷 Dragon模型的ba

15、ll剖分負載不平衡的情況實用有效的并行繪制負載平衡算法負載平衡的情況實用有效的并行繪制負載平衡算法靜態并行繪制負載平衡算法1111222233334444問題n屏幕配置一旦完成，系統就處于被動等待的狀態 n依據“圖元更易出現在屏幕中央”這一統計規律，因此其有效性也是統計意義上的 n針對具體的圖形應用的適應性差，不能滿足高性能圖形并行繪制的需要 動態并行繪制負載平衡算法1234567812345678（b） Whelan算法(c)Whitman算法125(d)MADH算法346784241234(a) Roble 算法13動態方法特點 利用所有圖元的頂點位置、幾何變換矩陣等幾何數據作為輸入計算負

16、載平衡狀態最佳的屏幕剖分，因此可以將統稱為“基于幾何數據分析”的方法。這些方法能根據應用程序的實際行為動態調整繪制負載的分配，具有較高的智能性。 基于幾何數據分析的動態方法的不足 n負載估算的精確度不足 n計算開銷過大 n實施難度較大 基于時空轉換的并行繪制負載平衡算法的原理1s2s3s(a)(b)(c)基于時空轉換的并行繪制負載平衡算法的原理 n以繪制服務器的工作時間作為其負載的度量n通過適當的算法將時間值轉換為空間值n空間值控制對繪制服務器的任務分配n放棄了龐大的幾何數據n一種相對 “輕量”的算法 流程n客戶端發送幾何變換矩陣和屏幕區域Aik到繪制節點Si，啟動第k幀繪制，并通知負載平衡模

17、塊；nSi完成Aik像素的繪制，通知客戶端；n客戶端主程序通知負載平衡模塊，后者記錄繪制時間tik；n所有Si繪制結束，拼接圖像并輸出；n負載平衡模塊進行計算，得出屏幕剖分方式Aik+1，用做下一幀繪制任務分配。 (a)(b)(c)(d)32145678t1wihit2t3t4t5t6t7t8屏幕剖分的三種方式校區漫游程序實際效果橫軸為繪制幀數，縱軸為時間（秒），藍線不使用負載平衡控制（固定分割屏幕），紅線使用負載平衡控制。 橫軸為繪制幀數，縱軸為最短繪制時間和最長繪制時間之比，藍線不使用負載平衡控制（固定分割屏幕），紅線使用負載平衡控制 實用的多屏并行繪制系統MSPRn保留模式的分布并行繪制系統 n類OpenGL的保留模式編程APIn對應用程序透明的圖形對象分布策略，包括圖形對象定義、刪除、遠程調用、繪制同步等機制n多屏高分