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

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