1、2020/10/8,1,本章內容,直線的掃描轉換 圓與橢圓的掃描轉換 區(qū)域填充 二維裁剪 字符生成 反走樣,2020/10/8,2,三種繪制直線的算法,數(shù)值微分法 原理簡單，實現(xiàn)方便，但在效率上低于后者。 用到了浮點數(shù)運算，不方便硬件實現(xiàn)。 中點畫線法 Bresenham畫線法 后兩種算法都是較為常見的畫線算法。對于直線段來說，兩種方法是等同的和最有效的。,di-ei,2020/10/8,3,第二節(jié) 圓與橢圓的掃描轉換,圓的掃描轉換 中點畫圓算法 Bresenham畫圓算法 內接正多邊形迫近法 橢圓的掃描轉換 中點畫法 若干相關問題,2020/10/8,4,圓的表示,原始定義：,等價定義,20

2、20/10/8,5,代數(shù)離散法,效率低,2020/10/8,6,圓的屬性分析,對稱性,正負劃分性,2020/10/8,7,圓的掃描轉換的數(shù)學模型,找到逼近如下圓弧線的像素點集合:,切線斜率范圍: 取x為自變量,2020/10/8,8,中點畫圓算法的原理,判別量定義:,?: 提高dk計算效率?,增量運算,2020/10/8,9,續(xù)：,浮點數(shù)!,2020/10/8,10,續(xù)：,設:,可替代的高效算法:,則判別量的初值為：,2020/10/8,11,結論,2020/10/8,12,二階差分方法,任意多項式均可使用該方法實現(xiàn)增量計算,類似地:,2020/10/8,13,中點畫圓算法偽代碼,Void M

3、idPointCircle(int r, int color) int x,y,d; x=0;y=r;d=1-r; delta1=3;delta2=5-2r; drawpiexl(x,y,color); while(yx) if(d0) d+=delta1; delta2+=2; else d+=delta2; delta2+=4; y- delta1+=2; x+; drawpiexl(x,y,color); drawotherpiexl(x,y,color); /while /end,2020/10/8,14,Bresenham畫圓算法（1）,原理：選擇與圓心距離與半徑之差較小的一點。,2

4、020/10/8,15,Bresenham畫圓算法(2),2020/10/8,16,Bresenham畫圓算法（3）,以最高點為初始點，計算判別量初值 再根據(jù)判別量的正負確定遞推關系 遞推關系的確定需根據(jù)右圖分別不同情況進行討論（去掉絕對值符號，并進行化簡）,2020/10/8,17,Bresenham畫圓算法（4）,初始值的計算,利用增量計算方法加速判別參數(shù)的計算,注：比較其與中點畫圓算法的判別參數(shù)。,圓的內接正多邊形迫近法,2020/10/8,19,基礎知識（1）-三角函數(shù),2020/10/8,20,基礎知識（2）-矩陣表示,表達式：,可寫成矩陣形式：,2020/10/8,21,基礎知識（

5、3）-矢量及其運算,2020/10/8,22,圓的內接正多邊形迫近法(1),內接正n邊形頂點,圓的多邊形迫近,2020/10/8,23,圓的內接正多邊形迫近法(2),使用增量計算確定多邊形頂點：,同理:,2020/10/8,24,圓的內接正多邊形迫近法(3),上述遞推公式可用矩陣形式表示為：,該遞推公式關于誤差穩(wěn)定。,2020/10/8,25,圓的內接正多邊形迫近法(4),2020/10/8,26,圓的內接正多邊形迫近法(5),改進的增量計算：使用兩個初始點,該遞推公式關于誤差穩(wěn)定,2020/10/8,27,圓的等面積正多邊形迫近法,原理：,圓的等面積正多邊形迫近法示意圖,2020/10/8,

6、28,內容回顧,圓的掃描轉換 中點掃描轉換算法 Bresenham掃描轉換算法 圓的內接正多邊形迫近法 圓的等面積正多邊形逼近法,橢圓的掃描轉換算法,2020/10/8,30,橢圓弧的幾何特點（1）,定義：到兩個定點的距離之和為定長的點的集合。 假設：橢圓中心在坐標原點。,2020/10/8,31,橢圓弧的幾何特點（2）,橢圓弧上一點處的切線,切線斜率,2020/10/8,32,橢圓弧的幾何特點（3）,具有與圓弧類似的屬性： 對稱性 空間的正負劃分性,2020/10/8,33,橢圓的掃描轉換,問題：繪制第一象限內橢圓弧對應的像素點,解決方案:中點掃描轉換算法 算法原理與圓弧的中點掃描轉換算法相

7、同 注意：第一象限內橢圓弧切線斜率跨2范圍： （-1，0以及（-，-1 切線斜率k=-1的點為掃描轉換分割點,2020/10/8,34,第一象限內橢圓弧的劃分,割點位置計算: 切線斜率為1的點 梯度的定義：,等價于計算梯度矢量斜率為1的點,2020/10/8,35,橢圓的中點掃描轉換算法,區(qū)域 1-2條件：下一點滿足,2020/10/8,36,橢圓弧上部的掃描轉換（1）,橢圓弧上部對應的決策參數(shù)：,根據(jù)決策參數(shù)的取值，成立：,2020/10/8,37,橢圓弧上部的掃描轉換（2）,決策參數(shù)的遞推計算,初始條件：,2020/10/8,38,橢圓弧上部的掃描轉換（3）,2020/10/8,39,橢圓

8、弧上部的掃描轉換（4）,2020/10/8,40,橢圓弧上部的掃描轉換（5）,遞推計算過程：,2020/10/8,41,橢圓弧下部的掃描轉換（1）,同理對橢圓弧的下部進行掃描轉換。,2020/10/8,42,橢圓弧下部的掃描轉換（2）,判別參數(shù)的遞推計算:,2020/10/8,43,橢圓弧的掃描轉換,從(0,ry)開始,繪制橢圓弧的上部,采用判別參數(shù)為d1i; 當繪制當前點滿足切線斜率大于-1時,橢圓弧上部繪制完成; 從(rx,0)開始,繪制橢圓弧的下部,采用判別參數(shù)為d2i; 當繪制當前點的坐標與橢圓弧上部的最后一點交叉時,橢圓弧下部繪制完成; 根據(jù)橢圓的對稱性完成整個橢圓的繪制.,2020

9、/10/8,44,若干相關問題(1),曲線的掃描轉換： 一般方法：直線段逼近 注意象素點的等距。為此可使用曲線的參數(shù)表示，或按照曲線斜率選擇自變量，而從顯式表示中生成等距位置點。,正負法： 尤其適合易畫曲線： 具有正負劃分性、平坦性、連續(xù)性 初始定向：起始點切線方向； 前進規(guī)則：正負劃分性確定；,2020/10/8,45,若干相關問題(2),直線繪制算法的并行實現(xiàn)： 任何線生成算法都可以通過線段分割而適用于并行實現(xiàn)。 有足夠多的處理器時，按照屏幕的不同區(qū)域分配處理器。,2020/10/8,46,若干相關問題(3),圖元幾何尺寸的保留： 在掃描轉換過程中注意象素集合的實際尺寸，如線段的始末點坐標

10、的定義。 不同圖元的尺寸變化不同。,2020/10/8,47,若干相關問題（4）,線寬控制 標準線寬的直線被掃描轉換為一個象素寬的直線段。 其它線寬的實現(xiàn)可以采用筆或刷的方式。 通過沿相鄰平行線路徑畫額外的象素可以定義標準線寬的正整數(shù)倍的其它線寬。 線刷子方法實現(xiàn)的線寬控制：分水平和垂直兩種。 垂直線刷子：一般地，對于任意線段，當某點切矢斜率在-1，1之間時，掃描轉換過程是：給定x以固定步長，確定y方向的增量，所以可用垂直線刷子掃過象素，即得到所要求的線段。,水平線刷子：對于其切矢斜率在-1，1之外的線段，可用水平線刷子掃過即可。,2020/10/8,48,線刷子的設計簡單高效。但它存在如圖所

11、示的缺陷。,線刷子方案的缺陷,2020/10/8,49,采用矩形刷子可以避免第一個缺陷 需設計新的數(shù)據(jù)結構以避免象素的重復繪制。,采用畫輪廓線再填充的方法可以避免上述三種缺陷。,解決方案,2020/10/8,50,線型控制 線型屬性：實線、虛線和點劃線等。 線型的實現(xiàn)方式：通過設置沿線路徑顯示的實線段的長度和間距來修改畫線算法得到不同類型的線。 例如：用布爾數(shù)組定義出指定的類型，如間距為5的虛線：1111100000（1表示繪制點，0表示不繪制點），并使其在直線段的有效定義范圍內不斷重復，即掃描轉換后得到的象素點依序與線型定義數(shù)組一一對應，并根據(jù)線型定義數(shù)組決定該象素點的繪制與否。,若干相關問題（5）,2020/10/8,51,線型的精確控制,采用上述固定劃線長度的實現(xiàn)方法會在直線方向定義不同時產生出不等長的劃線段。 原因在于相同個數(shù)的象素沿不同方向將生成不同長度的線段。 為實現(xiàn)精確的線型定義，應按照線的斜率調整線型定義數(shù)組中實線段和空白段的象素數(shù)目。,2020/10/8,52,另一種精確定義線型的方法是：將線上的每一段實劃線作為一段單獨的線段，定位其始末端點坐標，再調用直線的掃描轉換