[發明專利]一種基于流水線和狀態機的三角形快速分塊設計方法

有效

• 申請號: 201310556494.7
• 申請日: 2013-11-11
• 公開（公告）號: CN103559679B
• 公開（公告）日: 2019-07-02
• 發明（設計）人: 孫濤;周莉;王佳
• 申請（專利權）人: 濟南大學
• 主分類號: G06T1/20
• 分類號: G06T1/20
• 代理公司: 濟南智圓行方專利代理事務所(普通合伙企業) 37231
• 代理人: 杜文娟

1.一種基于流水線和狀態機的三角形快速分塊設計方法，其特征在于，包括以下步驟：

(1)從場景緩存scene buffer中讀取裁剪后的三角形數據并編號；

(2)將三角形進行視口變換；

(3)計算三角形的包圍盒、邊界函數參數；

(4)計算與包圍盒相交的分塊tile范圍；

(5)根據步驟(4)所確定的三角形包圍盒與分塊tile相交類型，用1位掩碼表示，0表示non-false-over lap無錯誤覆蓋類型情況，1表示包含false-over lap表示含有錯誤覆蓋類型；

(6)將三角形編號及步驟(3)(4)(5)所得相關信息寫入中間先進先出存儲單元FIFO；

(7)分塊列表生成單元Tile list讀取中間先進先出存儲單元FIFO中相關數據；

(8)根據掩碼信息解析相交類型，若為1則轉入步驟(9)，若為0則轉入步驟(10)；

(9)根據當前三角形數據進行LET相交測試，若相交則轉入步驟(10)，否則轉入步驟(11)；

(10)計算當前tile所對應的tile list寫地址，并將當前三角形編號寫入；

(11)將當前tile坐標增加相應量，并判斷與包圍盒相交的tile是否都已經處理完，若沒有處理完成，轉步驟(8)，若處理完成，轉步驟(7)，直到中間先進先出存儲單元FIFO為空結束；

所述步驟(2)包括以下步驟：

(2.1)顯示器屏幕的寬和高分別記為scr_w和scr_h，繪制窗口左下角坐標(win_x,win_y),繪制窗口寬和高分別為win_w、win_h,三角形三個頂點坐標v0(x0,y0)，v1(x1,y1)，v2(x2,y2)，視口變換后的頂點坐標記為V0(X0,Y0)，V1(X1,Y1)，V2(X2,Y2)，首先計算win_w/2、win_h/2；

(2.2)分別計算x0*win_w/2、x1*win_w/2、x2*win_w/2、y0*win_h/2、y1*win_h/2、y2*win_h/2，得到V0、V1、V2相對于繪制窗口左下角的坐標值；

(2.3)將(2.2)得到的坐標值分別與繪制窗口左下角在屏幕坐標系中的坐標值相加，得到三角形三個頂點在屏幕坐標系中的坐標值X0＝x0+x0*win_w/2、Y0＝y0+y0*win_h/2、X1＝x1+x1*win_w/2、Y1＝y1+y1*win_h/2、X2＝x2+x2*win_w/2、Y2＝y2+y2*win_h/2。

2.根據權利要求1所述的基于流水線和狀態機的三角形快速分塊設計方法，其特征在于，所述步驟(3)包括以下步驟：

(3.1)比較X0、X1、X2，Y0、Y1、Y2，分別記得到的較大值較小值為MIN_X、MIN_Y，MAX_X、MAX_Y，得到三角形的包圍盒；

(3.2)計算三角形三條邊e0、e1、e2所在直線的方程參數，具體如下：

e0＝a0*x+b0*y+c0,e1＝a1*x+b1*y+c1,e2＝a2*x+b2*y+c2,

其中，a0＝Y1-Y2,a1＝Y2-Y0,a2＝Y0-Y1，b0＝X2-X1,b1＝X0-X2,b2＝X1-X0，c0＝X1Y2-X2Y1,c1＝X2Y0-X0Y2,c2＝X0Y1-X1Y0。

3.根據權利要求2所述的基于流水線和狀態機的三角形快速分塊設計方法，其特征在于，所述步驟(4)包括以下步驟：

(4.1)將步驟(3)中得到的MIN_X、MIN_Y、MAX_X、MAX_Y的浮點類型數據舍棄小數部分轉化為整型，得到MIN_X_I、MIN_Y_I、MAX_X_I、MAX_Y_I；

(4.2)記所選取的tile的邊長均tile_w，對MIN_X_I、MIN_Y_I、MAX_X_I、MAX_Y_I作相應的低位置零操作，得到的值分別記為I_MIN、J_MIN、I_MAX、J_MAX，即為與包圍盒相交的tile的左下角坐標范圍。