圖形設(shè)備、系統(tǒng)和應(yīng)用

1、第四章大體圖形生成算法一、直線的掃描轉(zhuǎn)換1 .數(shù)值微分算法直接利用直線方程法、DDA算法(增量算法)優(yōu)勢：DDA算法比直接用直線方程的方式快：沒有浮點(diǎn)乘法:缺點(diǎn)：求每一個(gè)持續(xù)點(diǎn)時(shí)，需要浮點(diǎn)加法；加舍尾取整，無益于硬件實(shí)現(xiàn)：表示長直線時(shí)，由于精度限制一累計(jì)誤差;2 .中點(diǎn)畫線法原理：一、確信與直線距離最近的點(diǎn)P；二、利用點(diǎn)P確信下一個(gè)點(diǎn)3 .Brescnham畫線算法算法大體思想：每次迭代在增量最大方向上均走一步，其方向由增量的正負(fù)而定，另一方向上是不是也走，取決于計(jì)算出來的點(diǎn)與直線上的點(diǎn)的誤差，依照誤差決定是不是走一步。例如取X方向?yàn)樽畲笤隽糠较?，那么?1 =芍+1 j+i = y,+.=絲

2、Ar有:其中。4帆v 1算法優(yōu)勢：-快速增量算法；-要取得準(zhǔn)確的數(shù)學(xué)結(jié)果，只需通過整數(shù)的加、減法和乘2運(yùn)算：運(yùn)算機(jī)中乘2能夠容易的通過算術(shù)移位實(shí)現(xiàn)。給出利用Bresenham算法畫斜率介于0到45度之間的直線所需的步驟°-解答：§1、計(jì)算初始值：dx=x2-xl;dy=y2-yl;lncl=2dy;lnc2=2(dy-dx)：d=lncl-dx§二、設(shè)置左下方的端點(diǎn)坐標(biāo)為(x,y),同時(shí)將Xend設(shè)為x的最大值。若是dx<0,那么x=x2,y=y2,Xend=xl.若是dx>0,那么x=xl,y=yl,Xend=x2;§3、在當(dāng)前(x,y)坐

3、標(biāo)畫一個(gè)點(diǎn)；§4、判定整條線段是不是已經(jīng)畫完，若是x=Xend,那么停止：§五、計(jì)算下一個(gè)象素的位置，若是*0,那么d=d+lncl,若是d>=0,那么d=d+lnc2,且y=y+l;§六、增加x：x=x+l;§7、在當(dāng)前的(x,y)坐標(biāo)畫一個(gè)點(diǎn)：§八、轉(zhuǎn)到步驟4：二、圓與橢圓的掃描轉(zhuǎn)換1、圓的掃描轉(zhuǎn)換兩種直接離散方式：x = RcosOy = RsinO離散點(diǎn)6B皿22c2離散角度E(七，H =力2-42)尤(x y,j(round(R cosgsing)利用隱函數(shù)方程X+J=R-利用參數(shù)方程2、resenham畫圓算法僅考慮圓心在原點(diǎn)

4、，半徑為R的第一象限上的一段圓弧。且取(O,R)為起點(diǎn)，按順時(shí)針方向(+x,-y方向)繪制該1/4圓弧。算法原理：從當(dāng)前點(diǎn)亮象素(x,y)動(dòng)身，按順時(shí)針方向生成圓時(shí)，最正確逼近該圓的下一個(gè)象素只可能為H、D、V三象素之一。H、D、V中距圓周邊界距離最小者，即為所求的象素點(diǎn)：H、D、V三點(diǎn)到圓心的距離平方與圓的半徑平方差，即為H、D、V到圓弧距離的一種氣宇：為依照這些氣宇值可確信最正確象素點(diǎn)，第一，將H、D、V與理想圓弧的關(guān)系進(jìn)行分類。存在以下五種情形：1)H、D、V全在圓內(nèi)：2) H在圓外,D、V在圓內(nèi)；3) D在圓上，H在圓外，V在圓內(nèi)：4) H、D在圓外，V在圓內(nèi)：5) H、D、V全在圓外

5、。§習(xí)題：利用Bresenham算法掃描轉(zhuǎn)換圓的步驟是什么?§解答：一一、設(shè)置初始變量(h,k)二圓心坐標(biāo)；x=0;y二圓的半徑r：d=3-2r;- 二、測試整個(gè)圓是不是已經(jīng)掃描轉(zhuǎn)換完。若是x>y那么停止：- 3、以中心(h,k)為對稱點(diǎn)，對當(dāng)前的(x,y)坐標(biāo)畫8個(gè)圓上的點(diǎn)：Plot(x+h,y+k);plot(-x+h,-y+k);plot(y+h,x+k);plot(-y+h,-x+k)Plot(-y+h,x+k);plot(y+h,-x+k);plot(-x+h,y+k);plot(x+h,-y+k);- 4、計(jì)算下一個(gè)象素的位置,若是d<0,那么d=d

6、素x+6,和x=x+l.若是d>=0,那么d=d+4(x-y)+l若x=x+一、y=y-l.- 五、轉(zhuǎn)到步驟2；§習(xí)題：當(dāng)利用8路對稱方式從。度到45度或90度到45度的8分圓中生成整個(gè)圓時(shí)，有些象素被設(shè)置或畫了兩次，這種現(xiàn)象成為重?fù)?。請說明如何判定重?fù)舭l(fā)生？§解答：- 在初始坐標(biāo)為(r,0)或(0,r)時(shí)的位置。因?yàn)?0,r)二(-0,r),(0,-r)=(-0,-r),(r,0)=(r,-0),(-r,0)=(-r,-0);- 若是最后生成的象素在對角線上，坐標(biāo)為(ar,ar),其中a約為，那么在(ar,ar)、(-ar,ar)、(ar,-ar)、(-ar,-ar

7、)處會(huì)發(fā)生重?fù)簦?#167;習(xí)題：重?fù)舫速M(fèi)時(shí)刻外還有其它壞處嗎？§解答：-通?？刹荒苡袉栴}：-可是若是直接操縱輸出設(shè)備，可能有問題3、橢圓的掃描轉(zhuǎn)換§橢圓的中點(diǎn)算法-算法原理一一、上半部份：§M(Xi+1,一二、下半部份：(Xi+,Yi-1)§注意：-上半部份的終止判別；-下半部份誤差項(xiàng)的初值；§算法步驟：- 1.輸入橢圓的長半軸a和短半軸b;- 2.計(jì)算初始值d=b2+a2(-b+、x=0、y=b;- 3.繪制點(diǎn)(x,y)及其在四分象限上的另外三個(gè)對稱點(diǎn)；- 4.判定d的符號。假設(shè)dWO,先將d更新為d+b2(2x+3),再將(x,y)更新

8、為(x+l,y)；不然將d更新為d+b2(2x+3)+a2(-2y+2)»再將(x,y)更新為(x+1,y-1);- 5.當(dāng)b2(x+l)<a2時(shí)，重復(fù)步驟3和4。不然轉(zhuǎn)到步驟6;- 6.用上半部份計(jì)算的最后點(diǎn)(x,y)來計(jì)算下半部份中d的初值：- 7.繪制點(diǎn)(x,y)及其在四分象限上的另外三個(gè)對稱點(diǎn)；- 8.判定d的符號：§假設(shè)dWO,那么先將d更新為b2(2xi+2新為(-2yi+3),再將(x,y)更新為(x+1,y-1)：§不然先將d更新為d+a2(-2yi+3),再將(x,y)更新為(x,y-1);- 9.當(dāng)y>0時(shí)，重復(fù)步驟7和8。不然終止

9、；三、區(qū)域填充1、多邊形域的填充§多邊形的表示方式：一極點(diǎn)表示：用多邊形的極點(diǎn)序列刻劃多邊形；一點(diǎn)陣表示：用位于多邊形內(nèi)象素的集合來刻劃多邊形；-掃描轉(zhuǎn)換多邊形：將極點(diǎn)表示形式轉(zhuǎn)換成點(diǎn)陣表示形式:§三種方式：逐點(diǎn)判定法；掃描線算法；邊緣填充法：逐點(diǎn)判定法逐個(gè)判定畫圖窗口內(nèi)的像素：如何判定點(diǎn)在多邊形的內(nèi)外關(guān)系？1)射線法；2)累計(jì)角度法；3)編碼法；射線法步驟：1)從待判別點(diǎn)v發(fā)出射線；2)求交點(diǎn)個(gè)數(shù)k;3)K的奇偶性決定了點(diǎn)與多邊形的內(nèi)外關(guān)系；4)奇異情形處置；累計(jì)角度法編碼方式：累計(jì)角度方式的離散方式結(jié)論：逐點(diǎn)判定法程序簡單，速度太慢，效率低。2、邊填充算法：算法1(以掃

10、描線為中心的邊填充算法)：§一、將當(dāng)前掃描線上的所有象素著上顏色:§二、求余：for(i=0;i<=m;i+)在當(dāng)前掃描線上從橫坐標(biāo)為Xi的交點(diǎn)向右求余：算法2(以邊為中心的邊填充算法)：§一、將畫圖窗口的背景色設(shè)置：§二、對多邊形的每一條非水平邊做：從該邊上的每一個(gè)象素開始向右求余；結(jié)論：§適于具有幀緩存的圖形系統(tǒng)。處置后，按掃描線順序讀出幀緩存的內(nèi)容，送入顯示設(shè)備：§優(yōu)勢：算法簡單：§缺點(diǎn)：關(guān)于復(fù)雜圖形，每一象素可能被訪問多次，輸入/輸出的量比掃描線算法大得多：§邊標(biāo)志算法：分為兩步驟：- 第一步，對多邊

11、形的每條邊進(jìn)行直線掃描轉(zhuǎn)換，亦即對多邊形邊界所通過的象素打上邊標(biāo)志；- 第二步，填充。對每條與多邊形相交的掃描線，依從左到右順序，逐個(gè)訪問該掃描線上象素。利用一個(gè)布爾量inside來指示當(dāng)前點(diǎn)的狀態(tài)，假設(shè)點(diǎn)在多邊形內(nèi)，那么inside為真。假設(shè)點(diǎn)在多邊形外，那么inside為假。inside的初始值為假，每鐺鐺前訪問象素為被打上邊標(biāo)志的點(diǎn)，就把inside取反。對未打標(biāo)志的象素,inside不變。假設(shè)訪問當(dāng)前象素時(shí)，對inside作必要操作以后，inside為真，那么把該象素置為多邊形色。3、圓域的填充§將多邊形區(qū)域填充原理推行到圓域的填充:- 1)計(jì)算每條掃描線與圓域的相交區(qū)間；-

12、 2)把區(qū)間內(nèi)象素用指定顏色填充：§相交區(qū)間的確信：- 中點(diǎn)畫圓法一計(jì)算交點(diǎn)一確信相交區(qū)間：- 函數(shù)F的計(jì)算能夠采納增量法提高效率四、線寬與線型的處置1、直線線寬處置一線刷子：垂直刷子、水平刷子：一線刷子特點(diǎn)(1/2)§實(shí)現(xiàn)簡單、效率高。§斜線與水平(或垂直)線不一樣粗。§當(dāng)線寬為偶數(shù)個(gè)象素時(shí)，線的中心將偏移半個(gè)象素。§問題：利用線刷子生成線的始結(jié)尾老是水平或垂直的，看起來不太自然。§解決:添加''線帽(linecap)”一線刷子特點(diǎn)(2/2)§當(dāng)比較接近水平的線與比較接近垂直的線匯合時(shí)，匯合處外角有缺口；&

13、#167;解決：斜角連接(miterjoin)、圓連接(roundjoin),斜切連接(beveljoin);一方刷子：-特點(diǎn):方刷子繪制的線條(斜線)比用線刷子所繪制的線條要粗一些；方刷子繪制的斜線與水平(或垂直)線不一樣粗；方刷子繪制的線條自然地帶有一個(gè)“方線帽”；2、曲線線寬處置一線刷子一方刷子§要顯示一致的曲線寬度可通過旋轉(zhuǎn)刷子方向，使其在沿曲線移動(dòng)時(shí)與斜率方向一致；- 圓弧刷子§采納填充的方法3、線型的處置§直線線型處置- 實(shí)心段和中間空白段的長度（象素?cái)?shù)量）可用象素模板（pixelmask）指定：-存在問題：如何維持任何方向的劃線長度近似地相等？- 解

14、決：依照線的斜率來調(diào)整實(shí)心段和中間空白段的象素?cái)?shù)量：§曲線線型處置- 采納象素模板的方式：五、字符1、矢量字符§對每一個(gè)字符概念矢量代碼序列描述字符的幾何形狀：-不同的應(yīng)用利用不同的方式。§以AutoCAD采納的概念方式為例：-AutoCAD采納一種稱為形（SHAPE）的實(shí)體來概念字符-大體筆畫：直線和圓弧-形描述格式如下：*形編號，字節(jié)數(shù)，形名稱字節(jié)1,字節(jié)20形編號：1255整數(shù)：字節(jié)數(shù)：形概念描述行中包括終止符0在內(nèi)的字節(jié)數(shù)量；形名稱：用大寫字母；不然以為是形的說明性信息，不存儲(chǔ)：字3N：概念字符組成矢量的方向和大小，分為標(biāo)識(shí)位、低四位和高四位三組數(shù)字。標(biāo)識(shí)

15、位表示十六進(jìn)制（0）或十進(jìn)制（無標(biāo)識(shí)位）；高四位表示矢量的長度，低四位表示矢量方向。如：040即表示一16進(jìn)制數(shù)，其中，4表示矢量的長度，。表示矢量方向。§實(shí)例：二極管符號:§*133,11,DID0E040,044,04c,042,04c,040,048,04c,046,04c,0§把每一個(gè)字符都按上述方式描述后，存入一形文件中，即成立了相應(yīng)的矢量字符庫。2、點(diǎn)陣字符§每一個(gè)字符概念成稱為字符掩膜的矩陣：§西文字符：5X7的點(diǎn)陣字符：§漢文字符：16X16的點(diǎn)陣字符；§打?。?4X24,40X40,72X72的點(diǎn)陣字符&#

16、167;特殊字符：按需確信。3、字型技術(shù)節(jié)約空間，采納緊縮技術(shù)（字型數(shù)據(jù)緊縮存儲(chǔ)，利歷時(shí)，還原成字符點(diǎn)陣）：-黑白段緊縮法：§優(yōu)勢：簡單快速不失真；§缺點(diǎn)：緊縮較差，不方便，一樣用于低級文字處置系統(tǒng)：一部件緊縮法：§優(yōu)勢：緊縮比大§缺點(diǎn)：字型質(zhì)量不保證；- 輪廓字型法：緊縮比大，質(zhì)量保證（采納直線、BEZIER曲線的集合描述字符的輪廓線）；- 輪廓線和操縱信息（屬性、操縱點(diǎn)/線）組成緊縮數(shù)據(jù)，結(jié)合填充算法以取得較好的成效；4、字符的輸出- 畫圖儀輸出：方向、位移值轉(zhuǎn)換為設(shè)備驅(qū)動(dòng)指令：- 顯示器/打印機(jī)輸出：指定字符掩膜的原點(diǎn)與幀緩存中的字符左下腳位置對應(yīng)

17、，從而將字符掩膜中的值平移的寫入幀緩存中；六、裁剪1、線段裁剪§線段裁剪方式：-Cohen-SutherLand裁減算法-中點(diǎn)分割算法：-參數(shù)化方式§Cohen-SutherLand算法的改良：編碼算法- 目的：對顯然不可見線段實(shí)現(xiàn)快速判別：- 編碼方式：由窗口四條邊所在直線把二維平而分成9個(gè)區(qū)域，每一個(gè)區(qū)域給予一個(gè)四位編碼，CtCbCrCi，上下右左§Nicholl-Lee-Nicholl算法- 目的：通過對二維平面的更詳細(xì)劃分，排除Cohen.Sutherland算法中線段在被裁剪時(shí)需多次求交的情形。§中點(diǎn)分割法- 思想：從P0點(diǎn)動(dòng)身找出距P0最近的

18、可見點(diǎn)，從P1點(diǎn)動(dòng)身找出距P1最近的可見點(diǎn)。- 取中點(diǎn)Pm=（Pl+P2）/2§參數(shù)化方式-思想：利用數(shù)學(xué)上線段的參數(shù)方程；-如：考慮凸多邊形R和線段P1,計(jì)算線段落在區(qū)域R中的部份，上述算法簡化為Liang-Barsky算法四種算法比較：-Cohen-Sutherland與中點(diǎn)法在區(qū)碼測試時(shí)期能以位運(yùn)算方式高效率進(jìn)行一大多數(shù)線段能夠簡單地取舍時(shí)，效率較好；-Cyrus-Beck（參數(shù)化方式）：在多數(shù)線段需要進(jìn)行裁剪時(shí)效率高：因?yàn)檫\(yùn)算只涉及到參數(shù)，僅僅必要時(shí)才進(jìn)行坐標(biāo)計(jì)算；-LiangBarsky算法只能應(yīng)用在矩形窗口情形，效率比參數(shù)化方式更高.2、多邊形裁剪§Suther

19、land-Hodgman算法（逐邊裁剪算法）：-分割處置策略：將多邊形關(guān)于矩形窗口的裁剪分解為多邊形關(guān)于窗口四邊所在直線的裁剪:- 流水線進(jìn)程（左上右下）：左f則的結(jié)果是上邊的開始；- 內(nèi)側(cè)空間與外側(cè)空間；- 多邊形的邊與裁減線形成空間的關(guān)系- 多邊形各邊與裁減線的四種位置關(guān)系:§S,P與裁剪線同側(cè)：一同在可見一側(cè)；一同在不可見一側(cè)；§S,P與裁剪線不同側(cè):- S可見，P不可見；- S不可見，P可見：結(jié)論：一裁剪算法采納流水線方式，適合硬件實(shí)現(xiàn):一可推行到任意凸多邊形裁剪窗口：Weiler-Athenton算法（內(nèi)裁剪方式）- 裁剪窗口為任意多邊形（凸、凹、帶內(nèi)環(huán)）的情形：- 主多邊形：被裁剪多邊形，記為A- 裁剪多邊形：裁剪窗口，記為B- 算法（內(nèi)裁剪）步驟：§一、成立主多邊形和裁剪多邊的極點(diǎn)表.§二、求主多邊形和裁剪多邊形的交點(diǎn)，并將這些交點(diǎn)按順序插入兩多邊形的極點(diǎn)表中。在兩多邊表形極點(diǎn)表中的相同交點(diǎn)間成立雙向指針。§3、裁剪：若是存在沒有被跟蹤過的交點(diǎn)，執(zhí)行以下步驟：- （1）成立裁剪結(jié)果多邊形的極點(diǎn)表.- （2）選取任一沒有被跟蹤過的交點(diǎn)為始點(diǎn)，將其輸出