计算机图形学圆弧的生成ppt课件.ppt

28 03 2020 计算机图形学 ComputerGraphics CG 28 03 2020 4 3 1圆弧的生成 1 数值微分法 DDA法 2 中点画圆算法 3 Bresenham画圆算法 4 正负法 28 03 2020 与直线的生成类似 圆的生成算法的好坏将直接影响到绘图的效率 本节仅讨论圆心位于坐标原点的圆弧生成算法 对于圆心为任意的圆弧 可以先将其平移到原点 然后光栅化 再平移到原来的位置 28 03 2020 圆弧的DDA算法和直线段DDA法类似 也是根据圆弧的微分方程来实现的 我们以圆心在坐标系原点 半径为R的一段圆弧为例来讨论 圆心在原点 0 0 半径为R的方程为 1 数值微分法 DDA法 它的微分方程为 28 03 2020 若令 即可得离散变量微分方程式为 式中 为一很小的常数 若设 为用DDA法顺 时针画第一象限的圆弧在X Y方向的增量值 由上式可知 则有 4 1 28 03 2020 用矩阵表示为 4 2 但是 由式 4 1 得 所以式 4 1 表示的并不是一个圆 而是一个半径逐渐增大的螺旋线 要得到圆的方程 需要使式 4 2 中系数矩阵行列式值为1 即将式 4 2 中的 28 03 2020 变为1 若取 即能满足要求 即有 28 03 2020 也即 4 3 由 4 3 可知 在计算时我们不用 的结果 而是 直接引用 的值 28 03 2020 2 中点画圆算法 假设x坐标为的各像素点中 与该圆弧最近者已确定 为 那么 下一个与圆弧最近的像素只能是正右方的 或右下方的两者之一 令M为和的中点 易知M的坐标为 显然 若M在圆内 则离圆弧近 应取为下一个像素 否则应取 28 03 2020 判别式d d的初始值为 在d 0的情况下 取右下方像素 在d 0的情况下 取正右方像素 为了消除在计算判别式初始值产生的浮点数运算 将用4d来代替d 28 03 2020 下述程序使用中点画圆算法绘制一个1 8圆弧 voidMidPointCircle intr intcolor intx y dx 0 y r d 5 4r CirclePoint x y color while x y if d 0 d 8x 12 else d 8 x y 20 y x CirclePoint x y color 28 03 2020 3 Bresenham画圆算法 Bresenham画圆算法是最有效的算法之一 Bresenham画圆算法的基本原理是如下图所示 若为已经选定的点 那么下一个可能的像素点为其正右方的点或右下方的点 若到圆弧的距离小于到圆弧的距离 则取 反之取 28 03 2020 设R为圆弧的半径 记P x y 到原点的距离的平方与圆的半径的平方之差为D P 即 令 则 下面给出的递推公式 28 03 2020 当 0时 点做为下一个像素点 故 当 0时 点做为下一个像素点 故 28 03 2020 根据算法 可得Bresenham生成圆弧的程序如下 voidbresenham arc intR intcolor intx y d x 0 y R d 3 2 R while x y putpixel x y color if d 0 d 4 x 6 else d 4 x y 10 y 1 x if x y putpixel x y color 28 03 2020 4 生成圆弧的正负法 原理 设圆的方程为 假设求得的坐标为 则当在圆内时 有 当在圆外时 有 28 03 2020 即求得Pi点后选择下一个象素点Pi 1的规则为 当时 点落在圆弧上 当时 要右走一步 得 这是向圆外方向走去 的坐标为 代入到圆的方程可得 4 4 28 03 2020 当时 要向下走一步 这是向圆内方向走去 的坐标为 代入圆的方程可得 4 5 公式 4 4 和 4 5 就是计算的递推公