吉林大學(xué)計(jì)算機(jī)圖形學(xué)匯總(共27頁(yè))

1、 名詞解釋*計(jì)算機(jī)圖形學(xué)是指用計(jì)算機(jī)產(chǎn)生對(duì)象圖形的輸出的技術(shù)。更確切的說(shuō)，計(jì)算機(jī)圖形學(xué)是研究(ynji)通過(guò)計(jì)算機(jī)將數(shù)據(jù)轉(zhuǎn)換為圖形，并在專(zhuān)門(mén)顯示設(shè)備上顯示的原理、方法和技術(shù)的學(xué)科。*圖形學(xué)的主要研究(ynji)內(nèi)容：圖形的生成和表示技術(shù)；圖形的操作(cozu)和處理方法；圖形輸出設(shè)備與輸出技術(shù)的研究；圖形輸入設(shè)備、交互技術(shù)和用戶(hù)接口技術(shù)的研究；圖形信息的數(shù)據(jù)結(jié)構(gòu)及存儲(chǔ)、檢索方法；幾何模型構(gòu)造技術(shù)；動(dòng)畫(huà)技術(shù)；圖形軟硬件的系列化、模塊化和標(biāo)準(zhǔn)化的研究；科學(xué)計(jì)算的可視化*能夠正確地表達(dá)出一個(gè)對(duì)象性質(zhì)、結(jié)構(gòu)和行為的描述信息，成為這個(gè)對(duì)象的模型。*圖像處理是指用計(jì)算機(jī)來(lái)改善圖像質(zhì)量的數(shù)字技術(shù)。*模式識(shí)別

2、是指用計(jì)算機(jī)對(duì)輸入圖形進(jìn)行識(shí)別的技術(shù)。*計(jì)算幾何學(xué)是研究幾何模型和數(shù)據(jù)處理的學(xué)科。*交互式計(jì)算機(jī)圖形學(xué)是指用計(jì)算機(jī)交互式地產(chǎn)生圖形的技術(shù)。*計(jì)算機(jī)圖形系統(tǒng)的硬件包括五部分：計(jì)算機(jī)、顯示處理器、圖形顯示器、輸入設(shè)備、硬拷貝設(shè)備。*CRT圖形顯示器工作方式有兩種：隨機(jī)掃描方式和光柵掃描方式。*隨機(jī)掃描方式的圖形顯示器通過(guò)畫(huà)出一系列線(xiàn)段來(lái)畫(huà)出圖形。*一幀：掃描過(guò)程所產(chǎn)生的圖像。*像素：在光柵掃描圖形顯示器中，屏幕上可以點(diǎn)亮或熄滅的最小單位。*分辨率：顯示屏上像素的總數(shù)。*幀存儲(chǔ)器：二維矩陣，幀存儲(chǔ)大小=分辨率*單元字節(jié)，存儲(chǔ)屏幕上每個(gè)像素對(duì)應(yīng)的顏色或亮度值。*屏幕上每個(gè)像素對(duì)應(yīng)的顏色或亮度值要存儲(chǔ)在

3、幀存儲(chǔ)器中。*將圖形描述轉(zhuǎn)換成用像素矩陣表示的過(guò)程稱(chēng)為掃描轉(zhuǎn)換。*在光柵掃描顯示方式中像素坐標(biāo)是行和列的位置值，只能取整數(shù)。*圖形基元（輸出圖形元素）：圖形系統(tǒng)能產(chǎn)生的最基本圖形。*區(qū)域是指光柵網(wǎng)絡(luò)上的一組像素。*區(qū)域填充是把某確定的像素值送入到區(qū)域內(nèi)部的所有像素中。*區(qū)域填充方法：一類(lèi)方法是把區(qū)域看做是由多邊形圍成的，區(qū)域事實(shí)上由多邊形的頂點(diǎn)序列來(lái)定義，相應(yīng)的技術(shù)稱(chēng)為是以多邊形為基礎(chǔ)的；另一類(lèi)方法是通過(guò)像素的值來(lái)定義區(qū)域的內(nèi)部，這時(shí)可以定義出任意復(fù)雜形狀的區(qū)域。相應(yīng)的技術(shù)稱(chēng)為是以像素為基礎(chǔ)的。*通過(guò)像素的值的定義區(qū)域有兩種常用的方法。一種是內(nèi)定義區(qū)域，另一種是由邊界定義區(qū)域。*以像素為基礎(chǔ)的

4、區(qū)域填充主要是依據(jù)區(qū)域的連通性進(jìn)行。*四連通區(qū)域是指從區(qū)域的一個(gè)像素出發(fā)，經(jīng)過(guò)連續(xù)地向上、下、左、右四個(gè)相鄰像素的移動(dòng)，就可以到達(dá)區(qū)域內(nèi)的任意另一個(gè)像素的區(qū)域。（四聯(lián)通區(qū)域必是入連通的，反之未必）*八連通：如果除了要經(jīng)上下左右的移動(dòng)，還要經(jīng)左上、右上、左下和右下的移動(dòng)，才能由一個(gè)像素走到區(qū)域中另外任意一個(gè)像素。*利用區(qū)域的連通性進(jìn)行區(qū)域填充(tinchng)，除了需要區(qū)域應(yīng)該明確定義外，還需要事先給定一個(gè)區(qū)域內(nèi)部像素，這個(gè)像素稱(chēng)為種子(zhng zi)。做區(qū)域填充(tinchng)時(shí)，要進(jìn)行對(duì)光柵網(wǎng)格的遍歷。*像素段：將區(qū)域內(nèi)由邊界點(diǎn)限定的同一行內(nèi)相連接的不具有新值newvalue的一組像素稱(chēng)

5、為一個(gè)像素段，像素段用它最右邊的像素來(lái)標(biāo)識(shí)。*奇偶性質(zhì)：即一條直線(xiàn)與任意封閉的曲線(xiàn)相交時(shí)，總是從第一個(gè)交點(diǎn)進(jìn)入內(nèi)部，再?gòu)牡诙€(gè)交點(diǎn)退出，以下交替的進(jìn)入退出，即奇數(shù)次進(jìn)入，偶數(shù)次退出。當(dāng)然可能有一些“相切”的點(diǎn)應(yīng)特殊處理。*活躍邊：與當(dāng)前掃描線(xiàn)相交的邊。*活躍邊表AET：存貯當(dāng)前掃描線(xiàn)相交的各邊的表。*邊表ET：記錄多邊形的所有邊。*“吊桶”中各項(xiàng)的內(nèi)容一次是：1、邊的另一端點(diǎn)的較大的y坐標(biāo)ymax；2、與較小的y坐標(biāo)對(duì)應(yīng)的邊的斷電的x坐標(biāo)xmin；3、斜率的倒數(shù)，1/m。*柵欄：指一條與掃描線(xiàn)垂直的線(xiàn)，把多邊形一分為二。*規(guī)范化設(shè)備坐標(biāo)系：圖形系統(tǒng)為具體設(shè)備無(wú)關(guān)的引入，是二維正方形或三維正方體

6、，即各坐標(biāo)范圍規(guī)定為從0到1。*常見(jiàn)的基本二維圖形幾何變換有：平移變換、比例變換和旋轉(zhuǎn)變換。*本體坐標(biāo)系（模型坐標(biāo)系）：為規(guī)定基本形體而引入的便于描述的坐標(biāo)系。*用戶(hù)坐標(biāo)系（世界坐標(biāo)系）：用戶(hù)引入描述整個(gè)形體的坐標(biāo)系。*觀察坐標(biāo)系（視覺(jué)坐標(biāo)系/目坐標(biāo)系）：為說(shuō)明觀察姿態(tài)而引入，也就是觀察者所處的位置。*設(shè)備坐標(biāo)系（顯示器坐標(biāo)系/屏坐標(biāo)系）：是各種圖形設(shè)備自身規(guī)定的在顯示表面上采用的坐標(biāo)系。*齊次坐標(biāo)表示法就是用n+1維向量表示一個(gè)n維向量。*窗口就是在用戶(hù)坐標(biāo)系中指出的那個(gè)要顯示出來(lái)的區(qū)域，這一區(qū)域通常為矩形區(qū)域*通常把整個(gè)顯示屏幕區(qū)域稱(chēng)作屏幕域，它是設(shè)備輸出圖形的最大區(qū)域，是有限的區(qū)域。*視

7、見(jiàn)區(qū)是屏幕域中的一個(gè)子區(qū)域，通常為矩形區(qū)域，它最大與屏幕域等同。視見(jiàn)區(qū)用于顯示窗口中的圖形。*窗口與視見(jiàn)區(qū)的差別在于：窗口是在用戶(hù)坐標(biāo)系中確定的，它指出了要顯示的圖形，也就是我們想要看見(jiàn)什么；而視見(jiàn)區(qū)在設(shè)備坐標(biāo)系中確定，它指出了實(shí)際顯示的圖形處于顯示屏幕的哪一部分，也就是我們要用顯示屏幕的哪部分實(shí)際去看。視見(jiàn)區(qū)在設(shè)備坐標(biāo)系中定義，也可以用矩形區(qū)域的左下角點(diǎn)和右上角點(diǎn)的坐標(biāo)來(lái)表示。*視見(jiàn)變換：就是將用戶(hù)坐標(biāo)系窗口內(nèi)的圖形變換到顯示屏幕設(shè)備坐標(biāo)系的視見(jiàn)區(qū)中以產(chǎn)生顯示。*投影就是把n維空間中的點(diǎn)投射到小于n維的空間中去。*投影是如何形成的：首先在三維空間中確定一個(gè)投影中心和一個(gè)投影平面，然后從投影中

8、心引出一些投射直線(xiàn)，這些直線(xiàn)通過(guò)形體上的沒(méi)一點(diǎn)，與投影平面相交，在投影平面上就形成了形體的投影。*平行投影：當(dāng)投影中心與投影平面的距離為無(wú)窮遠(yuǎn)時(shí)，投射直線(xiàn)成為一組平行線(xiàn)，這種投影稱(chēng)為平行投影。*透視(tush)投影：當(dāng)投影中心與投影平面的距離是有限數(shù)值時(shí)，投射直線(xiàn)交于一點(diǎn)，形成(xngchng)滅點(diǎn)，這種投影稱(chēng)為透視投影。*平行投影可以(ky)分為兩種類(lèi)型：正交投影和斜交投影。*正交投影：投影方向與投影平面的法向相同。即投影方向垂直于投影平面。*常見(jiàn)的正交投影（三視圖）：正視投影、頂視投影、側(cè)視投影。*正投影：投影平面垂直于坐標(biāo)軸的正交投影。（正視投影、頂視投影和側(cè)視投影）*等軸投影：投影方向

9、與三個(gè)坐標(biāo)軸的夾角都相等。這種投影能使在三個(gè)坐標(biāo)軸方向上有相等的透視縮短。*斜交投影：投影方向與投影平面的法向不同。*常見(jiàn)的斜交投影：斜二側(cè)投影和斜等軸投影。在斜交投影中，投影平面一般取坐標(biāo)平面。*斜二側(cè)投影：垂直于投影平面的線(xiàn)段長(zhǎng)度縮短為原來(lái)的一半。*斜等軸投影：使垂直于投影平面的線(xiàn)段仍保持長(zhǎng)度。*透視投影性質(zhì)：任意一組平行直線(xiàn)，如果平行于投影平面，則經(jīng)透視投影后所得到的直線(xiàn)或者重合，或者仍保持平行；如果不平行于投影平面，將不再保持平行，并且必會(huì)匯聚于同一點(diǎn)。*消失點(diǎn)（滅點(diǎn)）：任意一組不平行于投影平面的平行直線(xiàn)，投影后所得的直線(xiàn)，必將匯聚于同一點(diǎn)。消失點(diǎn)可以取任意多個(gè)。*主消失點(diǎn)：三維直角坐

10、標(biāo)系中，透視投影時(shí)，如果一組平行直線(xiàn)平行于三個(gè)坐標(biāo)軸中的一個(gè)，那么對(duì)應(yīng)的消失點(diǎn)將落在坐標(biāo)軸上。最多只有三個(gè)主消失點(diǎn)。*裁剪：去掉窗口外的不可見(jiàn)部分，保留窗口內(nèi)的可見(jiàn)部分的過(guò)程。*三維圖形顯示的處理流程:Z方向深度裁剪世界坐標(biāo)變換T1投影T2窗口至視窗的變換T3至物理設(shè)備變換T4裁剪顯示*參數(shù)曲線(xiàn)的構(gòu)造方法：曲線(xiàn)上每一點(diǎn)的坐標(biāo)均要表示成某個(gè)參數(shù)t的一個(gè)函數(shù)式，則曲線(xiàn)上每一點(diǎn)笛卡爾坐標(biāo)參數(shù)式是：x=x(t)，y=y(t)，z=z(t)；把三個(gè)方程合寫(xiě)到一起，曲線(xiàn)上一點(diǎn)坐標(biāo)的向量表示是：P(t)=x(t) y(t) z(t)；如用“”表示對(duì)參數(shù)求導(dǎo)，則P(t)關(guān)于參數(shù)t的切向量或?qū)Ш瘮?shù)是：P(t)=

11、x(t) y(t) z(t)。類(lèi)似地，曲面寫(xiě)為參數(shù)方程形式為：x=x(u,w)，y=y(u,w)，z=z(u,w)；寫(xiě)成向量形式，則是：P(u,w)=x(u,w)，y(u,w)，z(u,w)*參數(shù)方程的優(yōu)點(diǎn)：1）對(duì)非參數(shù)方程表示的曲線(xiàn)、曲面進(jìn)行變換，必須對(duì)曲線(xiàn)、曲面上的每個(gè)型值點(diǎn)進(jìn)行幾何變換；而對(duì)參數(shù)表示的曲線(xiàn)、曲面可對(duì)其參數(shù)方程直接進(jìn)行幾何變換（如平移、比例、旋轉(zhuǎn)），從而節(jié)省計(jì)算工作量。2）便于處理斜率為無(wú)限大的問(wèn)題。3）有更大的自由度來(lái)控制曲線(xiàn)、曲面的形狀。同時(shí)對(duì)于復(fù)雜的曲線(xiàn)和曲面具有很強(qiáng)的描述能力和豐富的表達(dá)能力。4）參數(shù)方程中，代數(shù)、幾何相關(guān)和無(wú)關(guān)的變量是完全分離的，而且對(duì)變量個(gè)數(shù)不限

12、，從而便于用戶(hù)把低維空間中的曲線(xiàn)、曲面擴(kuò)展到高維空間去。這種變量分離的特點(diǎn)使我們可以用數(shù)學(xué)公式去處理幾何分量，同時(shí)可以使曲線(xiàn)和曲面具有統(tǒng)一的表示形式。5）規(guī)格化的參數(shù)(cnsh)變量t0，1，使其相應(yīng)的幾何分量是有界的，而不必用另外的參數(shù)去定義其邊界。它便于(biny)曲線(xiàn)和曲面的分段、分片描述，易于實(shí)現(xiàn)光順連接。6）易于用向量和矩陣表示幾何分量，計(jì)算(j sun)處理簡(jiǎn)便易行。*計(jì)算機(jī)上表現(xiàn)的曲線(xiàn)和曲面，大體上可分為兩類(lèi)：一類(lèi)要求通過(guò)事先給定的離散的點(diǎn)，稱(chēng)為插值的曲線(xiàn)或曲面。另一類(lèi)不要求通過(guò)事先給定的各離散點(diǎn)，而只是用給定各離散點(diǎn)形成的控制多邊形來(lái)控制形狀，成為逼近的曲線(xiàn)或曲面。事先給定的離

13、散點(diǎn)常稱(chēng)為型值點(diǎn)，由型值點(diǎn)求插值的或逼近的曲線(xiàn)或曲面的問(wèn)題，稱(chēng)為曲線(xiàn)或曲面的擬合問(wèn)題。*插值：要求構(gòu)造一條曲線(xiàn)順序通過(guò)型值點(diǎn)，稱(chēng)為對(duì)這些型值點(diǎn)進(jìn)行插值。*逼近：當(dāng)型值點(diǎn)太多時(shí)，構(gòu)造插值函數(shù)使其通過(guò)所有的型值點(diǎn)相當(dāng)困難的。此時(shí)人們往往構(gòu)造一條曲線(xiàn)，使它在某種意義上最佳逼近這些型值點(diǎn)，稱(chēng)之為對(duì)這些型值點(diǎn)進(jìn)行逼近。*曲線(xiàn)的數(shù)學(xué)表示形式：顯示、隱式、參數(shù)*在計(jì)算機(jī)上表現(xiàn)的曲線(xiàn)和曲面，大體分為兩類(lèi)：一類(lèi)要求通過(guò)事先給定的離散的點(diǎn)，稱(chēng)為插值的曲線(xiàn)或曲面，另一類(lèi)不要求通過(guò)事先給定的各離散點(diǎn)，而只是用給定各離散點(diǎn)形成的控制多邊形來(lái)控制形狀，稱(chēng)為逼近的曲線(xiàn)或曲面。*光順是指曲線(xiàn)的拐點(diǎn)不能太多，要光滑順暢。*Be

14、zier曲線(xiàn)性質(zhì)：1.P(0)=P0,P(1)=P1,曲線(xiàn)通過(guò)所給出型值點(diǎn)列的起點(diǎn)和終點(diǎn)2.P(0)=n(P1-P0),P(1)=n(Pn-Pn-1)曲線(xiàn)在始點(diǎn)和終點(diǎn)處的切線(xiàn)方向與它的控制多邊形的第一邊和最后一邊的走向一致。3.曲線(xiàn)有對(duì)稱(chēng)性，4.曲線(xiàn)的凸包性。整條曲線(xiàn)都包含在所有控制點(diǎn)所張成的凸包中。*簡(jiǎn)述B樣條曲線(xiàn)與Bezier之間的關(guān)系N+1個(gè)控制點(diǎn)P0,P1,Pn所確定的最高階的B樣條曲線(xiàn)是k=n+1階的，這時(shí)由節(jié)點(diǎn)向量(0,0,0,1,1,1)所去頂?shù)腂樣條曲線(xiàn)，與該n+1個(gè)控制點(diǎn)所確定的Bezier曲線(xiàn)相同。這個(gè)結(jié)論說(shuō)明了B樣條曲線(xiàn)確實(shí)是Bezier曲線(xiàn)的一種推廣，Bezier曲線(xiàn)是

15、B樣條曲線(xiàn)的特例。*凸殼：包含一個(gè)平面點(diǎn)集的最小凸區(qū)域。*凸區(qū)域：指要求區(qū)域內(nèi)任意兩點(diǎn)的連線(xiàn)仍在該區(qū)域內(nèi)。*求點(diǎn)集S的凸殼（設(shè)S是平面上n個(gè)點(diǎn)的集合，則S的凸殼是一個(gè)凸多邊形，它包含所有n點(diǎn)且面積最小）：1）在S中選出殼上的點(diǎn)；2）給出圍成凸多邊形的序列。*Graham掃面的實(shí)質(zhì)是圍繞已經(jīng)按“傾角”排序的各頂點(diǎn)進(jìn)行一次掃描，在掃描過(guò)程中消去在凸殼內(nèi)部的點(diǎn)，留下以希望次序排列的殼頂點(diǎn)。由于是按傾角遞增排序，故可知若三個(gè)頂點(diǎn)P1.P2.P3連續(xù)“右轉(zhuǎn)”，則P2是一個(gè)應(yīng)去掉的內(nèi)點(diǎn)。*簡(jiǎn)單多邊形：是平面上不相鄰的邊不能相交的多邊形。*簡(jiǎn)單多邊形做三角剖分：要求選出完全在內(nèi)部又互不相交的一組對(duì)角線(xiàn)，把整

16、個(gè)多邊形劃分成一些三角形。（對(duì)角線(xiàn)是不相鄰頂點(diǎn)間的連線(xiàn)）*簡(jiǎn)單多邊形的三角剖分：是選出的對(duì)角線(xiàn)的集合。*最小權(quán)三角(snjio)剖分（最小三角剖分）：一個(gè)(y )三角剖分中選取的對(duì)角線(xiàn)的總長(zhǎng)度最小。*與空間任意形體有關(guān)的信息(xnx)可以分為：圖形信息和非圖形信息兩類(lèi)。*圖形信息指構(gòu)成它們的點(diǎn)、線(xiàn)、面的位置，互相關(guān)系及大小等。*非圖形信息指形體的顏色、亮度、質(zhì)量、體積等一些性質(zhì)。*圖形信息包括：1、幾何信息：形體在空間的位置和大小。2、拓?fù)湫畔ⅲ航M成形體各部分的數(shù)目及相互間的連接關(guān)系。*形體的表示方法通?？煞譃閮深?lèi)：1、邊界表示：用邊界將形體分為內(nèi)部和外部。2、空間分區(qū)表示：描述形體的內(nèi)部性質(zhì)

17、，將包含形體的空間區(qū)域劃分為一組小的非重疊的連續(xù)實(shí)體。*曲線(xiàn)的表示法：1、折線(xiàn)法：就是用多段線(xiàn)段形成的折線(xiàn)去逼近曲線(xiàn)。2、帶樹(shù)法：帶樹(shù)就是一棵二叉樹(shù)，樹(shù)的每個(gè)結(jié)點(diǎn)對(duì)應(yīng)一個(gè)矩形帶段，這樣每個(gè)結(jié)點(diǎn)可由八個(gè)字段組成，前六個(gè)字段描述矩形帶段，后二個(gè)是指向兩個(gè)子結(jié)點(diǎn)的指針，即矩形帶段的起點(diǎn)是（xb，yb），終點(diǎn)是（xe，ye）。相對(duì)從起點(diǎn)到終點(diǎn)的連線(xiàn)，矩形有兩邊與之平行，兩邊與之垂直，平行兩邊與之距離分別為wl和wr。*三種四叉樹(shù)的存儲(chǔ)結(jié)構(gòu)，即規(guī)則方式、線(xiàn)性方式、一對(duì)四方式*四叉樹(shù)優(yōu)點(diǎn)（與像素陣列表示）：1）節(jié)省存儲(chǔ)空間；2）可以用不同精度來(lái)表示；3）與設(shè)備無(wú)關(guān)，便于移植。*形體的模型：主要指的就是包含

18、圖形信息所形成的模型。*幾何元素：形體本身的構(gòu)造有一定的層次性，底層部分組合構(gòu)成上一層部分，而上一層部分組合又可以構(gòu)成更高一層的部分，依次類(lèi)推可形成多層結(jié)構(gòu)。其中，每一層中的部分，我們把它又稱(chēng)為幾何元素。*消除隱藏面（面消隱）：確定可見(jiàn)面等價(jià)于消除場(chǎng)景中物體的不可見(jiàn)面。*消除隱藏線(xiàn)（線(xiàn)消隱）：顯示采用線(xiàn)框模型表示的物體時(shí)，要消除不可見(jiàn)的線(xiàn)。*面消隱算法分兩大類(lèi)：1、圖像空間算法：對(duì)顯示設(shè)備上每一個(gè)可分辨像素進(jìn)行判斷，看組成物體的多個(gè)多邊形表面中哪一個(gè)在該像素上可見(jiàn)，既要對(duì)每一像素檢查所有的表面。2、客體空間算法：把注意力集中在分析要顯示形體各部分之間的關(guān)系上，這種算法對(duì)每一個(gè)組成形體的表面，都

19、要與其它各表面進(jìn)行比較，以便消去不可見(jiàn)的面或面的不可見(jiàn)部分。*可見(jiàn)面：朝向觀察位置的面。*范圍檢查：即為最大最小檢驗(yàn)，通過(guò)比較有關(guān)的最大或最小值來(lái)實(shí)現(xiàn)。*點(diǎn)：是0維幾何元素，有端點(diǎn)、交點(diǎn)、切點(diǎn)、孤立點(diǎn)等形式。*邊：是一維幾何元素，是兩個(gè)鄰面（正則形體）或多個(gè)鄰面（非正則形體）的交界。*環(huán)：有序有向邊（直線(xiàn)段或曲線(xiàn)段）組成的面的封閉邊界。*面：是二維幾何元素(yun s)，是形體上一個(gè)有限、非零的區(qū)域，它由一個(gè)外環(huán)和若干個(gè)內(nèi)環(huán)所界定。*體是三維幾何元素(yun s)，由封閉表面圍成的空間，它是歐氏空間R3中非空、有界的封閉(fngb)子集，其邊界是有限面的并集。*體素：是可以用有限個(gè)尺寸參數(shù)定位

20、和定型的體。*形體的層次結(jié)構(gòu)：點(diǎn) - 邊 - 環(huán) - 面 - 外殼 - 形體*常用的多面體三表表示法是：頂點(diǎn)表，邊表，面表*通常用正則集合運(yùn)算來(lái)實(shí)現(xiàn)這種組合。*確定可見(jiàn)面等價(jià)于消除場(chǎng)景種物體的不可見(jiàn)面，即消除隱藏面（面消隱）*消隱面算法大體分為兩個(gè)大類(lèi)，即圖像空間算法和客體空間算法。*圖像空間算法把注意力集中在最終形成的圖形上?？腕w空間算法把注意力集中在分析要顯示形體各部分之間的關(guān)系上。*范圍檢查又稱(chēng)為最大最小檢驗(yàn)。設(shè)平面上四點(diǎn)設(shè)平面上四點(diǎn)(1，1)，(2，3)，(4，3)，(3，1)確定的Bezier曲線(xiàn)是P(t)，如果在點(diǎn)P(1/2)處將它分為兩段，求前后兩段做為Bezier曲線(xiàn)各自的四個(gè)

21、控制點(diǎn)坐標(biāo)。解答：使用分裂法，有：P0(1,1)R0P1(2,3)R1P2(4,3)R2P3(3,1)R3R0=(3/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前半段四個(gè)控制點(diǎn)Q0(1,1)，Q1(3/2,2)，Q2(9/4,5/2)，Q3(11/4,5/2)，0t1/2；后半段四個(gè)控制點(diǎn)R0(11/4,5/2)，R1(13/4,5/2)，R2(7/2,2)，R3(3,1)，1/2t1。*用計(jì)算機(jī)在圖形設(shè)備上生成真實(shí)感圖形必須完成四個(gè)基本的任務(wù)。第一用數(shù)學(xué)方法建立所構(gòu)造三 維場(chǎng)景的幾

22、何描述，并將它們輸入至計(jì)算機(jī)。第二,將三維幾何描述轉(zhuǎn)換為二維透視圖。第三,確定場(chǎng)景中的所有可見(jiàn)面，這需要使用隱藏面消除算法將被其它物體遮擋的不可見(jiàn)面消去。第四 計(jì)算場(chǎng)景中可見(jiàn)面的顏色，嚴(yán)格地說(shuō)，就是根據(jù)基于光學(xué)物理的光照明模型計(jì)算可見(jiàn)面投射到觀察者眼中的光亮度大小和顏色組成，并將它轉(zhuǎn)換成適合圖形設(shè)備的顏色值，從而確定投影畫(huà)面上每一象素的顏色，最終生成圖形。*設(shè)計(jì)一個(gè)光照模型需要考慮的主要問(wèn)題是照明特性、表面特性和觀察角度光照模型可以分解為三個(gè)部分，即漫射照明，具體光源的照射和透射效應(yīng)具體光源在物體表面可以引起漫反射和鏡面反射。亮度公式：I=IaKa+IpKd(L*N)Phong Bui Tuo

23、ng 提出的光照明模型，用cosna來(lái)近似表示反射光線(xiàn)引起的亮度隨著a增大而下降的速率。N的取值一般在02000之間，決定于反射表面的有關(guān)性質(zhì)。對(duì)于理想的反射表面，n就是無(wú)窮大。這里選用cosna，是以觀察經(jīng)驗(yàn)為基礎(chǔ)的。對(duì)實(shí)際物質(zhì)來(lái)說(shuō)，被鏡面反射的入射光的數(shù)量與入射角B有關(guān)，如果將鏡面反射光的百分?jǐn)?shù)記為W(B)，那么久可以將計(jì)算表面亮度的公式I=IaKa+IpKd(L*N)/(r+k)修改得到I=IaKa+Ip/(r+k)*Kd(L*N)+Ks(R*V)n方*$8深度暗示(nsh)技術(shù)首先(shuxin)，再投影坐標(biāo)系中定義兩個(gè)平面Z=Zf,Z=Zb,分別為前參考面和后參考面，并賦予比例因子S

24、f和Sb(Sf,Sb(-0,1)。給定(i dn)物體上一點(diǎn)的深度值Z0,該點(diǎn)對(duì)應(yīng)的比例因子S0這樣來(lái)確定1)當(dāng)Z0Zf時(shí)，取S0=Sf 2)當(dāng)Z0Zb時(shí)，取S0=Sb 3)當(dāng)Z0(- Zb,Zf時(shí)，S0=Sb+(Sf-Sb)/(Zf-Zb)*(Z0-Zb)原亮度I按比例S0與亮度Idc混合，目的是活的最終用于顯示的亮度I,Idc由用戶(hù)指定：I=S0I+(1-S0)Idc 若取Sf=1,Sb=0,Idc=0,則當(dāng)物體位于前參考面之前時(shí)，I=I.即亮度沒(méi)有被衰減；當(dāng)物體位于后參考面之后，I=Idc=0，即亮度被衰減為0，else I=S0I,亮度被部分衰減。*Phong方法繪制多邊形步驟計(jì)算多邊

25、形的單位法向量計(jì)算多邊形頂點(diǎn)的單位法向量。再掃描線(xiàn)消隱算法中，對(duì)多邊形頂點(diǎn)的法向量進(jìn)行雙線(xiàn)性插值，計(jì)算出多邊形內(nèi)部各點(diǎn)法向量當(dāng)掃描線(xiàn)y遞增一個(gè)單位，變?yōu)閥+1時(shí)，Na,Nb的增量分別為Na,Nb當(dāng)x遞增一個(gè)單位時(shí)Np增量為Np利用光照模型計(jì)算P點(diǎn)的顏色 解答題*計(jì)算機(jī)圖形學(xué)是指用計(jì)算機(jī)產(chǎn)生對(duì)象圖形的輸出的技術(shù)。更確切的說(shuō)，計(jì)算機(jī)圖形學(xué)是研究通過(guò)計(jì)算機(jī)將數(shù)據(jù)轉(zhuǎn)換為圖形，并在專(zhuān)門(mén)顯示設(shè)備上顯示的原理、方法和技術(shù)的學(xué)科。*圖形學(xué)的主要研究?jī)?nèi)容：圖形的生成和表示技術(shù)；圖形的操作和處理方法；圖形輸出設(shè)備與輸出技術(shù)的研究；圖形輸入設(shè)備、交互技術(shù)和用戶(hù)接口技術(shù)的研究；圖形信息的數(shù)據(jù)結(jié)構(gòu)及存儲(chǔ)、檢索方法；幾何

26、模型構(gòu)造技術(shù)；動(dòng)畫(huà)技術(shù)；圖形軟硬件的系列化、模塊化和標(biāo)準(zhǔn)化的研究；科學(xué)計(jì)算的可視化*與計(jì)算機(jī)圖形學(xué)相關(guān)的學(xué)科及它們之間的關(guān)系： 對(duì)象的描述 計(jì)算機(jī)圖形學(xué) 模式識(shí)別對(duì)象的圖形圖像處理圖像處理是指用計(jì)算機(jī)來(lái)改善圖像質(zhì)量的數(shù)字技術(shù)。模式識(shí)別是指計(jì)算機(jī)對(duì)輸入圖形進(jìn)行識(shí)別的技術(shù)。*計(jì)算機(jī)圖形系統(tǒng)的硬件包括五部分：計(jì)算機(jī)、顯示處理器、圖形顯示器、輸入設(shè)備、硬拷貝設(shè)備。*CRT圖形顯示器工作方式有兩種：隨機(jī)掃描方式和光柵掃描方式。*窗口與視見(jiàn)區(qū)的差別在于：窗口是在用戶(hù)坐標(biāo)系中確定的，它指出了要顯示的圖形，也就是我們想要看見(jiàn)什么；而視見(jiàn)區(qū)在設(shè)備坐標(biāo)系中確定，它指出了實(shí)際顯示的圖形處于顯示屏幕的哪一部分，也就是

27、我們要用顯示屏幕的哪部分實(shí)際去看。視見(jiàn)區(qū)在設(shè)備坐標(biāo)系中定義，也可以用矩形區(qū)域的左下角點(diǎn)和右上角點(diǎn)的坐標(biāo)來(lái)表示。*投影(tuyng)的形成過(guò)程：首先在三維空間中確定一個(gè)投影中心(zhngxn)和一個(gè)投影平面，然后從投影中心引出一些投射直線(xiàn)，這些直線(xiàn)通過(guò)形體上的沒(méi)一點(diǎn)，與投影平面相交，在投影平面上就形成了形體的投影。*三維圖形顯示(xinsh)的處理流程:Z方向深度裁剪世界坐標(biāo)變換T1投影T2窗口至視窗的變換T3至物理設(shè)備變換T4裁剪顯示*參數(shù)曲線(xiàn)的構(gòu)造方法：曲線(xiàn)上每一點(diǎn)的坐標(biāo)均要表示成某個(gè)參數(shù)t的一個(gè)函數(shù)式，則曲線(xiàn)上每一點(diǎn)笛卡爾坐標(biāo)參數(shù)式是：x=x(t)，y=y(t)，z=z(t)；把三個(gè)方程合

28、寫(xiě)到一起，曲線(xiàn)上一點(diǎn)坐標(biāo)的向量表示是：P(t)=x(t) y(t) z(t)；如用“”表示對(duì)參數(shù)求導(dǎo)，則P(t)關(guān)于參數(shù)t的切向量或?qū)Ш瘮?shù)是：P(t)=x(t) y(t) z(t)。類(lèi)似地，曲面寫(xiě)為參數(shù)方程形式為：x=x(u,w)，y=y(u,w)，z=z(u,w)；寫(xiě)成向量形式，則是：P(u,w)=x(u,w)，y(u,w)，z(u,w)*參數(shù)方程的優(yōu)點(diǎn)：1）對(duì)非參數(shù)方程表示的曲線(xiàn)、曲面進(jìn)行變換，必須對(duì)曲線(xiàn)、曲面上的每個(gè)型值點(diǎn)進(jìn)行幾何變換；而對(duì)參數(shù)表示的曲線(xiàn)、曲面可對(duì)其參數(shù)方程直接進(jìn)行幾何變換（如平移、比例、旋轉(zhuǎn)），從而節(jié)省計(jì)算工作量。2）便于處理斜率為無(wú)限大的問(wèn)題。3）有更大的自由度來(lái)控制

29、曲線(xiàn)、曲面的形狀。同時(shí)對(duì)于復(fù)雜的曲線(xiàn)和曲面具有很強(qiáng)的描述能力和豐富的表達(dá)能力。4）參數(shù)方程中，代數(shù)、幾何相關(guān)和無(wú)關(guān)的變量是完全分離的，而且對(duì)變量個(gè)數(shù)不限，從而便于用戶(hù)把低維空間中的曲線(xiàn)、曲面擴(kuò)展到高維空間去。這種變量分離的特點(diǎn)使我們可以用數(shù)學(xué)公式去處理幾何分量，同時(shí)可以使曲線(xiàn)和曲面具有統(tǒng)一的表示形式。5）規(guī)格化的參數(shù)變量t0，1，使其相應(yīng)的幾何分量是有界的，而不必用另外的參數(shù)去定義其邊界。它便于曲線(xiàn)和曲面的分段、分片描述，易于實(shí)現(xiàn)光順連接。6）易于用向量和矩陣表示幾何分量，計(jì)算處理簡(jiǎn)便易行。*計(jì)算機(jī)上表現(xiàn)的曲線(xiàn)和曲面，大體上可分為兩類(lèi)：一類(lèi)要求通過(guò)事先給定的離散的點(diǎn)，稱(chēng)為插值的曲線(xiàn)或曲面。另一

30、類(lèi)不要求通過(guò)事先給定的各離散點(diǎn)，而只是用給定各離散點(diǎn)形成的控制多邊形來(lái)控制形狀，成為逼近的曲線(xiàn)或曲面。事先給定的離散點(diǎn)常稱(chēng)為型值點(diǎn)，由型值點(diǎn)求插值的或逼近的曲線(xiàn)或曲面的問(wèn)題，稱(chēng)為曲線(xiàn)或曲面的擬合問(wèn)題。*Bezier曲線(xiàn)性質(zhì)：1.P(0)=P0,P(1)=P1,曲線(xiàn)通過(guò)所給出型值點(diǎn)列的起點(diǎn)和終點(diǎn)2.P(0)=n(P1-P0),P(1)=n(Pn-Pn-1)曲線(xiàn)在始點(diǎn)和終點(diǎn)處的切線(xiàn)方向與它的控制多邊形的第一邊和最后一邊的走向一致。3.曲線(xiàn)有對(duì)稱(chēng)性，4.曲線(xiàn)的凸包性。整條曲線(xiàn)都包含在所有控制點(diǎn)所張成的凸包中。*簡(jiǎn)述B樣條曲線(xiàn)與Bezier之間的關(guān)系N+1個(gè)控制點(diǎn)P0,P1,Pn所確定的最高階的B樣條

31、曲線(xiàn)是k=n+1階的，這時(shí)由節(jié)點(diǎn)向量(0,0,0,1,1,1)所去頂?shù)腂樣條曲線(xiàn)，與該n+1個(gè)控制點(diǎn)所確定的Bezier曲線(xiàn)相同。這個(gè)結(jié)論說(shuō)明了B樣條曲線(xiàn)確實(shí)是Bezier曲線(xiàn)的一種推廣，Bezier曲線(xiàn)是B樣條曲線(xiàn)的特例。*Graham掃面的實(shí)質(zhì)(shzh)是圍繞(wiro)已經(jīng)按“傾角(qngjio)”排序的各頂點(diǎn)進(jìn)行一次掃描，在掃描過(guò)程中消去在凸殼內(nèi)部的點(diǎn)，留下以希望次序排列的殼頂點(diǎn)。由于是按傾角遞增排序，故可知若三個(gè)頂點(diǎn)P1.P2.P3連續(xù)“右轉(zhuǎn)”，則P2是一個(gè)應(yīng)去掉的內(nèi)點(diǎn)。*形體的表示方法通?？煞譃閮深?lèi)： 1、邊界表示：用邊界將形體分為內(nèi)部和外部。 2、空間分區(qū)表示：描述形體的內(nèi)部性

32、質(zhì)，將包含形體的空間區(qū)域劃分為一組小的非重疊的連續(xù)實(shí)體。*曲線(xiàn)的表示法：1、折線(xiàn)法：就是用多段線(xiàn)段形成的折線(xiàn)去逼近曲線(xiàn)。2、帶樹(shù)法：帶樹(shù)就是一棵二叉樹(shù)，樹(shù)的每個(gè)結(jié)點(diǎn)對(duì)應(yīng)一個(gè)矩形帶段，這樣每個(gè)結(jié)點(diǎn)可由八個(gè)字段組成，前六個(gè)字段描述矩形帶段，后二個(gè)是指向兩個(gè)子結(jié)點(diǎn)的指針，即矩形帶段的起點(diǎn)是（xb，yb），終點(diǎn)是（xe，ye）。相對(duì)從起點(diǎn)到終點(diǎn)的連線(xiàn)，矩形有兩邊與之平行，兩邊與之垂直，平行兩邊與之距離分別為wl和wr。*面消隱算法分兩大類(lèi)：1、圖像空間算法：對(duì)顯示設(shè)備上每一個(gè)可分辨像素進(jìn)行判斷，看組成物體的多個(gè)多邊形表面中哪一個(gè)在該像素上可見(jiàn)，既要對(duì)每一像素檢查所有的表面。2、客體空間算法：把注意力集

33、中在分析要顯示形體各部分之間的關(guān)系上，這種算法對(duì)每一個(gè)組成形體的表面，都要與其它各表面進(jìn)行比較，以便消去不可見(jiàn)的面或面的不可見(jiàn)部分。*用計(jì)算機(jī)在圖形設(shè)備上生成真實(shí)感圖形必須完成四個(gè)基本的任務(wù)。第一用數(shù)學(xué)方法建立所構(gòu)造三 維場(chǎng)景的幾何描述，并將它們輸入至計(jì)算機(jī)。第二,將三維幾何描述轉(zhuǎn)換為二維透視圖。第三,確定場(chǎng)景中的所有可見(jiàn)面，這需要使用隱藏面消除算法將被其它物體遮擋的不可見(jiàn)面消去。第四 計(jì)算場(chǎng)景中可見(jiàn)面的顏色，嚴(yán)格地說(shuō)，就是根據(jù)基于光學(xué)物理的光照明模型計(jì)算可見(jiàn)面投射到觀察者眼中的光亮度大小和顏色組成，并將它轉(zhuǎn)換成適合圖形設(shè)備的顏色值，從而確定投影畫(huà)面上每一象素的顏色，最終生成圖形。 算法分析&

34、5.簡(jiǎn)單多邊形包含性檢驗(yàn)的算法：1.【準(zhǔn)備】XnX0,yny0,m -1,i02.【排除必不相交情形】若下列條件有一個(gè)成立，則到41)xpx,&xp=xi&xp=xi+13)xpy&ypyi+13.【計(jì)算交點(diǎn)】y=yi+(xp-xi)(yi+1 - yi)/(xi+1 - xi)分兩種情形：1)若y=yp,則P在多邊形邊界(binji)上，算法結(jié)束2)若yyp，則 m(-1)m;4.【結(jié)束(jish)判斷】ii+1，若ifabs(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

35、), (int)(y+0.5);x+=dx;y+=dy;中點(diǎn)畫(huà)線(xiàn)算法void MidpointLine (int x0,int y0,int x1,int y1)int a,b,delta1,delta2,d,x,y ;a = y0 - y1;b = x1 - x0;d = 2 * a + b ;delta1 = 2 * a ;delta2 = 2 *( a + b);x = x0 ;y = y0 ;SetPixel(x,y);while( xx1 )if( d0 ) x +;y +;d+= delta2;else x +;d+= delta1;SetPixel(x,y);Bresenham畫(huà)

36、線(xiàn)算法(sun f)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=0) y+;p+=2*(dy-dx);elsep+=2*dy;四連通內(nèi)定義區(qū)域(qy)的填充算法void Floodfill(int x,int y,COLORREF oldvalue,COLORREF newvalue) if (GetPixel(x,y) = oldvalue) SetPixel(x,y,newvalue);/賦值為新值Floodfill(

37、x,y-1,oldvalue,newvalue);/四向(s xin)擴(kuò)散Floodfill(x,y+1,oldvalue,newvalue);Floodfill(x-1,y,oldvalue,newvalue);Floodfill(x+1,y,oldvalue,newvalue); 掃描線(xiàn)種子(zhng zi)填充算法1對(duì)種子所在像素(xin s)段進(jìn)行填充。2從右至左檢查種子所在行的上一橫行(hngxng)，將查得的像素段依次編號(hào)存入堆棧。接著對(duì)種子所在行的下一橫行同樣處理。 3若堆棧為空則算法結(jié)束，否則從堆棧頂部取出一個(gè)像素段。就以這個(gè)像素為新的種子，返回到1。void Scanline

38、Seedfill(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);/種子像素入棧while(!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;/最右像

39、素x0= x-1;while(GetPixel(x0,y)!=boundaryvalue)/填充左方像素SetPixel(x0 ,y ,newvalue);x0-;xl=x0+1;/最左像素/檢查上一條掃描線(xiàn)和下一條掃描線(xiàn)，/若存在非邊界且未填充的像素，/則選取代表各連續(xù)區(qū)間的種子像素入棧。y0=y;for(int i=1;i=-1;i-=2)x0=xr;y=y0+i; while(x0=xl) flag=0;while(GetPixel(x0,y)!=boundaryvalue)& (GetPixel(x0,y)!=newvalue)& (x0 xl)if(flag=0) flag=1; x

40、id=x0;x0-;if(flag=1)s.push(Point(xid,y); flag=0;while(GetPixel(x0,y)=boundaryvalue)|(GetPixel(x0,y)=newvalue)x0-;/while(x0=xl)/for(int i=1;i=-1;i-=2)/while(!s.isempty() 多邊形的掃描轉(zhuǎn)換算法(sun f)1找出掃描線(xiàn)與多邊形邊界線(xiàn)的所有(suyu)交點(diǎn)；2按x坐標(biāo)增加順序?qū)稽c(diǎn)(jiodin)排序；3在交點(diǎn)對(duì)之間進(jìn)行填充。Cohen算法void Cohen_Sutherland(double x0, y0, x2, y2) in

41、t c, c1, c2; double x, y; makecode(x0, y0,c1); makecode(x2, y2, c2); while (c1!=0 | c2!=0) if (c1&c2!=0) 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) y=y0+(y2-y0)*(xr-x0)/(x2-x0); x=xr;else if (c&4) x=x0+(x2-x0)*(yb-y0)/(y2-y0); y=yb;else if (c&8) x=x0+(x2-x

42、0)*(yt-y0)/(y2-y0); y=yt; if (c=c1) x0=x; y0=y; makecode(x, y, c1); else x2=x; y2=y; makecode(x, y, c2); showline(x0, y0, x2, y2); /顯示可見(jiàn)(kjin)線(xiàn)段 void makecode(double x, y; int c) c=0; if (xxr) c=2; if (yyt) c=c+8;梁友東算法(sun f)void L_Barsky(double x0, y0, x2, y2)double t0, t1, deltax, deltay;t0=0.0; t

43、1=1.0;deltax=x2-x0;if (!cansee(-deltax, x0-x1, t0, t1) return;if (!cansee(deltax, xr-x0, t0, t1) return;deltay=y2-y0;if (!cansee(-deltay, y0-yb, t0, t1) return;if (!cansee(deltay, yt-y0, t0, t1) return;x2=x0+t1*deltax;y2=y0+t1*deltay;x0=x0+t0*deltax;y0=y0+t0*deltay;showline(x0, y0, x2, y2); /顯示可見(jiàn)(kj

44、in)線(xiàn)段bool cansee(double q, d, t0, t1) double r; if (qtl) cansee=false; return; else if (rt0) t0=r; else if (q0) r=d/q; if (rt0) cansee=false; return; else if (rt1) t1=r; else if (d0) cansee=false; return; cansee=true; 裁剪區(qū)域?yàn)槿我?rny)凸多邊形區(qū)域時(shí)的直線(xiàn)段的裁剪算法 第一步 計(jì)算所要裁剪(cijin)的直線(xiàn)段所在直線(xiàn)與凸多邊形區(qū)域的邊界直線(xiàn)段的交點(diǎn)。第二步 當(dāng)交點(diǎn)的個(gè)數(shù)為

45、0或1時(shí)，該直線(xiàn)(zhxin)段處于凸多邊形區(qū)域外 第三步，當(dāng)交點(diǎn)的個(gè)數(shù)為2時(shí)，通過(guò)判斷這兩個(gè)交點(diǎn)與被裁剪的直線(xiàn)段的端點(diǎn)在直線(xiàn)段所處的直線(xiàn)上的關(guān)系來(lái)進(jìn)行裁剪。 1.如果直線(xiàn)段的兩個(gè)端點(diǎn)和兩個(gè)交點(diǎn)剛好全部重合，則顯而易見(jiàn)該直線(xiàn)段完全可見(jiàn)。2.如果直線(xiàn)段的兩個(gè)端點(diǎn)和兩個(gè)交點(diǎn)中有一個(gè)重合，則將重合的點(diǎn)視為一點(diǎn)，則將重合點(diǎn)與另外的一個(gè)端點(diǎn)、一個(gè)交點(diǎn)按在直線(xiàn)上的順序排列。根據(jù)排列的順序有如下三種情況： 如果重合點(diǎn)和交點(diǎn)不相鄰，則直線(xiàn)段完全可見(jiàn)；如果重合點(diǎn)與交點(diǎn)相鄰，且該交點(diǎn)與另一個(gè)端點(diǎn)相鄰，則直線(xiàn)段部分可見(jiàn)，且可見(jiàn)部分為重合點(diǎn)與另一個(gè)交點(diǎn)確定的直線(xiàn)段，它的可見(jiàn)部分為直線(xiàn)段；如果重合點(diǎn)與交點(diǎn)相鄰，且該交點(diǎn)

46、與另一個(gè)端點(diǎn)不相鄰，則直線(xiàn)段完全不可見(jiàn)。 如果直線(xiàn)段的兩個(gè)端點(diǎn)和兩個(gè)交點(diǎn)都不重合。將這四個(gè)點(diǎn)按在直線(xiàn)上的順序排列，根據(jù)排列的順序有如下四種情況：如果兩個(gè)端點(diǎn)和兩個(gè)交點(diǎn)分別相鄰，則直線(xiàn)段完全不可見(jiàn)；如果兩個(gè)端點(diǎn)在兩個(gè)交點(diǎn)之間，則直線(xiàn)段完全可見(jiàn)；如果兩個(gè)交點(diǎn)在兩個(gè)端點(diǎn)之間，則直線(xiàn)段部分可見(jiàn)，且可見(jiàn)部分為兩個(gè)交點(diǎn)決定的直線(xiàn)段，它的可見(jiàn)部分為直線(xiàn)段；如果交點(diǎn)和端點(diǎn)的排列順序是交錯(cuò)的，則直線(xiàn)段部分可見(jiàn)，且可見(jiàn)部分為中間的一個(gè)交點(diǎn)和一個(gè)端點(diǎn)決定的直線(xiàn)段，它的可見(jiàn)部分為直線(xiàn)段 。 兩線(xiàn)段AB和CD交點(diǎn)的算法 1.計(jì)算行列式A (xb-xa)(yc-yd)-(xc-xd)(yb-ya)若 A =0,則兩線(xiàn)段重

47、合或平行,可算做無(wú)交點(diǎn),算法結(jié)束;2.計(jì)算交點(diǎn)參數(shù)B (xc-xa)(yc-yd)-(xc-xd)(yc-ya)/ 若B 1,則無(wú)交點(diǎn),算法結(jié)束;C(xb-xa)(yc-ya)-(xc-xa)(yb-ya)/ 若C 1,則無(wú)交點(diǎn),算法結(jié)束;3.計(jì)算交點(diǎn)xxa+ B (xb-xa),yya+ B(yb-ya),輸出交點(diǎn)(x,y)后算法結(jié)束;多條線(xiàn)段求交遇見(jiàn)某條線(xiàn)段S的左端點(diǎn),此時(shí)S應(yīng)加入次序關(guān)系。2遇見(jiàn)某線(xiàn)段S的右端點(diǎn),此時(shí)S應(yīng)從次序關(guān)系中刪除。3遇到某兩條線(xiàn)段S1和S2 的交點(diǎn),這時(shí)在次序關(guān)系中S1和S2交換位置。*$8深度暗示技術(shù)首先(shuxin)，再投影坐標(biāo)系中定義兩個(gè)(lin )平面Z

48、=Zf,Z=Zb,分別為前參考面和后參考面，并賦予比例因子Sf和Sb(Sf,Sb(-0,1)。給定物體上一點(diǎn)的深度值Z0,該點(diǎn)對(duì)應(yīng)的比例因子S0這樣來(lái)確定1)當(dāng)Z0Zf時(shí)，取S0=Sf 2)當(dāng)Z0Zb時(shí)，取S0=Sb 3)當(dāng)Z0(- Zb,Zf時(shí)，S0=Sb+(Sf-Sb)/(Zf-Zb)*(Z0-Zb)原亮度I按比例S0與亮度Idc混合，目的是活的最終用于顯示(xinsh)的亮度I,Idc由用戶(hù)指定：I=S0I+(1-S0)Idc 若取Sf=1,Sb=0,Idc=0,則當(dāng)物體位于前參考面之前時(shí)，I=I.即亮度沒(méi)有被衰減；當(dāng)物體位于后參考面之后，I=Idc=0，即亮度被衰減為0，else I=

49、S0I,亮度被部分衰減。*Phong方法繪制多邊形步驟計(jì)算多邊形的單位法向量計(jì)算多邊形頂點(diǎn)的單位法向量。再掃描線(xiàn)消隱算法中，對(duì)多邊形頂點(diǎn)的法向量進(jìn)行雙線(xiàn)性插值，計(jì)算出多邊形內(nèi)部各點(diǎn)法向量當(dāng)掃描線(xiàn)y遞增一個(gè)單位，變?yōu)閥+1時(shí)，Na,Nb的增量分別為Na,Nb當(dāng)x遞增一個(gè)單位時(shí)Np增量為Np利用光照模型計(jì)算P點(diǎn)的顏色Bresenham繪制橢圓算法如下：void BresenhamEllipse(int a,int b)int x,y,p;/下面繪制第 eq oac(,1)部分x=0;y=b;p=2b2+a2(1-2b);while (b2x=0)p+=4a2(1-y)+b2(4x+6);y-;el

50、sep+= b2(4x+6);x+;/下面繪制第 eq oac(,2)部分x=a;y=0;p=2a2+b2(1-2a);while (b2xa2y)SetPixel(x,y);if(p=0)p+=4b2(1-x)+a2(4y+6);x-;elsep+= a2(4y+6);y+;以上算法只是繪制出了1/4橢圓，只需在算法中繪制點(diǎn)的部分，將橢圓對(duì)稱(chēng)的其它三個(gè)部分：(-x,y)，(x,-y)，(-x,-y)也繪制出來(lái)就是全部的橢圓。作為算法寫(xiě)到以上這一步就可以了。下面給出使用Bresenham繪制橢圓的可執(zhí)行的C+函數(shù)代碼，該函數(shù)考慮了可以任意指定(zhdng)橢圓中心位置和長(zhǎng)短軸大小，并且可以設(shè)定

51、橢圓的顏色。void BresenhamEllipse(int a,int b,int x0,int y0,COLORREF color,CDC* dc)/參數(shù)(cnsh)a為長(zhǎng)軸，b為短軸，x0，y0為橢圓中心，color為橢圓的顏色，dc為繪圖設(shè)備指針int x,y,p;int aa=a*a,bb=b*b;/因?yàn)楹竺娲罅渴褂?shyng)了a*a和b*b，所以這里先計(jì)算出來(lái)/下面繪制第 eq oac(,1)部分x=0;y=b;p=2*bb+aa*(1-2*b);while (bb*xSetPixel(x+x0,y+y0,color);dc-SetPixel(-x+x0,y+y0,color

52、);dc-SetPixel(x+x0,-y+y0,color);dc-SetPixel(-x+x0,-y+y0,color);if(p=0)p+=4*aa*(1-y)+bb*(4*x+6);y-;elsep+= bb*(4*x+6);x+;/下面繪制第 eq oac(,2)部分x=a;y=0;p=2*aa+bb*(1-2*a);while (bb*xaa*y)dc-SetPixel(x+x0,y+y0,color);dc-SetPixel(-x+x0,y+y0,color);dc-SetPixel(x+x0,-y+y0,color);dc-SetPixel(-x+x0,-y+y0,color)

53、;if(p=0)p+=4*bb*(1-x)+aa*(4*y+6);x-;elsep+= aa*(4*y+6);y+;DDA直線(xiàn)(zhxin)掃描轉(zhuǎn)換算法 void DDALine(int x1,int 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;中點(diǎn)畫(huà)(din hu)線(xiàn)算法v

54、oid MidpointLine (int x0,int y0,int x1,int y1)int a,b,delta1,delta2,d,x,y ;a = y0 - y1;b = x1 - x0;d = 2 * a + b ;delta1 = 2 * a ;delta2 = 2 *( a + b);x = x0 ;y = y0 ;SetPixel(x,y);while( xx1 )if( d0 ) x +;y +;d+= delta2;else x +;d+= delta1;SetPixel(x,y);Bresenham畫(huà)線(xiàn)算法(sun f)void BresenhamLine(int x1

55、,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=0) y+;p+=2*(dy-dx);elsep+=2*dy;四連通內(nèi)定義區(qū)域的填充(tinchng)算法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);/四向(s

56、 xin)擴(kuò)散Floodfill(x,y+1,oldvalue,newvalue);Floodfill(x-1,y,oldvalue,newvalue);Floodfill(x+1,y,oldvalue,newvalue); 掃描線(xiàn)種子填充算法1對(duì)種子所在像素段進(jìn)行填充。2從右至左檢查種子所在行的上一橫行，將查得的像素段依次編號(hào)存入堆棧。接著對(duì)種子所在行的下一橫行同樣處理。 3若堆棧為空則算法結(jié)束，否則從堆棧頂部取出一個(gè)像素段。就以這個(gè)像素為新的種子，返回到1。void ScanlineSeedfill(int x,int y,COLORREF boundaryvalue,COLORREF n

57、ewvalue)int x0,xl,xr,y0,xid;int flag;Stack s; Point p;s.push(Point(x,y);/種子(zhng zi)像素入棧while(!s.isempty()p=s.pop(); /棧頂像素(xin s)出棧x=p.x;y=p.y;SetPixel(x ,y ,newvalue); x0= x+1;while(GetPixel(x0,y)!=boundaryvalue)/填充(tinchng)右方像素SetPixel(x0 ,y ,newvalue);x0+;xr=x0-1;/最右像素x0= x-1;while(GetPixel(x0,y)

58、!=boundaryvalue)/填充左方像素SetPixel(x0 ,y ,newvalue);x0-;xl=x0+1;/最左像素/檢查上一條掃描線(xiàn)和下一條掃描線(xiàn)，/若存在非邊界且未填充的像素，/則選取代表各連續(xù)區(qū)間的種子像素入棧。y0=y;for(int i=1;i=-1;i-=2)x0=xr;y=y0+i; while(x0=xl) flag=0;while(GetPixel(x0,y)!=boundaryvalue)& (GetPixel(x0,y)!=newvalue)& (x0 xl)if(flag=0) flag=1; xid=x0;x0-;if(flag=1)s.push(Po

59、int(xid,y); flag=0;while(GetPixel(x0,y)=boundaryvalue)|(GetPixel(x0,y)=newvalue)x0-;/while(x0=xl)/for(int i=1;i=-1;i-=2)/while(!s.isempty() 多邊形的掃描轉(zhuǎn)換算法(sun f)1找出掃描線(xiàn)與多邊形邊界線(xiàn)的所有(suyu)交點(diǎn)；2按x坐標(biāo)(zubio)增加順序?qū)稽c(diǎn)排序；3在交點(diǎn)對(duì)之間進(jìn)行填充。Cohen算法void Cohen_Sutherland(double x0, y0, x2, y2) int c, c1, c2; double x, y; make

60、code(x0, y0,c1); makecode(x2, y2, c2); while (c1!=0 | c2!=0) if (c1&c2!=0) 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) y=y0+(y2-y0)*(xr-x0)/(x2-x0); x=xr;else if (c&4) x=x0+(x2-x0)*(yb-y0)/(y2-y0); y=yb;else if (c&8) x=x0+(x2-x0)*(yt-y0)/(y2-y0); y=yt; if (