Graphics] Computational Geometry and Object Modeling

GregEsch∗

∗Oregon

PeterWonka†StateUniversity

PascalM¨uller‡StateUniversity

EugeneZhang∗

‡ETH

†Arizona

Z¨urich

Abstract

Thispaperaddressestheproblemofinteractivelymodelinglarge

streetnetworks.Weintroduceamodelingframeworkthatusesten-sorfieldstoguidethegenerationofastreetgraph.Ausercaninter-activelyeditastreetgraphbyeithermodifyingtheunderlyingten-sorfieldorbychangingthegraphdirectly.Thisframeworkallowstocombinehigh-andlow-levelmodelingoperations,constraints,andproceduraldescriptions.

CRCategories:F.4.2[MathematicalLogicandFormalLan-guages]:GrammarsandOtherRewritingSystemsI.3.5[Com-puterGraphics]:ComputationalGeometryandObjectModelingI.3.7[ComputerGraphics]:Three-DimensionalGraphicsandReal-ismI.6.3[SimulationandModeling]:ApplicationsJ.6[Computer-AidedEngineering]:Computer-AidedDesign(CAD)

Keywords:proceduralmodeling,streetmodeling,streetnetworks,tensorfields

1Introduction

Thispaperpresentsasolutiontoefficientlymodelthestreetnet-worksoflargeurbanareas.Thecreationofcompellingmodelsisacrucialtaskintheentertainmentindustry,varioustrainingapplica-tions,andurbanplanning.However,modelingthedetailsoflargethree-dimensionalurbanenvironments,isverytimeconsumingandcanrequireseveralmanyearsworthoflabor.Apowerfulsolu-tiontolarge-scaleurbanmodelingistheuseofproceduraltech-niques[M¨ulleretal.2006;Wonkaetal.2003;ParishandM¨uller2001].

ParishandM¨uller[2001]werethefirsttonotethatthestreetnet-workisthekeytocreatealargeurbanmodel,andtheypresentedasolutiontomodelstreetnetworksbasedonL-systems.Startingfromasinglestreetsegmenttheyprocedurallyaddfurtherseg-mentstogrowacompletestreetnetwork,similartogrowingatree[Prusinkiewiczetal.2003].Whilethisalgorithmcreatedahighqualitysolution,thereisasignificantremainingchallenge:themethoddoesnotallowextensiveuser-controloftheoutcometobeeasilyintegratedintoaproductionenvironment.Afterastreetnet-workiscreated,theusercanuseatraditionalmodelingtooltomovetheverticesinthegraph.However,oftentheprocedurallygeneratedgraphrequiresasignificantamountofeditinginordertomatchuserexpectations.Whenthishappens,theuserwillneedtoregeneratethecompleteenvironmentbutitisnotguaranteedthatmoredesir-ableresultscanbegenerated.

Toaddressthislimitationofapurelyproceduralapproach,wepro-videaratherdifferentalternativetostreetmodelingthatallowstointegrateawidevarietyofuserinput.Thekeyideaofthispaperistousetensorfieldstoguidethegenerationofstreetgraphs.Ausercaninteractivelyeditastreetgraphbyeithermodifyingtheunderlyingtensorfieldorbychangingthegraphdirectly.Thisal-lowsforefficientmodeling,becausewecancombinehigh-leveland

∗{eschgr|zhange}@eecs.oregonstate.edu,Corvallis,OR97331†peter.wonka@asu.edu,Tempe,AZ85287‡pmueller@vision.ee.ethz.ch,Switzerland

low-levelmodelingoperations,constraints,andproceduralmeth-ods.Themajorcontributionsofthispaperareasfollows:•Wearethefirsttointroduceaproceduralapproachtomodelurbanstreetnetworksthatcombinesinteractiveuser-guidededitingoperationsandproceduralmethods.Wewillidentifyimportantpatternsinstreetnetworksandimportanteditingoperationsthatenabletheusertomodelthesepatterns.•Weareintroducinganewmethodologytographmodelingingeneral.Theideaoftensor-guidedgraphmodelingtogetherwiththetightintegrationofinteractiveeditingandproceduralmodelinghasnotbeenexploredpreviouslyinrelatedmodel-ingproblems,suchasmodelingofbark,cracks,fracture,ortrees.

2RelatedWork

Ourapproachtoproceduralurbanmodelingfollowstheoutlinepre-sentedbyParishandM¨uller[2001],whofirstmodelastreetnet-work,thenparcels,andfinallythree-dimensionalgeometry.Wefocusonthemodelingofstreetnetworksincludingthegenerationofthree-dimensionalgeometry,andourapproachcanbecomple-mentedwithshapegrammars[M¨ulleretal.2006;Wonkaetal.2003]forbuildingstoobtainacompletemodelingsystemforur-banenvironments.Inthefollowingwereviewliteraturedescribingroadconstructionandgraphmodelingalgorithms.

RoadConstruction:Informationaboutthegeometryofroadcon-structioncanbefoundinthecivilengineeringliterature.Werec-ommendthetext[AASHTO2004]asacomprehensiveoverview.OtherusefulresourcesaretheHighwayCapacityManual[Board2000]andthetextbookbyManneringetal.[Manneringetal.2005].Streetgraphspresentafascinatingmodelingchallenge,becausetheyexhibitamixtureoffairlyregularandorganicpatterns.GraphGeneration:Themostsuccessfulalgorithmforstreetmod-elingtodatewaspresentedbyParishandM¨uller[2001],whoex-tendL-systemsandgrowstreetsegmentslikebranchesinatreeuntiltheyintersectanexistingstreetsegment.L-systemshavebeenverysuccessfullyappliedtoplantmodeling[PrusinkiewiczandLindenmayer1991;Prusinkiewiczetal.1994;MˇechandPrusinkiewicz1996;Prusinkiewiczetal.2001]andprovideanin-spirationformanygraphlayoutproblems.

Wewerealsoinspiredbyapproachestomodeliceraylatticede-sign[Stiny1977],mortarinbricklayouts[Legakisetal.2001],dif-fusionlimitedaggregation[WittenandSander1981],andcracksinBantikrenderings[Wyvilletal.2004].However,thesimilaritiesoftheirappearancestostreetlayoutswereratherremote.Averyinter-estingclassoflayoutalgorithmsusesVoronoiDiagrams[Bergetal.2000]of(randomly)distributedpoints.Thisideawasextendedtogeneratetextures[Worley1996],mosaics[Hausner2001],fracturepatterns[Mould2005],andevensomestreetpatterns[Sunetal.2002;Glassetal.2006].Jigsawimagemosaics[KimandPellacini2002]areanotherinterestingextensiontolayoutarbitraryshapes.Whilesomeofthesealgorithmscanmatchonespecificstreetpat-ternthatlookslikemudcracks,weproposeasystemthatallowsamuchwiderrangeandmorefrequentstreetlayouts.Additionally,weallowforamuchwiderrangeofeditingoperations.

Wealsobrieflyconsideredamodelingsystembasedonphys-icalsimulations.Simulationcansuccessfullymodelreaction-diffusion[Turk1991;WitkinandKass1991]andvariousmeth-odsforfractureformationonsurfaces[Hirotaetal.1998;O’BrienandHodgins1999;LefebvreandNeyret2002;FederlandPrusinkiewicz2004;Smithetal.2001;NeffandFiume1999].Wechosenottoworkwithphysicalsimulation,becausetheincorpo-rationofeditingoperationsistraditionallyverydifficultanditisalsounclearwhattypeofextensionsareneededtogenerateawiderrangeofstreetpattern.

Anotherpowerfulgraphgenerationalgorithmwasproposedinthecontextofmodelingleafvenationpatterns[Runionsetal.2005].ThisalgorithmgrowsleafveinstowardsAuxinsourcessimilartohowstreetsin[ParishandM¨uller2001]growtowardspopulationcenters.

3Overview

Inthissection,weexplainthemajorideaofthepaper,thestructureofthepaper,anddefinitionsandconceptsimportantfortheunder-standingoflatersections.

StreetNetworks:Wemodelahierarchyofstreets:majorroadsandminorroads.Majorroadsaretypicallymajorbusinessroadsandlocalhighways,andminorroadsareusuallyresidentialandbackroads.WestoreastreetnetworkasagraphG=(V,E)whereVareasetofnodesandEareasetofedges.Nodeswiththreeormoreincidentedgesarecrossings.Westoreattributeswithnodesandedges,suchasroadwidth,roadtype,pavementmarkings,andthetypeoflanes.Oneofthemostfascinatingaspectsaboutstreetgraphsisthewidevarietyofdifferentpatterns.Weneedamodelingmethodologythatcanhandlethesepatternswithawiderangeofregularity.Insection4,wewillhighlightsomeofthechallenges.

Figure1:Thisfigureillustrateshowadesignedtensorfield(left)canguidethegenerationofastreetgraph(right).

StreetNetworksasStreamlinesofTensorFields:Adominantaspectofstreetpatternsistheexistenceoftwodominantdirections.Thisobservationinspiredustousetensorfieldstoguidethestreetplacement.Tensorfieldsgiverisetotwosetsoftensorlines:Onefollowsthemajoreigenvectorfield,andtheothertheminoreigen-vectorfield.Oursolutiontostreetmodelingistointeractivelycre-ateatensorfieldthatguidestheroadnetworkgeneration.Thisconceptisillustratedinfigure1.Tensorlineshavebeenusedpre-viouslytovisualizetensorfields[WilsonandBrannon2005],togeneratepen-and-inksketchingofsmoothsurfaces[HertzmannandZorin2000;Zhangetal.2007],andtoremesh3Dgeometry[Alliezetal.2003;MarinovandKobbelt2004;Zhangetal.2007].Workflow:Oursystememploysathree-stagepipeline.First,ter-rainandpopulationdensitymapsareeitherprocedurallygenerated,painted,orextractedfromrealdatasets.Next,theusercreatesa

tensorfieldonthetheterrainusingtheeditingtoolsprovidedbyoursystem.Attheendofthisstep,nicely-spacedmajorandminortensorlinesaregeneratedaccordingtothetensorfield.Theselinesformagraph.Finally,theusercanmodifythegraph.Thisgraphcanthenbeusedasinputtoaproceduralmodelingtooltocreatethree-dimensionalgeometryforroads,buildings,andvegetation.PaperOverview:Todescribeoursystem,wewillfirstdemon-stratehowsuitabletensorfieldscanbefoundtomatchimportantstreetpatterns(section4).Second,wewillexplaininsection5whatoperationsareimportanttointeractivelyeditandcombineten-sorfields.Third,section6explainshowwegenerateroadnetworksfromatensorfieldandadditionalgraph-basedprocessingopera-tions,andsection7explainshowthree-dimensionalgeometryisgeneratedfromtheroadnetwork.Weshowsomerenderingsinsec-tion8anddiscussourcontribution,applications,andcomparisontorelatedworkinsection9.Conculsionsaregiveninsection10.TensorFieldDefinitions:Inthispaper,atensortreferstoa󰀂2×2symmetricand󰀃tracelessmatrix,whichisoftheformRcos2θsin2θsin2θ−cos2θwhereR≥0andθ∈[0,2π).Themajor

󰀂eigenvectorsoftare{λcosθ󰀃|λ=0},andtheminoreigenvec-󰀂sinθtorsare{λcos(θ+π󰀃sin(θ+π2)|λ=0}.Themajorandminoreigen-vectorsareperpendicular2)

toeachother,andtogethertheyformacross.

AtensorfieldTisacontinuousfunctionthatassociateseverypointp∈R2withatensorT(p).pissaidtobeadegeneratepointifT(p)=0.Otherwise,itisregular.AdegeneratepointpisisolatedifthereexistsacompactneighborhoodNofpsuchthatpistheonlysingularityintheinteriorofNandtherearenosingularitiesontheboundaryofN.Anisolatedsingularitycanbecharacterizedusingitstensorindex,whichisdefinedintermsofthewindingnumberoftheGaussmap.Anotherimportantandrelevantconceptistensorlines,whichdescribecurvesthataretangenttoaneigenvectorfieldeverywherealongitspath.Atensorlineiseithermajororminordependingonthetypeoftheunderlyingeigenvectorfield.Pleasenotethatthemajorandminoreigenvectorsofatensorfieldarenotrelatedtomajorandminorroads.

4StreetPatternsandTensorFields

Inthissectionweshowimportantconceptsofstreetnetworksandshowhowtoencodetheseconceptsastensorfields.WebuilduponclassificationsmadebyParishandMueller[2001],butourmethod-ologytoencodestreetpatternsistotallydifferenttoallowforinter-activeediting.Inthefollowingwewillfirstexplainhowtocreatesomeidealizedelementsandthengiveoursolutiontocreatemorevariationsinthestreetpattern.

Grid:Animportantbuildingblockformostcitiesisthegridpat-tern.Parcelsaregeneratedbytwoorthogonalsetsofparallelroads.Agridpatterncanbedefinedbyaregulartensorfieldelementdefiningthedirectionofthemajoreigenvector.Seefigure2foratensorfieldguidingstreetsinaregulargridpattern.󰀅Giventhedirection(vx,vy)definedatp0wecancomputel=

v2x+v2yand

θ=arctan(v

vy

x

)anddefinethefollowingbasisfield:󰀂

󰀃

T(p)=e

−d󰀊p−p0󰀊2

l

cos2θsin2θsin2θ−cos2θ(1)

wheredisadecayconstant.

Figure2:Left:Atensorfieldencodingaregulargrid.Right:Theresultingstreetnetwork.Radial:Radialpatternappearindifferentcontexts.Forexample,radialpatternsoccurattheminorleveltoaccessresidentialhomes(seefigure3rightforamapsectionfromScottsdale,Arizona).Otherexamplesareroadsaroundimportantmonuments,suchastheArcdeThriompheinParis.However,inthesecontextsthera-dialpatternismorenoisy.Tocreatearadialpatternatpacenterdesignelement,whosemajortensor0=(xlines0,yare0)wecanusecirclesandminortensorlinesemanatefromthecenterpoint.Thebasisfieldofacenterelement(radialpattern)hasthefollowingform:

󰀃

T(p)=e−d󰀊p−p20󰀊

2

󰀂

y2−x−2xy−2xy

−(y2−x2)

(2)

wherex=xp−x0andy=yp−y0.

Figure3:Aprocedurallygeneratedradialpattern(middle)anditstensorrepresentation(left).TheimageshownintherightisaradialpatternfoundinScottsdale,Arizona.

Boundary:Therearemanyexamplesofroadsthatarebuiltattheboundaryofnaturalorman-madestructures.Exampleareroadsnexttotheshoreline,suchasthehighwayoneinCalifornia(seefigure4).Otherexamplesareroadsattheboundaryofparksandroadssurroundingpopulationcenters.Todefineatensorfieldforaboundarypatternweproceedasfollows.

Theboundaryofaregionisrepresentedasapolyline,whichcon-sistsofanumberofconnectedlinesegments.Notetheboundarycanbeeitheropen(coastline)orclosed(boundaryofapark).Wefirstextractthetrianglestrip{T1,...Tn}thatcontainsthepolyline.Wethenassignvectorvaluestotheverticesofthetrianglesinthestripaccordingtotheorientationsofthepolylineinsidethetrian-gles.Forexample,ifalinesegmentABisinsideatriangleassignthevectorv=−AB→

Ti,we

tothethreeverticesofTmorethanonetrianglesinthesamestrip,i.Ifavertexissharedbytheaverageisused.Thevectorvaluesattheseverticeswillthenbetreatedaspartoftheboundaryconditionsforfieldsmoothinginordertoobtainsmoothtransitionsintounspecifiedregions.

Figure4:Left:AmapofthehighwayoneinCalifornia.Right:Atensorfieldandaroadgeneratedbythecoastline.

Heightfield:Thenaturalelevationisanimportantconstraintformostroadconstruction.Wecanobservethatroadsarebuiltac-cordingtothegradientoftheheightfield.Toderiveaten-sorfield∇H󰀆fromaheightfield

H(x,y),󰀂=∂H/∂x∂H/∂y󰀁wecomputethegradient.WethenfindthetensorfieldT(x,y)=Rcos2θsin2θ󰀃

sin2θ−cos2θwhoseminoreigenvectorfieldmatchesthe

gradientoftheheightfieldeverywhere,i.e.θ=arctan(∂∂H/∂y

H/∂x)+π2

andR=󰀄

(∂H/∂x)2+(∂H/∂y)2.

TransitionsinDensity:Atcityborderstheroaddensitydecreases.

Forexample,figure5leftshowsanexamplefromthenorthofDen-ver.Ifwelookathorizontalcrosssectionsofthemapandcountthemajorroads(yellow),wecanseeagradualtransitionfromaperfectsquaremilerastertoonlyoneroadatthetop.Transitionsindensityareaphenomenonofthestreetgraphandnottheunderly-ingtensorfield.Weuseroaddensitymaps(orpopulationdensitymaps)tocontroltheroadtracingalgorithmdescribedinsection6.Seefigure5rightforaresultfromourmodelingsystem.

Figure5:ThisfigureshowstransitionsinstreetdensityinDenver(left)andagenerateddensitytransitionontheright.

Irregularities:Thepreviouslydescribedtensorfieldsareallsmoothandwouldgiverisetoperfectlyregularstructures.Inrealstreetnetworkswecanobservevariousformsofirregularities.Wewillbrieflydescribehowtoclassifytheseirregularitiesandgiveastrategytoimplementthem.Inourmodelingframework,someoftheirregularitiesareimplementedasdistortionsofatensorfield,andotherirregularitiesarebetterimplementedonthegraphlevel:•DeletedStreetSegments:Therearemanyexampleswhereastreetstopsandlaterrestarts.Figure6leftshowsanexamplefromManhattaninNewYorkCity.Thedeletedstreetseg-mentsresultinmergedadjacentparcelsintheregulargridordeadendsifstreetsegmentsareonlydeletedpartially.The

Figure6:Left:Occasionallycellsaremergedtogether(1)orpar-tiallysplitbydeadends(2).Right:Slightirregularitiescanbeseeninaregulargrid(3).

Figure7:Left:ThismapshowsanexamplefromChicago,whereasinglestreetislayingoveranotherwiseregularnorth-southgridpattern.Right:Asimilarpatternwascreatedusingoursystem.

importantinsightisthattheseirregularitieshavetobemod-eledonthegraphlevel,byprocedurallyormanuallyselectingthestreetsegmentsthatshouldbedeleted.

•LayeredPatterns:Aseeminglyrandomstreetcutsacrossanotherwiseregularstreetnetwork.Thestreetcanhavearan-dombeginningandarandomend.Seefigure7foranexam-ple.•Noise:Moststreetpatternsoccurinaslightlydistortedfash-ion.Seefigure8forexamples.InourmodelingsystemweusePerlinNoise[Perlin1985]toeitherrotatethetensorfieldoralterthestreetsegmentsandnodesinthegraph.

Figure8:Thisfigureshowsaregularmajorroadgrid(left)andaradialmajorroadpattern(right)overslightlycurvedminorroads.CrackPatterns:Therearesomeinstanceswhereroadnetworkssharesomesimilaritieswithfracturepatterns.Oneexampleare

majorroadsinruralMissouri(seefigure9left).Inthiscaselocaltopographydominatestheroadlayout.Wehavesomepossibilitytomatchthesepatternswithatensorfieldandaddednoise.

Figure9:ThisfigureshowscrackpatternsinMissouri(left)andaprocedurallygeneratedpatternsusingoursystem(right).

5EditingTensorFieldsandStreetGraphs

Overview:Therearetwolevelsofeditingoperationsthatwepro-videtheuserwith.First,theusercanchangethestreetnetworkbymodifyingtheunderlyingtensorfield.Second,theusercandirectlychangethestreetnetworkbyadding,modifying,orremovingstreetsegments.However,suchchangescanbelostifanychangesaremadetotheunderlyingtensorfieldafterwards.Inthefollowingwewillfirstdescribetheeditingoperationsontensorfieldsfollowedbyeditingoperationsonthegraphstructure.Figure10illustratesseveralstepsinaneditingsession.

Figure10:Thisfigureshowsaworkflowthroughoursystem.Typ-icallyauserfirstcreatesalayoutofthemajorroadsandthenfillsinminorroadpatterns.

TensorFieldEditing:Tochangethetensorfield,weprovidethefollowingfunctionalities.

1.CombinationofBasisFields:Thesystemallowstheusertocreateandmodifyatensorfieldbyusingdesignelements.Adesignelementcorrespondstoauser-specifiedtensorfieldpatternsuchasconstantdirectionsorradialpatternsnearagivenlocation.Ourimplementationfollowscloselytheten-sordesignsystemofZhangetal.[2007],inwhicheveryuserspecificationisusedtocreateaglobalbasistensorfield.Thesebasisfieldsarethensummedusingradial-basisfunc-tionssuchthattheresultingtensorfieldsatisfiestheuserspec-ifications.Theusercanalsodeleteanexistingdesignelementormodifyitslocation,orientation,andisotropicandisotropicscales.Notethatthereareotherwaysofcreatingatensorfieldfromuserconstraints,suchasrelaxation[Turk2001;WeiandLevoy2001]andpropagation[Praunetal.2000].Wechoosetheideaofbasisfieldsduetoitssimplicityandintuitiveness.2.TensorFieldSmoothing:Theusercanreducethecomplex-ityinthetensorfieldbyperformcomponentwiseLaplacian

smoothing.Suchanoperationcanbeperformedeitherglob-allyorlocally.Inthelattercase,thetensorvaluesontheboundaryoflocalregionserveastheconstraintsinrelaxation.Smoothingtendstogreatlyreducethecomplexityintheten-sorfields.

3.TopologicalEditing:Theusercanexplicitlycontrolthenumberandlocationofthedegeneratepointsinthefield.Thisisachievedbyemployingthedegeneratepointpaircancella-tionandmovementoperations.Singularitypaircancellationallowsadegeneratepointpairtoberemovedsimultaneously,whiledegeneratepointmovementenablesadegeneratepointtobemovedtoamorefavorablelocation.Noticebothopera-tionsprovidetopologicalguaranteesthatnootherdegeneratepointsareaffected.4.BrushInterface:Wealsousetheideaofabrush-basedin-terface,inwhichtheuserproducetensorvaluesbymovingthemousetoformacurveoraloop.Thenaregionisfoundtohaveapre-defineddistancetothecurve.Finally,theten-sorvaluesinsidethisregionarecomputedbytreatingtheuser-specifiedcurveastheconstraint.Noticethisissimilartocreatingatensorfieldwithconstraintssuchascoastlinesandboundariesofapark.Thedifference,however,isthatthebrush-basedinterfaceallowstensorfieldtobecreatedlocallyinsteadofgloballyandsupportsdiscontinuitiesinthetensorfield.Moreimportantly,tensorfieldcanbecomediscontinu-ousalongtheboundaryoftheregion.Anexampleoperationisillustratedinfigure11

Figure11:Thisfigureshowstheapplicationofthebrushtooltoorientstreetsalongabrushstroke.

NoticethatthefirstthreefunctionalitiesfollowcloselyofthetensorfielddesignsystemofZhangetal.[2007].Ontheotherhand,thebrushinterfaceisnovel.Itiseasytouse,provideslocalcontrol,andallowsdiscontinuitiestobecreatedinthetensorfield.GraphEditing:

1.RoadSegmentsManipulation:Thesystemenablestheusertocreateandremovesegmentsinthegraphthatwasgeneratedfromthetensorfield.2.VertexManipulation:theusercanmoveverticesinthestreetgraph(userclicksonvertexandmovesusingdraganddrop)3.SeedPointCreation:theusercaninsertnewstreetsbypointsatspecifiedlocations4.MoveStreets:theusercanmovestreetastreetinthetensorfieldsothatitisretracedfromaclose-bylocation.Tohandlediscontinuitiesacrosstwoneighboringregions,weallowtwooptions.Inthefirstapproachwhichwerefertoasthesym-metriccase,thetworegionshaveequalpriority.Therefore,roads

fromthefirstregionwillbeclippedinsidethesecondregionminustheintersectionregion,andviceversa.Inthesecondcasewhichisasymmetric,theendpointsoftheroadsinsidetheregionofin-tersectionareusedasseedpointstogenerateroadinthesecondregion.

TodemonstratethecapabilitiesoftheeditingtoolweshowtwoeditsofasceneusingawatermapfromtheMissionBayinSanDiego(seefigure12andfigure13foranaddednodeinthetoprightcorner).

Figure12:ThisfigureshowsageneratedstreetgraphfortheMis-sionBayinSanDiego.

6

StreetGraphGenerationfromTensorFields

Ourstreamlinetracingalgorithmisanadaptationof[JobardandLefer1997],whichhasbeenusedinpen-and-inksketchingof3Dshapes[HertzmannandZorin2000]andquad-dominantremeshingofsurfaces[Alliezetal.2003;MarinovandKobbelt2004;Zhangetal.2007].

Givenasecond-ordersymmetrictensorfieldT(x,y),weproducetwofamilyofstreamlinescorrespondingtothemajoreigenvectorfieldE1(x,y)andtheminoreigenvectorfieldEstreamlines,westartfrom2(x,y),respectively.Totracethemajorasetofinitialseedpoints.Theseedpointscanbeeitherspecifiedbytheuserorgener-atedprocedurally,andtheyareplacedinapriorityqueue.Next,weenteraniterativeprocessinwhichastreamlineisgeneratedbasedonthetopelementinthequeue,whilenewseedsareaddedtothequeue.Totraceasinglestreamline,weuseanadaptedRunge-Kuttascheme[CashandKarp1990]thathasbeenmodifiedtohandletensorfields.Givenapositionofthecurrentendpoint,wefindthedirectioninwhichthestreamlinegrowsbyfindingthemajoreigenvectorvalueattheendpoint.Toremovethesignambiguityineigenvectordirections,weusethedirectioninwhichthecurrentpointhascomefrom.Thenextintegrationpointisthenfoundus-ingthenumericalscheme.Astreamlinestopsgrowingifithitstheboundaryofthedomain,runsintoadegeneratepoint,istoocloseto

Figure13:Thisfigureshowsthestreetgraphfromthepreviousfigurewithanaddedradialpattern.

anexistingstreamlinebyexceedingauser-defineddensitydwhichindicatesaloop,orexceedsauser-definedsep,re-turnstoitsoriginmaximumlength.Onceastreamlinehasbeentraced,additionalseedpointswillplacedalongitatadistanceofdusedtocontrolthedensityofthestreamlines.Next,sep.Noticediswetracethesepstreamlinesthatcorrespondtheminoreigenvectorfieldinasimilarfashion.

ThetwofamiliesofstreamlinescanbeusedtogenerateagraphG=(V,E).Thisisdonebyfindingtheintersectionpointsbetweenanypairofamajorstreamlineandaminorstreamline.Visthecol-lectionofintersectionpoints,andEisthesetofsegmentsbetweentwoconsecutiveintersectionpointsalongamajororminorstream-line.ThegraphGcanbeturnedintoapolygonalmeshbyidenti-fyingthepolygonsinthegraph.Thisishighlydesirablewhentheuserwishestoaddbuildingsorotherstructuresinbetweenroads.

7Three-dimensionalGeometryGeneration

Inthelastsectionswedescribedhowausercangenerateastreetnetwork.Thestreetnetworkisagraphthatconsistsofstreetsandintersections.Inthefollowingwedescribethestepsnecessarytogeneratethreedimensionalgeometryfromastreetnetwork.Weemployamethodthatallowsthespecificationtemplatesforstreetsegmentsandcrossingssimilarto[ThomasandDonikian2000].Theapproachworksasfollows:

•Astreetsegmentcanbespecifiedbyvariousattributesofthecrosssection.Thismethodistypicallyusedinurbandesignconceptswhereanurbanplannerwoulddrawcrosssectionstoconveyhisdesign(seefigure14).Westorecrosssectionsasalistoflanes.Eachlanehasattributesincludingwidth,textureinformation,andtype.Weimplementedsidewalks,vegetation,parkinglanes,lanesforcars,curbs,etc.•Anintersectioncanbespecifiedbyvariousattributesabout(1)trafficlights,(2)markingsonthefloorincludingpedes-triancrossings,yieldlines,stoplines,andarrows,(3)texture,

(4)andgeometricinformationaboutthesmoothnessofcor-ners,and(5)intersectiontype.OurcurrentimplementationallowsforX-,andT-intersectionsandroundabouts.Unfortu-nately,thegenerationofintersectiongeometryandtextureco-ordinatesinvolvesalargeamountoftediousgeometriccom-putations.Wereferthereadertothecivilengineeringliter-ature[AASHTO2004]foracomprehensivetreatmentofthetopic.

Selectedexamplemodelscanbeseeninfigure15.Thefigureshowsthreecrossingstogetherwithshortsectionsofstreetsegmentslead-inguptotocrossing.

Figure14:Thisfigureshowstwostreetcrosssections.

8Renderings

Wecombinedthestreetnetworkswithsimpleshapegrammarsforparcelsubdivisionandbuildingmassmodelgeneration.ThefinalimageswerecreatedusingRenderManwithambientocclusion.Seefigure16fortworenderingsoftheSanDiegosceneandoneren-deringofaradialcity.

9Discussion

Inthefollowingwediscussstrengthandlimitationsofourapproachandourcontributiontocomputergraphicsresearch.

Strengths:Theinherentstrengthsoftensorfieldsincludethepossi-bilitytomodelstreetpatterns,whichusuallycontaintwomostpre-ferreddirectionsthataremutuallyperpendicular.Furthermore,ten-sorfielddesignallowstheusertoquicklygenerateaninitialstreetlayoutwithwhichheorshecanmodifyateitherthetensorfieldlevelorthegraphlevel.Thisflexibilityisunmatchedbyeditingtoolsthatonlyoperateonthegraphlevel,especiallywhencreatingthetypicalstreetpatternssuchastheregularEast-WestandNorth-Southpatterns.

Limitations:Currently,oursystemonlyassumesasingle-levelspatialresolution,whichmakesitdifficulttomodifythetensorfieldatsignificantlydifferentscales.Weplantoenhanceoursystembyaddingthemulti-scaleeditingcapabilities.Anotherdirectionwewishtoexploreistheuseofasymmetrictensorstomodelstreetnetworkswhosetwopreferreddirectionsarenotalwaysorthogo-nal.

StreetModelingforComputerGraphics:Aninterestingques-tionistocompareourstreetmodelingtooltostreetmodelinginrealurbanenvironments.Thereareseveralimportantcharacter-isticsthatdistinguishacomputergraphicsapplicationandacivilengineeringapplication.Wearemainlyconcernedwithefficientlarge-scalemodeling.Large-scaleeditingisverydifficultinreality,becauseitisveryexpensivetoteardownexistinghouses.Inareasofrapidgrowth,suchasAtlantaorPhoenix,atoollikeourscouldbeusedinearlydesignstagestodesignroadsinlargerresidentialsubdivisions.Roadconstructionincivilengineeringissignificantlymoreconcernedwithlocaldetails.Examplesofimportantfactors

Figure15:Thisfigureshowsstreetintersections.

arenoiseregulations,theturningpathsoflargervehicles,owner-shipofland,legalregulations,andgeologicalcharacteristicsofthesoil.Civilengineeringsoftwarehassometoolsforintersectiongen-erationthatwouldbeinterestingforourdesignsystem.However,thegenerationofthree-dimensionalgeometricintersectiondetailsisaverycomplexsubjectthatwasbeyondthescopeofourresearchproject.

Application:Themainbenefactorsofthisresearchareapplica-tionsthatrequireefficientcontentcreation.Importantexamplesaretheentertainmentindustrywithastrongdemandtocreatecon-tentforcomputergamesandmovies.Inrecentyears,modelinghasevolvedtobethemostsignificantbottleneckinproduction.Asaso-lution,proceduralmethodscanbesuccessfultodrasticallyincreasemodelingtimes.However,ithasbeenourexperience,thatmostcompaniesarereluctanttoadoptproceduralmethods,iftheydonothavesignificantcontroltofine-tunetheoutcome.Therefore,theproposedmodelingframeworkisanattempttointegrateproceduralmethodswithhigh-andlow-leveluserinputtogivethemodelersthefreedomtheyseekindesigningtheirenvironments.

Figure16:ThisfigureshowstworenderingsoftheSanDiegosceneandanothercityusingaradialpattern.

GraphModeling:Thispapermakesanimportantcontributiontographmodelingproblemsingeneral.Eventhoughseveralgraphlayoutsappeartobefairlyrandom,closerinspectionwillrevealadistinctpatternoftwopreferreddirections.Webelievethatourmethodologytousertensorfieldstoguidethegenerationofgraphscanbeveryusefulforrelateddesignproblems,suchasthemodel-ingofcracks,fracturepatterns,leafvenationpatterns,bark,andicecrystals.Wewanttoexploresomeofthesepotentialconnectionsasourfuturework.

10Conclusion

Inthispaperwepresentedasolutiontointeractivelymodelstreetgraphs.Themainideasofthispaperareto(1)usetensorfieldmodelingtoguidethegenerationofagraphand(2)tointegrateproceduralmodelingwithinteractiveediting.Thesetwoconceptsshowedtobeveryusefultogeneratestreetnetworks,andweplantoextendthismodelingstrategytoothergraphicsmodelingproblems.

References

AASHTO.2004.APolicyonGeometricDesignofHighwaysandStreets,5thedition.AmericanAssociationofHighwayandTransportationOffi-cials.ALLIEZ,P.,COHEN-STEINER,D.,DEVILLERS,O.,L´E

VY,B.,ANDDES-BRUN,M.2003.Anisotropicpolygonalremeshing.ACMTransactionsonGraphics22,3,485–493.BERG,M.D.,KREVELD,M.V.,OVERMARS,M.,ANDSCHWARZKOPF,O.2000.ComputationalGeometry.Springer-Verlag.BOARD,T.R.2000.HighwayCapacityManual;U.S.CustomaryVersion.TransportationResearchBoard.CASH,J.R.,ANDKARP,A.H.1990.AvariableorderRunge-Kuttamethodforinitialvalueproblemswithrapidlyvaryingright-handsides.ACMTransactionsonMathematicalSoftware16,201–222.FEDERL,P.,ANDPRUSINKIEWICZ,P.2004.Finiteelementmodeloffractureformationongrowingsurfaces.InInternationalConferenceonComputationalScience,Springer,M.Bubak,G.D.vanAlbada,P.M.A.Sloot,andJ.Dongarra,Eds.,vol.3037ofLectureNotesinComputerScience,138–145.GLASS,K.R.,MORKEL,C.,ANDBANGAY,S.D.2006.Duplicatingroadpatternsinsouthafricaninformalsettlementsusingproceduraltech-niques.InAfrigaph’06:Proceedingsofthe4thinternationalconferenceonComputergraphics,virtualreality,visualisationandinteractioninAfrica,ACMPress,161–169.HAUSNER,A.2001.Simulatingdecorativemosaics.InSIGGRAPHPro-ceedings,573–580.HERTZMANN,A.,ANDZORIN,D.2000.Illustratingsmoothsur-faces.ComputerGraphicsProceedings,AnnualConferenceSeries(SIG-GRAPH2000)(Aug.),517–526.HIROTA,K.,TANOUE,Y.,ANDKANEKO,T.1998.Generationofcrackpatternswithaphysicalmodel.TheVisualComputer14,3,126–137.JOBARD,B.,ANDLEFER,W.1997.Creatingevenly-spacedstreamlinesofarbitrarydensity.Proc.EighthEurographicsWorkshoponVisualizationinScientificComputing,45–55.KIM,J.,ANDPELLACINI,F.2002.Jigsawimagemosaics.InSIG-GRAPH2002ConferenceProceedings,ACMPress/ACMSIGGRAPH,J.Hughes,Ed.,AnnualConferenceSeries,657–6.LEFEBVRE,S.,ANDNEYRET,F.2002.Synthesizingbark.InRenderingTechniques(EurographicsWorkshoponRendering-EGSR).LEGAKIS,J.,DORSEY,J.,ANDGORTLER,S.J.2001.Feature-basedcellulartexturingforarchitecturalmodels.InProceedingsofACMSIG-GRAPH2001,ACMPress,E.Fiume,Ed.,309–316.MANNERING,F.L.,KILARESKI,W.P.,ANDWASHBURN,S.S.2005.PrinciplesofHighwayEngineeringandTrafficAnalysis.JohnWiley&Sons.MARINOV,M.,ANDKOBBELT,L.2004.Directanisotropicquad-dominantremeshing.ComputerGraphicsandApplications,12thPacificConfer-enceon(PG’04),207–216.MˇE

CH,R.,ANDPRUSINKIEWICZ,P.1996.Visualmodelsofplantsinter-actingwiththeirenvironment.InProceedingsofACMSIGGRAPH96,ACMPress,H.Rushmeier,Ed.,397–410.MOULD,D.2005.Image-guidedfracture.InGI’05:Proceedingsofthe2005conferenceonGraphicsinterface,CanadianHuman-ComputerCommunicationsSociety,219–226.MULLER¨,P.,WONKA,P.,HAEGLER,S.,ULMER,A.,ANDVANGOOL,L.2006.ProceduralModelingofBuildings.InProceedingsofACMSIGGRAPH2006/ACMTransactionsonGraphics.NEFF,M.,ANDFIUME,E.1999.Avisualmodelforblastwavesandfracture.InGraphicsInterface,193–202.O’BRIEN,J.F.,ANDHODGINS,J.K.1999.Graphicalmodelingandanimationofbrittlefracture.InProceedingsofACMSIGGRAPH1999,ACMPress/Addison-WesleyPublishingCo.,137–146.

PARISH,Y.I.H.,ANDMULLER¨,P.2001.Proceduralmodelingofcities.

InProceedingsofACMSIGGRAPH2001,ACMPress,E.Fiume,Ed.,301–308.PERLIN,K.1985.Animagesynthesizer.InSIGGRAPH’85:Proceed-ingsofthe12thannualconferenceonComputergraphicsandinteractivetechniques,287–296.PRAUN,E.,FINKELSTEIN,A.,ANDHOPPE,H.2000.Lappedtex-tures.ComputerGraphicsProceedings,AnnualConferenceSeries(SIG-GRAPH2000)(Aug.),465–470.PRUSINKIEWICZ,P.,ANDLINDENMAYER,A.1991.TheAlgorithmicBeautyofPlants.SpringerVerlag.PRUSINKIEWICZ,P.,JAMES,M.,ANDMˇE

CH,R.1994.Synthetictopiary.InProceedingsofACMSIGGRAPH94,ACMPress,A.Glassner,Ed.,351–358.PRUSINKIEWICZ,P.,MUNDERMANN¨,P.,KARWOWSKI,R.,ANDLANE,

B.2001.Theuseofpositionalinformationinthemodelingofplants.InProceedingsofACMSIGGRAPH2001,ACMPress,E.Fiume,Ed.,2–300.PRUSINKIEWICZ,P.,FEDERL,P.,KARWOWSKI,R.,ANDMECH,R.2003.L-systemsandbeyond.ACMSIGGRAPH2003CourseNotes(Aug.).RUNIONS,A.,FUHRER,M.,LANE,B.,FEDERL,P.,ROLLAND-LAGAN,A.-G.,ANDPRUSINKIEWICZ,P.2005.Modelingandvisualizationofleafvenationpatterns.ACMTransactionsonGraphics24,3,702–711.SMITH,J.,WITKIN,A.,ANDBARAFF,D.2001.Fastandcontrollablesimulationoftheshatteringofbrittleobjects.ComputerGraphicsForum20,2,81–91.STINY,G.1977.Ice-ray:anoteonchineselatticedesigns.EnvironmentandPlanningB4,–98.SUN,J.,YU,X.,BACIU,G.,ANDGREEN,M.2002.Template-basedgenerationofroadnetworksforvirtualcitymodeling.InVRST’02:ProceedingsoftheACMsymposiumonVirtualrealitysoftwareandtech-nology,ACMPress,NewYork,NY,USA,33–40.THOMAS,G.,ANDDONIKIAN,S.2000.Modellingvirtualcitiesdedicatedtobehaviouralanimation.ComputerGraphicsForum(Proc.Eurograph-ics’00)19,3(Aug.),71–80.TURK,G.1991.Generatingtexturesonarbitrarysurfacesusingreaction-diffusion.InProceedingsofACMSIGGRAPH91,ACMPress,2–298.TURK,G.2001.Texturesynthesisonsurfaces.ComputerGraphicsPro-ceedings,AnnualConferenceSeries(SIGGRAPH2001),347–354.WEI,L.Y.,ANDLEVOY,M.2001.Texturesynthesisoverarbitrarymani-foldsurfaces.ComputerGraphicsProceedings,AnnualConferenceSe-ries(SIGGRAPH2001),355–360.WILSON,A.,ANDBRANNON,R.2005.Exploring2dtensorfieldsusingstressnets.IEEEVisualizationProceeding,11–18.WITKIN,A.,ANDKASS,M.1991.Reaction-diffusiontextures.InPro-ceedingsofACMSIGGRAPH91,ACMPress,299–308.WITTEN,T.A.,ANDSANDER,L.M.1981.Diffusion-limitedaggregation,akineticcriticalphenomenon.Phys.Rev.Lett.47,1400–1403.WONKA,P.,WIMMER,M.,SILLION,F.,ANDRIBARSKY,W.2003.In-stantarchitecture.ACMTransactionsonGraphics22,3,669–677.WORLEY,S.1996.Acellulartexturebasisfunction.InProceedingsofACMSIGGRAPH96,ACMPress,NewYork,NY,USA,291–294.WYVILL,B.,VANOVERVELD,K.,ANDCARPENDALE,S.2004.Creat-ingCracksforBatikRenderings.NPAR2004ProceedingsofthethirdinternationalsymposiumonNon-photorealisticanimationandrender-ing,61–70.ZHANG,E.,HAYS,J.,ANDTURK,G.2007.Interactivetensorfielddesignandvisualizationonsurfaces.IEEETransactionsonVisualizationandComputerGraphics13,1,94–107.