图形学资料.docx

如何计算有N个顶点（P1，P2，P3，Pn）定义的平面多边形的面积？多边形面积的计算公式如下：设有n个点(x1,y1)(x2,y2),.(xn,yn)围成一个没有边相交的多边形，则其围成的闭合多边形面积|S| 为：S=yi *(xi+1-xi-1)?!?没看懂， 其中i=1,2,.n，且当i与j除以n的余数相同的时候，xi=xj，yi=yj。该公式用于凸凹多边形均可。如何判别一个点Q是否落在该多边形内部？交点计数检验法：从点Q作一射线至无穷远X=X0+u（u0）Y=Y0求射线与多边形边的交点个数。若交点个数为奇数，则点在多边形内；否则，点在多边形外（当射线穿过多边形顶点时，必须特殊对待。若共享顶点的两边在射线的同一侧，则交点计数加2，否则加1）多边形填充算法：（OpenGL中采用哪种算法呢？） 扫描线填色(Scan-Line Filling)算法。这类算法建立在多边形边界的矢量形式数据之上，可用于程序填色，也可用于交互填色。算法的基本思想。多边形以n、x_array、y_array的形式给出，其中，x_array、y_array中存放着多边形的n个顶点的x，y坐标。用水平扫描线从上到下扫描由点线段构成的多段定义成的多边形。每根扫描线与多边形各边产生一系列交点。这些交点按照x坐标进行排序，将排序后的交点成对取出，作为两个端点，以所需要填的色彩画水平直线。多边形被扫描完毕后，填色也就完成。求交运算: 求交点是计算机图形学中极力需要避免的,因为它计算量大.扫描线填充算法是一种非常有效的算法，它对于每个象素只访问一次，其缺点是对于各种表的维持和排序的耗费大。 种子填色(Seed Filling)算法。这类算法建立在多边形边界的图像形式数据之上，并还需提供多边形边界内一点的坐标。所以，它一般只能用于人机交互填色，而难以用于程序填色。种子填色又称边界填色(Boundary Filling)。它的功能是，给出多边形光栅化后的边界位置及边界色代码boundary_color，以及多边形内的一点(x, y)位置，要求将颜色fill_color填满多边形。通常采用的填法有两种：四邻法和八邻法帧缓存（frame buffer）Frame buffer：the memory to hold the pixel intensity values(平均像素强度值)Properties of a frame buffer that affect the graphics performance:-size screen resolution-depth color level-speed refresh speed1 320 x 240 pixels2 24 bits/pixel3 So how many bits are needed to represent this image in a computers memory?320 x 240 x 24 =1,843,200To convert to Kbytes Divide by 8, then divide by 1024225 Kb多边形裁剪算法：仍保持封闭Sutherland-Hodgman算法思路：将多边形的各边先相对于窗口的某一条边界进行裁剪，然后将裁剪结果再与另一条边界进行裁剪，如此重复多次，便可得到最终结果。实现方法：设置二个表 输入顶点表(向量)用于存放被裁剪多边形的顶点p1-pm。 输出顶点表(线性链表)用于存放裁剪过程中及结果的顶点 q1-qn。输入顶点表中各顶点要求按一定顺序排列，一般可采用顺时针或逆时针方向。相对于裁剪窗口的各条边界，按顶点表中的顺序，逐边进行裁剪。具体操作： Pi 若位于边界线的可见一侧，则 Pi 送输出顶点表 Pi 若位于边界线的不可见一侧，则将其舍弃。 除第一个顶点外，还要检查每一个 Pi 和前一顶点 Pi-1是否位于窗口边界的同一侧，若不在同一侧，则需计算出交点送输出顶点表。 最后一个顶点 Pn则还要与 P1 一起进行同样的检查。几何变换：光线跟踪与辐射度基本原理7 光线跟踪方法沿着到达视点的光线的反方向跟踪，经过屏幕上每一像素，找出与视线所交的物体表面点P0，并继续跟踪，找出影响P0点光强的所有光源，从而算出P0点上光照强度。光线跟踪方法优点： 2) 各物体之间反射的影响，因此显示效果十分逼真。3) 有消隐功能4) 有影子效果 5) 该算法具有并行性质 光线跟踪算法 1 光线跟踪算法中的每一条光线要与场景中的各个物体所含的各个面求交。有必要对数据进行管理 2 对于多面体，常采取链表构成的树形结构对数据进行分层表达与管理。 与辐射度算法的比较深度缓存算法（Z-buffer算法）（OpenGL 支持）我们先看看它的算法：（1）将屏幕设成背景色，（2）把要画的物体（多边形）按其离开视点的从远到近排序。由此构成深度优先级表。然后从远到近画物体（多边形），近的就因为优先级高而覆盖远的多边形。由此可消隐。这个算法需要两个数组：一是深度缓存数组ZB，也就是所谓的Z-Buffer，另一个是颜色属性数组CB（color-Buffer）。这两个数组的大小与屏幕的分辨率有关，等于横向像素数和纵向像素数n的乘积1 优点：简单且被硬件广泛支持lz-buffer是3D图形卡的一部分计算深度值很简单2 缺点：过度绘制 对不可见的多边形也进行光栅化深度误差令人头痛透明和基于过滤的反走样难以实现 (需要保存部分覆盖的多边形的信息)与画家算法的比较们之间最本质的区别在于：画家算法是按照物体（多边形）的深度进行排序，比较容易实现；而Z-buffer算法是按照图像每一个像素进行排序，比总体排序灵活简单。如何使用z-buffer算法实现阴影绘制 P167Phong光照模型1 where, ks is the materials specular reflection coefficient ranging between 0 and 1, n is the specular reflection exponent is the material property the object, is the reflected ray vector and is the view vector3) is the reflected ray vector and is the view vector4) The ambient light is , where Ia is the intensity of ambient lightand ka is the materials ambient reflection coefficient ranging from 0 to 14 Ip is the point light source intensity, kd is the materials diffuse reflection coefficient ranging from 0 to 1. and must be between 00 and 900 for the point to be lit 着色模型：常量着色Gourand着色（OpenGL采用）采用亮度插值，Gourand光滑化的优点是计算量小，缺点是它使高光部位变得模糊，而且有时会引起不规则的现象。Phong着色不是采用亮度插值，而是采用法线方向插值。按照插值后各点的法线方向，用光照模型求出其亮度。用Phong方法可以产生很好的镜面反射高光效果，真实感更强，但计算工作量也更大。OpenGL中绘制流水线从三维场景到屏幕像素，经过了哪些过程消隐和裁剪，是先消隐还是先裁剪童老师上课特别强调过这个，先消隐的话运算量大，应该先裁剪天图形学的考试题目和总结总共五道题，大体如下：1、扫描线填充和种子填充算法概述，优缺点比较。2、Phong模型和Gouraud模型概述，比较。3、画家算法和z-buffer消隐算法概述，比较。4、光线跟踪算法和辐射度方法。5、如何用深度缓存生成影子。我的解答：1、扫描线是为矢量图形系统开发的，种子填充适合光栅图形系统，尤其应用于交互式的程序，如windows 画图板的填充功能。2、前者计算量大，但是效果更好一点。后者计算量小，适用于实时系统，但是对于某些高光效果不如phong模型。opengl的GL_SMOOTH是gouraud填色模型。3、消隐两类算法，一个是面向图像空间，一个是面向对象空间。z-buffer是面向图像的，画家算法是两者的结合。注意理解bsp树。4、这个我也不太会。5、参见中文教材。主要思想是以点光源为观察点做透视和消隐，计算深度，并且比较点p和深度缓冲。图形学大概几块：1、opengl2、几何变换（平移，旋转，缩放，错切，齐次坐标表示）3、基本图元生成算法，dda，bresenham算法等4、消隐，z-buffer，画家算法5、剪裁，线剪裁算法，多边形剪裁算法6、光照模型，重点是普通光照模型和phong光照模型。填色模型，重点是phong和gouraud模型比较。光线跟踪（现在还不太明白）7、纹理（这个好像没怎么考过。理论比较简单，opengl编程很麻烦）还有一些乱七八糟的，如计算面积，判断点在多边形内部（even-odd rule, winding-number rule)等等，就这么多了。最后一道题是跟求教有关的，判断点是否在图形内部，比较开放，要自己想算法这个问题要好好看看书上关于判断点是否在图形内部的几种算法。很多人当时都没复习到上学期倒数第二题是有关坐标系，这道题很简单，但是有陷阱，先平移或者先旋转都可以，但是要细心一点，注意平移矢量和旋转矢量的变化。送分题比如问你简单光照模型EPs=RPcos iIPs+WP(i)cosn sIPs各个参数的意义，适用于什么光效光照模型phong模型和Gourand模型的基本思想和评价各自的优缺点消隐和裁剪，是先消隐还是先裁剪童老师上课特别强调过这个，先消隐的话运算量大，应该先裁剪八叉树模型等的评价消隐的Zbuffer考到的，就是简述一下思想直线裁剪的算法过程简述种子填充法的思想画家算法！openGL的基本函数还是要会的，有一道题会考到，不过关注的是算法上学期的 只想起一点点 供本学期考的人参考 其余考过的可