1、 名詞解釋*計算機圖形學是指用計算機產生對象圖形的輸出的技術。更確切的說，計算機圖形學是研究通過計算機將數據轉換為圖形，并在專門顯示設備上顯示的原理、方法和技術的學科。*圖形學的主要研究內容：圖形的生成和表示技術；圖形的操作和處理方法；圖形輸出設備與輸出技術的研究；圖形輸入設備、交互技術和用戶接口技術的研究；圖形信息的數據結構及存儲、檢索方法；幾何模型構造技術；動畫技術；圖形軟硬件的系列化、模塊化和標準化的研究；科學計算的可視化*能夠正確地表達出一個對象性質、結構和行為的描述信息，成為這個對象的模型。*圖像處理是指用計算機來改善圖像質量的數字技術。*模式識別是指用計算機對輸入圖形進行識別的技術

2、。*計算幾何學是研究幾何模型和數據處理的學科。*交互式計算機圖形學是指用計算機交互式地產生圖形的技術。*計算機圖形系統的硬件包括五部分：計算機、顯示處理器、圖形顯示器、輸入設備、硬拷貝設備。*CRT圖形顯示器工作方式有兩種：隨機掃描方式和光柵掃描方式。*隨機掃描方式的圖形顯示器通過畫出一系列線段來畫出圖形。*一幀：掃描過程所產生的圖像。*像素：在光柵掃描圖形顯示器中，屏幕上可以點亮或熄滅的最小單位。*分辨率：顯示屏上像素的總數。*幀存儲器：二維矩陣，幀存儲大小=分辨率*單元字節，存儲屏幕上每個像素對應的顏色或亮度值。*屏幕上每個像素對應的顏色或亮度值要存儲在幀存儲器中。*將圖形描述轉換成用像素

3、矩陣表示的過程稱為掃描轉換。*在光柵掃描顯示方式中像素坐標是行和列的位置值，只能取整數。*圖形基元（輸出圖形元素）：圖形系統能產生的最基本圖形。*區域是指光柵網絡上的一組像素。*區域填充是把某確定的像素值送入到區域內部的所有像素中。*區域填充方法：一類方法是把區域看做是由多邊形圍成的，區域事實上由多邊形的頂點序列來定義，相應的技術稱為是以多邊形為基礎的；另一類方法是通過像素的值來定義區域的內部，這時可以定義出任意復雜形狀的區域。相應的技術稱為是以像素為基礎的。*通過像素的值的定義區域有兩種常用的方法。一種是內定義區域，另一種是由邊界定義區域。*以像素為基礎的區域填充主要是依據區域的連通性進行。

4、*四連通區域是指從區域的一個像素出發，經過連續地向上、下、左、右四個相鄰像素的移動，就可以到達區域內的任意另一個像素的區域。（四聯通區域必是入連通的，反之未必）*八連通：如果除了要經上下左右的移動，還要經左上、右上、左下和右下的移動，才能由一個像素走到區域中另外任意一個像素。*利用區域的連通性進行區域填充，除了需要區域應該明確定義外，還需要事先給定一個區域內部像素，這個像素稱為種子。做區域填充時，要進行對光柵網格的遍歷。*像素段：將區域內由邊界點限定的同一行內相連接的不具有新值newvalue的一組像素稱為一個像素段，像素段用它最右邊的像素來標識。*奇偶性質：即一條直線與任意封閉的曲線相交時，

5、總是從第一個交點進入內部，再從第二個交點退出，以下交替的進入退出，即奇數次進入，偶數次退出。當然可能有一些“相切”的點應特殊處理。*活躍邊：與當前掃描線相交的邊。*活躍邊表AET：存貯當前掃描線相交的各邊的表。*邊表ET：記錄多邊形的所有邊。*“吊桶”中各項的內容一次是：1、邊的另一端點的較大的y坐標ymax；2、與較小的y坐標對應的邊的斷電的x坐標xmin；3、斜率的倒數，1/m。*柵欄：指一條與掃描線垂直的線，把多邊形一分為二。*規范化設備坐標系：圖形系統為具體設備無關的引入，是二維正方形或三維正方體，即各坐標范圍規定為從0到1。*常見的基本二維圖形幾何變換有：平移變換、比例變換和旋轉變換

6、。*本體坐標系（模型坐標系）：為規定基本形體而引入的便于描述的坐標系。*用戶坐標系（世界坐標系）：用戶引入描述整個形體的坐標系。*觀察坐標系（視覺坐標系/目坐標系）：為說明觀察姿態而引入，也就是觀察者所處的位置。*設備坐標系（顯示器坐標系/屏坐標系）：是各種圖形設備自身規定的在顯示表面上采用的坐標系。*齊次坐標表示法就是用n+1維向量表示一個n維向量。*窗口就是在用戶坐標系中指出的那個要顯示出來的區域，這一區域通常為矩形區域*通常把整個顯示屏幕區域稱作屏幕域，它是設備輸出圖形的最大區域，是有限的區域。*視見區是屏幕域中的一個子區域，通常為矩形區域，它最大與屏幕域等同。視見區用于顯示窗口中的圖形

7、。*窗口與視見區的差別在于：窗口是在用戶坐標系中確定的，它指出了要顯示的圖形，也就是我們想要看見什么；而視見區在設備坐標系中確定，它指出了實際顯示的圖形處于顯示屏幕的哪一部分，也就是我們要用顯示屏幕的哪部分實際去看。視見區在設備坐標系中定義，也可以用矩形區域的左下角點和右上角點的坐標來表示。*視見變換：就是將用戶坐標系窗口內的圖形變換到顯示屏幕設備坐標系的視見區中以產生顯示。*投影就是把n維空間中的點投射到小于n維的空間中去。*投影是如何形成的：首先在三維空間中確定一個投影中心和一個投影平面，然后從投影中心引出一些投射直線，這些直線通過形體上的沒一點，與投影平面相交，在投影平面上就形成了形體的

8、投影。*平行投影：當投影中心與投影平面的距離為無窮遠時，投射直線成為一組平行線，這種投影稱為平行投影。*透視投影：當投影中心與投影平面的距離是有限數值時，投射直線交于一點，形成滅點，這種投影稱為透視投影。*平行投影可以分為兩種類型：正交投影和斜交投影。*正交投影：投影方向與投影平面的法向相同。即投影方向垂直于投影平面。*常見的正交投影（三視圖）：正視投影、頂視投影、側視投影。*正投影：投影平面垂直于坐標軸的正交投影。（正視投影、頂視投影和側視投影）*等軸投影：投影方向與三個坐標軸的夾角都相等。這種投影能使在三個坐標軸方向上有相等的透視縮短。*斜交投影：投影方向與投影平面的法向不同。*常見的斜交

9、投影：斜二側投影和斜等軸投影。在斜交投影中，投影平面一般取坐標平面。*斜二側投影：垂直于投影平面的線段長度縮短為原來的一半。*斜等軸投影：使垂直于投影平面的線段仍保持長度。*透視投影性質：任意一組平行直線，如果平行于投影平面，則經透視投影后所得到的直線或者重合，或者仍保持平行；如果不平行于投影平面，將不再保持平行，并且必會匯聚于同一點。*消失點（滅點）：任意一組不平行于投影平面的平行直線，投影后所得的直線，必將匯聚于同一點。消失點可以取任意多個。*主消失點：三維直角坐標系中，透視投影時，如果一組平行直線平行于三個坐標軸中的一個，那么對應的消失點將落在坐標軸上。最多只有三個主消失點。*裁剪：去掉

10、窗口外的不可見部分，保留窗口內的可見部分的過程。*三維圖形顯示的處理流程:Z方向深度裁剪à世界坐標變換T1à投影T2à窗口至視窗的變換T3à至物理設備變換T4à裁剪à顯示*參數曲線的構造方法：曲線上每一點的坐標均要表示成某個參數t的一個函數式，則曲線上每一點笛卡爾坐標參數式是：x=x(t)，y=y(t)，z=z(t)；把三個方程合寫到一起，曲線上一點坐標的向量表示是：P(t)=x(t) y(t) z(t)；如用“'”表示對參數求導，則P(t)關于參數t的切向量或導函數是：P(t)=x(t) y(t) z(t)。類似地，曲面寫為

11、參數方程形式為：x=x(u,w)，y=y(u,w)，z=z(u,w)；寫成向量形式，則是：P(u,w)=x(u,w)，y(u,w)，z(u,w)*參數方程的優點：1）對非參數方程表示的曲線、曲面進行變換，必須對曲線、曲面上的每個型值點進行幾何變換；而對參數表示的曲線、曲面可對其參數方程直接進行幾何變換（如平移、比例、旋轉），從而節省計算工作量。2）便于處理斜率為無限大的問題。3）有更大的自由度來控制曲線、曲面的形狀。同時對于復雜的曲線和曲面具有很強的描述能力和豐富的表達能力。4）參數方程中，代數、幾何相關和無關的變量是完全分離的，而且對變量個數不限，從而便于用戶把低維空間中的曲線、曲面擴展到高

12、維空間去。這種變量分離的特點使我們可以用數學公式去處理幾何分量，同時可以使曲線和曲面具有統一的表示形式。5）規格化的參數變量t0，1，使其相應的幾何分量是有界的，而不必用另外的參數去定義其邊界。它便于曲線和曲面的分段、分片描述，易于實現光順連接。6）易于用向量和矩陣表示幾何分量，計算處理簡便易行。*計算機上表現的曲線和曲面，大體上可分為兩類：一類要求通過事先給定的離散的點，稱為插值的曲線或曲面。另一類不要求通過事先給定的各離散點，而只是用給定各離散點形成的控制多邊形來控制形狀，成為逼近的曲線或曲面。事先給定的離散點常稱為型值點，由型值點求插值的或逼近的曲線或曲面的問題，稱為曲線或曲面的擬合問題

13、。*插值：要求構造一條曲線順序通過型值點，稱為對這些型值點進行插值。*逼近：當型值點太多時，構造插值函數使其通過所有的型值點相當困難的。此時人們往往構造一條曲線，使它在某種意義上最佳逼近這些型值點，稱之為對這些型值點進行逼近。*曲線的數學表示形式：顯示、隱式、參數*在計算機上表現的曲線和曲面，大體分為兩類：一類要求通過事先給定的離散的點，稱為插值的曲線或曲面，另一類不要求通過事先給定的各離散點，而只是用給定各離散點形成的控制多邊形來控制形狀，稱為逼近的曲線或曲面。*光順是指曲線的拐點不能太多，要光滑順暢。*Bezier曲線性質：1.P(0)=P0,P(1)=P1,曲線通過所給出型值點列的起點和

14、終點2.P(0)=n(P1-P0),P(1)=n(Pn-Pn-1)曲線在始點和終點處的切線方向與它的控制多邊形的第一邊和最后一邊的走向一致。3.曲線有對稱性，4.曲線的凸包性。整條曲線都包含在所有控制點所張成的凸包中。*簡述B樣條曲線與Bezier之間的關系N+1個控制點P0,P1,Pn所確定的最高階的B樣條曲線是k=n+1階的，這時由節點向量(0,0,0,1,1,1)所去頂的B樣條曲線，與該n+1個控制點所確定的Bezier曲線相同。這個結論說明了B樣條曲線確實是Bezier曲線的一種推廣，Bezier曲線是B樣條曲線的特例。*凸殼：包含一個平面點集的最小凸區域。*凸區域：指要求區域內任意兩

15、點的連線仍在該區域內。*求點集S的凸殼（設S是平面上n個點的集合，則S的凸殼是一個凸多邊形，它包含所有n點且面積最小）：1）在S中選出殼上的點；2）給出圍成凸多邊形的序列。*Graham掃面的實質是圍繞已經按“傾角”排序的各頂點進行一次掃描，在掃描過程中消去在凸殼內部的點，留下以希望次序排列的殼頂點。由于是按傾角遞增排序，故可知若三個頂點P1.P2.P3連續“右轉”，則P2是一個應去掉的內點。*簡單多邊形：是平面上不相鄰的邊不能相交的多邊形。*簡單多邊形做三角剖分：要求選出完全在內部又互不相交的一組對角線，把整個多邊形劃分成一些三角形。（對角線是不相鄰頂點間的連線）*簡單多邊形的三角剖分：是選

16、出的對角線的集合。*最小權三角剖分（最小三角剖分）：一個三角剖分中選取的對角線的總長度最小。*與空間任意形體有關的信息可以分為：圖形信息和非圖形信息兩類。*圖形信息指構成它們的點、線、面的位置，互相關系及大小等。*非圖形信息指形體的顏色、亮度、質量、體積等一些性質。*圖形信息包括：1、幾何信息：形體在空間的位置和大小。2、拓撲信息：組成形體各部分的數目及相互間的連接關系。*形體的表示方法通常可分為兩類：1、邊界表示：用邊界將形體分為內部和外部。2、空間分區表示：描述形體的內部性質，將包含形體的空間區域劃分為一組小的非重疊的連續實體。*曲線的表示法：1、折線法：就是用多段線段形成的折線去逼近曲線

17、。2、帶樹法：帶樹就是一棵二叉樹，樹的每個結點對應一個矩形帶段，這樣每個結點可由八個字段組成，前六個字段描述矩形帶段，后二個是指向兩個子結點的指針，即矩形帶段的起點是（xb，yb），終點是（xe，ye）。相對從起點到終點的連線，矩形有兩邊與之平行，兩邊與之垂直，平行兩邊與之距離分別為wl和wr。*三種四叉樹的存儲結構，即規則方式、線性方式、一對四方式*四叉樹優點（與像素陣列表示）：1）節省存儲空間；2）可以用不同精度來表示；3）與設備無關，便于移植。*形體的模型：主要指的就是包含圖形信息所形成的模型。*幾何元素：形體本身的構造有一定的層次性，底層部分組合構成上一層部分，而上一層部分組合又可以構

18、成更高一層的部分，依次類推可形成多層結構。其中，每一層中的部分，我們把它又稱為幾何元素。*消除隱藏面（面消隱）：確定可見面等價于消除場景中物體的不可見面。*消除隱藏線（線消隱）：顯示采用線框模型表示的物體時，要消除不可見的線。*面消隱算法分兩大類：1、圖像空間算法：對顯示設備上每一個可分辨像素進行判斷，看組成物體的多個多邊形表面中哪一個在該像素上可見，既要對每一像素檢查所有的表面。2、客體空間算法：把注意力集中在分析要顯示形體各部分之間的關系上，這種算法對每一個組成形體的表面，都要與其它各表面進行比較，以便消去不可見的面或面的不可見部分。*可見面：朝向觀察位置的面。*范圍檢查：即為最大最小檢驗

19、，通過比較有關的最大或最小值來實現。*點：是0維幾何元素，有端點、交點、切點、孤立點等形式。*邊：是一維幾何元素，是兩個鄰面（正則形體）或多個鄰面（非正則形體）的交界。*環：有序有向邊（直線段或曲線段）組成的面的封閉邊界。*面：是二維幾何元素，是形體上一個有限、非零的區域，它由一個外環和若干個內環所界定。*體是三維幾何元素，由封閉表面圍成的空間，它是歐氏空間R3中非空、有界的封閉子集，其邊界是有限面的并集。*體素：是可以用有限個尺寸參數定位和定型的體。*形體的層次結構：點 -> 邊 -> 環 -> 面 -> 外殼 -> 形體*常用的多面體三表表示法是：頂點表，邊表

20、，面表*通常用正則集合運算來實現這種組合。*確定可見面等價于消除場景種物體的不可見面，即消除隱藏面（面消隱）*消隱面算法大體分為兩個大類，即圖像空間算法和客體空間算法。*圖像空間算法把注意力集中在最終形成的圖形上。客體空間算法把注意力集中在分析要顯示形體各部分之間的關系上。*范圍檢查又稱為最大最小檢驗。設平面上四點設平面上四點(1，1)，(2，3)，(4，3)，(3，1)確定的Bezier曲線是P(t)，如果在點P(1/2)處將它分為兩段，求前后兩段做為Bezier曲線各自的四個控制點坐標。解答：使用分裂法，有：P0(1,1)R0P1(2,3)R1P2(4,3)R2P3(3,1)R3R0=(3

21、/2,2)R1=(3,3)R2=(7/2,2)R0=(9/4,5/2)R1=(13/4,5/2)R0=(11/4,5/2)i=0i=1i=2Q0Q1Q2Q3前半段四個控制點Q0(1,1)，Q1(3/2,2)，Q2(9/4,5/2)，Q3(11/4,5/2)，0t1/2；后半段四個控制點R0(11/4,5/2)，R1(13/4,5/2)，R2(7/2,2)，R3(3,1)，1/2t1。*用計算機在圖形設備上生成真實感圖形必須完成四個基本的任務。第一用數學方法建立所構造三 維場景的幾何描述，并將它們輸入至計算機。第二,將三維幾何描述轉換為二維透視圖。第三,確定場景中的所有可見面，這需要使用隱藏面消

22、除算法將被其它物體遮擋的不可見面消去。第四 計算場景中可見面的顏色，嚴格地說，就是根據基于光學物理的光照明模型計算可見面投射到觀察者眼中的光亮度大小和顏色組成，并將它轉換成適合圖形設備的顏色值，從而確定投影畫面上每一象素的顏色，最終生成圖形。*設計一個光照模型需要考慮的主要問題是照明特性、表面特性和觀察角度光照模型可以分解為三個部分，即漫射照明，具體光源的照射和透射效應具體光源在物體表面可以引起漫反射和鏡面反射。亮度公式：I=IaKa+IpKd(L*N)Phong Bui Tuong 提出的光照明模型，用cosna來近似表示反射光線引起的亮度隨著a增大而下降的速率。N的取值一般在02000之間

23、，決定于反射表面的有關性質。對于理想的反射表面，n就是無窮大。這里選用cosna，是以觀察經驗為基礎的。對實際物質來說，被鏡面反射的入射光的數量與入射角B有關，如果將鏡面反射光的百分數記為W(B)，那么久可以將計算表面亮度的公式I=IaKa+IpKd(L*N)/(r+k)修改得到I=IaKa+Ip/(r+k)*Kd(L*N)+Ks(R*V)n方*$8深度暗示技術首先，再投影坐標系中定義兩個平面Z=Zf,Z=Zb,分別為前參考面和后參考面，并賦予比例因子Sf和Sb(Sf,Sb(-0,1)。給定物體上一點的深度值Z0,該點對應的比例因子S0這樣來確定1)當Z0>Zf時，取S0=Sf 2)當Z

24、0<Zb時，取S0=Sb 3)當Z0(- Zb,Zf時，S0=Sb+(Sf-Sb)/(Zf-Zb)*(Z0-Zb)原亮度I按比例S0與亮度Idc混合，目的是活的最終用于顯示的亮度I,Idc由用戶指定：I=S0I+(1-S0)Idc 若取Sf=1,Sb=0,Idc=0,則當物體位于前參考面之前時，I=I.即亮度沒有被衰減；當物體位于后參考面之后，I=Idc=0，即亮度被衰減為0，else I=S0I,亮度被部分衰減。*Phong方法繪制多邊形步驟1) 計算多邊形的單位法向量2) 計算多邊形頂點的單位法向量。3) 再掃描線消隱算法中，對多邊形頂點的法向量進行雙線性插值，計算出多邊形內部各點法

25、向量1. 當掃描線y遞增一個單位，變為y+1時，Na,Nb的增量分別為Na,Nb2. 當x遞增一個單位時Np增量為Np4) 利用光照模型計算P點的顏色 解答題*計算機圖形學是指用計算機產生對象圖形的輸出的技術。更確切的說，計算機圖形學是研究通過計算機將數據轉換為圖形，并在專門顯示設備上顯示的原理、方法和技術的學科。*圖形學的主要研究內容：圖形的生成和表示技術；圖形的操作和處理方法；圖形輸出設備與輸出技術的研究；圖形輸入設備、交互技術和用戶接口技術的研究；圖形信息的數據結構及存儲、檢索方法；幾何模型構造技術；動畫技術；圖形軟硬件的系列化、模塊化和標準化的研究；科學計算的可視化*與計算機圖形學相關

26、的學科及它們之間的關系： 對象的描述 à計算機圖形學 模式識別ß對象的圖形圖像處理圖像處理是指用計算機來改善圖像質量的數字技術。模式識別是指計算機對輸入圖形進行識別的技術。*計算機圖形系統的硬件包括五部分：計算機、顯示處理器、圖形顯示器、輸入設備、硬拷貝設備。*CRT圖形顯示器工作方式有兩種：隨機掃描方式和光柵掃描方式。*窗口與視見區的差別在于：窗口是在用戶坐標系中確定的，它指出了要顯示的圖形，也就是我們想要看見什么；而視見區在設備坐標系中確定，它指出了實際顯示的圖形處于顯示屏幕的哪一部分，也就是我們要用顯示屏幕的哪部分實際去看。視見區在設備坐標系中定義，也可以用矩形區域的

27、左下角點和右上角點的坐標來表示。*投影的形成過程：首先在三維空間中確定一個投影中心和一個投影平面，然后從投影中心引出一些投射直線，這些直線通過形體上的沒一點，與投影平面相交，在投影平面上就形成了形體的投影。*三維圖形顯示的處理流程:Z方向深度裁剪à世界坐標變換T1à投影T2à窗口至視窗的變換T3à至物理設備變換T4à裁剪à顯示*參數曲線的構造方法：曲線上每一點的坐標均要表示成某個參數t的一個函數式，則曲線上每一點笛卡爾坐標參數式是：x=x(t)，y=y(t)，z=z(t)；把三個方程合寫到一起，曲線上一點坐標的向量表示是：P(t)=x

28、(t) y(t) z(t)；如用“'”表示對參數求導，則P(t)關于參數t的切向量或導函數是：P(t)=x(t) y(t) z(t)。類似地，曲面寫為參數方程形式為：x=x(u,w)，y=y(u,w)，z=z(u,w)；寫成向量形式，則是：P(u,w)=x(u,w)，y(u,w)，z(u,w)*參數方程的優點：1）對非參數方程表示的曲線、曲面進行變換，必須對曲線、曲面上的每個型值點進行幾何變換；而對參數表示的曲線、曲面可對其參數方程直接進行幾何變換（如平移、比例、旋轉），從而節省計算工作量。2）便于處理斜率為無限大的問題。3）有更大的自由度來控制曲線、曲面的形狀。同時對于復雜的曲線和曲

29、面具有很強的描述能力和豐富的表達能力。4）參數方程中，代數、幾何相關和無關的變量是完全分離的，而且對變量個數不限，從而便于用戶把低維空間中的曲線、曲面擴展到高維空間去。這種變量分離的特點使我們可以用數學公式去處理幾何分量，同時可以使曲線和曲面具有統一的表示形式。5）規格化的參數變量t0，1，使其相應的幾何分量是有界的，而不必用另外的參數去定義其邊界。它便于曲線和曲面的分段、分片描述，易于實現光順連接。6）易于用向量和矩陣表示幾何分量，計算處理簡便易行。*計算機上表現的曲線和曲面，大體上可分為兩類：一類要求通過事先給定的離散的點，稱為插值的曲線或曲面。另一類不要求通過事先給定的各離散點，而只是用

30、給定各離散點形成的控制多邊形來控制形狀，成為逼近的曲線或曲面。事先給定的離散點常稱為型值點，由型值點求插值的或逼近的曲線或曲面的問題，稱為曲線或曲面的擬合問題。*Bezier曲線性質：1.P(0)=P0,P(1)=P1,曲線通過所給出型值點列的起點和終點2.P(0)=n(P1-P0),P(1)=n(Pn-Pn-1)曲線在始點和終點處的切線方向與它的控制多邊形的第一邊和最后一邊的走向一致。3.曲線有對稱性，4.曲線的凸包性。整條曲線都包含在所有控制點所張成的凸包中。*簡述B樣條曲線與Bezier之間的關系N+1個控制點P0,P1,Pn所確定的最高階的B樣條曲線是k=n+1階的，這時由節點向量(0

31、,0,0,1,1,1)所去頂的B樣條曲線，與該n+1個控制點所確定的Bezier曲線相同。這個結論說明了B樣條曲線確實是Bezier曲線的一種推廣，Bezier曲線是B樣條曲線的特例。*Graham掃面的實質是圍繞已經按“傾角”排序的各頂點進行一次掃描，在掃描過程中消去在凸殼內部的點，留下以希望次序排列的殼頂點。由于是按傾角遞增排序，故可知若三個頂點P1.P2.P3連續“右轉”，則P2是一個應去掉的內點。*形體的表示方法通常可分為兩類： 1、邊界表示：用邊界將形體分為內部和外部。 2、空間分區表示：描述形體的內部性質，將包含形體的空間區域劃分為一組小的非重疊的連續實體。*曲線的表示法：1、折線

32、法：就是用多段線段形成的折線去逼近曲線。2、帶樹法：帶樹就是一棵二叉樹，樹的每個結點對應一個矩形帶段，這樣每個結點可由八個字段組成，前六個字段描述矩形帶段，后二個是指向兩個子結點的指針，即矩形帶段的起點是（xb，yb），終點是（xe，ye）。相對從起點到終點的連線，矩形有兩邊與之平行，兩邊與之垂直，平行兩邊與之距離分別為wl和wr。*面消隱算法分兩大類：1、圖像空間算法：對顯示設備上每一個可分辨像素進行判斷，看組成物體的多個多邊形表面中哪一個在該像素上可見，既要對每一像素檢查所有的表面。2、客體空間算法：把注意力集中在分析要顯示形體各部分之間的關系上，這種算法對每一個組成形體的表面，都要與其它

33、各表面進行比較，以便消去不可見的面或面的不可見部分。*用計算機在圖形設備上生成真實感圖形必須完成四個基本的任務。第一用數學方法建立所構造三 維場景的幾何描述，并將它們輸入至計算機。第二,將三維幾何描述轉換為二維透視圖。第三,確定場景中的所有可見面，這需要使用隱藏面消除算法將被其它物體遮擋的不可見面消去。第四 計算場景中可見面的顏色，嚴格地說，就是根據基于光學物理的光照明模型計算可見面投射到觀察者眼中的光亮度大小和顏色組成，并將它轉換成適合圖形設備的顏色值，從而確定投影畫面上每一象素的顏色，最終生成圖形。 算法分析&5.簡單多邊形包含性檢驗的算法：1.【準備】XnßX0,yn&

34、#223;y0,mß -1,iß02.【排除必不相交情形】若下列條件有一個成立，則到41)xp<x,&&xp<xi+12)xp>=xi&&xp>=xi+13)xp<y&&yp<yi+13.【計算交點】y=yi+(xp-xi)(yi+1 - yi)/(xi+1 - xi)分兩種情形：1)若y=yp,則P在多邊形邊界上，算法結束2)若y<yp，則 mß(-1)m;4.【結束判斷】ißi+1，若i<n,則返回到2，否則算法結束，此時若m = -1 則點P在多邊形外部

35、，m=1,則在內部。*簡述掃描線種子填充算法的工作步驟。1， 對種子所在的像素段進行填充2， 從右到左檢查種子所在行的上一橫行，將查到的像素段依次編號存入堆棧。實際存入堆棧內的可以是每個像素段最右邊像素的地址。接著對種子所在行的下一橫行同樣處理。3， 若堆棧為空則算法結束，否則從堆棧頂部取出一個像素段。因為按先進后出的順序，所以將取出編號最大的像素段。實際取出的是這個像素段最右邊像素的地址。就以這個像素為新的種子，返回到1.寫出Graham凸殼求解算法1.(傾角排序)選出輸入電集S中X坐標最小的點，若這樣的點不唯一則再由其中選出y坐標最小的點，設為O.設想有一條從O向右的射線OX,對點集中其余

36、每一點P,計算傾角POX,再按傾角排序，得到點序列Q1=O,Q2,Q3,Qn;2.(準備掃描)vßQ1;3.(掃描)若NEXT(v) != Q1,則循環執行下面的操作至NEXT(v)=Q1時止，此時點序列中剩下排成凸多邊形的殼上頂點，算法結束。若三個相繼的點v, Next(v), Next(NEXT(v)形成一個左轉，則vßNEXT(v);否則先刪除NEXT(v),再做vßPRED(v);*寫出Jarvis凸殼求解算法1(準備)v0ß點集S中按x,y字典次序最小的點；dß豎直向下的一個方向向量；點v0送入收集凸殼頂點的隊列Q中；S1ß

37、S u,v0；ußv02(一步行進)v1ßWrapping(u,d,S1);S1中各點相對于自u出發方向為d的射線，計算傾角，取傾角最小的點，若傾角相同，取與u距離最遠的點，Wrapping(u,d,S1);返回下一個殼頂點。3(準備下次) if v1 != v0,v1送入Q中；S1 = S u,v1; dß從u到v1的一個方向向量； ußv1;返回步驟24(結束)Q中存入所有的殼頂點，算法結束*試寫出判定一空間多邊形與一凸多面體之間關系的算法1. 求出空間多邊形和凸多面體的包圍盒分別做x,y,z三向測試，若包圍盒檢查(最大最小檢驗)有一個為真，則空間多

38、邊形和凸多面體分離。算法輸出分離并結束。2. 一次用凸多面體的每一表面多邊形來求解與空間多邊形各邊的交點若有交點，測試空間多邊形的頂點是否均在凸多面體內，若均在體內，則為包含；若有交點，測試空間多邊形的頂點有內有外，則相交；若無交點，測試空間多邊形的頂點是否在凸多面體內，若均在體內，則為包含；若無交點，測試空間多邊形的頂點均在凸多面體外，則為分離。7.1線面比較法消除隱藏線1）、消除隱藏線的線面比較法的最先一步就是利用外法線判斷出所有可能的可見面。2）、做xv方向和yv方向的范圍檢查。3）、接著做zv方向的范圍檢查，即粗略的深度比較。4）、進行精確的深度比較。比較時，應計算線段兩端點在可能遮擋

39、它的平面上的投影點，比較相應的z坐標。如果z1z1并且z2z2，則線段不會被遮擋；如果z1z1并且z2z2，則線段有可能被遮擋，還需要做進一步檢查。如果不是上述兩種情況，必發生線段與表面相交。這時，需要用交點，這些交點把線段的投影分成兩部分。判斷得知線段確實被平面遮擋了哪些部分。5）、做精確計算。計算是求出線段的投影與遮擋平面上多邊形表面邊框投影的所有交點，這些交點把線段的投影分成可見和不可見的一些子線段。對子線段的可見性，先取其上一點做點的包含性檢驗來進行判斷。7.3*深度排序(優先級)算法1.把所有的多邊形按頂點最大z坐標值進行排序。2.解決當多邊形在z坐標范圍內發生交迭時出現的不明確問題

40、1)多邊形的x坐標范圍不相交迭，所以多邊形不相交迭2)多邊形的y坐標范圍不相交迭，所以多邊形不相交迭3）P完全在Q遠離觀察點的一側4）Q完全在P靠近觀察點的一側5）多邊形在z=0平面上的投影本身不相交迭。實現這個檢查可以檢查一個多邊形的每條邊與另一個多邊形的每條邊是否相交。若這步檢查為真，則兩個多邊形也是互補遮擋的。如果上述5步檢查都為假，就假定P遮擋了Q,交換P和Q在排序表中的位置。事實上，P不一定遮擋Q,所以交換后應該重新上述5步的檢查。3.按最大z坐標值逐次減小的次序，對每個多邊形進行掃描轉換。|7.5*深度緩存算法(Z-Buffer)的基本工作流程。幀緩沖區置成背景色；Z-緩沖區置成最

41、大z值；For(各個多邊形)掃描轉換該多邊形for(計算多邊形所覆蓋的每個像素(x,y) 計算多邊形在該象素的深度值Z(x,y);If(Z(x,y)小于Z緩沖區中的(x,y)處的值)把Z(x,y)存入Z緩沖區中(x,y)處;把多邊形在(x,y)處的亮度值存入更新緩存區(x,y)處*對Z緩沖算法進行改進，只用一個緩沖存儲器實現消隱。Z-Buffer() 幀緩存全置為背景色For(屏幕上的每個像素(I,j)深度緩存變量zb置最大值MaxValueFor(多面體上的每個多邊形pk)if(像素點(I,j)在pk的投影多邊形之內)計算pk在(I,j)處的深度值depth;If(depth小于zb)zb

42、= depth; indexp = k; If(zb != MaxValue)計算多邊形Pindexp在交點(I,j)處的光照顏色并顯示。7.7*區域分割算法（圖像空間算法）區域分割算法要將投影平面分割成區域，考察區域內的圖像。如果容易決定在這個區域內某些多邊形是可見的，那么就可以顯示那些可見的多邊形，完成對這一區域的顯示任務；否則，就將區域再分割成小的區域，對小的區域遞歸地進行判斷。由于區域逐漸變小，每個區域內的多邊形逐漸變小，最終總可以判定哪些多邊形是可見的。在下面四種情況下，可以很容易做出判定，而不必再做進一步分割：1. 所有的多邊形與區域分離，所以在區域內只顯示背景值。2. 只有一個相

43、交的多邊形，或者只有一個被包含的多邊形。這時可以對區域首先填充背景值，然后對多邊形進行掃描轉換。在某些顯示設備上，將整個幀存儲器都初始化為背景值，可能更為方便。對于相交的多邊形，只是被包含的部分被掃描轉換3. 只有一個包圍的多邊形，沒有其他的多邊形。這時整個區域可填充這個包圍多邊形的像素值。4. 有多于一個包圍的、相交的或被包圍的多邊形，且至少有一個包圍的多邊形。這時可以檢查是否能有一個包圍的多邊形位于所有其他多邊形的前面*八叉樹算法：1. 遍歷形體原來的八叉樹T1，對遇到的每個黑節點，做下述步2.2. 對遇到黑節點對應的正立方體做相應變換，得到一般來說斜置的新位置。若這位置已超出定義八叉樹的

44、充分大正立方體C之外，報告出錯；否則執行下述的步3.3. 從要計算求出的目標樹T2的根開始，檢查2.中確定的處于新位置立方體與T2中節點對應的直立的正立方體是否相交，分以下三種情況進行處理：(1) 不相交，說明正考查直立正方體未被占據，可保持為白節點，不做處理。(2) 直立的正立方體整個被占據，即它在變換后“斜置”立方體內，置對應節點為黑節點。(3) 在上述兩條都不成立時，生成當前節點的八個子節點，對八個子節點對應的八個直立子立方體，依次再遞歸執行步3. 如果最終這八個節點被標上同樣特性，比方為黑節點，則應再刪掉這八個子節點而把它們的共同父節點置為黑。*修改Cohen-Sutherland直線

45、裁剪算法，使其成為一個直線“開窗”算法，即指定一個窗口后，窗口內舍棄，窗口外保留。解答：根據題意，可知只需要對原Cohen-Sutherland算法中的兩處進行修改即可滿足要求。第一處是判斷C1和C2的邏輯乘結果不為0時，此時如果該條件滿足，表示線段完全在窗外，原算法此處需要將原線段完全舍棄，這里就需要將原線段完全繪制出來即可。第二處是最后要將原線段中窗口中可見部分繪制出來，此時原算法已經完成對原線段的裁剪，得出來原線段在窗口內的部分，這里只需要改成將原線段去掉窗口以內部分后的線段繪制出來即可。根據以上分析，修改Cohen-Sutherland直線裁剪算法為直線“開窗”算法如下：double

46、xl, xr, yt, yb; (這里事先給出窗口的位置，四個數值是已知的)，修改的部分用藍色表示void Cohen_Sutherland(double x0, y0, x2, y2)int c, c1, c2;double x, y;/需要將原線段的端點保存起來，以備后面需要確定原線段去除窗口內部分時使用double x00=x0,y00=y0,x22=x2,y22=y2;makecode(x0, y0,c1); makecode(x2, y2, c2);while (c1!=0 | c2!=0)if (c1&c2!=0) showline(x00, y00, x22, y22);

47、/顯示原線段，能走到這說明原線段都在窗口外return;c=c1; if (c=0) c=c2;if (c&1=1) y=y0+(y2-y0)*(x1-x0)/(x2-x0); x=x1;else if (c&2=2) y=y0+(y2-y0)*(xr-x0)/(x2-x0); x=xr;else if (c&4=4) x=x0+(x2-x0)*(yb-y0)/(y2-y0); y=yb;else if (c&8=8) x=x0+(x2-x0)*(yt-y0)/(y2-y0); y=yt;if (c=c1)x0=x; y0=y; makecode(x, y, c

48、1);elsex2=x; y2=y; makecode(x, y, c2);/因為原算法的線段分割保證了端點的順序性，所以采用如下的方法可確定原線段在窗口外的部分if (x00!=x0 | y00!=y0) showline(x00,y00,x0,y0);if (x2!=x22 | y2!=y22) showline(x2,y2,x22,y22);此算法已經編碼實現并測試通過。另一種方法是在分割線段的同時繪制窗口外的線段，該方法無需記錄初始點坐標。double xl, xr, yt, yb; (這里事先給出窗口的位置，四個數值是已知的)，修改的部分用藍色表示void Cohen_Sutherl

49、and(double x0, y0, x2, y2)int c, c1, c2;double x, y;makecode(x0, y0,c1); makecode(x2, y2, c2);while (c1!=0 | c2!=0)if (c1&c2!=0) /顯示線段，此時繪制的是分割完后，完全在窗口外同側的線段showline(x0, y0, x2, y2); return;c=c1; if (c=0) c=c2;if (c&1=1) y=y0+(y2-y0)*(x1-x0)/(x2-x0); x=x1;else if (c&2=2) y=y0+(y2-y0)*(xr

50、-x0)/(x2-x0); x=xr;else if (c&4=4) x=x0+(x2-x0)*(yb-y0)/(y2-y0); y=yb;else if (c&8=8) x=x0+(x2-x0)*(yt-y0)/(y2-y0); y=yt;if (c=c1)showline(x0,y0,x,y);/繪制被分割拋棄的線段x0=x; y0=y; makecode(x, y, c1);elseshowline(x,y,x2,y2);/繪制被分割拋棄的線段x2=x; y2=y; makecode(x, y, c2);DDA直線掃描轉換算法 void DDALine(int x1,in

51、t y1,int x2,int y2) double dx,dy,e,x,y; dx=x2-x1; dy=y2-y1;e=(fabs(dx)>fabs(dy)?fabs(dx):fabs(dy);dx/=e;dy/=e;x=x1;y=y1;for(int i=1;i<=e;i+) SetPixel(int)(x+0.5), (int)(y+0.5);x+=dx;y+=dy;中點畫線算法void MidpointLine (int x0,int y0,int x1,int y1)int a,b,delta1,delta2,d,x,y ;a = y0 - y1;b = x1 - x0;

52、d = 2 * a + b ;delta1 = 2 * a ;delta2 = 2 *( a + b);x = x0 ;y = y0 ;SetPixel(x,y);while( x<x1 )if( d<0 ) x +;y +;d+= delta2;else x +;d+= delta1;SetPixel(x,y);Bresenham畫線算法void BresenhamLine(int x1,int y1,int x2,int y2)int x,y,dx,dy,p;x=x1;y=y1;dx=x2-x1; dy=y2-y1;p=2*dy-dx;for(;x<=x2;x+) Set

53、Pixel(x,y);if(p>=0) y+;p+=2*(dy-dx);elsep+=2*dy;四連通內定義區域的填充算法void Floodfill(int x,int y,COLORREF oldvalue,COLORREF newvalue) if (GetPixel(x,y) = oldvalue) SetPixel(x,y,newvalue);/賦值為新值Floodfill(x,y-1,oldvalue,newvalue);/四向擴散Floodfill(x,y+1,oldvalue,newvalue);Floodfill(x-1,y,oldvalue,newvalue);Flo

54、odfill(x+1,y,oldvalue,newvalue); 掃描線種子填充算法1對種子所在像素段進行填充。2從右至左檢查種子所在行的上一橫行，將查得的像素段依次編號存入堆棧。接著對種子所在行的下一橫行同樣處理。 3若堆棧為空則算法結束，否則從堆棧頂部取出一個像素段。就以這個像素為新的種子，返回到1。void ScanlineSeedfill(int x,int y,COLORREF boundaryvalue,COLORREF newvalue)int x0,xl,xr,y0,xid;int flag;Stack s; Point p;s.push(Point(x,y);/種子像素入棧w

55、hile(!s.isempty()p=s.pop(); /棧頂像素出棧x=p.x;y=p.y;SetPixel(x ,y ,newvalue); x0= x+1;while(GetPixel(x0,y)!=boundaryvalue)/填充右方像素SetPixel(x0 ,y ,newvalue);x0+;xr=x0-1;/最右像素x0= x-1;while(GetPixel(x0,y)!=boundaryvalue)/填充左方像素SetPixel(x0 ,y ,newvalue);x0-;xl=x0+1;/最左像素/檢查上一條掃描線和下一條掃描線，/若存在非邊界且未填充的像素，/則選取代表各連續區間的種子像素入棧。y0=y;for(in