计算机图形学算法思想

1、扫描转换扫描转换直线段DDA算法基本思想：直接求点中点算法基本思想：根据一个点的取值范围来确定下一个点的取值是NE还是E（利用取值范围的中点M在直线上方还是下方来确定取点）具体实现：以中点d的符号来确定取NE还是E，当d0，取E，反之取NE；F（x，y）=deltaX*y-deltaY*x-deltaX*B为了去除分母，d=2*F（x，y）然后d的符号是根据递推式来求取，直接用（x+2，yi+1+0.5）带入F，然后根据yi+1与yi的关系把F（x+1，yi+0.5）的那部分取出来，剩余一部分就是要加上去的那一部分。最后d0 di+1=di-2*delataY d0，取SE，反之取E；F（x，

2、y）=x2+y2-R2d=F(M)然后d的符号是根据递推式来求取，直接用（x+2，yi+1-0.5）带入F，然后根据yi+1与yi的关系把F（x+1，yi -0.5）的那部分取出来，剩余一部分就是要加上去的那一部分。最后d0 di+1=di+2(xi-yi)+5 d0 dpi+1=dpi-2yi+1 pi0 dpi+1=dpi+2xi+1扫描转换矩形基本思想：直接找到矩形的box，然后直接用一个for循环即可。扫描转换多边形逐点判断算法基本思想：找到多边形的box，然后依次判断里面的点是否属于多边形，可以用逐点判断算法，累计角度法或者是编码法来判断点是否在多边形内部。注：这里特别实现过，所以是

3、重点射线法基本思想：为了方便，从一个点引出水平向右的射线，然后计数它与多边形边的交点个数来确定它是否在多边形内，若为奇数则在多边形内，否则在多边形外。但是要注意水平边取0个交点，还有顶点下取上不取这些奇异情况。编码法基本思想：它是累计角度法的离散化思想，以v为原点建立坐标系，然后对各边进行编码，然后相加的和若为0，则在外部，若为+-4，则在内部。在求和过程中特别要注意+-3的情况要进行加减周期4处理，还有+-2的情况，这是跨象限的情况，所以要额外判断，可以根据直线与y=0的交点的正负来进行判断。还有若顶点落在坐标系上，这种特殊处理，简化吧。扫描线算法基本思想：点的连续性和边的连续性来减少无效的

4、判断，建立边的分类表ET和活化边表AEL。然后从最小的y开始依次往上走，依次组织成对交点进行填充即可。但是要注意取整必须往多边形内部方向取整，以及落在边上左取右不取，还有顶点下取上不取，水平边不计。边缘填充算法基本思想：有两种，第一种以扫描线为中心向右填充，第二种以边为中心向右填充。若填充了偶数次，则那些点就是外部点，奇数次则为内部点。填充图元区域填充递归填充算法基本思想：直接调用递归。扫描线算法基本思想：利用扫描线连续性，先以一个种子点填充其所在的区段，然后进行上下填充，这个算法相对比较复杂，涉及堆栈的一些基本操作，所以估计不会出大题。二维裁剪直线段裁剪直接求交算法基本思想：判断两个端点关于

5、裁剪框的关系即可。Cohen-Sutherland算法基本思想：编码法的思想，先对各区域进行合理的编码，然后直接可以确定完全可见和完全不可见的线段，剩下的可以不断进行与矩形框某一条边的求交，然后舍去其外部部分。注：这个算法我认为也比较重要，也实现过，可能是写其中的片段算法。Nicholl-Lee-Nicholl算法基本思想：在Cohen-Sutherland算法的基础上，更加划分细的区域减少求交。中点分割算法基本思想：用递归的方法以一个精确度E来找p0和p1最近的可见点。梁友栋-Barsky算法基本思想：生成诱导窗口将二维的相加问题转到一维上来，可见部分VW=P0P1交LR交TB，LR和TB分别是P0P1所在直线与窗口左右上下所交的点连线。然后以参数式的形式求得相应的t0，t0， t1，t1，以及初始的（0,1）求交集。主要是定义r=d/q来求取交点这里，这是用相似的方法得出的，比如说（x0-xL）/deltax，可以看做是p0交点与p0p1在水平方向上的比例，这样得到t带入参数式就可以得到交点了。注：这个算法我认为也比较重要。多边形裁剪Sutherland-Hodgman算法基本思想：逐边裁剪法，利用窗口边的半空间特点，则考虑到4种不同情况。然后以点为着眼点，结果集中的点的集合为交点或者是原来的顶点的集合。Weiler-Atherton算法基本思想：主多