第3_1章 计算机图形学的基本算法.ppt

第三章 计算机图形学的基本算法 主要内容 1.计算机图形学生成基础 2.基本图形生成算法 点、直线段、曲线等 点的生成 点是图形中最基本的图形元素，直线、曲线以及其它的图形都是点的集合 在图形学里，点既有位置又有大小，大小是一个像素，像素是最小的图形单位。像素的大小取决于显示器的尺寸和分辨率，用灰度或颜色表示点的像素，又叫“点亮” 点的生成 o X Y P（X，Y） 点可用数值坐标来表示，二维坐标用（x，y），三维坐标用（x，y，z） o X Y Z P（X，Y，Z） 直线段的生成 在计算机图形学中，直线是由离散的像素点逼近理想直线段的点的集合 理想直线 实际绘制 直线的宽度与像素点的大小有关，一个像素宽的直线的线粗为像素的边长 直线段的生成 直线的生成要求 直线的起、终点要准确 直线要直 直线粗细要均匀（构成线段的像素点的集合尽量分布均匀、其密度应该与线段的方向及长度无关） 线段生成的速度要快 绘制直线的常用算法 数值微分法(DDA) 中点画线法 Bresenham法 直线基础 直线的笛卡儿斜率截距方程为 y=m?x+b m--- 直线的斜率 b --- 直线于y轴的截距 给定线段的两个端点(x0,y0), (x1,y1)，可以计算斜率m和截距b 在X方向上，给定任意增量?x，对应y的增量为?y, 则? y = m? x 图形学直线的算法是以上面的直线方程、斜率方程、截距方程和增量方程为基础 数值微分算法(DDA法) 一种从直线的微分方程出发生成直线的方法，其本质是用数值法解微分方程 直线的微分方程： m: 直线的斜率 DX，DY：直线起、终点差值 起点坐标 终点坐标 数值微分算法(DDA法) 可通过计算x方向的增量Δx引起y的改变来生成直线 由 （ 为直线上某步的初值） 则 也可通过计算由y方向的增量Δy引起x的改变来生成直线 设 则 数值微分算法(DDA法) 选定 和 中较大者作为步进方向。假设 较大，取该方向上的 为一个像素单位长，即 每次递增1（一个像素），然后利用下式计算相应的 值， 把每次计算出的（ ）经取整后顺序输出到显示 器，则得光栅化后的直线。 下面给出简单DDA算法，选择Δ 和Δ 中较大者为一个像素单位，其相应方向的增量为1 算法的基本思想 数值微分算法(DDA法) DDA算法缺点 在此算法中，y或x、斜率m都是float，且每一步都必须对y或x进行舍入取整，不利于硬件实现 Bresenham 画线算法 1965年，由Bresenham提出，该算法是一种精确而有效的光栅直线段生成算法，主要借助一个决策参数 ，来确定下一个像素点的位置 先考虑斜率小于1，沿线路径的像素位置由以单位 间距的取样来决定的直线情况。从给定线段的左端点（ ）开始，逐步处理每个后继列（ 位置），并在扫描线 值最接近线段的像素上绘出一点 它是目前最有效的线段生成算法 Bresenham 画线算法 两个候选像素的 值与线段上理想 值的差值 和 假设直线段上当前的像素点已确定，其坐标为（ ）那么下一步需要在列 上确定扫描线的 值。 值要么不变，要么递增1 Bresenham 画线算法 设 和 分别为端点的垂直和水平偏离量 则 即为画线算法中第K步的决策参数 常量与像素位置无关 Bresenham 画线算法 的符号与 的符号相同（因为本例中 ），如果 处的像素比 的像素更接近于线段（即 ），那么参数 是正的。此时绘制较高像素；反之，绘制较底像素