图形学算法 (2).doc

&:
1.【准备】XnßX0,ynßy0,mß -1,iß0
2.【排除必不相交情形】若下列条件有一个成立,则到4
1)xp<x,&&xp<xi+1
2)xp>=xi&&xp>=xi+1
3)xp<y&&yp<yi+1
3.【计算交点】y=yi+(xp-xi)(yi+1 - yi)/(xi+1 - xi)分两种情形:
1)若y=yp,则P在多边形边界上,算法结束
2)若y<yp,则 mß(-1)m;
4.【结束判断】ißi+1,若i<n,则返回到2,否则算法结束,此时若m = -1 则点P在多边形外部,m=1,则在内部。
*简述扫描线种子填充算法的工作步骤。
对种子所在的像素段进行填充
从右到左检查种子所在行的上一横行,将查到的像素段依次编号存入堆栈。实际存入堆栈内的可以是每个像素段最右边像素的地址。接着对种子所在行的下一横行同样处理。
若堆栈为空则算法结束,否则从堆栈顶部取出一个像素段。因为按先进后出的顺序,所以将取出编号最大的像素段。实际取出的是这个像素段最右边像素的地址。就以这个像素为新的种子,返回到1.
写出Graham凸壳求解算法
1.(倾角排序)选出输入电集S中X坐标最小的点,若这样的点不唯一则再由其中选出y坐标最小的点,,对点集中其余每一点P,计算倾角POX,再按倾角排序,得到点序列Q1=O,Q2,Q3,…,Qn;
2.(准备扫描)vßQ1;
3.(扫描)若NEXT(v) != Q1,则循环执行下面的操作至NEXT(v)=Q1时止,此时点序列中剩下排成凸多边形的壳上顶点,算法结束。若三个相继的点v, Next(v), Next(NEXT(v))形成一个左转,则vßNEXT(v);否则先删除NEXT(v),再做vßPRED(v);
*写出Jarvis凸壳求解算法
1(准备)v0ß点集S中按x,y字典次序最小的点;dß竖直向下的一个方向向量;点v0送入收集凸壳顶点的队列Q中;S1ßS –{u,v0};ußv0
2(一步行进)v1ßWrapping(u,d,S1);S1中各点相对于自u出发方向为d的射线,计算倾角,取倾角最小的点,若倾角相同,取与u距离最远的点,Wrapping(u,d,S1);返回下一个壳顶点。
3(准备下次) if v1 != v0,v1送入Q中;S1 = S –{u,v1}; dß从u到v1的一个方向向量; ußv1;返回步骤2
4(结束)Q中存入所有的壳顶点,算法结束
*试写出判定一空间多边形与一凸多面体之间关系的算法
求出空间多边形和凸多面体的包围盒
分别做x,y,z三向测试,若包围盒检查(最大最小检验)有一个为真,则空间多边形和凸多面体分离。算法输出分离并结束。
一次用凸多面体的每一表面多边形来求解与空间多边形各边的交点
若有交点,测试空间多边形的顶点是否均在凸多面体内,若均在体内,则为包含;若有交点,测试空间多边形的顶点有内有外,则相交;若无交点,测试空间多边形的顶点是否在凸多面体内,若均在体内,则为包含;若无交点,测试空间多边形的顶点均在凸多面体外,则为分离。

1)、消除隐藏线的线面比较法的最先一步就是利用外法线判断出所有可能的可见面。
2)、做