計(jì)算機(jī)圖形學(xué)備課筆記

PAGEPAGE159第一章概述重點(diǎn)：掌握計(jì)算機(jī)圖形學(xué)研究的內(nèi)容、應(yīng)用領(lǐng)域以及圖形硬件和軟件系統(tǒng)。難點(diǎn)：理解光柵掃描顯示器和隨機(jī)掃描顯示器的區(qū)別以及彩色顯示機(jī)理。課時(shí)安排：授課2學(xué)時(shí)。

計(jì)算機(jī)圖形學(xué)（ComputerGraphics）是隨著計(jì)算機(jī)技術(shù)的發(fā)展而發(fā)展起來(lái)的一門新興學(xué)科。計(jì)算機(jī)圖形學(xué)研究怎樣通過(guò)計(jì)算機(jī)來(lái)產(chǎn)生圖形（1）專題圖件：地形圖、地貌圖、資源分布圖、旅游資源圖、土地利用現(xiàn)狀圖、管網(wǎng)分布圖等；

（2）照片、三維逼真圖形等；

（3）實(shí)體的視圖，如：機(jī)械零件的正視圖、側(cè)視圖等；

（4）抽象概念的形象表示：計(jì)劃圖、餅圖、統(tǒng)計(jì)曲線、流程圖等。國(guó)際標(biāo)準(zhǔn)化組織（ISO）對(duì)計(jì)算機(jī)圖形學(xué)的定義計(jì)算機(jī)圖形學(xué)是研究通過(guò)計(jì)算機(jī)將數(shù)據(jù)轉(zhuǎn)換為圖形，并在專門的設(shè)備上輸出的原理、方法和技術(shù)的學(xué)科。與計(jì)算機(jī)圖形學(xué)密切相關(guān)的幾門學(xué)科是：1、圖像處理（ImageProcessing）圖像處理利用計(jì)算機(jī)對(duì)圖形和圖像進(jìn)行分析處理，繼而再現(xiàn)圖像。圖形（圖像）信息輸入計(jì)算機(jī)中，按照不同的應(yīng)用要求，計(jì)算機(jī)對(duì)圖像進(jìn)行各種各樣的分析和處理。

例如，進(jìn)行圖像的存儲(chǔ)、壓縮、增強(qiáng)（突出某些特征）、復(fù)原（使模糊圖像清晰）、分割、重建、編碼、傳輸?shù)鹊?，最后把?jīng)過(guò)加工處理后的結(jié)果重新輸出。應(yīng)用實(shí)例：工業(yè)中射線探傷、人體的CT掃描、衛(wèi)星遙感以及資源勘測(cè)?，F(xiàn)在圖像處理正從二維處理朝著三維圖像生成、立體成像、多種傳輸媒體等方向發(fā)展。2、模式識(shí)別（PatternRecognition）圖像的模式識(shí)別所研究的問(wèn)題與計(jì)算機(jī)圖形學(xué)所研究的問(wèn)題是互逆的。模式識(shí)別是由圖像來(lái)獲得對(duì)圖像本身的描述。它是以圖像為依據(jù)，將圖像變換成數(shù)據(jù)、符號(hào)或者是抽象的圖。例如，自動(dòng)分檢信封上的郵件編碼、文本自動(dòng)閱讀裝置、還有地圖符號(hào)的識(shí)別，都是先由掃描得到圖像，然后經(jīng)識(shí)別還原為圖形或字符。3、計(jì)算幾何（ComputationalGeometry）計(jì)算幾何則著重討論幾何形體在計(jì)算機(jī)內(nèi)的表示、分析和綜合，研究怎樣方便靈活地建立幾何形體的數(shù)學(xué)模型，提高算法的效率，在計(jì)算機(jī)內(nèi)如何更好地存儲(chǔ)和管理這些模型等。它的研究?jī)?nèi)容包括曲線曲面的表示、生成、拼接和造型、三維立體造型、離散數(shù)據(jù)插值等等。計(jì)算機(jī)圖形學(xué)與其他學(xué)科的關(guān)系：如下圖所示，計(jì)算機(jī)圖形學(xué)與圖像處理、模式識(shí)別、計(jì)算幾何這幾門相關(guān)學(xué)科之間正在不斷相互滲透、相互溝通，其學(xué)科界線也變得模糊起來(lái)。例如，計(jì)算機(jī)圖形學(xué)課程中往往要介紹參數(shù)曲線、曲面的數(shù)學(xué)表示；工程圖掃描輸入后要先用圖象處理技術(shù)提取畫面的特征信息，然后再用模式識(shí)別技術(shù)生成矢量形式的各種幾何元素。圖形系統(tǒng)的任務(wù)：1.1計(jì)算機(jī)圖形學(xué)的研究?jī)?nèi)容計(jì)算機(jī)圖形學(xué)的研究?jī)?nèi)容涉及到用計(jì)算機(jī)對(duì)圖形數(shù)據(jù)進(jìn)行處理的硬件和軟件兩方面的技術(shù)，以及與圖形生成、顯示密切相關(guān)的基礎(chǔ)算法：1、二維圖形元素的生成算法點(diǎn)、直線、圓、弧、規(guī)則曲線、自由曲線、文本等圖元的生成。2、二維圖形的基本操作和圖形處理算法對(duì)圖形的平移、縮放、旋轉(zhuǎn)、鏡像、錯(cuò)切等操作，此外還包括二維圖形的裁剪、多邊形填充以及二維圖形的布爾運(yùn)算（并、交、差）等。3、二維圖形的輸入輸出用圖形輸入設(shè)備實(shí)現(xiàn)人機(jī)交互及用戶接口技術(shù)。4、三維幾何造型技術(shù)包括基本體素的建立與生成，規(guī)則曲面與自由曲面的構(gòu)造，以及三維形體之間的布爾運(yùn)算等。5、真實(shí)感圖形的生成算法三維圖形的消隱算法、光照模型的建立，陰影及彩色濃淡圖的生成算法。6、科學(xué)計(jì)算可視化技術(shù)這是20世紀(jì)90年代計(jì)算機(jī)圖形學(xué)領(lǐng)域的前沿課題。研究的是，將科學(xué)計(jì)算中大量難以理解的數(shù)據(jù)通過(guò)計(jì)算機(jī)圖形顯示出來(lái)，從而加深人們對(duì)科學(xué)過(guò)程的理解。例如，有限元分析的結(jié)果，應(yīng)力場(chǎng)、磁場(chǎng)的分布，各種復(fù)雜的運(yùn)動(dòng)學(xué)和動(dòng)力學(xué)問(wèn)題的圖形仿真等。在大學(xué)本科階段，應(yīng)著重了解前面三個(gè)內(nèi)容，而后面三個(gè)涉及三維圖形的內(nèi)容可留待研究生階段去研究。計(jì)算機(jī)圖形學(xué)正以很快的速度向前發(fā)展，當(dāng)前這一領(lǐng)域研究的前沿課題有：（1）圖形軟件與開發(fā)環(huán)境的標(biāo)準(zhǔn)化（2）提高算法的可靠性和效率消隱算法、真實(shí)感彩色圖像、明暗圖、體素拼合中的曲面求交和拓?fù)涮幚淼葐?wèn)題上。（3）用并行處理技術(shù)提高真實(shí)感圖像的生成速度如采用多處理器，將一幅光柵圖像的512×512或更多個(gè)象素用幾十個(gè)甚至幾百個(gè)處理器并行計(jì)算，可以明顯提高圖像的生成速度?！酰?）探討自然景象的模擬方法采用紋理映射、分維技術(shù)、粒子系統(tǒng)等方法再現(xiàn)景物表面的色彩和紋理細(xì)節(jié)，體現(xiàn)山巒的粗糙巖面，重現(xiàn)云、火、水等飄忽不定的景色。（5）科學(xué)可視化1.2計(jì)算機(jī)圖形學(xué)的發(fā)展歷史1950年，美國(guó)麻省理工學(xué)院（MIT）研制出第一臺(tái)圖形顯示器。作為旋風(fēng)1號(hào)（WhirlWind1）計(jì)算機(jī)的輸出設(shè)備。利用這臺(tái)顯示器在計(jì)算機(jī)的控制下第一次顯示了一些簡(jiǎn)單圖形。隨后，一些公司和研究所也陸續(xù)地研制了繪圖儀等一些簡(jiǎn)單的圖形設(shè)備。但這些設(shè)備僅僅具有圖形輸出功能，因此這時(shí)的圖形學(xué)只能算“被動(dòng)”的圖形學(xué)。隨后，由麻省理工學(xué)院林肯實(shí)驗(yàn)室主持研制的SAGE空中警戒雷達(dá)系統(tǒng)，成功地把雷達(dá)波形轉(zhuǎn)換成圖形在顯示器上顯示出來(lái)。指揮員可以通過(guò)光筆與系統(tǒng)交互，獲取某地區(qū)更詳細(xì)的信息或發(fā)出命令。這個(gè)系統(tǒng)可以說(shuō)是交互式計(jì)算機(jī)圖形系統(tǒng)的雛形，它預(yù)示著交互式圖形生成技術(shù)的誕生。60年代是計(jì)算機(jī)圖形學(xué)興起和確立的年代。1962年，美國(guó)麻省理工學(xué)院的IvenSutherland發(fā)表了題目為“Sketchpad：一個(gè)人機(jī)通信的圖形系統(tǒng)”的博士論文，在論文中他首次使用了“計(jì)算機(jī)圖形學(xué)”（ComputerGraphics）這個(gè)術(shù)語(yǔ)，指出交互式計(jì)算機(jī)圖形學(xué)是一個(gè)有生命力、有前途和振奮人心的研究領(lǐng)域，從而確立了計(jì)算機(jī)圖形學(xué)作為一個(gè)嶄新的科學(xué)分支的地位。他在論文中所提出的一些基本概念和技術(shù)，如交互技術(shù)、分層存儲(chǔ)符號(hào)的數(shù)據(jù)結(jié)構(gòu)等至今還在廣為使用。與此同時(shí)，美國(guó)、英國(guó)、法國(guó)在汽車和飛機(jī)制造領(lǐng)域?qū)τ?jì)算機(jī)圖形學(xué)開展了大規(guī)模研究。在計(jì)算機(jī)輔助設(shè)計(jì)（CAD）和計(jì)算機(jī)輔助制造（CAM）中，一些相關(guān)的科研項(xiàng)目、商品化產(chǎn)品紛紛出現(xiàn)。但是，由于圖形硬件設(shè)備非常昂貴，并且基于圖形技術(shù)的應(yīng)用相對(duì)較少，所以直到80年代初，圖形學(xué)仍然是一個(gè)較小的專業(yè)化學(xué)科。隨后，情況發(fā)生了變化，由于大規(guī)模集成電路技術(shù)的快速發(fā)展，計(jì)算機(jī)硬件性能不斷提高，體積縮小，價(jià)格降低，特別是廉價(jià)的圖形輸入輸出設(shè)備和大容量存儲(chǔ)介質(zhì)的出現(xiàn)，使得以小型機(jī)、微機(jī)、圖形工作站為基礎(chǔ)的圖形系統(tǒng)進(jìn)入市場(chǎng)并成為主流，如IBM－PC、蘋果機(jī)等微機(jī)和Apollo、Sun等工作站。80年代，是計(jì)算機(jī)圖形系統(tǒng)迅速推廣應(yīng)用的年代。計(jì)算機(jī)圖形軟件功能開始部分地由硬件實(shí)現(xiàn)，尤其是微機(jī)的大面積推廣，進(jìn)一步拓寬了圖形學(xué)的研究和應(yīng)用，三維計(jì)算機(jī)圖形學(xué)的國(guó)際標(biāo)準(zhǔn)PHIGS和GKS－3D的頒布，為研制通用的圖形系統(tǒng)提供了良好的基礎(chǔ)。90年代，隨著多媒體概念的提出計(jì)算機(jī)圖形學(xué)已成為計(jì)算機(jī)系統(tǒng)必不可少的一個(gè)組成部分，并且迅速投入使用中。同時(shí)，隨著面向?qū)ο蟮某绦蛟O(shè)計(jì)語(yǔ)言的發(fā)展，也提出了面向?qū)ο蟮挠?jì)算機(jī)圖形系統(tǒng)。作為計(jì)算機(jī)圖形系統(tǒng)的一個(gè)重要組成部分——圖形顯示器，隨著計(jì)算機(jī)圖形學(xué)的確立和發(fā)展也經(jīng)歷了從矢量顯示器、存儲(chǔ)管顯示器到光柵顯示器的發(fā)展過(guò)程。圖形輸入設(shè)備也在發(fā)展，出現(xiàn)了：拇指輪、操作桿、跟蹤球、光筆、鼠標(biāo)、觸摸屏、數(shù)據(jù)手套、數(shù)字化儀、掃描儀等輸入設(shè)備。和圖形硬件一樣，圖形軟件也得到很大的發(fā)展，各種圖形算法、圖形標(biāo)準(zhǔn)、圖形數(shù)據(jù)結(jié)構(gòu)等逐漸成熟并投入使用，使計(jì)算機(jī)圖形學(xué)成為一門成熟的學(xué)科。1.3計(jì)算機(jī)圖形學(xué)的應(yīng)用領(lǐng)域圖形比文字更直觀、逼真且信息載荷量大，隨著計(jì)算機(jī)圖形學(xué)的發(fā)展，以及計(jì)算機(jī)軟、硬件性能的提高和成本下降，用計(jì)算機(jī)處理圖形的領(lǐng)域越來(lái)越廣泛，下面是一些主要的應(yīng)用領(lǐng)域。一、計(jì)算機(jī)輔助設(shè)計(jì)與制造（CAD/CAM）這是一個(gè)最廣泛、最活躍的應(yīng)用領(lǐng)域，在機(jī)械、建筑、汽車、飛機(jī)、造船、電子等領(lǐng)域有著廣泛的應(yīng)用。如機(jī)械結(jié)構(gòu)和零部件的設(shè)計(jì)，土木建筑工程及其圖紙的設(shè)計(jì)，汽車、飛機(jī)、輪船的外形設(shè)計(jì)，集成電路、印刷線路板的設(shè)計(jì)等。過(guò)去在這些設(shè)計(jì)工作中，用的是繪圖板加丁字尺的傳統(tǒng)設(shè)計(jì)方法，現(xiàn)在正迅速地被CAD技術(shù)所代替。使用CAD技術(shù)后，不僅提高了設(shè)計(jì)效率，縮短了設(shè)計(jì)周期，改善了設(shè)計(jì)質(zhì)量，降低了設(shè)計(jì)成本，而且可以為后續(xù)工序的計(jì)算機(jī)輔助制造（CAM）建立起CAD數(shù)據(jù)庫(kù)，使CAD/CAM聯(lián)成一體，為生產(chǎn)自動(dòng)化奠定基礎(chǔ)。CAD/CAM是高新技術(shù)，是先進(jìn)的生產(chǎn)力，它已經(jīng)并將進(jìn)一步給人類帶來(lái)巨大的影響和利益?，F(xiàn)在，CAD技術(shù)的水平已成為衡量一個(gè)國(guó)家工業(yè)技術(shù)水平的重要標(biāo)志。二、科學(xué)計(jì)算可視化用圖形來(lái)表示大量數(shù)據(jù)計(jì)算的結(jié)果或中間過(guò)程。例如：

·科技工作者需要認(rèn)真分析大量的計(jì)算結(jié)果以確定一個(gè)系統(tǒng)的描述；

·商業(yè)主管需要分析大量的統(tǒng)計(jì)數(shù)據(jù)以做出對(duì)未來(lái)商業(yè)行為的決策；

·醫(yī)生需要面對(duì)大量的CT數(shù)據(jù)以確定病人體內(nèi)是否發(fā)生病變及何處發(fā)生病變；

·氣象人員需要處理氣象衛(wèi)星傳回的大批數(shù)據(jù)以繪出未來(lái)一段時(shí)間內(nèi)的天氣變化趨勢(shì)圖。分析處理這些大批數(shù)據(jù)是艱難和枯燥的，但如果應(yīng)用計(jì)算機(jī)圖形處理技術(shù)建立數(shù)據(jù)與圖形之間的關(guān)系并將它們以圖形的形式在屏幕上顯示出來(lái)，則使用者很容易觀察其中的各種現(xiàn)象并找出變化規(guī)律。這種研究如何將來(lái)自科學(xué)、工程、醫(yī)學(xué)等領(lǐng)域的抽象數(shù)據(jù)用圖形表示的學(xué)科稱為科學(xué)計(jì)算可視化?？梢暬夹g(shù)發(fā)展很快，已廣泛應(yīng)用于流體力學(xué)、有限元分析、醫(yī)學(xué)、遙感等領(lǐng)域。三、地理信息系統(tǒng)與制圖地理信息系統(tǒng)是建立在地理圖形之上的關(guān)于人口分布、礦藏分布、森林覆蓋、土地利用、旅游資源、海洋地理、地形地貌、山川河流分布、區(qū)域規(guī)劃、城市交通、管線管網(wǎng)等綜合信息管理系統(tǒng)。目前，它在發(fā)達(dá)國(guó)家中已得到廣泛應(yīng)用，我國(guó)也對(duì)其開展了廣泛的研究與應(yīng)用，全國(guó)數(shù)十所高校也紛紛設(shè)置地理信息系統(tǒng)專業(yè)。在地理信息系統(tǒng)中，計(jì)算機(jī)圖形技術(shù)被用來(lái)產(chǎn)生高精度的上述各種資源的專題圖，并為管理者提供有效的決策和幫助。四、事務(wù)管理和辦公自動(dòng)化無(wú)論是企業(yè)還是事業(yè)行政管理中，都存在著大量的圖表，如作業(yè)進(jìn)程表、生產(chǎn)產(chǎn)量表、庫(kù)存表、銷售統(tǒng)計(jì)圖、生產(chǎn)計(jì)劃表，以及統(tǒng)計(jì)分析方面的各種圖表。這些圖表都可以用計(jì)算機(jī)圖形技術(shù)產(chǎn)生的直方圖、餅圖和折線圖來(lái)表示。在辦公自動(dòng)化方面，各國(guó)都非常重視。辦公自動(dòng)化系統(tǒng)可以從聯(lián)網(wǎng)的數(shù)據(jù)庫(kù)中，取出所需要的數(shù)據(jù)，用清晰明了的圖表在屏幕上顯示或在打印機(jī)、繪圖儀上輸出。五、虛擬現(xiàn)實(shí)系統(tǒng)虛擬現(xiàn)實(shí)又稱為虛擬環(huán)境，是指由計(jì)算機(jī)實(shí)時(shí)生成一個(gè)虛擬的三維空間。這個(gè)空間可以是小到分子、原子的微觀世界，或是大到天體的宏觀世界，也可以是類似于真實(shí)社會(huì)的生活空間。用戶可以在這個(gè)三維空間中“自由”地走動(dòng)，隨意地觀察，并可以通過(guò)一些特殊的設(shè)備與所處的虛擬景物進(jìn)行交互操作。交互是多通道的、自然的，用來(lái)傳遞的信息可以是某個(gè)操作、一個(gè)手勢(shì)、一個(gè)眼神，也可以是一個(gè)表情等。在此環(huán)境中，用戶看到的是由計(jì)算機(jī)生成的逼真圖像，聽到的是虛擬環(huán)境中的聲音，身體可以感受到虛擬環(huán)境所反饋的作用力，由此產(chǎn)生身臨其境的感覺(jué)。虛擬現(xiàn)實(shí)技術(shù)主要研究用計(jì)算機(jī)模擬三維圖形空間，并使用戶能夠自然地與該空間進(jìn)行交互。在模擬訓(xùn)練中，可以用來(lái)訓(xùn)練飛機(jī)駕駛員操縱飛機(jī)飛行、訓(xùn)練宇航員駕駛登月艙登月。在模擬訓(xùn)練中，駕駛員的操作實(shí)時(shí)地變換成三維場(chǎng)景并投影在球形房間的內(nèi)壁上，以模擬空中飛行的環(huán)境和狀態(tài)，同時(shí)配上模擬飛行的音響效果，使駕駛員在訓(xùn)練駕駛艙內(nèi)所見到的外部景物如同在真實(shí)的空中一樣。這樣的訓(xùn)練，既安全又方便，且節(jié)省了訓(xùn)練費(fèi)用。目前，該技術(shù)已在航空航天、醫(yī)學(xué)、教育、藝術(shù)、建筑等領(lǐng)域得到初步的應(yīng)用。六、過(guò)程控制和指揮系統(tǒng)將各種實(shí)時(shí)過(guò)程的重要參數(shù)，如火箭的運(yùn)行狀態(tài)，煉油廠、發(fā)電廠和電力系統(tǒng)送來(lái)的壓力、溫度、電壓、電流等數(shù)據(jù)傳送到計(jì)算機(jī)，用圖形方式進(jìn)行顯示，管理人員對(duì)圖形進(jìn)行監(jiān)控，并對(duì)異常情況作出調(diào)整。此外，現(xiàn)在大量的指揮系統(tǒng)，軍用指揮、鐵路調(diào)度、機(jī)場(chǎng)指揮等系統(tǒng)，也用圖形進(jìn)行監(jiān)視與控制。七、計(jì)算機(jī)動(dòng)畫為了產(chǎn)生連續(xù)的動(dòng)畫，每秒至少需要24幀畫面。因而，一部?jī)尚r(shí)的動(dòng)畫片就需要十幾萬(wàn)張畫面，如果用傳統(tǒng)的方式手工繪制，工作量是巨大的。首先要由原畫設(shè)計(jì)師創(chuàng)作出人物、場(chǎng)景的關(guān)鍵畫面，而兩個(gè)關(guān)鍵畫面之間的變化過(guò)程由其它動(dòng)畫工作者逐張完成。中間畫的張數(shù)取決于人物動(dòng)作變化的幅度及運(yùn)動(dòng)規(guī)律，要使動(dòng)作過(guò)渡得平滑自然。60年代制作動(dòng)畫片《大鬧天宮》時(shí)，就花了幾十位動(dòng)畫工作者近兩年的時(shí)間。如果用計(jì)算機(jī)圖形技術(shù)來(lái)制作，一方面可以利用造型工具創(chuàng)作出形象逼真的演員、場(chǎng)景，另一方面可以在關(guān)鍵畫面之間利用圖形變換技術(shù)自動(dòng)插入中間畫面。這樣大大提高了動(dòng)畫制作的質(zhì)量和效率?，F(xiàn)在，基于計(jì)算機(jī)圖形技術(shù)的計(jì)算機(jī)動(dòng)畫軟件3DMAX、ComputerAnimation被廣泛用于電視廣告、節(jié)目片頭、科教演示、電子游戲等的制作。1.4圖形硬件設(shè)備與一般計(jì)算機(jī)系統(tǒng)一樣，計(jì)算機(jī)圖形系統(tǒng)也是由硬件和軟件兩部分組成。硬件包括主機(jī)、輸入設(shè)備和輸出設(shè)備。輸入設(shè)備通常為鍵盤、鼠標(biāo)、數(shù)字化儀、掃描儀和光筆等。輸出設(shè)備則為圖形顯示器、繪圖儀和打印機(jī)。這里主要介紹圖形輸出設(shè)備，而圖形輸入設(shè)備的內(nèi)容放在交互技術(shù)那一章去介紹。1.4.1顯示設(shè)備圖形系統(tǒng)一般使用視頻顯示器作為基本的輸出設(shè)備，目前大部分視頻顯示器的操作是基于標(biāo)準(zhǔn)的陰極射線管（CRT：CathodeRayTube）設(shè)計(jì)的。此外，還有液晶顯示器和等離子板顯示器等，它們體積小，功耗少，主要用于便攜式電腦上。一、刷新式CRT刷新式CRT結(jié)構(gòu)示意圖如下圖所示。CRT由五部分組成：電子槍、加速電極、聚焦系統(tǒng)、偏轉(zhuǎn)系統(tǒng)和熒光屏，這五部分都封裝在真空管內(nèi)。

刷新式CRT結(jié)構(gòu)示意圖電子槍由燈絲、陰極和控制柵極組成。燈絲加熱陰極，陰極表面向外發(fā)射自由電子，控制柵控制自由電子發(fā)出的強(qiáng)弱。發(fā)出的電子在加速電極的作用下，形成一股高速的電子束，在到達(dá)屏幕的途中，被聚焦系統(tǒng)（電子透鏡）聚焦成很細(xì)的電子束，再由偏轉(zhuǎn)系統(tǒng)產(chǎn)生偏轉(zhuǎn)電場(chǎng)（或磁場(chǎng)），使得電子束左右、上下偏轉(zhuǎn)，從而控制熒光屏上的光點(diǎn)落在指定的位置上。熒光屏上涂有一層熒光粉，受到電子束打擊時(shí)會(huì)發(fā)出熒光。當(dāng)打擊結(jié)束后，熒光仍會(huì)保持一段時(shí)間才消失，這種現(xiàn)象稱為余輝，熒光亮度隨著時(shí)間按指數(shù)衰減，為了使人們看到一個(gè)穩(wěn)定而不閃爍的圖形，整個(gè)畫面必須在每秒鐘內(nèi)重復(fù)顯示許多次，這也稱為屏幕刷新。CRT上用的熒光物質(zhì)有多種，除顏色不同外，熒光物質(zhì)的主要差別在于它們的余輝保持時(shí)間，短余輝熒光層需要較高刷新速度，才能保證屏幕圖像不閃爍。短余輝熒光層用于動(dòng)畫，而長(zhǎng)余輝熒光層則用來(lái)顯示高復(fù)雜程度的靜態(tài)圖形。對(duì)于圖形顯示CRT，通常采用余輝時(shí)間為10μs～60μs的熒光材料。二、彩色CRT顯示器CRT顯示器利用能發(fā)射不同顏色的熒光物質(zhì)的組合來(lái)顯示彩色圖形。組合不同熒光物質(zhì)的發(fā)射光，便能生成一定范圍的彩色。用CRT產(chǎn)生彩色顯示的兩種基本技術(shù)是電子束穿透法和蔭罩法。電子束穿透法用于隨機(jī)掃描顯示器。兩層熒光層，通常是一紅一綠，涂覆在CRT屏幕的內(nèi)層，而顯示的顏色取決于電子束穿透進(jìn)熒光層的深淺。慢速的電子束只激活外面的紅色層，快速的電子束穿過(guò)紅色層并激活里面的綠色層。而中速的電子束，通過(guò)紅、綠光發(fā)射的組合，來(lái)生成另外的兩種顏色：橙色和黃色。電子束穿透法是隨機(jī)掃描顯示器生成彩色的廉價(jià)途徑，但只可能有四色，而且圖形質(zhì)量不如其它方法。蔭罩法常用于光柵掃描系統(tǒng)，因?yàn)樗墚a(chǎn)生的彩色范圍比電子束穿透法寬廣得多。在每個(gè)象素位置上分布著呈三角形排列的三個(gè)熒光彩色點(diǎn)，三個(gè)熒光點(diǎn)分別發(fā)射紅光、綠光和藍(lán)光。

紅、綠、藍(lán)三個(gè)熒光點(diǎn)呈三角形排列這樣的彩色CRT有三支電子槍，分別與三個(gè)熒光點(diǎn)相對(duì)應(yīng)，即每支電子槍發(fā)出的電子束專門用于轟擊某一個(gè)熒光點(diǎn)。而蔭罩板被安裝在緊靠熒光涂層的地方，板上有很多小孔，每個(gè)小孔與一個(gè)象素（即三個(gè)熒光點(diǎn)）相對(duì)應(yīng)。三個(gè)電子束經(jīng)聚焦偏轉(zhuǎn)后穿過(guò)蔭罩板上的小孔，激活該小孔對(duì)應(yīng)的三個(gè)熒光點(diǎn)。由于三個(gè)熒光點(diǎn)很小并充分靠近，我們觀察到的是它們混合顏色的一個(gè)光點(diǎn)，即象素。屏幕上的熒光點(diǎn)、蔭罩板上的小孔和電子槍被精確地安排處于一條直線上，使得由某一電子槍發(fā)出的電子束只能轟擊到它所對(duì)應(yīng)的熒光點(diǎn)上。這樣，只要調(diào)節(jié)各電子槍發(fā)出電子束的強(qiáng)弱，即可控制各象素中三個(gè)熒光點(diǎn)所發(fā)出的紅、綠、藍(lán)三色光的亮度。于是我們可以根據(jù)彩色中所含紅、綠、藍(lán)三色的數(shù)量，以不同的強(qiáng)度激勵(lì)三個(gè)熒光點(diǎn)，從而可以產(chǎn)生范圍很廣的彩色。假如每個(gè)電子槍發(fā)出電子束的強(qiáng)度有256個(gè)等級(jí)，則該顯示器能顯示16兆種顏色，即：28×28×28=224。能顯示16兆種顏色的顯示系統(tǒng)叫做真彩色顯示系統(tǒng)。

CRT產(chǎn)生彩色的工作原理三、隨機(jī)掃描顯示器隨機(jī)掃描顯示器中，電子束可以在任意方向上自由移動(dòng)，按照顯示命令用畫線的方式繪出圖形，因此也稱矢量顯示器。在隨機(jī)掃描顯示系統(tǒng)中，圖形的定義以矢量畫線命令的形式存放在顯示文件中，所以依靠顯示文件對(duì)屏幕圖形進(jìn)行刷新。應(yīng)用程序若要修改屏幕上的圖形，則要修改顯示文件中的某些繪圖命令，修改的結(jié)果在下一次刷新時(shí)得到體現(xiàn)。

隨機(jī)掃描方式顯示圖形圖中的顯示處理器DPU可以看作是一個(gè)專用的CPU，具有自己的一套指令系統(tǒng)、數(shù)據(jù)格式和指令計(jì)數(shù)器，同時(shí)還有一些功能部件，如矢量產(chǎn)生器、字符產(chǎn)生器等。在工作過(guò)程中，它依次讀取顯示文件中的指令系列，進(jìn)行譯碼、解釋、并啟動(dòng)功能部件在CRT上畫出點(diǎn)、線、字符串等。隨機(jī)掃描顯示器是為畫線應(yīng)用設(shè)計(jì)的，由于圖形修改方便，因此交互性能較好，圖形可以作無(wú)級(jí)放大，而不會(huì)出現(xiàn)鋸齒狀。但不能顯示色彩逼真圖形，另外圖形的顯示質(zhì)量與一幀的畫線數(shù)量有關(guān)，當(dāng)一幀線劃太多，無(wú)法維持30～60幀/秒的刷新頻率時(shí)，就會(huì)出現(xiàn)滿屏閃爍。四、光柵掃描顯示器普通使用的CRT圖形監(jiān)視器是基于電視技術(shù)的光柵掃描顯示器。光柵掃描的CRT中，電子束依照固定的掃描線和規(guī)定的掃描順序進(jìn)行掃描。電子束先從熒光屏左上角開始，向右掃一條水平線，然后迅速地回掃到左邊偏下一點(diǎn)的位置，再掃第二條水平線，照此固定的路徑及順序掃下去，直到最后一條水平線，即完成了整個(gè)屏幕的掃描。在掃描時(shí)，電子束的強(qiáng)度不斷變化來(lái)建立亮點(diǎn)的圖案。圖形定義存放在幀緩沖存儲(chǔ)器中，幀緩存保存了對(duì)應(yīng)屏幕所有點(diǎn)的亮度值。每個(gè)屏幕點(diǎn)稱作象素，由于光柵掃描CRT對(duì)屏幕上每個(gè)象素都有存儲(chǔ)亮度信息的能力，因此它能較好地用于包含細(xì)微陰影和彩色場(chǎng)景的逼真顯示。家用電視和打印機(jī)是另一類使用光柵掃描方式的例子。

幀緩存中的單元與屏幕象素的對(duì)應(yīng)關(guān)系光柵掃描顯示器中，屏幕圖形是依靠幀緩存進(jìn)行刷新的，而視頻控制器是負(fù)責(zé)刷新的部件，它建立了幀緩存中的單元與屏幕象素之間一一對(duì)應(yīng)的關(guān)系，視頻控制器的邏輯結(jié)構(gòu)如下圖所示：X、Y寄存器用來(lái)存放屏幕象素的坐標(biāo)，存儲(chǔ)在幀緩存中該象素對(duì)應(yīng)位置的值被取出，并用來(lái)控制CRT電子束的強(qiáng)度。從左到右，從上到下，對(duì)一幀的每一個(gè)象素都進(jìn)行處理后，又重復(fù)上述過(guò)程進(jìn)行下一輪的刷新。

視頻控制器的邏輯結(jié)構(gòu)象素的亮度范圍取決于幀緩存的位數(shù)。在簡(jiǎn)單的黑白顯示中，每個(gè)象素只有兩個(gè)亮度值：亮、暗，因此每個(gè)象素只需一位來(lái)控制屏幕位置的亮度。如果要顯示彩色并且亮度可變，就需要增加位，在高質(zhì)量系統(tǒng)中，每個(gè)象素可多達(dá)24位（紅、綠、藍(lán)三基色，每種基色占8位：8×3=24位），這時(shí)每個(gè)象素可顯示224種亮度值。工作于高分辨率和真彩色模式下的光柵系統(tǒng)顯示的圖形精度高、質(zhì)量好，但也帶來(lái)兩個(gè)問(wèn)題：其一是需要大容量的幀緩存，例如當(dāng)屏幕分辨率為1024×1024，每個(gè)象素24位（以真彩色顯示）時(shí)，幀緩存的容量需要：1024×1024×24/8=3M字節(jié)；其二是要求視頻控制器對(duì)幀緩存有較快的存取速度，通信線路有較大的傳輸帶寬。解決的辦法也有兩個(gè)：采用彩色表機(jī)制和采用隔行掃描方法。1、彩色表彩色表是一維的線性表，它用來(lái)定義象素的顏色。我們知道要顯示很多種顏色，幀緩存的容量就要很大。但實(shí)際上對(duì)一幅具體的畫面而言，其使用的顏色數(shù)目并不多（幾百至幾千種）。為了解決幀緩存容量不能過(guò)大而又滿足實(shí)際需要，產(chǎn)生了彩色表，彩色表又稱為調(diào)色板，它的工作原理如下圖所示。從圖中可以看到，幀緩存各單元保存的不再是相應(yīng)象素的顏色值，而僅是該象素顏色的一個(gè)索引，它是彩色表的某個(gè)地址，按照這個(gè)索引值在彩色表中取出紅、綠、藍(lán)三種顏色的分量，然后送CRT顯示器對(duì)該象素進(jìn)行顏色顯示。

采用彩色表的光柵掃描顯示系統(tǒng)的工作原理假設(shè)彩色表的長(zhǎng)度為256，而該表中的顏色又是從待顯示畫面中挑選出來(lái)的最具代表性的顏色，則顯示出來(lái)的畫面一般來(lái)說(shuō)質(zhì)量相當(dāng)不錯(cuò)。目前，各種格式的圖像文件中都帶有彩色表數(shù)據(jù)。2、掃描方法在光柵CRT中，因?yàn)閹彺胬锎娣帕艘粠瑘D像的亮度信息，所以依靠幀緩存對(duì)屏幕進(jìn)行刷新，刷新頻率一般為50～60幀/秒。圖像再現(xiàn)時(shí)，有兩種掃描方法：逐行掃描（見下圖）從屏幕頂端第0行開始，逐行往下掃。在每一行掃完回到下一行時(shí)，回掃線是被消隱的，從屏幕頂部到底部掃描一次稱為一幀，由底部再回到頂部的回掃過(guò)程也是消隱的。隔行掃描（見下圖）將掃描分成兩場(chǎng)，先掃描偶數(shù)行0、2、4、6…，再掃描奇數(shù)行1、3、5、7…，順序從頂部掃描到底部。隔行掃描只需用逐行掃描一半的時(shí)間就能看見整個(gè)屏幕顯示，因此隔行掃描技術(shù)用于較慢的刷新頻率。例如刷新頻率為30幀/秒，如采用逐行掃描顯示，可注意到圖形在閃爍，但采用隔行掃描，掃描一幀的時(shí)間只用了原來(lái)一半，也就是說(shuō)刷新頻率接近60幀/秒，這時(shí)圖形顯示質(zhì)量提高，不再閃爍。

掃描方法光柵掃描顯示器最突出的優(yōu)點(diǎn)是：它不僅可以顯示物體的輪廓線，而且由于能對(duì)每一象素的灰度或色彩控制，因而可以進(jìn)行實(shí)面積填充，這就使得輸出真實(shí)感圖形成為可能。此外，它可以和電視兼容，價(jià)格遠(yuǎn)低于隨機(jī)掃描顯示器。自80年代以來(lái)，得到迅速發(fā)展，其應(yīng)用領(lǐng)域也不斷擴(kuò)大，已成為顯示器市場(chǎng)的主流。光柵掃描顯示器的缺點(diǎn)是：從應(yīng)用程序中將圖形的描述轉(zhuǎn)換成幀緩存中象素信息的過(guò)程（掃描轉(zhuǎn)換）比較費(fèi)時(shí)，相應(yīng)的軟件比較復(fù)雜。另外，在顯示斜線時(shí)，還存在線條邊緣的階梯效應(yīng)。五、直視存儲(chǔ)管顯示器直視存儲(chǔ)管顯示器DVST（Direct－ViewStorageTube）是20世紀(jì)60年代后期開始出現(xiàn)的圖形顯示器，它的最大特點(diǎn)在于它的熒光粉能夠在足夠長(zhǎng)的時(shí)間內(nèi)（以小時(shí)計(jì)）保持圖形而不需要刷新，因此價(jià)格低廉，工作中可以不閃爍地顯示任意多的線條和字符，而且相當(dāng)清晰。直視存儲(chǔ)管顯示器顯示圖形的方式和隨機(jī)掃描顯示器一樣，電子束在屏幕上隨機(jī)繪出圖形，同樣它也只能畫線圖，不能進(jìn)行實(shí)面積填充。直視存儲(chǔ)管顯示器的致命弱點(diǎn)在于圖形的修改和刪除方面，它只能一次擦除整屏的圖形，而且擦除時(shí)間長(zhǎng)達(dá)數(shù)秒，若想有選擇地擦除某一部分圖形則是不可能的。這樣，就限制了它在動(dòng)態(tài)作圖和交互修改作圖方面的應(yīng)用。1.4.2硬拷貝設(shè)備圖形顯示器用于觀察、修改圖形，但是屏幕上的圖形不可能長(zhǎng)久地保存下來(lái)，在工程界還需要變成圖紙或膠片用于生產(chǎn)，因此在計(jì)算機(jī)圖形系統(tǒng)中還應(yīng)該有繪圖機(jī)這樣的圖形硬拷貝輸出設(shè)備。象顯示器一樣，圖形硬拷貝輸出設(shè)備的發(fā)展也非常迅速，且種類繁多，它的發(fā)展動(dòng)向正朝著高速度、高精度、高性能、大面積、低成本的方向發(fā)展。一、打印機(jī)打印機(jī)以兩種方式：擊打式或非擊打式產(chǎn)生輸出。擊打式打印機(jī)隔著色帶將某種格式的字符打在紙上。行式打印機(jī)是擊打設(shè)備的例子，其字體裝在帶上、鏈上、鼓上或輪上。非擊打式打印機(jī)和繪圖儀用激光技術(shù)、噴墨技術(shù)、復(fù)印技術(shù)（照相拷貝）、靜電方式和電熱方式，把圖像印在紙上。字符擊打式打印機(jī)常常有一個(gè)點(diǎn)陣打印頭，其中包含有一組矩形陣列結(jié)構(gòu)金屬針，針的總數(shù)決定著打印機(jī)的質(zhì)量，單個(gè)字符或圖案可用縮回某些針而讓余下的針來(lái)打印。打印機(jī)實(shí)物圖二、激光設(shè)備在激光設(shè)備里，激光束把要打印的圖形寫在感光鼓上，鼓再把這一圖形轉(zhuǎn)移到紙上。激光打印機(jī)的主要構(gòu)成部分有感光鼓、炭粉、打底電暈絲和轉(zhuǎn)移電暈絲。

激光打印機(jī)結(jié)構(gòu)圖三、噴墨設(shè)備噴墨法產(chǎn)生的輸出，是沿包裹在鼓上的紙卷逐行噴墨水來(lái)實(shí)現(xiàn)的。在高壓下墨水形成墨霧，充電荷的墨霧在電場(chǎng)控制下發(fā)生偏轉(zhuǎn)，將墨霧噴印到紙上。噴繪儀實(shí)物圖四、靜電設(shè)備靜電設(shè)備沿紙的寬度方向一次一整行地置負(fù)電荷于紙上，爾后，面對(duì)調(diào)色劑曝光。調(diào)色劑充以正電，被吸引到充以負(fù)電的區(qū)域，從而產(chǎn)生指定的輸出。靜電繪圖儀分辨率可達(dá)200dpi，其速度比筆繪儀高，運(yùn)行可靠，噪聲小，但用紙?zhí)厥舛鴥r(jià)格昂貴。靜電繪圖儀結(jié)構(gòu)圖五、電熱式設(shè)備電熱式利用點(diǎn)陣打印頭的熱度，在熱感應(yīng)紙上輸出圖案。熱升華打印機(jī)六、筆繪儀筆繪儀有一支或多支筆安裝在橫跨紙的筆架或滑桿上，各種彩色和不同粗細(xì)的筆用來(lái)繪制各種陰影和線型。與前面幾種點(diǎn)陣硬拷貝設(shè)備不同，筆繪儀屬于隨機(jī)畫線硬拷貝設(shè)備。筆繪儀的繪圖速度取決于繪圖筆移動(dòng)的速度和加速度。這里，加速度和筆繪儀筆頭的質(zhì)量有關(guān)。機(jī)械傳動(dòng)式繪圖儀結(jié)構(gòu)圖平面電機(jī)式繪圖儀結(jié)構(gòu)圖1.5圖形軟件系統(tǒng)硬件是實(shí)現(xiàn)繪圖的必要條件，但要保證具有良好的信息處理能力、較高的繪圖速度與精度、清晰美觀的圖形、操作使用方便，則必須有足夠先進(jìn)的軟件支持系統(tǒng)。圖形軟件系統(tǒng)涉及：圖形應(yīng)用數(shù)據(jù)結(jié)構(gòu)、圖形應(yīng)用程序、圖形軟件包及圖形接口等內(nèi)容。一、圖形應(yīng)用數(shù)據(jù)結(jié)構(gòu)圖形應(yīng)用數(shù)據(jù)結(jié)構(gòu)實(shí)際上是一組圖形數(shù)據(jù)文件，其中存儲(chǔ)了欲生成圖形對(duì)象的全部描述信息。這些信息包括對(duì)象的幾何坐標(biāo)數(shù)據(jù)，對(duì)象的顏色、線型（實(shí)線、虛線、點(diǎn)劃線等）、紋理等屬性，以及對(duì)象各部分之間連接關(guān)系的數(shù)據(jù)，有時(shí)還可能包括對(duì)象的某些專業(yè)屬性，如：比重、價(jià)格、材料、高程、植被等。在計(jì)算機(jī)圖形學(xué)中，根據(jù)這類信息的詳細(xì)描述，生成對(duì)應(yīng)的圖形，并完成對(duì)這些圖形的操作和處理。所以，圖形應(yīng)用數(shù)據(jù)結(jié)構(gòu)是生成圖形的基礎(chǔ)。二、圖形應(yīng)用程序圖形應(yīng)用程序在整個(gè)圖形軟件系統(tǒng)中起著主控的作用。它一方面根據(jù)應(yīng)用問(wèn)題的要求，從應(yīng)用數(shù)據(jù)結(jié)構(gòu)中提取數(shù)據(jù)，調(diào)用圖形包的相關(guān)子程序，完成作圖或?qū)D形進(jìn)行各種處理；另一方面，它又接受操作員的輸入信息，作出相應(yīng)的反應(yīng)（如修改或增刪數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)項(xiàng)，改變作圖模式，重新作圖等）；此外，它還包括用戶界面的一些操作：菜單提示、文件存取、圖形設(shè)備接口的調(diào)用、圖形圖像格式的轉(zhuǎn)換、系統(tǒng)維護(hù)、信息提示、幫助等等，從而構(gòu)成一個(gè)功能完整的圖形軟件系統(tǒng)環(huán)境。三、圖形軟件包圖形軟件包是圖形軟件的核心，它實(shí)際上是由許多圖形子程序所組成。圖形軟件包在操作系統(tǒng)上建立了面向圖形的輸入、輸出、生成、坐標(biāo)變換、修改等功能命令，以及系統(tǒng)調(diào)用和定義標(biāo)準(zhǔn)，而且要求對(duì)用戶透明，與所采用的圖形設(shè)備無(wú)關(guān)，與所使用的程序設(shè)計(jì)語(yǔ)言無(wú)關(guān)，接口友善、技術(shù)相容。這些被用戶所承認(rèn)和廣泛應(yīng)用的圖形軟件包，形成了一個(gè)為大家都接受的圖形標(biāo)準(zhǔn)，就像現(xiàn)在所通用流行的GKS、GKS-3D、PHIGS、CORE等圖形標(biāo)準(zhǔn)。采用圖形標(biāo)準(zhǔn)開發(fā)的圖形軟件包的優(yōu)點(diǎn)是：不受機(jī)器的限制、與應(yīng)用無(wú)關(guān)、與設(shè)備無(wú)關(guān)、與語(yǔ)言無(wú)關(guān)，因而降低軟件研制費(fèi)用，方便應(yīng)用軟件在不同系統(tǒng)間的移植。四、圖形接口圖形接口把與設(shè)備無(wú)關(guān)的圖形軟件包與具體的圖形設(shè)備隔離開來(lái)，在兩者之間建立起橋梁。目前國(guó)際標(biāo)準(zhǔn)化組織（ISO）公布的圖形設(shè)備接口標(biāo)準(zhǔn)是CGI。第二章二維基本圖形的生成重點(diǎn)：掌握二維圖元直線、圓、區(qū)域填充、字符的生成算法。難點(diǎn)：理解二維圖元生成的算法思想并且用C語(yǔ)言進(jìn)行算法的實(shí)現(xiàn)。課時(shí)安排：授課8學(xué)時(shí)（直線、圓：3學(xué)時(shí)；區(qū)域填充：4學(xué)時(shí)；字符：1學(xué)時(shí)）；上機(jī)4學(xué)時(shí)（直線、圓：2學(xué)時(shí)；區(qū)域填充：2學(xué)時(shí)）。

圖元生成算法的要求：準(zhǔn)確、亮度均勻、速度快。前面已經(jīng)知道，矢量顯示（隨機(jī)掃描顯示器）和光柵顯示是兩種完全不同的圖形顯示技術(shù)。目前，光柵顯示技術(shù)占主要地位。原因是：1、光柵顯示可以用顏色或圖案來(lái)填充一個(gè)區(qū)域；

2、光柵顯示以象素為單位進(jìn)行讀寫和存儲(chǔ)，可以實(shí)現(xiàn)對(duì)物體細(xì)節(jié)的描述；

3、圖形的任意部分均可以被移動(dòng)和復(fù)制。在這一章里，主要介紹在光柵輸出設(shè)備上，根據(jù)物體的坐標(biāo)描述構(gòu)造二維幾何圖形的方法。在光柵顯示器上，象素是屏幕的最小顯示單位，因此二維圖形的構(gòu)造就是找出最靠近所描述幾何圖形的那些象素，將它們置入規(guī)定的顏色并放入幀緩存。我們知道，一幅圖是由點(diǎn)、直線、曲線、多邊形填充區(qū)域以及字符串等組成。下面將討論這些基本圖元的生成技術(shù)和算法。

2.1直線的掃描轉(zhuǎn)換一、數(shù)學(xué)直線在數(shù)學(xué)上，理想的直線是一條由無(wú)窮多個(gè)無(wú)限小的連續(xù)的點(diǎn)組成。數(shù)學(xué)直線二、光柵平面顯示的直線但在光柵顯示平面上，我們只能用二維光柵格網(wǎng)上盡可能靠近這條直線的象素點(diǎn)的集合來(lái)表示它。每個(gè)象素具有一定的尺寸，是顯示平面上可被訪問(wèn)的最小單位，它的坐標(biāo)x和y只能是整數(shù)，也就是說(shuō)相鄰象素的坐標(biāo)值是階躍的而不是連續(xù)的。光柵直線三、直線的掃描轉(zhuǎn)換直線的掃描轉(zhuǎn)換，就是要找出顯示平面上最佳逼近理想直線的那些象素的坐標(biāo)值，并將這些象素置成所要求的顏色。直線的掃描轉(zhuǎn)換由于一幅圖中可能包含成千上萬(wàn)條直線，所以要求繪制算法應(yīng)該：1、最接近數(shù)學(xué)上的直線；2、沿著線段分布的象素應(yīng)均勻；不均勻的例子如下圖所示，對(duì)同樣長(zhǎng)的線段，如果進(jìn)行圖中的掃描轉(zhuǎn)換，就會(huì)因?yàn)樾甭实牟煌?，產(chǎn)生的象素個(gè)數(shù)不相等，這樣將導(dǎo)致象素亮度分布不均勻。3、畫線速度盡可能的快。本節(jié)我們介紹兩個(gè)常用的直線生成算法：數(shù)值微分法（\o"2.1.1生成直線的DDA算法"DDA）和\o"2.1.2生成直線的Bresenham算法"Bresenham算法。2.1.1生成直線的DDA算法數(shù)值微分法即DDA法(DigitalDifferentialAnalyzer)，是一種基于直線的微分方程來(lái)生成直線的方法。一、直線DDA算法描述：設(shè)(x1，y1)和(x2，y2)分別為所求直線的起點(diǎn)和終點(diǎn)坐標(biāo)，由直線的微分方程得=m=直線的斜率(2－1)可通過(guò)計(jì)算由x方向的增量△x引起y的改變來(lái)生成直線：xi+1=xi+△x(2－2)yi+1=yi+△y=yi+△x·m(2－3)也可通過(guò)計(jì)算由y方向的增量△y引起x的改變來(lái)生成直線：yi+1=yi+△y(2－4)xi+1=xi+△x=xi+△y/m(2－5)式(2－2)至(2－5)是遞推的。二、直線DDA算法思想：選定x2－x1和y2－y1中較大者作為步進(jìn)方向(假設(shè)x2－x1較大)，取該方向上的增量為一個(gè)象素單位(△x=1)，然后利用式(2－1)計(jì)算另一個(gè)方向的增量(△y=△x·m=m)。通過(guò)遞推公式(2－2)至(2－5)，把每次計(jì)算出的(xi+1，yi+1)經(jīng)取整后送到顯示器輸出，則得到掃描轉(zhuǎn)換后的直線。之所以取x2－x1和y2－y1中較大者作為步進(jìn)方向，是考慮沿著線段分布的象素應(yīng)均勻，這在下圖中可看出。另外，算法實(shí)現(xiàn)中還應(yīng)注意直線的生成方向，以決定Δx及Δy是取正值還是負(fù)值。三、直線DDA算法實(shí)現(xiàn)：1、已知直線的兩端點(diǎn)坐標(biāo)：(x1，y1)，(x2，y2)

2、已知畫線的顏色：color

3、計(jì)算兩個(gè)方向的變化量：dx=x2－x1

dy=y2－y1

4、求出兩個(gè)方向最大變化量的絕對(duì)值：

steps=max(|dx|，|dy|)

5、計(jì)算兩個(gè)方向的增量(考慮了生成方向)：

xin=dx/steps

yin=dy/steps

6、設(shè)置初始象素坐標(biāo)：x=x1,y=y1

7、用循環(huán)實(shí)現(xiàn)直線的繪制：

for(i=1；i<=steps；i++)

{putpixel(x，y，color)；/*在(x，y)處，以color色畫點(diǎn)*/

x=x+xin；

y=y+yin；

}四、直線DDA算法特點(diǎn)：該算法簡(jiǎn)單，實(shí)現(xiàn)容易，但由于在循環(huán)中涉及實(shí)型數(shù)的運(yùn)算，因此生成直線的速度較慢。五、直線DDA算法程序：#include<math.h>

voidDDALine(intx1,inty1,intx2,inty2,intcolor)

{

floatincrex，increy,x,y;

intsteps,i;

if(abs(x2－x1)>abs(y2－y1))

steps=abs(x2－x1);

else

steps=abs(y2－y1);

increx=(float)(x2－x1)/steps;

increy=(float)(y2－y1)/steps;

x=x1;

y=y1;

for(i=1;i<=steps;i++)

{

putpixel(x，y，color);//在(x，y)處，以color色畫點(diǎn)

x+=increx;

y+=increy;

}

}2.1.2生成直線的Bresenham算法從上面介紹的DDA算法可以看到，由于在循環(huán)中涉及實(shí)型數(shù)據(jù)的加減運(yùn)算，因此直線的生成速度較慢。在生成直線的算法中，Bresenham算法是最有效的算法之一。Bresenham算法是一種基于誤差判別式來(lái)生成直線的方法。一、直線Bresenham算法描述：它也是采用遞推步進(jìn)的辦法，令每次最大變化方向的坐標(biāo)步進(jìn)一個(gè)象素，同時(shí)另一個(gè)方向的坐標(biāo)依據(jù)誤差判別式的符號(hào)來(lái)決定是否也要步進(jìn)一個(gè)象素。我們首先討論m=△y/△x，當(dāng)0≤m≤1且x1<x2時(shí)的Bresenham算法。從DDA直線算法可知這些條件成立時(shí)，公式(2-2)、(2-3)可寫成：xi+1=xi+1(2－6)yi+1=yi+m(2－7)有兩種Bresenham算法思想，它們各自從不同角度介紹了Bresenham算法思想，得出的誤差判別式都是一樣的。二、直線Bresenham算法思想之一：由于顯示直線的象素點(diǎn)只能取整數(shù)值坐標(biāo)，可以假設(shè)直線上第i個(gè)象素點(diǎn)坐標(biāo)為(xi，yi)，它是直線上點(diǎn)(xi，yi)的最佳近似，并且xi=xi(假設(shè)m<1），如下圖所示。那么，直線上下一個(gè)象素點(diǎn)的可能位置是(xi+1，yi)或(xi+1，yi+1)。由圖中可以知道，在x=xi+1處，直線上點(diǎn)的y值是y=m(xi+1)+b，該點(diǎn)離象素點(diǎn)(xi+1，yi)和象素點(diǎn)(xi+1，yi+1)的距離分別是d1和d2：d1=y-yi=m(xi+1)+b-yi(2－8)d2=(yi+1)-y=(yi+1)-m(xi+1)-b(2－9)這兩個(gè)距離差是d1-d2=2m(xi+1)-2yi＋2b-1(2－10)

我們來(lái)分析公式(2-10)：

(1)當(dāng)此值為正時(shí)，d1>d2，說(shuō)明直線上理論點(diǎn)離(xi+1，yi+1)象素較近，下一個(gè)象素點(diǎn)應(yīng)取(xi+1，yi+1)。

(2)當(dāng)此值為負(fù)時(shí)，d1<d2，說(shuō)明直線上理論點(diǎn)離(xi+1，yi)象素較近，則下一個(gè)象素點(diǎn)應(yīng)取(xi+1，yi)。

(3)當(dāng)此值為零時(shí)，說(shuō)明直線上理論點(diǎn)離上、下兩個(gè)象素點(diǎn)的距離相等，取哪個(gè)點(diǎn)都行，假設(shè)算法規(guī)定這種情況下取(xi+1，yi+1)作為下一個(gè)象素點(diǎn)。因此只要利用(d1-d2)的符號(hào)就可以決定下一個(gè)象素點(diǎn)的選擇。為此，我們進(jìn)一步定義一個(gè)新的判別式：pi=△x×(d1-d2)=2△y·xi-2△x·yi+c(2－11)

式(2-11)中的△x=(x2-x1)>0，因此pi與(d1-d2)有相同的符號(hào)；這里△y=y2-y1，m=△y/△x；c=2△y+△x(2b-1)。下面對(duì)式(2-11)作進(jìn)一步處理，以便得出誤差判別遞推公式并消除常數(shù)c。將式(2-11)中的下標(biāo)i改寫成i+1，得到：pi+1=2△y·xi+1-2△x·yi+1+c(2－12)將式(2-12)減去(2-11)，并利用xi+1=xi+1，可得：pi+1=pi+2△y-2△x·(yi+1-yi)(2－13)再假設(shè)直線的初始端點(diǎn)恰好是其象素點(diǎn)的坐標(biāo)，即滿足：y1=mx1+b(2－14)由式(2-11)和式(2-14)得到p1的初始值：p1=2△y-△x(2－15)這樣，我們可利用誤差判別變量，得到如下算法表示：初始p1=2△y-△x(2－16)當(dāng)pi≥0時(shí)：yi+1=yi+1,

xi+1=xi+1，

pi+1=pi+2(△y-△x)否則：yi+1=yi,

xi+1=xi+1，

pi+1=pi+2△y

從式(2-16)可以看出，第i+1步的判別變量pi+1僅與第i步的判別變量pi、直線的兩個(gè)端點(diǎn)坐標(biāo)分量差△x和△y有關(guān)，運(yùn)算中只含有整數(shù)相加和乘2運(yùn)算，而乘2可利用算術(shù)左移一位來(lái)完成，因此這個(gè)算法速度快并易于硬件實(shí)現(xiàn)。三、直線Bresenham算法思想之二：由于象素坐標(biāo)的整數(shù)性，數(shù)學(xué)點(diǎn)(xi，yi)與所取象素點(diǎn)(xi，yir)間會(huì)引起誤差(εi)，當(dāng)xi列上已用象素坐標(biāo)(xi，yir)表示直線上的點(diǎn)(xi，yi)，下一直線點(diǎn)B(xi+1，yi+1)，是取象素點(diǎn)C(xi+1，yir)，還是D(xi＋1，y(i+1)r)呢？設(shè)A為CD邊的中點(diǎn)，正確的選擇：若B點(diǎn)在A點(diǎn)上方，選擇D點(diǎn)；否則，選C點(diǎn)。用誤差式描述為：ε(xi+1)=BC-AC=(yi+1-yir)-0.5(2－8')求遞推公式：ε(xi+2)=(yi+2-y(i+1)r)-0.5=yi+1+m-y(i+1)r-0.5(2－9')當(dāng)ε(xi+1)≥0時(shí)，選D點(diǎn)，y(i+1)r=yir+1ε(xi+2)=yi+1+m-yir-1-0.5=ε(xi+1)+m-1(2－10')當(dāng)ε(xi+1)﹤0時(shí)，選C點(diǎn)，y(i+1)r=yirε(xi+2)=yi+1+m－yir-0.5=ε(xi+1)+m(2－11')初始時(shí)：ε(xs+1)=BC-AC=m-0.5(2－12')為了運(yùn)算中不含實(shí)型數(shù)，同時(shí)不影響不等式的判斷，將方程兩邊同乘一正整數(shù)。令方程兩邊同乘2·Δx，即d=2·Δx·ε，則：初始時(shí)：d=2·Δy-Δx(2－13')遞推式：當(dāng)d≥0時(shí)：{d=d+2·(Δy－Δx)；

y++；

x++；

}

否則：{d=d+2·Δy；

x++；

}(2－14')四、直線Bresenham算法實(shí)現(xiàn)：條件：0≤m≤1且x1<x21、輸入線段的兩個(gè)端點(diǎn)坐標(biāo)和畫線顏色：x1，y1，x2，y2，color；

2、設(shè)置象素坐標(biāo)初值：x=x1，y=y1；

3、設(shè)置初始誤差判別值：p=2·Δy-Δx；

4、分別計(jì)算：Δx=x2-x1、Δy=y2-y1；

5、循環(huán)實(shí)現(xiàn)直線的生成：

for(x=x1；x<=x2；x++)

{putpixel(x,y,color)；

if(p>=0)

{y=y+1；

p=p+2·(Δy-Δx)；

}

else

{p=p+2·Δy；

}}五、直線Bresenham算法完善：現(xiàn)在我們修正(2-16)公式，以適應(yīng)對(duì)任何方向及任何斜率線段的繪制。如下圖所示，線段的方向可分為八種，從原點(diǎn)出發(fā)射向八個(gè)區(qū)。由線段按圖中所示的區(qū)域位置可決定xi+1和yi+1的變換規(guī)律。容易證明：當(dāng)線段處于①、④、⑧、⑤區(qū)時(shí)，以|△x|和|△y|代替前面公式中的△x和△y，當(dāng)線段處于②、③、⑥、⑦區(qū)時(shí)，將公式中的|△x|和|△y|對(duì)換，則上述兩公式仍有效。在線段起點(diǎn)區(qū)分線段方向

六、直線Bresenham算法特點(diǎn)：由于程序中不含實(shí)型數(shù)運(yùn)算，因此速度快、效率高，是一種有效的畫線算法。七、直線Bresenham算法程序：voidBresenhamline(intx1,inty1,intx2,inty2,intcolor)

{

intx,y,dx,dy,s1,s2,p,temp,interchange,i;

x=x1;

y=y1;

dx=abs(x2-x1);

dy=abs(y2-y1);

if(x2>x1)

s1=1;

else

s1=-1;

if(y2>y1)

s2=1;

else

s2=-1;

if(dy>dx)

{

temp=dx;

dx=dy;

dy=temp;

interchange=1;

}

else

interchange=0;

p=2*dy-dx;

for(i=1;i<=dx;i++)

{

putpixel(x,y,color);

if(p>=0)

{

if(interchange==0)

y=y+s2;

else

x=x+s1;

p=p-2*dx;

}

if(interchange==0)

x=x+s1;

else

y=y+s2;

p=p+2*dy;

}

}2.2圓的生成這里僅討論圓心位于坐標(biāo)原點(diǎn)的圓的掃描轉(zhuǎn)換算法，對(duì)于圓心不在原點(diǎn)的圓，可先用平移變換，將它的圓心平移到原點(diǎn)，然后進(jìn)行掃描轉(zhuǎn)換，最后再平移到原來(lái)的位置。有幾種較容易的方法可以得到圓的掃描轉(zhuǎn)換，但是效率都不高。例如：直角坐標(biāo)法和極坐標(biāo)法：1、直角坐標(biāo)法圓的直角坐標(biāo)方程為x2+y2=R2

若取x作為自變量，解出y，得到(2－17)我們可以先掃描轉(zhuǎn)換四分之一的圓周。讓自變量x從0到R以單位步長(zhǎng)增加，在每一步時(shí)可解出y，然后調(diào)用畫點(diǎn)函數(shù)即可逐點(diǎn)畫出圓。但這樣做，由于有乘方和平方根運(yùn)算，并且都是浮點(diǎn)運(yùn)算，算法效率不高。而且當(dāng)x接近R值時(shí)(圓心在原點(diǎn))，在圓周上的點(diǎn)（R，0）附近，由于圓的斜率趨于無(wú)窮大，使得圓周上有較大的間隙。2、極坐標(biāo)法假設(shè)圓周上一點(diǎn)P（x，y）處的半徑與x軸的夾角為θ，則圓的極坐標(biāo)方程為

x=Rcosθ

y=Rsinθ(2－18)利用下面將要介紹的圓周上點(diǎn)的對(duì)稱性，那么自變量θ的取值范圍就是(0，45°)。這個(gè)方法涉及三角函數(shù)計(jì)算和乘法運(yùn)算，計(jì)算量較大。因此，也不是一種有效的方法。

2.2.1圓的八分對(duì)稱性圓心位于原點(diǎn)的圓有四條對(duì)稱軸x=0、y=0、x=y和x=－y，見下圖。從而若已知圓弧上一點(diǎn)P(x，y)，就可以得到其關(guān)于四條對(duì)稱軸的七個(gè)對(duì)稱點(diǎn)，這種性質(zhì)稱為八分對(duì)稱性。因此只要能畫出八分之一的圓弧，就可以利用對(duì)稱性的原理得到整個(gè)圓弧。下面的函數(shù)CirclePoints()用來(lái)顯示P(x，y)及其七個(gè)對(duì)稱點(diǎn)。voidCirclePoints(x,y,color)

intx,y,color;

{

putpixel(x,y,color);

putpixel(x,－y,color);

putpixel(－x,y,color);

putpixel(－x,－y,color);

putpixel(y,x,color);

putpixel(y,－x,color);

putpixel(－y,x,color);

putpixel(－y,－x,color);

}圓的八分對(duì)稱性注意：當(dāng)圓心不在原點(diǎn)時(shí)，只須在putpixel()函數(shù)中加上平移量x0、y0（圓心坐標(biāo)）即可。

例如當(dāng)x0=300，y0=200時(shí)，則：…

putpixel(x0+x，y0+y，color)；

putpixel(x0+x，y0-y，color)；

putpixel(x0-x，y0+y，color)；

putpixel(x0-x，y0-y，color)；

putpixel(x0+y，y0+x，color)；

putpixel(x0+y，y0-x，color)；

putpixel(x0-y，y0+x，color)；

putpixel(x0-y，y0-x，color)；

…2.2.2中點(diǎn)算法生成圓中點(diǎn)畫圓算法在一個(gè)方向上取單位間隔，在另一個(gè)方向的取值由兩種可能取值的中點(diǎn)離圓的遠(yuǎn)近而定。實(shí)際處理中，用決策變量的符號(hào)來(lái)確定象素點(diǎn)的選擇，因此算法效率較高。一、中點(diǎn)畫圓算法描述設(shè)要顯示圓的圓心在原點(diǎn)(0，0)，半徑為R，起點(diǎn)在(0，R)處，終點(diǎn)在(，)處，順時(shí)針生成八分之一圓，利用對(duì)稱性掃描轉(zhuǎn)換全部圓。為了應(yīng)用中點(diǎn)畫圓法，我們定義一個(gè)圓函數(shù)F(x，y)=x2+y2-R2(2－19)任何點(diǎn)(x，y)的相對(duì)位置可由圓函數(shù)的符號(hào)來(lái)檢測(cè)：F(x，y)<0點(diǎn)(x，y)位于數(shù)學(xué)圓內(nèi)

=0點(diǎn)(x，y)位于數(shù)學(xué)圓上

>0點(diǎn)(x，y)位于數(shù)學(xué)圓外(2－20)

如下圖所示，圖中有兩條圓弧A和B，假定當(dāng)前取點(diǎn)為Pi(xi，yi)，如果順時(shí)針生成圓，那么下一點(diǎn)只能取正右方的點(diǎn)E(xi+1，yi)或右下方的點(diǎn)SE(xi+1，yi-1)兩者之一。中點(diǎn)畫線算法假設(shè)M是E和SE的中點(diǎn)，即，則：1、當(dāng)F(M)<0時(shí)，M在圓內(nèi)(圓弧A)，這說(shuō)明點(diǎn)E距離圓更近，應(yīng)取點(diǎn)E作為下一象素點(diǎn)；

2、當(dāng)F(M)>0時(shí)，M在圓外(圓弧B)，表明SE點(diǎn)離圓更近，應(yīng)取SE點(diǎn)；

3、當(dāng)F(M)=0時(shí)，在E點(diǎn)與SE點(diǎn)之中隨便取一個(gè)即可，我們約定取SE點(diǎn)。二、中點(diǎn)畫圓算法思想因此，我們用中點(diǎn)M的圓函數(shù)作為決策變量di，同時(shí)用增量法來(lái)迭代計(jì)算下一個(gè)中點(diǎn)M的決策變量di+1。(2－21)下面分兩種情況來(lái)討論在迭代計(jì)算中決策變量di+1的推導(dǎo)。1、見圖（a），若di<0，則選擇E點(diǎn)，接著下一個(gè)中點(diǎn)就是，這時(shí)新的決策變量為：(2－22)（a）(di<0)中點(diǎn)畫線算法

式(2－22)減去(2－21)得：di+1=di+2xi+3(2－23)2、見圖（b），若di≥0，則選擇SE點(diǎn)，接著下一個(gè)中點(diǎn)就是，這時(shí)新的決策變量為：(2－24)（b）(di≥0)中點(diǎn)畫線算法式(2－24)減去(2－21)得：di+1=di+2(xi-yi)+5(2－25)我們利用遞推迭代計(jì)算這八分之一圓弧上的每個(gè)點(diǎn)，每次迭代需要兩步處理：

（1）用前一次迭代算出的決策變量的符號(hào)來(lái)決定本次選擇的點(diǎn)。

（2）對(duì)本次選擇的點(diǎn)，重新遞推計(jì)算得出新的決策變量的值。剩下的問(wèn)題是計(jì)算初始決策變量d0，如下圖所示。對(duì)于初始點(diǎn)(0，R)，順時(shí)針生成八分之一圓，下一個(gè)中點(diǎn)M的坐標(biāo)是，所以：(2－26)生成圓的初始條件和圓的生成方向三、中點(diǎn)畫圓算法實(shí)現(xiàn)1、輸入：圓半徑r、圓心(x0，y0)；

2、確定初值：x=0，y=r、d=5/4-r；

3、While(x<=y)

{

·利用八分對(duì)稱性，用規(guī)定的顏色color畫八個(gè)象素點(diǎn)(x，y)；

·若d≥0

{

y=y-1；

d=d+2(x-y)+5)；

}

否則

d=d+2x+3；

·x=x+1；

}四、中點(diǎn)畫圓算法完善在上述算法中，使用了浮點(diǎn)數(shù)來(lái)表示決策變量d。為了簡(jiǎn)化算法，擺脫浮點(diǎn)數(shù)，在算法中全部使用整數(shù)，我們使用e=d-1/4代替d。顯然，初值d=5/4-r對(duì)應(yīng)于e=1-r。決策變量d<0對(duì)應(yīng)于e<-1/4。算法中其它與d有關(guān)的式子可把d直接換成e。又由于e的初值為整數(shù)，且在運(yùn)算過(guò)程中的迭代值也是整數(shù)，故e始終是整數(shù)，所以e<-1/4等價(jià)于e<0。因此，可以寫出完全用整數(shù)實(shí)現(xiàn)的中點(diǎn)畫圓算法。

要求：寫出用整數(shù)實(shí)現(xiàn)的中點(diǎn)畫圓算法程序，并上機(jī)調(diào)試，觀看運(yùn)行結(jié)果。五、中點(diǎn)畫圓算法程序voidMidpointCircle(intx0,inty0,intr,intcolor)

{

intx,y;

floatd;

x=0;

y=r;

d=5.0/4-r;

while(x<=y)

{

putdot(x0,y0,x,y,color);

if(d<0)

d+=x*2.0+3;

else

{

d+=2.0*(x-y)+5;

y--;

}

x++;

}

}putdot(x0,y0,x,y,color)

{

putpixel(x0+x,y0+y,color);

putpixel(x0+x,y0-y,color);

putpixel(x0-x,y0+y,color);

putpixel(x0-x,y0-y,color);

putpixel(x0+y,y0+x,color);

putpixel(x0+y,y0-x,color);

putpixel(x0-y,y0+x,color);

putpixel(x0-y,y0-x,color);

}2.2.3正負(fù)算法生成圓正負(fù)法是利用平面曲線將平面劃分成正負(fù)區(qū)域，對(duì)當(dāng)前點(diǎn)產(chǎn)生的圓函數(shù)進(jìn)行符號(hào)判別，利用負(fù)反饋調(diào)整以決定下一個(gè)點(diǎn)的產(chǎn)生來(lái)直接生成圓弧。一、正負(fù)畫圓算法描述設(shè)要顯示圓的圓心在原點(diǎn)(0，0)，半徑為R，初始點(diǎn)的坐標(biāo)為(0，R)，順時(shí)針生成八分之一圓，令：F(x，y)=x2+y2-R2則圓的方程為：F(x，y)=0(2-27)當(dāng)點(diǎn)(x，y)在圓內(nèi)時(shí)，則F(x，y)<0；

當(dāng)點(diǎn)(x，y)在圓外時(shí)，則F(x，y)>0；

當(dāng)點(diǎn)(x，y)在圓上時(shí)，則F(x，y)=0；二、正負(fù)畫圓算法思想現(xiàn)以下圖的AB弧為例，來(lái)說(shuō)明正負(fù)畫圓法(順時(shí)針生成圓)。假設(shè)當(dāng)前點(diǎn)為Pi(xi，yi)，取下一個(gè)點(diǎn)Pi+1(xi+1，yi+1)的原則是：

1、當(dāng)F(xi，yi)≤0時(shí)：取xi+1=xi+1，yi+1=yi。即向右走一步，從圓內(nèi)走向圓外。對(duì)應(yīng)圖(a)中的從Pi到Pi+1。

2、當(dāng)F(xi，yi)>0時(shí)：取xi+1=xi，yi+1=yi-1。即向下走一步，從圓外走向圓內(nèi)。對(duì)應(yīng)圖(b)中的從Pi到Pi+1。由于向圓內(nèi)或向圓外走取決于F(xi，yi)的正負(fù)，因此稱為正負(fù)法。下面分兩種情況求出F(xi，yi)的遞推公式：

(1)當(dāng)F(xi，yi)≤0時(shí)，向右走，取xi+1=xi+1，yi+1=yi，則F(xi+1，yi+1)=F(xi+1，yi)

=(xi+1)2+yi2-R2

=(xi2+yi2-R2)+2xi+1

=F(xi，yi)+2xi+1(2-28)(2)當(dāng)F(xi，yi)>0時(shí)，向下走，取xi+1=xi，yi+1=yi-1，則F(xi+1，yi+1)=F(xi，yi-1)

=xi2+(yi-1)2-R2

=(xi2+yi2-R2)-2yi+1

=F(xi，yi)-2yi+1(2-29)初始時(shí)，x=0，y=R，故F(0，R)=(02+R2)-R2=0(2-30)公式(2-28)、(2-29)和(2-30)就構(gòu)成正負(fù)畫圓算法的核心。給象素坐標(biāo)(x，y)及F賦初始值后，進(jìn)入循環(huán)畫點(diǎn)；畫點(diǎn)后，根據(jù)F的符號(hào)進(jìn)行F值的遞推和下一個(gè)點(diǎn)的獲取，直到x>y為止。同前面介紹的一樣，利用圓的八分對(duì)稱性，循環(huán)一次，畫八個(gè)點(diǎn)。三、正負(fù)畫圓算法實(shí)現(xiàn)注意：初值不同、圓的生成方向不同時(shí)，當(dāng)前點(diǎn)和下一個(gè)點(diǎn)的獲取原則是不同的，見下圖。例如，初始點(diǎn)(R，0)，逆時(shí)針生成圓，從圖（b）可知：若當(dāng)前點(diǎn)Pi在圓內(nèi)，則下一點(diǎn)Pi+1(xi，yi+1)，即向上走一步；

若當(dāng)前點(diǎn)Pi在圓外，則下一點(diǎn)Pi+1(xi-1，yi)，即向左走一步；(a)順時(shí)針生成圓