广工数媒计算机图形学之基本图形生成算法直线圆弧.pptVIP

直线的扫描转换——中点Bresenham算法 算法说明： 设直线斜率在0~1之间，且位于第一象限。光标走步规则为：每次在x方向上加1，y方向根据误差项判断，或加1或加0。 直线的扫描转换——中点Bresenham算法 误差项判别式构造： 当前点P，下一个点可能为Pd (即yi+1=yi点) ，可能为Pu (即yi+1=yi+1点)。M为Pd 与Pu的中点。 若M在Q点下方，说明Pu点离直线近，则有yi+1=yi+1; 若M在Q点上方，说明Pd点离直线近，则有yi+1=yi; 直线的扫描转换——中点Bresenham算法 直线方程为： 要判断点M与直线的位置关系，只需要把M的坐标代入直线方程，若： F(xM, yM)=0，即点M在直线上； F(xM, yM)0，即点M在直线上方； F(xM, yM)0，即点M在直线下方； 直线的扫描转换——中点Bresenham算法 点M与点Q误差项d判别式推导： 当di0时，M在直线下方，Pu (即yi+1=yi+1点)为下一个点； 当di=0时，M在直线上方或在直线上，Pd (即yi+1=yi点)为下一个点。 根据递推思想，推导出di与di+1的关系。 直线的扫描转换——中点Bresenham算法 当di0时，xi+1=xi+1; yi+1=yi+1; 则有： 直线的扫描转换——中点Bresenham算法 当di=0时，xi+1=xi+1; yi+1=yi; 则有 d的初值：绘制直线时，光点最初在直线的起点P0(x0, y0)处，可推导出：d0=0.5-k 直线的扫描转换——中点Bresenham算法 直线的斜率k=dy/dx，将斜率带入判别式： 当di0时，则有 当di=0时，则有 d的初值： di的正负决定下一个点的位置，与di 的具体数值无关，因此，统一以2dxHdi替代di，以简化判别式。 直线的扫描转换——中点Bresenham算法 当di0时，则有 当di=0时，则有 d的初值： 因此在代码中最终用到的判别式为： 直线的扫描转换——中点Bresenham算法 绘制点(x, y) yes no 直线的扫描转换——中点Bresenham算法 上述推导的中点Bresenham算法绘制直线的判别式适用于直线斜率在0~1之间的情况。 观察例mid_bresenham.cpp绘制斜率在0~1之间的直线和斜率大于1的直线。 当直线大于1时，可不必重新推导判别式，只需交换x和y的规则。bresenham.cpp 直线的扫描转换——Bresenham算法 中点Bresenham算法的误差项判别式需要用到直线斜率，改进后的Bresenham算法，思路保持不变，对误差项判别式进行简化。 Bresenham算法直接比较距离t和s的大小，来确定下一个绘制的像素。 推导、简化后得到的误差项判别式为： 当di=0时，xi+1=xi+1; yi+1=yi+1; 有 直线的扫描转换——Bresenham算法 当di0时，xi+1=xi+1; yi+1=yi; 则有 从推导得出的确定画笔下一步位置的公式可以看出，Bresenham算法中只包括加法、减法和乘2的操作，所需要的计算量很小。 Bresenham算法不仅用于绘制直线，也可用于显示圆和其他曲线的整数增量计算，应用很广泛。 直线的扫描转换——Bresenham算法 例程分析：bresenham.cpp 几个重要变量说明： dt——误差项，对应判别式d; tx、ty——x、y方向的增量，取值可为-1、0、1; interchange——记录直线斜率情况。当斜率1时，该变量取值1；当斜率=1时，该变量取值0。 直线的扫描转换——Bresenham算法 圆的扫描转换 给出圆心(xc , yc)和半径r，逐点绘制圆的方式有： 一、利用直角坐标方程 利用直角坐标方程绘制圆弧思路清楚，但计算涉及开方运算，计算量大。更大的缺点是，由于y不是x的线性函数，因此，当x取值从0到r均匀递增时，y的值变化极不均匀，尤其当x接近r时，绘制出来的圆会出现较大的间断。 圆的扫描转换 二、利用圆的参数方程 利用参数方程绘制圆弧可以克服直角坐标方程画圆的弊端。参数为圆周角，当圆周角按固定增量变化时，能获得均匀分布在圆周上的点。 圆的扫描转换 但是，利用圆的参数方程绘制圆弧有两个严重缺陷： 一、每次求点坐标都需要计算三角函数，计算量大，效率低。 二、t 增量的大小与半径相关。如，若t 取某一定值，当半径很小时，计算出来的像素可能会重叠（相邻像素的x和y的增量都不于1）；而当半径较大时，有可能会造成圆弧出现断开现象（相邻像素的x和y的增量过大） 。 观察例程“圆参数方程” 圆的扫描转换——八分法画圆 圆心位于原点的圆有四条对称轴线： 若已知圆周上任意一点，可以利用圆的对称性得到另外七个点的坐标