[發明專利]一種適用于繪制區域任意劃分的并行繪制負載平衡方法

無效

• 申請號: 200910213092.0
• 申請日: 2009-11-10
• 公開（公告）號: CN101702244A
• 公開（公告）日: 2010-05-05
• 發明（設計）人: 唐杰;武港山;朱煉
• 申請（專利權）人: 南京大學
• 主分類號: G06T15/00
• 分類號: G06T15/00;G06T17/00
• 代理公司: 南京天翼專利代理有限責任公司 32112
• 代理人: 黃明哲

技術領域

本發明屬于計算機圖形學領域，涉及計算機圖形繪制，具體為一種適用于繪制區域 任意劃分的并行繪制負載平衡方法。

背景技術

并行繪制技術研究的是利用集群運算系統進行三維繪制。集群運算系統常應用于運 算量巨大的項目，如材料科學、聲學、數學計算和工業設計等方面。大規模數據渲染的 計算密集性大，非常適合由集群運算系統來完成。高性能的并行繪制系統可以為海量數 據場景繪制、大規模虛擬現實和仿真、超高分辨率科學計算可視化等高端應用提供所需 的圖形繪制能力。和專業的圖形工作站相比，集群繪制系統具有極高的性價比和較強的 擴展性。因此，并行繪制技術具有重要的研究意義和實際價值。

Sort-first體系結構常用來構建高性能并行圖形繪制系統。該模式最大程度保持了圖 形流水線的完整性，因此集群并行繪制系統大都采用sort-first結構。Sort-first系統通過 剖分屏幕在多個繪制節點間分配計算任務，當幾何圖元在屏幕上分布不均勻時，容易出 現節點間的負載不平衡：一些繪制節點因處理大量圖元而處于忙碌狀態，同時另一些節 點因分配到稀疏的圖元而處于空閑。由于一幀的繪制時間取決于最后完成工作的節點， 所以這種不均衡狀態將導致并行繪制系統速度的嚴重下降。由此可見，Sort-first模式下 的負載平衡是影響系統性能的一個重要問題。

負載平衡對于sort-first并行繪制系統的性能有很大影響。按照是否動態修改屏幕的 剖分，負載平衡方法可分為靜態方法和動態方法兩類。

靜態方法將屏幕固定地剖分為一些相等的矩形任務塊，塊數大于繪制節點數。這些 任務塊間隔、固定地分配給各繪制節點，使每個繪制節點既有屏幕中央部分的塊，也有 屏幕邊緣部分的塊。對圖形應用程序的觀察統計發現，圖元更易出現在屏幕中央，因此 劃分越細，各繪制節點越傾向于獲得相同的負載。靜態方法優點是實現簡單，幾乎沒有 什么開銷。缺點是其有效性只是統計意義上的，過于粗糙，不能滿足高性能圖形并行繪 制的需要。

動態負載平衡方法根據圖形應用負載分布情況動態改變屏幕的剖分和分配。常見的 方法有：Roble方法、Whelan的median-cut方法、Whitman的自頂向下分解方法、 MAHD(Mesh-based?Adaptive?Hierarchical?Decomposition)方法。它們的區別在于對繪制區 域的調整策略不同。這些方法都通過離線的模擬程序證明了有效性，但沒有直接在集群 繪制系統中得到應用。原因在于它們都需要對所有圖元做幾何變換以確定其屏幕位置， 集群繪制系統往往用于處理上百兆、甚至上G的幾何數據，遍歷圖元的計算開銷太大。 理論上，幾何變換是圖形繪制計算的一部分，其計算結果可以與負載平衡計算共享。但 現實中的并行繪制系統是軟、硬件高度耦合的系統，將負載平衡計算插入到繪制流水線 中去是不現實的。

負載評估是實現負載平衡的關鍵步驟。為了得到較準確的評估值，我們需要對模型 在各個繪制區域內的分布情況有一個充分的分析。然而充分的分析意味著需要花費很多 的時間，這勢必造成集群系統整體效率的下降。因此，速度與精確性成為需要仔細權衡 的兩個方面。負載評估的實現目標是：在盡可能短的時間里，盡可能準確地得到模型的 分布情況。目前每個節點的負載評估常用的指標是上一幀的繪制時間。當場景變化較為 緩慢時，該指標基本能反映本節點的負載。但是當場景變化較為劇烈時，該指標的變化 與實際繪制負載的變化相比，就會產生滯后現象，誤導負載平衡算法，造成繪制性能的 下降。

因此，一個實用的負載平衡算法要滿足如下條件：一、應具備較快的計算速度，使 其本身的開銷小于使用該方法得到的性能提升；二、負載平衡的結果應盡量準確，即在 繪制節點性能相同的前提下，各節點分配的負載應盡量相等，屏幕區域應能任意剖分。

發明內容

本發明要解決的問題是：現有并行繪制負載平衡算法不能很好解決場景劇烈變化下 的要求，提出一種適用于繪制區域任意劃分的并行繪制負載平衡方法。

本發明的技術方案為：一種適用于繪制區域任意劃分的并行繪制負載平衡方法，用 于三維渲染，通過剖分屏幕空間在多個繪制節點間分配計算任務，繪制節點也稱渲染節 點，包括以下步驟：

步驟一：預處理