第5章 基本图形生成算法--第一讲.ppt

第五章 基本图形生成算法 圆弧、椭圆弧光栅化 直线段的光栅化 如何在光栅化输出设备上根据数学坐标描述构造基本的二维几何图形（点、直线、圆、椭圆等）输出。 问题的提出： 内容回顾 LineTo，Polyline DDA算法（数值微分法） 第一讲 直线段的光栅化 算法目标： 中点Bresenham画线法 确定最佳逼近于该直线段的一组像素，并且按扫描线顺序，对这些像素进行写操作。 Bresenham算法 直线段的光栅化－－ DDA方法 一般算法起始思想 直线方程y = kx + b 直观、简单； 每一步需要一次浮点乘法和舍入运算、效率较低。 x = x0 + 1 y = kx + b 每个栅格点(x, round(y)); (x0,y0) (x1,y1) 给定一个直线的屏幕起点、终点像素坐标(x0, y0), (x1, y1)--(整数)； x = x0 x1 沿着x取整 取像素栅格x步距为1 k = y1 - y0 x1 - x0 = ?y ?x 直线段的光栅化－－ DDA方法 直线的微分方程 y1 x y y0 DDA方法： y1 - y0 x1 - x0 = = k dy dx = (5-1) ?y ?x 增量算法：一种迭代算法，每一步的操作在上一步的基础上加一个增量来获得。 假设k0, 需要分成两种情况考虑： 保证了图元的 不间断像素表示。 0k ≤ 1, k1, X方向像素变化大，以x的增量为光栅化增量 Y方向像素变化大，以y的增量为光栅化增量 直线段的光栅化－－ DDA方法 y1 x y x1 x0 y0 x和y的增量表示： DDA方法： 先考虑0k≤1的情况： yi+1 xi+1 = xi+ 1 即：当x每递增1，y递增k(即直线斜率)； 取像素策略：对每个点的下一个点，取点（xi+1, round(yi+k) ) ?y = k?x， = yi+ ?y = yi+k (5-2) 取?x=1， 则?y=k， 直线段的光栅化－－ DDA方法 DDA方法： y1 x y x1 x0 y0 x和y的增量表示 当k1的情况： 取dy =1 即：当y每递增1，x递增1/k; 取像素策略：对每个点的下一个点，取点（ round(xi+k) , yi+1) (5-3) dx = dy k yi+1 = yi+ 1 xi+1 = xi+ ?x dx = 1 k = xi + 1 k max(|△x|,|△y|)=|△x|，即|k|≤1的情况： max(|△x|,|△y|)=|△y|，此时|k|≥1： 直线段的光栅化－－ DDA方法 DDA方法： xi+1 = xi + 1 yi+1 = yi + k _ _ xi+1 = xi + yi+1 = yi + 1 _ _ 1 k (5-4) (5-5) 直线段的光栅化－－ DDA方法 特点： 直观、易实现； y、k必须是float，不利于硬件实现； 增量算法，利用了上一次判断的计算结果，速度较快； 直线段的光栅化－－ 中点Bresenham画线法 基本原理 假定：直线斜率0K1， 且已确定上一个像素点P（Xp ,Yp ） 下一个与直线最接近的只能是P1点或P2点。 设M为中点，Q为交点 P（Xp ,Yp ） Q M P1 P2 现需确定下一个点亮的像素是P1还是P2 当M在Q的下方 M在Q的上方 M与Q重合， P1、P2任取一点。默认取P1点 如何确定M在Q的上方还是下方？ Q P2离直线更近 取P2 P1离直线更近 取P1 直线段的光栅化－－ 中点Bresenham画线法 基本原理 直线方程变成以x, y为自变量函数，为 F(x, y) = y -kx - b = 0; x y x y F(x, y) 0 F(x, y) 0 F(x, y) 0 F(x, y) = 0 F(x, y) 0 F(x, y) 0 F(x, y) 0 ∴欲判断M点是在Q点上方还是在Q点下方，只需把M代入F(x,y),并检查它的符号。 F(x, y) = 0 判断平面上任意一点(x, y)和直线之间的关系： 点在直线上 点在直线上方 点在直线下方 直线的扫描转换－－ 中点Bresenham画线法 构造判别式 P（Xp ,Yp） Q M P1 P2 = F(M) = F(Xp+1, Yp+0.5) = (Yp+0.5) - k