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

無效

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

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

步驟一：預處理

首先對要繪制的模型進行預處理，對模型進行等質量劃分，得到子模型，將圖元也 就是子模型組織成KD樹空間結構，圖元為KD樹節點，則處于KD樹同一層次的節點 質量相同，密度越大的節點，其體積越小，在同一層次上，KD樹的節點質心更接近模 型的實際質量分布；模型在空間中有一個外接包圍盒，在KD樹的組織過程中，選擇垂 直于包圍盒最長邊的平面作為模型的分割平面；

步驟二：負載評估

將三維模型空間的點映射至二維的屏幕空間，劃分屏幕空間得到子繪制區域，一個 渲染節點對應一個子繪制區域，子繪制區域內的模型部分為渲染視區，負載評估對模型 在各個子繪制區域內的分布情況進行分析，也就是分析圖元屬于哪個渲染視區，評估過 程通過進行KD樹自頂向下的圖元歸屬判斷來實現，由子繪制區域內的圖元計算子繪制 區域的負載，從KD樹根節點開始按層次順序對每個節點進行歸屬判斷，如果某一個節 點完全位于某個子繪制區域內部或者完全位于其外部，那么它所有的子節點在后續的層 次遍歷過程中都可以忽略，對于不屬于前述情況的節點，即跨邊界節點，則繼續進行其 子節點的歸屬判斷；

步驟三：負載平衡

負載評估之后，得到各個子繪制區域的負載值，獲取本子繪制區域內的各子模型包 圍盒，將各子模型包圍盒的八個頂點映射至屏幕空間，然后在屏幕二維空間內取這八個 點的包圍矩形，將每個矩形作為一個負載體，稱之為負載矩形，負載平衡以負載矩形為 對象；每個渲染節點對應一個渲染視區，對每個渲染節點對應的渲染視區重新劃分，在 負載評估的負載值基礎上動態調整渲染視區范圍，使得每個渲染節點的繪制負載相等， 首先將所有的渲染節點組織成一棵二叉樹，二叉樹的葉節點與各個渲染節點對應，所述 二叉樹的性質如下：對于該二叉樹中的任意一個中間節點，設其左右子樹中的葉節點數 分別為NumL和NumR，那么NumL和NumR滿足這樣的關系：NumL＝NumR或者 NumL+1＝NumR；

設有N個渲染視區，整個模型的總體負載值為L，調整每個葉節點的渲染視區范圍， 使每個葉節點的負載值為L/N，每個中間節點的負載等于其左右子樹的負載之和，按照 渲染節點組織成的二叉樹，由自頂向下逐層分解，按每個節點的負載值劃分屏幕空間；

步驟四：根據新的渲染視區范圍對應調整屏幕空間上的子繪制區域；

步驟五：繪制下一幀。