实验报告5 多边形裁剪与填充.docx
- 文档编号:16501565
- 上传时间:2023-07-14
- 格式:DOCX
- 页数:28
- 大小:107.92KB
实验报告5 多边形裁剪与填充.docx
《实验报告5 多边形裁剪与填充.docx》由会员分享,可在线阅读,更多相关《实验报告5 多边形裁剪与填充.docx(28页珍藏版)》请在冰点文库上搜索。
实验报告5多边形裁剪与填充
《计算机图形学》实验5实验报告
实验题目:
多边形裁剪与填充
实验内容:
1阅读理解提供的参考资料。
2编写并调通一个多边形裁剪的java程序。
3编写并调通一个多边形填充的java程序。
参考资料:
1fillPolygon.java
2clipSC2.java
3变换与剪裁.ppt
4多边形的填充.ppt
基本概念:
1变换与裁剪:
(1)计算机处理图形的过程一般分为三个阶段:
①图形的数字化;②图形操作;③图形输出。
(2)模型坐标系(局部坐标系):
当构造单个对象的数字模型时,为了方便,可以将其置一个特定的坐标系下,即模型坐标系或局部坐标系。
(3)世界坐标系:
为描述图形场景中所有图形之间的空间关系,将它们置于一个统一的坐标系中,该坐标系被称为世界坐标系。
(4)设备坐标系:
要输出经过处理后的数字化图形,需要在输出设备上建立一个坐标系,称为设备坐标系。
(5)标准化设备坐标系:
有些图形系统,对设备坐标系进行了规范化,将坐标范围限定在区间
{x,y,z|0≤x≤1,0≤y≤1,0≤z≤1}
内,称标准化设备坐标系。
(6)三维图形的显示流程图
(7)裁剪
裁剪作用:
选择显示的内容--图形在窗口内的部分被显示出来,窗口外的部分被裁剪掉。
图形中每个基本元素都要经过裁剪,因此裁剪直接影响整个图形系统的效率。
裁剪类型:
二维裁剪、三维裁剪
裁剪窗口:
矩形,凸多边形,任意多边形
视见体:
棱台、立方体
裁剪对象:
直线段、多边形、文字等
2多边形的填充:
(1)多边形的填充指在给定区域填上所需要的颜色,就是把多边形的顶点表示转换为点阵表示,即从多边形的给定边界出发,求出位于其内部的各个像素,并将帧缓冲器内的各个对应元素设置相应的灰度或颜色。
(2)多边形的表示:
1)顶点表示是用多边形的顶点的序列来描述多边形,该表示几何意义强、占内存少,但它不能直观地说明哪些像素在多边形内。
2)点阵表示是用位于多边形内的象素的集合来刻划多边形,该方法虽然没有多边形的几何信息,是面着色所需要的图像表示形式。
算法设计:
1多边形的裁剪:
Sutherland-Cohen算法:
基本思想:
对于每条线段P1P2分为三种情况处理。
(1)若P1P2完全在窗口内,则显示该线段P1P2简称“取”之。
(2)若P1P2明显在窗口外,则丢弃该线段,简称“弃”之。
(3)若线段既不满足“取”的条件,也不满足“弃”的条件,则在交点处把线段分为两段。
其中一段完全在窗口外,可弃之。
然后对另一段重复上述处理。
具体操作:
分为两步
第一步是判定:
1)完全在窗口内的直线段,称为完全可见的线段;
2)完全在窗口外的线段,称为完全不可见线段。
第二步处理不能断定为完全可见或完全不可见的线段。
这时需要计算出直线段和窗口边界的一个交点,这个交点把直线分成两段,其中一条为完全不可见的线段,被抛弃。
对余下部分再作第一步的判断,重复上述过程,直到直线段余下的部分可用第一步的判断得出肯定的结论为止。
2多边形的填充:
(1)多边形填充的扫描线算法
a.令y=c为一个常数,扫描整个多边形的边,记录横坐标为xi记为序列1.
b.设d为一整数,d=c–1,且yi0≥y≥yin;设位于扫描线y=d上的交点序列为,记为序列2。
c.奇点的处理:
多边形P的顶点可分为两类:
极值点和非极值点。
如果
,
称顶点Pi为极值点(P1,P2,P3,P5,P6,P8);否则称Pi为非极值点(P0,P4,P7)。
若扫描线与多边形相交于多边形的顶点,则该交点(顶点)称为奇点。
为了使交点个数保持为偶数,规定当奇点是P的极值点时,该点按两个交点计算;否则按一个交点计算。
(2)边缘填充算法:
对多边形P的每一非水平边上的各像素做向右求反运算即可。
步骤:
a.以值为boundary-color的特殊颜色勾画多边形P的边界。
设多边形顶点为Pi=(xi,yi),0≤i≤n,xi,yi均为整数;置Pn+1=P0。
每一条扫描线上着上这种特殊颜色的点的个数必定是偶数(包括零)。
b.设interior_point是一布尔变量。
对每一条扫描线从左到右进行搜索,如果当前是像素位于多边形P内,则interior_point=true,需要填上值为polygon_color的颜色;否则该像素在多边形P外,需要填上值为background_color的颜色。
(3)区域填充:
a.区域是指已经表示成点阵形式的像素集合。
在光栅图形中,区域可采用内点表示和边界表示两种形式进行描述。
内点表示法:
把位于给定区域内的所有像素一一列举出来的方法称为内点表示法。
边界表示法:
把位于给定区域边界上的像素一一列举出来的方法称为边界表示法。
b.区域的连通性:
1)连通的区域:
取区域内任意两点,在该区域内若从其中一点出发通过上、下、左\右四种运动可到达另一点。
2)连通的区域:
取区域内任意两点,若从其中任一点出发,在该区域内通过沿水平方向、垂直方向和对角线方向的八种运动可到达另一点。
(4)扫描线种子填充算法:
从给定的种子点开始,填充当前扫描线上种子点所在的一区段,然后确定与这一段相邻的上下两条扫描线上位于区域内的区段(需要填充的区间),从这些区间上各取一个种子点依次把它们存起来,作为下次填充的种子点。
反复进行这过程,直到所保存的各区段都填充完毕。
步骤:
a.(初始化)将算法设置的堆栈置为空。
将给定的种子点(x,y)压入堆栈
b.(出栈)如果堆栈为空,算法结束;否则取栈顶元素(x,y)作为种子点
c.(区段填充)从种子点(x,y)开始,沿纵坐标为y的当前扫描线向左右两个方向逐个像素
用新的颜色值进行填充,直到边界为止即象素颜色等于边界色。
设区间两边界的横坐标分别
为xleft和xright。
d.在与当前扫描线相邻的上下两条扫描线上,以区间[xleft,xright]为搜索范围,求出需要填
充的各小区间,把各小区间中最右边的点并作为种子点压入堆栈,转到步骤2。
代码:
1多边形的裁剪:
publicintcode(floatx,floaty)
{
intc=0;
if(x elseif(x>xR)c=c|2; if(y elseif(y>yT)c=c|8; returnc;//二进制分别为01101001000 } //Sutherland_Cohen裁减算法 publicvoidSutherland_Cohen(Graphicsg,floatx0,floaty0,floatx2,floaty2) { intc1,c2,c; floatx,y,wx,wy; booleanaccept=false,done=false; c1=code(x0,y0); c2=code(x2,y2); do{ if((c1|c2)==0)//两个编码都为0,表明在窗口内 { accept=true; done=true; } elseif((c1&c2)! =0)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; } elseif((c&4)==4) { x=x0+wx*(yB-y0)/wy; y=yB; } elseif((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; y0=y; c1=code(x0,y0); }else//终点不在窗口内,交点作为新的终点 { x2=x; y2=y; c2=code(x2,y2); } }//else }while(done==false); if(accept)g.drawLine((int)x0,(int)y0,(int)x2,(int)y2); } 2多边形的填充: classactiveEdgeList{ activeEdgeListEntryheader=null; activeEdgeListEntrytailer=null; publicactiveEdgeList(activeEdgeListEntryelement){ header=tailer=element;//指向第一个边结点 } //把新结点插入有序排列的多边形单链表 publicvoidinsert(activeEdgeListEntryelement){ activeEdgeListEntrysentinel; if(element==null||this.header==null)//新结点异常或者链表空 thrownewNullPointerException();//出错,抛出异常 sentinel=this.header;//当前指针指向表头结点 intxt=element.topx;//新结点的topx intxtold=sentinel.topx; doubleoldDelta=sentinel.delta;//当前结点的delta doublenewDelta=element.delta; /*排序第一关键字结点的topx,第二关键字结点的delta*/ /*两个关键字由小到大*/ if((xtold while(true){//在链表头指针之后寻找新结点element的位置 if(sentinel.next==null){ sentinel.next=element;//追加到表尾 this.tailer=element; break;//结束while循环 } activeEdgeListEntrymp=sentinel.next;//下一结点 intxmt=mp.topx; doublemidDelta=mp.delta; if((xmt sentinel=mp;//新结点仍然大于下一结点,当前结点指针后移,继续循环 } else{//否则,新结点就应该插入当前位置 sentinel.next=element; element.next=mp; break;//结束while循环,尾指针不动 } } } else{//新结点作为单链表头结点 sentinel=this.header; this.header=element; element.next=sentinel; } }//插入新结点结束 //把新结点作为多边形链表的头结点或者尾结点 publicvoidappend(activeEdgeListEntryelement){ if(element==null)thrownewNullPointerException(); if(tailer==null){//如果单链表是空 tailer=element;header=element; } else{//否则把新结点作为单链表尾结点 tailer.next=element;tailer=element; } } //两个多边形单链表的合并: 自身单链表与list单链表的合并 publicactiveEdgeListmerge(activeEdgeListlist,inty){ if(list==null)returnthis; activeEdgeListEntrya=this.header;//自身单链表的头指针 activeEdgeListEntryb=list.header;//单链表list的头指针 activeEdgeListEntrysave=null;//指向链表结点的工作指针 activeEdgeListEntryanext,bnext;//指向链表结点的工作指针 activeEdgeListresult=null;//合并结果链表 while(true){ if(a==null&&b==null)returnresult;//两个空表 elseif(a==null){//自身为空表 if(save! =null){ save.next=b; result.tailer=list.tailer; returnresult; } } elseif(b==null){//list为空表 if(save! =null){ save.next=a; result.tailer=this.tailer; returnresult; } } /*两个表都不空*/ intxa=(int)(a.topx+(a.topy-y)*a.delta);//自身链表 intxb=b.topx;//list链表头结点的topx if(xa<=xb){//决定合并后两个表的先后 anext=a.next; a.next=null; if(result==null){//结果链表为空,则a表在前 result=newactiveEdgeList(a); save=result.tailer; } elseresult.append(a);//结果链表不空,则a表在后 save=a; a=anext; } else{ bnext=b.next; b.next=null; if(result==null){//结果链表为空,则b表在前 result=newactiveEdgeList(b); save=result.tailer; } elseresult.append(b);//结果链表不空,则b表在后 save=b; b=bnext; } }//结束while }//单链表合并结束 //删除多边形单链表的结点 publicvoidremove(activeEdgeListEntryelement){ activeEdgeListEntryp,q; if(header==element){//要删除的是头结点 header=element.next; if(tailer==element)tailer=header; return; } p=q=header; while(p! =element){ q=p;p=p.next; if(p==null)thrownewNullPointerException();//查无此结点 } if(element==tailer)tailer=q;//要删除的是尾结点 q.next=p.next;//要删除的是非头尾结点 } //多边形单链表的相邻结点 publicvoidtraverse(){ activeEdgeListEntryp,q,r,tmp; p=r=header; while(p! =null){ q=p.next; if(q==null)break;//到达末尾 if(q.x tmp=q.next;//交换两个结点 if(p==header)header=q;elser.next=q; q.next=p; p.next=tmp; } r=p;//指向尾结点 p=p.next;//下一个结点 }//结束while tailer=r;//多边形单链表新的尾指针 } }//结束多边形单链表类 //*****定义直线类 classLine{ publicdoublex1,y1; publicdoublex2,y2; publicLine(doublex1,doubley1,doublex2,doubley2){ this.x1=x1;this.y1=y1; this.x2=x2;this.y2=y2; } }//结束直线类 //***********定义多边形的填充类*******// publicclassfillPolygonextendsApplet//继承鼠标事件监听接口 implementsMouseListener,MouseMotionListener{ protectedMyCanvasm;//定义MyCanvas的对象 //扫描行处理用数据 protectedactiveEdgeListEntry[]edgeData=null;//边结点数组 protectedactiveEdgeList[]bucket=null;//多边形单链表数组 protectedactiveEdgeListactiveHeader=null;//当前边单链表的头指针 protectedintnumEdge=0;//多边形的边数 //鼠标相关数据 protectedbooleanisFirstClicked=true;//鼠标最初点击 protectedbooleanisDoubleClicked=false;//双击标志 protectedbooleanisSingleClicked=false;//单击标志 //绘图区域 protectedintwidth,height;//Applet绘图区的大小 protectedImageimage=null;//图像区域 protectedMemoryImageSourcemis=null;//内存图像 protectedint[]pixel=null;//内存图像配色数组 protectedintpixelWidth;//图像宽度 protectedintpixelHeight;//图像高度 protectedintxoffset;//pixel数据的窗口内显示偏移量 protectedintyoffset; protecteddoubleleftTopx;//pixel数据的起始点 protecteddoubleleftTopy; //多边形的绘图数据 protecteddoublex0,y0;//边的起点 protecteddoublelastx,lasty;//边的终点位置 protecteddoublemovingx,movingy;//用户坐标系下一个点的坐标 protectedintnumPoints=0;//顶点计数器 protectedbooleanisPolygonMode=true;//标志 protectedVectorlines=newVector(256,256);//Java的向量类 //APPLET程序的初始化 publicvoidinit(){ m=newMyCanvas(this);//本APPLET容器的MyCanvas对象 addMouseListener(this);//定义鼠标按钮监听器 addMouseMotionListener(this);//定义鼠标按钮监听器 Dimensiond=getSize();//本APPLET容器的大小 width=d.width;height=d.height; } //成员变量初始化 publicvoidinitData(){ isFirstClicked=true;//鼠标最初点击 isPolygonMode=true;//标志描绘多边形 numPoints=0;//多边形顶点计数器 bucket=newactiveEdgeList[height+1];//边的单链表数组 for(inti=0;i if(lines.size()>0)lines.removeAllElements();//向量类的对象 } //APPLET程序的绘图 publicvoidpaint(Graphicsg){ if(isFirstClicked){//初始状态 initData(); Fontf=m.MyFont(m.getFont().getName(),Font.BOLD+Font.ITALIC,1.5); m.setFont(f); m.drawString("单击画多边形",-0.5,0.2); m.drawString("双击填充多边形",-0.9,-0.15); } m.setBackground(newColor(220,220,220));//背景色 m.setColor(Color.black);//前景色 for(inti=0;i Linel=(Line)lines.elementAt(i);//转换第i个向量 m.drawLine(l.x1,l.y1,l.x2,l.y2); } if(isPol
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 实验报告5 多边形裁剪与填充 实验 报告 多边形 裁剪 填充