计算机图形学 《计算机图形学》 路 通 博士、教授 南京大学计算机科学与技术系课程 路 通 博士、教授 lutong@nju.edu.cn http://cs.nju.edu.cn/lutong/ 18913926002 Department of Computer Science and Technology, NanJing Uiversity

1 Bresenham直线绘制算法 2 圆/弧的绘制算法 3 其它曲线的绘制算法 第4讲 图元绘制算法 1 Bresenham直线绘制算法 2 圆/弧的绘制算法 3 其它曲线的绘制算法

线画图元生成思想 线画图元生成指的是 线画图元生成的基本思想是 从图元的数学/参数表示形式(由用户按需要指定）转换成适于光栅系统显示所需要的点阵表示形式 1 2 4 5 3 y x 线的光栅表示 线的数学表示 象素 扫描线 6 线画图元生成的基本思想是 根据直线的数学/参数方程计算出落在直线段上或充分靠近它的一串像素，并以此像素集近似替代原来直线段，在屏幕上显示 也就是说：线段通过像素绘制，会产生台阶状；水平和垂直方向的台阶大小受像素的间隔(或分辨率)大小限制 具体实现时，在离散位置上对线段取样，并在每个取样位置上决定距线段最近的像素

图元像素编址 数字式设备通过绘制两端点间的离散点来显示直线段 图元像素编址(数学输入点到有限像素区域的映射) 要在屏幕上显示世界坐标系中指定对象的几何形状，需要调整数学输入点到有限像素区域的映射 线路径上离散坐标位置是从线段方程中计算出来的。其采用精确的世界坐标描述，其每一位置是数学上的一个无限小的点 屏幕像素坐标参考有限的屏幕区域，屏幕位置使用整数值，所以，绘制的位置仅是在两指定端点间的实际线段位置的近似 图元像素编址(数学输入点到有限像素区域的映射) 按对象边界与像素区域的覆盖量来调整显示物体的尺寸，即：对象与像素中心对准 将对象映射到像素间的屏幕位置，以使物体边界与像素边界对准

像素网格坐标 这个编址策略是依照像素中心给显示位置定址 扫描线从屏幕底部从零开始顺序编号 像素列则沿每条扫描线从左至右从零开始编号 其每个点的坐标位置在像素点的中心处 占据具有屏幕坐标位置(x,y)的一个像素的区域标识为中点位置在(x,y)处的单位面积

屏幕网格坐标 参考由相距为单位长的水平和垂直像素边界线组成网格的屏幕坐标，这样屏幕坐标位置是一对标定两像素间网格相交位置的整数值 假如坐标原点位于屏幕左下方，那么每个像素区域就可由左下角的整数网格坐标来指定 通常，将占据具有屏幕坐标位置(x,y)的一个像素的区域标识为对角位置在(x,y)和(x+1,y+1)处的单位面积

屏幕网格坐标 这种像素编址方案有很多优点：它避免了半整数像素边界，实现了精确的对象表示，并简化了包含在许多扫描转换算法和其它光栅程序的处理

Bresenham画线算法 由Bresenham提出的一种精确而有效的光栅线段生成算法，它可用于圆和其它曲线显示的整数增量运算 以单位x间距取样，需确定每个放样步长时哪两个像素位置更接近于线段路径 Bresenham算法引入“正比于两像素与实际线段点间偏移”的整型参量，采取对整型参量值的符号进行检测而选择两像素之一

Bresenham算法问题定义 先考虑具有小于1且大于0的斜率线的扫描转换过程 沿线路径的像素位置由以单位x间距的取样来决定 从给定线段的左端点(x0,y0)开始 逐步处理每个后继点(x位置)，并在扫描线y值最接近线段的像素上绘出一点

Bresenham算法问题定义 图示为过程的第k＋1步。 假如前一步确定的像素位置为：(xk,yk)；

Bresenham算法推导 在取样位置xk+1，用d1和d2来标识两个候选像素与线段数学路径点的垂直偏移。 在像素列位置xk+1处的数学线段点的y坐标可计算为： y = m(xk+1)+b = m(xk+1)+b (屏幕坐标为单位网格，有：xk+1= xk+1；yk+1= yk+1) 那么：d1=y-yk=m(xk+1)+b-yk； d2=yk+1-y =yk+1-m(xk+1)-b； 这两个分离点的差分为： d1-d2=2m (xk+1)-2yk+2b-1 (1) 设：△y和△x分别为端点的垂直和水平偏离量， 令：m=△y/△x，代入方程转化后得： pk=△x (d1-d2)=2△yxk-2△xyk+c (2) 方程(2)仅包含整数运算；参数c=2△y+△x(2b-1)是常量，与像素位置无关，且会在增量循环计算pk时被消除。

Bresenham算法的决策参数 根据算法推导，得到： pk=△x (d1-d2) =2△yxk-2△xyk+c pk称为画线算法中第k步的决策参数。 pk的符号与d1-d2的符号相同(△x＞0)。 基本起点 (xk,yk) 若pk大于零(d1>d2) 取高像素:yk+1=yk+1 若pk小于零(d1<d2) 取低像素:yk+1=yk yk xk yk+1 xk+1

Bresenham算法的决策参数 根据决策参数的符号，可判别第k+1步所选择的像素： 假如yk处像素比yk+1处像素更接近于线段数学点(即：d1＜d2)，那么，参数pk是负的，此时，选择绘制较低像素(xk+1,yk) 反之，假如yk+1处像素比yk处像素更接近于线段数学点(即：d2＜d1)，那么，参数pk是正的，此时，选择绘制较高像素(xk+1,yk+1) 基本起点 (xk,yk) 若pk大于零(d1>d2) 取高像素:yk+1=yk+1 若pk小于零(d1<d2) 取低像素:yk+1=yk yk xk yk+1 xk+1

Bresenham算法的增量处理 线画图元生成过程中，每一单位步长都会引起沿线段x和y方向坐标变化。因此，可利用递增整数运算得到后继决策参数值 在k步，决策参数为： pk =2△y · xk-2△x · yk+c 在k+1步，决策参数为：pk+1=2△y · xk+1-2△x · yk+1+c 上述两方程相减，可得到： pk+1-pk=2△y(xk+1-xk)-2△x(yk+1-yk) 由xk+1=xk+1，因而得到： pk+1=pk+2△y-2△x(yk+1-yk) 取决于参数pk的符号，yk+1-yk取0或1；也就是： 取高像素(xk+1,yk+1)（pk>0）： yk+1-yk=1，pk+1=pk+2△y-2△x； 取低像素(xk+1,yk) （pk<0） ： yk+1-yk=0，pk+1=pk+2△y。 起始像素位置(x0,y0)第一个参数p0从方程(2)及m=△y/△x计算出： p0=2△y-△x 在每个整数x位置，从线段的坐标端点开始，反复进行决策参数的这种递归运算

Bresenham算法生成过程 |m|＜1的Bresenham画线算法 ⑴. 输入线的两个端点，并将左端点存贮在(x0,y0)中； ⑶. 计算常量：△x、△y、2△y和2△y-2△x，并得到决策参数的第一个值：p0 = 2△y - △x； 屏幕显示过程 ⑷. 从k=0开始，在沿线的每个xk处，进行下列检测： 假如pk＜0，画下一点(xk+1,yk)， 且：pk+1= pk+2△y； 否则，下一待画点(xk+1,yk+1)， 且：pk+1=pk + 2△y-2△x。 ⑸. k=k+1； ⑹. 重复步骤4，共△x次。 像素生成过程

Bresenham算法示例 计算常量： 例：计算端点分别为(20,10)和(30,18)直线生成像素点坐标 斜率小于1，x方向取单位步长，选取y方向象素。 k Pk (xk+1, yk+1) 6 (29,17) 5 (24,13) 1 2 (28,16) (23,12) -2 (27,16) 7 (22,12) 3 14 (26,15) 8 (21,11) 4 10 (25,14) (20,10) k Pk (xk+1, yk+1) 6 (21,11) 5 (26,15) 1 2 (22,12) (27,16) -2 (23,12) 7 (28,16) 3 14 (24,13) 8 (29,17) 4 10 (25,14) (30,18)

Bresenham算法说明 斜率为正且大于1的线段： 只要交换x和y之间的规则，即沿y方向以单位步长步进并计算最接近线段路径的x连续值 起始端点： 当然，也能改变程序使之能从任何端点开始绘制像素，假如具有正斜率线段的初始位置是右端点，那么在从右至左的步进中x和y都递减 相同像素： 为了确信不管从何端点开始都能绘制相同的像素，当候选像素相对于线段的两个垂直偏高相等时(d1=d2)，总是选择其中较高(或较低)的像素 负斜率： 除非一个坐标递减而另一个递增，否则程序是类似的 特殊情况 水平线(△y=0)、垂直线(△x=0)和对角线|x|=|y|，它们都可直接装入帧缓冲器而无需进行画线算法处理

Bresenham算法通用规则 通过考虑xy平面各种八分和四分区域间的对称性，Bresenham算法对任意斜率的线段具有通用性 Increment x by 1 Increment x by -1 Increment y by 1 Increment y by -1 x =x-1 y =y-1 x = x-1 y = y+1 x =x+1 y =y+1

中点圆生成基本思路 直接利用光栅系统的Bresenham画线算法 但是，圆方程是非线性的：像素与圆周距离计算必须进行平方根运算 中点圆生成算法 思想：比较像素与圆距离的平方，避免平方根运算 通过检验两候选像素间中间点与圆周边界的相对位置(在圆边界内或外)，来选择像素

中点圆生成基本处理 给定半径为r和圆中心在(xc,yc)的圆 运用平移：先给出中心在坐标原点(0,0)圆像素位置的算法，然后通过将xc加到x和yc加到y，而把每个计算出的位置(x,y)移动到满足给定条件的屏幕位置 利用对称：在第一像限中，圆弧段从x=0到x=y，曲线的斜率从0变化到-1，因此，可先计算这八分圆上圆弧段的像素位置，而后利用对称性计算其它七个八分圆弧的位置 定义圆函数：fcircle(x,y) = x2+ y2 - r2 圆边界上任何具有半径r的点(x,y)满足方程： fcircle(x,y)=0。 任何点(x,y)的相对位置可由对圆函数符号的检测来决定： fcircle(x,y)＜0，(x,y)位于圆边界内; fcircle(x,y)＝0，(x,y)位于圆边界上; fcircle(x,y)＞0，(x,y)位于圆边界外。

中点圆生成算法原理 在中点算法中圆函数是决策参数 圆函数的检测在每个取样上对接近圆周的两个像素的中点进行，并可像在画线算法中一样为这个函数设置增量运算 决策参数是圆函数在这两个候选像素中点处求值： Pk = fcircle(xk+1,yk-1/2)=(xk+1)2+(yk-1/2)2-r2；或 Pk =fcircle(xk+1,yk-1+1/2) 候选 高像素 低像素 候选像素 中点 前一 像素 x2+y2=r2 第一象限上七分限内的圆弧 注意：此段圆弧斜率绝对值小于1，因此，x方向取单位步长；同时，x方向为增量，y方向是减量。 根据决策参数判断： 假如pk＜0，中点在圆内，高像素接近于圆边界 假如pk>0，中点位于圆外或在圆周边界上，选择低像素

其它曲线生成算法 常见曲线包括圆锥曲线、三角和指数函数、概率分布、通用多项式和样条函数 这些曲线的显示可采用类似于圆和椭圆函数来生成 直接从显式表示y=f(x)或参数方程中得到 用中点法绘制隐式函数f(x,y)=0曲线 直接逼近：直接方法是用直线段来逼近曲线－“以直代曲” 沿曲线轨迹等距的线端点位置可使用参数表示 按曲线的斜率选择独立变量从显式表示中生成等距位置 直线拟合： 可将曲线离散成坐标点数据集，用直线段来将离散点连结在一起，或采用线性或非线性回归来拟合数据组 利用对称： 利用函数对称性来减少曲线轨迹坐标位置的计算量

openGL中点的输出 (x，y)－帧缓存地址－像素颜色等 分辨率 H * V 每个像素1-N位 核心：快速计算Addr(x,y) 直线 曲线 多边形 像素阵列 字符 openGL中点的输出 (x，y)－帧缓存地址－像素颜色等 分辨率 H * V 每个像素1-N位 核心：快速计算Addr(x,y) glBegin(GL_POINTS) glVertex*(x,y); glEnd; 【glVertex 2/3i/f(v) 】

点的属性 大小 size 颜色 整数 Size>1的点就是一个方块 点 直线 曲线 多边形 像素阵列 字符 设置：glPointSize (size) 查询：glGetIntegerv (GL_POINT_SIZE, 　　　　　　　　 sizeValues); 颜色

注意 谁调用bresenham算法等？ 谁执行bresenham算法等？ openGL，directX（ WPF ），cocoa touch，swing。。。 画线、画多边形、填充、渲染函数。。。 谁执行bresenham算法等？ CPU GPU（显卡的核心） 硬加速：各种变换，3D效果，浮点运算，像素级并行。。。 通过专门的程序设计来充分利用其性能

把控制权交给OpenGL OpenGL OpenGL内核决定如何使用 支持OpenGL等 OS （显卡驱动） CPU 显卡上GPU 显示输出 PhotoShop Creative Suite 4 基于OpenGL的GPU加速 更好的支持3D等。

编程自由控制：多核和CUDA等 多核 多CPU单CPU多核单核多线程 软件配合（分配任务，负载均衡等）实现硬件上的并行 点 直线 曲线 多边形 像素阵列 字符 编程自由控制：多核和CUDA等 多核 多CPU单CPU多核单核多线程 软件配合（分配任务，负载均衡等）实现硬件上的并行 CUDA（Compute Unified Device Architecture，统一计算设备架构） 硬件：GPU+CPU，　CUDA ISA 软件：CUDA SDK，C 适于实现图形图像处理等各种密集型/并行数据计算 利用CUDA控制GPU，无需经由API（如openGL）

OpenGL画线 Glint p1[ ] = {x1,y1}, p2[ ] = {x2,y2}… 点 直线 曲线 多边形 像素阵列 字符 OpenGL画线 Glint p1[ ] = {x1,y1}, p2[ ] = {x2,y2}… glBegin(GL_LINES) GL_LINE_STRIP GL_LINE_LOOP glVertex2iv(p1); glVertex2iv(p2); glVertex2iv(p3); glVertex2iv(p4); glVertex2iv(p5); glEnd;