第4章二維圖形的光柵顯示ppt課件

1、1/46第第4章章 二維圖形的光柵顯示二維圖形的光柵顯示4.1 計(jì)算機(jī)顯示系統(tǒng)計(jì)算機(jī)顯示系統(tǒng)4.2 掃描轉(zhuǎn)換掃描轉(zhuǎn)換 2/46顯示系統(tǒng)是由顯示器顯示系統(tǒng)是由顯示器MonitorMonitor和顯示控制適配器和顯示控制適配器Adapter,Adapter,又稱顯示卡或圖形卡兩部分組成。顯示器的又稱顯示卡或圖形卡兩部分組成。顯示器的作用是將電信號(hào)轉(zhuǎn)換為可以直接觀察到的字符、圖形或圖作用是將電信號(hào)轉(zhuǎn)換為可以直接觀察到的字符、圖形或圖像，是像，是CADCAD中最為重要的人機(jī)交互設(shè)備。中最為重要的人機(jī)交互設(shè)備。 4.1.1 CRT4.1.1 CRT工作原理工作原理 以前采用陰極射線管以前采用陰極射線管C

2、RTCRTCathode Ray TubeCathode Ray Tube技術(shù)。技術(shù)。但液晶顯示但液晶顯示LCD(Liquid Crystal Display)LCD(Liquid Crystal Display)等技術(shù)設(shè)計(jì)的等技術(shù)設(shè)計(jì)的液晶顯示器已獲得應(yīng)用。液晶顯示器已獲得應(yīng)用。4.1 計(jì)算機(jī)顯示系統(tǒng)計(jì)算機(jī)顯示系統(tǒng)3/461. 單色單色CRT它利用電場(chǎng)產(chǎn)生高速的聚焦電子束，偏轉(zhuǎn)到屏幕表面的不它利用電場(chǎng)產(chǎn)生高速的聚焦電子束，偏轉(zhuǎn)到屏幕表面的不同部位，以產(chǎn)生可見的圖形。同部位，以產(chǎn)生可見的圖形。主要組成部分：電子槍、聚焦系統(tǒng)、偏轉(zhuǎn)系統(tǒng)和熒光屏。主要組成部分：電子槍、聚焦系統(tǒng)、偏轉(zhuǎn)系統(tǒng)和熒光屏。C

3、RT顯示器簡(jiǎn)易結(jié)構(gòu)圖顯示器簡(jiǎn)易結(jié)構(gòu)圖4/46 當(dāng)電子束離開熒光點(diǎn)后，其亮度值隨時(shí)間按指數(shù)規(guī)律衰減。余輝時(shí)間就是指光亮度衰減到初始1/10所需的時(shí)間。余輝時(shí)間非常短暫，一般在0.51ms之間。計(jì)算機(jī)計(jì)算機(jī)CRT圖形顯示卡圖形顯示卡電子束產(chǎn)生的光點(diǎn)直徑通常為電子束產(chǎn)生的光點(diǎn)直徑通常為0.250.5mm。分辨率：一個(gè)分辨率：一個(gè)CRT在水平或垂直方向上能夠識(shí)別出的最大光在水平或垂直方向上能夠識(shí)別出的最大光 點(diǎn)數(shù)稱為分辨率，如點(diǎn)數(shù)稱為分辨率，如640480,1024768等。有時(shí)，等。有時(shí)， 也把分辨率理解成所能識(shí)別的光點(diǎn)的最小距離。也把分辨率理解成所能識(shí)別的光點(diǎn)的最小距離。xyxy屏屏幕幕5/462

4、. 彩色彩色CRTRGB顏色模型：顏色模型：RGB(0,0,0)black(1,0,1)magentablue(0,0,1)(1,1,1)white(1,1,0)yellow(0,1,0)greencyan(0,0,1)(1,0,0)redgray axisRGB顏色空間顏色空間顏色的加法過程：顏色的加法過程：從黑色開始，通過從黑色開始，通過增加適當(dāng)?shù)念伾衷黾舆m當(dāng)?shù)念伾至恐诞a(chǎn)生所需要的量值產(chǎn)生所需要的顏色。這種過程與顏色。這種過程與顯示器的工作原理顯示器的工作原理極其相似。極其相似。顏色坐標(biāo)顏色坐標(biāo)r,g,b),它既它既能表示顏色又能表示能表示顏色又能表示亮度。亮度。6/46 CRT屏幕內(nèi)

5、部涂有很多組呈三角形的熒光粉，每一組有三屏幕內(nèi)部涂有很多組呈三角形的熒光粉，每一組有三個(gè)熒光點(diǎn)，當(dāng)某組熒光粉被激勵(lì)時(shí)，分別發(fā)出紅、綠、藍(lán)三個(gè)熒光點(diǎn)，當(dāng)某組熒光粉被激勵(lì)時(shí)，分別發(fā)出紅、綠、藍(lán)三個(gè)基色。個(gè)基色。蔭罩式彩色蔭罩式彩色CRTCRT顯色原理示意圖顯色原理示意圖7/46CRT的刷新頻率是指每秒重畫圖像的次數(shù)。為了得到的刷新頻率是指每秒重畫圖像的次數(shù)。為了得到穩(wěn)定的畫面，通常刷新頻率應(yīng)為穩(wěn)定的畫面，通常刷新頻率應(yīng)為3050幀幀/秒。秒。8/464.1.2 圖形顯示器的工作原理圖形顯示器的工作原理根據(jù)電子束的掃描方式，顯示器分為隨機(jī)掃描式顯根據(jù)電子束的掃描方式，顯示器分為隨機(jī)掃描式顯示器和光柵

6、掃描式顯示器。示器和光柵掃描式顯示器。隨機(jī)掃描方式指屏幕上的圖形是按矢量線段一筆一隨機(jī)掃描方式指屏幕上的圖形是按矢量線段一筆一筆畫出的，其順序完全按用戶的繪圖指令來決定。筆畫出的，其順序完全按用戶的繪圖指令來決定。對(duì)于光柵掃描方式，電子束按照從左到右，從上到對(duì)于光柵掃描方式，電子束按照從左到右，從上到下按固定節(jié)拍掃描，遇到圖形時(shí)，相應(yīng)的柵格發(fā)光，下按固定節(jié)拍掃描，遇到圖形時(shí)，相應(yīng)的柵格發(fā)光，由此顯示圖形或字符。由此顯示圖形或字符。9/46基本工作過程：要顯示的圖形由計(jì)算機(jī)加工成顯示器的基本工作過程：要顯示的圖形由計(jì)算機(jī)加工成顯示器的顯示指令顯示指令顯示文件，存儲(chǔ)在顯示器的緩沖存儲(chǔ)器中。顯示文件

7、，存儲(chǔ)在顯示器的緩沖存儲(chǔ)器中。CPUSystem MemoryDisplayProcessorMonitorSystem BusI/O Devices隨機(jī)掃描所繪制的圖形只能是單線條圖形。隨機(jī)掃描所繪制的圖形只能是單線條圖形。繪制速度與圖形的復(fù)雜程度有關(guān)。繪制速度與圖形的復(fù)雜程度有關(guān)。1. 隨機(jī)掃描顯示器隨機(jī)掃描顯示器簡(jiǎn)單隨機(jī)掃描系統(tǒng)的體系結(jié)構(gòu)簡(jiǎn)單隨機(jī)掃描系統(tǒng)的體系結(jié)構(gòu)10/462. 光柵掃描顯示器光柵掃描顯示器光柵掃描顯示器的工作原理是：光柵掃描顯示器的工作原理是： 首先，屏幕網(wǎng)格化。首先，屏幕網(wǎng)格化。xyxy屏屏幕幕mn個(gè)像素個(gè)像素其次，圖形光柵化。它其次，圖形光柵化。它用幀緩存用幀緩存f

8、rame buffer存儲(chǔ)每個(gè)像素點(diǎn)的光亮存儲(chǔ)每個(gè)像素點(diǎn)的光亮度值。度值。 最后，光柵化的像素值由偏轉(zhuǎn)及顏色系統(tǒng)，在最后，光柵化的像素值由偏轉(zhuǎn)及顏色系統(tǒng)，在CRT屏幕顯示。屏幕顯示。11/46特點(diǎn)：特點(diǎn)： 幀緩存中存放的不是顯示指令，而是對(duì)應(yīng)每個(gè)像幀緩存中存放的不是顯示指令，而是對(duì)應(yīng)每個(gè)像素的亮度或色彩信息。素的亮度或色彩信息。 可用于顯示真實(shí)感的圖形。可用于顯示真實(shí)感的圖形。 光柵顯示與原始圖形的復(fù)雜程度無關(guān)。光柵顯示與原始圖形的復(fù)雜程度無關(guān)。 屏幕上的每個(gè)像素都對(duì)應(yīng)幀緩沖存儲(chǔ)器的若干位。屏幕上的每個(gè)像素都對(duì)應(yīng)幀緩沖存儲(chǔ)器的若干位。 各種掃描轉(zhuǎn)換算法已固化在硬件中。各種掃描轉(zhuǎn)換算法已固化在硬

9、件中。 圖形的近似表示。圖形的近似表示。 12/46CPUSystem MemoryVideoControllerMonitorSystem BusI/O Devices簡(jiǎn)單的光柵掃描系統(tǒng)的體系結(jié)構(gòu)簡(jiǎn)單的光柵掃描系統(tǒng)的體系結(jié)構(gòu)幀緩存可以位于系統(tǒng)內(nèi)存的任何地方。幀緩存可以位于系統(tǒng)內(nèi)存的任何地方。顯示控制器存取幀緩存刷新屏幕。顯示控制器存取幀緩存刷新屏幕。13/46CPUSystem MemoryVideoControllerMonitorSystem BusI/O DevicesFrameBuffer系統(tǒng)內(nèi)存中一個(gè)固定區(qū)域作為幀緩存區(qū)使用。系統(tǒng)內(nèi)存中一個(gè)固定區(qū)域作為幀緩存區(qū)使用。顯示控制器直接存

10、取幀緩存中的像素顏色值。顯示控制器直接存取幀緩存中的像素顏色值。具有固定幀緩存的光柵掃描系統(tǒng)的體系結(jié)構(gòu)具有固定幀緩存的光柵掃描系統(tǒng)的體系結(jié)構(gòu)14/46CPUVideoControllerMonitorSystem BusI/O DevicesDisplayProcessor MemoryFrameBufferDisplayProcessorSystemMemory具有顯示處理器的光柵掃描系統(tǒng)的體系結(jié)構(gòu)具有顯示處理器的光柵掃描系統(tǒng)的體系結(jié)構(gòu)顯示處理器的主要任務(wù)是進(jìn)行掃描轉(zhuǎn)換顯示處理器的主要任務(wù)是進(jìn)行掃描轉(zhuǎn)換Scan-Conversion）15/464.1.3 圖形顯示卡圖形顯示卡 圖形顯示的核心

11、部分是圖形加速芯片。圖形圖形顯示的核心部分是圖形加速芯片。圖形加速芯片是一個(gè)固化了一定數(shù)量最常用基本圖形加速芯片是一個(gè)固化了一定數(shù)量最常用基本圖形程序模塊的集成電路，它大大減輕了程序模塊的集成電路，它大大減輕了CPU的負(fù)荷，的負(fù)荷，加快了圖形操作速度。加快了圖形操作速度。 圖形適配器從接口形式可分為圖形適配器從接口形式可分為ISA, VESA, PCI和和AGP等。等。1. 普通顯示卡。如普通顯示卡。如CGA、EGA、VGA、TVGA。這種卡的圖形處理完全由主機(jī)這種卡的圖形處理完全由主機(jī)CPU完成，價(jià)格低完成，價(jià)格低廉。廉。16/46PCI總線總線顯示卡顯示卡硬盤硬盤網(wǎng)卡網(wǎng)卡CPU處理器處理器

12、系統(tǒng)內(nèi)存系統(tǒng)內(nèi)存?zhèn)鹘y(tǒng)傳統(tǒng)PCI芯片卡芯片卡132MB/s528MB/s傳統(tǒng)的傳統(tǒng)的PCI總線結(jié)構(gòu)總線結(jié)構(gòu)2. 有圖形處理芯片的圖形顯示卡?；谟袌D形處理芯片的圖形顯示卡。基于PCI總線并集成總線并集成有圖形處理芯片，如有圖形處理芯片，如 Intel 82786 和和 TMS 34020。顯示卡主要用于解決輸入輸出總線速度遠(yuǎn)遠(yuǎn)慢于顯示卡主要用于解決輸入輸出總線速度遠(yuǎn)遠(yuǎn)慢于CPU內(nèi)部?jī)?nèi)部處理速度的問題。處理速度的問題。17/463. 基于基于AGP的圖形卡的圖形卡與傳統(tǒng)的顯示卡相比，與傳統(tǒng)的顯示卡相比，AGP (Advanced Graphics Port) 在在傳輸總線上有較大改進(jìn)。它把主存與顯

13、存直接連接起來，傳輸總線上有較大改進(jìn)。它把主存與顯存直接連接起來，是新一代圖形卡接口。是新一代圖形卡接口。PCI總線總線硬盤硬盤網(wǎng)卡網(wǎng)卡聲卡聲卡顯示卡顯示卡系統(tǒng)內(nèi)存系統(tǒng)內(nèi)存AGP芯片卡芯片卡132MB/s528MB/sCPU處理器處理器AGP總線結(jié)構(gòu)總線結(jié)構(gòu)18/46顯示卡一般都有顯示緩存。根據(jù)不同的要求，顯示緩存有顯示卡一般都有顯示緩存。根據(jù)不同的要求，顯示緩存有2MB, 4MB, 8MB等配置。等配置。19/464.2 掃描轉(zhuǎn)換掃描轉(zhuǎn)換 4.2.1 掃描轉(zhuǎn)換的必要性掃描轉(zhuǎn)換的必要性計(jì)算機(jī)圖形學(xué)中所研究的圖形是從客觀世界物體中抽象出來計(jì)算機(jī)圖形學(xué)中所研究的圖形是從客觀世界物體中抽象出來的帶灰

14、度或彩色及形狀的圖或形。計(jì)算機(jī)中表示一個(gè)圖的帶灰度或彩色及形狀的圖或形。計(jì)算機(jī)中表示一個(gè)圖形常用的方法有兩種：形常用的方法有兩種：（1點(diǎn)陣法：是用具有灰度或色彩的點(diǎn)陣表示圖形的一種點(diǎn)陣法：是用具有灰度或色彩的點(diǎn)陣表示圖形的一種方法，它強(qiáng)調(diào)由哪些點(diǎn)組成，并具有什么灰度或色彩。方法，它強(qiáng)調(diào)由哪些點(diǎn)組成，并具有什么灰度或色彩。（2參數(shù)法：參數(shù)法： 是以計(jì)算機(jī)中所記錄的形狀參數(shù)與屬性參數(shù)是以計(jì)算機(jī)中所記錄的形狀參數(shù)與屬性參數(shù)表示圖形的一種方法。形狀參數(shù)可以是描述其形狀的方程的表示圖形的一種方法。形狀參數(shù)可以是描述其形狀的方程的系數(shù)、線段的起點(diǎn)和終點(diǎn)等；屬性參數(shù)則包括灰度、顏色、系數(shù)、線段的起點(diǎn)和終點(diǎn)等

15、；屬性參數(shù)則包括灰度、顏色、線型等非幾何屬性。線型等非幾何屬性。通常將參數(shù)法描述的圖形稱為參數(shù)圖形，也稱矢量圖形。而通常將參數(shù)法描述的圖形稱為參數(shù)圖形，也稱矢量圖形。而把點(diǎn)陣法描述的圖形叫做像素圖形，簡(jiǎn)稱圖像。把點(diǎn)陣法描述的圖形叫做像素圖形，簡(jiǎn)稱圖像。20/46光柵圖形的表示方法是點(diǎn)陣式，它的主要特點(diǎn)是面著色，光柵圖形的表示方法是點(diǎn)陣式，它的主要特點(diǎn)是面著色，即在指定的平面區(qū)域著上所需要的顏色。與單純由線條所即在指定的平面區(qū)域著上所需要的顏色。與單純由線條所構(gòu)成的線劃圖形相比，采用面著色繪制的光柵圖形顯得更構(gòu)成的線劃圖形相比，采用面著色繪制的光柵圖形顯得更為生動(dòng)、直觀，真實(shí)感更強(qiáng)。為生動(dòng)、直觀

16、，真實(shí)感更強(qiáng)。一般地，復(fù)雜的圖形是由基本的圖形元素如點(diǎn)、線、圓及多一般地，復(fù)雜的圖形是由基本的圖形元素如點(diǎn)、線、圓及多邊形構(gòu)成的。這些圖形元素通常是在連續(xù)的空間定義，而不邊形構(gòu)成的。這些圖形元素通常是在連續(xù)的空間定義，而不是由離散圖像空間中的像素定義。是由離散圖像空間中的像素定義。圖形系統(tǒng)的任務(wù)之一就是將在連續(xù)空間中定義的幾何元圖形系統(tǒng)的任務(wù)之一就是將在連續(xù)空間中定義的幾何元素轉(zhuǎn)化為圖像空間中的像素表示。這一轉(zhuǎn)化任務(wù)稱為掃素轉(zhuǎn)化為圖像空間中的像素表示。這一轉(zhuǎn)化任務(wù)稱為掃描轉(zhuǎn)換或光柵化。描轉(zhuǎn)換或光柵化。 矢量圖形矢量圖形光柵圖形光柵圖形掃描轉(zhuǎn)換掃描轉(zhuǎn)換21/46yx0101像素坐標(biāo)像素坐標(biāo)(0,

17、0)掃描線掃描線y=0像素像素:方形區(qū)域方形區(qū)域用像素中心表示像素用像素中心表示像素像素、像素坐標(biāo)、掃描線、屏幕坐標(biāo)像素、像素坐標(biāo)、掃描線、屏幕坐標(biāo)yx0101屏幕坐標(biāo)屏幕坐標(biāo)(0,0)掃描線掃描線y=0用像素網(wǎng)格的左下角表示像素用像素網(wǎng)格的左下角表示像素22/464.2.2 點(diǎn)的掃描轉(zhuǎn)換點(diǎn)的掃描轉(zhuǎn)換設(shè)設(shè)(x,y)是圖像區(qū)域中的一點(diǎn)，其中是圖像區(qū)域中的一點(diǎn)，其中x,y均為實(shí)數(shù)。均為實(shí)數(shù)。我們需要將它轉(zhuǎn)換為圖像空間中的一個(gè)像素我們需要將它轉(zhuǎn)換為圖像空間中的一個(gè)像素(x,y)。方法方法1：?。喝和和y分別為分別為x和和y的整數(shù)部分。的整數(shù)部分。23/46P3PixelCoordinatesyxP

18、ixel Grid1.02.00.01.02.0012012P2P1P1(1.7,0.8)P2(2.2,1.3)P3(2.8,1.9)這種做法的本質(zhì)是將連續(xù)坐標(biāo)系統(tǒng)的原點(diǎn)放在圖這種做法的本質(zhì)是將連續(xù)坐標(biāo)系統(tǒng)的原點(diǎn)放在圖像空間的像素網(wǎng)格的左下角。像空間的像素網(wǎng)格的左下角。24/46方法方法2：采用四舍五入的方法。即：采用四舍五入的方法。即x和和y分別為分別為x+0.5及及y+0.5的的整數(shù)部分。整數(shù)部分。PixelCoordinatesyxPixel Grid1.02.00.01.02.0012012P2P3P1P1(1.7,0.8)P2(2.2,1.3)P3(2.8,1.9)33.0將連續(xù)空間

19、中的整數(shù)值與圖像空間中的像素坐標(biāo)對(duì)齊。將連續(xù)空間中的整數(shù)值與圖像空間中的像素坐標(biāo)對(duì)齊。25/464.2.3 直線段的掃描轉(zhuǎn)換直線段的掃描轉(zhuǎn)換 典型地，圖形學(xué)中的一條線指一條線段，它由兩個(gè)端點(diǎn)及直線方程定義。 斜率截距式方程不適合表示垂線，因此，程度、垂線、對(duì)角線線段需特殊處理。無需用下述掃描轉(zhuǎn)換算法。OP1(x1,y1)P2(x2,y2)y=mx+bxy26/461. 直接應(yīng)用直線方程直接應(yīng)用直線方程 首先，將首先，將P1,P2掃描轉(zhuǎn)換為像素坐標(biāo)掃描轉(zhuǎn)換為像素坐標(biāo)x1,y1）和）和(x2,y2)。 其次，設(shè)其次，設(shè)m=(y2-y1)/(x2-x1), b=y1-mx1。假設(shè)假設(shè)|m|1,則對(duì)介

20、于則對(duì)介于y1和和y2之間之間的每個(gè)整數(shù)值的每個(gè)整數(shù)值y，用直線方程計(jì)算出，用直線方程計(jì)算出x值并值并掃描轉(zhuǎn)換掃描轉(zhuǎn)換(x,y)。 缺陷：因缺陷：因m,b都是浮點(diǎn)數(shù)，因此這種方法都是浮點(diǎn)數(shù)，因此這種方法的每步都要進(jìn)行浮點(diǎn)數(shù)乘法與加法計(jì)算。的每步都要進(jìn)行浮點(diǎn)數(shù)乘法與加法計(jì)算。27/46例例: 對(duì)于對(duì)于|m|=1的直線段，應(yīng)用斜率的直線段，應(yīng)用斜率-截距式方程繪制該線截距式方程繪制該線段需要哪些步驟段需要哪些步驟?計(jì)算計(jì)算dx: dx=x2-x1;計(jì)算計(jì)算dy: dy=y2-y1;計(jì)算斜率計(jì)算斜率: m=dy/dx;計(jì)算截距計(jì)算截距b: b=y1-mx1; 設(shè)設(shè)xend為為x1與與x2中的最大者，

21、若中的最大者，若dx0, 則則x=x1,y=y1, 且且xend=x2；檢查整條線段是否繪制完畢，如果檢查整條線段是否繪制完畢，如果x xend,則停止運(yùn)行；則停止運(yùn)行；在當(dāng)前在當(dāng)前(x,y)坐標(biāo)處畫點(diǎn)；坐標(biāo)處畫點(diǎn)；增大增大x: x=x+1；根據(jù)方程根據(jù)方程y=mx+b計(jì)算下一個(gè)計(jì)算下一個(gè)y值；值；返回第返回第6步。步。28/462. DDA(Digital Differential Analyzer)算法算法 該算法是增量掃描轉(zhuǎn)換方法。假設(shè)在第該算法是增量掃描轉(zhuǎn)換方法。假設(shè)在第i步求步求出了直線上的點(diǎn)出了直線上的點(diǎn)xi,yi）。由于下一點(diǎn)）。由于下一點(diǎn) 滿足滿足于是，于是，)11,(iiyx

22、iixymxy1i1ixx ,yy ,/xmyyii1myxxii/1或或這些公式在這些公式在DDA算法中的應(yīng)用如下：算法中的應(yīng)用如下：當(dāng)當(dāng)|m|=1時(shí)，我們從時(shí)，我們從x=x1(假設(shè)假設(shè)x11的情況可做類似處理。的情況可做類似處理。1xmyyii129/46例例: 用偽碼描述用偽碼描述DDA算法，假設(shè)直線段的斜率滿足算法，假設(shè)直線段的斜率滿足: |m|1。對(duì)于直線段的兩個(gè)端點(diǎn)對(duì)于直線段的兩個(gè)端點(diǎn)(x1,y1)和和(x2,y2)，假設(shè)，假設(shè)y1y2。int x,y=y1;float xf=x1, minv=(x2-x1)/(y2-y1);while(y=y2) x=Floor(xf+0.5);

23、/ Floor(x)表示取表示取x的整數(shù)部分的整數(shù)部分 setPixel(x,y);/在像素在像素(x,y)處畫點(diǎn)處畫點(diǎn) xf=xf+ minv; y+;/即將即將y值增加值增加1 30/46DDA算法效率的評(píng)述算法效率的評(píng)述:優(yōu)點(diǎn)優(yōu)點(diǎn):較直接，用直線方程的方法速度更快。較直接，用直線方程的方法速度更快。缺陷缺陷:浮點(diǎn)數(shù)和取整運(yùn)算仍然費(fèi)時(shí)。浮點(diǎn)數(shù)和取整運(yùn)算仍然費(fèi)時(shí)。克服方法克服方法: 將增量將增量m和和1/m分成整數(shù)和分?jǐn)?shù)兩部分，使所有分成整數(shù)和分?jǐn)?shù)兩部分，使所有計(jì)算歸結(jié)為整數(shù)操作計(jì)算歸結(jié)為整數(shù)操作(這里不再深入分析這種算這里不再深入分析這種算法法)。31/463. Bresenhams直線算

24、法直線算法 該算法是掃描轉(zhuǎn)換線段的精確高效的增量算法。該算法是掃描轉(zhuǎn)換線段的精確高效的增量算法。它僅利用整數(shù)加法、減法及被它僅利用整數(shù)加法、減法及被2乘的乘法就可以乘的乘法就可以得到數(shù)學(xué)上的精確結(jié)果。得到數(shù)學(xué)上的精確結(jié)果。 這種方法可推廣應(yīng)用到圓和其他曲線的掃描轉(zhuǎn)這種方法可推廣應(yīng)用到圓和其他曲線的掃描轉(zhuǎn)換。換。32/46假設(shè)假設(shè)0m1syxyiyi+1xixi+1True lineScan-converted pointsP1P2STts像素像素S: xi+1=xi+1,yi+1=yi像素像素T: xi+1=xi+1,yi+1=yi+1知知: (xi,yi)確定確定(xi+1,yi+1)?y=

25、mxi+1+bs=y-yi ,t=(yi+1)-y33/46當(dāng)當(dāng)s-t=0,則選則選T, 此時(shí)此時(shí)di+1= di+2(dy-dx)如果如果di0,則選則選S, 此時(shí)此時(shí)di+1= di+2dy34/46可以算出可以算出: d1=2dy-dx推導(dǎo)過程如下推導(dǎo)過程如下:由由di=2dyxi - 2dx yi+C, 其中其中C=2dy+dx(2b-1)得得d1=2dxmx1-2dxy1+2mdx+dx(2b-1) /留留意意:m=dy/dx=dx2m(x1+1)+2b-2y1-1=dx2(mx1+b-y1)+2m-1由于由于 mx1+b-y1=0,所以所以d1=dx(2m-1)=2dy-dx 35

26、/46已知直線段：從已知直線段：從P1(x1,y1)到到P2(x2,y2),其中其中 x1x2, 0m1則則Bresenhams直線掃描算法如下：直線掃描算法如下：int x=x1, y=y1;int dx=x2-x1,dy=y2-y1,dT=2(dy-dx), dS=2dy;int d=2dy-dx;setPixel(x,y);while(xx2)x+;if (d0) d=d+dS;36/46elsey+;d=d+dT;setPixel(x,y);例：已知線段端點(diǎn)例：已知線段端點(diǎn)20,10)及及30,18）,斜率斜率m=0.8，這時(shí)，這時(shí)，dx=10, dy=8, dT=-4, dS=16,

27、d=6我們首先畫初始點(diǎn)我們首先畫初始點(diǎn)20，10），然后依），然后依次畫點(diǎn)：次畫點(diǎn)：37/464.2.4 多邊形的掃描轉(zhuǎn)換與區(qū)域填充多邊形的掃描轉(zhuǎn)換與區(qū)域填充一個(gè)區(qū)域是指一組相鄰而又相連的像素，且具有一個(gè)區(qū)域是指一組相鄰而又相連的像素，且具有同樣的屬性。同樣的屬性。區(qū)域可以由像素級(jí)定義，也可以由幾何級(jí)定義。區(qū)域可以由像素級(jí)定義，也可以由幾何級(jí)定義。在像素級(jí)，區(qū)域可以用內(nèi)點(diǎn)表示和邊界表示。在在像素級(jí)，區(qū)域可以用內(nèi)點(diǎn)表示和邊界表示。在幾何級(jí)，區(qū)域可以由抽象的輪廓線定義，如相互幾何級(jí)，區(qū)域可以由抽象的輪廓線定義，如相互連接的線段和曲線。連接的線段和曲線。多邊形區(qū)域多邊形區(qū)域38/461. 多邊形的掃

28、描轉(zhuǎn)換多邊形的掃描轉(zhuǎn)換 在計(jì)算機(jī)圖形學(xué)中，多邊形有兩種重要的表示在計(jì)算機(jī)圖形學(xué)中，多邊形有兩種重要的表示方法：頂點(diǎn)表示和點(diǎn)陣表示。方法：頂點(diǎn)表示和點(diǎn)陣表示。 頂點(diǎn)表示是用多邊形的頂點(diǎn)的序列來刻畫多邊頂點(diǎn)表示是用多邊形的頂點(diǎn)的序列來刻畫多邊形。這種方法直觀、幾何意義強(qiáng)。形。這種方法直觀、幾何意義強(qiáng)。 點(diǎn)陣表示是用位于多邊形內(nèi)的像素的集合來刻點(diǎn)陣表示是用位于多邊形內(nèi)的像素的集合來刻畫多邊形。該方法失去了許多重要的幾何信息，但畫多邊形。該方法失去了許多重要的幾何信息，但便于運(yùn)用幀緩沖器表示圖形。便于運(yùn)用幀緩沖器表示圖形。P0P1P2P3P4多邊形的頂點(diǎn)表示多邊形的頂點(diǎn)表示多邊形的點(diǎn)陣表示多邊形的點(diǎn)陣

29、表示 39/46多邊形的掃描線填充算法：多邊形的掃描線填充算法：xy 對(duì)每條穿過多邊形的掃描線，對(duì)每條穿過多邊形的掃描線，求出該掃描線與多邊形邊界求出該掃描線與多邊形邊界的交點(diǎn)，將這些交點(diǎn)按照從的交點(diǎn)，將這些交點(diǎn)按照從左到右進(jìn)行排序，在每對(duì)交左到右進(jìn)行排序，在每對(duì)交點(diǎn)之間相應(yīng)的幀緩存位置設(shè)點(diǎn)之間相應(yīng)的幀緩存位置設(shè)置指定的填充色。置指定的填充色。一些掃描線在多邊形頂點(diǎn)處一些掃描線在多邊形頂點(diǎn)處的交點(diǎn)需要特殊處理。的交點(diǎn)需要特殊處理。1211211處理方法：若該頂點(diǎn)不是處理方法：若該頂點(diǎn)不是局部極值點(diǎn)，當(dāng)掃描線與局部極值點(diǎn)，當(dāng)掃描線與該點(diǎn)相交時(shí)，按一個(gè)交點(diǎn)該點(diǎn)相交時(shí)，按一個(gè)交點(diǎn)處理。處理。40/4

30、6提高算法效率的基本方法：（提高算法效率的基本方法：（1利用同一條掃描線上相利用同一條掃描線上相鄰像素的相關(guān)性；（鄰像素的相關(guān)性；（2利用同一條邊兩個(gè)相鄰掃描線的利用同一條邊兩個(gè)相鄰掃描線的相關(guān)性。相關(guān)性。掃描線掃描線yk掃描線掃描線yk+1(xk,yk)(xk+1,yk+1)xk+1=xk+1/m= xk+dy/dx容易推出遞推公式：容易推出遞推公式：與多邊形一條邊相交的兩條相鄰的掃描線與多邊形一條邊相交的兩條相鄰的掃描線于是，于是，xk+1=x0+k/m41/462. 區(qū)域填充算法區(qū)域填充算法 這里所說的區(qū)域是指已經(jīng)表示成點(diǎn)陣形式這里所說的區(qū)域是指已經(jīng)表示成點(diǎn)陣形式的像素的集合。的像素的集

31、合。 區(qū)域填充是指先將區(qū)域內(nèi)的一點(diǎn)區(qū)域填充是指先將區(qū)域內(nèi)的一點(diǎn)(常稱種子常稱種子點(diǎn)點(diǎn))賦予給定顏色，然后將這種顏色擴(kuò)展到整個(gè)賦予給定顏色，然后將這種顏色擴(kuò)展到整個(gè)區(qū)域的過程。這種技術(shù)廣泛應(yīng)用于動(dòng)畫和美術(shù)區(qū)域的過程。這種技術(shù)廣泛應(yīng)用于動(dòng)畫和美術(shù)畫的計(jì)算機(jī)輔助制作中。畫的計(jì)算機(jī)輔助制作中。 區(qū)域的兩種定義方法區(qū)域的兩種定義方法:內(nèi)點(diǎn)表示和邊界表示。內(nèi)點(diǎn)表示和邊界表示。 將給定區(qū)域內(nèi)的所有像素表示成點(diǎn)陣形式將給定區(qū)域內(nèi)的所有像素表示成點(diǎn)陣形式的方法稱為內(nèi)點(diǎn)表示法。在內(nèi)點(diǎn)表示中區(qū)域內(nèi)的方法稱為內(nèi)點(diǎn)表示法。在內(nèi)點(diǎn)表示中區(qū)域內(nèi)的所有像素都著同一種顏色的所有像素都著同一種顏色(常稱為原色常稱為原色)，而，而區(qū)域的邊界上的像素則不著這種顏色。區(qū)域的邊界上的像素則不著這種顏色。 以內(nèi)點(diǎn)表示法為基礎(chǔ)，將該區(qū)域中的全部以內(nèi)點(diǎn)表示法為基礎(chǔ)，將該區(qū)域中的全