《某实验报告材料5多边形裁剪与填充要点》由会员分享，可在线阅读，更多相关《某实验报告材料5多边形裁剪与填充要点（17页珍藏版）》请在金锄头文库上搜索。
1、word计算机图形学实验5实验报告实验题目：多边形裁剪与填充实验内容：1 阅读理解提供的参考资料。2编写并调通一个多边形裁剪的java程序。3编写并调通一个多边形填充的java程序。参考资料：根本概念：1变换与裁剪：（1） 计算机处理图形的过程一般分为三个阶段：图形的数字化；图形操作；图形输出。2模型坐标系局部坐标系：当构造单个对象的数字模型时，为了方便,可以将其置一个特定的坐标系下，即模型坐标系或局部坐标系。3世界坐标系：为描述图形场景中所有图形之间的空间关系,将它们置于一个统一的坐标系中，该坐标系被称为世界坐标系。4设备坐标系：要输出经过处理后的数字化图形，需要在输出设备上建立一个坐标系，
2、称为设备坐标系。5标准化设备坐标系：有些图形系统，对设备坐标系进展了规X化，将坐标X围限定在区间x,y,z | 0x1, 0y1, 0z1内，称标准化设备坐标系。6三维图形的显示流程图7裁剪裁剪作用：选择显示的内容-图形在窗口内的局部被显示出来，窗口外的局部被裁剪掉。图形中每个根本元素都要经过裁剪,因此裁剪直接影响整个图形系统的效率。裁剪类型：二维裁剪、三维裁剪裁剪窗口：矩形，凸多边形，任意多边形视见体:棱台 、立方体裁剪对象：直线段、多边形、文字等2多边形的填充: (1)多边形的填充指在给定区域填上所需要的颜色，就是把多边形的顶点表示转换为点阵表示，即从多边形的给定边界出发，求出位于其内部的
3、各个像素，并将帧缓冲器内的各个对应元素设置相应的灰度或颜色。(2)多边形的表示：1顶点表示是用多边形的顶点的序列来描述多边形，该表示几何意义强、占内存少，但它不能直观地说明哪些像素在多边形内。2点阵表示是用位于多边形内的象素的集合来刻划多边形，该方法虽然没有多边形的几何信息，是面着色所需要的图像表示形式。算法设计：1 多边形的裁剪：Sutherland-Cohen算法:根本思想：对于每条线段P1P2分为三种情况处理。1假如P1P2完全在窗口内，如此显示该线段P1P2简称“取之。2假如P1P2明显在窗口外，如此丢弃该线段，简称“弃之。3假如线段既不满足“取的条件，也不满足“弃的条件，如此在交点处
4、把线段分为两段。其中一段完全在窗口外，可弃之。然后对另一段重复上述处理。具体操作：分为两步第一步是判定：1) 完全在窗口内的直线段，称为完全可见的线段；2) 完全在窗口外的线段，称为完全不可见线段。第二步处理不能断定为完全可见或完全不可见的线段。这时需要计算出直线段和窗口边界的一个交点，这个交点把直线分成两段，其中一条为完全不可见的线段,被抛弃。对余下局部再作第一步的判断，重复上述过程，直到直线段余下的局部可用第一步的判断得出肯定的结论为止。2多边形的填充:(1) 多边形填充的扫描线算法a. 令y = c 为一个常数，扫描整个多边形的边，记录横坐标为xi记为序列1.b. 设d为一整数，d=c1
5、，且yi0yyin；设位于扫描线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),0in，
6、 xi, yi均为整数；置Pn+1=P0。每一条扫描线上着上这种特殊颜色的点的个数必定是偶数(包括零)。b. 设interior_point 是一布尔变量。对每一条扫描线从左到右进展搜索，如果当前是像素位于多边形P内，如此interior_point=true，需要填上值为polygon_color的颜色；否如此该像素在多边形P外，需要填上值为background_color的颜色。 (3)区域填充:a. 区域是指已经表示成点阵形式的像素集合。在光栅图形 中，区域可采用内点表示和边界表示两种形式进展描述。内点表示法：把位于给定区域内的所有像素一一列举出来的方法称为内点表示法。边界表示法：把位于
7、给定区域边界上的像素一一列举出来的方法称为边界表示法。b.区域的连通性:1) 连通的区域: 取区域内任意两点，在该区域内假如从其中一点出发通过上、下、左右四种运动可到达另一点。2连通的区域: 取区域内任意两点，假如从其中任一点出发，在该区域内通过沿水平方向、垂直方向和对角线方向的八种运动可到达另一点。4扫描线种子填充算法:从给定的种子点开始，填充当前扫描线上种子点所在的一区段，然后确定与这一段相邻的上下两条扫描线上位于区域内的区段需要填充的区间，从这些区间上各取一个种子点依次把它们存起来，作为下次填充的种子点。反复进展这过程，直到所保存的各区段都填充完毕。步骤：a.初始化将算法设置的堆栈置为空
8、。将给定的种子点x, y压入堆栈b.出栈如果堆栈为空，算法完毕；否如此取栈顶元素x, y作为种子点c.区段填充从种子点x, y开始，沿纵坐标为y的当前扫描线向左右两个方向逐个像素用新的颜色值进展填充，直到边界为止即象素颜色等于边界色。设区间两边界的横坐标分别为xleft 和xright。d. 在与当前扫描线相邻的上下两条扫描线上，以区间xleft, xright为搜索X围，求出需要填充的各小区间，把各小区间中最右边的点并作为种子点压入堆栈，转到步骤2。 代码：1 多边形的裁剪：publicint code(float x,float y) int c=0;if(xxR)c=c|2;if(yyT
9、)c=c|8;return c;/二进制分别为 0 1 10 100 1000 /Sutherland_Cohen裁减算法publicvoid 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; elseif(c1&c2)!=0
10、)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
11、; 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多边形的填充：class activeEdgeList activeEdgeListEntry header=null;activeEdgeListEntry tailer=null;public activeEdgeList(activeEdgeListEntry element) header=t
12、ailer=element;/指向第一个边结点/把新结点插入有序排列的多边形单链表publicvoid insert(activeEdgeListEntry element) activeEdgeListEntry sentinel;if(element=null | this.header=null)/新结点异常或者链表空thrownew NullPointerException();/出错，抛出异常sentinel=this.header;/当前指针指向表头结点int xt=element.topx;/新结点的topxint xtold=sentinel.topx;double oldDe
13、lta=sentinel.delta;/当前结点的deltadouble newDelta=element.delta;/* 排序第一关键字结点的topx，第二关键字结点的delta */* 两个关键字由小到大*/if(xtoldxt)|(xtold=xt)&(oldDeltanewDelta)while(true)/在链表头指针之后寻找新结点element的位置if(sentinel.next=null) sentinel.next=element;/追加到表尾this.tailer=element;break;/完毕while循环activeEdgeListEntry mp=sentinel.next;/下一结点int xmt=mp.topx;double midDelta=mp.delta;if(xmtxt)|(xmt=xt)&(midDeltanewDelta)sentinel=mp;/新结点仍然大于下一结点，当前结点指针后移，继续循环else /否如此，新结点就应该插入当前位置sentinel.next=element;element.next=mp;break;/完毕while循环，尾指针不动else /新结点作为单链表头结点sentinel=this.header;this.hea
