季潔

摘要：《計算機圖形學(xué)》是計算機科學(xué)與技術(shù)專業(yè)一門重要的專業(yè)課，其中直線生成算法是教學(xué)重點之一。該文通過分析幾種直線生成算法的特點，闡述了理論教學(xué)和實踐教學(xué)的重點和難點，總結(jié)了教學(xué)的體會和心得，對《計算機圖形學(xué)》直線生成算法的本科教學(xué)有一定借鑒作用。

關(guān)鍵詞：計算機圖形學(xué)；直線生成算法；DDA算法；Bresenham算法

中圖分類號：G642 文獻標(biāo)識碼：A 文章編號：1009-3044（2015）23-0072-02

Teaching Experience of the Straight Line Generation Algorithm in Computer Graphics

JI Jie

（College of Computer and Electronic Engineering， Hunan University of Commerce， Changsha 410205， China）

Abstract："Computer graphics" is an important course in the major of computer science and technology， and the straight line generation algorithm is one of the key points in teaching of this course. In this paper， we analyse the characteristics of several line generating algorithm， describe the key and difficult points of theory teaching and practice teaching，summarize the teaching experience.It has some reference for the teaching of the straight line generating algorithm in computer graphics.

Key words： Computer graphics； straight line generating algorithm；DDAalgorithm； Bresenham algorithm

計算機圖形學(xué)是計算機科學(xué)中一門重要的分支研究方向，主要研究將二維或三維的圖形通過數(shù)學(xué)算法轉(zhuǎn)換為計算機輸出設(shè)備中的光柵形式?！队嬎銠C圖形學(xué)》這門課程是計算機科學(xué)與技術(shù)、軟件工程等相關(guān)專業(yè)在本科高年級教學(xué)中一門重要的專業(yè)課，在教學(xué)計劃中占有重要地位和作用。學(xué)習(xí)本課程旨在使學(xué)生掌握基本二維、三維圖形生成和變換技術(shù)算法、真實感圖形生成算法、計算機動畫技術(shù)的基本方法和原理，并通過編寫計算機程序加深對圖形學(xué)基本理論知識的理解，提高理論指導(dǎo)實踐的動手能力，為學(xué)生今后學(xué)習(xí)其他相關(guān)課程和進行相關(guān)方面的研究夯實基礎(chǔ)。

1 直線生成算法的教學(xué)重要性分析

計算機圖形學(xué)中的圖形可分為二維圖形和三維圖形，在坐標(biāo)系中，三維圖形可以通過一系列的投影變換得到二維的平面圖形，所以說，二維圖形的生成是三維圖形生成的基礎(chǔ)。

各種無論多么復(fù)雜的二維圖形，實際上都是通過直線段和曲線段組成的。在理論上，絕對光滑的曲線是繪制不出來的，曲線段經(jīng)過微分之后可以轉(zhuǎn)換成細(xì)微的短直線段。例如，一個較復(fù)雜的曲面，可能是由成千上萬條很短的直線組成的。所以，可以說所有圖形都是以直線段的生成為基礎(chǔ)的，而直線段生成質(zhì)量的好壞和速度的快慢也直接決定整個圖形生成的質(zhì)量和速度[1]，所以直線生成算法的學(xué)習(xí)顯得尤為重要。因此，在《計算機圖形學(xué)》的教學(xué)中，直線生成算法是教學(xué)重點之一，并且是學(xué)生們接觸到的第一類圖形生成算法。

2 幾種經(jīng)典直線生成算法分析和回顧

由于顯示設(shè)備的柵格性質(zhì)，圖形顯示器是由一個個排列有序的像素點構(gòu)成的，一條直線就是由一些像素點組成的。無論分辨率的大小，像素點之間還是存在一定距離的，而直線在圖形學(xué)中是不存在厚度的，所以一條直線不可能剛好經(jīng)過所有的像素點（平行于x軸、y軸以及斜率為45度的直線除外）。直線生成算法是計算出與該直線靠近的像素點，并繪制出來的過程。在教學(xué)中，主要給學(xué)生們介紹以下幾種直線生成算法：

1）中點生成算法：以第一象限為例，假設(shè)當(dāng)前像素點P已經(jīng)確定，那么下一個像素點只能是正右方的點P1或者是右上方的點P2，另M為P1和P2的中點，若直線與P1P2所在垂直線的交點在M的上方，則P2離直線比較近，應(yīng)選為下一個像素點；否則應(yīng)取P1位下一個像素點[2]。

2）逐點比較算法：逐點比較算法主要運用于繪圖儀中，其主要思路為：在繪圖的過程中，每繪制一個像素點，就與規(guī)定圖形進行比較，然后決定下一個像素點的位置。同樣以第一象限為例，如畫的直線為OA，當(dāng)前畫筆的位置為M，以O(shè)M和OA之前的斜率之差來計算偏差δ，若δ<0，則表示筆在直線OA的下方，應(yīng)該往+y方向走一步；若δ>0，則表示筆在直線OA的上方，應(yīng)該往+x方向走一步[1]。

3）數(shù)值微分（DDA）算法：這是一種基于直線的微分方程來生成直線的方法。設(shè)（x1，y1）和（x2，y2）分別為直線的端點坐標(biāo)，選定x2-x1和y2-y1中較大者作為步進方向，假設(shè)x2-x1比較大，則取x方向每次的增量為1個像素點，通過直線的微分方程，求出相應(yīng)的y值，并四舍五入取整之后作為下一個像素點輸出[1]。

4）Bresenham算法：這種方法最初是為數(shù)字繪圖儀設(shè)計的，但同樣也適用于光柵圖形顯示器。其基本思想是：過各行各列的像素中線虛擬的柵格化出一組網(wǎng)格線，直線與網(wǎng)格線的生成一系列交點，通過計算與該列中像素點的偏差距離e，并判斷偏差的符號來找到最近的像素點。以通過原點（0，0），且斜率k∈（0，1）的直線為例，則偏差e≥1/2的直線，下一個像素點應(yīng)該x加1，y+1；偏差e<1/2的直線，下一個像素點應(yīng)該x加1，y不變[2]。

3 教學(xué)的開展和體會

1）教學(xué)思路和過程

筆者對于計算機圖形學(xué)中直線生成算法的教學(xué)思路，總體分為四步走：首先，讓學(xué)生了解直線生成算法的統(tǒng)一特點，即在圖形輸出設(shè)備所給定的有限個像素矩陣中，確定最佳逼近于該直線的一組像素，從直線的起點開始，通過判斷尋找下一個最接近直線的像素點，一直到終點；第二步，讓學(xué)生具體了解算法的基本思路及具體實現(xiàn)的數(shù)學(xué)推導(dǎo)過程，判別函數(shù)、誤差項的生成過程；第三步，通過習(xí)題的演算和練習(xí)加深對算法的理解；最后，理論指導(dǎo)實踐的過程，上機操作將算法形成代碼，運行后得出結(jié)果。

2）教學(xué)重點和難點

在以上的教學(xué)過程中，第二步是教學(xué)的難點。因為這四種直線生成算法涉及大量的數(shù)學(xué)模型和算法實現(xiàn)，對于計算機專業(yè)的學(xué)生，數(shù)學(xué)基礎(chǔ)相對薄弱，學(xué)生在理解算法的基本思路上掌握得還不錯，但對于學(xué)習(xí)算法具體實現(xiàn)的數(shù)學(xué)推導(dǎo)過程就只能被動的聽課，很難主動地去進行推導(dǎo)，尤其是為了判別函數(shù)或者誤差項的計算簡單，常常需要進行各種推導(dǎo)變換及除法消除等操作。

由于課時有限，以上的四種算法不可能面面俱到，因此在教學(xué)安排中，中點生成法和逐點比較法做簡單闡述，DDA法和Bresenham法則作為重點講述。DDA法雖然效率不高，但比較直觀，方便通過實例讓學(xué)生了解每一步分解過程，通過改進之后使得算法中只包含加法和取整，適合硬件實現(xiàn)。Bresenham法是計算機圖形學(xué)領(lǐng)域使用最廣泛的直線生成算法，且算法很簡單，速度也相當(dāng)快。認(rèn)真掌握這兩種算法能幫助學(xué)生后續(xù)學(xué)習(xí)圓和曲線生成的算法奠定基礎(chǔ)。

3）實驗課程的內(nèi)容安排

計算機圖形學(xué)中涉及理論知識、數(shù)學(xué)模型和構(gòu)造算法，一般比較抽象和難懂。為了加深對書本理論知識的理解，加強本科學(xué)生動手能力的培養(yǎng)，從而突出實踐性和實用性，計算機圖形學(xué)重點的算法都安排了上機實驗。實驗平臺環(huán)境為Visual C++，因為Visual C++是集編輯、編譯、運行、調(diào)試于一體功能強大的集成編程環(huán)境。且MFC將圖形設(shè)備接口（GDI）的設(shè)備描述表（DC）封裝在C++類中，程序員可以通過調(diào)用專門的GDI函數(shù)來進行圖形程序設(shè)計。

直線生成算法的實驗任務(wù)安排了實現(xiàn)DDA畫線程序和Bresenham畫線程序。DDA算法程序邏輯簡單，學(xué)生理解較為輕松，原本DDA算法中含有浮點運算和取整運算，不利于硬件實現(xiàn)，但改進后的DDA算法只含有加法運算和取整運算，雖然效率不高，但硬件實現(xiàn)起來變得方便。通過分支語句結(jié)構(gòu)可以實現(xiàn)判斷x和y方向增量較大者作為步進方向，通過語句int（x+0.5）或者int（y+0.5）可以實現(xiàn)四舍五入取整的操作，通過循環(huán)語句可以實現(xiàn)從起點到終點像素點的繪制。Bresenham算法程序相對復(fù)雜，關(guān)鍵點在于區(qū)分直線位于不同的象限，判斷條件有所不同，具體用程序?qū)崿F(xiàn)的時候，會需要進行直線區(qū)域的變換。大部分的學(xué)生能夠在課程規(guī)定的時間內(nèi)完成DDA算法和Bresenham算法的程序?qū)崿F(xiàn)，基礎(chǔ)較好的同學(xué)還能完成中點生成算法及逐點比較法的程序?qū)崿F(xiàn)。

之后的教學(xué)中圓弧、橢圓、曲線的生成都牽涉到用短的直線段來逼近曲線，實踐證明，學(xué)生較好掌握了直線生成算法后，對后續(xù)的學(xué)習(xí)奠定了良好的基礎(chǔ)。

4 結(jié)束語

本文主要總結(jié)了在計算機科學(xué)與技術(shù)、軟件工程等相關(guān)專業(yè)《計算機圖形學(xué)》課程本科教學(xué)中直線生成算法的教學(xué)體會?；谥本€生成算法在本課程中的重要性，通過闡述和對比四種直線生成算法的異同，設(shè)計出了適合計算機科學(xué)與技術(shù)、軟件工程等相關(guān)專業(yè)《計算機圖形學(xué)》課程本科生教學(xué)的思路，并給出了相關(guān)實驗課程開展的良好建議。對于《計算機圖形學(xué)》課程本科教學(xué)有一定的借鑒作用。

參考文獻：

[1] 王汝傳，黃海平，林巧民，等.計算機圖形學(xué)教程[M]. 3版. 北京：人民郵電出版社，2014.

[2] 銀紅霞，杜四春，蔡立軍.計算機圖形學(xué)[M].北京：中國水利水電出版社，2013.