計算機圖形學若干基礎算法的研究

引言：我們現代人生活在各種各樣的信息之中，如何應用計算機處理信息，處理圖形成為了一個越來越重要的課題。本論文主要介紹了計算機圖形學，以及兩種基礎算法：多邊形裁剪算法和逐點生成算法。

1. 計算機圖形學

1.1 計算機圖形學概述

我們現代人生活在各種各樣的信息之中，如何應用計算機處理信息，處理圖形成為了一個越來越重要的課題。本論文所要介紹的計算機圖形技術，是計算機領域的熱門領域之一，它是同電子硬件和計算機的周邊設備一同發展而來。隨著人類在航空航天、軍事和通信等領域的突破，計算機圖形學也得到了很快的發展。

計算機圖形學是一門實用計算機產生、顯示以及處理圖形界面的知識體系。計算機圖形學已經變得越來越重要，主要原因是：人們接收和發出信息，圖形是很好的一種傳遞信息的方式。一個圖形本身，就具有很豐富的信息，人們根據圖形能夠很自然快速地與外界進行交流。

1.2 計算機圖形學研究熱點

計算機圖形學主要研究以下三個方面的內容。第一：隱藏線（面）的消除；第二：基本曲線的裁剪以及繪制；第三：現代圖形學熱點研究的內容，主要是虛擬現實技術、可視化、三維立體的重建等等。

由于在一個圖形應用或圖形軟件中要大量重復調用這些基礎算法，因此在這方面的任何進步都會對整個圖形系統產生很大的影響。計算機圖形學的基礎算法經過人們幾十年的研究，己比較成熟。但每一個進步對解決圖形技術所面臨的存儲、傳輸、顯示等問題都有很大的幫助。

2. 基礎算法的研究

2.1 多邊形裁剪算法

裁剪是處理圖形一種很基礎的方法，常見的裁剪操作主要有將不同的圖形裁剪拼接形成新的圖形。我們可以看出，裁剪算法在計算機圖形學中是一種十分基礎但是卻又十分重要的操作[1]。

本論文所提到的裁剪方法，主要是針對凸多邊形的。裁剪方法主要可以分為四個方法：中點算法、CS算法、CB算法、梁B算法。

（1）CS算法是Cohen-Sutherland的一種分區編碼算法[2]。CS算法以前是計算機圖形學中很重要的一種算法。CS算法對線段可以分為以下三種情況：窗內、窗外以及其它情況。我們在使用CS算法的時候，需要判斷線段兩端端點的編碼，進而判斷窗口和線段之間的位置關系，這種算法的缺點是對于判斷所做的工作比其他算法多。端點編碼檢查算法的核心代碼如下：

end point code algorithm

P1 and P2 are the end points of the line

xL，xn，yT，yB are the left， right， top and bottom window coordinates calculate the end point codes

put the codes for each end into 1*4 arrays called P1code and P2code

first end point： P1

if x1 < xL then P1code（4） = 1 else P1code（4） = 0

if x1 > xR then P1code（3） = 1 else P1code（3） = 0

if y1 < yB then P1code（2） = 1 else P1code（2） = 0

if y1 < yT then P1code（1） = 1 else P1code（1） = 0

second end point： P2

if x2 < xL then P1code（4） = 1 else P1code（4） = 0

if x2 > xR then P1code（3） = 1 else P1code（3） = 0

if y2 < yB then P1code（2） = 1 else P1code（2） = 0

if y2 < yT then P1code（1） = 1 else P1code（1） = 0

finish

（2）中點算法是基于硬件實現的。重點算法同樣把窗口和線段的關系分成三種情況：窗內、窗外以及其它情況。對于窗內和窗外這兩種情況，中點算法和CS算法的處理方法相同；對于第三種情況，中點算法簡單地將線段分成兩段。中點算法是基于硬件的，所以算法比較簡單，相對于用軟件來實現，更偏重于用硬件來實現。

（3）CB算法能夠裁剪任意一種凸多邊形的窗口。CB算法會將交點簡化成上下兩組，主要判斷的方法是：直線段的方向矢量和窗口邊法矢量的點積是否大于零。CB算法會取上組部分最小的交點以及下組最大的交點，作為可見部分的端點。由于CB算法更適用于一般情況，所以CB算法的運算更加復雜。

（4）梁B算法在四種方法中，運算速度最快。但是在某些特殊情況下，梁B算法也需要進行大量的運算。

四種基礎算法的適用情況，如表2-1所示。

2.2 逐點生成算法

上一小節主要介紹了圖像的裁剪，本小節的逐點生成算法主要著重于研究圖形曲線的繪制。由于任何圖像都是根據圖形而來，而任何圖形都需要繪制，所以圖形曲線的繪制也是一項非常基礎性的研究課題。

科學家最開始采用幾何算法作為繪圖算法，這是因為以前的圖形顯示器都是掃描類型的顯示器。目前這種算法已經很少采用，但是在工程制圖的繪制過程中，受到各方面的限制，我們往往不得不采取這種方法。這種算法的基本思想就是：步長之間的兩個點，采取直線的方法連接。但是由于步長很小，我們實際看起來就是一條曲線。由于繪制條件以及算法本身的限制，這類算法有著自身的缺點：運算量非常大而且繪制不夠精細。

不同于曲線的幾何算法，像素級生成算法是一種全新的基于計算機的算法，這種算法主要分成兩種。第一種是對參數方程進行求導，進而計算出小于或等于一個像素迭代步長的距離的點。這類算法的優點是能夠適用于大多數曲線的繪制；這類算法的缺點是計算量很大，而且會造成多余的計算。第二種是根據曲線的隱式方程，找出曲線走向中下一個像素中最近的點。正是由于采用了這種原理進行曲線繪制，所以曲線的誤差在一個像素范圍內。這類算法的優點是速度快，因為每一次的步長都是一個像素點的距離；這類算法的缺點是適用范圍狹窄[3]。

3. 結論

我們現代人生活在各種各樣的信息之中，如何應用計算機處理信息，處理圖形成為了一個越來越重要的課題。本論文主要介紹了計算機圖形學，以及兩種基礎算法：多邊形裁剪算法和逐點生成算法。對于這些基礎算法的研究，對提高計算機圖形系統系能具有重要的意義。

參考文獻

[1]高云 計算機圖形學若干基礎算法的研究[J] 沈陽工業大學，2002.

[2]沈穎，宋文強 計算機圖形學的基本算法實現研究[J] 電腦知識與技術，2009，17（5）：4518-4519.

[3]陳麗，陳根才 改進的增量式關聯規則維護算法[J] 計算機工程與設計，2002，（1）：60-63.

（作者單位：福州大學）