《一種降低在矢量圖形填充過程中對CPU耗費的方法及裝置》是炬力積體電路設計有限公司於2009年6月10日申請的專利，該專利的申請號為2009102037283，公布號為CN101923699A，授權公布日為2010年12月22日，發明人是馬晨光、白雲波。
《一種降低在矢量圖形填充過程中對CPU耗費的方法及裝置》公開了一種降低在矢量圖形填充過程中對CPU耗費的方法及裝置，該方法包括：解析所述矢量圖形，得到一系列多邊形；利用變換參數以及變換矩陣將多邊形映射到1/2像素為單位的新繪圖坐標系中，同時更新繪圖視窗至新坐標系中，其中，變換參數為A，A＝2/20，n為移位參數，n取值為自然數；獲取新坐標系中多邊形在新繪圖視窗內的部分；將所述新坐標系中多邊形在新繪圖視窗內的部分轉換為一組掃描段；將所述掃描段坐標的原碼右移n位，並對移位後的掃描段上的像素著色。該發明實施例中，在將掃描線覆蓋的像素著色時，採用將坐標值移位的方式代替除法運算，同時將產生的多邊形裁減誤差轉移到著色以前的計算過程中，在保證結果正確的前提下，減少了除法運算，從而減少對CPU資源的占用。
2016年12月7日，《一種降低在矢量圖形填充過程中對CPU耗費的方法及裝置》獲得第十八屆中國專利優秀獎。
（概述圖為《一種降低在矢量圖形填充過程中對CPU耗費的方法及裝置》摘要附圖）
基本介紹
- 中文名：一種降低在矢量圖形填充過程中對CPU耗費的方法及裝置
- 公布號：CN101923699A
- 授權日：2010年12月22日
- 申請號：2009102037283
- 申請日：2009年6月10日
- 申請人：炬力積體電路設計有限公司
- 地址：廣東省珠海市唐家灣鎮哈工大路1號15棟1單元1號
- 發明人：馬晨光、白雲波
- Int.Cl.：G06T1/00(2006.01)I、G06T11/40(2006.01)I
- 代理機構：北京同達信恆智慧財產權代理有限公司
- 代理人：黃志華
- 類別：發明專利
專利背景,發明內容,專利目的,技術方案,改善效果,附圖說明,技術領域,權利要求,實施方式,榮譽表彰,
專利背景
矢量圖形是由一系列坐標點描述的具有特定形狀和屬性的幾何圖形。Flash作為一種矢量圖形動畫格式，其圖形定義主要包括線和區域。其中，線是用來描繪形狀的輪廓，區域是形狀輪廓圈定的內部閉合範圍。Flash矢量圖形繪製中主要是區域填充。Flash中，區域是按照各種顏色交織在一起的方式定義的，並且定義區域輪廓的線包括直線和曲線。為了填充算法上的統一，在填充之前，區域需要被分割成一系列顏色單一的多邊形，通過對多邊形的填充完成對區域的填充。
多邊形的填充是一個計算密集的處理過程，每個步驟都需要大量的計算資源，對中央處理器（CPU）的處理能力有很高的要求，該處理過程包括：多邊形頂點坐標變換、多邊形針對繪圖視窗的裁剪、多邊形轉換成繪圖視窗內的掃描線、掃描線著色。
參見圖1所示，2009年6月前技術中對多邊形進行填充的具體流程如下：
步驟101：解析矢量圖形，得到一系列多邊形。
步驟102：通過矩陣運算對每個多邊形的頂點坐標進行變換，將多邊形映射到繪圖視窗。其中，多邊形是以1/20像素為單位。
步驟103：針對繪圖視窗對多邊形進行裁剪，得到位於繪圖視窗內的多邊形。
步驟104：套用掃描轉換算法，將位於繪圖視窗內的多邊形轉換為繪圖視窗內的一組掃描線。
步驟105：對每條掃描線覆蓋的像素進行著色。著色前，將掃描線交點坐標除以20，以得到繪圖視窗中的像素坐標值。
在上述填充過程中，所述多邊形的頂點坐標以1/20像素為單位，在步驟104對每條掃描線覆蓋的象素進行著色之前，所有計算都要在1/20像素單位上進行，著色時再將轉換的掃描線交點坐標除以20，以得到繪圖視窗中的像素坐標值。由於在CPU上執行除法運算很耗時，需要較多的CPU資源，對CPU的處理能力要求較高。
發明內容
專利目的
《一種降低在矢量圖形填充過程中對CPU耗費的方法及裝置》提供一種降低在矢量圖形填充過程中對CPU資源耗費的方法及裝置，用以降低在進行失量圖形填充過程中對CPU資源的消耗。
技術方案
《一種降低在矢量圖形填充過程中對CPU耗費的方法及裝置》實施利提供的一種降低在矢量圖形填充過程中對CPU資源耗費的方法包括：解析所述矢量圖形，得到一系列多邊形；利用變換參數以及變換矩陣將多邊形映射到1/2像素為單位的新繪圖坐標系中，同時更新繪圖視窗至新坐標系中，其中，變換參數為A，A＝2/20，n為移位參數，n取值為自然數；獲取新坐標系中多邊形在新繪圖視窗內的部分；將所述新坐標系中多邊形在新繪圖視窗內的部分轉換為一組掃描段；將所述掃描段坐標的原碼右移n位，並對移位後的掃描段上的像素著色。
《一種降低在矢量圖形填充過程中對CPU耗費的方法及裝置》實施利提供的一種降低在矢量圖形填充過程中對CPU資源耗費的裝置包括：解析單元，用於解析所述矢量圖形，得到一系列多邊形；映射單元，用於利用乘以變換參數的變換矩陣將多邊形映射到1/2像素為單位的新繪圖坐標系中，同時更新繪圖視窗至新坐標系中，其中，變換參數為A，A＝2/20，n為移位參數，n取值為自然數；多邊形獲取單元，用於獲取新坐標系中多邊形在新繪圖視窗內的部分；掃描轉換單元，用於將所述新坐標系中多邊形在新繪圖視窗內的部分轉換為一組掃描段；移位單元，用於將所述掃描段坐標的原碼右移n位；像素著色單元，用於對移位後的掃描段上的像素著色。
改善效果
《一種降低在矢量圖形填充過程中對CPU耗費的方法及裝置》實施例中，在將掃描線覆蓋的像素著色時，採用將坐標值移位的方式代替除法運算，同時將產生的多邊形裁剪誤差轉移到著色以前的計算過程中，從而在保證結果正確的前提下，減少了除法運算，最終達到減少占用CPU資源的目的。
附圖說明
圖1為2009年6月前技術中實現矢量填充的方法流程示意圖；
圖2為《一種降低在矢量圖形填充過程中對CPU耗費的方法及裝置》實施例實現矢量填充的方法流程示意圖；
圖3為該發明實施例提供的用戶自定義指令（User Defined Instructions，UDI）的操作過程示意圖；
圖4為該發明是實施例提供的裁剪誤差示意圖；
圖5為該發明實施例提供的外包矩形與繪圖視窗位置關係示意圖；
圖6為該發明實施例提供的多邊形裁剪示意圖；
圖7為該發明實施例提供的外包矩形的示意圖；
圖8為該發明實施例提供的多邊形掃描轉換示意圖；
圖9為該發明實施例提供的矢量圖形填充裝置的結構示意圖。
技術領域
《一種降低在矢量圖形填充過程中對CPU耗費的方法及裝置》涉及多媒體數據處理領域，特別是一種降低在矢量圖形填充過程中對CPU耗費的方法及裝置。
權利要求
1.一種降低在矢量圖形填充過程中對CPU資源耗費的方法，其特徵在於，該方法包括以下步驟：解析所述矢量圖形，得到一系列多邊形；利用變換參數以及變換矩陣將多邊形映射到以1/2像素為單位的新繪圖坐標系中，同時更新原繪圖視窗至新坐標系中，其中，變換參數為A，A＝2/20，n為移位參數，n取值為自然數；獲取新坐標系中多邊形在新繪圖視窗內的部分；將所述新坐標系中多邊形在新繪圖視窗內的部分轉換為一組掃描段；將所述掃描段坐標的原碼右移n位，並對移位後的掃描段上的像素著色。
2.根據權利要求1所述的方法，其特徵在於，通過如下公式利用變換參數以及變換矩陣將多邊形映射到1/2像素為單位的新繪圖坐標系中，
其中，所述變換矩陣為
，Sx為x方向縮放因子，Sy為y方向縮放因子，Rx為x方向旋轉因子，Ry為y方向旋轉因子，Tx為x方向平移因子，（x，y）為原始坐標，（x′，y′）為變換後的坐標。
3.根據權利要求1或2所述的方法，其特徵在於，所述利用變換參數以及變換矩陣將多邊形映射到1/2為單位的新繪圖坐標系採用用戶定義指令UDI中的單周期指令實現。
4.根據權利要求1所述的方法，其特徵在於，所述獲取新坐標系中多邊形在新繪圖視窗內的部分步驟之前，進一步包括：根據新坐標系中多邊形的頂點坐標，計算並存儲多變形每條邊的斜率，所述存儲的多邊形每條邊的斜率用於提供裁剪和掃描轉換過程所使用。
5.根據權利要求1或4的方法，其特徵在於，所述獲取新坐標系中多邊形在新繪圖視窗內的部分的步驟包括：獲取所述多邊形的外包矩形；利用所述外包矩形與新繪圖視窗的位置關係，判斷是否對所述多邊形進行裁剪處理，如果不需要裁剪，則直接獲取所述多邊形，否則，對所述多邊形進行裁剪得到位於新繪圖視窗內的多邊形的部分。
6.根據權利要求5所述的方法，其特徵在於，利用所述外包矩形與新繪圖視窗的位置關係，判斷是否對所述多邊形進行裁剪處理，包括：當所述外包矩形在所述新繪圖視窗內時，則確定不需要裁剪；當所述外包矩形與所述新繪圖視窗部分相交時，確定需要對所述多邊形進行裁剪。
7.根據權利要求5所述的方法，其特徵在於，所述對所述多邊形進行裁剪包括：依次獲取每條邊的數據結構，利用裁剪算法對相應多邊形的邊與繪圖視窗進行裁剪，當多邊形的邊完全在新繪圖視窗內時，裁剪後邊的端點坐標保持不變，當多邊形的邊與新繪圖視窗有交點時，裁剪後計算出交點坐標，更新所述數據結構中的坐標值。
8.根據權利要求5所述的方法，其特徵在於，所述獲取外包矩形的步驟包括：獲得多邊形頂點坐標的極值，由頂點坐標中最大和最小橫坐標和縱坐標界定外包矩形。
9.根據權利要求1所述的方法，其特徵在於，所述將新坐標系中所變形在新繪圖視窗內的部分轉換為一組掃描段的步驟包括：當新繪圖視窗內的掃描線縱坐標為2的整數倍時，獲得與該掃描線對應的掃描段，所述掃描段為掃描線與新坐標系中多邊形在新繪圖視窗內的部分的公共部分。
10.一種降低在矢量圖形填充過程中對CPU資源耗費的裝置，其特徵在於，該裝置包括：解析單元，用於解析所述矢量圖形，得到一系列多邊形；映射單元，用於利用乘以變換參數的變換矩陣將多邊形映射到以1/2像素為單位的新繪圖坐標系中，同時更新原繪圖視窗至新坐標系中，其中，變換參數為A，A＝2/20，n為移位參數，n取值為自然數；多邊形獲取單元，用於獲取新坐標系中多邊形在新繪圖視窗內的部分；掃描轉換單元，用於將所述新坐標系中多邊形在新繪圖視窗內的部分轉換為一組掃描段；移位單元，用於將所述掃描段坐標的原碼右移n位；像素著色單元，用於對移位後的掃描段上的像素著色。
11.根據權利要求10所述的裝置，其特徵在於，所述映射單元通過如下公式利用變換參數以及變換矩陣將多邊形映射到1/2像素為單位的新繪圖坐標系中，
其中，所述變換矩陣為，Sx為x方向縮放因子，Sy為y方向縮放因子，Rx為x方向旋轉因子，Ry為y方向旋轉因子，Tx為x方向平移因子，（x，y）為原始坐標，（x′，y′）為變換後的坐標。
12.根據權利要求10所述的裝置，其特徵在於，所述映射單元利用變換參數以及變換矩陣將多邊形映射到1/2為單位的新繪圖坐標系採用用戶定義指令UDI中的單周期指令實現。
13.根據權利要求10所述的裝置，其特徵在於，該裝置進一步包括：斜率計算單元，根據新坐標系中多邊形的頂點坐標，計算多變形每條邊的斜率；存儲單元，用於存儲多邊形每條邊的斜率以提供裁剪和掃描轉換過程所使用。
14.根據權利要求10所述的裝置，其特徵在於，所述多邊形獲取單元包括：外包矩形獲取單元，用於獲取所述多邊形的外包矩形；第一獲取單元，利用所述外包矩形與新繪圖視窗的位置關係，判斷是否對所述多邊形進行裁剪處理，如果不需要裁剪，則直接獲取所述多邊形，否則，對所述多邊形進行裁剪得到位於新繪圖視窗內的多邊形的部分。
15.根據權利要求14所述的裝置，其特徵在於，所述第一獲取單元，用於當所述外包矩形在所述新繪圖視窗內時，則確定不需要裁剪；當所述外包矩形與所述新繪圖視窗部分相交時，確定需要對所述多邊形進行裁剪。
16.根據權利要求14所述的裝置，其特徵在於，所述第一獲取單元，用於依次獲取每條邊的數據結構，利用裁剪算法對相應多邊形的邊與繪圖視窗進行裁剪，當多邊形的邊完全在新繪圖視窗內時，裁剪後邊的端點坐標保持不變，當多邊形的邊與新繪圖視窗有交點時，裁剪後計算出交點坐標，更新所述數據結構中的坐標值。
17.根據權利要求14所述的裝置，其特徵在於，所述外包矩形獲取單元，用於獲得多邊形頂點坐標的極值，並由頂點坐標中最大和最小橫坐標和縱坐標界定外包矩形。
18.根據權利要求10所述的裝置，其特徵在於，所述掃描轉換單元，用於當新繪圖視窗內的掃描線縱坐標為2的整數倍時，獲得與該掃描線對應的掃描段，所述掃描段為掃描線與新坐標系中多邊形在新繪圖視窗內的部分的公共部分。
實施方式
在《一種降低在矢量圖形填充過程中對CPU耗費的方法及裝置》實施例進行多邊形矢量圖形填充的過程中，首先要解析所述矢量圖形，得到一系列多邊形，然後再利用變換參數以及變換矩陣將每個多邊形映射到1/2像素為單位的新繪圖坐標系中，同時更新繪圖視窗至新坐標系中；獲取新坐標系中多邊形在新繪圖視窗內的部分；將所述新坐標系中多邊形在新繪圖視窗內的部分轉換為一組掃描段；將所述掃描段坐標的原碼右移n位，並對移位後的掃描段上的像素著色；其中，變換參數A＝2/20，n為移位參數，為自然數。
由於2009年6月前技術中在對掃描線覆蓋的像素著色時，需要將掃描段的起止坐標及掃描線y坐標除以20，轉換為以像素為單位的值，需要大量除法運算。在《一種降低在矢量圖形填充過程中對CPU耗費的方法及裝置》實施例中，為了減少除法運算，採用移位的方法代替除法運算，將除以20運算採用除以一個與20相近似的2的整次冪的數代替，這樣，就可以用簡單的整數移位代替除法運算。與此同時，將產生的多邊形裁減誤差轉移到著色以前的計算過程中，從而消除最終結果的誤差。
與20相近似的2的整次冪的數有8、16、32、64等，當然也可以用其它數值，當用這些數代替20時，掃描線覆蓋的像素著色以前相應的計算結果就要乘0.4、0.8、1.6、3.2等，以保證最終的計算結果是正確的。
為了節省成本，如精簡指令及計算機（RISC）處理器一般都不具有浮點處理單元，在這樣的處理器上做浮點運算，或者通過軟體模擬方式，或者使用定點近似方式，在精度誤差允許範圍內，使用定點方式的運算速度要快於軟體模擬方式。因此，為了加速處理器的處理速度，在《一種降低在矢量圖形填充過程中對CPU耗費的方法及裝置》實施例中，處理過程中涉及到浮點運算的部分要用定點方式來完成，小數運算均用定點數來代替。
圖2示出了《一種降低在矢量圖形填充過程中對CPU耗費的方法及裝置》實施例提供的一種在攜帶型多媒體設備上實現矢量圖像填充的方法的實現流程，該方法可以降低攜帶型多媒體設備中CPU資源的耗費，具體如下：
步驟201：解析矢量圖形，得到一系列多邊形。這裡，由於矢量圖形檔案中多邊形頂點坐標的單位為1/20像素，這裡解析得到的多邊形坐標為1/20像素。
步驟202：利用變換參數以及變換矩陣將每個多邊形映射到1/2像素為單位的新繪圖坐標系中，同時更新繪圖視窗至新坐標系中，其中，變換參數為A，A＝2/20，n為移位參數，n取值為自然數。
Flash矢量圖形中，多邊形頂點坐標是按32位整數形式定義的，變換矩陣的旋轉因子和縮放因子是按16.16的定點數形式定義的，其平移因子是按32位整數形式定義的。
《一種降低在矢量圖形填充過程中對CPU耗費的方法及裝置》實施例中將坐標變換矩陣定義為：
其中，Sx為x方向縮放因子，Sy為y方向縮放因子，Rx為x方向旋轉因子，Ry為y方向旋轉因子，Tx為x方向平移因子。變換過程為：
，
展開後：x′＝Sxx+Ryy+Tx，y′＝Rxx+Syy+Ty，其中，（x，y）為原始坐標，（x′，y′）為變換後的坐標。
除以32和乘1.6的組合為例，具體來說，假設有一個坐標點（x0，y0），通過坐標變換
映射到繪圖視窗中的坐標點（x1，y1），隨後將（x1，y1）的x和y坐標除20得到像素單位坐標值，有：
上式表明，用1.6倍的變換坐標值除32，就能夠無誤差的得到像素單位坐標值。
1.6倍的變換坐標值可以通過如下變換得到：
上式表明，可以通過將變換矩陣的縮放因子、旋轉因子、平移因子分別乘以1.6，然後用乘以1.6後的矩陣將原始坐標進行變換，得到所需要的1.6倍變換坐標值。上式還表明，不必將原始坐標值乘1.6，只需要將變換因子乘1.6，因此可以減少計算量。
從上述展開後的變換式可以看出，變換過程是一個連續的乘加過程，要執行2次乘法和3次加法。其中，乘法運算是32位整數與16.16格式的定點數乘法，結果為48.16格式的定點數，因為最終變換結果是32位整數坐標值，因此要對乘法結果進行移位處理。RISC處理器中，兩個32位數乘法運算的結果為一個64位數，分別放在HI和LO暫存器中，HI存放高32位，LO存放低32位，為了得到32位整數值，需要通過對HI和LO暫存器中的值進行移位操作。一般情況下，HI中的高16位是可以捨去的無效位，LO中的低16位是要捨去的小數部分，HI的低16位是32位整數坐標值的高16位，LO的高16位是正數坐標的低16位。因此，通過對HI和LO的以下操作，可以得到32位整數坐標值：
HI＜＜16HI | 邏輯左移16位 |
LO＞＞16LO | 邏輯右移16位 |
R＝HI|LO | HI與LO進行位或操作，得到結果 |
可以看出，要通過3次位操作，才能得到32位整數坐標值。但在RISC處理器中，可以通過用戶自定義，將某些複雜操作通過一條指令完成，以上的操作可以使用RISC處理器的UDI指令udi8rs，rt，rd，（imm＜＜3）來實現。該UDI指令的操作過程如下所示：rd＝{rs[（31-8*imm）:0]，rt[31:（31-8*imm+1）]；imm＝00，01，10，11，100。
圖3中，ABCD表示暫存器rs的內容，其中：A＝rs[31:24]，B＝rs[23:16]，C＝rs[15:8]，D＝rs[7:0]。EFGH表示暫存器rt的內容，其中：E＝rt[31:24]，F＝rt[23:16]，G＝rt[15:8]，H＝rt[7:0]。Imm＝00，表示從rs中取出ABCD，按ABCD順序放入暫存器rd中；imm＝01，表示從rs中取出BCD，從rt中取出E，按BCDE順序放入暫存器rd中；imm＝10，表示從rs中取出CD，從rt中取出EF，按CDEF順序放入暫存器rd中；imm＝11，表示從rs中取出D，從rt中取出EFG，按DEFG順序放入暫存器rd中；imm＝100，表示從rt中取出EFGH，按EFGH順序放入暫存器rd中。通過該指令，將HI作為rs暫存器，LO作為rt暫存器，指定imm＝10，可以獲取HI暫存器的低16位與LO暫存器的高16位並組合成所需要的32位整數結果。上述計算，使用該指令的操作為：udi8HI，LO，R，（10）＜＜3。
《一種降低在矢量圖形填充過程中對CPU耗費的方法及裝置》實施利中通過使用UDI中的單周期指令udi8rs，rt，rd，（imm＜＜3），使原來需要3條指令才能完成的操作，縮減為1條指令就可完成，節省了指令數，同時減少了指令執行的周期數，加快了變換處理過程。
上述計算過程中，HI暫存器的高16位有可能也是有效位。這表明，變換後的坐標值太大，已經超出了32位整數所能表示的範圍，出現了溢出。這種情況下，需要對溢出進行處理，一般將出現溢出的變換結果賦值為0x7FFFFFFF（上溢出）或0x80000000（下溢出）。結果是否溢出，可以通過HI暫存器的高16位是否為有效位進行判斷，具體方法為：當HI暫存器的最高位為0時，如果其高16位全為0，則沒有溢出，否則出現溢出，將結果賦值為0x7FFFFFFF；當HI暫存器的最高位為1時，如果其高16位全為1，則沒有溢出，否則出現溢出，將結果賦值為0x80000000。
在步驟202中，還需要將繪圖視窗更新至新坐標系中。
圖4a為平移因子沒有乘變換參數之前的多邊形與串口的相對位置，參見圖4b所示，當變換矩陣的平移因子乘1.6後，多邊形與繪圖視窗的相對位置就會發生變化，將導致多邊形的裁剪產生誤差。為了消除裁剪誤差，在《一種降低在矢量圖形填充過程中對CPU耗費的方法及裝置》實施例中，將繪圖視窗也作相應的更新，將繪圖視窗的4個頂點坐標轉換為1/20像素單位，同時對每個坐標用如下矩陣進行變換：
這樣，用變化了的繪圖視窗對多邊形裁剪，消除了裁剪誤差。
步驟203：獲取新坐標系中多邊形在新繪圖視窗內的部分。
頂點坐標變換完成後，多邊形就被映射到繪圖坐標系下。多邊形與繪圖視窗的位置關係有三種：多邊形在繪圖視窗內、多邊形與繪圖視窗相交、多邊形在繪圖視窗外。對於在繪圖視窗內的多邊形，所有邊都是有效的，都是要填充區域的有效邊界，此時不需要裁剪處理；對於在繪圖視窗外的多邊形，所有的邊都是無效的，所包圍的區域不需要填充，此時多邊形直接被拋棄，不必進行後續的處理過程；對於與繪圖視窗相交的多邊形，有部分在繪圖視窗外面，這部分是不需要被繪製出的，因此需要針對繪圖視窗進行裁剪，計算出位於視窗內的部分，以對視窗內的部分進行填充。
如圖7所示，外包矩形是指包圍多邊形頂點的最小矩形。為了減少不必要的計算過程，《一種降低在矢量圖形填充過程中對CPU耗費的方法及裝置》實施例通過獲得的多邊形的外包矩形判斷多邊形與繪圖視窗的位置關係來決策是否需要進行裁剪處理，如果不需要裁剪，則直接獲取所述多邊形，否則，對所述多邊形進行裁剪得到位於新繪圖視窗內的多邊形的部分。
利用所述外包矩形與新繪圖視窗的位置關係，判斷是否對所述多邊形進行裁剪處理可以這樣實現：當所述外包矩形在所述新繪圖視窗內時，則確定不需要裁剪；當所述外包矩形與所述新繪圖視窗部分相交時，確定需要對所述多邊形進行裁剪。
獲得多邊形的外包矩形是一個在頂點的x、y坐標中求極值的過程。外包矩形可以通過如下方式獲得：（1）獲得多邊形頂點坐標的極值，即：頂點坐標中最大和最小橫坐標和縱坐標；xmin＝MIN（xi），ymin＝MIN（yi），xmax＝MAX（xi），ymax＝MAX（yi），i＝0，…，N，其中，xi、yi為多邊形頂點坐標，N為多邊形的頂點數量；（2）由（xmin，ymin）、（xmax，ymax）界定外包矩形。
外包矩形確定後，通過該矩形與繪圖視窗矩形的布爾運算，即可獲得多邊形與繪圖視窗的位置關係。位置關係如圖5所示，圖5a中，外包矩形與繪圖視窗不相交，圖5b中外包矩形與繪圖視窗相交，圖5c中外包矩形在繪圖視窗內。對於外包矩形與繪圖視窗不相交的情況，退出處理過程；對於外包矩形與繪圖視窗相交的情況，需要進行多邊形裁剪；對於外包矩形在繪圖視窗內的情況，此時可以跳過裁剪過程，直接進行掃描轉換。
處理過程中，對多邊形的裁剪和掃描轉換過程都需要計算邊的斜率，都需要除法運算。為了減少除法運算量，對多邊形的邊計算一次斜率，即可滿足裁剪和掃描轉換時的使用。因此，在進行裁剪和掃描轉換之前，首先進行多邊形邊的斜率計算。為了滿足套用要求，計算出的斜率處理成16.16格式的定點數。計算斜率時，填充如表1所示的數據結構：
Edge | x1 | y1 | x2 | y2 | Slopex |
從變換後的坐標中，取一條邊的兩個頂點坐標（x1，y1）和（x2，y2），然後計算斜率Slopex，計算方法為：
同時將Slopex處理成16.16格式的定點數。當為水平邊時，無法計算出Slopex，但由於水平邊在掃描轉換過程中對生成掃描段沒有貢獻，可以在掃描轉換時剔除，因此將Slopex賦為某一固定值如0x7FFFFFFF，表明該Slopex無意義，計算時不會被使用到。最後，各個值寫入數據結構中以便後面的處理過程使用。
多邊形的裁剪過程可以按照頂點順序，依次獲取每條邊的數據結構Edge，然後通過裁剪算法，依次對多邊形的每條邊與繪圖視窗進行裁剪，裁剪後得到新的頂點坐標。如圖6所示，當邊完全在繪圖視窗內時，裁剪後邊的端點坐標保持不變，同時Slopex保持不變。當邊與繪圖視窗的邊界有1個或2個交點時，裁剪後用計算出的交點對應更新（x1，y1）或（x2，y2），更新規則如圖6所示，圖6a中交點P1代替（x2，y2），圖6b中交點P1代替（x1，y1），圖6c中交點P1代替（x1，y1），交點P2代替（x2，y2）。同時Slopex保持不變。
裁剪算法中，需要使用邊的斜率Slopex，當使用Slopex時，直接從數據結構中獲取。裁剪過程執行完成後，每條邊的Edge數據被更新，多邊形的所有邊都處在了繪圖視窗內。
步驟204：將所述新坐標系中多邊形在新繪圖視窗內的部分轉換為一組掃描段。
對已經完全處在新繪圖視窗內的多邊形，接下來要進行的是掃描轉換過程，將多邊形轉換為一組掃描線上的掃描段。掃描線是繪圖視窗內的一條貫穿視窗的水平線，一個繪圖視窗共有H條掃描線，H是以像素為單位的繪圖視窗高度。掃描段是指掃描線位於多邊形內部的部分，H條掃描線上的掃描段完全覆蓋了多邊形，這樣，通過對這些掃描段的著色，就完成了對多邊形的著色。
掃描轉換過程中，從Edge中獲取邊數據，依次求出與當前掃描線相交的邊，並計算出這些邊與掃描線的交點，計算交點的方法為：ix＝x1+Slopex（iy-y1），其中，ix為掃描線與邊的交點x坐標值，iy為掃描線的y坐標。由於水平邊對生成掃描段沒有貢獻，因此，如果從Edge中獲取的是水平邊，那么跳過對該邊執行的掃描轉換過程。掃描轉換的計算過程如圖8所示。
計算完成後，對得到的2m+2個交點x坐標，其中m為非負整數，按照x大小順序排序，並將數據寫入如表2所示的數據結構中：
ScanLine |  |  |  | … |  |  |
這樣，就能保證諸如、
這樣的由交點界定的掃描段覆蓋多邊形的內部，而象
、
這樣的掃描段覆蓋多邊形的外部，即由偶-奇序號交點界定的掃描段覆蓋多邊形內部，奇-偶序號交點界定的掃描段覆蓋多邊形外部。同時，對偶-奇序號交點界定的掃描段進行著色，就能保證正確填充多邊形內部區域。對所有的掃描線執行這個過程，完成多邊形的掃描轉換過程。
值得注意的是，目前所有的坐標數據都是以1/20像素為單位的，計算交點時，掃描線y坐標也要轉換為1/20像素為單位，如果掃描線y坐標為y′，那么轉換後的掃描線y坐標iy＝20y′。為了加快新繪圖視窗內進行掃描轉換的過程，《一種降低在矢量圖形填充過程中對CPU耗費的方法及裝置》的一個優選實施例是只對掃描線縱坐標是2的整數倍的掃描線進行掃描。
該實施例按如下方式執行：建立一個掃描段鍊表；當新繪圖視窗內的掃描線縱坐標為2的整數倍時，求與該掃描線對應的掃描段，所述掃描段為掃描線與新坐標系中多邊形在新繪圖視窗內的部分的公共部分。
將所述掃描段的參數添加到所述掃描段鍊表中。
在該實施例中，需要將掃棉線與新坐標系中多邊形區域在新繪圖視窗內部的部分的公共線段的參數加入到所述掃描段鍊表中。所述參數可以包括下述組合中任何一個組合的參數，掃描線的縱坐標iy，掃描段一個端點的橫坐標以及掃描段另一端點的橫坐標的組合；或者掃描線的縱坐標iy，掃描段的兩個端點中橫坐標較小端點的橫坐標以及掃描段長度width的組合；或者掃描線的縱坐標iy，掃描段的兩個端點中橫坐標較大端點的橫坐標以及掃描段的長度width的組合。《一種降低在矢量圖形填充過程中對CPU耗費的方法及裝置》實施例使用的參數包括第一組參數，即掃描線的縱坐標iy，掃描段一個端點的橫坐標以及掃描段一個端點的橫坐標。
步驟205：將所述掃描段坐標的原碼右移n位，並對移位後的掃描段上的像素著色。
完成掃描轉換過程後，從ScanLine數據結構中依次獲取掃描段其中m為不大於n的非負整數，將每一個掃描段覆蓋的像素著色，就完成了對多邊形的填充。
圖9示意出了《一種降低在矢量圖形填充過程中對CPU耗費的方法及裝置》實施例提供的一種實現矢量圖形填充的裝置結構示意圖，為了便於說明，僅示意出了與《一種降低在矢量圖形填充過程中對CPU耗費的方法及裝置》實施例相關的部分，該裝置可以集成在多媒體播放終端內，例如行動電話，個人數字助理（PDA）、MP4、GPS導航器等，實現FLASH動畫檔案，GPS圖像等以矢量構成的多媒體數據的播放。
參見圖9所示，《一種降低在矢量圖形填充過程中對CPU耗費的方法及裝置》實施例的一種降低在矢量圖形填充過程中對CPU耗費的裝置包括：解析單元91、映射單元92、多邊形獲取單元93、掃描轉換單元94、移位單元95以及像素著色單元96。其中，解析單元91，用於解析所述矢量圖形，得到一系列多邊形；映射單元92，用於利用乘以變換參數的變換矩陣將多邊形映射到以1/2像素為單位的新繪圖坐標系中，同時更新原繪圖視窗至新坐標系中，其中，變換參數為A，A＝2/20，n為移位參數，n取值為自然數；多邊形獲取單元93，用於獲取新坐標系中多邊形在新繪圖視窗內的部分；掃描轉換單元94，用於將所述新坐標系中多邊形在新繪圖視窗內的部分轉換為一組掃描段；移位單元95，用於將所述掃描段坐標的原碼右移n位；像素著色單元96，用於對移位後的掃描段上的像素著色。
所述映射單元91可以通過如下公式利用變換參數以及變換矩陣將多邊形映射到1/2像素為單位的新繪圖坐標系中，
其中，所述變換矩陣為，Sx為x方向縮放因子，Sy為y方向縮放因子，Rx為x方向旋轉因子，Ry為y方向旋轉因子，Tx為x方向平移因子，（x，y）為原始坐標，（x′，y′）為變換後的坐標。
所述映射單元還可以採用UDI中的單周期指令實現利用變換參數以及變換矩陣將多邊形映射到1/2為單位的新繪圖坐標系。《一種降低在矢量圖形填充過程中對CPU耗費的方法及裝置》實施利中通過使用UDI中的單周期指令udi8rs，rt，rd，（imm＜＜3），使原來需要3條指令才能完成的操作，縮減為1條指令就可完成，節省了指令數，同時減少了指令執行的周期數，加快了變換處理過程。
該裝置還可以進一步包括：斜率計算單元，根據新坐標系中多邊形的頂點坐標，計算多變形每條邊的斜率；存儲單元，用於存儲多邊形每條邊的斜率以提供裁剪和掃描轉換過程所使用。
所述多邊形獲取單元93包括：外包矩形獲取單元，用於獲取所述多邊形的外包矩形；第一獲取單元，利用所述外包矩形與新繪圖視窗的位置關係，判斷是否對所述多邊形進行裁剪處理，如果不需要裁剪，則直接獲取所述多邊形，否則，對所述多邊形進行裁剪得到位於新繪圖視窗內的多邊形的部分。
所述第一獲取單元，用於當所述外包矩形在所述新繪圖視窗內時，則確定不需要裁剪；當所述外包矩形與所述新繪圖視窗部分相交時，確定需要對所述多邊形進行裁剪。
所述第一獲取單元，用於依次獲取每條邊的數據結構，利用裁剪算法對相應多邊形的邊與繪圖視窗進行裁剪，當多邊形的邊完全在新繪圖視窗內時，裁剪後邊的端點坐標保持不變，當多邊形的邊與新繪圖視窗有交點時，裁剪後計算出交點坐標，更新所述數據結構中的坐標值。
所述外包矩形獲取單元93用於獲得多邊形頂點坐標的極值，並由頂點坐標中最大和最小橫坐標和縱坐標界定外包矩形。
所述掃描轉換單元用於當新繪圖視窗內的掃描線縱坐標為2的整數倍時，獲得與該掃描線對應的掃描段，所述掃描段為掃描線與新坐標系中多邊形在新繪圖視窗內的部分的公共部分。
所述掃描轉換單元當新繪圖視窗內的掃描線縱坐標為2的整數倍時，獲得與該掃描線對應的掃描段的具體過程可以這樣實現：建立一個掃描段鍊表；當新繪圖視窗內的掃描線縱坐標為2的整數倍時，求與該掃描線對應的掃描段，所述掃描段為掃描線與新坐標系中多邊形在新繪圖視窗內的部分的公共部分。
將所述掃描段的參數添加到所述掃描段鍊表中。
在該實施例中，需要將掃棉線與新坐標系中多邊形區域在新繪圖視窗內部的部分的公共線段的參數加入到所述掃描段鍊表中。所述參數可以包括下述組合中任何一個組合的參數，掃描線的縱坐標iy，掃描段一個端點的橫坐標以及掃描段另一端點的橫坐標的組合；或者掃描線的縱坐標iy，掃描段的兩個端點中橫坐標較小端點的橫坐標以及掃描段長度width的組合；或者掃描線的縱坐標iy，掃描段的兩個端點中橫坐標較大端點的橫坐標以及掃描段的長度width的組合。《一種降低在矢量圖形填充過程中對CPU耗費的方法及裝置》實施例使用的參數包括第一組參數，即掃描線的縱坐標iy，掃描段一個端點的橫坐標以及掃描段一個端點的橫坐標
《一種降低在矢量圖形填充過程中對CPU耗費的方法及裝置》實施例中，在將掃描線覆蓋的像素著色時，採用將坐標值移位的方式代替除法運算，同時將產生的多邊形裁減誤差轉移到著色以前的計算過程中，在保證結果正確的前提下，減少了除法運算。
《一種降低在矢量圖形填充過程中對CPU耗費的方法及裝置》實施例充分考慮了RISC處理器的特點及flash多邊形處理過程的特點和計算關聯性，能較好的加速flash多邊形處理過程。Flash中的多邊形頂點坐標是以1/20像素單位定義的，在掃描轉換完成後，將掃描段著色時，需要將坐標值除20，轉換為以像素為單位。這裡，將除20運算用右移n位代替，同時將誤差乘到變換矩陣中，這樣在保證結果正確的前提下，減少了除法運算。
《一種降低在矢量圖形填充過程中對CPU耗費的方法及裝置》實施利中通過使用特定UDI指令，將變換中定點數乘法運算結果快速的轉換為所需的整數結果，減少了變換所需指令數，加快了坐標變換處理過程。
《一種降低在矢量圖形填充過程中對CPU耗費的方法及裝置》實施例中通過定義多邊形的外包矩形，並計算多邊形的外包矩形與繪圖視窗的相對位置，以決策多邊形是否需要裁剪，同時對需要裁剪的多邊形才進行裁剪處理，減少了不必要的計算。由於多邊形裁剪和掃描轉換處理過程中，都需要計算邊的斜率。在該發明實施例中，通過在裁剪和掃描轉換處理之前，預先計算出邊的斜率，在裁剪和掃描轉換過程中重複使用，減少了斜率計算次數，同時減少了除法運算。
榮譽表彰
2016年12月7日，《一種降低在矢量圖形填充過程中對CPU耗費的方法及裝置》獲得第十八屆中國專利優秀獎。
