圖形學簡單總結(jié)范文.doc

圖形學簡單總結(jié)范文 DAA算法（直線）條件是 1、端點坐標P0（x0，y0）P1(x1,y1) 2、斜率m=y/x,x=x1-x0y=y1-y 03、直線方程y=mx+B,0 1、劃分區(qū)間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)復(fù)雜度加法+取整其他斜率情況 1、m1交換x和y的位置 2、m0步長dx或dy取-1不足取證操作和浮點運算仍十分耗時Bresenham畫線算法（圓和曲線）基本原理從給定線段的左端點開始，逐步處理每個后繼列，并在其掃描線y值最接近線段的像素上繪出一點。 算法分析在取樣位置xk+1,使用dlower,dupper來表示兩個像素與數(shù)學路徑上的垂直偏移。 y=m(xk+1)+b,dlower=y-yk=m(xk+1)+b-yk,dupper=(yk+1)-y=yk+1-m(xk+1)-b決策函數(shù)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，并得到?jīng)Q策函數(shù)的第一個值 4、從k=0開始，在沿線路徑的每個xk處，進行決策函數(shù)檢測 5、重復(fù)步驟4，共x?1次中點畫圓算法分析采用圓函數(shù)決策函數(shù)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基函數(shù)Bi,n(t)為,（t）曲線性質(zhì) 1、端點插值R0,R1 2、端點切向0n,1n 3、對稱性,1，!,曲線的控制頂點的幾何地位是對稱的 4、凸包性Bezier曲線位于控制多邊形的凸包內(nèi) 5、幾何不變性Bezier曲線的形狀僅與控制多邊形有關(guān)，與坐標系無關(guān)不足 1、整體性質(zhì)當移動曲線的一個控制定點時，整條曲線的形狀都會發(fā)生改變 2、表示復(fù)雜形狀時，需要將更多條Bezier曲線光滑的拼接起來Cohen-Sutherland算法通過初試測試來減少求交計算，從而提高效率特點對顯然不可見的線段快速判別，可直接推廣到三維區(qū)域編碼用窗口四邊所在的直線將整個平面分成9個區(qū)域，每個區(qū)域賦于一個四位的編碼CtCbCrCl1010端點編碼定義為它所在區(qū)域的編碼結(jié)論當線段的兩個端點的編碼的邏輯“與”非零時，線段為顯然不可見的；對于不能判斷完全在窗口外或窗口內(nèi)的線段，則要測試其與窗口的交點方法線段與裁剪邊界逐個求交線段與裁剪邊界的交點計算可使用斜率截矩式方程yx當y，1，10當y當x當x0，x=xwmin;xwmax垂直邊界步驟 1、判別線段兩段點是否都落在窗口內(nèi)，如果是，則線段完全可見；否則進入第二步 2、判別線段是否為顯然不可見，如果是，則裁剪結(jié)束；否則進行第三步 3、求線段與窗口邊延長線的交點，這個交點將線段分為兩段，其中一段顯然不可見，丟棄。 對余下的另一端重新進行第一步、第二步判斷算法缺點裁剪一條直線仍然需要多次求交Nicholl-Lee-Nicholl算法在求交前進行更多的區(qū)域測試，從而減少求交運算特點僅用于二維裁剪步驟 1、窗口四邊所在的直線將二維平面劃分成9個區(qū)域，假定p0落在區(qū)域 0、 4、 52、從p0點向窗口的四個角點發(fā)出射線，這四條射線和窗口的四條邊所在的直線一起將二維平面劃分為更多的小區(qū)域 3、確定p0所在的區(qū)域（方法比較該線段的斜率和裁剪區(qū)域邊界的斜率） 4、求交點，確定p0p1的可見部分梁友棟-Barsky算法直線的參數(shù)形式x?,y?,0u1,其中?x,?y直線在裁剪窗口內(nèi)的條件?,?改寫上式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對應(yīng)于左、右、下、上邊界），如果還滿足qk0，則線段完全在邊界之外，舍棄線段當qk0時，線段位于平行邊界內(nèi)當pk0時，線段從裁剪邊界延長線的外部延伸到內(nèi)部；當pk0時,反之。 可以計算線段與邊界K的延長線的交點u值u對每條直線可計算出參數(shù)u1和u2，他們定義了裁剪矩形內(nèi)的部分u1的值由線段從外到內(nèi)遇到的矩形邊界所決定(p0)對于這些邊界，計算rk=qk/pk.u1取0和各個r之中最大值u2的值由線段從內(nèi)到外遇到的矩形邊界所決定(p0)。 根據(jù)這些邊界計算出rk，u2取1和各個r值中最小值如果u1u2，則線段完全落在裁剪窗口之外，舍棄。 否則由參數(shù)u的兩個值計算出裁剪后的線段端點更新參數(shù)u1和u2僅僅需要一次除法；計算出u1和u2的最后值之后，線段與窗口的交點只計算一次比Cohen-Sutherland算法減少了求交次數(shù)，算法效率更高；可擴展到三維裁剪算法Sutherland-Hodgman算法:（可用于裁剪凸多邊形）策略:順序地將每一線段的一對頂點送給一組裁剪器（左、右、下、上）。 一個裁剪器完成一對頂點的處理后，該邊裁剪后留下的坐標值送給下一個裁剪器逐邊裁剪第一次分解將多邊形關(guān)于矩形窗口的裁剪分解為它關(guān)于窗口四條邊所在直線的裁剪；第二次分解將多邊形關(guān)于一條直線的裁剪分解為多邊形各邊關(guān)于該直線的裁剪推廣關(guān)于任意凸多邊形窗口的裁剪不足之處裁剪凹多邊形時，可能顯示一條多余的直線，原因是該算法只有一個輸出頂點隊列改進方法 1、將凹多邊形分解為兩個或者更多個的凸多邊形 2、將輸出頂點隊列分為兩個或多個 3、使用更一般的凹多邊形裁剪算法Weiler-Atherton算法（可用于裁剪凸多邊形或凹多邊形）多邊形頂點排列順序的原則使多邊形區(qū)域位于有向邊的左側(cè)兩類交點 1、進點主多邊形邊界由此進入裁剪多邊形內(nèi) 2、出點主多邊形邊界由此離開裁剪多邊形區(qū)域算法步驟（逆時針的多邊形填充區(qū)域） 1、按逆時針處理多邊形填充區(qū)，直到一對內(nèi)-外頂點與邊界相遇（出點） 2、在窗口邊界上從出交點沿逆時針到達另一個多邊形的交點。 如果該點是處理邊的點，則走向下一步。 如果是新交點，則繼續(xù)按逆時針處理多邊形直到遇見已處理的頂點 3、形成裁剪后該區(qū)域的頂點隊列 4、回到出交點并繼續(xù)按逆時針處理多邊形的邊推廣可用任意多邊形窗口來處理任意多邊形填充區(qū)多邊形掃描轉(zhuǎn)換算法核心思想(從下到上掃描) 1、計算掃描線y=ymin與多邊形的交點，通常這些交點由多邊形的頂點組成 2、根據(jù)多邊形邊的連貫性，按從下到上的順序求得各條掃描線的交點序列 3、根據(jù)區(qū)域和掃描線的連貫性判斷位于多邊形內(nèi)部的區(qū)段 4、對位于多邊形內(nèi)的直線段進行著色算法 1、(y初始化)取掃描線縱坐標y的初始值為ET中非空元素的最小序號(y=2) 2、(AEL初始化)將邊的活化鏈表AEL設(shè)置為空 3、按從下到上的順序?qū)v坐標值為y的掃描線(當前掃描線)執(zhí)行如下步驟，直到分類邊表ET和邊的活化鏈表AEL都變成空為止a)如果分類邊表ET中的第y類元素非空，則將屬于該類的所有邊從ET中取出插入邊的活化鏈表AEL中(同時將ET中相應(yīng)的邊表刪除)，AEL中的各邊按照x值(x值相等時，按dx值)遞增方向排序；b)若對于當前掃描線，邊的活化鏈表非空，則將AEL中的邊交點兩兩依次配對。 每一對邊與當前掃描線的交點區(qū)間位于多邊形內(nèi)部，依次對這些區(qū)間上的像素按多邊形屬性著色；c)將邊的活化鏈表AEL中滿足y=ymax的邊刪除；d)將邊的活化鏈表AEL中剩下的每一條邊的x累加dx，即x=x+dx;e)將當前掃描線的縱坐標值y累加，即y=y+1。 優(yōu)點充分利用多邊形的區(qū)域、掃描線和邊的連貫性，避免了反復(fù)求交的大量運算不足 1、算法的數(shù)據(jù)結(jié)構(gòu)和程序結(jié)構(gòu)復(fù)雜 2、對各種表的維持和排序開銷太大，適合軟件實現(xiàn)而不適合硬件實現(xiàn)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