專利名稱：粗線生成方法及裝置的制作方法
技術領域：
本發明涉及計算機圖形學領域、GDI(Graphics Device Interface，圖形設備接口)基礎圖形生成算法，尤其涉及一種粗線生成方法及裝置，其能夠快速生成粗線，尤其適用于例如嵌入式地理信息系統、導航系統中地理圖形的快速描畫。
背景技術：
本發明來源于“LBS(Location Based Service，基于位置的服務)軟件平臺”項目，可以通過無線定位技術和GIS(GeographicInformation System，地理信息系統)技術的結合，通過嵌入式用戶終端(手機等)的圖形顯示系統來告訴用戶需要的地理位置圖形信息。
在顯示基于目標地理位置的信息時，需要頻繁地調用基礎圖形生成算法來進行地理圖形描畫，因此，高效的圖形描畫算法，即計算機圖形學基礎算法研究是該軟件平臺研究的關鍵之一。市場上的嵌入GIS設備幾乎都存在地理圖形描畫速度慢的問題，快速高效的圖形生成算法無疑會極大地改善地理信息服務的系統性能和效率，提高用戶滿意度和產品競爭力。
在地理圖形描畫過程中，經常需要畫寬度大于一個像素的短粗線條，來表示道路、標志、輪廓、建筑、河流等。常用的粗線畫法為了達到精細描畫，使用了較多的運算量來計算粗線的輪廓多邊形然后再采用多邊形填充算法，其中需要相當多的浮點乘、除、平方、開方、取整運算，在圖形工作站或PC系統中由于系統主頻高、有硬件浮點處理器、GPU支持，并且一般的應用并不需要頻繁畫大量的粗線等原因，通常會體現出較快的描畫速度。而在嵌入式圖形系統中頻繁地描畫大量的細線、粗線組成的地理圖形時，在中高檔圖形系統中的硬件配置條件都不存在了，因此也就無法實現較快的描畫速度。
為了解決上述問題，需要根據嵌入系統硬件配置的特點來設計粗直線的高速生成方法，然而目前尚未實現此種生成方法。雖然計算機圖形學基礎算法的研究已經有40余年的歷史，其發展已經相當成熟，很難再做出創新性的成果，但是基礎算法的微小進步就會可觀的改善圖形系統效率。研究、改善和優化基礎圖形生成算法有著很重要的意義。
發明內容
考慮到現有技術中存在的上述問題而提出本發明，為此，本發明旨在提供一種粗線生成方法及裝置，其能夠實現快速填充、減少浮點運算和取整運算，從而快速生成粗線，并能夠對繪制地圖輪廓時的應用特點做一些實用的工程化處理。
根據本發明，提供了一種粗線生成方法。
該粗線生成方法包括步驟一，預先生成線寬增量表，其中，寬度增量表中包含線寬預定時四個斜率區間對應的線寬增量；步驟二，根據粗線端點的坐標值通過快速移位比較確定粗線的斜率區間；步驟三，根據在步驟二中得到的斜率區間和線寬，在寬度增量表中查找相應的線寬增量，將線寬和線寬增量相加得到掃描線長度L；步驟四，用“兩點-對稱”畫線算法每次計算生成一個點時，以當前點為中點掃描出一條水平或垂直的線，對稱掃描，掃描行程為掃描線長度L的一半；步驟五，繪制線帽。
其中，在步驟一中，根據斜率的中值來計算寬度增量。具體地，根據等誤差中值來計算寬度增量，其中，等誤差中值為按斜率值取得的斜率區間正中間時的斜率值。根據等概率中值來計算寬度增量，其中，等概率中值為按等角取得的斜率區間正中間時的斜率值。另外，在生成線寬增量表時，每隔4個像素進行一次線寬增量計算。
上述的四個斜率區間為(0，1/4)、(1/4，1/2)、(1/2，3/4)、(3/4，1)，并且線寬增量表中進一步包括與四個斜率區間對應的SLOPE值。
相應地，在步驟三中，根據確定的斜率區間在線寬增量表中查找其對應的SLOPE值，然后，根據線寬的四分之一的值和查找的SLOPE值，從線寬增量表中查找對應的線寬增量。
在步驟四中，從掃描線的兩頭同時開始畫線，一次畫兩個點，經過L/2次畫出整條掃描線。而在步驟五中，在繪制線帽時，一次畫四個點。此外，在繪制線帽時，當粗線斜率的絕對值小于1時，生成粗線的左線帽和右線帽，當粗線斜率的絕對值大于1時，生成粗線的上線帽和下線帽。
根據本發明，還提供了一種粗線生成裝置。該裝置包括線寬增量表生成模塊，用于生成線寬增量表，其中，寬度增量表中包含線寬預定時四個斜率區間對應的線寬增量；斜率區間確定模塊，用于根據粗線端點的坐標值通過快速移位比較確定粗線的斜率區間；掃描線長度確定模塊，用于根據斜率區間確定模塊確定的斜率區間和線寬，在寬度增量表中查找相應的線寬增量，將線寬和線寬增量相加得到掃描線長度L；畫線模塊，用于用“兩點-對稱”畫線算法每次計算生成一個點時，以當前點為中點掃描出一條水平或垂直的線，對稱掃描，掃描行程為掃描線長度L的一半；線帽繪制模塊，用于繪制線帽。
其中，線寬增量表生成模塊根據斜率的中值來計算寬度增量，并且在生成線寬增量表時，每隔4個像素進行一次線寬增量計算。
另外，掃描線長度確定模塊根據斜率區間確定模塊確定的斜率區間在線寬增量表中查找其對應的SLOPE值，然后，根據線寬的四分之一的值和查找的SLOPE值，從線寬增量表中查找對應的線寬增量。畫線模塊從掃描線的兩頭同時開始畫線，一次畫兩個點，經過L/2次畫出整條掃描線。線帽繪制模塊在繪制線帽時，當粗線斜率的絕對值小于1時，生成粗線的左線帽和右線帽，當粗線斜率的絕對值大于1時，生成粗線的上線帽和下線帽。
通過本發明，提供了一種運算量小且連接效果好的粗線快速生成方案，通過應用本發明可以提高圖形系統的效率。
本發明的其它特征和優點將在隨后的說明書中闡述，并且，部分地從說明書中變得顯而易見，或者通過實施本發明而了解。本發明的目的和其他優點可通過在所寫的說明書、權利要求書、以及附圖中所特別指出的結構來實現和獲得。
附圖用來提供對本發明的進一步理解，并且構成說明書的一部分，與本發明的實施例一起用于解釋本發明，并不構成對本發明的限制。在附圖中圖1為點變掃描線法(常用的粗線生成算法一般都未采用該方法)畫粗線效果圖；
圖2為典型的掃描線長計算方法的示意圖；圖3為根據本發明實施例的粗線生成方法的流程圖；圖4為根據本發明實施例的線帽描圖步驟的示意圖；圖5為根據本發明裝置實施例的粗線生成裝置的框圖；圖6示出了線帽的連接效果圖；圖7示出了使用本發明畫粗線生成多邊形時的效果圖；以及圖8示出了本發明的線帽描畫方法的缺陷。
具體實施例方式
本發明實施例提供了一種粗線生成方法和裝置，其能夠快速生成連接效果較好的粗線，屬于嵌入式地理信息服務設備基礎圖形生成算法研究的一部分。
以下結合附圖對本發明的優選實施例進行說明，應當理解，此處所描述的優選實施例僅用于說明和解釋本發明，并不用于限定本發明。
方法實施例根據本發明實施例，提供了一種粗線生成方法，其使用“兩點-對稱”直線生成算法生成粗線的軸心，不需要計算粗線輪廓，直接用與線寬相當的掃描線畫出(掃描線的長度通過查表增量算法得出)，達到了相當快的生成速度。在整個粗線生成過程中，僅用到了整型數的加、減、移位和內存查表運算，運算量非常小。該方法還解決了在粗線繪制過程中存在的折線接頭處線帽連接處理的問題，提出了一種新穎的線帽畫法，不僅運算量小，而且達到了比較好的連接效果。
首先，圖1為點變掃描線法(常用的粗線生成算法一般都未采用該方法)畫粗線效果圖。它是在兩點-對稱Bresenham直線生成算法的基礎上，每生成一個點，就把畫點操作用畫豎直(粗線斜率小于1)或水平(粗線斜率大于1)掃描線操作替代，這樣畫出來的是一個平行四邊形的粗線，如果再畫上合適的線帽(端頭)，還可以在畫折線時表現出良好的連續性。沒有畫線帽時的結果如圖1所示。
點變掃描線法使用時首先要計算掃描線的長度，如圖2所示的典型計算方法使用了運算量相當大的浮點運算。
本發明的方法采用查表增量算法代替了圖2所示的計算方法，令L=w×1+(dy/dx)2=w×1+m2=w+Δw,]]>采用一種實用工程化的近似處理方法，根據不同的斜率區間和線寬先計算出寬度增量Δw＝L-w，這些已經計算好的寬度增量值存放在一張寬度增量表中，使用時就可以通過直線的線寬和斜率快速的索引到寬度增量值。因為L＝w+Δw，這樣就可以通過查寬度增量表的方法來代替計算L的復雜運算，本發明的方法可以僅僅用整數的移位、比較來快速索引出的對應粗線的Δw值。
基于以上描述，接下來，如圖3所示，根據本發明實施例的粗線生成方法包括步驟S302，預先生成線寬增量表(如下的表1和表2)，其中，寬度增量表中包含線寬預定時四個斜率區間對應的線寬增量；步驟S304，根據粗線端點的坐標值(dx，dy)通過快速移位比較確定粗線的斜率區間；
步驟S306，根據在步驟S304中得到的斜率區間和線寬，在寬度增量表中查找相應的線寬增量，將線寬w和線寬增量Δw相加得到掃描線長度L(L＝w+Δw)；步驟S308，用“兩點-對稱”畫線算法每次計算生成一個點時，以當前點為中點掃描出一條水平或垂直的線，對稱掃描，掃描行程為掃描線長度L的一半；步驟S310，繪制線帽。
以下將進一步描述上述處理的各個細節。
表1表示了線寬為1時的線寬增量，示出了線寬W＝1時四個斜率區間(0，1/4)、(1/4，1/2)、(1/2，3/4)、(3/4，1)中寬度增量Δw的計算結果(線寬增量表中進一步包括與四個斜率區間對應的SLOPE值)。
L=w×1+(dy/dx)2=w×1+m2=1×1+m2=1+Δw,]]>在表1中，根據斜率m的中值來精確計算出Δw，其中，等誤差中值是指按斜率值取斜率區間正中間時的斜率值來計算Δw，等概率中值是指按照按等角取得的斜率區間正中間時的斜率值來計算Δw。由于線寬每變化一個像素都要計算四個斜率區間的線寬增量，這樣制作出的線寬增量表就可能很大，考慮到一個像素時的線寬增量最大值為0.325，不妨將線寬每隔4個像素時做一個線寬增量計算，這樣就可以通過(w/4)×(4*ΔmW)和SLOPE的值來制作增量表，并且通過w/4和SLOPE的值來快速查出Δw＝AddWith[w＞＞2][SLOPE]，L＝w+Δw。從制作完成的表2可以看出這樣處理帶來的誤差使得線寬不失連續性，也就是說，最大有一個像素的誤差。
表1
表2示出了方法(算法)中實際使用的線寬增量表(單位像素)。該表存儲了線寬從1到80個像素時的線寬增量。
表2
在步驟S304中，根據直線端點算出的坐標差值dx、dy，通過快速移位比較的方法來獲得斜率區間SLOPE的值，SLOPE值放在ROM中，如下面的C語言宏定義所示#define SLOPE_ROM(dx，dy，ROM) \if(dx＞(dy＜＜1)‖dx＝＝(dy＜＜1)) /*斜率＜＝1/2*/ \{ \if(dx＞(dy＜＜2)) ROM＝0； /*斜率＜1/4*/ \else ROM＝1；\} \else\{ \if(((dy＜＜1)+dy)＜(dx＜＜2))ROM＝2；/*1/2＜斜率＜3/4*/ \else ROM＝3； \在步驟S306中，根據確定的斜率區間在線寬增量表中查找其對應的SLOPE值，然后，根據線寬的四分之一的值(w/4)和查找的SLOPE值，從線寬增量表中查找對應的線寬增量。例如，結合表2，要求畫的線斜率為0.8、寬度為23個像素的粗線，先求出線寬關于4的整數倍數23/4＝5，再確定斜率區間值m＝0.8∈(3/4，1)，所以SLOPE＝3。在表中w/4＝5行，SLOPE＝3列可以查到線寬增量為7，那么掃描長度就為L＝w+Δw＝23+7＝30，而使用精確的公式計算結果為29.454。通過以上的查表方法，最大誤差為8％*w，在繪制地理圖形時，由于經常繪制的線寬一般小于30個像素，并且繪制的線寬精度不需要有繪圖機、圖形工具那樣高，這樣的誤差是可以接受的。
在步驟S308中，由于對稱性，可以從掃描線的兩頭同時開始畫線，一次畫兩個點，經過L/2次畫出整條掃描線。由于兩點-對稱算法一次可以生成4個點，這樣每步掃描實際上可以畫出8個點，有8倍加速效果。實際掃描線長會因L的奇偶性而有一個像素的誤差，當然，不使用對稱掃描可以消除這個誤差。這樣當“兩點-對稱”畫線生成了粗線軸心時，粗線的掃描生成也完成了。
在步驟S310中，繪制線帽是生成粗線的最后一個步驟。算法的實現是由一個循環語句完成，考慮到線帽形狀的對稱性，又同時畫兩個線帽，一次可以畫到4個點。斜率大于1時采用附圖4的模式2，斜率小于1時用圖4的模式1，分stepx＝1(圖4(1))、stepx＝-1(圖4(2))、stepy＝1(圖3(3))、stepy＝-1(圖4(4))幾種情況來處理。即，粗線斜率絕對值小于1時，生成粗線段的左線帽和右線帽；粗線斜率絕對值大于1時，生成粗線段的上線帽和下線帽。
裝置實施例根據本發明實施例，提供了一種粗線生成裝置。
如圖5所示，該裝置包括線寬增量表生成模塊502，用于生成線寬增量表，其中，寬度增量表中包含線寬預定時四個斜率區間對應的線寬增量；斜率區間確定模塊504，用于根據粗線端點的坐標值通過快速移位比較確定粗線的斜率區間；掃描線長度確定模塊506，用于根據斜率區間確定模塊確定的斜率區間和線寬，在寬度增量表中查找相應的線寬增量，將線寬和線寬增量相加得到掃描線長度L；畫線模塊508，用于用“兩點-對稱”畫線算法每次計算生成一個點時，以當前點為中點掃描出一條水平或垂直的線，對稱掃描，掃描行程為掃0描線長度L的一半；線帽繪制模塊510，用于繪制線帽。
其中，線寬增量表生成模塊502根據斜率的中值來計算寬度增量，并且在生成線寬增量表時，每隔4個像素進行一次線寬增量計算。
另外，掃描線長度確定模塊506根據斜率區間確定模塊確定的斜率區間在線寬增量表中查找其對應的SLOPE值，然后，根據線寬的四分之一的值和查找的SLOPE值，從線寬增量表中查找對應的線寬增量。畫線模塊508從掃描線的兩頭同時開始畫線，一次畫兩個點，經過L/2次畫出整條掃描線。線帽繪制模塊510在繪制線帽時，當粗線斜率的絕對值小于1時，生成粗線的左線帽和右線帽，當粗線斜率的絕對值大于1時，生成粗線的上線帽和下線帽。
以上方法實施例中描述的多個細節同樣適用于該裝置實施例，為了避免不必要的重復，省略了對相同部分的重復描述。
另外，圖6示出了本發明實施例的線帽的連接效果圖，其中，在生成折線和多邊形時粗線的端頭需要平滑連接；圖7示出了使用本發明畫粗線生成多邊形時的效果圖，在實際應用中可以滿足地理圖形描畫的效果要求。
以下的表3示出了本發明同現有技術在畫長粗線生成運算時間方面的比較。先對隨機產生的100,000條平均長度為500像素、寬度為10個像素的粗線進行描畫，使用微軟的GDI函數MoveToEx、LineTo來描畫使用的時間為16090-70＝16020ms，使用本發明的查表掃描線法來描畫使用的時間為4150-70＝4080ms，加速比為16020/4080＝3.9265。表3中記錄了算法速度測試結果，共測10次。測試環境為Pentium 4，x86 Family 6 Model 8 Stepping 3，GenuineIntel，Win2000。
表3
表4是本發明同現有技術在畫短粗線多邊形生成運算時間方面的比較。描畫一般的地理圖形所使用的粗線段線寬通常小于10個像素，并且由于便攜式移動式設備的顯示屏不大，不超過480×640像素，又因為要逼近圖形輪廓，因此都是比較短的粗折線，所以寬度不大的短折線在地圖的粗線描畫中極大的比例。表4記錄了對不同線寬的五邊形生成進行對比測試的結果，對五邊形重復生成10000次，五邊形平均邊長為60像素左右，表中的每個數值都是測量10次取平均結果。測試環境為Pentium 4，x86 Family 6 Model 8 Stepping3，Genuine Intel，Win2000。
表4
圖8示出了本發明的線帽描畫方法的缺陷。本方法在線帽連接處會因粗線掃描線寬不同而產生不光滑的毛刺，在水平線與45度線相交時效果最差，圖8表示了這種情況下的效果。因為在嵌入式設備上實際地理圖形描畫應用中使用的線寬一般不會超過15個像素，因此可以接受。
這樣，通過本發明，實現了粗線的快速生成，從而提高了圖形系統的效率。
以上所述僅為本發明的優選實施例而已，并不用于限制本發明，對于本領域的技術人員來說，本發明可以有各種更改和變化。凡在本發明的精神和原則之內，所作的任何修改、等同替換、改進等，均應包含在本發明的保護范圍之內。
權利要求
1.一種粗線生成方法，其特征在于，包括步驟一，預先生成線寬增量表，其中，所述寬度增量表中包含線寬預定時四個斜率區間對應的線寬增量；步驟二，根據粗線端點的坐標值通過快速移位比較確定粗線的斜率區間；步驟三，根據在所述步驟二中得到的斜率區間和線寬，在所述寬度增量表中查找相應的線寬增量，將線寬和線寬增量相加得到掃描線長度L；步驟四，用“兩點-對稱”畫線算法每次計算生成一個點時，以當前點為中點掃描出一條水平或垂直的線，對稱掃描，掃描行程為所述掃描線長度L的一半；以及步驟五，繪制線帽。
2.根據權利要求1所述的粗線生成方法，其特征在于，在所述步驟一中，根據斜率的中值來計算所述寬度增量。
3.根據權利要求2所述的粗線生成方法，其特征在于，根據等誤差中值來計算所述寬度增量，其中，所述等誤差中值為按斜率值取得的斜率區間正中間時的斜率值。
4.根據權利要求2所述的粗線生成方法，其特征在于，根據等概率中值來計算所述寬度增量，其中，所述等概率中值為按等角取得的斜率區間正中間時的斜率值。
5.根據權利要求1所述的粗線生成方法，其特征在于，在所述步驟一中，在生成所述線寬增量表時，每隔4個像素進行一次線寬增量計算。
6.根據權利要求1至5中任一項所述的粗線生成方法，其特征在于，在所述線寬增量表中，所述四個斜率區間為(0，1/4)、(1/4，1/2)、(1/2，3/4)、(3/4，1)，并且所述線寬增量表中進一步包括與所述四個斜率區間對應的SLOPE值。
7.根據權利要求6所述的粗線生成方法，其特征在于，在所述步驟三中，根據確定的所述斜率區間在所述線寬增量表中查找其對應的SLOPE值，然后，根據所述線寬的四分之一的值和查找的所述SLOPE值，從所述線寬增量表中查找對應的線寬增量。
8.根據權利要求1所述的粗線生成方法，其特征在于，在所述步驟四中，從掃描線的兩頭同時開始畫線，一次畫兩個點，經過L/2次畫出整條掃描線。
9.根據權利要求1所述的粗線生成方法，其特征在于，在所述步驟五中，在繪制線帽時，一次畫四個點。
10.根據權利要求1所述的粗線生成方法，其特征在于，在所述步驟五中，在繪制線帽時，當粗線斜率的絕對值小于1時，生成粗線的左線帽和右線帽，當粗線斜率的絕對值大于1時，生成粗線的上線帽和下線帽。
11.一種粗線生成裝置，其特征在于，包括線寬增量表生成模塊，用于生成線寬增量表，其中，所述寬度增量表中包含線寬預定時四個斜率區間對應的線寬增量；斜率區間確定模塊，用于根據粗線端點的坐標值通過快速移位比較確定粗線的斜率區間；掃描線長度確定模塊，用于根據所述斜率區間確定模塊確定的斜率區間和線寬，在所述寬度增量表中查找相應的線寬增量，將線寬和線寬增量相加得到掃描線長度L；畫線模塊，用于用“兩點-對稱”畫線算法每次計算生成一個點時，以當前點為中點掃描出一條水平或垂直的線，對稱掃描，掃描行程為所述掃描線長度L的一半；以及線帽繪制模塊，用于繪制線帽。
12.根據權利要求11所述的粗線生成裝置，其特征在于，所述線寬增量表生成模塊根據斜率的中值來計算所述寬度增量，并且在生成所述線寬增量表時，每隔4個像素進行一次線寬增量計算。
13.根據權利要求11所述的粗線生成裝置，其特征在于，所述掃描線長度確定模塊根據所述斜率區間確定模塊確定的所述斜率區間在所述線寬增量表中查找其對應的SLOPE值，然后，根據所述線寬的四分之一的值和查找的所述SLOPE值，從所述線寬增量表中查找對應的線寬增量。
14.根據權利要求11所述的粗線生成裝置，其特征在于，所述畫線模塊從掃描線的兩頭同時開始畫線，一次畫兩個點，經過L/2次畫出整條掃描線；所述線帽繪制模塊在繪制線帽時，當粗線斜率的絕對值小于1時，生成粗線的左線帽和右線帽，當粗線斜率的絕對值大于1時，生成粗線的上線帽和下線帽。
全文摘要
本發明提供了一種粗線生成方法及裝置，上述方法包括以下處理步驟一，預先生成線寬增量表，其中，寬度增量表中包含線寬預定時四個斜率區間對應的線寬增量；步驟二，根據粗線端點的坐標值通過快速移位比較確定粗線的斜率區間；步驟三，根據在步驟二中得到的斜率區間和線寬，在寬度增量表中查找相應的線寬增量，將線寬和線寬增量相加得到掃描線長度L；步驟四，用“兩點－對稱”畫線算法每次計算生成一個點時，以當前點為中點掃描出一條水平或垂直的線，對稱掃描，掃描行程為掃描線長度L的一半；步驟五，繪制線帽。通過本發明，實現了運算量小且連接效果好的粗線快速生成方案，提高了圖形系統的效率。
文檔編號G01C21/26GK101093584SQ20071013805
公開日2007年12月26日 申請日期2007年8月2日 優先權日2007年8月2日
發明者黨茂昌 申請人:中興通訊股份有限公司
專業數控銑床產品供應商
20年生產經驗，實力工廠，精工品質，質量有保障
