計(jì)算機(jī)圖形學(xué)第三章

第3章輸出圖元輸出圖元是基本幾何結(jié)構(gòu)。輸出圖元種類：點(diǎn)、直線線段、圓、圓錐曲線、二次曲面、樣條線段、多邊形填色區(qū)域、字符串等。本章內(nèi)容點(diǎn)和線直線段掃描轉(zhuǎn)換DDA算法Bresenham畫線算法中點(diǎn)畫線法圓弧掃描轉(zhuǎn)換Bresenham畫圓算法中點(diǎn)畫圓算法橢圓弧掃描轉(zhuǎn)換填充區(qū)域圖元點(diǎn)和線點(diǎn)和線是計(jì)算機(jī)圖形表示的最簡單的基本圖元點(diǎn)：將應(yīng)用程序的單個(gè)坐標(biāo)位置轉(zhuǎn)換成輸出設(shè)備的相應(yīng)操作，即為畫點(diǎn)操作。直線掃描轉(zhuǎn)換當(dāng)我們對直線進(jìn)行光柵化時(shí)，只能在顯示器所給定的有限個(gè)象素組成的矩陣中，確定最佳逼近于該直線的一組象素，并且按掃描線順序，對這些象素進(jìn)行寫操作，這就是通常所說的用顯示器繪制直線或直線掃描轉(zhuǎn)換。圖形的掃描轉(zhuǎn)換：在光柵顯示器等數(shù)字設(shè)備上確定一個(gè)最佳逼近于圖形的象素集的過程。一般采用整數(shù)值表示屏幕位置，因此，繪制的位置只能接近兩指定端點(diǎn)的實(shí)際線段位置。如（3，3.6），轉(zhuǎn)換為象素點(diǎn)的位置是即（int（3+0.5

），int（3.6+0.5））=（3，4）直線的掃描轉(zhuǎn)換算法直線的繪制要求：直線要直直線上的點(diǎn)要準(zhǔn)確，即無不定向性和斷裂情況直線的亮度、色澤要均勻畫線的速度要快要求不同直線可具有不同的色澤、亮度、線型等提出問題：對于給定直線兩端點(diǎn)P0(x0,y0)和P1(x1,y1)，如何在屏幕上畫出該直線。三個(gè)常用算法：數(shù)值微分法（DDA）Bresenham算法中點(diǎn)畫線法直線基礎(chǔ)直線的笛卡兒斜率截距方程為：m---直線的斜率b---直線于y軸的截距給定線段的兩個(gè)端點(diǎn)（x0,y0),(x1,y1)，可以計(jì)算斜率m和截距b：在x方向上，給定任意增量?x，那么對應(yīng)的y的增量為?y,即?y=m?x圖形學(xué)直線的算法是以上面的直線方程、斜率方程、截距方程和增量方程為基礎(chǔ)數(shù)值微分法（DDA-digitaldifferentialanalyzer）DDA算法是一種線段掃描轉(zhuǎn)換算法，它是在一個(gè)坐標(biāo)軸上以單位間隔對線條取樣，從而確定另一個(gè)軸上最靠近線段路徑的對應(yīng)整數(shù)值。首先考慮斜率值m在（0，1）之間的直線。假定直線的起點(diǎn)、終點(diǎn)分別為：（x0,y0),(x1,y1)，且都為整數(shù)。x、y軸的單位間隔為1柵格交點(diǎn)表示象素點(diǎn)位置如果采用一般計(jì)算方法那么直線斜率為這種方法直觀，但效率太低，因?yàn)槊恳徊叫枰淮胃↑c(diǎn)乘法和一次舍入運(yùn)算。DDA方法思想由即：當(dāng)x每遞增1，y遞增m(即直線斜率)；注意上述分析的算法僅適用于|m|≤1的情形。在這種情況下，x每增加1,y最多增加1。當(dāng)|m|>1時(shí)，必須把x，y地位互換,y每增加1，x相應(yīng)增加1/m。增量算法：在一個(gè)迭代算法中，如果每一步的x、y值是用前一步的值加上一個(gè)增量來獲得，則稱為增量算法。DDA算法就是一個(gè)增量算法。|m|≤1情形時(shí)的算法例：畫直線段P0(0,0)--P1(5,2)則k=0.4當(dāng)?x＝1時(shí)，yi+1＝y(tǒng)i+m算法缺點(diǎn)：在此算法中，y、m必須是float，且每一步都必須對y進(jìn)行舍入取整，不利于硬件實(shí)現(xiàn)。Bresenham畫線算法Bresenham算法是Bresenham提出的一種精確且有效的光柵生成算法。它用于顯示線、圓和其它曲線的整數(shù)運(yùn)算它是目前最有效的線段生成算法考慮斜率0<m<1時(shí)的掃描轉(zhuǎn)換情況,如圖：設(shè)斜線在（xk,yk）已經(jīng)確定了一個(gè)點(diǎn)，下一步是xk+1處的點(diǎn)，如何確定？設(shè)點(diǎn)Q為斜線段與xk+1直線的交點(diǎn)，d1、d2分別為點(diǎn)Q距上下平行線yk,yk+1距離設(shè)斜線y=m?x+b，點(diǎn)Q的x軸坐標(biāo)為xk+1，則點(diǎn)Q的y軸坐標(biāo)為：

y=m（xk+1）+b

則可求出d1、d2的長度d1=m(xk+1)+b-ykd2=(yk+1)–[m(xk+1)+b]則：d1、d2的差值為d1-d2=2m(xk+1)-2yk+2b