图形学 考试算法.doc

浮动水平线法首先将投影曲线按距观察点的距离递增排序从最近的曲线开始，对每一x值决定其对应的y值对于当前曲线上一点的y值，若大于先前所有平面曲线上同一点的y值则可见；反之不可见。只有所有曲线上的点均在第一条曲线之上时，该算法是正确的，但实际上并非如此，如下图，某些后面的曲线可能位于第一条曲线的下方，这些曲线位于曲面的底部应是可见的，但按上述算法它们被当作不可见： 多边形的逼近二次B样条优于三次B样条三次B样条优于三次Bezier曲线，最佳：三次样条插值。直线DDA算法源程序： void DDAline(int x1, int y1, int x2, int y2, CDC* pDC) int i,steps; float x,y,dx,dy; steps = abs(x2-x1) abs(y2-y1) ? abs(x2-x1) : abs(y2-y1); dx = (float)(x2-x1) / steps; dy = (float)(y2-y1) / steps; x = x1 + 0.5; y = y1 + 0.5; for (i = 0; i SetPixel(m_winSizeX/2+x, m_winSizeY/2-y, RGB(225,0,0); x += dx; y += dy; 直线B算法源程序： void Bline(int x1, int y1, int x2, int y2, CDC* pDC) int x,y,dx,dy,i,e,px,py,flag,steps; steps = abs(x2-x1) abs(y2-y1) ? abs(x2-x1) : abs(y2-y1); dx=abs(x2-x1); dy=abs(y2-y1); px=(x2-x1)0? 1:-1; py=(y2-y1)0? 1:-1; e=-dx; x=x1; y=y1; if(dydx)flag=1;elseflag=0;for(i=0;iSetPixel(m_winSizeX/2+x, m_winSizeY/2-y,RGB(0,0,225);if(flag=0)e=e+2*dy;x=x+px;if(e=0)y=y+py;e=e-2*dx;else e=e+2*dx; y=y+py; if(e=0) x=x+px; e=e-2*dy; 种子像素入栈当栈非空时，重复以下步骤：栈顶像素出栈沿扫描线对出栈像素的左右像素进行填充，直到遇到边界像素为止将上述区间内最左、最右像素记为xl和xr 在区间xl,xr中检查与当前扫描线相邻的上下两条扫描线是否全为边界像素、或已填充的像素，若为非边界、未填充的像素，则把每一区间的最右像素取为种子像素入栈对于那些非完全可见、又非完全不可见的线段，需要求交，求交前先测试与窗口哪条边所在直线有交？(只要按顺序检测到端点编码的某位不为0时，才把线段与对应的窗口边界进行求交）Void ClipLine(int *x1, int *y1, int *x2, int *y2)iflag = 0;if(abs(*x1 - *x2) APERATURE)iflag = -1; /*垂直边*/elseslop = (float (*y1 - *y2)/ (*x1 - *x2);for (i=0; i4; i+)visible = Cohen(x1, y1, x2, y2);if (visible = 1)return 1;if (!visible)return 0;if (iflag = -1 & i2)continue;if( i2 )intery = slop * (windowi - *x1) + *y1; *x1 = windowi; *y1 = intery;elseif(iflag = -1) *y1 = windowi;else *x1 = 1.0/slop * (windowi - *y1) + *x1; *y1 = windowi;int Cohen(int *x1, int *y1, int *x2, int *y2)code1 = EndPoint(x1, y1); code2 = EndPoint(x2, y2);if(code1 = 0 & code2 = 0)return 1;if(code1 & code2)return 0;if(code1 = 0)temp = *x1; *x1 = *x2 , *x2 = temp;temp = *y1; *y1 = *y2 , *y2 = temp;intEndPoint(int *x, int *y)code = 0;if(*x window1)code = code | 2;if(*y window3)code = code | 8;梁友栋-barsky算法(1)输入直线段的两个端点坐标(x0, y0),(x1, y1)以及窗口的四条边界坐标xL，xR，yB，yT。若x0，则QL=QR=0，此时进一步判断是否满足DL0或DR0且DR0，则进一步计算tl和tu，算法转(5)。若y0，则QT=QB=0，此时进一步判断是否满足DT0或DB0且DB0，则进一步计算tl和tu，算法转(5)。若上述两条都不满足，则有Qi不为0，此时计算tl和tu求得tl和tu后进行判断，若tltu，则直线段在窗口外，算法转(7)，否则利用直线的参数方程求得直线段在窗口内的两端点坐标。利用直线段的扫描转换算法绘制在窗口内的直线段。算法结束。Sutherland-Hodgman算法分割处理策略：将多边形关于矩形窗口的裁剪分解为多边形关于窗口四边所在直线的裁剪。如同画家作画一样，确定空间的显示次序由远至近1 算法原理收集空间所有可见面三角形分割三角形排序（由远至近）输出显示三角形2 三角形排序空间任两三角形P499基本步骤生成深度优先级队列据视点距离远的多边形优先级低，排在队列的前端据视点距离近的多边形优先级高，排在队列的后端 从队列中依次取出多边形，计算其表面光亮度写入帧缓冲器 直到队列中所有多边形的光亮度都计算完毕，并写入帧缓冲器三 深度缓冲器算法 深度缓冲器算法（z-buffer）算法是常用的物体表面可见性判断的像空间算法。z-buffer算法的基本思想是：对投影平面上每个像素所对应的表面深度进行比较。即:先将Z缓冲器中各单元的初始值置为最小值。当要改变某个像素