计算机图形学computer graphics课件15

FromVerticestoFragmentsSoftwareCollege,ShandongUniversityInstructor:ZhouYuanfengE-mail:yuanfeng.zhou@ReviewShadinginOpenGL;Lights&Material;Fromvertextofragment:Cohen-Sutherland2ProjectionFragmentsClippingShadingBlackboxSurfacehiddenTextureTransparency3ObjectivesGeometricProcessing:Cyrus-BeckclippingalgorithmLiang-BarskyclippingalgorithmIntroduceclippingalgorithmforpolygonsRasterization:DDA&BresenhamCohen-SutherlandIncaseIV:o1&o2=0Intersection:ClippingLinesbySolvingSimultaneousEquations4SolvingSimultaneousEquationsEquationofaline:Slope-intercept:y=mx+hdifficultforverticallineImplicitEquation:Ax+By+C=0Parametric:Linedefinedbytwopoints,P0andP1P(t)=P0+(P1-P0)tx(t)=x0+(x1-x0)ty(t)=x0+(y1-y0)t6ParametricLinesandIntersectionsForL1:x=x0l1+t(x1l1–x0l1)y=y0l1+t(y1l1–y0l1)ForL2:x=x0l2+t(x1l2–x0l2)y=y0l2+t(y1l2–y0l2)TheIntersectionPoint:x0l1+t1(x1l1–x0l1)

=x0l2+t2(x1l2–x0l2)y0l1+t1

(y1l1–y0l1)

=y0l2+t2(y1l2–y0l2)Cyrus-Beckalgorithm(1978)forpolygonsMikeCyrus,JayBeck."Generalizedtwo-andthree-dimensionalclipping".Computers&Graphics,1978:23-28.GivenaconvexpolygonR:7Cyrus-BeckAlgorithmP1P2ANRparatsparate0≤t≤1,then

isinsideofR;,then

isonRorextension;,then

isoutsideofR.HowtogettsandteCyrus-BeckAlgorithmIntersection:NL

●(P(t)–A)=0SubstitutelineequationforP(t)P(t)=P0+t(P1-P0)Solvefortt=NL

●(P0–A)/-NL

●

(P1-P0)ANLP(t)InsideOutsideP0P1Cyrus-BeckAlgorithmComputetforlineintersectionwithalledges;Discardall(t<0)and(t>1);ClassifyeachremainingintersectionasPotentiallyEnteringPoint(PE)PotentiallyLeavingPoint(PL)(How?)NL●(P1-P0)<0impliesPLNL●(P1-P0)>0impliesPENotethatwecomputedthisterminwhencomputingtCyrus-BeckAlgorithmForeachedge:10L1L2L3L4L5P0P1t1t2t5t3t4paratsparateComputePEwithlargesttComputePLwithsmallesttCliptothesetwopointsCyrus-BeckAlgorithmWhen;thenifif11ThenP0P1isinvisible;Thengotonextedge;Programming:12for（k

edgesofclippingpolygon）{solveNi·(p1-p0);

solveNi·(p0-Ai);if(

Ni·(p1-p0)

==0)//parallelwiththeedge{

if(Ni·(p0-Ai)<0)break;//invisibleelsegotonextedge;

}else//Ni·(p1-p0)!=0{

solveti;if(Ni·(p1-p0)<0)else}}Output:if(ts>te)returnnil;elsereturnP(ts)andP(te)asthetrueclipintersections;Input:If(P0=P1)Lineisdegeneratesoclipasapoint;Liang-BarskyAlgorithm(1984)13TheONLYalgorithmnamedforChinesepeopleinComputerGraphicscoursebooksLiang,Y.D.,andBarsky,B.,"ANewConceptandMethodforLineClipping",

ACMTransactionsonGraphics,3(1):1-22,January1984.Becauseofhorizontalandverticalcliplines:ManycomputationsreduceNormalsPickconstantpointsonedgessolutionfort:tL=-(x0-xleft)/(x1-x0)tR=(x0-xright)/-(x1-x0)tB=-(y0-ybottom)/(y1-y0)tT=(y0-ytop)/-(y1-y0)Liang-BarskyAlgorithm(1984)PEPLP1PLPEP0(-1,0)(1,0)(0,-1)(0,1)15EdgeInnernormalAP1-ALeftx=XL（1，0）（XL，y）（x1-XL，y1-y）Rightx=XR（-1，0）（XR，y）（x1-XR，y1-y）Bottomy=YB（0，1）（x，YB）（x1-x，y1-YB）Topy=YT（0，-1）（x，YT）（x1-x，y1-YT）Liang-BarskyAlgorithm(1984)Whenrk<0,tkisenteringpoint;whenrk>0,tkisleavingpoint.Ifrk=0andsk<0,thenthelineisinvisible;elseprocessotheredges16Liang-BarskyAlgorithm(1984)Let∆x=x2－x1，∆y=y2－y1:ComparisonCohen-Sutherland:RepeatedclippingisexpensiveBestusedwhentrivialacceptanceandrejectionispossibleformostlinesCyrus-Beck:Computationoft-intersectionsischeapComputationof(x,y)clippointsisonlydoneonceAlgorithmdoesn’tconsidertrivialaccepts/rejectsBestwhenmanylinesmustbeclippedLiang-Barsky:OptimizedCyrus-BeckNicholletal.:Fastest,butdoesn’tdo3D18ClippingasaBlackBoxCanconsiderlinesegmentclippingasaprocessthattakesintwoverticesandproduceseithernoverticesortheverticesofaclippedlinesegment19PipelineClippingofLineSegmentsClippingagainsteachsideofwindowisindependentofothersidesCanusefourindependentclippersinapipeline20ClippingandNormalizationGeneralclippingin3DrequiresintersectionoflinesegmentsagainstarbitraryplaneExample:obliqueview21Plane-LineIntersectionsPoint-to-PlaneTestDotproductisrelativelyexpensive3multiplies5additions1comparison(to0,inthiscase)Thinkabouthowyoumightoptimizeorspecial-casethis?23NormalizedFormbeforenormalizationafternormalizationNormalizationispartofviewing(preclipping)butafternormalization,weclipagainstsidesofrightparallelepipedTypicalintersectioncalculationnowrequiresonlyafloatingpointsubtraction,e.g.isx>xmaxtopviewClippingPolygonsClippingpolygonsismorecomplexthanclippingtheindividuallinesInput:polygonOutput:polygon,ornothing25PolygonClippingNotassimpleaslinesegmentclippingClippingalinesegmentyieldsatmostonelinesegmentClippingapolygoncanyieldmultiplepolygonsHowever,clippingaconvexpolygoncanyieldatmostoneotherpolygon26TessellationandConvexityOnestrategyistoreplacenonconvex(concave)polygonswithasetoftriangularpolygons(atessellation)Alsomakesfilleasier(wewillstudylater)TessellationcodeinGLUlibrary,thebestisConstrainedDelaunayTriangulation27PipelineClippingofPolygonsThreedimensions:addfrontandbackclippersStrategyusedinSGIGeometryEngineSmallincreaseinlatencySutherland-HodgmanClippingIvanSutherland,GaryW.Hodgman:ReentrantPolygonClipping.CommunicationsoftheACM,vol.17,pp.32-42,1974Basicidea:ConsidereachedgeoftheviewportindividuallyClipthepolygonagainsttheedgeequationSutherland-HodgmanClippingBasicidea:ConsidereachedgeoftheviewportindividuallyClipthepolygonagainsttheedgeequationAfterdoingallplanes,thepolygonisfullyclippedSutherland-HodgmanClippingBasicidea:ConsidereachedgeoftheviewportindividuallyClipthepolygonagainsttheedgeequationAfterdoingallplanes,thepolygonisfullyclippedSutherland-HodgmanClippingBasicidea:ConsidereachedgeoftheviewportindividuallyClipthepolygonagainsttheedgeequationAfterdoingallplanes,thepolygonisfullyclippedSutherland-HodgmanClippingBasicidea:ConsidereachedgeoftheviewportindividuallyClipthepolygonagainsttheedgeequationAfterdoingallplanes,thepolygonisfullyclippedSutherland-HodgmanClippingBasicidea:ConsidereachedgeoftheviewportindividuallyClipthepolygonagainsttheedgeequationAfterdoingallplanes,thepolygonisfullyclippedSutherland-HodgmanClippingBasicidea:ConsidereachedgeoftheviewportindividuallyClipthepolygonagainsttheedgeequationAfterdoingallplanes,thepolygonisfullyclippedSutherland-HodgmanClippingBasicidea:ConsidereachedgeoftheviewportindividuallyClipthepolygonagainsttheedgeequationAfterdoingallplanes,thepolygonisfullyclippedSutherland-HodgmanClippingBasicidea:ConsidereachedgeoftheviewportindividuallyClipthepolygonagainsttheedgeequationAfterdoingallplanes,thepolygonisfullyclippedSutherland-HodgmanClippingBasicidea:ConsidereachedgeoftheviewportindividuallyClipthepolygonagainsttheedgeequationAfterdoingallplanes,thepolygonisfullyclippedWillthisworkfornon-rectangularclipregions?Whatwould3-D

clippinginvolve?Sutherland-HodgmanClippingInput/outputforalgorithm:Input:listofpolygonverticesinorderOutput:listofclippedpoygonverticesconsistingofoldvertices(maybe)andnewvertices(maybe)Note:thisisexactlywhatweexpectfromtheclippingoperationagainsteachedgeSutherland-HodgmanClippingSutherland-Hodgmanbasicroutine:GoaroundpolygononevertexatatimeCurrentvertexhaspositionp

Previousvertexhadpositions,andithasbeenaddedtotheoutputifappropriateSutherland-HodgmanClippingEdgefromstop

takesoneoffourcases:(Graylinecanbealineoraplane)insideoutsidesppoutputinsideoutsidespnooutputinsideoutsidespioutputinsideoutsidespioutput

poutputSutherland-HodgmanClippingFourcases:sinsideplaneandpinsideplaneAddptooutputNote:shasalreadybeenaddedsinsideplaneandpoutsideplaneFindintersectionpointiAdditooutputsoutsideplaneandp

outsideplaneAddnothings

outsideplaneandpinsideplaneFindintersectionpointiAdditooutput,followedbypSutherland-HodgmanClipping42Point-to-PlanetestAverygeneraltesttodetermineifapointpis“inside”aplaneP,definedbyqandn: (p-q)•n<0: pinsideP (p-q)•n=0: ponP (p-q)•n>0: poutsidePPnpqPnpqPnpq44BoundingBoxesRatherthandoingclippingonacomplexpolygon,wecanuseanaxis-alignedboundingboxorextentSmallestrectanglealignedwithaxesthatenclosesthepolygonSimpletocompute:maxandminofxandy45BoundingBoxesCanusuallydetermineaccept/rejectbasedonlyonboundingboxrejectacceptrequiresdetailedclippingEllipsoidcollisiondetection46RasterizationRasterization(scanconversion)DeterminewhichpixelsthatareinsideprimitivespecifiedbyasetofverticesProducesasetoffragmentsFragmentshavealocation(pixellocation)andotherattributessuchcolor,depthandtexturecoordinatesthataredeterminedbyinterpolatingvaluesatverticesPixelcolorsdeterminedlaterusingcolor,texture,andothervertexproperties.47ScanConversionofLineSegmentsStartwithlinesegmentinwindowcoordinateswithintegervaluesforendpointsAssumeimplementationhasawrite_pixelfunctiony=mx+hScanConversionofLineSegments48Onepixel49DDAAlgorithmDigitalDifferentialAnalyzer(1964)DDAwasamechanicaldevicefornumericalsolutionofdifferentialequationsLiney=mx+hsatisfiesdifferentialequationdy/dx=m=Dy/Dx=y2-y1/x2-x1AlongscanlineDx=1For(x=x1;x<=x2,x++){y+=m;//note:misfloatnumberwrite_pixel(x,round(y),line_color);}50ProblemDDA=foreachxplotpixelatclosestyProblemsforsteeplines51UsingSymmetryUsefor1

m

0Form>1,swaproleofxandyForeachy,plotclosestx52Bresenham’sAlgorithmDDArequiresonefloatingpointadditionperstepWecaneliminateallfpthroughBresenham’salgorithmConsideronly1

m

0OthercasesbysymmetryAssumepixelcentersareathalfintegers(OpenGLhasthisdefinition)

Bresenham,J.E.(1January1965)."Algorithmforcomputercontrolofadigitalplotter".IBMSystemsJournal4(1):25–30.Bresenham’sAlgorithmObserving:Ifwestartatapixelthathasbeenwritten,thereareonlytwocandidatesforthenextpixeltobewrittenintotheframebuffer5354CandidatePixels1

m

0lastpixelcandidatesNotethatlinecouldhavepassedthroughanypartofthispixel55DecisionVariable-d=△x(a-b)disanintegerd<0useupperpixeld>0uselowerpixelHowtocomputeaandb?b-a=(yi+1–yi,r)-(yi,r+1-yi+1)=2yi+1–yi,r–(yi,r+1)=2yi+1–2yi,r–1ε(xi+1)=yi+1–yi,r–0.5=BC-AC=BA=B-A=yi+1–(yi,r+yi,r+1)/2ABCIncrementalForm56ifε(xi+1)≥0,yi+1,r=yi,r+1,pickpixelD,thenextpixelis(

xi+1,yi,r+1)yi,ryi,r+1ABxixi+1DCd1d2yi,ryi,r+1Axixi+1DCd1d2ifε(xi+1)<0,yi+1,r=yi,r,pickpixelC,thenextpixelis(

xi+1,yi,r)Improvementanew=alast–manew=alast–(m-1)bnew=blast+mbnew=blast+(m-1)57----d=△x(a-b)Improvement58Moreefficientifwelookatdk,thevalueofthedecisionvariableatx=kdk+1=dk–2△y,ifdk>0dk+1=dk–2(△y-△x),otherwiseForeachx,weneeddoonlyanintegeradditionandatestSingleinstructionongraphicschipsmultiply2issimple.59BSPdisplayTypeTreeTree*front;Faceface;Tree*back;EndAlgorithmDrawBSP(TreeT;point:w)//w为视点IfTisnullthenreturn;endifIfwisinfrontofT.facethenDrawBSP(T.back,w);Draw(T.face,w);DrawBSP(T.front,w);Else//wisbehindoronT.faceDrawBSP(T.front,w);Draw(T.face,w);DrawBSP(T.back,w);Endifend60HiddenSurfaceRemovalObject-spaceapproach:usepairwisetestingbetweenpolygons(objects)WorstcasecomplexityO(n2)fornpolygonspartiallyobscuringcandrawindependently61ImageSpaceApproachLookateachprojector(nmforann

x

mframebuffer)andfindclosestofkpolygonsComplexityO(nmk)Raytracingz-buffer62Painter’sAlgorithmRenderpolygonsabacktofrontordersothatpolygonsbehindothersaresimplypaintedoverBbehindAasseenbyviewerFillBthenA63DepthSortRequiresorderingofpolygonsfirstO(nlogn)calculationfororderingNoteverypolygoniseitherinfrontorbehindallotherpolygonsOrderpolygonsanddealwitheasycasesfirst,harderlaterPolygonssortedbydistancefromCOP64EasyCases(1)AliesbehindallotherpolygonsCanrender(2)PolygonsoverlapinzbutnotineitherxoryCanrenderindependently65HardCases(3)Overlapinalldirectionsbutcanoneisfullyononesideoftheothercyclicoverlappenetration(4)66Back-FaceRemoval(Culling)

faceisvisibleiff90

-90equivalentlycos

0or

v

•n

0planeoffacehasformax+by+cz+d=0butafternormalization

n=(0010)T

needonlytestthesignofcInOpenGLwecansimplyenablecullingbutmaynotworkcorrectlyifwehavenonconvexobjects67z-BufferAlgorithmUseabuffercalledthezordepthbuffertostorethedepthoftheclosestobjectateachpixelfoundsofarAswerendereachpolygon,comparethedepthofeachpixeltodepthinzbufferIfless,placeshadeofpixelincolorbufferandupdatezbuffer68EfficiencyIfweworkscanlinebyscanlineaswemoveacrossascanline,thedepthchangessatisfya

x+b

y+c

z=0Alongscanline

y=0

z=-

xInscreenspace

x=1

69Scan-LineAlgorithmCancombineshadingandhsrthroughscanlinealgorithmscanlinei:noneedfordepthinformation,canonlybeinnooronepolygonscanlinej:needdepthinformationonlywheninmorethanonepolygon70ImplementationNeedadatastructuretostoreFlagforeachpolygon(inside/outside)IncrementalstructureforscanlinesthatstoreswhichedgesareencounteredParametersforplanes71VisibilityTestingInmanyrealtimeapplications,suchasgames,wewanttoeliminateasmanyobjectsaspossiblewithintheapplicationReduceburdenonpipelineReducetrafficonbusPartitionspacewithBinarySpatialPartition(BSP)Tree72SimpleExampleconsider6parallelpolygonstopviewTheplaneofAseparatesBandCfromD,EandF73BSPTreeCancontinuerecursivelyPlaneofCseparatesBfromAPlaneofDseparatesEandFCanputthisinformationinaBSPtreeUseforvisibilityandocclusiontesting74PolygonScanConversionScanConversion=FillHowtotellinsidefromoutsideConvexeasyNonsimpledifficultOddeventestCountedgecrossingsWindingnumberodd-evenfill75Wind