图形学简单总结范文.doc

图形学简单总结范文 DAA算法（直线）条件是 1、端点坐标P0（x0，y0）P1(x1,y1) 2、斜率m=y/x,x=x1-x0y=y1-y 03、直线方程y=mx+B,0 1、划分区间x0,x1:x0,x1,xn,其中xi+1=xi+ 12、计算纵坐标yi+1=mxi+1+B=m(xi+1)+B=mxi+B+m=yi+m 3、取整yi+1=round(yi+1)=(int)(yi+m+0.5)复杂度加法+取整其他斜率情况 1、m1交换x和y的位置 2、m0步长dx或dy取-1不足取证操作和浮点运算仍十分耗时Bresenham画线算法（圆和曲线）基本原理从给定线段的左端点开始，逐步处理每个后继列，并在其扫描线y值最接近线段的像素上绘出一点。 算法分析在取样位置xk+1,使用dlower,dupper来表示两个像素与数学路径上的垂直偏移。 y=m(xk+1)+b,dlower=y-yk=m(xk+1)+b-yk,dupper=(yk+1)-y=yk+1-m(xk+1)-b决策函数pk=x(dlower-dupper)=2yxk-2xyk+c,pk+1-pk=2y(xk+1-xk)-2x(yk+1-yk)pk+1=pk+2y-2x(yk+1-yk)yk+1-yk=0或1p0=2y-x|m|1时的算法流程 1、输入线段的两个端点，将左端点存储在(x0,y0)中 2、将(x0,y0)装入帧缓存,画出第一个点 3、计算常量x、y、2y、2y-2x，并得到决策函数的第一个值 4、从k=0开始，在沿线路径的每个xk处，进行决策函数检测 5、重复步骤4，共x?1次中点画圆算法分析采用圆函数决策函数fx,ypfx1,yp21yk-1,增量是2xk+1+1或者2xk+1+1-2yk+11,r1,两个候选像素的中点，pk0时取yk，反之取yk-11,yk+1是yk(pk=y Bezier曲线N次Bezier曲线Rt,，0t1Bernstein基函数Bi,n(t)为,（t）曲线性质 1、端点插值R0,R1 2、端点切向0n,1n 3、对称性,1，!,曲线的控制顶点的几何地位是对称的 4、凸包性Bezier曲线位于控制多边形的凸包内 5、几何不变性Bezier曲线的形状仅与控制多边形有关，与坐标系无关不足 1、整体性质当移动曲线的一个控制定点时，整条曲线的形状都会发生改变 2、表示复杂形状时，需要将更多条Bezier曲线光滑的拼接起来Cohen-Sutherland算法通过初试测试来减少求交计算，从而提高效率特点对显然不可见的线段快速判别，可直接推广到三维区域编码用窗口四边所在的直线将整个平面分成9个区域，每个区域赋于一个四位的编码CtCbCrCl1010端点编码定义为它所在区域的编码结论当线段的两个端点的编码的逻辑“与”非零时，线段为显然不可见的；对于不能判断完全在窗口外或窗口内的线段，则要测试其与窗口的交点方法线段与裁剪边界逐个求交线段与裁剪边界的交点计算可使用斜率截矩式方程yx当y，1，10当y当x当x0，x=xwmin;xwmax垂直边界步骤 1、判别线段两段点是否都落在窗口内，如果是，则线段完全可见；否则进入第二步 2、判别线段是否为显然不可见，如果是，则裁剪结束；否则进行第三步 3、求线段与窗口边延长线的交点，这个交点将线段分为两段，其中一段显然不可见，丢弃。 对余下的另一端重新进行第一步、第二步判断算法缺点裁剪一条直线仍然需要多次求交Nicholl-Lee-Nicholl算法在求交前进行更多的区域测试，从而减少求交运算特点仅用于二维裁剪步骤 1、窗口四边所在的直线将二维平面划分成9个区域，假定p0落在区域 0、 4、 52、从p0点向窗口的四个角点发出射线，这四条射线和窗口的四条边所在的直线一起将二维平面划分为更多的小区域 3、确定p0所在的区域（方法比较该线段的斜率和裁剪区域边界的斜率） 4、求交点，确定p0p1的可见部分梁友栋-Barsky算法直线的参数形式x?,y?,0u1,其中?x,?y直线在裁剪窗口内的条件?,?改写上式upkqk,k=1,2,3,4p1=-x,q1=x0-xwwmin;p2=x,q2=xwwmax-x0;p3=-y,q3=y0-ywwmin;p4=y,q4=ywwmax-y0当pk=0时，（k=1，2，3，4对应于左、右、下、上边界），如果还满足qk0，则线段完全在边界之外，舍弃线段当qk0时，线段位于平行边界内当pk0时，线段从裁剪边界延长线的外部延伸到内部；当pk0时,反之。 可以计算线段与边界K的延长线的交点u值u对每条直线可计算出参数u1和u2，他们定义了裁剪矩形内的部分u1的值由线段从外到内遇到的矩形边界所决定(p0)对于这些边界，计算rk=qk/pk.u1取0和各个r之中最大值u2的值由线段从内到外遇到的矩形边界所决定(p0)。 根据这些边界计算出rk，u2取1和各个r值中最小值如果u1u2，则线段完全落在裁剪窗口之外，舍弃。 否则由参数u的两个值计算出裁剪后的线段端点更新参数u1和u2仅仅需要一次除法；计算出u1和u2的最后值之后，线段与窗口的交点只计算一次比Cohen-Sutherland算法减少了求交次数，算法效率更高；可扩展到三维裁剪算法Sutherland-Hodgman算法:（可用于裁剪凸多边形）策略:顺序地将每一线段的一对顶点送给一组裁剪器（左、右、下、上）。 一个裁剪器完成一对顶点的处理后，该边裁剪后留下的坐标值送给下一个裁剪器逐边裁剪第一次分解将多边形关于矩形窗口的裁剪分解为它关于窗口四条边所在直线的裁剪；第二次分解将多边形关于一条直线的裁剪分解为多边形各边关于该直线的裁剪推广关于任意凸多边形窗口的裁剪不足之处裁剪凹多边形时，可能显示一条多余的直线，原因是该算法只有一个输出顶点队列改进方法 1、将凹多边形分解为两个或者更多个的凸多边形 2、将输出顶点队列分为两个或多个 3、使用更一般的凹多边形裁剪算法Weiler-Atherton算法（可用于裁剪凸多边形或凹多边形）多边形顶点排列顺序的原则使多边形区域位于有向边的左侧两类交点 1、进点主多边形边界由此进入裁剪多边形内 2、出点主多边形边界由此离开裁剪多边形区域算法步骤（逆时针的多边形填充区域） 1、按逆时针处理多边形填充区，直到一对内-外顶点与边界相遇（出点） 2、在窗口边界上从出交点沿逆时针到达另一个多边形的交点。 如果该点是处理边的点，则走向下一步。 如果是新交点，则继续按逆时针处理多边形直到遇见已处理的顶点 3、形成裁剪后该区域的顶点队列 4、回到出交点并继续按逆时针处理多边形的边推广可用任意多边形窗口来处理任意多边形填充区多边形扫描转换算法核心思想(从下到上扫描) 1、计算扫描线y=ymin与多边形的交点，通常这些交点由多边形的顶点组成 2、根据多边形边的连贯性，按从下到上的顺序求得各条扫描线的交点序列 3、根据区域和扫描线的连贯性判断位于多边形内部的区段 4、对位于多边形内的直线段进行着色算法 1、(y初始化)取扫描线纵坐标y的初始值为ET中非空元素的最小序号(y=2) 2、(AEL初始化)将边的活化链表AEL设置为空 3、按从下到上的顺序对纵坐标值为y的扫描线(当前扫描线)执行如下步骤，直到分类边表ET和边的活化链表AEL都变成空为止a)如果分类边表ET中的第y类元素非空，则将属于该类的所有边从ET中取出插入边的活化链表AEL中(同时将ET中相应的边表删除)，AEL中的各边按照x值(x值相等时，按dx值)递增方向排序；b)若对于当前扫描线，边的活化链表非空，则将AEL中的边交点两两依次配对。 每一对边与当前扫描线的交点区间位于多边形内部，依次对这些区间上的像素按多边形属性着色；c)将边的活化链表AEL中满足y=ymax的边删除；d)将边的活化链表AEL中剩下的每一条边的x累加dx，即x=x+dx;e)将当前扫描线的纵坐标值y累加，即y=y+1。 优点充分利用多边形的区域、扫描线和边的连贯性，避免了反复求交的大量运算不足 1、算法的数据结构和程序结构复杂 2、对各种表的维持和排序开销太大，适合软件实现而不适合硬件实现Differences andrelations amongComputer Graphics,ComputationalGeometry,Pattern Recognition,ImageProcessing:Researches inComputer Graphicshas twogoals,they arerealism andreal time.Rendering isthe kernel.Octrees:The fundamentalidea behindboth quadtreeand octreeisthe divide-and-conquer powerof binarysubdivision.Advantages: 1、Simple datastructure 2、Easy forset operation 3、Easy forinspecting collisionbetween solidobjects 4、Easy forcalculating objects propertiessuch asvolume,mass,and soon.Drawback: 1、Still needlarge amountmemory 2、Difficult todo transformation 3、Difficult totransfer tob-reps DrawingPipeline Fillin WorldCoordinateFlow outScreen CoordinateVideo BufferDefinition:A transformation is afunction thattakes apoint ofa coordinatesystemand mapsthe pointinto thecorresponding pointwithinanother coordinatesystem.Transformation Pipeline:ModelingCoordinatesModeling TransformationWorld CoordinatesViewing CoordinatesProjection TransformationProjection CoordinatesNormalization TransformationNormalized OrijectionCoordinatesWorkstation TransformationDevice CoordinatesIllumination:Element ofobject appearance:Geometry、Surface property、Light sourceBasic illuminationponents Ambient、Diffuse、Specular LocalIllumination DiffuseReflection Model: 1、It isview-independent 2、Reflection coeffecientdepends onthe charactericticsof materialand inputlight wavelengthSpecular reflectionModel: 1、It isview-dependent 2、nisspecular reflectionexponent ofmaterial,higher nsimulate asharp(锐化),focused highlight（聚焦突出） 3、The colorof thehighlight is not dependenton materialproperty,it isthe colorof lightsource I 1、Point lightsource only 2、Light sourceand viewerareboth atinfinity 3、Only directillumination isconsidered 4、Ambient lightis constantShading FlatShading: 1、Constant ShadingOr FlatShading 2、The Simplestand Cheapestand ThereforeFastest ShadingMethod 3、Filling AnEntire Polygonwith OneColor Intensity 4、This Modelis OnlyValid(Realistic)If:a)The lightsource isimagined to be atinfinity b)The vieweris atinfinity c)The polygonisnotan approximationto acurved surfaceGouraud Shading: 1、Also calledSmooth shading 2、Color InterpolationAlgorithm a)Interpolation alongpolygon edgesb)Interpolation acrosspolygon surfacesPhong Shading: 1、An InterpolationProcess SimilarTo GouraudShading 2、Interpolating NormalVector Insteadof VertexColor a)Normal vectorstell aboutan objectsorientation b)Surface orientationis importantin respectto theposition of (1)The observer/viewer ofa scene (2)The sourceof lighting 3、Creating greaterrealism thanGouraud shadinga)Specially whenbined withan illuminationmodel b)Usually implementedthrough applicationsoftware c)Computing intenseyy?I?) (3)(11?1?1331ssbyyIyyyyI?I?) (2)(11?1221ssayyIyyyyI?I?)(x)(xasbsbaabsxIxxxI?N?) (2)(11?11221ssayyNyyyyN?N?) (3)(11331ssbyyNyyN?Ray Tracing:Main Idea: 1、Cast raysout fromthe eye,through each pixel,and determinewhat theyhit first:Builds the image pixelby pixel,one ata time 2、Cast additionalrays fromthe hitpoint todetermine the pixel color a)Shadow rays toward eachlight.If theyhit something,then theobject isshadowed fromthat light,otherwise use“standard”model forthe lightb)Reflection raysfor mirrorsurfaces,to seewhat shouldbe reflectedin themirror(ideally specularreflection)c)Transmission raysto seewhat can be seenthrough transparentobjects(ideally refraction)Sum allthe contributionsto getthe pixelcolor Terminationconditions: 1、Intersected withlight 2、Escaped outof thescene 3、Reached themaxmumrecursive number 4、IR,IThas beensmallthan agiven thresholdRaytracing Implementation: 1、Raytracing breaksdown intotwo tasks:a)Constructing theraystocast b)Intersecting rayswith geometry 2、The formerproblem issimple vectorarithmetic 3、The intersectionproblem arisesin manyareas ofputer graphicsa)Collision detectionb)Other renderingalgorithms 4、Intersection isessentially rootfinding(as wewill see)Any rootfinding techniquecan beapplied Drawback:The intersectionproblem arisesin manyareas ofputer graphics.Pseudo-code:Void TraceRay(start,direction,depth,color)if(depthMaxDepth)*color=Black;elseif(RayHit(start,direction,&hitPoint,&hitObject)=Nothing)*color=BackGround;elseShade(hitObject,hitPoint,&localColor);CalculateReflection(hitObject,hitPoint,direction,&rDirection);?N?)(x)(x1?asbsbaabsxNxxxN?CalculateTransmmission(hitObject,hitPoint,direction,&tDirection);hitObject.kt,color);Photon Mapping: 1、Photon tracinga)Emission b)Scattering c)Storing:only ondiffuse surface 2、Rendering a)Direct lightingb)Specular reflectionc)Caustics d)Indirect lightingZ-Buffering:Z bufferingworks byholding adepth value for eachpixel in theimage.Before rendering,the depth valueforeachpixelis setto themaximum valuepossible(very deepinto the screen).The imageis thenrendered,polygon bypolygon,and insteadof justsetting apixel toa certaincolour,we performthe following:Is the z screenvalue(depth)for this point onthe polygonsmaller(nearer to the viewer)than the depthvalueinthez bufferfor this pixel?Yes:This pointis nearer tothe viewer thanany pointsthat havebeen written to thispixel previously.Calculate theshade ofthepixeland writeit tothescreen.Write th