Drawing Antialiased Lines with OpenGL | by Mapbox

I worked on an experiment that uses only two vertices per line segment, but this way of drawing lines requires three draw calls per line. To ... OpeninappHomeNotificationsListsStoriesWritePublishedinmapsfordevelopersDrawingAntialiasedLineswithOpenGLByKonstantinKäferMapsaremostlymadeupoflines,aswellastheoccasionalpolygonthrownin.Unfortunately,drawinglinesisaweakpointofOpenGL.TheGL_LINESdrawingmodeislimited:itdoesnotsupportlinejoins,linecaps,non-integerlinewidths,widthsgreaterthan10px,orvaryingwidthsinasinglepass.Giventheselimitations,it’sunsuitableforthelineworknecessaryforhigh-qualitymaps.Here’sanexampleofGL_LINES:Additionally,OpenGL’santialiasing(multisampleantialiasing)isnotreliablypresentonalldevices,andgenerallyisofpoorqualityanyway.Asanalternativetonativelines,wecantessellatethelinetopolygonsanddrawitasashape.Afewmonthsago,Iinvestigatedvariousapproachestolinerenderingandexperimentedwithonethatdrawssixtrianglesperline:Twopairsoftrianglesformaquadrilateralgradientoneachsides,andaquadrilateralinthemiddlemakesuptheactualline.Thegradientsprovideantialiasing,sothatthelinefadesoutattheedges.Whenscaleddown,thisproduceshighqualitylines:Unfortunately,generatingsixtrianglesperlinesegmentmeansgeneratingeightverticesperlinesegment,whichrequiresalotofmemory.Iworkedonanexperimentthatusesonlytwoverticesperlinesegment,butthiswayofdrawinglinesrequiresthreedrawcallsperline.Tomaintainagoodframerateweneedtominimizethenumberofdrawcallsperframe.AttributeinterpolationtotherescueOpenGL’sdrawingworksintwostages.First,alistofverticesispassedtothevertexshader.Thevertexshaderisbasicallyasmallfunctionthattransformseveryvertex(inthemodelcoordinatesystem)toanewposition(thescreencoordinatesystem),sothatyoucanreusethesamearrayofverticesforeveryframe,butstilldothingslikerotate,translate,orscaletheobjects.Threeconsecutiveverticesformatriangle.Allpixelsinthatareaarethenprocessedbythefragmentshader,alsocalledthepixelshader.Whilethevertexshaderisrunonceforeveryvertexinthesourcearray,thefragmentshaderisrunonceforeverypixelinatriangletodecidewhatcolortoassigntothatpixel.Inthesimplestcase,itmightassignaconstantcolor,likethis:glslvoidmain(){gl_FragColor=vec4(0,0,0,1);}ThecolororderisRGBA,sothisexamplerendersallfragmentsasopaqueblack.Ifwerenderedlinesbycreatingpolygonsfromthoselines,andassignaconstantcolortoallpixelsinthatpolygon,we’dstillhavehorriblyaliasedlines.Weneedawaytodecreasethealphavaluefrom1to0asthepixelsapproachthepolygon’sborder.Whentransformingverticesinthevertexshader,OpenGLallowsustoassignattributestoeveryvertex,forexample:Theseattributesarethenpassedontothepixelshader.Theinterestingpartisthis:sinceapixelcan’tbedirectlyassociatedwithasinglevertex,theattributesareinterpolatedbetweenthreediscretevaluesaccordingtothepixel’sdistancetothethreeverticesthatmakeupthetriangle:Thisinterpolationproducesgradientsbetweenthevertices.ThisisthebasisforthelinedrawingmethodI’mgoingtodescribe.RequirementsWhendrawinglines,wehaveacoupleofrequirements:Variablelinewidth:Wewanttochangethelinewidthineveryframewedrawsothatwhentheuserzoomsin/out,wedon’thavetotessellatethelinetotrianglesoverandoveragain.Thismeansthatthefinalvertexpositionmustbecalculatedinthevertexshaderatrendertimeandnotwhenwesetupthescene.Endcaps(butt,round,square):Thisdescribeshowtheendsoflinesaredrawn.Linejoins(miter,round,bevel):Thisdescribeshowjointsbetweentwolinesaredrawn.Multiplelines:Forperformancereasons,wewantlineswithvaryingwidthsandcolorsinonedrawcall.LineTessellationSincewewanttochangethelinewidthdynamically,wecannotperformthecompletetessellationatsetuptime.Instead,werepeatthesamevertextwice,sothatforalinesegment,weendupwithfourvertices(marked1-4)inourarray:Inaddition,wecalculatethenormalunitvectorforthelinesegmentandassignittoeveryvertex,withthefirstvertexgettingapositiveunitvectorandthesecondanegativeunitvector.Theunitvectorsarethesmallarrowsyouseeinthispicture:Inourvertexshader,wecannowadjustthelinewidthatrendertimebymultiplyingthevertex’sunitvectorwiththelinewidthsetforthatdrawcall,andendupwithtwotriangles,visualizedinthispicturebythereddottedline.Thevertexshaderlookssomethinglikethis:```glslattributevec2a_pos;attributevec2a_normal;uniformfloatu_linewidth;uniformmat4u_mv_matrix;uniformmat4u_p_matrix;voidmain(){vec4delta=vec4(a_normal*u_linewidth,0,0);vec4pos=u_mv_matrix*vec4(a_pos,0,1);gl_Position=u_p_matrix*(pos+delta);}```Inthemainfunction,wemultiplythenormalunitvectorwiththelinewidthtoscaleittotheactuallinewidth.Thecorrectvertexposition(inscreenspace)isdeterminedbymultiplyingitwiththemodel/viewmatrix.Afterward,weaddtheextrusionvectorsothatthelinewidthisindependentofanymodel/viewscaling.Finally,wemultiplybytheprojectionmatrixtogetthevertexpositioninprojectionspace(inourcase,weuseaparallelprojectionsothereisnotmuchgoingon,exceptforscalingthescreenspacecoordinatestotherangeof0..1).AntialiasingWenowhavelinesegmentsofarbitrarywidth,butwestilldon’thaveantialiasedlines.Toachievetheantialiasingeffect,we’regoingtousethenormalunitvectors,butthistimeinthepixelshader.Inthevertexshader,wejustpassthroughthenormalunitvectorstothepixelshader.Now,OpenGLinterpolatesbetweenbothnormalssothatthecalculatedvectorwereceiveinthepixelshaderisagradientbetweenthetwounitvectors.Thismeanstheyarenolongerunitvectors,sincetheirlengthislessthanone.Whenwecalculatethelengthofthevector,wegettheperpendiculardistanceofthatpixelfromtheoriginallinesegment,intherangeof0..1.Wecanusethisdistancetocalculatethepixel’salphavalue.Ifwefactorinthelinewidth,wejustassigntheopaquecolortoalldistancesthatarewithinthelinewidth,minusa“feather”distance(seeimagebelow).Betweenlinewidth-featherandlinewidth+feather,weassignalphavaluesbetweenoneandzero,andtoallfragmentsthatarefurtherthantheunitvectorawayfromtheline,weassignanalphavalueofzero(rightnow,therearenopixelsthatfulfillthatproperty,butwe’llencounterthemsoon).Apartfromthelinewidth,wecanalsovarythefeatherdistancetogetblurredlines,orshadows.Wecanreduceittozerotohavealiasedlines.Afeathervalueof0.5producesregularantialiasingthatlooksverysimilartowhatAggproduces.Afeathervaluebetween0and0.5producesresultsmimickingMapnik’sgammavalue.LineJoinsThetechniqueaboveworksforsingularlinesegments,butinmostcaseswe’redrawinglinescomposedofseveralsegmentsjoinedtogether.Whenjoininglinesegments,wehavetochoosealinejoinstyleandmovetheverticesaccordingly:Earlierwecalculatedthenormalofthelinesegmentandassignedthattothevertex.Thisnolongerworksinthecaseoflinejoinsbecauseweactuallyneedtocalculateaper-vertexnormal,ratherthanaperlinesegmentnormal.Theper-vertexnormalistheanglebisectornormalofthetwolinesegmentnormals.Unitvectorsforlinejoinsalsodon’tworkbecausethedistanceofthevertexfromthelineatjoinlocationsisactuallyfurtherawaythanone.Soratherthanusingtheanglebisectorunitvector,wejustaddthelinesegmentunitvectors,whichresultsinavectorthatisneitheraunitvectornoranormal.Icallitanextrusionvector.Unfortunately,wenowhaveanotherproblem:extrusionvectorsarenolongernormaltothelinesegment,sointerpolationbetweentwoofthemwillnotyieldaperpendiculardistance.Instead,weintroduceanotherper-vertexattribute,thetexturenormal.Thisisavalueofeither1or-1,dependingonwhetherthenormalpointsupordown.Thisisofcoursenotanactualnormalbecauseithasnoorientationin2Dspace,butit’ssufficientforachievinginterpolationbetween1and-1togetourlinedistancevaluesfortheantialiasing.Sincewedon’twanttointroduceyetanotherbyte,ofwhichwe’deffectivelyuseonlyasinglesignbit,weencodethetexturenormalintotheactualvertexattribute.Thevertexattributesuse16-bitintegers(-32768..32767)thatarebigenoughtoholdourtypicalvectortilecoordinatesof0..4095.Wedoubleeachcoordinate(0..8190)andthenusetheleastsignificantbittostorethetexturenormal.Inthevertexshader,weextractthatbitandusethemodel/viewmatrixtoscaleourcoordinatesdowntotheactualsize.Tosavememory,weencodetheextrusionvectorswithonebyteperaxis,sowehavean(integer)rangeof-128..127foreveryaxis.Unfortunately,extrusionvectorscangrowarbitrarilylongforlinejoinsbecausetheextrusionvectorlengthgrowstoinfinityastheanglegetsmoreacute.Thisisacommonproblemwhendrawinglinejoins,andthesolutionistointroducea“miterlimit”.Iftheextrusionvectorgetslongerthanthemiterlimit,thelinejoinisswitchedtoabeveljoin.Thisallowsustoscaleupthefloatingpointnormaldramaticallysothatweretainenoughangleprecisionfortheextrusionvector.MapboxGLLookforfutureblogpostsaswetalkaboutmoreofthedesignandengineeringworkthathasgoneintoMapboxGL.Linesarejustasmallbutnecessarypartofthebiggerpictureofwhatgoesintohigh-qualitycustommapsrenderedinrealtimeonthedevice.KonstantinKäferKonstantinisanapplicationdeveloperatMapbox.HeisanexpertinJavaScript,node.js,C++,OpenGLandSQLiteand…www.mapbox.comMorefrommapsfordevelopersFollowtheofficialMapboxblogReadmorefrommapsfordevelopersAboutHelpTermsPrivacyGettheMediumappGetstartedMapbox24KFollowersmappingtoolsfordevelopers+preciselocationdatatochangethewayweexploretheworldFollowMorefromMediumJeannotMullerinXojoDevelopmentOpensourceXojoWeb2pluginsJeremyChengMakeTelegramMessengerUsableChelaruAdrianMakeyourNextcloudreadyforaccessingovertheinternetBrendanBrowninTheArcadiaSourceArchitectingasignupfunnelappwithReactandXState:Part1HelpStatusWritersBlogCareersPrivacyTermsAboutKnowable