Computer Graphics

浏览量:22,955

区域填充算法和多边形填充的扫描线算法

本文主要介绍几种区域填充算法,重点解释多边形的扫描线填充算法,最后实现了多边形填充算法,包括在附录文件中。在参考【5】中,作者详细介绍了一系列区域填充算法,可以查看相应网页。代码的下载地址为:https://github.com/twinklingstar20/twinklingstar_cn_region_polygon_fill_scanline/ 1. 1.      区域的定义和填充 1.1   像素定义的区域(Pixel-Defined Region) 1.1.1        边界定义区域(boundary-defined) 定义某些像素是边界,边界包围着一块区域。填充所有在边界内的相连通的像素,主要分下面几个步骤: 从区域内部一个像素点开始 判断这个像素是否是一个边界像素点或者已经被填充了 如果都不是,就把它填充,然后开始设置邻居像素点。 用图片演示这个过程,如下面的幻灯片所示,代码片段如下所示: void boundaryFill4 (int x, int y, int fill, int boundary) { int current; current = getPixel (x,y); if (current != boundary && current

spacer
浏览量:3,600

布雷森汉姆直线算法

本篇文章,主要介绍布雷森汉姆直线算法,包括一个用glut实现的demo。代码的下载地址为:https://github.com/twinklingstar20/twinklingstar_cn_demo_bresenham-line-algorithm 一.             布雷森汉姆(Bresenham)算法说明 图1. 在显示器上绘制直线 如图1所示,在显示器上绘制一条直线,直线上一些像素会被启动,由此形成一条直线效果。直线绘制算法是图形学中的一个基本的算法,绘制直线时需要考虑哪些像素需要被启动,这里介绍布雷森汉姆直线绘制算法。它是一种基本的递增算法,基于前一个像素信息就可以计算出下一个像素值,能确定一条直线上哪些像素要启动,而且它的计算只采用整数值,避免了浮点运算运算。 布雷森汉姆算法有几种变种,这里考虑其中的一个中点算法。假设现在要绘制两个端点是(ax,ay)和(bx,by)之间的线段,需要确定介于它们之间的像素序列。为了简化讨论,这里考虑一种特殊的情况,即ax<bx,直线斜率0<k<1的情况。线段的宽是W=bx-ax,高是H=by-ay,则有W>H,所有穿过两个端点的直线都满足下面的一个等式: -W(y-ay)+H(x-ax)=0 定义一个函数如下所示: F(x,y) = -2W(y-ay)+2H(x-ax) 如果F(x,y)>0,则说明(x,y)位于直线下;如果F(x,y)<0,则说明(x,y)位于直线上。 图2. 中点算法的一个参数 图中所示,假设从黑色点(Px,Py)处开始考虑算法,现在考虑在Px+1的位置上,Y方向上最合适的值是Py +1还是Py,即U(Px+1, Py+1)还是L(Px +1,Py)。接着是要判断Q点更靠近U还是L,可以通过计算中间值M(Px+1,Py+1/2),可以使用上面所说的等式,如果F(Mx,My)<0,则点M在直线上,选择L点;如果F(Mx,My)>0,则点M在直线下,选择U点,Y方向上加1。 F(Mx,My)=-2W(Py+1/2-ay) + 2H(Px+1-ax) 接下来,当X方向上的值是Px+2时,判断现在的M取值是M’还是M’’。如果前面一步选择的是L点,则取M’(Px+2,Py+1/2);相反,如果前一步选择的是U点,则取M’’ (Px+2,Py+3/2)。    所以分下面两种情况讨论: 1)  如果前一步F的值是负的,则有Fnext=F(Px+2,Py+1/2)=-2W(Py+1/2-ay) + 2H(Px+2-ax) = F(Mx,My)+2H 2)  如果前一步F的值是正的,则有 Fnext=F(Px+2,Py+3/2)=-2W(Py+3/2-ay) + 2H(Px+2-ax) = F(Mx,My)+2(H-W) 初始情况下M=(ax+1,ay+1/2),则有F(x,y)=-2W(ay+1/2-ay)+2H(ax+1-ax)=2H-W,如果这里没有乘以2的话,就会有浮点数存在了。总结下算法流程就是: 1)  初始化F=2H-W,x=ax,y=ay

spacer