圓橢圓多邊形和字符串等曲線及一些其他的復雜圖形均可用線段課件

1、甘朝華第三章 基本圖元的生成3.1線段的生成3.2圓的生成3.3區(qū)域填充3.4字符的生成3.5其他曲線3.6 圖元屬性控制3.7 反走樣基本圖元復雜圖形組合、變換 基本圖元的生成算法研究是計算機圖形學的基本問題之一。 基本的二維圖元有點、線段、圓、橢圓、多邊形和字符串等。 曲線及一些其他的復雜圖形均可用線段或多邊形擬合得到。光柵掃描轉(zhuǎn)換理解所有算法過程的思維主線：（1）該問題在數(shù)學或幾何上的意義是什么，相應的數(shù)學計算公式是什么；（2）在光柵顯示器上每一個像素點都占據(jù)一定的空間；（3）生成某種圖形的算法可能有多種，可以根據(jù)使用場合不同，用某些指標來衡量算法的效能。3.1 線段的生成數(shù)學基礎： 設

2、線段的2個端點為（xs,ys）和（xe,ye），直線的斜率截距方程為：y=mx+b （3.1）3.1 線段的生成 數(shù)字微分分析法（digital differential analyzer，簡稱DDA）是一種線段掃描轉(zhuǎn)換算法。3.1.1 DDA畫線算法 在圖形生成算法中由于幾何圖形在空間位置上具有連貫性，成為多種圖形生成算法的基本思想。 基于這種思想的圖形繪制算法中所需要解決的問題就是如何確定后一個像素點。（中點畫線、Bresenham畫線、中點畫圓、Bresenham畫圓）。3.1 線段的生成3.1.2 中點畫線算法幾何圖形在空間位置上具有連貫性：（1）根據(jù)圖形的幾何方程式構(gòu)造判斷條件（即判

3、別式），根據(jù)判斷條件的值與0之間的關(guān)系可以確定下一個圖形取值點的坐標；（2）根據(jù)坐標增量規(guī)律計算判別條件之間的遞推關(guān)系，并確定在起點坐標處的初始判別條件值；（3）觀察判別條件中有無可能進行一些調(diào)整來減少運算的復雜程度。3.1 線段的生成3.1.2 中點畫線算法3.1 線段的生成3.1.2 中點畫線算法3.1 線段的生成處理方法分析優(yōu)化計算過程程序?qū)崿F(xiàn)3.1.2 中點畫線算法3.1 線段的生成算法思想： 假定線段位于第一象限（m0，1），其它象限雷同。3.1.3 Bresenham畫線算法3.1 線段的生成算法思想：3.1.3 Bresenham畫線算法3.1 線段的生成兩頭并進算法、雙步算法、

4、N步畫線算法 利用并行計算機進行并行處理也是提高畫線速度的一種方式。 通過某種分割方法將線段分解成若干部分，并分配到多個處理器上分別進行線段像素位置計算。3.1.4 并行畫線算法3.2 圓的生成 圓是一種常用圖元，由于其具有8子象限對稱性，因此在下面的討論中只要生成其某一個子象限的圓弧，就可根據(jù)其對稱性畫出整個圓。3.2 圓的生成直角坐標法極坐標法圓的8對稱性3.2.1 圓的特性3.2 圓的生成 中點畫圓算法與中點畫線算法類似，只是構(gòu)造判別式有所不同。3.2.2 中點畫圓算法3.2 圓的生成3.2.3 Bresenham畫圓算法3.3 區(qū)域填充填充區(qū)域（fill area）: 由一定的邊界圍成

5、的一個區(qū)間，其內(nèi)部用某種顏色或圖案進行填充。 填充區(qū)域的邊界可有多種形式，如圓形、折線、不規(guī)則曲線等，但規(guī)定在計算機圖形學中只用多邊形來表示填充區(qū)域。3.3 區(qū)域填充凸（convex）多邊形凹（concave）多邊形內(nèi)角3.3.1 多邊形分類與識別3.3 區(qū)域填充1.識別凹多邊形3.3.1 多邊形分類與識別3.3 區(qū)域填充2.分割凹多邊形 向量法（vector method） 旋轉(zhuǎn)法（rotational method）3.3.1 多邊形分類與識別3.3 區(qū)域填充多邊形有兩種表示方法： 頂點表示 點陣表示3.3.2 掃描線填色算法3.3 區(qū)域填充區(qū)域填充的過程可以分為兩步：（1）確定哪些像素屬

6、于區(qū)域內(nèi)部，哪些屬于區(qū)域外部；（2）對屬于區(qū)域內(nèi)部的像素，按所要求的填充色或圖案來填充對應的像素。3.3.2 掃描線填色算法3.3 區(qū)域填充填充算法分為兩大類：（1）掃描線填充算法（scan-line filling）（2）種子填充算法（seed filling）3.3.2 掃描線填色算法3.3 區(qū)域填充1.掃描交點奇偶數(shù)判斷法3.3.2 掃描線填色算法3.3 區(qū)域填充2.改進的掃描線填充算法頂點計數(shù)問題處理掃描線與相交邊求交點減少求交計算量-活性邊表3.3.2 掃描線填色算法3.3 區(qū)域填充2.改進的掃描線填充算法3.3.2 掃描線填色算法3.3 區(qū)域填充3.3.3 種子填色算法3.3 區(qū)域

7、填充1. 堆棧式種子像素填充法3.3.3 種子填色算法3.3 區(qū)域填充2.四鄰法種子填充算法3.3.3 種子填色算法3.3 區(qū)域填充 完整的OpenGL多邊形是用glBegin、glEnd之間所描述的頂點集合來描述，多邊形的形狀由glBegin函數(shù)中參數(shù)的6種不同的符號常量來決定。 1.多邊形形狀描述常量 2.像素陣列函數(shù)3.3.4 OpenGL多邊形區(qū)域填充函數(shù)、像素陣列函數(shù)3.3 區(qū)域填充1.多邊形形狀描述常量3.3.4 OpenGL多邊形區(qū)域填充函數(shù)、像素陣列函數(shù)3.3 區(qū)域填充2.像素陣列函數(shù) 像素陣列是多邊形填充的一種形式，它是用一個圖像陣列重復填充一個多邊形的內(nèi)部。 兩類：由彩色像

8、素構(gòu)成的陣列稱為一個像素圖（pixmap）; 陣列每個像素的值為0或1的像素陣列稱為位圖（bitmap），其顏色構(gòu)成只有黑、白兩種。3.3.4 OpenGL多邊形區(qū)域填充函數(shù)、像素陣列函數(shù)3.4 字符的生成 字符是圖形中的主要組成部分，主要用來作為圖形表達意義的補充形式。3.4 字符的生成 在點陣字庫中，每個字符都被定義成字符掩膜的矩陣。3.4.1 點陣式字符3.4 字符的生成 矢量字符記錄字符的筆畫信息而不是整個位圖，具有存儲空間小、不變形、美觀、變換方便等優(yōu)點。 對于字符的旋轉(zhuǎn)、縮放等變換，點陣字符的變換需要對表示字符位圖中的每一像素進行；而矢量字符的變換只要對其筆畫端點進行變換就可以了。

9、3.4.2 矢量字符3.4 字符的生成 矢量輪廓字符采用直線、二次三次Bezier曲線及提示（Hint）技術(shù)描述字型。3.4.2 矢量字符3.4 字符的生成 OpenGL基本庫僅提供了顯示單個字符和文字串的基本支持。3.4.3 OpenGL字符函數(shù)3.5 其他曲線 許多曲線函數(shù)在對象建模、動畫軌跡的描述、數(shù)據(jù)和函數(shù)的圖形化及其他圖形應用中均是重要的圖元。 常見曲線有圓錐曲線、三角和指數(shù)函數(shù)、概率分布、通用多項式和樣條函數(shù)。3.6 圖元屬性控制 任何影響圖元顯示方式的參數(shù)都可稱為圖元屬性控制參數(shù)，圖元的類型不同其控制參數(shù)類型也有所不同。 一般的屬性控制參數(shù)包括顏色、大小、線型、填充方式、字體、可

10、見性、可檢測性等。3.6 圖元屬性控制3.6.1 顏色3.6 圖元屬性控制 點的屬性一般涉及顏色和大小2個屬性，這些屬性由系統(tǒng)的狀態(tài)變量的當前值決定。3.6.2 點的屬性3.6 圖元屬性控制 直線的基本顯示屬性包括顏色、線寬、線型。其顏色屬性仍由系統(tǒng)狀態(tài)表中當前顏色值決定，線寬和線型需要進行其他處理。3.6.3 線的屬性3.6 圖元屬性控制1 線寬: 標準的直線繪制寬度為1個像素，其他線寬是標準線寬的整數(shù)倍。 在光柵實現(xiàn)中，通過沿相鄰水平線路徑（或相鄰垂直線路徑）繪制額外的像素而得到。3.6.3 線的屬性3.6 圖元屬性控制1 線寬: 缺點: 2個線段在交點處有缺口 線的粗細不一樣 線段的始末

11、端總是水平或垂直的3.6.3 線的屬性3.6 圖元屬性控制1 線寬: 解決方法: 采用斜角連接或圓連接或斜切連接的方式 采用反走樣技術(shù) 采用線帽（方帽、圓帽、突方帽）方法3.6.3 線的屬性3.6 圖元屬性控制2 線型: 線型指定了線段在繪制中的形狀屬性，即構(gòu)成線段的各個像素是否繪制的屬性。實線虛線點線3.6.3 線的屬性3.6 圖元屬性控制填充方式: 實填充 圖形填充 圖案填充 符號填充3.6.4 多邊形填充屬性3.7 反走樣 基本圖元生成算法繪制的非水平且非垂直的直線、多邊形的邊或圓弧、橢圓弧時，會產(chǎn)生鋸齒狀圖形的現(xiàn)象，稱為走樣(aliasing)。3.7 反走樣解決走樣問題的3種方法： 過取樣（s