計(jì)算機(jī)圖形學(xué)

AttributesofGeometricPrimitives

幾何圖元的屬性ComputerGraphics2Outline(Hearn&Baker,P141:Chapter4)1.Fill-Area★

（4.10,4.13P159-162.P163-167）2.Antialiasing

★（4.17P175-182）1.AreaFillAlgorithms

(區(qū)域填充算法)(

Hearn&Baker,

Section4-10/13,P159-162.P163-167)4AreaFillFillorcolorizeaboundedareausingacolororpatternExamples:barchart,surfaces,solidobjects,etc.5DescriptionofAreaThedescriptionoftheareatobefilledisgivengeometrically:1.byedges,lines,polygons,circles,etc.

(邊界定義區(qū)域,boundary-defined)2.byasetofpixelsdefiningaboundary(內(nèi)部定義區(qū)域，interior-defined)6CommentsonFillingAlgorithmsTechniquesforrasteringapolygonoranarea:3.Scan-lineSeedFillMethod

（掃描線種子填充算法）2.Seedfillmethod（種子填充算法）1.Scan-linemethod

(掃描線填充算法）…自學(xué)Scan-linefillingmethods

(掃描線填充算法)8Scan-linemethods

(掃描線填充算法)WorksrowbyrowfromtoptobottomApixelinsidethecurrentscanlineisonlydrawnifitislocatedinsidethepolygon.逐點(diǎn)判斷法

判斷點(diǎn)在多邊形的內(nèi)外關(guān)系:射線法9如何區(qū)分點(diǎn)在多邊形的內(nèi)部與外部？射線法比較常用從一點(diǎn)p引射線，如果與多邊形邊界交點(diǎn)數(shù)為偶數(shù)，則p在多邊形外，否則在多邊形內(nèi)部如果交點(diǎn)為頂點(diǎn)，需要特別處理通常射線就是掃描線10Scan-linemethodsWorksforgeometricallyaswellaspixel-wisedefinedareasGreedyapproachveryslow!!!?Improvementspossiblebyexploitingcoherence!(連貫性):11Scan-linemethodsTheapproachisbasedonscan-linecoherence(連貫性):Neighboringpixelsareverylikelytogetthesameintensity/colorvaluesassigned.Thepixelcharacteristics,i.e.color/intensityvalues,onlychangewhereanedgeofthepolygonintersectsthescanline,i.e.thepartofthescan-linebetweentwointersectionpointsiseithercompletelyinsideorcompletelyoutsideofthepolygon.(掃描線的連貫性)12Scan-linemethods:ExampleExample:

Scanliney=2:

-intersectionwithpolygonatx=1,8-wecansubdividethescanlineinto3sections:x<1:outsidethepolygon1≤x≤8:insidethepolygonx>8:outsidethepolygon13Scan-linemethods:ExampleExample:

Scanliney=4:

-intersectionwithpolygon

atx=1,4,6,8-wecansubdividethescanlineinto5sections:x<1:outsidethepolygon1≤x≤4:insidethepolygon4<x<6:outsidethepolygon6≤x≤8:insidethepolygonx>8:outsidethepolygon14Scan-linemethodsSingularitiesareProblematic:i.e.locationswherethescanlineintersectswithavertexofthepolygon.?considerlocalextremes15LocalextremesofPolygonDefinitionofLocalextremes:thosey-valuesofthecornerofthepolygonwherethesevaluesaregreaterorsmallerthanbothvertices(withrespecttothey-value)attheoppositesideoftheedge.Distinguishtwocases:-Ifthevertexisalocalextreme,

theintersectioncountstwice-Ifthevertexisnotlocalextreme,

theintersectioncountsonceonly16Scan-linemethodsThesimpleorderededgelistalgorithm

(有序邊表算法)

Method:preprocessing+scanconversion17OrderedEdgeListAlgorithmPreprocessing(1)Determineforeveryedgeofthepolygontheintersectionswiththescanlinesatthepixelcenters;ignorehorizontaledges.(2)Storeeveryintersection(x,y)inalist.(3)Sortlistfromtoptobottom,lefttoright.18OrderedEdgeListAlgorithmScanconversion(1)Considerpairsofsubsequentintersections(x1,y1)and(x2,y2)inthelist,i.e.listelement1and2,listelement3and4,…)(2)Duetothepreprocessingstep,weknowthatforeveryscanliney:y=y1=y2,x1≤x2(3)Drawallpixelsalongthescanlineyforwhich:x1≤x<x2

foreveryintegernumberx.19Example:Preprocessing20Example：ScanConversionSeedfillmethods

(種子填充算法)22Seedfillmethods(種子填充算法)Seedfillmethodsfillthearea

boundedbythepolygon

startingfromaninitialpixel

(seed)andaresuitablefor

pixel-wisedefinedareas,

hencealsoforrasterdisplays.seedpoint23ConnectednessofAreas4-connected:

connectedhorizontallyorvertically（四連通）8-connected:additionallydiagonallyconnected（八連通）(區(qū)域的連通性)24ConnectednessDifferencebetween4-and8-connect

連通性：4連通可看作8連通區(qū)域，但對(duì)邊界有要求不同依據(jù)區(qū)域內(nèi)點(diǎn)能否訪問到區(qū)域外的點(diǎn)，對(duì)邊界的要求是:4連通區(qū)域，邊界只要8連通即可8連通區(qū)域，邊界必須是4連通例：如右圖（1）4連通區(qū)域，邊界為○像素（2）8連通區(qū)域，邊界為○和△像素25Examplesfor4-and8-connected264directionsofmovementaredefinedbyboundaryFILO/LIFONote:

somepixelsmaybestoredinthestack

(andalsocolored)multipletimes.SimpleSeedFillAlgorithm27voidFloodFill4(intx,inty,intnew,intold){

intcolor;getPixel(x,y,color);if(color=old)

{setPixel(x,y);FloodFill4(x+1,y,new,old);//rightFloodFill4(x,y+1,new,old);//up

FloodFill4(x–1,y,new,old);//leftFloodFill4(x,y–1,new,old);//down}}SimpleFlood-FillAlgorithm28Seedfillmethods:Example-1

(numbersindicatelocationofpixelswithinthestack)29Seedfillmethods:Example-1

(numbersindicatelocationofpixelswithinthestack)travel:→R→U→L→Dstack:FILOsomepixelsmaybestoredinthestack(andalsocolored)multipletimes.30Seedfillmethods:Example-2areawithhole5.Antialiasing(反走樣)(Hearn&Baker,Section4-17,P175-182)32AliasingandAntialiasingwhatisaliasing?whatisthereasonforaliasing?whatcanwedoagainstit?33AliasingGenerally,aliasingeffects

areerroneousreconstructionofa(continuous)signalduesamplingratewithatoolowfrequency(seealsoNyquisttheorem).用離散量(像素)表示連續(xù)的量(圖形)而引起的失真，稱為走樣或稱為混淆。34Reasonsforaliasingerrorsthatarecausedbythediscretization

ofanalogdatatodigitaldatatoobadresolutiontoofewcolorstoofewimages/secgeometricerrorsnumericerrors35AliasingThetermaliasing

intheareaofcomputergraphicsisused,besidesvisualeffectsresultingfromtheabove(e.g.aliasingwhenrenderingacheckerboard),todescribevisualartifacts

resultingfromtheprocessofscanconversion.

(e.g.staircasingwhendrawingdiagonallines).36AliasingAliasingartifactsincomputergraphicsTextureartifacts(e.g.checkerboard)Staircasingartifactswhenrasteringcurves?jaggedlinesDisappearanceofobjectswhicharesmallerthanapixelDisappearanceofsmall,skinnyobjectsLossofdetailincompleximages“Flipping”smallobjectsduringmotion/animation37AliasingStaircasingartifacts,jaggededgesThepreviouslydiscussedtechniquesforrasteringstraightlinesandcurvesresultinstaircasingartifacts(left)sinceitisonlypossibletodrawpointsatfixedrasterlocations.Theselocationsaregenerallynotidenticaltothereal/ideallocationsofthesepoints.階梯狀的、鋸齒狀的38VariousAliasingEffects39AliasingfromtoofewColorsartificialcolorborderscanappear40AliasinginAnimationsjumpingimages"worming"41AntialiasingAntialiasing(反走樣)

methodsaretechniques(e.g.over-sampling,filtering)thattrytominimizethealiasingeffect.EliminatingthealiasingeffectisoftenNOTpossible

(alreadyfromatheoreticalpointofview).42ShannonSamplingTheorem43ShannonSamplingTheorem44Antialiasing:NyquistSamplingFrequency45SolutionsagainstAliasing?1.improvethedeviceshigherresolutionmorecolorlevelsfasterimagesequence2.improvetheimages=antialiasingpost-processingpre-filteringsoftwareexpensive46AntialiasingStrategiessupersamplingstraight-linesegmentsareasamplingstraight-linesegmentsfilteringtechniquescompensatingforline-intensitydifferencesantialiasingareaboundaries(adjustingboundarypixelpositions)adjustingboundarypixelintensity47Antialiasing:SupersamplingLinesSupersampling(超級(jí)采樣)48Antialiasing:SupersamplingLines49Antialiasing:AreaSamplingLinescalculatethepixelcoverageexactlycanbedonewithincrementalschemesunweighted

area

sampling(非加權(quán)區(qū)域采樣)

weightedareasampling(加權(quán)區(qū)域采樣)50Unweighted

Area

SamplingSettingintensityproportionaltotheamountofareacovered.theintensitiesofneighboringpixelschangecontinuously51Unweighted

Area

Sampling兩點(diǎn)認(rèn)識(shí):(1)像素不是點(diǎn)，一個(gè)小區(qū)域，形狀由硬件決定(如正方形)；(2)直線有寬度。掃描轉(zhuǎn)換時(shí)兩點(diǎn)假設(shè):(1)象素是數(shù)學(xué)上抽象的點(diǎn)，它的面積為0，它的亮度由覆蓋該點(diǎn)的圖形的亮度所決定；(2)直線段是數(shù)學(xué)上抽象直線段，它的寬度為0。反走樣方法:

把像素看作一個(gè)平面區(qū)域進(jìn)行采樣(1)將直線段看作具有一定寬度的狹長(zhǎng)矩形；(2)當(dāng)直線段與像素有交時(shí)，求出兩者相交區(qū)域的面積；(3)根據(jù)相交區(qū)域的面積，確定該象素的亮度值。相鄰兩個(gè)象素的灰度之間有一個(gè)平緩的過渡，淡化了鋸齒狀的邊界。52WeightedAreaSampling權(quán)函數(shù)：

或經(jīng)驗(yàn)值，可自定義；直線與像素相交，相交區(qū)域?yàn)锳’，則直線對(duì)象素的亮度的貢獻(xiàn)為：W(X,Y)=1：非加權(quán)情形。53WeightedAreaSampling加權(quán)區(qū)域采樣算法（直線段情形）：求直線段與像素的相交區(qū)域A’；計(jì)算的值；用上面的值乘以像素的最大灰度值，即為像素的顯示灰度值。54WeightedAreaSampling加權(quán)區(qū)域采樣的離散算法：分割像素成n個(gè)子像素{Ai},面積為1/n，每個(gè)子像素對(duì)原像素的亮度的貢獻(xiàn)為將各權(quán)值保存在一張加權(quán)表中。求所有子像素中心落在直線段內(nèi)的子像素集；計(jì)算這些子像素對(duì)原像素亮度的和例：加權(quán)表的取法55Antialiasing:FilteringTechniquescontinuousoverlappingweightingfunctionstocalculatetheantialia