河南理工大学计算机图形学3章-1直线解读.ppt

第3章 二维图形生成 第3章 二维图形生成 第三章 二维图形生成技术 计算机图形学 第3章- * 计算机科学与技术学院 1 复杂的图形通常被看作是由一些基本图形元素（也 称图元）构成的； 2 基本二维图元包括点、直线、圆弧等； 3 点是由其坐标(x,y)来描述的。直线由其两端点坐标描述。折线是由构成它的顶点序列描述； 4 所有图形的输出都归结为设备上的光栅像素点亮，或者设备的动作； 5 基本图形除了位置信息外，还描述了图元的一些属性信息，比如线宽、线型、颜色、填充图案等。 §3.1 直线图形生成 §3.2 圆及二次曲线生成 §3.3 区域图形填充 §3.4 字符生成 §3.5 反走样 §3.1 直线图形的生成 一、直线生成算法 直线的生成算法基本思想是折线逼近直线，根据逼近的方式分为模拟逼近和插值逼近两种方式。 1.模拟逼近：模拟人的绘图过程，把动作进行分解为基本动作，然后进行过程模拟，适应于绘图机。 2.插值逼近：在直线两端点之间进行差值计算，然后在端点之间插入相应的点，适用于显示器。 3.常用算法：逐点比较法、数值微分法、 中点画线法和Bresenham算法等。 1．DDA算法（数值微分法） 本算法是根据直线的微分方程来画直线。 设直线从起点Ps（xs, ys）到终点Pe(xe, ye ), 令：Δx=(xe-xs)，Δy=(ye-ys) k=Δy/Δx 方程：y=ys+k(xe-xs) xi+1=xi +Δx yi+1=yi +Δy Δx,Δy 为增量 xi+1=xi +Δx yi+1=yi +Δy Δy=m·Δx 若0k1 , Δx=1 xi+1=xi +Δx=xi+1 yi+1=yi +Δy=yi+k 取 整 1a 1b 2b 3b 4b 2a 3a 4a 其中令 Δt = max(|Δx| ，|Δy|) 若取时间步长为：1/Δt， 则递推公式： xi+1=xi +Δx/Δt yi+1=yi+Δy/Δt 1a 2b -1 区域 Δx Δy 1b m 2a 1 m 1/m 1 -1/m 1 3a -1 -m 把平面分为四个象限，每个象限分两部分，即8个区域。 第一象限： 1) 当k1,且|Δx||Δy|时， |Δx|=1,|Δy| =k 2) 当k1, 且|Δx||Δy|时， |Δy|=1，|Δx|=1/k 即1b区域 即1a区域 2．逐点比较法(模拟) 生成过程： 逐点比较法算法思想 开始 偏差判别 走步 计算偏差 终点判别 N 结束 Y 算法思想：在绘图的过程中，把每画一笔(走一步)都和标准图形进行比较，然后 确定下一步的走向，用步步逼近的方法画出规定图形。图示如下： 逼近约定： 1） 步长：小于0.1mm； 2）方向：上下左右。 算法步骤： 1) 设定在不同象限中的走步方向：下图（右） 原则：①使逼近的误差最小; ②使走笔方向和画图的趋势一致。 X Y 2) 从起点出发开始画线：开始抬笔到起点。 3) 偏差计算：计算当前点相对于直线的位置偏差。 ①一般方法:(第一象限） 设定线段OA，笔位于M点，A(Xa,Ya)，M(Xm,Ym)。 算法思路: 位置判断→角度比较→数学计算 则OA和OM斜率分别为： dA=tgα= Ya/Xa dM=tgβ= Ym/Xm M点偏差值d为： d=tgβ-tgα=Ym/Xm-Ya/Xa=(YmXa-YaXm)/XmXa ∵ XmXa0 ∴ 令 Fm= YmXa-YaXm 偏差判别式 若 Fm0，βα，点M位于直线上方， M2，走X+。 Fm=0，α=β，点M位于直线上， M0，走X+。 Fm0，βα，点M位于直线下边， M1，走Y+。 即 Fm≥0，β≥α，点M位于直线上方， M2，走X+。 Fm0，βα， 点M位于直线下边， M1，走Y+。 两乘除一加减 在图中，计算点从M1到M3的走步过程和偏差判别式： 当点M1→M2时，Fm0 ，令沿Y+走一步距