用於對凸多邊形進行柵格化的系統及方法

2023-06-15 21:23:16

專利名稱：用於對凸多邊形進行柵格化的系統及方法
技術領域：
本發明涉及圖像圖形處理領域，更具體地涉及一種用於對凸多邊形進行柵格化的
系統及方法。
背景技術：
柵格化是計算機圖形學中將圖元掃描變換成顯示像素的一種技術，是將矢量圖形 格式表示的圖像變換成柵格圖像以用於顯示器或印表機等的輸出的過程。對圖元進行柵格 化的過程主要包括兩個步驟首先，確定顯示平面上哪些像素是由圖元覆蓋的；其次，將圖 元的屬性(顏色、深度、以及紋理等)賦給每個像素。 計算機圖形學領域中存在很多多邊形柵格化的方法。其中的一個主要方向是，將 多邊形分割成三角形，然後對三角形進行柵格化，該方法在柵格化之前需要很多計算資源 來進行三角化和幾何設置。另外的一個主要方向是，使用Jordan曲線定理和多邊形邊之間 的跨距來進行柵格化，該方法適合凸多邊形和凹多邊形，但是不適合使用邊方程算法來實 現。 綜上所述，現有的用於對多邊形進行柵格化的方法/系統的柵格化架構非常復 雜，所以實現困難且浪費軟體及硬體資源。

發明內容
鑑於以上所述的一個或多個問題，本發明提供了一種新的用於對凸多邊形進行柵 格化的系統及方法，以通過較為簡單的柵格化架構來實現對凸多邊形的柵格化，從而節省 對凸多邊形進行柵格化時所使用的軟體及硬體資源。 根據本發明實施例的用於對凸多邊形進行柵格化的系統，包括設置模塊，用於計 算需要進行柵格化的凸n邊形的n條邊的邊方程係數，記錄用於限定凸n邊形的柵格化區 域的邊界框對所述柵格化區域的區域限定信息，以及根據區域限定信息創建所述邊界框， 其中，n為大於3的整數；掃描模塊，用於利用區域限定信息找出對所述柵格化區域進行掃 描的起始位置，利用凸n邊形的n條邊的邊方程係數逐個判斷從起始位置開始對所述柵格 化區域進行掃描的過程中掃描到的像素是否位於所述柵格化區域內，如果是，則判斷掃描 到的像素需要描畫，否則判斷掃描到的像素不需要描畫；以及描畫模塊，用於在掃描到的像 素需要描畫的情況下，對掃描到的像素進行描畫。 根據本發明實施例的用於對凸多邊形進行柵格化的方法，包括計算需要進行柵 格化的凸n邊形的n條邊的邊方程係數，記錄用於限定凸n邊形的柵格化區域的邊界框對 所述柵格化區域的區域限定信息，以及根據區域限定信息創建所述邊界框，其中，n為大於 3的整數；利用區域限定信息找出對所述柵格化區域進行掃描的起始位置，利用凸n邊形的 n條邊的邊方程係數逐個判斷從起始位置開始對所述柵格化區域進行掃描的過程中掃描到 的像素是否位於所述柵格化區域內，如果是，則判斷掃描到的像素需要描畫，否則判斷掃描 到的像素不需要描畫；以及當掃描到的像素需要描畫時，對掃描到的像素進行描畫。
本發明結合使用了邊方程算法和局部邊方法來對凸多邊形進行柵格化，從而使得 對凸多邊形進行柵格化的柵格化架構與現有技術相比結構相對簡單，從而可以節省對凸多 邊形進行柵格化時所使用的軟體及硬體資源，提高對凸多邊形進行柵格化的速度。


圖1是根據本發明實施例的用於對凸多邊形進行柵格化的系統的框圖；
圖2是根據本發明實施例的設置模塊的動作過程的框圖； 圖3是根據本發明實施例的掃描模塊與設置模塊和描畫模塊進行配合作業的動 作過程的框圖； 圖4是根據本發明實施例的用於對凸多邊形進行柵格化的系統的流水線處理過 程的流程圖； 圖5是根據本發明實施例的邊界框完全覆蓋凸多邊形的示意圖；
圖6是根據本發明實施例的坐標系和局部邊的說明性示意圖； 圖7是根據本發明實施例的說明利用左上規則判斷凸多邊形的各邊是否需要描 畫的情況的說明性示意圖； 圖8是根據本發明實施例的說明判斷當前掃描到的像素是處於凸多邊形的局部 邊之間還是處於凸多邊形的兩側的情況的示意圖； 圖9是根據本發明實施例的起始單元位於凸多邊形的上頂點處的情況的示意圖；
圖10是根據本發明實施例的起始單元位於邊界框範圍內的凸多邊形部分的左上 頂點處的情況的示意圖； 圖11是根據本發明實施例的起始單元位於邊界框範圍內的凸多邊形部分的左上 或右上頂點處的情況的示意圖； 圖12是根據本發明實施例的起始單元位於邊界框範圍內的凸多邊形部分的左上 頂點處的情況的示意圖； 圖13是根據本發明實施例的起始單元位於邊界框範圍內的凸多邊形部分的右上 頂點處的情況的示意圖； 圖14是根據本發明實施例的說明判斷當前掃描到的像素是處於凸多邊形的左側 還是右側的情況的示意圖； 圖15是根據本發明實施例的依次掃描邊界框範圍內的凸多邊形部分的過程的示 意圖；以及 圖16是根據本發明實施例的對當前掃描到的像素進行插值的情況的說明性示意 圖。
具體實施例方式
在本發明中，使用邊方程算法和局部邊方法對凸多邊形進行柵格化。其中，邊方程 定義了兩個平面，如果像素在一個半平面的邊方程值為正，那麼其在另一個半平面的邊方 程值為負，這有利於判斷當前像素是否在凸多邊形內。局部邊是與當前掃描線相交的多邊 形邊，對於凸多邊形來說，只存在兩條局部邊，它們組成三個平面左平面、多邊形內平面、 和右平面。使用局部邊來判斷像素是否畫，以及對像素進行參數插值是相對容易的。
7
本發明的一種實施方式中使用的坐標系統具有如下形式原點位於左上方，X軸
向右，y軸向下。 根據本發明實施例的用於對凸多邊形進行柵格化的系統可以對按順時針排序的n 頂點多邊形進行柵格化。其中，n頂點多邊形的頂點坐標是x[i]和y[i]，O < = i <n。
根據本發明實施例的系統包括一個設置模塊、一個掃描模塊、以及一個描畫模塊， 如圖1所示。其中，設置模塊和掃描模塊的動作過程的框圖分別如圖2和圖3所示。根據 本發明實施例的系統的流水線處理過程的流程圖如圖4所示。 如圖4所示，根據本發明實施例的系統的工作過程為S402，從節點內存中取出多 邊形頂點信息；S404，根據多邊形頂點信息計算邊方程係數；S406，根據多邊形頂點信息尋 找多邊形的最頂端頂點，對多邊形進行裁剪，以及創建邊界框；S408，將邊方程係數存儲在 內存中，用於後續處理；S410，尋找對裁剪後的多邊形進行掃描的起始單元，並尋找局部邊； S412，判斷掃描到的像素是否需要描畫；S414，對掃描到的像素進行插值；S416，將掃描到 的像素的顏色信息存入像素緩存；以及S418，將掃描到的像素描畫出來。
下面描述根據本發明實施例的設置模塊和掃描模塊的具體細節
—、設置模塊。設置模塊主要進行以下動作
1.計算邊方程係數 一個像素(x， y)相對於由頂點(x[O]， y[O])和(x[l]， y[l])組成的邊的邊方程
為e(x，y) =_(y[l]-y
) (x-x
) + (x[1]-x
) (y-y[O]) = (y
-y[1])x+(x[1]-x
)
y+x
y[l]-x[l]y
二ax+by+c，這裡(x， y) 、 (x
， y
)、以及(x[l]，y[l])是設備坐標
系統中的坐標。因此，可以獲得(下面的01表示從0標號的點開始，到1標號的點結束) a01 = y[O]-y[l]; b01 = x[l]-x[O]; c01 = x[O]y[l]-x[l]y[O]。 對於n頂點凸多邊形，存在n條邊。因此，存在三個數組a[n] 、 b[n]和c[n]。在 這裡，可以使用存儲器來存儲這些值 a[O] = a01， a[l] = a12， a[2] = a23， ， a[n-1] = a(n-1)0，b[O] =b01，b[l] =bl2，b[2] = b23， ， b [n_l] =b(n_l)0， c[O] = c01， c[l] = c12， c[2] = c23， ， c[n-l] = c(n-l)O， 這裡，ai j 、 bi j和ci j表示這些值是通過i頂點到j頂點的邊方程計算出來的。 2.創建邊界框 在由 (xmin， ymin)禾口 (xmax， ymax)組成的邊界框(例如，圖5中的502)倉ll建之 前，需要找到多邊形頂點的最小和最大坐標值。頂點(xs， ys)用於記錄多邊形的最頂端頂 點，同時系統也使用一個變量clipmap記錄裁剪信息，它們都用於掃描模塊中尋找起始單 元(例如，圖9中的902、圖10中的1002、圖11中的1104、圖12中的1202、以及圖13中的 1302)。對於裁剪信息，只有以邊界窗口 (即，邊界框)的上邊(例如，圖11中的H02)、左 邊(例如，圖12中的1202)、和右邊(例如，圖13中的1302)進行裁剪的情況需要記錄。
由於在本發明的實施例中，將同一列的兩個像素稱為像素單元(例如，圖5中的 504)，因此在每次掃描時掃描轉換兩條像素線(偶數線和奇數線)。邊界框的上邊的y坐標 總是為偶數，邊界框的底邊y坐標總是為奇數。
8
具體地，尋找最頂端頂點、記錄裁剪信息、以及創建邊界框的過程為首先，將多邊 形的第一個頂點初始化為最小坐標點、最大坐標點、以及尋找起始點，同時初始化clipm即 為0。然後，從多邊形的第一個頂點開始，依次在多邊形的n條邊中尋找，看是否有更大以 及更小的坐標值，如果有，就替換掉原來的最大以及最小坐標，同時記錄最小的y坐標所在 的頂點為最頂端頂點，並將浮點型數值的最大、最小坐標值進行整數化從而獲得未裁減的 邊界框。最後，依次按照頂邊、左邊和右邊的順序分別比較新的邊界框和當前邊界框的坐 標，以獲得新的邊界框坐標，並記錄裁剪信息。如果新的邊界框的頂邊與多邊形相交，則 clipm即的最低位置為1 ;如果新的邊界框的左邊與多邊形相交，則clipm即的最低第2位 置為1 ;如果新的邊界框的右邊與多邊形相交，則clipm即的最低第3位置為1。對於該過 程，可以通過以下程序段實現
fxmin = fxmax = xs = x[O];
fymin = fymax = ys = y[O];
clipmap = 0 ;
for (i = 1 ;i < n ;i++) {
if (fxmin > x[i])fxmin = x[i]; if (fymin > y[i]) { fymin = y[i];
//Keep the coordinates of the topmost vertex xs = x[i] s ys = y[i];




















if (fxmax < x [i]) fxmax = x [i] if (fymax < y [i]) fymax = y [i]
xmin = (int) (fxmin) + (fxmin >= 0. Of O:-l); xmax = (int) (fxmax)+l ; ymin = (int) (fymin) &( 1); ymax = (int)(fymax+1) |1 ; //Keep the clipping information.
//Clip window consists of(clip_xmin，clip_ymin)and(clip_xmax，clip_ymax) if (ymin < clip_ymin) {ymin = clip_ymin ;clipmap & = lb ;} if (xmin < clip_xmin) {xmin = clip_xmin ;clipmap & = 10b ;} if (xmax > clip_xmax) {xmax = clip_xmax ;clipmap & = 100b ;} if(ymax > clip_ymax)ymax = clip_ymax ;
需要設置模塊傳遞到掃描模塊的數據包括x[n+l] 、y[n+1] 、a[n] 、b[n] 、c[n] 、xs、 ys、xmin、ymin、xmax、ymax、clipmap、以及p[n+l]。這裡，p[n+l]是存儲多邊形頂點上參數 (顏色、紋理和深度等)的數組。特別地，在數組x[n+l]、y[n+l]和p[n+l]中，數組元素有 如下關係:x[n] == x
，y[n] == y
，p[n] == p[O]。
二、掃描模塊。掃描模塊主要進行以下動作
在掃描模塊進行具體動作之前，我們預先定義如何判斷像素是否需要描畫(通過 JudgeDrawing 函數實現)。 首先，需要找到對應當前掃描線y二yc(例如，圖6中的602)的局部邊(例如，圖 6中的604)。局部邊是與當前掃描線相交的多邊形邊。對於一個由頂點V[i](x[i]，y[i]) 和V[i+l] (x[i+l]，y[i+l])構成的多邊形邊來說，當滿足條件y[i] <yc<=y[i+l]或者 y[i+l] <yc<=y[i]時，它就是一條局部邊。對於凸多邊形來說，只有兩條局部邊。
尋找局部邊的過程為依次將多邊形中的每一條邊的兩個端點的y坐標y[i]、 y[i+l]與當前掃描線的y坐標yc進行比較，如果滿足條件y[i] <yc<=y[i+l]或者 y[i+l] 〈yc〈二y[i]，則將多邊形的該條邊的計數i記錄下來。對於該過程，可以通過以 下程序段實現 FindlxicalEdges (yi) { j = 0 ; for(i = 0 ;i < n ;i++) { if (y[i] < yi <= y[i+l] | |y[i+l] < yi 1) return error ; } 在特殊情況下，當滿足條件y[i] ==yc==y[i+l]時，當前掃描線與當前多邊 形邊重合，此掃描線上的像素位於此多邊形邊上，此時只需要應用左上規則來判斷當前像 素是否需要描畫。另外，如果當前像素在局部邊上，則其相對於局部邊的邊方程值為0，此時 也只需要應用左上規則來判斷當前像素是否需要描畫。 此時，利用多邊形的邊法線(a[i]，b[i])來確立左上規則，如圖7所示。如果a[i]
<0，則此邊為右側邊(例如，圖7中的702);如果a[i] 二二O並且b[i] <0，此邊為底側
邊(例如，圖7中的704)。如果當前像素位於右側或者底側邊上，當前像素不需要描畫。如
果當前像素位於上側邊或者左側邊(例如，圖7中的706)，則其需要描畫。 如果當前像素不在局部邊上，那麼它就在配對的局部邊之間或者一側，分別稱為
中間性和一側性，如圖8所示。如果當前像素相對於配對的局部邊的邊方程值都為正，則當
前像素具有中間性(即，位於配對的局部邊之間，例如，圖8中的802);如果當前像素相對
於配對的局部邊的邊方程值一個為正一個為負，則當前像素具有一側性(即，位於配對的
局部邊的一側，例如，圖8中的804)。如果當前像素在配對的局部邊之間，則判定為需要描
畫；如果配對的局部邊的一側，則判定為不需要描畫。 其中，JudgeDrawing函數的定義如下JudgeDrawing(xi， yi) { between = aside = 0 ; 皿mO = localEdgeN咖[O]; 皿ml = localEdgeN咖[l];










if (e[誦0] (xi， yi) = = 0) {
if (a[誦0] < 0| I (a[誦O] == 0&&b[num0] < O))
return flagd = 0 5 else return flagd = 1 j }else if (e[皿ml] (xi， yi) = = 0) {
if (a[誦l] < 0| I (a[誦l] == 0&&b[numl] < O))
return flagd = 0 5 else return flagd = 1 j }else if (e[誦0] (xi， yi) > 0&&e[numl] (xi， yi) > 0)
return flagd = 1 5 else return flagd = 0 j } 接下來，具體說明掃描單元實施的動作
1.尋找起始單元 預先確定一個規則，即起始單元應該位於邊界框中多邊形最頂端區域所在的像素 單元之內。其中，多邊形被邊界框底邊裁剪的情況不用考慮。確定起始單元的過程如圖9 到圖13所示。 如圖9所示，如果最頂端頂點位於邊界窗口內，那麼起始單元就是包含此頂點的 像素單元902。 如圖IO所示，如果最左上像素單元判定為需要描畫，那麼起始單元就是此單元 1002。 在其他情況下，需要使用裁剪信息。我們首先考慮由邊界窗口的頂邊(1102)裁剪 的情況，如圖ll所示。此時，有兩個可能的起始單元1104，任何一個都可行。然後，考慮由 邊界窗口的左邊和右邊進行裁剪的情況，如圖12和圖13所示。如果是左邊進行裁剪，則找 出左邊最上端需要描畫的像素單元；如果是右邊進行裁剪，則找出右邊最上端需要描畫的 像素單元。 在需要使用裁剪信息的所有情況中，使用以下方法來確定起始單元的坐標 如果最左上單元的邊方程值為e0和eO+b，那麼最頂端單元線的邊方程值為eO+a*X和 eO+b+a朽，最左側單元線的邊方程值為eO+b*y和eO+b* (y+l)，最右側單元線的邊方程值為 eO+a*width+b*y和eO+a*width+b* (y+l)。如果邊界窗口邊與多邊形邊相交，則對應的邊方 程值在交點將為O，可以使用這個信息來獲得起始單元的x和y坐標值。
比如，當使用邊界框的頂邊進行裁剪時，設eO+a*x = 0和eO+b+a*X = O，將得到 x = -eO/a，以及x = _(60+13)/￡1，分別為頂邊像素單元中上像素和下像素的x坐標，而它們 的y坐標分別為ymin和ymin+l。同理，當使用裁剪框左邊進行裁剪時，設eO+b*y = 0和 eO+b*(y+l) = O，得到y = -eO/b和y = -eO/b_l，分別為左邊像素單元中上像素和下像素的 y坐標，而它們的x坐標為xmin。同樣，當使用裁剪框右邊進行裁剪時，設eO+a*width+b*y =0禾口 eO+a*width+b*(y+l) = O，f尋至ljy = _ (eO+a*width)/b禾口 y = _(eO+a*width)/b_l， 分別為右邊像素單元中上像素和下像素的y坐標，而它們的x坐標為xmax。
尋找起始單元可以通過以下程序段實現
if (xmin <= xs <= xmax&&ymin <= ys <= ymax) {xstart = xs ^ystart = ys ^}else {flagd0 = JudgeDrawing (xmin， ymin);flagdl = JudgeDrawing(xmin， ymin+1);if (flagdO flagdl){xstart = xmin ;ystart = ymin ;}else {if ((clipmap&lb) == 1) {yi = ymin ;for(i = 0 ;i < n ;i++) {if(a[i] ! = 0) {xi = _e[i] (xmin， ymin)/a[i];xi = (xi == (int)xi) (int)xi: (int) (xi+1);
flagdO = JudgeDrawing(xi， yi);flagdl = JudgeDrawing(xi， yi+l);if (flagdO flagdl){xstart = xi ^ystart=yi ;
break Jxi = (int) (xi_l);flagdO = JudgeDrawing(xi， yi);flagdl = JudgeDrawing(xi， yi+l);if (flagdO flagdl){xstart = xi ^ystart=yi ;
break J}else if ((clipmap&10b) == 1) {xi = xmin ;ystart = ymax—l ;for(i = 0 ;i < n ;i++) {if(b[i] ! = 0) {yi = _e[i] (xmin， ymin)/b[i];yi = (yi == (int)yi) (int)yi: (int) (yi+l);flagdO = JudgeDrawing(xi， yi);if (flagdO&&ystart 〉 yi){xstart = xi ;ystart =((int)
yi)&( 1)}else if ((clipmap&100b) == 1) {xi = xmax ;
12
ystart = ymax-l ; for(i = 0 ;i < n ;i++) {
if (b[i] ! = 0) { yi = -(e[i] (xmin， ymin)+a[i]承xmax)/b[i]; yi = (yi == (int)yi) (int) yi : (int) (yi+1); flagd0 = JudgeDrawing(xi， yi); if (flagdO&&ystart > yi) {xstart = xi ;ystart = ((int)
yi)&( 1) ;} } } }else{flagd = 0 ;}//The whole polygon is clipped outside. } 2.掃描多邊形 在掃描方法確定之前，預先給出判斷當前像素是在多邊形的左邊還是右邊的定 義，如圖14所示。 如果當前像素相對於兩條局部邊中的任何一條邊的邊方程值為負，並且對應的x 係數a[i]為正，那麼此像素在多邊形的左側(例如，圖14中的1402)。如果當前像素相對 於兩條局部邊中的任何一條邊的邊方程值為負，並且對應的x係數a[i]小於或等於O，那麼 此像素在多邊形的右側(例如，圖14中的1404)。注意，當a[i] ==0時，所有的像素判定 為處於多邊形的右側。 用於判斷當前像素位於多邊形的左側的函數JudgeLeft 、以及用於判斷當前像 素位於多邊形的右側的函數JudgeRight如下
:0165] JudgeLeft (xi ， yi) {
:0166] flagleft = 0 ;
:0167] 皿m0 = localEdgeN咖[O];
:0168] 皿ml = localEdgeNum[l];
:0169] if ((e[誦O] (xi， yi) < 0&&a[numO] > 0) |
:0170] (e[誦l] (xi， yi) < 0&&a[numl] > O)) return flagleft = 1 ;
:0171] return flagleft ;
:0172] }
:0173] JudgeRight(xi， yi) {
:0174] flagright = 0 ;
:0175] 皿mO = localEdgeN咖[O];
:0176] 皿ml = localEdgeNum[l];
:0177] if ((e[誦O] (xi， yi) < 0&&a[numO] <= 0) |
:0178] (e[皿ml] (xi， yi) < 0&&a[numl] <= O)) return flagright = 1 ;
:0179] return flagright 5
:0180] } 從起始單元開始，多邊形首先往左掃描，然後往右掃描，如圖15所示。當JudgeLeft為真時，左掃描結束；同樣，當JudgeRight為真時，右掃描結束。將緊挨 最左端的判定為需要描畫的像素單元下面的單元作為下一掃描線的起始單元。如果函數 JudgeLeft和JudgeRight都為真，則掃描過程停止。 如果當前像素使用JudgeDrawing函數判定為需要描畫，那麼其參數通過調用 InterpolatePara函數進行插值。 具體地，掃描過程如下首先檢查多邊形是否完全在裁剪框之外，如果是，則不需 要掃描過程；如果不是，則進行以下過程。掃描過程包含兩層循環，內層為x方向，首先往 左，然後往右，外層為y方向，只是從上到下。在往左掃描過程中，判斷當前像素是否位於配 對局部邊的左邊，如果不是，則判斷當前像素是否需要描畫，如果是，則調用插值函數進行 參數插值。在判斷為位於局部邊的左邊後，記錄下一次掃描的起始位置。同樣，以相同的方 式往右進行掃描。當判斷當前像素即在左邊又在右邊時，掃描結束。此過程可以用如下代
碼描述if(flagd== 1) { //The polygon is not clipped out of screen.xi = xstart ;yi = ystart ;while ((yi+l) = xmin) {//Traverse to leftflagl0 = JudgeLeft(xi， yi);flagll = JudgeLeft(xi， yi+1);if (flag10 ==腦flagll == l)flagl = 1 ;if (flagl == 1) break ;else if (flagl = = 0) {flagd0 = JudgeDrawing(xi， yi);flagdl = JudgeDrawing(xi， yi+1);if(flagd0== 1) InterpolatePara(xi， yi);if(flagdl == 1) InterpolatePara(xi， yi+1);xstartnext = xi+1 jystartnext = yi+2 5xi = xstart+1 jyi = ystart ;while (xi <= xmax) { //Traverse to rightflagr0 = JudgeRight(xi， yi);flagrl = JudgeRight(xi， yi+1);if (flagr0 ==腦flagrl == l)flagr = 1 ;if (flagr == 1) break 5
else if (flagr = = 0) { flagd0 = JudgeDrawing(xi， yi); flagdl = JudgeDrawing(xi，yi+1); if (flagdO == 1) InterpolateP,(xi， yi); if(flagd 1 == 1) InterpolateP,(xi， yi+1); } xi++; } if (flagl == l&&flagr == 1) break ; xi = xstart = xstartnext ; yi = ystart = ystartnext ;
}
} 3.參數插值 對於凸多邊形來說，局部邊的數目是2，當前像素處於由局部邊構成的四邊形中， 如圖16所示。對應於像素p的局部邊為V1V2以及V3V4的情況，像素p處於四邊形V1V2V3V4 中。對於參數插值來說，首先要做的是判斷像素在哪個三角形裡面。 這存在兩種情況。如果局部邊相連，則配對的局部邊的四個頂點縮減為三個。這 三個頂點構成一個三角形，當前需要描畫的像素就在這個三角形中進行插值(例如，圖16 中的1602)。 如果局部邊不相連，那麼配對的局部邊的四個頂點構成兩個三角形，需要判斷需 要描畫的像素處於哪個三角形中。首先，計算當前像素相對於連接第三個和第一個頂點V3 和VI的邊方程值，如果此值為正，則當前像素就處於由第一、第二和第三個頂點VI、 V2和 V3構成的三角形中(例如，圖16中的1604);如果此值為負，則當前像素處於由第三、第四 和第一個頂點V3、 V4和VI構成的三角形中(例如，圖16中的1606)。需要描畫的像素的 參數通過相應的三角形進行插值。 參數插值在三角形內完成，如果對應三角形頂點VO的參數為pO，對應頂點VI的參 數為pl，對應頂點V2的參數為p2，那麼三角形內任何一點的參數為P0*e0+pl*el+p2*e2，這 裡e0、 el和e2分別為當前像素對應三角形三條邊的邊方程值。
具體地，對多邊形進行插值的過程可以由以下程序段實現InterpolatePara(xi， yi) { 誦0 = localEdgeN咖[O]; 皿ml = localEdgeN咖[l]; if(x[皿m0] = = x[numl+l]&&y[皿m0] = = y[皿ml+l]) {//one triangle a0 = y[誦0+l]-y[誦l]; b0 = x[誦l]-x[誦0+l]; c0 = x[numO+l]*y[numl]_x[numl]*y[numO+l]; e0 = aO氺xi+bO氺yi+c0 ; p(xi，yi) = p [numO]承eO+p [numO+l]承e [numl]+p [numl]承e [numO];
}else if(x[皿m0+l] = = x[numl]&&y[皿mO+l] ==y[numl]){ //one
triangleaO = y [皿ml+l] _y [皿mO];bO = x [皿mO] _x [皿ml+l];cO = x[numl+l]承y[numO]—x[numO]承y[numl+1];eO = aO氺xi+bO氺yi+c0 ;p(xi， yi) = p[numO+1]氺eO+p[numO]氺e[numl]+p[numl+1]氺e[num
0];}el,se {//two trianglesaO = y [皿ml] _y [皿mO];bO = x [皿mO] _x [皿ml];cO = x[numl]承y[numO]_x[numO]承y[numl] 5eO = aO氺xi+bO氺yi+c0 ;if (eO >= 0) { //in the triangle consisting of 1st， 2nd， and
3rd verticesal = y [皿mO+l] _y [皿ml];bl = x[皿ml]_x[皿mO+l];cl = x[皿mO+l]*y[皿ml]_x[皿ml]*y[皿mO+l];el = al承xi+bl承yi+cl ;p(xi，yi) = p[numO+l]承eO+p[numO]承el+p[ruiml]承e[ruimO];}el,se{//in the triangle consisting of 3rd，4th，and 5th verticeseO = -eO ;al = y [皿ml+l] _y [皿mO];bl = x[皿mO]_x[皿ml+l];cl = x[皿ml+l]*y[皿mO]_x[皿mO]*y[皿ml+l];el = al承xi+bl承yi+cl ;p(xi，yi) = p[皿ml+l]*eO+p[皿ml]*el+p[皿mO]*e[皿ml];//end if two triangles } 綜上所述，根據本發明實施例的用於對凸多邊形進行柵格化的系統包括設置模 塊，用於計算需要進行柵格化的凸n邊形的n條邊的邊方程係數，記錄用於限定凸n邊形的 柵格化區域的邊界框對所述柵格化區域的區域限定信息，以及根據區域限定信息創建邊界 框，其中，n為大於3的整數；掃描模塊，用於利用區域限定信息找出對所述柵格化區域進行 掃描的起始位置，利用凸n邊形的n條邊的邊方程係數逐個判斷從起始位置開始對所述柵 格化區域進行掃描的過程中掃描到的像素是否位於所述柵格化區域內，如果是，則判斷掃 描到的像素需要描畫，否則判斷掃描到的像素不需要描畫；描畫模塊，用於在掃描到的像素 需要描畫的情況下，對掃描到的像素進行描畫。 其中，掃描模塊包括起始位置獲取單元，用於利用區域限定信息判斷凸n邊形的
16最頂端頂點是否位於柵格化區域內，如果是，則判斷最頂端頂點所在的像素單元為起始位置，否則判斷柵格化區域內的最高或最低點所在的像素單元為起始位置，其中，像素單元由
在y方向相鄰的兩個像素組成；區域掃描執行單元，用於掃描格柵化區域，並在掃描格柵化區域的過程中利用凸n邊形的n條邊的邊方程係數逐個判斷掃描到的像素是否位於柵格化區域內，如果是，則判斷掃描到的像素需要描畫，否則判斷掃描到的像素不需要描畫。
另外，根據本發明實施例的用於對凸多邊形進行柵格化的系統還可以包括插值模塊，用於在相對於當前像素所在的掃描線的兩條局部邊相連的情況下，使用兩條局部邊的公共端點以及兩條局部邊的其他端點組成的三角形對掃描到的像素進行插值，在該兩條局部邊不相連的情況下，使用兩條局部邊的四個端點中的任意三個端點組成的三角形對掃描到的像素進行插值。 根據本發明實施例的用於對凸多邊形進行柵格化的方法包括計算需要進行柵格化的凸n邊形的n條邊的邊方程係數，記錄用於限定凸n邊形的柵格化區域的邊界框對所述柵格化區域的區域限定信息，以及根據區域限定信息創建邊界框，其中，n為大於3的整數；利用區域限定信息找出對所述柵格化區域進行掃描的起始位置，利用凸n邊形的n條邊的邊方程係數逐個判斷從起始位置開始對所述柵格化區域進行掃描的過程中掃描到的像素是否位於所述柵格化區域內，如果是，則判斷掃描到的像素需要描畫，否則判斷掃描到的像素不需要描畫；當掃描到的像素需要描畫的情況下，對掃描到的像素進行描畫。
其中，利用區域限定信息找出對所述柵格化區域進行掃描的起始位置的過程包括利用區域限定信息判斷凸n邊形的最頂端頂點是否位於柵格化區域內；如果是，則判斷最頂端頂點所在的像素單元為起始位置，否則判斷柵格化區域內的最高或最低點所在的像素單元為起始位置，其中，像素單元由在y方向相鄰的兩個像素組成。 另外，根據本發明實施例的用於對凸多邊形進行柵格化的方法，在對掃描到的像素進行描畫之前，還可以包括在相對於當前像素所在的掃描線的兩條局部邊相連的情況下，使用兩條局部邊的公共端點以及兩條局部邊的其他端點組成的三角形對掃描到的像素進行插值，在該兩條局部邊不相連的情況下，使用兩條局部邊的四個端點中的任意三個端點組成的三角形對掃描到的像素進行插值。 本領域技術人員將理解，還存在可用於實現本發明實施例的更多可選實施方式和改進方式，並且上述實施方式和示例僅是一個或多個實施例的說明。因此，本發明的範圍僅由所附權利要求書限制。
權利要求
一種用於對凸多邊形進行柵格化的系統，其特徵在於，包括設置模塊，用於計算需要進行柵格化的凸n邊形的n條邊的邊方程係數，記錄用於限定所述凸n邊形的柵格化區域的邊界框對所述柵格化區域的區域限定信息，以及根據所述區域限定信息創建所述邊界框，其中，n為大於3的整數；掃描模塊，用於利用所述區域限定信息找出對所述柵格化區域進行掃描的起始位置，利用所述凸n邊形的n條邊的邊方程係數逐個判斷從所述起始位置開始對所述柵格化區域進行掃描的過程中掃描到的像素是否位於所述柵格化區域內，如果是，則判斷所述掃描到的像素需要描畫，否則判斷所述掃描到的像素不需要描畫；以及描畫模塊，用於在所述掃描到的像素需要描畫的情況下，對所述掃描到的像素進行描畫。
2. 根據權利要求l的用於對凸多邊形進行柵格化的系統，其特徵在於，所述掃描模塊包括起始位置獲取單元，用於利用所述區域限定信息判斷所述凸n邊形的最頂端頂點是否 位於所述柵格化區域內，如果是，則判斷所述最頂端頂點所在的像素單元為所述起始位置， 否則判斷所述柵格化區域內的最高點所在的像素單元為所述起始位置，其中，所述像素單 元由在y方向相鄰的兩個像素組成；區域掃描執行單元，用於掃描所述格柵化區域，並在掃描所述格柵化區域的過程中利 用所述凸n邊形的n條邊的邊方程係數逐個判斷所述掃描到的像素是否位於所述柵格化 區域內，如果是，則判斷所述掃描到的像素需要描畫，否則判斷所述掃描到的像素不需要描 畫。
3. 根據權利要求2的用於對凸多邊形進行柵格化的系統，其特徵在於，所述區域掃描執行單元通過以下過程來判斷所述掃描到的像素是否位於所述柵格化區域內根據所述凸n邊形的n條邊的邊方程係數構造所述凸n邊形的n條邊的邊方程；計算所述掃描到的像素相對於所述凸n邊形中的兩條局部邊的邊方程值，其中，所述 局部邊是所述凸n邊形中的與所述掃描到的像素所在的掃描線相交的邊，並且所述掃描線 的位置高於所述局部邊的下端點且低於或通過所述局部邊的上端點；如果所述掃描到的像素相對於所述兩條局部邊之一的邊方程值為零，則判斷所述掃描 到的像素位於所述兩條局部邊之一上，並且進一步根據所述掃描到的像素所在的局部邊的 邊方程係數判斷所述掃描到的像素所在的局部邊是否為所述凸n邊形的右側邊或底側邊， 如果是，則判斷所述掃描到的像素不需要描畫，否則判斷所述掃描到的像素需要描畫；如果所述掃描到的像素相對於所述兩條局部邊的邊方程值都不為零，則進一步判斷所 述掃描到的像素相對於所述兩條局部邊的邊方程值是否一個為正一個為負，如果是，則判 斷所述掃描到的像素位於所述兩條局部邊的兩側從而判斷所述掃描到的像素不需要描畫， 否則判斷所述掃描到的像素位於所述兩條局部邊之間從而判斷所述掃描到的像素需要描 畫。
4. 根據權利要求3的用於對凸多邊形進行柵格化的系統，其特徵在於，所述區域掃描 執行單元按照從右向左或從左向右的順序掃描所述柵格化區域，並在判斷所述掃描到的像 素位於所述兩條局部邊的兩側時，進一步根據距離所述掃描到的像素較近的局部邊的邊方 程係數判斷所述掃描到的像素位於所述凸n邊形的左側還是右側。
5. 根據權利要求4的用於對凸多邊形進行柵格化的系統，其特徵在於，如果根據距離 所述掃描到的像素較近的局部邊的邊方程係數判斷所述掃描到的像素既位於所述凸n邊 形的左側又位於所述凸n邊形的右側，則終止掃描所述柵格化區域。
6. 根據權利要求1至5中任一項的用於對凸多邊形進行柵格化的系統，其特徵在於，還 包括插值模塊，用於在所述兩條局部邊相連的情況下，使用所述兩條局部邊的公共端點以 及所述兩條局部邊的其他端點組成的三角形對所述掃描到的像素進行插值，在所述兩條局 部邊不相連的情況下，使用所述兩條局部邊的四個端點中的任意三個端點組成的三角形對 所述掃描到的像素進行插值。
7. 根據權利要求6的用於對凸多邊形進行柵格化的系統，其特徵在於，在所述兩條局 部邊不相連的情況下，所述插值模塊從處於右側的局部邊的上端點開始按順時針對所述兩 條局部邊的四個端點進行計數，並根據所述掃描到的像素相對於連接所述兩條局部邊的四 個端點中的的第一和第三端點的線段的邊方程值判斷是使用由所述兩條局部邊的四個端 點中的第一、第二、及第三端點組成的三角形對所述掃描到的像素進行插值還是使用由所 述兩條局部邊的四個端點中的第三、第四、及第一端點組成的三角形對所述掃描到的像素 進行插值。
8. 根據權利要求7的用於對凸多邊形進行柵格化的系統，其特徵在於，在所述掃描到 的像素位於所述兩條局部邊之一上的情況下，所述區域掃描執行單元在所述掃描到的像素 所在的局部邊的邊方程係數中的x分量小於零的情況下，判斷所述掃描到的像素所在的局 部邊為所述凸n邊形的右側邊，在所述掃描到的像素所在的局部邊的邊方程係數中的x分 量等於零且y分量小於零的情況下，判斷所述掃描到的像素所在的局部邊為所述凸n邊形 的底側邊。
9. 根據權利要求8的用於對凸多邊形進行柵格化的系統，其特徵在於，所述區域掃描 執行單元在判斷所述掃描到的像素位於所述兩條局部邊的兩側時，在距離所述掃描到的像 素較近的局部邊的邊方程係數的x分量為正的情況下，判斷所述掃描到的像素位於所述凸 n邊形的左側，在距離所述掃描到的像素較近的局部邊的邊方程係數的x分量為負的情況 下，判斷所述掃描到的像素位於所述凸n邊形的右側。
10. 根據權利要求9的用於對凸多邊形進行柵格化的系統，其特徵在於，所述插值模塊 在所述掃描到的像素相對於連接所述兩條局部邊的四個端點中的的第一和第三端點的線 段的邊方程值為正的情況下，使用由所述兩條局部邊的四個端點中的第一、第二、及第三端 點組成的三角形對所述掃描到的像素進行插值，在所述掃描到的像素相對於連接所述兩條 局部邊的四個端點中的第一和第三端點的線段的邊方程值為負的情況下，使用由所述兩條 局部邊的四個端點中的第三、第四、及第一端點組成的三角形對所述掃描到的像素進行插 值。
11. 一種用於對凸多邊形進行柵格化的方法，其特徵在於，包括計算需要進行柵格化的凸n邊形的n條邊的邊方程係數，記錄用於限定所述凸n邊形 的柵格化區域的邊界框對所述柵格化區域的區域限定信息，以及根據所述區域限定信息創 建所述邊界框，其中，n為大於3的整數；利用所述區域限定信息找出對所述柵格化區域進行掃描的起始位置，利用所述凸n邊形的n條邊的邊方程係數逐個判斷從所述起始位置開始對所述柵格化區域進行掃描的過 程中掃描到的像素是否位於所述柵格化區域內，如果是，則判斷所述掃描到的像素需要描 畫，否則判斷所述掃描到的像素不需要描畫；以及當所述掃描到的像素需要描畫時，對所述掃描到的像素進行描畫。
12. 根據權利要求11的用於對凸多邊形進行柵格化的方法，其特徵在於，利用所述區 域限定信息找出對所述柵格化區域進行掃描的所述起始位置的過程包括利用所述區域限定信息判斷所述凸n邊形的最頂端頂點是否位於所述柵格化區域內； 如果是，則判斷所述最頂端頂點所在的像素單元為所述起始位置，否則判斷所述柵格化區域內的最高點所在的像素單元為所述起始位置，其中，所述像素單元由在y方向相鄰 的兩個像素組成。
13. 根據權利要求12的用於對凸多邊形進行柵格化的方法，其特徵在於，判斷所述掃 描到的像素是否位於所述柵格化區域內的過程包括根據所述凸n邊形的n條邊的邊方程係數構造所述凸n邊形的n條邊的邊方程；計算所述掃描到的像素相對於所述凸n邊形中的兩條局部邊的邊方程值，其中，所述 局部邊是所述凸n邊形中的與所述掃描到的像素所在的掃描線相交的邊，並且所述掃描線 的位置高於所述局部邊的下端點且低於或通過所述局部邊的上端點；如果所述掃描到的像素相對於所述兩條局部邊之一的邊方程值為零，則判斷所述掃描 到的像素位於所述兩條局部邊之一上，並且進一步根據所述掃描到的像素所在的局部邊的 邊方程係數判斷所述掃描到的像素所在的局部邊是否為所述凸n邊形的右側邊或底側邊， 如果是，則判斷所述掃描到的像素不需要描畫，否則判斷所述掃描到的像素需要描畫；如果所述掃描到的像素相對於所述兩條局部邊的邊方程值都不為零，則進一步判斷所 述掃描到的像素相對於所述兩條局部邊的邊方程值是否一個為正一個為負，如果是，則判 斷所述掃描到的像素位於所述兩條局部邊的兩側從而判斷所述掃描到的像素不需要描畫， 否則判斷所述掃描到的像素位於所述兩條局部邊之間從而判斷所述掃描到的像素需要描 畫。
14. 根據權利要求13的用於對凸多邊形進行柵格化的方法，其特徵在於，按照從右向 左或從左向右的順序掃描所述柵格化區域，並在判斷所述掃描到的像素位於所述兩條局部 邊的兩側時，進一步根據距離所述掃描到的像素較近的局部邊的邊方程係數判斷所述掃描 到的像素位於所述凸n邊形的左側還是右側。
15. 根據權利要求14的用於對凸多邊形進行柵格化的方法，其特徵在於，如果根據距 離所述掃描到的像素較近的局部邊的邊方程係數判斷所述掃描到的像素既位於所述凸n 邊形的左側又位於所述凸n邊形的右側，則終止掃描所述柵格化區域。
16. 根據權利要求11至15中任一項的用於對凸多邊形進行柵格化的方法，其特徵在 於，在對所述掃描到的像素進行描畫之前，還包括在所述兩條局部邊相連的情況下，使用所述兩條局部邊的公共端點以及所述兩條局部 邊的其他端點組成的三角形對所述掃描到的像素進行插值，在所述兩條局部邊不相連的情 況下，使用所述兩條局部邊的四個端點中的任意三個端點組成的三角形對所述掃描到的像 素進行插值。
17. 根據權利要求16的用於對凸多邊形進行柵格化的方法，其特徵在於，在所述兩條局部邊不相連的情況下，從處於右側的局部邊的上端點開始按順時針對所述兩條局部邊的 四個端點進行計數，並根據所述掃描到的像素相對於連接所述兩條局部邊的四個端點中的 的第一和第三端點的線段的邊方程值判斷是使用由所述兩條局部邊的四個端點中的第一、 第二、及第三端點組成的三角形對所述掃描到的像素進行插值還是使用由所述兩條局部邊 的四個端點中的第三、第四、及第一端點組成的三角形對所述掃描到的像素進行插值。
18. 根據權利要求17的用於對凸多邊形進行柵格化的方法，其特徵在於，在所述掃描 到的像素位於所述兩條局部邊之一上的情況下，在所述掃描到的像素所在的局部邊的邊方 程係數中的x分量小於零的情況下，判斷所述掃描到的像素所在的局部邊為所述凸n邊形 的右側邊，在所述掃描到的像素所在的局部邊的邊方程係數中的x分量等於零且y分量小 於零的情況下，判斷所述掃描到的像素所在的局部邊為所述凸n邊形的底側邊。
19. 根據權利要求18的用於對凸多邊形進行柵格化的方法，其特徵在於，在判斷所述 掃描到的像素位於所述兩條局部邊的兩側時，在距離所述掃描到的像素較近的局部邊的邊 方程係數的x分量為正的情況下，判斷所述掃描到的像素位於所述凸n邊形的左側，在距離 所述掃描到的像素較近的局部邊的邊方程係數的x分量為負的情況下，判斷所述掃描到的 像素位於所述凸n邊形的右側。
20. 根據權利要求19的用於對凸多邊形進行柵格化的方法，其特徵在於，在所述掃描 到的像素相對於連接所述兩條局部邊的四個端點中的的第一和第三端點的線段的邊方程 值為正的情況下，使用由所述兩條局部邊的四個端點中的第一、第二、及第三端點組成的三 角形對所述掃描到的像素進行插值，在所述掃描到的像素相對於連接所述兩條局部邊的四 個端點中的第一和第三端點的線段的邊方程值為負的情況下，使用由所述兩條局部邊的四 個端點中的第三、第四、及第一端點組成的三角形對所述掃描到的像素進行插值。
全文摘要
本發明公開了一種用於對凸多邊形進行柵格化的系統及方法。其中，該系統包括設置模塊，用於計算需要進行柵格化的凸n邊形的n條邊的邊方程係數，記錄用於限定所述凸n邊形的柵格化區域的邊界框對該柵格化區域的區域限定信息，以及根據該區域限定信息創建該邊界框，其中，n為大於3的整數；掃描模塊，用於利用區域限定信息找出對該柵格化區域進行掃描的起始位置，利用凸n邊形的n條邊的邊方程係數逐個判斷從起始位置開始對該柵格化區域進行掃描的過程中掃描到的像素是否位於該柵格化區域內，如果是，則判斷掃描到的像素需要描畫，否則判斷掃描到的像素不需要描畫；以及描畫模塊，用於在掃描到的像素需要描畫的情況下，對掃描到的像素進行描畫。
文檔編號G06T11/00GK101739696SQ20081017547
公開日2010年6月16日 申請日期2008年11月10日 優先權日2008年11月10日
發明者洲鐮康, 白向暉, 譚志明 申請人:富士通株式會社