图元属性及图形处理.ppt

1、计算机图形学第6讲 图元属性及图形处理,华中科技大学 吴义忠,主要内容,图元属性：关键数据；颜色、点属性、线属性、曲线属性、填充属性、字符属性 图元的一般处理 填充算法 裁剪算法 反走样,6.1 图元属性颜色,颜色与灰度 RGB模式与索引模式Index RGBA模式(alfa),OpenGL颜色函数,glutInitDisplayMode (GLUT_SINGLE | GLUT_RGB) or GLUT_INDEX RGBA模式 Index模式：,void glClearColor*(); void glClearIndex(GLfloat cindex); void

2、 glSecondaryColor*();,void glEnable (GL_BLEND),6.1 图元属性点属性,关键数据：点坐标 颜色和大小 样式（OpenGL不支持，可以自定义）,void glPointSize (GLint size);,6.1 图元属性线属性,关键数据：起点、终点坐标 颜色 glColor*() 线宽 glLineWidth(wid) 线型 glEnable(GL_LINE_STIPPLE) glLineStipple(); 画笔和画刷：使用矩形笔画线，则画刷起作用（OpenGL未提供）,6.1 图元属性曲线属性,关键数据 颜色 线宽 线型 精度（显示曲线的段数）

3、 Bezier曲线/NURBS曲线（后）,6.1 图元属性填充属性,关键数据：实体集合 填充颜色 填充样式 glPolygonStipple(pattern) 填充区域 glBegin/glEnd,glEnable(GL_POLYGON_STIPPLE),6.1 图元属性字符属性,颜色 字体 大小 位置、方向,glTranslate glRotate,6.2 图元的一般处理,属性改变：颜色、线型、宽度等； 关键数据改变： 图形变换：移动、旋转、放缩 复制操作：拷贝粘贴、镜像、阵列 关键点操作：拖动 裁剪与延伸 倒角与圆弧倒角 ,光栅显示的重要特点是能进行面着色，区域填充就是在一个闭合区域内填充

4、某种颜色或图案。区域填充一般分两类：多边形填充和种子填充。,6.3 区域填充算法,多边形填充算法,给定一顶点序列(Pi ，i=0，1，n )，依次连线构成一封闭多边形。,多边形内点判别 射线法,若射线与多边形边界的交点个数为奇数时，则该点为内点；反之，交点个数为偶数时，则该点为外点。 当扫描线过多边形顶点时，则交点为奇异点。奇异点为局部极值点应看成两点，若为非极值点应看成一点。,多边形填充算法,多边形内点判别 夹角法,夹角和为0，点p为外点；夹角和为360，点p为内点,这类算法建立在多边形边边界的矢量形式数据之上，可用于程序填色，也可用交互填色。,该算法基于几何求交算法，步骤如下： 输入多边形

5、顶点坐标； 求多边形顶点中最大和最小y坐标，以确定范围； 计算每条扫描线起止点（交点），并扫描填充，直至所有扫描线处理完毕。,1）扫描线填充算法思路,(Scan-Line Filling),算法步骤,扫描线填充算法改进,边相关扫描线填充算法,本算法改进的关键所在： 如何快速求扫描线与多边形交点； 扫描线填充利用画水平直线快速画法(为什么不用斜线？)； 应该利用扫描线与多边形交点的连贯性加速求交算法（多边形与扫描线相交，则与下一条扫描线很可能相交，交点可直接计算） 由于相邻扫描线上的交点是与多边形的边线相关的。对同一条边，前一条扫描线yi与该边的交点为xi，而后一条扫描线yi+1=yi+1与该边

6、的交点则为xi+1=xi+1/m，利用相关性可省去大量求交运算（算法详见图形学教材）。,这类算法建立在多边形边界的图象形式数据之上，并需提供多边形界内一点的坐标，一般只能用于人机交互填色，而难以用于程序填色。,从多边形内部点出发，沿四连通方向（或八连通方向）扩散搜索区域内所有待填充的象素点，适用于交互绘图。,算法思想：,用4连通填充算法的填充结果,用8连通填充算法的填充结果,2）种子填色算法（Seed Filling）,种子填色算法（见Test1.vcprj）,给定多边形边界颜色及内部填充颜色； 从内部点 ( x, y ) 开始，检测该点与边界和填充色是否相同，均不相同则填充该点； 检测相邻点

7、与边界和填充色是否相同，均不相同则填充该点； 重复第步直至所有象素点被填充。,算法步骤：,算法特点：,直接基于象素，用递归算法，不必求交。但递归太多，存储不够，易造成堆栈溢出。 （可用一个大的矩阵记录象素填充的状态来避免递归算法）,任意封闭区域的填充算法,边界实体集合生成 封闭性判断 若封闭： 得到边界实体集合的包容盒 坐标转换：世界坐标设备坐标 每条扫描线求交 根据交点显示扫描线,3）图案填充算法（参考）,实际应用中，有时需要用图案来填充平面区域，只需将种子填充算法中写象素的那部分代码修改 。（种子点颜色改写为定义图案对应点颜色查表即可）,定义填充图案是一个MN的位图，用数组存放。M、N常比

8、需要填充区域尺寸小得多（88、1616等），图案设计成周期性的，使之重复使用构成任意尺寸图案。 边界的处理？,图案填充算法,图案定位方法,相对定位法： 把图案原点与填充区域边界或内部的某点对齐。当被填充的多边形移动时，图案也跟着移动，看起来比较自然。对于多边形，可取边界上最左边的顶点，对于圆和椭圆这样具有光滑边界的区域，最好取区域内部某一点，如取中心与图案原点对齐。,绝对定位法：把图案原点与屏幕原点对齐。将整个屏幕看成被要填充的图案布满，只是要填充的区域是透明的，可以让图案显露出来，其它区域对此图案却是不透明的，图案被全部挡住。这种方法比较简单，并且在相邻区域用同一图案填充时，可以达到无缝连接

9、的效果。但它有一个潜在的毛病，即当区域移动时，图案不会跟着移动。其效果是区域内的图案变了。,任意区间的图案填充算法,前面同“实填充” 根据对齐方式确定包容盒内任意像素点处的颜色 根据交点信息确定哪些像素点显示,OpenGL中的填充,glBegin(GL_TRIANGLE/POLYGON/QUAD)，等自动实现多边形填充 设置 glPolygonStipple(pattern)可实现图案填充，过程同字符绘制,包容盒定义 Bounding Box,在计算机图形学、CAD、CAE中经常遇到相交（碰撞）测试。如鼠标拾取，视窗裁剪、曲面求交、光线跟踪、布尔运算、装配干涉校验、动画漫游、运动碰撞、机器人与

10、机床刀具的轨迹规划等。尤其对较大规模数据的模型而言，处理相交（碰撞）测试的速度对系统效率影响很大。 为加速测试计算速度，通常采用包容盒方法。,1）相交（碰撞）测试算法,轴对齐包容盒（矩形盒）：通常称AABB，表面平行于坐标面。,有向包容盒：简称OBB，即任意方向的AABB，往往由一个中心，三个单位矢量和三个半边长定义。,AABB Axis Align BB,OBB Oriented BB,KDOP K discrete oriented polytope,多边形/多面体包容盒 环包容盒 球体包容盒,6.4 多边形裁减算法,直线的包围盒，计算直接利用其特征点起始点和终点就可得到,矩形的包围盒是其

11、本身，圆的包围盒是该圆的边界矩形,圆弧的包围盒，主要是由圆弧的起始点和终止点，以及与通过圆心的4个坐标轴相交的交点,自由曲线的包容盒，可根据离散的小直线段的起始点和终止点比较后获得，若精确求解并不经济，因图形显示采用离散多边形，且图形变换频繁,复杂组合图形的包容盒，可以在简单图形的包容盒基础上进行比较得到,包容盒计算,AABB：直接比较所有多面体（前面的离散多面体）顶点坐标即可得,球体包容盒：计算麻烦。较为简单的方法是先计算AABB，再计算AABB的中心，以此为球心，球心到最远顶点的距离即为半径。其它更好更优的算法可查资料。显然，最远距离两点最为球的直径是最优解，关键是快速。,OBB：计算方法较多，较繁琐。方法之一是：1）计算凸包；2）计算凸包质心；3）计算协方差矩阵的特征向量；4) 其特征向量即为OBB三个方向；5）向三个方向投影即可求出半长值。,AABB、圆球包容盒比较粗糙，各有优势。KDOP 比 AABB更紧致，OBB 则较 kDOP 更优，选用何种包容盒视复杂度而定。,相交测试,1）尽可能用最简单算法排除或确定相交情形，如采用包容盒排除； 2）充分利用前一次计算结果，尽量避免复杂计算（如sin，开方等）； 3）如果使用了多种测试，可以尝试改变内部顺序，或许会有意外收效； 4）尽量降低维数，使问题简化，确保计算鲁棒性。,算法实现的基本原则：,求交计算是CG glEna