05计算机图形学双语课程i

1、Implementation I原著Ed AngelProfessor of Computer Science, Electrical and Computer Engineering, and Media ArtsUniversity of New Mexico编辑 武汉大学计算机学院图形学课程组ObjectivesIntroduce basic implementation strategies介绍绘制实现的基本策略和框架Clipping裁剪问题Outline7.1 Basic implementation strategies基本绘制框架7.2 Four required tasks四个

2、主要任务7.3 Clipping 裁剪7.4 Line-segment 线段裁剪7.7 Clipping in three dimensions三维裁剪7.1 Basic implementation strategies绘制框架(Overview)At end of the geometric pipeline, vertices have been assembled into primitives几何阶段之后，顶点装配成图元Must clip out primitives that are outside the view frustum必须对视见体之外的图元进行裁剪Algorithms

3、 based on representing primitives by lists of vertices算法是基于顶点表示的图元Must find which pixels can be affected by each primitive找到每个图元所对应的像素Fragment generation产生片元Rasterization or scan conversion进行光栅化和扫描转换7.1 Basic implementation strategies绘制框架(图形处理过程)计算机图形系统可看作一个黑盒子输入：程序中定义的顶点和状态量-几何对象、属性和照相机设置输出：帧缓冲区里的彩

4、色像素阵列内部：变换、裁剪、明暗处理、隐藏面消除和光栅化对每个几何对象进行处理给颜色缓冲区的每个像素赋颜色值7.1 Basic implementation strategies绘制框架(Rasterization Meta Algorithms基本算法)Consider two approaches to rendering a scene with opaque objects考虑绘制由不透明对象构成的场景的两种方法For every pixel, determine which object that projects on the pixel is closest to the vie

5、wer and compute the shade of this pixel对于每个像素，确定投影到这个像素的离观察者最近的那个对象，从而基于该对象计算像素的明暗值Ray tracing paradigm光线跟踪框架for (each_pixel) assign_a_color(pixel)7.1 Basic implementation strategies绘制框架(Rasterization Meta Algorithms基本算法)For every object, determine which pixels it covers and shade these pixels对于每个对象

6、，确定它所覆盖的像素，并用对象的状态确定像素的明暗值Pipeline approach流水线方法Must keep track of depths必须跟踪深度值for (each_object) render(object)7.1 Basic implementation strategies绘制框架(算法类型)这两种方法分别称为面向图像(image-oriented)的方法面向对象(object-oriented)的方法也分别称为先排序(sort-first)后排序(sort-last)方法基于隐藏面消除发生的地方进行命名的7.1 Basic implementation strategie

7、s绘制框架(面向对象方法)A polygon might flow through the steps7.1 Basic implementation strategies绘制框架(面向对象方法优缺点)优点：处理速度快，运行成本低缺点：过去需要占用大量内存，每个对象单独处理的代价较大。由于低价大容量内存，以及专用硬件芯片的出现，已不再是问题不能得到大多数全局效果，例如涉及多个对象的复杂光照隐藏面消除例外，Z buffer全局深度信息7.1 Basic implementation strategies绘制框架(面向图像方法优缺点)优点：任何时刻只需有限的显示内存，且可以按显示器的刷新速度和次序

8、生成像素利用相邻像素间的连贯性可设计增量式算法适合处理全局效果缺点：需要复杂的几何对象的数据结构必须确定哪些图元影响哪些像素绘制过程中需要随时访问所有的几何数据7.2 Four required Tasks四个主要任务Modeling建模Transformations几何处理投影、图元装配、裁剪、明暗处理Rasterization or scan conversion光栅化Some tasks deferred until fragments processing片元处理Hidden surface removal隐藏面消除Anti-aliasing反走样纹理映射、融合7.2 Required

9、 Tasks主要任务(建模)建模器可以认为是一个黑盒子输出几何对象的顶点数据集工作在对象坐标系Chapter 6 球体近似建模，网格模型Chapter 10 层次建模Chapter 11 过程建模7.2 Required Tasks主要任务(几何处理)几何处理的对象是顶点，目标是确定显示在屏幕上的几何对象，并确定这些对象顶点的明暗值或颜色值投影图元装配裁剪明暗处理7.2 Required Tasks主要任务(投影)第一步：利用模型-视图变换把几何对象从对象坐标系变换到照相机坐标系或视点坐标系第二步：利用投影变换把顶点变换到规范化视景体顶点表示为裁剪坐标7.2 Required Tasks主要任

10、务(图元装配)变换是对顶点进行的，在进行后续操作需要组装成几何对象，称为图元装配裁剪是针对图元进行的光栅器不能对顶点单独进行处理7.2 Required Tasks主要任务(裁剪)裁剪器确定哪些图元或图元的哪些部分会被传送到光栅器，最终可能会显示在屏幕上只有在视景体内的对象经过光栅化后能被显示在屏幕上部分在视景体内的图元，裁剪后生成新的图元没被裁剪掉的顶点仍表示为四维齐次坐标，通过透视除法转换为三维的规范化设备坐标7.2 Required Tasks主要任务(明暗处理)为每个顶点赋颜色，两种方法第一种方法，由当前绘制颜色决定，程序直接指定第二种方法，开启光照时，根据改进的Phong模型计算得到

11、7.2 Required Tasks主要任务(光栅化)光栅化或扫描转换：从裁剪后的对象生成片元（准像素）对于线段，确定哪些像素可用来近似表示顶点间的线段对于多边形，确定哪些像素位于多边形顶点定义的二维区域的内部片元的颜色取决于 系统颜色状态值 或 由光照模型计算的顶点明暗值插值得到输入：由规范化设备坐标表示的顶点输出：由三维窗口坐标表示的片元7.2 Required Tasks主要任务(片元处理)最简单的情形下，片元的颜色由光栅器赋值，并且该值就是片元所对应的帧缓冲区中像素的颜色值纹理贴图 像素流水线隐藏面消除：确定可见对象的片元值可见对象指位于视景体内，且没有被其他更靠近照相机的不透明对象所

12、遮挡的对象融合：半透明效果，反走样7.3 Clipping裁剪2D against clipping window二维相对于裁剪窗3D against clipping volume三维相对于裁剪体Easy for line segments polygons,hard for curves and text对线段和多边形很容易进行，对于曲线和文本很难进行Convert to lines and polygons first首先转化为线段和多边形7.4 Clipping 2D Line Segments二维线段的裁剪Brute force approach: compute intersect

13、ions with all sides of clipping window直观方法: 计算线段与裁剪窗口边界的交点Inefficient: one division per intersection低效：每次求交运算需要一次除法7.4.1 Cohen-Sutherland Algorithm Cohen-Sutherland算法Idea: eliminate as many cases as possible without computing intersections想法：尽可能避免求交运算就消除许多情形Start with four lines that determine the s

14、ides of the clipping window从确定裁剪窗口边界的四条直线开始x = xmaxx = xminy = ymaxy = ymin7.4.1 Cohen-Sutherland算法(The Cases各种情形-1)Case 1: both endpoints of line segment inside all four lines线段的两个端点都在裁剪窗口内Draw (accept) line segment as is原样绘制直线，即接受Case 2: both endpoints outside all lines and on same side of a line两

15、个端点都在窗口外，且在同一条直线的外侧Discard (reject) the line segment 丢弃这条直线，即拒绝x = xmaxx = xminy = ymaxy = ymin7.4.1 Cohen-Sutherland算法(The Cases各种情形-2)Case 3: One endpoint inside, one outside一个端点在内部，一个端点在外部Must do at least one intersection必须进行至少一次求交Case 4: Both outside都在外部May have part inside仍可能部分在内部Must do at lea

16、st one intersection必须进行至少一次求交x = xmaxx = xminy = ymax7.4.1 Cohen-Sutherland算法(Defining Outcodes定义编码)For each endpoint, define an outcode对于每个端点，定义一个编码b0b1b2b3Outcodes divide space into 9 regions编码把空间分成九个区域Computation of outcode requires at most 4 subtractions计算编码最多需要四次减法b0 = 1 if y ymax, 0 otherwiseb

17、1 = 1 if y xmax, 0 otherwiseb3 = 1 if x a3 a2 a1Intersect right, top, left, bottom: shorten交点依次在右、顶、左、底：缩短In (b)情形(b): a4 a2 a3 a1 Intersect right, left, top, bottom: reject交点依次在右、左、顶、底：抛弃7.4.2 梁-Barsky Clipping(效率的考虑)交点的表示= (ymax y1)/(y2y1)需要浮点除法尽可能地避免交点计算交点方程的重写：a (y2y1) = ay = (ymax y1) = ymax所需要

18、的测试可以对ymax和y以及其它类似项进行全部在窗口外，直接抛弃的线段只有当需要对直线进行缩短时才计算交点部分在窗口内，需要对长度裁减7.4.2 梁-Barsky Clipping(Advantages优势)Can accept/reject as easily as with Cohen-Sutherland 与Cohen-Sutherland 算法一样很简单地接受或拒绝Using values of a, we do not have to use algorithm recursively as with C-S 应用a值使得不必要像Cohen-Sutherland算法那样重复应用代码E

19、xtends to 3D 也可以推广到三维的情形 相比之下，一些高效的二维算法不能扩展到三维情形7.7 Clipping in three dimensions三维裁剪把二维裁剪扩展到三维，采用长方形体作为裁剪体(clip against a bounded volume)Clipping algorithms in two-dimension can be extended to three-dimension二维裁剪算法都能扩展到三维情况7.7 Clipping in three dimensions ( Cohen Sutherland in 3D) 三维空间中的Cohen-Sutherland算法Use 6-bit outcodes利用6位进行编码，27个区域When needed, clip line segment against planes 必要时，相对于平面裁剪线段7.7 Clipping in three dimensionsClipping and Normalizat