实验5 计算机图形学 实验报告.
实验5实验报告格式计算机图形学实验5实验报告xxxxxx xxx xxxxxxx实验题目：多边形裁剪与填充实验内容：1 阅读理解提供的参考资料。2编写并调通一个多边形裁剪的java程序。3编写并调通一个多边形填充的java程序。参考资料：1 fillPolygon.java 2 clipSC2.java2变换与剪裁.ppt3多边形的填充.ppt基本概念：（详细叙述自己对实验内容的理解）变换与裁剪基本概念的理解：矢量：矢量是一个n元组，在坐标系中它对应于n维空间的一个点，这个点 可以代表物体在空间的位置，也可以代表其运动状态等。模型坐标系（局部坐标系）：当构造单个对象的数字模型时，为了方便,可以将其置于一个特定的坐标系下，即模型坐标系或局部坐标系.世界坐标系：为描述图形场景中所有图形之间的空间关系，将它们置于一个统一的坐标系中，该坐标系被称为世界坐标系。标准化设备坐标系：有些图形系统，对设备坐标系进行了规范化，将坐标范围限定在区间x,y,z | 0x1, 0y1, 0z1内，称标准化设备坐标系投影: 三维空间中的对象要在二维的屏幕或图纸上显示出来，就必须通过投影。投影的方法有两种，平行投影和透视投影。视区：在屏幕或绘图纸上定义一个矩形，称为视区，也称为视口,窗口内的景物在视区中显示。平移：点(x,y,z)由点(x, y, z)在x, y和z轴方向分别移动距离x, y和z得到。两点坐标间的关系为 x=x+x y=y+y (4.1) z=z+z放大和缩小以原点为中心的缩放：设点(x, y, z)经缩放变换后得点(x,y,z)。两点坐标间的关系为其中sx,sy和sz 分别为沿x, y和z轴方向放缩的比例。其矩阵形式是图形模式：矩阵合并时，先调用的矩阵放在右边，后调用的矩阵放在左边.也称为固定坐标系模式。这种模式的特点是每一次变换均可看成相对于原始坐标系执行的。空间模式：又称活动坐标系模式。先调用的矩阵放在左边，后调用的矩阵放在右边,连续执行几次变换时，每一次变换均可看成是在上一次变换形成的新坐标系中进行的。多边形的填充：多边形的表示方法：1）顶点表示是用多边形的顶点的序列来描述多边形，该表示几何意义强、占内存少，但它不能直观地说明哪些像素在多边形内。2）点阵表示是用位于多边形内的象素的集合来刻划多边形，该方法虽然没有多边形的几何信息，是面着色所需要的图像表示形式。区域是指已经表示成点阵形式的像素集合。在光栅图形中，区域可采用内点表示和边界表示两种形式进行描述。内点表示法：把位于给定区域内的所有像素一一列举出来的方法称为内点表示法。边界表示法：把位于给定区域边界上的像素一一列举出来的方法称为边界表示法。算法设计：（详细叙述自己设计的的算法）多边形裁剪算法分析： 基本思想是一次用窗口的一条边裁剪多边形，窗口的一条边以及延长线构成裁剪线，该线把平面分成两个部分：可见一侧，不可见一侧。用一条裁剪边对多边形进行裁剪，得到一个顶点序列，作为下一条裁剪边处理过程的输入点。 对于每一条裁剪边，只是判断点在窗口的哪一测以及求线段与裁剪边的交点算法应随之改变。多边形裁剪的SutherlandHodgman算法 1>. SutherlandHodgman多边形裁剪算法思想 该算法的基本思想是每次用窗口的一条边界及其延长线来裁剪多边形的各边。多边形通常由它的顶点序列来表示，经过裁剪规则针对某条边界裁剪后，结果形成新的顶点序列，又留待下条边界进行裁剪，直到窗口的所有边界都裁剪完毕，算法形成最后的顶点序列，才是结果多边形（它可能构成一个或多个多边形）。 当多边形一个顶点Pi相对于窗口某条边界及其延长线进行剪裁时，不外乎下列四种情况（即裁剪规则）： 1、顶点Pi在内侧，前一顶点Pi-1也在内侧，则将Pi纳入新的顶点序列； 2、顶点Pi在内侧，前一顶点Pi-1在外侧，则先求交点Q，再将Q、Pi依次纳入新的顶点序列； 3、顶点Pi在外侧，前一顶点Pi-1在内侧，则先求交点Q，再将Q纳入新的顶点序列； 4、顶点Pi与前一顶点Pi-1均在外侧，则顶点序列中不增加新的顶点。多边形填充算法分析： 确定多边形所占有的最大扫描线数，得到多边形顶点的最小和最大y值（ymin和ymax），从y=ymin 到 y=ymax, 每次用一条扫描进行填充。对一条扫描线填充的过程可分为四个步骤: a.求交b.排序c.交点配对d.区间填色。扫描多边形填充算法的基本原理在直角坐标系中，假设有一条从左至右的扫描线穿过多边形，从左至右开始计数，与多边形交点为奇数时，开始进入多边形，与多边形交点为偶数时，走出多边形。这样在这相邻配对的奇偶交点间的所有象素都在多边形内。如图，奇数交点a，c，都是入多边形，偶数交点b，d都是走出多边形，相邻的奇偶交点配对，a，b之间，c，d之间的象素都多边形内，可见一条扫描线上，与多边形交点个数需要为偶数。依据这样的思路，扫描线从上到下从左到右依次扫过多边形即可求得多边形所占据的象素。（注意退化情况的处理，也就是扫描线刚好经过顶点或者多边形的边本身就是水平的情况）bdca扫描多边形填充的原理代码：（给出和实验内容相关的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)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; y0=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;/链表尾指针/构造方法public activeEdgeList(activeEdgeListEntry element) header=tailer=element;/指向第一个边结点/把新结点插入有序排列的多边形单链表public void insert(activeEdgeListEntry element) activeEdgeListEntry sentinel;/当前结点指针if(element=null | this.header=null)/新结点异常或者链表空throw new NullPointerException();/出错，抛出异常sentinel=this.header;/当前指针指向表头结点int xt=element.topx;/新结点的topxint xtold=sentinel.topx;double oldDelta=sentinel.delta;/当前结点的deltadouble newDelta=element.delta;/* 排序第一关键字结点的topx，第二关键字结点的delta */* 两个关键字由小到大*/if(xtold<xt)|(xtold=xt)&&(oldDelta<newDelta)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(xmt<xt)|(xmt=xt)&&(midDelta<newDelta)sentinel=mp;/新结点仍然大于下一结点，当前结点指针后移，继续循环else /否则，新结点就应该插入当前位置
