實驗5 計算機圖形學 實驗報告

1、實驗5實驗報告格式計算機圖形學實驗5實驗報告xxxxxx xxx xxxxxxx實驗題目：多邊形裁剪與填充實驗內容：1 閱讀理解提供的參考資料。2編寫并調通一個多邊形裁剪的java程序。3編寫并調通一個多邊形填充的java程序。參考資料：1 fillPolygon.java 2 clipSC2.java2變換與剪裁.ppt3多邊形的填充.ppt基本概念：（詳細敘述自己對實驗內容的理解）變換與裁剪基本概念的理解：矢量：矢量是一個n元組，在坐標系中它對應于n維空間的一個點，這個點 可以代表物體在空間的位置，也可以代表其運動狀態(tài)等。模型坐標系（局部坐標系）：當構造單個對象的數(shù)字模型時，為了方便,可以

2、將其置于一個特定的坐標系下，即模型坐標系或局部坐標系.世界坐標系：為描述圖形場景中所有圖形之間的空間關系，將它們置于一個統(tǒng)一的坐標系中，該坐標系被稱為世界坐標系。標準化設備坐標系：有些圖形系統(tǒng)，對設備坐標系進行了規(guī)范化，將坐標范圍限定在區(qū)間x,y,z | 0x1, 0y1, 0z1內，稱標準化設備坐標系投影: 三維空間中的對象要在二維的屏幕或圖紙上顯示出來，就必須通過投影。投影的方法有兩種，平行投影和透視投影。視區(qū)：在屏幕或繪圖紙上定義一個矩形，稱為視區(qū)，也稱為視口,窗口內的景物在視區(qū)中顯示。平移：點(x,y,z)由點(x, y, z)在x, y和z軸方向分別移動距離x, y和z得到。兩點坐標

3、間的關系為 x=x+x y=y+y (4.1) z=z+z放大和縮小以原點為中心的縮放：設點(x, y, z)經縮放變換后得點(x,y,z)。兩點坐標間的關系為其中sx,sy和sz 分別為沿x, y和z軸方向放縮的比例。其矩陣形式是圖形模式：矩陣合并時，先調用的矩陣放在右邊，后調用的矩陣放在左邊.也稱為固定坐標系模式。這種模式的特點是每一次變換均可看成相對于原始坐標系執(zhí)行的?？臻g模式：又稱活動坐標系模式。先調用的矩陣放在左邊，后調用的矩陣放在右邊,連續(xù)執(zhí)行幾次變換時，每一次變換均可看成是在上一次變換形成的新坐標系中進行的。多邊形的填充：多邊形的表示方法：1）頂點表示是用多邊形的頂點的序列來描述

4、多邊形，該表示幾何意義強、占內存少，但它不能直觀地說明哪些像素在多邊形內。2）點陣表示是用位于多邊形內的象素的集合來刻劃多邊形，該方法雖然沒有多邊形的幾何信息，是面著色所需要的圖像表示形式。區(qū)域是指已經表示成點陣形式的像素集合。在光柵圖形中，區(qū)域可采用內點表示和邊界表示兩種形式進行描述。內點表示法：把位于給定區(qū)域內的所有像素一一列舉出來的方法稱為內點表示法。邊界表示法：把位于給定區(qū)域邊界上的像素一一列舉出來的方法稱為邊界表示法。算法設計：（詳細敘述自己設計的的算法）多邊形裁剪算法分析：基本思想是一次用窗口的一條邊裁剪多邊形，窗口的一條邊以及延長線構成裁剪線，該線把平面分成兩個部分：可見一側，不

5、可見一側。用一條裁剪邊對多邊形進行裁剪，得到一個頂點序列，作為下一條裁剪邊處理過程的輸入點。對于每一條裁剪邊，只是判斷點在窗口的哪一測以及求線段與裁剪邊的交點算法應隨之改變。多邊形裁剪的SutherlandHodgman算法1.SutherlandHodgman多邊形裁剪算法思想該算法的基本思想是每次用窗口的一條邊界及其延長線來裁剪多邊形的各邊。多邊形通常由它的頂點序列來表示，經過裁剪規(guī)則針對某條邊界裁剪后，結果形成新的頂點序列，又留待下條邊界進行裁剪，直到窗口的所有邊界都裁剪完畢，算法形成最后的頂點序列，才是結果多邊形（它可能構成一個或多個多邊形）。當多邊形一個頂點Pi相對于窗口某條邊界及其

6、延長線進行剪裁時，不外乎下列四種情況（即裁剪規(guī)則）：1、頂點Pi在內側，前一頂點Pi-1也在內側，則將Pi納入新的頂點序列；2、頂點Pi在內側，前一頂點Pi-1在外側，則先求交點Q，再將Q、Pi依次納入新的頂點序列；3、頂點Pi在外側，前一頂點Pi-1在內側，則先求交點Q，再將Q納入新的頂點序列；4、頂點Pi與前一頂點Pi-1均在外側，則頂點序列中不增加新的頂點。多邊形填充算法分析：確定多邊形所占有的最大掃描線數(shù)，得到多邊形頂點的最小和最大y值（ymin和ymax），從y=ymin到y(tǒng)=ymax,每次用一條掃描進行填充。對一條掃描線填充的過程可分為四個步驟:a.求交b.排序c.交點配對d.區(qū)間

7、填色。掃描多邊形填充算法的基本原理在直角坐標系中，假設有一條從左至右的掃描線穿過多邊形，從左至右開始計數(shù)，與多邊形交點為奇數(shù)時，開始進入多邊形，與多邊形交點為偶數(shù)時，走出多邊形。這樣在這相鄰配對的奇偶交點間的所有象素都在多邊形內。如圖，奇數(shù)交點a，c，都是入多邊形，偶數(shù)交點b，d都是走出多邊形，相鄰的奇偶交點配對，a，b之間，c，d之間的象素都多邊形內，可見一條掃描線上，與多邊形交點個數(shù)需要為偶數(shù)。依據這樣的思路，掃描線從上到下從左到右依次掃過多邊形即可求得多邊形所占據的象素。（注意退化情況的處理，也就是掃描線剛好經過頂點或者多邊形的邊本身就是水平的情況）bdca掃描多邊形填充的原理代碼：（給

8、出和實驗內容相關的Java程序和注解，不要輔助代碼，否則扣分） /Sutherland_Cohen裁減算法 public void Sutherland_Cohen(Graphics g,float x0,float y0,float x2,float y2) int c1,c2,c; float x,y,wx,wy; boolean accept=false,done=false; c1=code(x0,y0); c2=code(x2,y2); do if (c1|c2)=0)/兩個編碼都為0，表明在窗口內 accept=true; done=true; else if(c1&c2)!=0)

9、done=true;/兩個編碼的某一位為1，則必然在外側顯然在窗口外 else c=c1; if(c=0)c=c2; wx=x2-x0; wy=y2-y0; if (c&8)=8) /求交點 x=x0+wx*(yT-y0)/wy; y=yT; else if (c&4)=4) x=x0+wx*(yB-y0)/wy; y=yB; else if (c&1)=1) y=y0+wy*(xL-x0)/wx; x=xL; else/即(c&2)=2 y=y0+wy*(xR-x0)/wx; x=xR; if (c=c1) /表明c1!=0,起始點不在窗口內，將交點作為新的起點重復判斷步驟； x0=x; y

10、0=y; c1=code(x0,y0); else /終點不在窗口內，交點作為新的終點 x2=x; y2=y; c2=code(x2,y2); /else while (done=false); if(accept)g.drawLine(int)100,(int)150,(int)200,(int)150);=/fillPolygon.java/*定義多邊形單鏈表類activeEdgeListclass activeEdgeList activeEdgeListEntry header=null;/鏈表頭指針activeEdgeListEntry tailer=null;/鏈表尾指針/構造方法

11、public activeEdgeList(activeEdgeListEntry element) header=tailer=element;/指向第一個邊結點/把新結點插入有序排列的多邊形單鏈表public void insert(activeEdgeListEntry element) activeEdgeListEntry sentinel;/當前結點指針if(element=null | this.header=null)/新結點異?；蛘哝湵砜誸hrow new NullPointerException();/出錯，拋出異常sentinel=this.header;/當前指針指向表

12、頭結點int xt=element.topx;/新結點的topxint xtold=sentinel.topx;double oldDelta=sentinel.delta;/當前結點的deltadouble newDelta=element.delta;/* 排序第一關鍵字結點的topx，第二關鍵字結點的delta */* 兩個關鍵字由小到大*/if(xtoldxt)|(xtold=xt)&(oldDeltanewDelta)while(true)/在鏈表頭指針之后尋找新結點element的位置if(sentinel.next=null) /當前位置是表尾sentinel.next=elem

13、ent;/追加到表尾this.tailer=element;break;/結束while循環(huán)activeEdgeListEntry mp=sentinel.next;/下一結點int xmt=mp.topx;double midDelta=mp.delta;if(xmtxt)|(xmt=xt)&(midDeltanewDelta)sentinel=mp;/新結點仍然大于下一結點，當前結點指針后移，繼續(xù)循環(huán)else /否則，新結點就應該插入當前位置sentinel.next=element;element.next=mp;break;/結束while循環(huán)，尾指針不動/結束whileelse /新

14、結點作為單鏈表頭結點sentinel=this.header;this.header=element;element.next=sentinel;/插入新結點結束/把新結點作為多邊形鏈表的頭結點或者尾結點public void append(activeEdgeListEntry element) if(element=null) throw new NullPointerException();if(tailer=null) /如果單鏈表是空tailer=element;header=element;else /否則把新結點作為單鏈表尾結點tailer.next=element;tailer

15、=element;/兩個多邊形單鏈表的合并：自身單鏈表與list單鏈表的合并public activeEdgeList merge(activeEdgeList list,int y) if(list=null) return this;activeEdgeListEntry a=this.header;/自身單鏈表的頭指針activeEdgeListEntry b=list.header;/單鏈表list的頭指針activeEdgeListEntry save=null;/指向鏈表結點的工作指針activeEdgeListEntry anext,bnext;/指向鏈表結點的工作指針activ

16、eEdgeList result=null;/合并結果鏈表while(true) if(a=null&b=null) return result; /兩個空表else if(a=null) /自身為空表if(save!=null) save.next=b;result.tailer=list.tailer;return result; else if(b=null)/list為空表 if(save!=null) save.next=a;result.tailer=this.tailer;return result; /*兩個表都不空*/int xa=(int)(a.topx+(a.topy-y

17、)*a.delta);/自身鏈表int xb=b.topx;/list鏈表頭結點的topxif(xa=xb) /決定合并后兩個表的先后anext=a.next;a.next=null;if(result=null) /結果鏈表為空，則a表在前result=new activeEdgeList(a);save=result.tailer;else result.append(a);/結果鏈表不空，則a表在后save=a;a=anext;else bnext=b.next;b.next=null;if(result=null) /結果鏈表為空，則b表在前result=new activeEdgeL

18、ist(b);save=result.tailer;else result.append(b);/結果鏈表不空，則b表在后save=b;b=bnext; /結束while/單鏈表合并結束/刪除多邊形單鏈表的結點public void remove(activeEdgeListEntry element) activeEdgeListEntry p,q;if(header=element) /要刪除的是頭結點header=element.next;if(tailer=element) tailer=header;return;p=q=header;while(p!=element) q=p;p=

19、p.next;if(p=null) throw new NullPointerException();/查無此結點if(element=tailer) tailer=q;/要刪除的是尾結點q.next=p.next;/要刪除的是非頭尾結點/多邊形單鏈表的相鄰結點public void traverse() activeEdgeListEntry p,q,r,tmp;p=r=header;while(p!=null)q=p.next;if(q=null) break;/到達末尾if(q.xp.x) /多邊形單鏈表相鄰結點的x坐標要由小到大tmp=q.next;/交換兩個結點if(p=header

20、) header=q; else r.next=q;q.next=p;p.next=tmp;r=p;/指向尾結點p=p.next;/下一個結點/結束whiletailer=r;/多邊形單鏈表新的尾指針/結束多邊形單鏈表類/*定義直線類class Line public double x1,y1;public double x2,y2;public Line(double x1,double y1,double x2,double y2) this.x1=x1;this.y1=y1;this.x2=x2;this.y2=y2; /結束直線類/*定義多邊形的填充類*/public class fi

21、llPolygon extends Applet /繼承鼠標事件監(jiān)聽接口implements MouseListener,MouseMotionListener protected MyCanvas m;/定義MyCanvas的對象/掃描行處理用數(shù)據protected activeEdgeListEntry edgeData=null;/邊結點數(shù)組protected activeEdgeList bucket=null;/多邊形單鏈表數(shù)組protected activeEdgeList activeHeader=null;/當前邊單鏈表的頭指針protected int numEdge=5;/

22、多邊形的邊數(shù)/鼠標相關數(shù)據protected boolean isFirstClicked=true;/鼠標最初點擊protected boolean isDoubleClicked=false;/雙擊標志protected boolean isSingleClicked=false;/單擊標志/繪圖區(qū)域protected int width,height;/Applet繪圖區(qū)的大小protected Image image=null;/圖像區(qū)域protected MemoryImageSource mis=null;/內存圖像protected int pixel=null;/內存圖像配色數(shù)

23、組protected int pixelWidth;/圖像寬度protected int pixelHeight;/圖像高度protected int xoffset;/pixel數(shù)據的窗口內顯示偏移量protected int yoffset;protected double leftTopx;/pixel數(shù)據的起始點protected double leftTopy;/多邊形的繪圖數(shù)據protected double x0,y0;/邊的起點protected double lastx,lasty;/邊的終點位置protected double movingx,movingy;/用戶坐標系下

24、一個點的坐標protected int numPoints=0;/頂點計數(shù)器protected boolean isPolygonMode=true;/標志protected Vector lines=new Vector(256,256);/Java的向量類/APPLET程序的初始化public void init()m=new MyCanvas(this);/本APPLET容器的MyCanvas對象addMouseListener(this);/定義鼠標按鈕監(jiān)聽器addMouseMotionListener(this);/定義鼠標按鈕監(jiān)聽器Dimension d=getSize();/本A

25、PPLET容器的大小width=d.width; height=d.height;/成員變量初始化public void initData()isFirstClicked=true;/鼠標最初點擊isPolygonMode=true;/標志描繪多邊形numPoints=0;/多邊形頂點計數(shù)器bucket=new activeEdgeListheight+1;/邊的單鏈表數(shù)組for(int i=0;i0) lines.removeAllElements();/向量類的對象/APPLET程序的繪圖public void paint(Graphics g) if(isFirstClicked) /初

26、始狀態(tài)initData();Font f=m.MyFont(m.getFont().getName(),Font.BOLD+Font.ITALIC,3);m.setFont(f);m.drawString(單擊畫多邊形,-1,0.2);m.drawString(雙擊填充多邊形,-4,-6);m.setBackground(new Color(220,220,220);/背景色m.setColor(Color.black);/前景色for(int i=0;ilines.size();i+) Line l=(Line)lines.elementAt(i);/轉換第i個向量m.drawLine(l.

27、x1,l.y1,l.x2,l.y2);if(isPolygonMode&!isFirstClicked)/畫線m.drawLine(lastx,lasty,movingx,movingy);if(!isPolygonMode)&(image!=null)/填充m.myDrawImage(image,leftTopx,leftTopy,this);/APPLET程序的繪圖/把多邊形頂點數(shù)據生成邊結點public void registerActiveEdgeEntry() numEdge=lines.size();/多邊形邊的數(shù)量edgeData=new activeEdgeListEntryn

28、umEdge;for(int i=0;inumEdge;i+)/每個邊的單鏈表頭結點edgeDatai=new activeEdgeListEntry();/* 四個極值用于確定顯示圖像的大小和范圍 */int LARGE=0x0ffffffff;int xmin=LARGE,xmax=-1,ymin=LARGE,ymax=-1;double dxmin=LARGE,dxmax=-1,dymin=LARGE,dymax=-1;for(int i=0;iiy2) /邊的斜向edgeDatai.isHorizontal=false;edgeDatai.topy=iy1;edgeDatai.topx

29、=ix1;edgeDatai.x=ix1;edgeDatai.boty=iy2;edgeDatai.delta=(double)(-(ix2-ix1)/(iy2-iy1);if(iy2ymax) ymax=iy1;dymax=l.y1;else if(iy1iy2) /邊的斜向edgeDatai.isHorizontal=false;edgeDatai.topy=iy2;edgeDatai.topx=ix2;edgeDatai.x=ix2;edgeDatai.boty=iy1;edgeDatai.delta=(double)(-(ix1-ix2)/(iy1-iy2);if(iy1ymax) y

30、max=iy2;dymax=l.y2;else /水平邊y1=iy2edgeDatai.isHorizontal=true;if(iy1ymax) ymax=iy1;dymax=l.y1;if(ix1ix2) /進行xMin xMax 計算if(ix1xmax) xmax=ix2;dxmax=l.x2;else if(ix2ix1) if(ix2xmax) xmax=ix1;dxmax=l.x1;else /垂直邊ix2=ix1if(ix1xmax) xmax=ix1;dxmax=l.x1;/結束for循環(huán)/*內存圖像的數(shù)組空間及相關數(shù)據*/pixelWidth=xmax-xmin+1;pix

31、elHeight=ymax-ymin+1;pixel=new intpixelWidth*pixelHeight;/圖像的個點顏色for(int k=0;kpixelWidth*pixelHeight;k+)pixelk=0x00000000;/初值透明色xoffset=xmin;yoffset=ymin;leftTopx=dxmin;/用于顯示圖像方法myDrawImage();leftTopy=dymax;/生成邊結點registerActiveEdgeEntry()/多邊形單鏈表數(shù)組bucketd初始化public void bucketSort() for(int i=0;i=0;y-

32、) if(buckety!=null) /該指針元素存在makeActiveEdgeList(buckety,y);/建立該行的邊鏈表processActiveEdgeList(y);/處理該行的邊鏈表else if(activeHeader!=null&activeHeader.header!=null)processActiveEdgeList(y);/處理該行的邊鏈表/結束for循環(huán)/多邊形的掃描轉換/處理給定行的邊鏈表public void processActiveEdgeList(int y) int xleft,xright;double xl,xr;activeEdgeList

33、Entry left=activeHeader.header;activeEdgeListEntry right=left.next;if(right=null) return;while(true) xl=left.x;xr=right.x;xleft=(int)xl;xright=(int)(xr+0.5);if(xleft=y-1 & right.boty=y-1) xleft=(int)left.x;xright=(int)(right.x+0.5);if(xleft=y-1) /將左面的邊從當前鏈表中刪去activeHeader.remove(left);if(right.boty=

34、y-1) /將左面的邊從當前鏈表中刪去activeHeader.remove(right);left=right.next;/選擇當前鏈表中下一對結點if(left=null) break;/到達鏈表末尾,退出循環(huán)right=left.next;if(right=null)/邊鏈表的結點數(shù)一定為偶數(shù)throw new NullPointerException();/出錯/結束whileactiveHeader.traverse();/邊封閉后,重新整理單鏈表/處理給定行的邊鏈表/建立指定行的邊鏈表public void makeActiveEdgeList(activeEdgeList lis

35、t,int y) if(activeHeader=null)activeHeader=list;/指定為當前單鏈表else/把list與當前單鏈表合并activeHeader=activeHeader.merge(list,y);/填充何種圖案public boolean isTilePattern(int i,int j) if( i%8=0 | j%8=0 | i%8=1 | j%8=1 |i%8=2 | j%8=2 ) return true;/ 填充圖案1return false;/ 填充圖案2/設定像素顏色public void putPixel(int i,int j) int r

36、,g,b;if(isTilePattern(i,j)r=g=b=0;/黑色else r=(int)(Math.random()*255);/0到255之間的隨機數(shù)g=(int)(Math.random()*255);b=(int)(Math.random()*255);int a=0xff000000|(r16)|(g8)|b;/像素顏色/*圖像的i行j列處的顏色*/pixel(pixelHeight-1-(j-yoffset)*pixelWidth+(i-xoffset)=a;/填充指定行的像素列public void fillScanline(int xleft,int xright,in

37、t y) for(int x=xleft;x=2) /雙擊，添加多邊形的頂點isDoubleClicked=true;/標記/* 給光柵向量表增加一行，這個向量成員方法導致編譯要加上參數(shù)-Xlint，會出現(xiàn)警告錯誤*/lines.addElement(new Line(lastx,lasty,x0,y0);isPolygonMode=false;scanLineFillPolygon();/多邊形填充總控程序if(numEdge2) /內存圖像生成mis=new MemoryImageSource(pixelWidth,pixelHeight,pixel,0,pixelWidth);image

38、=createImage(mis);else /單擊，準備開始if(isFirstClicked) /初次點擊isFirstClicked=false;/*先按照Jawa AWT坐標ix iy得到視圖索引號，再由視圖反向轉換得到用戶坐標系下的lastx lasty*/lastx=x0=m.getUserX(ix,m.getViewport(ix,iy);lasty=y0=m.getUserY(iy,m.getViewport(iy,iy);movingx=lastx; movingy=lasty;else /非初次點擊/*ix iy所對應的用戶坐標系下的坐標*/x=m.getUserX(ix,m.getViewport(ix,iy);y=m.getUserY(iy,m.getViewport(iy,iy);/* 給光柵向量表增加一行 */lines.addElement(new Line(lastx,lasty,x,y);lastx=x; lasty=y;numPoints+;repaint();/paint繪圖/結束if(isPolygonMode)語句/響應鼠標擊鍵事件/響應鼠標移動事件public void mouseMoved(