計(jì)算機(jī)圖形學(xué)第3章-基本光柵圖形生成算法(參考版)
2025-05-03 12:01本頁面
【正文】 由于要計(jì)算面積，使得計(jì)算量大大增加，速度也由此而減慢，所以它 不適合于動(dòng)態(tài)的交互式圖形顯示 。反混淆線段是將位于原相鄰階梯之間的象素置為 過渡顏色 或 灰度 ，使得顏色或者灰度過渡自然，變化柔和，階梯被淡化后，線形就顯得平直了。求平均值時(shí)可取算術(shù)平均，也可取加權(quán)平均。 高分辨率計(jì)算 ：將低分辨的圖形顯示象素劃分為許多子象素 ，如 2 2劃分 ， 3 3劃分等 ， 然后按通常的算法計(jì)算出各個(gè)子象素的顏色值或灰度值 。 ? 采用 軟件 : 花費(fèi)的代價(jià)小 ， 也容易實(shí)現(xiàn) 。 步驟 4：在與當(dāng)前掃描線相鄰的上下兩條掃描線上 ， 以區(qū)間 [xleft,xright]為搜索范圍 ， 求出需要填充的各小區(qū)間 ， 把各小區(qū)間中最右邊的點(diǎn)并作為種子點(diǎn)壓入堆棧 ， 轉(zhuǎn)到步驟 2。 步驟 3：從種子點(diǎn)（ x, y）開始，沿縱坐標(biāo)為 y的當(dāng)前掃描線向左右兩個(gè)方向逐個(gè)像素用新的顏色值進(jìn)行填充，直到邊界為止。將給定的種子點(diǎn)（ x, y）壓入堆棧。 圖 的八連通區(qū)域 圖 圖 八連通區(qū)域的不同邊界 基本思想： 給定區(qū)域 G一種子點(diǎn)（ x, y）首先判斷該點(diǎn)是否是區(qū)域內(nèi)的一點(diǎn)，如果是，則將該點(diǎn)填充為新的顏色，然后將該點(diǎn)周圍的四個(gè)點(diǎn)（四連通）或八個(gè)點(diǎn)（八連通）作為新的種子點(diǎn)進(jìn)行同樣的處理，通過這種擴(kuò)散完成對(duì)整個(gè)區(qū)域的填充 基本思想： 首先填充當(dāng)前掃描線上的位于給定區(qū)域內(nèi)的一區(qū)段，然后確定與這一區(qū)段相鄰的上下兩條掃描線上位于區(qū)域內(nèi)的區(qū)段，并依次把它們保存起來。號(hào)的象素組成的區(qū)域作為 4連通區(qū)域，則其邊界由圖中的標(biāo)有 △ 號(hào)的象素組成。 圖 運(yùn)動(dòng) 4連通區(qū)域也可理解成 8連通區(qū)域，但是兩者的邊界 不盡相同 。 圖 圖 4連通的區(qū)域 : 取區(qū)域內(nèi)任意兩點(diǎn) ， 在該區(qū)域內(nèi)若從其中一點(diǎn)出發(fā)通過上 、 下 、 左 、右四種運(yùn)動(dòng)可到達(dá)另一點(diǎn) 。 ?內(nèi)點(diǎn)表示法：把位于給定區(qū)域內(nèi)的所有像素一一列舉出來的方法稱為內(nèi)點(diǎn)表示法。對(duì)每一條掃描線從左到右進(jìn)行搜索，如果當(dāng)前是像素位于 多邊形內(nèi) ，則interior_point=true，需要填上值為 polygon_color的顏色；否則該像素在 多邊形外 ，需要填上值 background_color的顏色 區(qū)域 是指已經(jīng)表示成點(diǎn)陣形式的像素集合在光柵圖形中，區(qū)域可采用內(nèi)點(diǎn)表示和邊界表示兩種形式進(jìn)行描述。每一條掃描線上著上這種特殊顏色的點(diǎn)的個(gè)數(shù)必定是偶數(shù) (包括零 )。然后再把位于 多邊形 內(nèi)的各個(gè)像素著上所需的顏色 ?步驟 1：以值為 boundarycolor 的特殊顏色勾畫 多邊形的邊界。 ? 算法實(shí)現(xiàn) ： ?對(duì) 多邊形 P的每一非水平邊（ i=0,1,… ,n）上的各像素做 向右求反 運(yùn)算即可， 見下圖， 其中 (a)為給定的多邊形； (b)為對(duì)區(qū)域賦初值； (c)， (d)， (e)和 (f)表示逐邊向右求反。 ?對(duì)于仍留在 AET表中的每個(gè)記錄，用 xi+1/m代替 xi進(jìn)行修改，這就是該記錄的邊線與下一條掃描線 yj+1的交點(diǎn)。 ?依次取出 AET表各記錄中的 xi坐標(biāo)值，兩兩配對(duì)填充，即將每對(duì) xi之間的象素填上所要求的顏色。 對(duì)于循環(huán)變量 yj的每一整數(shù)值，重復(fù)作以下事情，直到 yj大于 ymax，或 ET表與 AET表都為空為止： ?如果 ET表中 yj桶非空，則將 yj桶中的全部記錄合并到 AET表中。 ? 初始化 AET表指針，使它為空。對(duì)不同的掃描線，與之相交的邊線也是不同的，當(dāng)對(duì)某一條掃描線進(jìn)行掃描轉(zhuǎn)換時(shí)，我們只需要考慮與它相交的那些邊線，為此需要建立一個(gè)只與當(dāng)前掃描線相交的邊記錄鏈表，稱之為活動(dòng)邊表。 ? 第四項(xiàng)：指針。 ? 第二項(xiàng)：某邊的最小的 y對(duì)應(yīng)的 x值。邊的記錄定義為： ? 第一項(xiàng)：某邊的最大 y值（ ymax）。 (a)掃描線的相關(guān)性 (b)邊的相關(guān)性 ? 數(shù)據(jù)結(jié)構(gòu) ? 邊相關(guān)掃描線填充算法的實(shí)現(xiàn)需要建立兩個(gè)表：邊表（ ET）和活動(dòng)邊表（ AET）。對(duì)同一條邊，前一條掃描線 yi與該邊的交點(diǎn)為 xi，而后一條掃描線yi+1=yi+1與該邊的交點(diǎn)則為 xi+1=xi+1/m，利用這種相關(guān)性可以省去大量的求交運(yùn)算。見下圖 (a)。 ?該算法利用了掃描線的相關(guān)性和多邊形邊的相關(guān)性，而不是逐點(diǎn)進(jìn)行處理。它割斷了各象素之間的聯(lián)系，孤立地考慮問題，由于要對(duì)每個(gè)象素進(jìn)行多次求交運(yùn)算，求交時(shí)要做大量的乘除運(yùn)算，從而影響了填充速度。 ?如果個(gè)數(shù)為奇數(shù)：該點(diǎn)置為填充色。 ?對(duì)包圍盒中的每個(gè)象素
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1