计算机图形学 算法总结

《计算机图形学 算法总结》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、计算机图形学算法总结viopond@life-sciences一、二维线画图元的生成扫描转换直线段生成直线段的DDA算法利用直线方程直接计算，结果取整。用到浮点数的加法和取整。生成直线段的中点算法利用直线的正负划分性，构造隐函数F（x,y）。每次计算F(xi+1,yi+0.5)，判断函数正负，若为正则下一点在右侧，若为负则下一点在右上。判别式F(x,y)=△xy-△yx-△xB(原直线y=mx+B，把m改写)。计算判别式递推的方法：分d>=0和d<0两个情况，计算横坐标为xi+2时的判别式表达式，获得d的增

2、量。Breseham画线算法d是误差项。x下标每次加1，d相应增加斜率k。一旦d>=1,就把它减去1。当d>=0.5时，取当前象素右上方象素。当d<0.5时，取右边象素。为方便计算，令e=d-0.5扫描转换圆弧圆的八对称性利用圆弧方程开根计算或者利用参数方程计算，开根/三角函数，计算量大圆弧的中点算法F(x,y)=x^2+y^2-R^2正在圆弧外，取右下。负在圆弧内，取右。第一象限：构造判别式d=F(M)=F(xi+1,yi-0.5)，递推方法类似直线的中点算法。椭圆的中点画法也与此类似。判别式函数不一样而

3、已。生成圆弧的多边形逼近法给定最大逼近误差delta,确定圆心角，R-Rcosa<=deltan=2pi/a下一个顶点，用cosa–sina矩阵乘xisinacosayi一个顶点需4次乘法，一共4n次乘法，外加直线段中点算法的计算量圆的等面积逼近法求多边形径长，从而求所有顶点坐标。由逼近误差值确定圆心角a。生成圆弧的正负法曲线把平面分成G+和G-两个区域，前进△x时，到达P1,再前进△y到P2，之后若点与P1在同侧，则前进△y，否则前进△x。判别式D(Pi)=F(Pi).F(P1)=F(xi,yi).F(x

4、0+△x,y0)二、二维填充图元的生成扫描转换矩形做x,y坐标的二重循环，逐点填充。共享边界：左闭右开，下闭上开。扫描转换多边形逐点判断法、扫描线算法、边缘填充法逐点判断法：射线法：从每个象素点发射线，交点个数偶数的在外，反之在内。避免射线通过顶点。累积角度法：记录从该象素到多边形每个顶点的有向角（逆时针旋转为正），若代数和为0则在外，若为正负2pi的在内。编码方法：从X轴起逆时针把各象限编码，确认各顶点所在象限的编码，然后两顶点相减计算各边的编码，用4处理使编码绝对值不大于2，最后求各边编码代数和。代数和

5、为0的在外，为正负4的在内。特殊情况：(1)点在边上.预处理解决(2)代数和为正负2（取中点再编码，递归）扫描线算法求扫描线与多边形各边的交点对所得交点从小到大排序两两配对，填充每个区段原则：与扫描线的交点向多边形内取整。交点落在象素点上时，仅落在左边上的属于多边形。交点为多边形顶点时，每个边被认为下闭上开(p74)。数据结构和算法流程P76特点：算法效率比逐点填充法高很多缺点：对各种表的维持和排序开销太大，适合软件实现而不是硬件实现。边缘填充法：基本思想：对于每条扫描线盒每条多边形边的交点，将该扫描线上交

6、点右方的所有像素颜色取补。对多边形的每条边做此处理。原理：以求余运算代替扫描线算法中的排序运算。特点：适合用于具有帧缓存的图形系统。算法简单，但对于复杂图形，每一像素被访问多次，输入输出多。扫描转换扇形区域原理同多边形扫描转换，问题在于确认扫描线与直边和圆弧边的相交顺序。分情况讨论，固定P1在第一象限时有4种情况，一共十六种。区域填充四向联通区域、八向联通区域边界表示的四连通递归算法（种子填充算法）：种子像素入栈，栈非空时，重复执行以下步骤：栈顶像素出栈，将出栈像素置色，四向检查像素，若其中某个像素不在边界

7、且未被置色，则该像素入栈。可用于填充带内孔的平面区域。缺点：有些像素反复入栈降低效率，栈结构占空间。递归执行算法简单但效率不高。可用下面的扫描线填充算法解决。扫描线填充算法目标：减少递归算法：栈顶像素出栈沿扫描线对出栈像素的左右像素进行填充，直到遇到边界像素为止。（填充区间）检查上下扫描线，选相应区间的最左像素作为种子入栈。特点：由区域算法定区间，再定上下邻区间。多边形扫描转换与区域填充方法比较：不同点：前者将顶点表示转换成点阵表示，后者只是改变颜色，没有改变表示方法。前者只要求扫描线与多边形边界交点个数为

8、偶数。后者要求区域封闭。前者从边界顶点信息出发，后者从区域内种子点出发。三、二维光栅图形的混淆与反混淆用离散量（像素）表示连续的量（图形）而引起的失真，叫做混淆或者走样。反混淆方法提高分辨率：方便，代价巨大区域采样方法：把直线段看做具有一定宽度的狭长矩形，当直线段与像素有交时，求出相交区域的面积。根据面积大小确定亮度值，使相邻两个像素的灰度之间有平缓的过渡。非加权区域采样方法：非加权区域采样方法性质：（1）像素亮