Computer Graphics的基本算法實現分析

摘 要：Computer Graphics又稱計算機圖形學，本文對計算機圖形學中多邊形剪裁和逐點生成的基礎算法進行比較和研究，對于提高計算機圖形系統的性能具有很大的幫助，具有很強的理論和現實意義。

關鍵詞：計算機圖形學；基本算法；分析

中圖分類號：TP391.41 文獻標識碼：A 文章編號：1674-7712 （2014） 16-0000-01

計算機圖形學（Computer Graphics）是伴隨著電子計算機及其外圍設備而產生和發展起來的。目前幾乎所有的計算機的實際應用都不同程度地使用了圖形技術。所以計算機圖形技術同計算機網絡，人工智能及圖像處理等技術一樣是目前計算機領域的研究熱點之一。

一、計算機圖形學基木算法研究

（一）多邊形剪裁算法

線裁剪是計算機圖形學中的一個基本操作。對于凸多邊形窗口的裁剪，經過國內外學者的多年研究己經形成了許多經典有效的算法。但對于凹多邊形窗口的線裁剪，還有待進一步研究。對于凸多邊形窗口的線裁剪，國內外提出了多種多樣的線裁剪算法，其中五個具代表性意義的算法為：Cohen一Sutherland的分區編碼算法、基于硬件實現的中點分割算法、通過法向點積進行判別的Cvrus一Beck裁剪算法、梁友棟一Barskv線裁剪算法、以及Nieholl一LPe算法、為敘述方便，下面我們分別簡稱為C、中點、CB、梁B，NLN算法。

算法在計算機圖形學上曾經占據重要的地位，它對每條線段分三中情況處理。（1）窗內；（2）窗外；（3）不滿足條件（1）（2）的情況。它需要確定線段端點的編碼以辨別線段與窗口的位置關系，其判斷的運算量明泉多于其它算法。

中點算法把線段與窗口的關系一樣分為三種情況。對前兩種情況的處理與CS相同，對第三種情況則簡單的把線段等分為兩段。它適用于對乘、除沒有硬件支持的計算機，其算法便于硬化，用軟件實現則效率不高。CB算法適用于對任意凸多邊形窗口的裁剪。它通過判斷直線段的方向矢量與窗口邊法矢量的點積是否大于零而將所有交點分為上、下兩組。然后，分別取上組中的最小交點和下組中的最大交點，即為線段可見部分的端點。由于所采用的方法過于一般化，對一根不平行于坐標軸但完全落在窗口內部的線段的裁剪，CB算法需做12次加法、16次減法、20次乘法和除法。

梁B算法速度最快，但當線段在某窗口邊界線的不可見一側時，或完全落在窗口內部可見時，梁B算法仍要做算術運算。對四種算法比較，CS與中點法在區碼測試階段能以位運算方式高效率地進行，因而當大多數線段需要進行裁剪時，效率較好、，CB算法在多數線段需要進行裁剪時，效率更高。梁B算法只適用于矩形窗口，其效率比CB更高，因為在此算法中增加了另外的測試，使之在某此情況下不必對四條窗口邊都求交，就可以排除線段與窗口不交的情況。

NLN算法雖然在理論上運算量少于CS算法和梁B算法，但卻不實用。該算法包含多個子程序，系統開銷很大，并且無法用人工的方法消去這些子程序以減少系統開銷，即使用計算機軟件的方法達到了這一目的，也將導致一個長程序，這必然引起裁剪時間的增加。事實上，NLN中沒有對NLN算法與其它算法作執行時間上的比較，而執行時間的比較是衡量一個算法效率的必不可少的手段。

（二）逐點生成算法

隨著廣泛使用光柵掃描顯示器作為圖形顯示器，隨之出現了一類圖形算法，即象素級的圖形繪制算法（或稱點式生成算法）。這類算法生成的曲線是很細致的并且誤差小（坐標軸方向最大偏差不大于半個象素中一位）。可以說這類算法充分利用了光柵顯示器的特點。

曲線的像素級生成算法大體可以分為兩類。一類是根據曲線的隱式方程，通過判斷曲線的可能的走向，找出在各個走向中的下一個像素中距離曲線最近的像素。由于，曲線的每一步都是一個像素距離，所以誤差在坐標軸方向不會超過一個像素。此類算法的優點是每步走一個像素距離，速度快。其缺點是適用的范圍小，且下一個像素的位置判斷比較麻煩。另一類方法是根據曲線的平滑度，利用參數方程求導，求出使每一步前進距離都小于等于一個像素的迭代步長。這類算法的優點是適用范圍廣。缺點是由于步長的選取是針對整個曲線的，因此在曲線的某此階段，需要走許多步以后才能到達一個像素，造成許多多余的計算。它們共同的特點是讓每一步的像素選取都和前一個像素的距離小于等于一個像素。無論那種算法都必須使前后像素的坐標滿足一個迭代關系，盡量減少乘法和除法運算。

這類算法在20世紀60年代和70年代出現了著名的Bresenham直線算法，Pitteway橢圓和雙曲線算法和Bresenham圓生成算法。其實至此直線和圓的像素級生成算法己相當成熱，但仍有人在繼續從事這方面的研究。其著眼點主要集中在研制每一步生成多個點的算法上，20世紀80年代以后，人們的主要精力集中在其它曲線（高階或自由曲線等）的生成算法的研究上，如國內學者蔡耀志、金通光等提出的正負法、T-N法等，而在國外則有許多學者在進行這方面的研究，目前出現的自由曲線生成算法中大部分屬于生成或逼近算法，或者有此算法可以說是點式生成算法。但其兩點的間距較大，并非逐點選擇，所以生成的曲線不夠細致。在象素級算法中主要是關于二次和三次自由曲線的生成算法。如Patt提出的二次樣條曲線的象素級生成算法能夠較精確地選擇距離曲線最近的象素點，但該算法所生成的曲線的走向只能在一個象限內變化（90度范圍），不能生成曲率大的曲線。

二、結束語

本文對目前國內外計算機圖形學二維技術領域人們所關注的焦點問題的幾個主要方面的研究現狀及其發展趨勢進行了詳細的分析，對計算機圖形裁剪技術、逐點算法等進行了深入的比較和研究，這此基礎算法的研究，對于提高計算機圖形系統的性能具有很大的幫助，具有很強的理論和現實意義。

參考文獻：

[1]王增波.計算機圖形學中的方法論[J].科技信息：科學教研，2007（19）.

[2]田海山，何援軍，蔡鴻明.基于點的計算機圖形學綜述[J].系統仿真學報，2006（S1）.