Monthly Archives: November 2013

累积缓冲区

经过《锯齿与抗锯齿技术介绍》和《随机采样和分布式光线追踪》两篇文章的铺垫,现在介绍一种图形学中较高级的主题,就是累积缓冲区。读这篇文章前,假设你们对图形学的顶点处理管线,glFrustum()和gluPerspective()之间的关系等都很熟悉。文章首先会简单的介绍下OpenGL中的几种缓冲区和基本的清除缓冲区的操作,接着介绍下OpenGL中操作累积缓冲区的接口使用方法,最后介绍如何使用累积缓冲区完成抗锯齿(anti-alias)、运动模糊(Motion Blur)和深度场(Depth Field)的特效。在文章最后,使用glut库,提供了三种特效实现的程序。 示例代码下载地址:https://github.com/twinklingstar20/twinklingstar_cn_demo_accumulation_buffer/ 一. OpenGL中的缓冲区 1.1   缓冲区分类: OpenGL系统通常有以下几种缓冲区: (1)颜色缓冲区 OpenGL的颜色缓冲区主要有:front-left,front-right,back-left,back-right和一些辅助颜色缓冲区。我们绘制的图像就是存储在颜色缓冲区中,它可以存储颜色索引、RGB颜色数据以及alpha值,如果一些OpenGL实现支持立体渲染(stereoscopic rendering,立体的概念参见【6】,举个与立体3D的应用,例如3D电影或者3D显示器,戴上带有偏振效果的眼镜可以看立体电影),会有存储左右眼图像的左缓冲区和右缓冲区,相反,如果不支持立体渲染,则只有左缓冲区。在支持双缓存的系统中会有前缓冲区和后缓冲区,而单缓冲区系统只有前缓冲区。OpenGL可能还支持一些不用于显示的辅助颜色缓冲区,OpenGL并没有规定那些缓冲区的用途,所以你可以随意的使用那些缓冲区(前提是如果有)。 (2)深度缓冲区 深度缓冲区存储每个像素的深度值,深度值用于存储物体与人眼的距离,深度值越大的像素会被深度值小的像素覆盖,深度缓冲区有时候也称为Z缓冲区。 (3)模板缓冲区 模板缓冲区的一个应用就是限制屏幕上可显示的区域,举个例子,如果你要存储一个形状奇特的挡风玻璃,你只需要模板缓冲区存储这个挡风玻璃的形状,接着绘制整个屏幕,只有挡风玻璃所在区域中的内容会显示出来,这就是模板缓冲区的功能。 (4)累计缓冲区 后面会详细介绍。 1.2   清除缓冲区 在图形程序当中,清除缓冲区的开销非常的大,在一个1280*1024的显示器,就有上百万个像素。OpenGL专门设计了清除缓冲区的命令,充分利用体系结构的特点来解决这个问题。清除缓冲区,分两步走战略: (1)指定要用什么值来填充要清除的缓冲区,例如颜色缓冲区中所有的像素值都用(0,0,0)填充等,指定不同缓冲区值的方法如下所示,单从名字就可以看出指定哪类缓冲区要填充的值了。各个函数具体的参数和使用方法,可以参考【4】中的文档。 void glClearColor(); void glClearIndex(); void glClearDepth(); void glClearStencil( ); void glClearAccum(); (2)选择待清除的缓冲区并开始清除,OpenGL实现这个功能的函数如下所示,具体可以参考【4】中的文档。 void glClear(GLbitfield mask); 下面举个清除颜色缓冲区和深度缓冲区的例子,演示这清除的整个步骤,如下面的代码片段所示: glClearColor(0.0, 0.0,

spacer

3D场景的漫游,纹理装载

下载内容: (1)       实现了两种摄像机漫游类和OpenGL纹理装载类 (2)       参考NEHE中提供的教程,实现了个简单的DEMO。 (3)       下载地址:https://github.com/twinklingstar20/download_fly_camera_texture_load 下载说明: 1. 摄像机漫游类的设计 共有两个,SrCameraBase和SrCameraEdit,它们是相互继承的关系,但是它们实现的摄像机漫游的方式不同。这三个类,实现的功能有视口的设置,透视投影的设置和摄像机的设置。 SrCameraBase提供了基本的摄像机漫游的功能,就像CS游戏中人物的漫游方式一样,可以上下左右前后移动,并且旋转。它的定义如下所示,其中涉及到相机坐标的计算,这几个矩阵在《顶点渲染管线》文章中的视点坐标那块有介绍,要注意的就是该小节说的OpenGL矩阵顺序的问题。 /* \brief Setting some configuration of the tranformations and the camera,including view port transformation, projection transformation(only perspective transformation). This class provides with a simple to fly a camera

spacer

四元数

重新看了三年前写的文章,感觉很多叙述并不到位,重新更新了一篇博客《三维旋转》,里面有更加清晰的介绍。 对于四元数的概念也许大家不太熟悉,这里介绍下四元数概念,四元数、矩阵和欧拉角之间的关系,四元数球面插值的概念。 一. 四元数 1.1 四元数的概念 四元数是由爱尔兰数学家威廉•卢云•哈密顿在1843年发现的数学概念,在图形学中有重要的应用。在3D程序中,通常用四元数来计算3D物体的旋转角度,与矩阵相比,四元数更加高效,占用的储存空间更小,此外也更便于插值。 可以把四元数看做一个标量和一个3D向量的组合。实部w表示标量,虚部表示向量标记为V或三个单独的分量(x,y,z),则四元数可以记为或。正规化四元数可以表示为: 在三维中,可以用四元数表示绕着某个轴的旋转,如下公式所示: α表示旋转的角度,cos(βx), cos(βy) 和cos(βz)表示定位旋转轴的方向余弦 根据欧拉旋转定理,任何两个坐标系的相对定向,可以由一组四个数字来设定;其中三个数字是方向余弦,用来设定特征矢量(固定轴);第四个数字是绕着固定轴旋转的角值。这样四个数字的一组称为四元数。上面这段话阐述了四元数的原理:三维空间内所有的旋转都可以用四个数来表示。在通过四元数方法来计算旋转,已经替代了方向余弦方法,这是因为它能减少所需的工作,和它能减小舍入误差。在电脑图形学里,四元数与四元数之间,简易执行插值的能力是很有价值的。 1.2 旋转矩阵 旋转矩阵(Rotation Matrix)与一个向量相乘,会改变向量的方向但不改变大小的效果。旋转可分为主动旋转与被动旋转。主动旋转是指将向量逆时针围绕旋转轴所做出的旋转。被动旋转是对坐标轴本身进行的逆时针旋转,它相当于主动旋转的逆操作。在三维空间中,旋转矩阵有一个等于单位1的实特征值。只用三个实数就可以指定一个 3 维旋转矩阵。生成旋转矩阵的一种简单方式是把它作为三个基本旋转的序列复合。关于右手笛卡尔坐标系的 x-, y- 和 z-轴的旋转分别叫做 roll, pitch 和 yaw 旋转。因为这些旋转被表达为关于一个轴的旋转,它们的生成元很容易表达。 1.2 欧拉角 图1 欧拉角表示 设定 xyz-轴为参考系的参考轴,称 xy-平面与 XY-平面的相交为交点线,用英文字母(N)代表。zxz 顺规的欧拉角可以静态地这样定义:(1)a 是 x-轴与交点线的夹角;(2)B是 z-轴与Z-轴的夹角;(3)r 是交点线与X-轴的夹角。 欧拉角来描述刚体在三维欧几里得空间的取向,如图1所示。对于任何一个参考系,一个刚体的取向,是依照顺序,从这参考系,做三个欧拉角的旋转而设定的。所以,刚体的取向可以用三个基本旋转矩阵来决定。换句话说,任何关于刚体旋转的旋转矩阵是由三个基本旋转矩阵复合而成的。对于在三维空间里的一个参考系,任何坐标系的取向,都可以用三个欧拉角来表现。参考系又称为实验室参考系,是静止不动的。而坐标系则固定于刚体,随着刚体的旋转而旋转。

spacer

八叉树颜色量化

本文简单的介绍了颜色量化的几种方法,重点介绍八叉树颜色量化算法,并实现了该算法。算法实现的下载地址(参见下载)。 一. 颜色量化介绍(Color Quantization) 计算机图形学中,常采用的一种方法是把颜色看成是基于红、绿、蓝三种颜色的混合,也可以采用色度、彩度、亮度等描述颜色,用多种不同的描述符来表示颜色,就称为颜色模型(Color Model),如果有人能量化这三种不同的描述符的数值,就可以用一个三元组来表示一种颜色,例如(r,g,b),这就形成了一个描述颜色的三维坐标系统,选择不同的颜色模型能形成不同坐标系统,坐标系统上所有颜色的集合就称为颜色空间(Color Spaces)。 在图形学中,颜色量化是为了减少一张图像中的颜色数并且使用它尽可能的与原始图像一样,在一些由于内存限制只能显示有限颜色的设备上,颜色量化就显得特别的重要,根据参考【5】的总结,介绍几种颜色量化方法,最后重点介绍八叉树颜色量化方法。 1.1   统一颜色量化(Uniform Quantization) 在RGB颜色模型,颜色可以表示成三维空间中的一个坐标,颜色空间可以表示为X,Y,Z轴都在范围的值,这样颜色空间就相当于一个正方体。统一颜色量化的基本思想就是独立的看待颜色空间中的每个坐标轴,把它们平均分成N条线段,这样就能形成一个个小方块,每个方块当作一种颜色。有时候把红和绿的坐标轴分成8段,把蓝色的坐标轴分成4段,这样就可以生成256个小方块,即256种颜色;除此之外,当然还有别的划分方法,例如可以把红色和蓝色分成6段,绿色分成7段,这样就能产生252种颜色。每个方块内的颜色值,可以取该方块所有颜色值的平均值。这种方法实现非常的简单快速,但是产生的结果并不好。 1.2   流行色算法(Popularity Algorithm) 通过某种颜色在图像中发生的频率来进行颜色量化,频率越高的赋予越大的优先级,这种方法不考虑常用的颜色之间是否是相似的,即可能频率较高的几种颜色很相近,但是确实又有不同的颜色坐标。流行色算法基本的做法通过两次扫描来处理:第一次扫描图像,创建一个包括颜色和颜色计数的表,以颜色计数从大到小排序,选择前K种颜色作为这张图像的调色板,别的颜色都丢弃掉;第二次扫描,需要计算图像上的颜色在调色板上的索引值,例如颜色(red,green,blue),通过计算它与调色板上所有颜色距离的平方值dist,找到dist值取最小时的索引i值,就是图像上该种颜色的索引值。 dist=(red - red )^2 + (green - green )^2 + (blue - blue )^2 1.3   中值切割法(Median Cut Algorithm) 与统一颜色量化方法有些相似,也是把颜色空间分成K个子块,使得每个了块尽可能的估计出相同数量的颜色。为了简化说明,这里用二维的平面来解释这个过程,如下图所示。原始图像上的颜色值放到颜色坐标系统上,沿着它最长的维度的中位数位置分成两半,剩下的子块按照类似的方法进行处理,得到右边那张图所示的结果。注意:中位数跟中点不是相同的概念。 图1. 中值切割 算法的基本过程如下所示: (1)       找到包含所有图像颜色的最小方块 (2)      

spacer

TGA文件格式解析

本文主要介绍TGA文件格式的解析,在网上找到了一篇Truevision提供的TGA文件解析的文档,这里对它的部分内容进行翻译,具体代码实现的下载网址(见下载),在该下载页面上也提供了英文原文件,代码测试通过了参考【3】中提供的所有TGA图像文件。 一.   介绍 图1 TGA 文件格式 如图1所示,新的TGA文件包含5个区域:(1)TGA文件头(TGA File Header);(2)图像/颜色表数据(Image/Color Map Data);(3)开发者区域(Developer Area);(4)拓展区域(Extension Area);(5)TGA文件注脚(TGA File Footer)。最后3个区域是在1980年9月以前增加的,所以1989年9月以前的TGA文件格式称为旧生版本TGA文件格式,1989年9月以后的则称为新版本的TGA文件格式。接下来介绍TGA文件格式中涉及的几种类型的颜色。 伪彩色(pseudo-color)图像的每个像素值实际上是一个索引值或代码,该代码值作为色彩查找表CLUT(Color Look-Up Table)中某一项的入口地址,根据该地址可查找出包含实际R、G、B的强度值。这种用查找映射的方法产生的色彩称为伪彩色。用这种方式产生的色彩本身是真的,不过它不一定反映原图的色彩。在VGA显示系统中,调色板就相当于色彩查找表,从16色标准VGA调色板的定义可以看出这种伪彩色的工作方式。伪彩色图像是每个像素的颜色不是由每个基色分量的数值直接决定,而是把像素值当作彩色查找表的表项入口地址,去查找一个显示图像时使用的R,G,B强度值,用查找出的R,G,B强度值产生的彩色称为伪色彩。 真彩色(true-color)是指图像中的每个像素值都分成R、G、B三个基色分量,每个基色分量直接决定其基色的强度,这样产生的色彩称为真彩色。例如图像深度为24,用R:G:B=8:8:8来表示色彩,则R、G、B各占用8位来表示各自基色分量的强度,每个基色分量的强度等级为2^8=256种。图像可容纳2^24=16M种色彩。这样得到的色彩可以反映原图的真实色彩,故称真彩色。例如,用RGB 5:5:5表示的彩色图像,R,G,B分量大小的值直接确定三个基色的强度,这样得到的彩色是真实的原图彩色。 调配色(direct-color)的获取是通过每个像素点的R、G、B分量分别作为单独的索引值进行变换,经相应的色彩变换表找出各自的基色强度,用变换后的R、G、B强度值产生的色彩。 调配色与伪彩色相比,相同之处是都采用查找表,不同之处是前者对R、G、B分量分别进行查找变换,后者是把整个像素当作查找的索引进行查找变换。因此,调配色的效果一般比伪彩色好。 调配色与真彩色比,相同之处是都采用R、G、B分量来决定基色强度,不同之处是前者的基色强度是由R、G、B经变换后得到的,而后者是直接用R、G、B决定。在VGA显示系统中,用调配色可以得到相当逼真的彩色图像,虽然其色彩数受调色板的限制而只有256色。 二.   文件结构分析 2.1     TGA文件头(TGA FILE HEADER) 图像信息字段长度(ID length)– 字段1(1个字节): 这个字段规定了包含在字段6(Image ID字段)中的字节数,最大的字符数是255,它的值为0,则表示在这个文件中没有图像信息字段。 颜色表类型(Color Map Type)– 字段2(1个字节): 当前已定义的有两个值0或者1,0 表示没有颜色表(color

spacer

八叉树颜色量化、BMP、TGA文件解析

下载内容: (1)       C++程序:实现了八叉树颜色量化,写BMP文件和读BMP文件,写TGA文件和读TGA文件三个功能; (2)       对BMP文件格式和TGA文件格式较完整的叙述的英文文档   (3)       下载地址:https://github.com/twinklingstar20/octree-bmp-tga/ 下载说明: 在写BMP文件时,使用到八叉树颜色量化的方法。而BMP文件格式的解析,从网上可以找到很多这样的博客,比如CSDN上的博客【1】,这里不再描述BMP文件结构。 这里特别说明一点是在代码的实现中,对于每个像素用15bit或者16bit表示的情况。常规的方法,解析出来的RGB颜色值是5位的,把它左移3位就可以。采用参考【2】中的方法,如下所示,在左移3位后,同时在尾部加上一些附加位。具体的说明可以参见相应的博客。 result.r = (result.r << 3) | (result.r >> 2); result.g = (result.g << 3) | (result.g >> 2); result.b = (result.b << 3) | (result.b >> 2); 对TGA文件格式的解析,可以参见本网站上的博客《TGA文件格式解析》。  对八叉树颜色量化方法,可以参见本网站上的博客《八叉树颜色量化》。

spacer

随机采样和分布式光线追踪

本文主要叙述了论文【3】【4】中的两个方法,一种是随即采样,一种是分布式光线追踪方法,在介绍随机采样方法前,由泊松圆盘采样引入。 一.泊松圆盘采样(Poisson Disk Distribution) 一个采样位置不均匀分布的例子就是眼睛,眼睛有有限数量的光感受器,就像其它采样过程一样,应该是有一个奈奎斯特极限(Nyquist limit),但是眼睛正常情况下是不会发生锯齿现象的。在眼睛的中央窝(Fovea)中,六边形图案的细胞是紧密排列起来的,晶状体就扮演着低通滤波器的作用,这就避免了锯齿的发生。但是在中央窝外部,细胞的排列都很稀疏,所以采样率是很低的,然而在那里却也没有发生锯齿,原因就是通过细胞的不均匀分布来避免这个区域发生锯齿。 已经有人过研究眼睛中视锥细胞的分布,与人眼相似,光感受器在猴子眼睛的中央窝外部的分布如图1所示,这样一个分布称之为泊松圆盘分布:采样点随机分布在一定的范围内且任意两个采样点之间的距离不小于某个值。距离的最小值能限制噪声的数量,举个例子,胶片颗粒(Film Grain)就是随机分布的,如图2所示,但是没有像泊松圆盘分布一样有最小距离的限制,而是采用纯随机分布。造成的结果就是一些样本点会集中一些区域而在其它的某些区域留下大量空白,所以胶片(Film)没有锯齿,有噪声(Noise)存在。 图1. 猴子眼睛中光感受器的分布 图2. 胶片颗粒 一种简单的实现泊松圆盘分布的方法是:(1)随机生成采样位置,如果随机生成的采样位置与已经选择过的距离小于一给定值,则丢弃它,至少采样区域满为止,采用这种方法可以创建一个查询表(Lookup Table);(2)还需要计算滤波器的值,该值描述了每个采样点与周围的像素点的关系。位置信息和滤波器的值存储在一个查询表中,这种简单的方法确实能产生很好的图像效果,但是要求有一个非常大的查询表。因此这里引入另外一种技术:抖动。 二. 随机采样(Stochastic Sampling) 抖动技术也可以称在采样位置中加入一些噪声,它是随机采样的一种形式,是一种逼近泊松圆盘分布的技术。抖动技术又有很多种类型,这里主要介绍规格网格的抖动技术,这种技术能产生较好的实验结果并且很适用于图像渲染算法。抖动可以使得高频信号降低,但是降低的高频信号中的能量会出现在噪声中而不会消失,因此基本的光谱组合没有发生变化。与纯种的泊松圆盘分布技术相比,该技术可能会造成更多的噪声,而且可能会留下部分锯齿。 举个抖动的例子,计算时间抖动(Time Jitter)的效果,第n个样本抖动ζn的量,所以会在nT+ζn的位置采样,T表示采样周期,如图3所示,就是时间抖动的效果。可以采用不同的模型来表示抖动量ζn,比如用方差是σ2的高斯分布函数,增益量就可以为频率μ的函数,如下等式所示: 图3时间抖动 把一个像素看成是一个网格,或者由多个子像素(subpixel)网格构成的大网格,这样就是一个二维的抖动。噪声随机的加到X方向上的位置或者Y方向上的位置,X,Y方向相互独立,就相当于是两个一维的抖动构成的,要求使得每个采样点发生在某个像素网格范围内的随机位置上。如果已知道哪些采样点是可见的,则通过重构过滤器(Reconstruction Filter)对那些采样点的值进行处理。重构过滤器的实现方法是一个开放性的问题,最简单的重构过滤器是箱式滤波器(Box Filter):取多个采样点的平均值。也可以采用加权重构滤波器,这种情况下,滤波器是一个采样位置与周围像素相关的加权值。每个像素是附近采样点的值乘以加权值的总和,这些滤波器可以提前计算好保存在一个查询表中。 总结下随机采样的步骤:(1)加入随机抖动的采样样本;(2)重构过滤器重构该像素值。 三. 分布式光线追踪(Distributed Ray Tracing) 3.1 分布式光线追踪的概念和作用 它不是在分布式系统上的光线追踪,而是一种基于随机、分布式、超采样的光线追踪方法,解释下这里面有几个关键词的意思,如图4所示: (1)超采样,传统的光线追踪,是一个像素对应一条光线,而分布式光线追踪是一个像素多个采样点,所以一个像素就有多条光线,不限于图中所示的9条; (2)随机性,其实图4表示分布式光线不太准确,因为几条光线都是均匀分布的,由于本人比较懒就不画新的图片演示了,分布式光线中说的几条光线是随机的分布在一个像素方格内。 传统的光线追踪方法能产生较严重的锯齿,使得渲染出来的图像并不是自己想要的。而且在真实世界中,产生的图像不并像计算机产生的世界那样完美,即真实世界中,几何模型的边界棱角可能是模糊的,阴影的显示也有一个过渡过程。基于这个需求,分布式光线追踪这种技术应运而生,它是一种尽可能逼近这种效果的技术。 图4 分布式光线追踪 计算机图形学尝试将一个真实的世界显示在一个视频显示器上,真实的世界是由无穷多个像素组成的,但是显示器的光栅显示有像素数量的限制,显示器上的每个像素只能覆盖场景中的某个区域,所以像素值必需是该区域的估计。传统的光线追踪方法,每个像素只有一条光线穿过,依靠它来获取真实的世界中值,这种方法很简单,但是不精确。相反,如果采用多条光线的话,这个效果就不言而喻了。 3.2 着色模型 场景上一个点的光照强度值用数学解析函数可以表示成发光函数(Illumination Function)和反射函数(Reflectance

spacer

锯齿与抗锯齿技术介绍

本文主要介绍锯齿产生的原因,几种简单的抗锯齿技术,像前置滤波,后置滤波,基于光线追踪的抗锯齿技术中的一种。这篇文章是为后面介绍分布式射线追踪(Distributed Ray Tracing),随机采样(Stochastic Sampling)和累积缓存(Accumulation Buffer)作铺垫。 一.    锯齿的介绍 锯齿的概念最早出现在信号采样的采样理论中,以一定频率离散的采样一个信号,如果采样频率不够大就会发生锯齿。如图(1)所示的两个sine波,圆圈表示采样点。对(a)图中的sine波以图中所示的采样频率采样,足以构造出原始的sine波;对(b)图中的sine波以同样的采样频率采样,构造出来的sin波的频率就会降低,这就是一个锯齿信号(Aliased Signal)。奈奎斯特定理(Nyquist Theorem)就指出,为了精确的重构原始的信号,采样频率必需是原始信号中最高频率的两倍。在给定采样频率的条件下,能精确重构的信号中的最大频率是奈奎斯特极限(Nyquist Limit),即对所有在极限范围内的信号以给定的采样频率采样,可以精确的重构出原始信号,对超过那个范围的信号就会发生锯齿,出现下图的情况了。 图1. 在奈奎斯特极限范围内和范围外的点采样 在图形学范畴中,像素是一个个离散的点,在显示器上的光栅显示就相当于对图像进行采样,对于给定分辨率的显示器相当于给定了采样频率。如果要显示的图像的最高频率超过了奈奎斯特极限,就会发生锯齿,在图形学中称之为jaggies,翻译成中文也是锯齿的意思。 最好的避免锯齿的方法是要有足够大的采样频率,例如针对图形学来说,就是要有足够大的分辨率。但在多数情况下,并不能满足这个条件,所以就需要采用一些其它技术来解决这个问题。 显示器清晰度不够,能产生锯齿,使用一些高清显示器就可以解决这个问题,但这里叙述几种在显示器清晰度不够的情况下解决锯齿问题的技术,处理锯齿问题的方法称为抗锯齿技术。 二.    抗锯齿技术 图2. 未使用抗锯齿技术,使用抗锯齿技术和使用基于sinc过滤器的抗锯齿技术 图2(a)显示了图片未使用抗锯齿技术时发生失真,越靠近图片顶部,棋盘格子越小,图片越难以辨识;而图2(b)采用了一种抗锯齿操作,靠近顶部的棋盘逐渐变在灰色,在屏幕分辨率不足以显示远处的格子时,这种效果更加可接受,而越近的格子也越光滑;图(c)使用了另外一种抗锯齿算法,是基于sinc过滤器的抗锯齿算法,能达到比图片(b)更好的效果。 还有一些抗锯齿技术,像将图像模糊(bluring),根据Nyquist采样理论,是给定采样频率,通过降低原始信号的频率来使得信号能够被重构出来,如图3所示。对模糊化处理和未处理的原图像进行下采样,得到图中底部的两张图,模糊化处理的原图像下采样的图像还能看出一些轮廓,而未处理的原图像下采样的图像就显得更加混乱。 图3. 采样前未模糊化处理和模糊化处理形成的效果图 从上面看出,采用抗锯齿技术,可以一定程度上缓解样本不足导致的失真。这里在图形学的角度,介绍三种抗锯齿技术。 2.1. 前置滤波(Prefiltering) 前置滤波技术,是通过物体的覆盖范围来计算其像素颜色值的,即一个像素的多少区域被物体覆盖。每个像素会有一个灰度(Intensity),该值依赖物体或者直线对像素所在区域的覆盖率,如图4所示。灰度是0,表示黑色;灰度是1,表示白色。如果一个像素的一半被多边形覆盖,灰度是1/2;如果1/3被覆盖,灰度是1/3,依次类推。如果帧缓冲区中每个像素占4位,则黑色用0表示,白色用15表示,所以每个像素值是像素灰度值乘以15,图4(a)中的多边形,可以用图4(b)中的像素值来表示。 图4. 前置滤波像素值的计算 找到每个像素的灰度需要较大的运算量,这里介绍一种方法是由Pitteway和Watkinson提出的,是对布雷森汉姆直线绘制算法(参见文章《布雷森汉姆直线算法》)进行的修改。基本思想是:多边形填充时,采用的是逐行扫描的方式,用AEL数据结构确定要填充的像素段,当一条扫描线被填充完成后,采用布雷森汉姆算法更新存储在AEL结点中的数据xint,即改变了文章《区域填充算法和多边形填充的扫描线算法》2.2中所叙述的原则2。 通过一个例子来说明该算法,图5中的边的斜率是m=4/10,像素值所在方格用标准的布雷森汉姆算法进行计算,方格中像素强度依次为0.5,0.9,0.3,初始像素值是0.5。从左到右扫描边,如果y方向的坐标值不变,则像素强度加上m=0.4,如果y方向的坐标值加1,则像素的灰度值减去1-m=0.6,这相比于《区域填充算法和多边形填充的扫描线算法》中的多边形填充算法,锯齿问题能得到一定程度的缓解。 图5. 抗锯齿的扫描线算法 最后演示一个由参考【5】中找到的两张前置滤波的例子,如图6所示。总结下:前置滤波必需考虑对象的几何细节并计算每个像素的平均灰度,对于处理除多边形形状以外的几何图元来说,前置滤波运算量非常的大,不太适用。 图6. 前置滤波的对图像的影响 2.2. 后置滤波(Postfiltering) 首先介绍一个很重要的概念,就是超采样(Supersample),简单来说,就是原先一个像素只选择一个采样样本,现在一个像素中选取多个采样样本,即以亚像素(subpixel)作为样本。如图7所示,一个格子表示一个像素,每个像素上取9个采样点,即水平分辨率和垂直分辨率都是原来的3倍。如果要绘制圆圈A中的像素,因为有6个采样点在圆圈内部,3个采样点在外部,所以计算得到它的颜色值为:(2/3*圆圈内颜色+1/3圆圈外颜色)。B像素的9个采样点颜色都一样,它的颜色值就多边形的颜色,即圆圈内的颜色。

spacer

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

本文主要介绍几种区域填充算法,重点解释多边形的扫描线填充算法,最后实现了多边形填充算法,包括在附录文件中。在参考【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

布雷森汉姆直线算法

本篇文章,主要介绍布雷森汉姆直线算法,包括一个用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