資源描述：
《計算機圖形學 ppt課件.ppt》由會員上傳分享，免費在線閱讀，更多相關內容在教育資源-天天文庫。
1、計 算 機 圖 形 學第四章基本圖形生成算法引 言光柵顯示器可以看做一個像素的矩陣，每個像素可以用一種或多種顏色顯示，在顯示器上顯示的任何一種圖形，實際上都是一種或多種像素的集合。確定一個像素集合及其顏色，用于顯示一個圖形的過程，稱為圖形的掃描轉換或光柵化。過程：確定有關像素→對像素進行寫操作（設備驅動程序實現(xiàn)）主要工作：確定最佳逼近于圖形的像素集裁剪和反走樣基本的圖形生成算法直線的掃描轉換圓和橢圓的掃描轉換填充算法線寬和線型字符裁剪反走樣直線直線是基本的、常用的圖形元素。9/20/2021繪制直線的要求生成的直線要直：選擇最靠近直線的可尋址點來逼近直線。理想的繪制9/20
2、/2021繪制直線的要求起點和終點要準：在繪制直線的過程中由于受精度的影響，所繪直線的終點與原終點有一個累積誤差，導致直線的終點不準。9/20/2021繪制直線的要求直線的粗細要均勻：由于選點不均勻，造成直線粗細不均勻，直觀上反映出直線的亮度不均勻9/20/2021實際繪制9/20/20214.1直 線 的 掃 描 轉 換一個像素線寬的直線的掃描轉換逐點比較法數(shù)值微分法(DDA)中點畫線法Bresenham畫線算法1.逐點比較法算法的基本思想：在繪制直線的過程中，每繪制一個點，就與原直線進行比較，根據(jù)比較的結果決定下一步的走向，這樣一步一步逼近直線。保證要繪制的點盡可能的靠近
3、直線而不發(fā)生遠離直線的趨向。9/20/2021繪制思路由一個點到下一個點的走法是只在X方向或Y方向走一步。9/20/2021計算偏差（確定X和Y的最大走向）??這里X是最大的走向。K1K2(xA,yA)(7,5)?’9/20/2021設?=tg?-tg?于是有1)?=0，點在直線上；2)?>0，點在直線上方；3)?<0，點在直線下方。設偏差計算公式為：9/20/2021偏差計算可以簡化為根據(jù)計算出偏差，然后確定下一步的走向。以直線(0,0)-(7,5)為例，初始：x0=0,y0=0,則F0=0第一步：第二步：=F0-YA=F1+XA9/20/2021偏差遞推公式1）時，走X方
4、向一步，即2）時，走Y方向一步，即9/20/2021偏差遞推公式以上討論的是起點為原點，X為最大步長方向的情況，對于起點是任意點，最大步長方向為其他情況下的繪制直線的偏差計算和偏差判別，自行推導。終點判別判別終點的方法：設立計數(shù)器，計數(shù)取X或Y方向的最大增量值（計長方向），在計長方向每走一步，計數(shù)器減1，直到計數(shù)器值為零為止。9/20/2021繪制直線9/20/20212.數(shù)值微分法DDA(DigitalDifferentialAnalyzer)該算法是建立在微分方程的基礎上。由點(xA,yA)到點(xB,yB)的直線段滿足的微分方程為：9/20/2021因此有則有令有9/2
5、0/2021直 線 的 掃 描 轉 換原理:k＝(y1-y0)/(x1-x0)對于點(x,y),每步遞增1，計算y=kx+B,取:(x,[y])(x1,y1)(x0,y0)(x,y)xx1xx0y直觀又可行但效率低下：一個浮點乘法和一個舍入運算直 線 的 掃 描 轉 換數(shù)值微分法改進算法:yi+1=kxi+1+B=k(xi+Δx)+B=kxi+B+kΔx=yi+kΔx=yi+Δy當Δx=1時,有yi+1=yi+kDDA繪制的直線9/20/2021直 線 的 掃 描 轉 換數(shù)值微分法(程序)DDAline(x0,y0,x1,y1,color)intx0,y0,x1,y1,col
6、or{intx;floatk,y;k=(y1-y0)/(x1-x0);y=y0for(x=x0,x<=x1,x++){Putpixel(x,int(y+0.5),color)y=y+k}}舉例用DDA方法掃描轉換連接兩點P0（0,0）和P1（5,2）的直線段動畫演示：數(shù)值微分畫線算法（DDA）xint(y+0.5)y+0.5000100.4+0.5210.8+0.5311.2+0.5421.6+0.5直 線 的 掃 描 轉 換3.中點畫線法原理（0<斜率<1）:MPP1P2P(xp,yp)P1(xp+1,yp),P2(xp+1,yp+1)M(xp+1,yp+0.5)Q直 線
7、的 掃 描 轉 換F(x,y)=ax+by+c=0對于在直線上的點，F(xiàn)(x,y)=0;在直線上方的點，F(xiàn)(x,y)>0;在直線下方的點，F(xiàn)(x,y)<0將M代入上式,判斷F(M)>0或者F(M)<0MPP1P2Q中點畫線法由直線一般方程有:MP1P2Q直 線 的 掃 描 轉 換P(xp,yp),P1與P2的中點M(xp+1,yp+0.5)d=F(M)=F(xp+1,yp+0.5)=a(xp+1)+b(yp+0.5)+ci.若d>0，即M在直線線上方時，取P1點，則d1=F(xp+2,yp+0.5)=a(
