An informed environment dedicated to the simulation of virtual humans in urban context

Volume18(1999),Number3

AnInformedEnvironmentdedicatedtothesimulationof

virtualhumansinurbancontext

NathalieFarenc,RonanBoulicandDanielThalmann

Nathalie.Farenc,Ronan.Boulic,Daniel.Thalmann@epfl.ch

ComputerGraphicsLaboratorySwissFederalInstituteofTechnology

Lausanne,Switzerland

Abstract

Inthispaper,weoutlinethecreationofanInformedEnvironment,dedicatedtourbanlifesimulation.WeproposemethodsandtoolsforcreatingandprovidingtheinformationnecessaryforanimatingvirtualhumansinacityusinganInformedEnvironment.TheInformedEnvironmentisbasedonahierarchicaldecompositionofaurbansceneintoEnvironmentEntitiesprovidinggeometricalinformationaswellassemanticnotions,thusallowingamorerealisticsimulationofhumanbehaviour.Inthismanner,virtualhumanscanintegratewithacertainkindofurbanknowledge.

1.Introduction

Incombinationwiththerapidtechnicalimprovementsofcomputers,buildinglargevirtualsceneshasbecomeapopu-larfieldincomputergraphics.Ourspecificaimistopopulatethesesceneswithvirtualhumansinordertoofferassistanceindecisionmakingconcerningurbaninfrastructures.Inthisview,wehavetosolvetheproblemofplanninghumanac-tionsandbehavioursforurbanlifesimulation.

Thebehaviourofhumansorothermobileentitiesmustbecoherentwithrespecttotheirlocationinthecity.Pop-ulatingabig-scalevirtualscenesuchasatownisdifficult,duetotheneedoflargequantityofgeometricaldataorigi-natingfromthemodel(locationofobjects,agentsetc)andincludingadditionalinformationthatweshallcall“urbanknowledge”.Inordertoyieldmorerealisticsimulations,theenvironmentmustintegrateseveralsemanticnotionsaboutspecificareassuchas“asidewalkisaspacededicatedtopedestrianmotion”.OurInformedEnvironmentdedicatedtothesimulationofvirtualhumansprovidesalldatatoguidevirtualhumanswithcoherentbehaviours.Theurbanknowl-edgeattachedtotheInformedEnvironmenthasbeende-finedincorrelationwithhumanperceptionandanalysisinthecontextofurbanlife.Duetothecostofvirtualpercep-tion4,theInformedEnvironmentisagoodwayforsubsti-tutingcostlyperceptionsanalysisbyinformationobtained

cTheEurographicsAssociationandBlackwellPublishers1999.PublishedbyBlackwell󰀁

Publishers,108CowleyRoad,OxfordOX41JF,UKand350MainStreet,Malden,MA02148,USA.

throughdatabaseaccess.The“walkingonasidewalk”ac-tioninvolvestwosub-tasks:1.

Recognitionofplacescalled“sidewalks”,theirlocationinspaceandverificationofthecoher-enceofthewalkingactionassociatedwiththemobileentity.

Animationofthebodyinthevirtualsceneusingawalkingmodelaccordingtothepreviousdatagivenasparameter.

2.

Inthispaper,wefocusmainlyonamethodforcreatinganInformedEnvironment.Thisenvironmentprovidestheinfor-mationnecessaryfortherecognitionofplacesandtheloca-tionofvariousobjects.Humanmotiongenerationishandledatalowerlevelandisnotaddressedinthispaper6.Wepresentamethodforbuildingavirtualscenewithas-sociatedsemanticinformationaswellasfortheexploitationofsuchscenes.Severalstudieshaveaddressedthetopicofvirtualcityconstruction,suchasreconstructingarealcityusingimageprocessing,archaeologicaldata7,21,11,orus-ingtheurbancontexttodealwithtrafficproblems11,9,17,urbandisplacement10,11,1orcitymodelling14,11.Themaindifferencebetweenourapproachandpreviousstudiescon-cernsthesimulationofacitywithrealisticvirtualhumans.Bycomparisonwithsimulationsusingiconsthatrepresenthumans,simulationswithrealistichumansallowabetterap-

Farencetal./AnInformedEnvironment

proachforevaluatingrealconstraintsinalifelikecitysim-ulation.However,theanimationofrealisticvirtualhumanshasthedrawbackofaddingconstraintsaswellasdatare-quirements.Thus,weaimatobtainingaurbanmodelwithintegratedknowledgeadaptedtohumanbehavioursimula-tion.Asin11,ourworkisbasedonenvironmentdecompo-sitionwithlinkstotraditionaltwo-dimensionalGeographicInformationSystems(GIS)anddatabases.Inordertostruc-turethevirtualcitydata,wedefineahierarchicalmodelvalidfordifferentkindsofsimulationofhumanlife.Thismodelislinkedtomethodsofsceneconstructionandusage.Thepaperisorganisedasfollows:inSection2westartdefiningourentities.Section3describesdataextractionfromtheoriginalthree-dimensionalmodel.Section4con-cernstheusageofthedatabaseconstructedfromtheenti-ties.Finally,Section5showssomeresultsandendswithaconclusion.

2.EnvironmentalEntities2.1.Definitions

Atafirststage,ananalysispermitstheidentificationofma-jorcompulsionsforurbanlifesimulation.Theseconstraintsconcerntheinformationthatistransferedtoautonomousagentsasawaytolinkthescenecreationtoitsuseduringsimulation.Concretely,inordertohandleagentsandactionsassociatedwithaplace,themanagingagentneedsallthege-ometricalinformationassociatedwiththisplace.Thisinfor-mationincludesthewhereaboutsoftheagent,thelistofob-jectspresentinthisareaandthelistofbehavioursoractionsassociatedwiththisplaceforacertainkindofmobileenti-ties.Knowledgeaboutobjectsisusedfordealingwithcolli-sionavoidanceorforinteractingwiththem.Wehavedefinedmobileentitesasobjectswithmobilitysuchaspedestrians,wheelchairs,cars,buses,bicycles.Thesemobileentitiesusecertainsurfaces(theEnvironmentEntitiesorENV)fordis-placement.AnENVrepresentsasurfaceorvolumeandhasassociatedsemanticinformation.AsingleENVcanbecom-posedofdifferentkindsofobjectssuchasobjectsassociatedwithobstacles(treesorwallsforexample)andsmartobjectsusedforspecificinteractions(doorsorescalators).Variousmethodscanbeappliedforcarryingoutasim-ulationofaninhabitedcity.Asetofelementaryrulescanbeused,withrespecttovariouslocationcharacteristics,todefinehumanbehavioursduringinteractionswithobjectsorwithotherhumans.Thismethodhasthedrawbackofhandlingeverythingandtherulesmustcoverallthesetop-ics.Thus,efficientrulesforaurbancontextaretoonu-merousandcomplex.Analternatemethodistodistributeinformationor“knowledge”tospecificapplications12.Inthisapproach,oneapplicationdealswithinternalcrowdmanagement18,anotheroneisdedicatedtoobjectinterac-tions(handposition,movementofthebodyandtheobjects)usingsmartobjects15,arule-based-behaviourgiveshigh-levelorderstohumans22andalastapplicationdealswithall

datacomingfromtheenvironment.ThislatterapplicationexploitsourInformedEnvironment.

Onthebasisofthisconcept,toacomplexenvironment,wewanttoaddinformationrepresentingurbanknowledge.Acomplexenvironmentischaracterisedasaplacewhereinformation(semanticandgeometric)isdense,andcanbestructuredandorganisedusingrules.Thenotionofurbanknowledgeenclosesurbanstructuralinformationandobjectsusableaccordingtoasetofconventions.Itpresentsalsosomeassociationsbetweenplaces(geometricalarea)andse-manticinformation.Thegeometricalinformationoriginatesdirectlyfromthethree-dimensionalmodel:ourscene.Onepossibilityfordealingwiththiskindofproblematicistocreatethesceneandduringthisprocesstoassociateinfor-mationviaaninterfacebetweenthedesignerandadatabaseconstructor.Themainideaistoaddasemanticlayerontoacorecorrespondingtoaclassicalscene(ensembleofgraph-icalobjects)modelledusinggraphicalsoftware(Figure1).Thesemanticlayerassociatesobjectswithpropertiesusableduringsimulationofurbanlife.

3D sceneSemantic LayerFigure1:Modellingscheme

2.2.HierarchicalDecomposition

Ascenecorrespondingtothismodelincludesbothgraphi-calobjectsforvisualisationpurposeandobjectsprovidingtheirownvisualrepresentationandsemanticinformation.Wehavealsodefinedobjectsthatarecreatedonlyforcarry-ingsemanticinformationandthataresubsequentlydeletedfromthefinalvisualisationscene.OurmodelofInformedEnvironmentscenecorrespondstoasetofEnvironmentalEntities.Inordertoperformhumanmotiongeneration,thesurfacesthatweusemustbeofhumanscale,thisimplyingafinedecompositionofthescene.Inthisfashion,withahugecomplexenvironmentsuchasacity,wehavetoconsidertheproblemofdealingwithalargequantitiesofdataduringac-cessormanipulation.Ourapproachistodefinesomestruc-turedareas.Theareasareeithersubdividedintosub-areas,orgrouped,dependingonthelevelofinformation.Thus,byanalogytoageographicalmap,wedecomposealargeareaintosub-areaswithinformationinherenttothelevelofde-scription.Atthecitylevel,withthedatabase,wecanasso-ciateinformationcorrespondingtothemainaxesofthetownforenteringorexiting.Thesemainaxesallowcrossingthe

󰀁

cTheEurographicsAssociationandBlackwellPublishers1999.Farencetal./AnInformedEnvironment

city.Atalowerlevel,theseaxeswillberecognisedasstreets.Inthedatabase,thestreetlevelprovidesinformationaboutcrosswalksandsidewalks.Asweusethenotionofencapsu-lation,thesamesurfacecanbelongfirsttoasidewalk,thentoastreet,thentoablockandatthehighestlevel,tothecity.Thisclassificationcorrespondstoahierarchy,sortingandtidyingupallthedata.Thecityisdividedintoseveralareas,dependingontheirgeographicalandfunctionalproperties.Figure2showsagraphrepresentativeofthisstructure.Ourmodelcandecomposeacityintwenty-ninedifferentEnvi-ronmentalEntities.Inthehierarchicaldecompositiontree,thereareENV’scorrespondingtothesameENVtypebutwithdifferentascendantENVsuchas,forexample,thecir-culationareatype.Thistypeispresentedintheparcelsorinthebuildingoratafloorlevel.Theyaredistinctduetotheirlocalisationandduetothefactthattheirfunctionalitiescanbedifferent.TheseENVcaneitherbedecomposedintoasetofotherentities(theyareascendantENV)ornot,inwhichcasetheyrepresentleavesinthehierarchytree.

2.3.ObjectNamingandRe-naming

Asthenamesoftheobjectsallowtoassociateatypeandalocationinthetreedecompositionwiththeobjectsthenominationoftheobjectsispreponderant.Thedesignersofasceneandthedatabasecreatorhaveincommontheur-banscenedecompositionwhichdefinesthenamesandtypestotheobjectsinanurbanmodel.Thisdecompositionhasbeenproprosedincollaborationwithadesigner2inordertocreateasyntaxandconstraintsusablebybothsceneanddatabasedesigners.Thiskindofinterfacebetweendesigneranduseralsoprovidesfacilitiesforscenecreation.Inordertomakecorrectandeasyuseofthesyntax,theobjectsarenotfullynamedduetothesizeofthenameatalowlevelinthetree.Thedesigneronlydesignatesscenepartsbyab-breviations.Thesolutionwehaveadoptedistouselabelsabovegroupsofobjectstore-namealltheentitiesbeforedatabaseconstruction.Figure3representsnamesgivenbythedesignerandthere-namingusinglabelsorfilenames.Anexampleisthecaseofasidewalk.Thedesignergivesthe

Figure3:Hierarchywithfullynamedobjectsobjectthename“TRxx”,thisobjectisunderagrouplabeled“RUE_VH01_INT”.Thisentityrepresentstheentirestreet,andbyusingpartofthename,weareabletofullynamethesidewalk“RUE_VH01_TRxx”.Thelinkbetweensidewalkandstreetisestablishedatthisstagebythenewnameoftheobject.Alltheobjectsarenamedbythedesignerbasedontheobjectnamingpreviouslydefined.Applyingtherulesof

Figure2:AnInformedEnvironment

cTheEurographicsAssociationandBlackwellPublishers1999.󰀁

Farencetal./AnInformedEnvironment

re-namingofENV,theentiresceneisreadandallENV’sarefullynamed.

2.4.AGenericModel

Thismodelofhierarchicaldecompositionisdefinedina

genericwayatthedatabasecreationstage.Wechoosethisdecompositioninviewofthesimulationwehadinmind,withautonomoushumansinavirtualcity.Forothertypesofsimulation,othersemanticsmaybemoreappropriate,andascriptdescribesthedecompositionmodelinafiledefin-ingasetofprototypes,theENVprototypes.Thus,itiseasytodefineanewdecompositionhierarchyfortheENV.Allthelinksbetweenentitiesaredescribed.Forthemoment,weworkonlyattheblocklevelandonlytheENV’sundertheblockareusedandknowntothesystem.AswedonotuseanycommercialGISsystemwealsodefinehowtostoretheENV,thefilenames,thetypeoftheascendantENV,thenamesofthesub-ENVandtheENVtype.ThisENVdefini-tion(anENVprototype)yields,inthecaseoftheparcel:

parcelnameoftheentitytype:1typeoftheentitynb_under:3numberofentityunderparzcilistofthesub_entitynamesnotraffic_zonebuilding

type_eng_up:0

typeoftheupen-tity,inthiscasetheblocklabel:INTnamefoundinthescenefortheparcelname:PAR_#2#_INTnameafterre-namingrename_from:0typeofinformationusedtore-nametheENV,inthiscasethenamefilePAR_#2#.wrlformatofthefilenamenamefile:1numberoffilewherewecanfindthisENVPAR_#2#.wrlnameofthepreviousfilesstore_file_name:DEF_FILE_PARnameofthefiletostoretheENVtype_mobile:5mobileen-tityabletousethisENV(pedestri-ansinthiscase)Figure4:Manipulationofthescene

3.ExtractionofENVandDatabaseCreation3.1.Generalities

Thethree-dimensionalsceneprovidedbythedesignerisdi-videdintotwoparts,oneforvisualisationandanotherfordatabaseconstruction(Fig4).Thesceneisparsedandalltheobjectnames(thefullnames)areanalysedusingtheENVprototypepreviouslydefined.Withthisprototype,foralltheENV,weknowtheirtypeandlocationinthehierarchytree.Then,theENVareextractedfromthescenewiththeirgeo-metricalcharacteristics(surface,volume,locationinspacewithmatrix,boundingbox)andassociatedsemantic.TheENVarerecognisedandthenewinformationisstoredinthedatabase.AnENVisrepresentedinthedatabasebyitsgeometry,locationinthescene(positionmatrix),andlinkstootherENV(linkofdecomposition(ascendantanddescen-dant)orconnexitywithotherENVhavingthesameascen-dantENV).DependingonthetypeoftheENV,theENVgeometricalrepresentationcanbedeletedfromthesceneinordertocreateavisualscene.InordertocreatesomegraphrepresentingtheconnectionbetweenENV’s,weneedpointstopasstoanENVtoanotherone.Then,inasecondstage,foreachENVusablebymobileentities,someentry/exitpointscomputationisperformeddependingontheENVtype.WecreateinthedatabasealistofpointslinkedtotheENV.Foreachpoint,weaddtheinformationconcerningthemobileentitytypethatisabletousethem(busorpedestrianforex-ample).Inthecaseofthesidewalk,twopointsarecreatedatthesidewalksextremities,theassociatedENVprototypebeingthesidewalk,andonlythepedestrianmobiletypeisthemobiletypeallowedtousethem.Anotherkindofinfor-mationconcernstheconnexitylinksbetweentheENV.WehavechosentocomputeandstorefortheENVonlyconnex-itylinkshavingthesameascendantENV,inordertomin-imisethenumberofstoredconnexitylinks.Inthesidewalkexample,itsascendantisastreet,andtherollingwayandcrosswalkareconnexentitieshavingthesameascendant.Onlytheselinksarestoredinthedatabase.Moreconnex-itycomputationwithotherstreetsandparcelsiscarriedoutduringthesimulation.3.2.ASegmentedScene

Databasecreationreliesonasegmentedscene.Allregionsonthegroundthatprovidespecificinformationintermsoffunctionalityaremodelledasseparateobjects.Toillustratethisidea,Figure5showsaselectedsidewalk.Onlyitsownrepresentationisdisplayedprominently.Figure6illustratestheInventorhierarchy19correspondingtothescenesegmen-tation,theselectedobjectandthedifferentlabelsusedtoprovideinformation.

Thissegmentationofthesceneisforthemomentcar-riedoutatthedesignlevel.Itcouldbedoneinanotherwaythroughauserinterface,withavirtualscenemodelledwith-outobjectsegmentationorbyobjectrecognitionfromareal

󰀁

cTheEurographicsAssociationandBlackwellPublishers1999.Farencetal./AnInformedEnvironment

image.Oncewehaveawellsegmentedscene,theassoci-atedInformedEnvironmentiscreatedonthesamemodelofdecomposition.

Selected Sidewalk

Figure5:Viewofthecitywithasidewalkselected

Bloc level : root of the sceneFile for the street

Label to rename the street

label : \"I_TRC_H02a\"Other objects

composing the street

Sidewalk representation

transformations and textures for the cube

cube representation

Figure6:Viewofthehierarchyforaselectedsidewalk

3.3.ExtractionofSpecificData:LuresandSmart

ObjectsUsingthesamenotionofobjectsnamingtoextractdatafromthescene,specialobjectsarecreatedonlytoprovideinfor-mationtothedatabase.Calledlures,theseobjectsarenotdisplayed,theirgeometricalrepresentationisonlyforcarry-inginformationforhumanbehaviors.Wehavedefinedtwocategoriesoflures,someoftheseobjectsrepresentaddi-tionalinformationusedforcollisiondetectioninthecaseofcomplexobjectsandothersareusedforactionknowledge.3.3.1.Luresascomplexboundingbox

Wedetecttheobjectsattachedtoacirculationareaduringdatabasecreation.Weautomaticallycomputetheirbound-ingboxtofacilitatecollisiondetectionduringsimulation.Iftheobjectshavespecificshapes,suchasaU-shape,itmaybeusefultogiveaccesstotheinsideofthisU-shape.In

󰀁

cTheEurographicsAssociationandBlackwellPublishers1999.thiscase,duringscenebuilding,wecreatesomeluresas-sociatedwiththevisualobject,inordertoyieldboundingboxesadaptedtosimulation.Figure7andFigure8showanexampleofagroupofseatsinastation.Theseseatsmustbedefinedinordertoavoidanagentcollidingwiththemduringsimulation.Asaglobalboundingboxkeepsvirtualhumansfromusingtheareainsidethegroupofseats,wedefinedsomeluressoastostillprovideinformationforcol-lisionavoidance,butalsoinordertominimisetheboundingboxsize.Thesesluresarenotinthevisualisationfile.3.3.2.LuresasareawithattachedactionknowledgeOtherkindsoflurescontributetoactionknowledgesuchasclimbingstairs,forexample(withparametersforstairssuchassizeofthestep,depthandheight,number).Thisinforma-tioncanbeanalysedbeforeaclimbingmotionusingtheseparameters,orcanindicateakeyframefilestoredinthestairsplacetoperformthebodymotionduringsimulation3.Inthiscase,thelureisasurfaceatthetopandbottomofthestairs.Duringdatabasecreation,thisobjectisalsodeletedfromthevisualscene.Otherobjects,namedsmart

Figure7:Objectanditsboundingbox

objects,marketoutbytheirspecificlabels,arealsoex-tractedfromthescene.Theirgraphicalrepresentationscre-atesomearchivesasstartingpointsforsomehumaninter-actionspecification15.Theseobjectsarereferencedinthe

databasewiththeirlocationandlinkswithENV.4.UtilisationoftheENVDatabase

4.1.LocalisationofObjects,AreasandMobileEntitiesThedatabasecontainsgeometricalandsemanticinforma-tionformobileentitiessimulation.AnareadefinedasanIn-

Farencetal./AnInformedEnvironment

Figure8:Objectanditslures

formedEnvironmentprovidessub-areas(ENV),alongwith

thelistofobjectstoavoid.Inordertominimisethenumberofobjects,peripheralobjectssuchaswallsarenotincludedintheENVsurfacedescription.ThedatabasecansimulateperceptionssuchasbeingawareofalltheobjectsinsideanENV.Anotheruse,istoreducethevirtualperceptioncostbygivingdatasuchasallthesurfacesadjoininganENVinordertomoreefficientlyperformvirtualperceptionintheseareasandnotinallthescene.Thedecompositionhierarchymakesnodistinctionbetweenaparkandacemetery.Bothareparcelsinthecity.Inordertospecifysuchknowledge,weaddalabelabovetheENVdefinition,thusallowingspec-ificationofaplace.Thisadditionalcharacteristicpermitsdeclarationssuchas“gotothepark”,orspecificbehaviouroractiondefinitionssuchas“inaparkcommonactionsareplaying,readingetc”.

4.2.PathCreationbythemeansofanInformed

EnvironmentAnotherwaytousethedatabaseistocreatepathsbythemeansofourInformedEnvironment.Dependingonthetypeofmobileentity(pedestrianorbusforexample),theIn-formedEnvironmentdeterminesapathusingtheEntry/ExitpointsandthetypeoftheENVcurrentlyinuse.Apedes-triancannotusearollingwayforwalking.Atastreetlevel,apathforthiskindofmobileentitycanonlypassthroughsidewalks,crosswalkandcirculationareas.ThefirststageistousethedatabasetodefinealltheENVandassociatedpointsusablebytheconsideredkindofmobileentity.Conse-quently,foreachENV,accordingtothetypeofmobileentity,thedatabasereturnsalltheconnexleavesthatarereachablebythemobileentities.Wethusobtainafirstgraphwithoutweights.Inordertofindtheshortestpathinthegraph,wehaveintroducedamodifiedversionoftheDijkstraalgorithm13,20addingedgedependencies.Wehavedefinedsomecrite-riaandconstraintsinordertochoosethisalgorithm:wewanttofindthebestpath(shortest,fastest),wecandealwithsev-eralarcsbetweentwoENV(thedistanceinsideanENVde-pendingontheentryandexitpointsandthiscreatesanotionofdependencybetweenarcs).ThenodesaretheENVandtheedgescorrespondtothepointsallowingpassagefromoneENVtoanother.Theedgesareassociatedwithweightscorrespondingtothedistance,forexample,betweentheen-tryandexitpointsoftheENVcurrentlyinuse.Figure9showsanexampleoftwopathsfromAtoBpassingthroughdifferentENV.ThepathPath2istheshortestpath,butifwelookatthesub-pathgoingtotheENV4,theshortestpathisapartofPath3.TheweightdependsontheentryandexitpointsintheENV4.Thus,wehaveasystemwithdependen-ciesonedges.

WehaveaspecificgraphforeachkindofmobileentitiesandsomeENVallowaconnectionbetweengraphs.Forex-ample,saywehavetwographs,oneforpedestriansandoneforbuses:thesegraphswerebothcreatedinthesamewayaspreviouslydefined.Inordertosetapathforavirtualhumaninapark,usingtheshortesttimeoption,pathcreationtoolindicatestakingthebusinordertoquicklyleavetheparkandreachthesupermarket.Busstopsarethelinksbetweengraphsforpedestriansandbuses.Aninterfacehasbeencre-atedforselectingpointsinthecitysceneinordertodefinestartingandendingpointsforpath.Itisalsopossible,forexample,toaddconstraintsforguidingthepaththroughthepark.Thesepathsareusedaspre-computedpath.

Theenvironmentpathsareprovidedtoapplicationman-aginghumansasthecrowdmodule18.Thepathisalistofsurfacesjoinedbypoints.Theclientusingtheenvironmentpathscreatesitsownpathinthisareainawaytoavoidob-staclesassociatedtotheplaceandtoavoidotherhumans.4.3.PathOptimisation

WecomputethepathsusingtheENVpointssituatedinthemiddleoftheENVsides.Thepathspresentsomejaggedforms,andinordertoavoidsuchincoherence,wehaveim-provedpathcomputationbyaddingoptimisation.Inordertosmoothenthepath,thisoptimisationanalysesthepathandforeachpointinthepath,computesanewpointlocationontheedgeslinkingthetwoconnexENV.WeleaveaminimaldistancefromtheENVborder.Figure10showsanexampleofpathcomputationforapedestrianinthepark,andFig-ure11presentsthesamepathusingoptimisation.

Byusingthehierarchicaldecomposition,wehavesimpli-fiedtheproblemofthepathplanning.However,figure10illustratestheincoherenceofsuchsimplification,duetotheuseofentry/exitpoints.Theoptimisationfindthebestpathcorrespondingtotheinitialpathchoicebutthedistanceasso-ciatedisfalse(distanceusingtheentry/exitpoints).AbettersolutionshouldbeapplyingthealgorithmofLozanoPerez16,howeverduetotheneedofrapidityforpathcomputation,

󰀁

cTheEurographicsAssociationandBlackwellPublishers1999.Farencetal./AnInformedEnvironment

2D3BD6D7415D1D5AD23D4start & end points for the pathPath 2 : passing through the crosswalk 2in/out point for pedestrian mobil typePath 3 : passing through the crosswalk 3

DiWeights for the edges of the graph

iEnvironmental Entity

Figure9:Paththroughastreetshowingedgesdependencies

wecannotapplyittoalargescenesuchasacity.Inordertousethehierarchicaldecomposition,thatcanbeassociatedtoapre-processingstage,asolutioncouldbetoapplythealgorithmofLozanoPerezlocally(intheparcelENVoftheparkforexample).

Figure10:Pathcomputationwithnooptimisation

4.4.ActionPlanning

Anexampleofactionplanningduringsimulationisthestairsexample.Anagentneedstofollowapathtogofromoneplacetoanother,andduringhisdisplacement,hehastoclimbstairs.Theenvironmentprovidestheagentwithone

󰀁

cTheEurographicsAssociationandBlackwellPublishers1999.Figure11:Pathcomputationforpedestriansintheparkus-ingoptimisation

keyframefileforperformingthemovementtoclimbthestairs.Thekeyframefilewaspre-processedbeforesimu-lation.ThedatabaseprovidesalinkbetweentheENVandthekeyframefile.Duringsimulation,theENVinformstheagentsofwhichkeyframefiletoplayfortheascension.5.SomeResults5.1.Implementation

Forthetimebeingthesceneiscreatedusing3DSMax,andconvertedtotheInventorformat.Wehaveproducedtwodatabases:oneforacity,andoneforatrainstation.Fig-ure12representespicturestakenfromsimulationsinthecityandinthestationusingthecrowdsystem18,22.5.1.1.TheCity

Thecitywascreatedusingthedecompositionrulesandob-jectsnamingdefinedjointlybythedesigner2anddatabasemanager.Forthisscenewehavedefinedadatabase.Con-taining256ENV’sand348in/outpoints,itincludessev-eralstreetsandjunctions,apark,asupermarketandahouse.Inthiscontextwedefinedpathsforpedestriansandbuses.Humancrowdswalkthroughthecityaccordingtopre-calculatedpaths(autonomouscrowd)andusingonlyareasauthorisedforpedestrians18.Anothersimulationconcernsthebus.Thelattersendsamessagetoallagentswaitingatthebusstopwhereitisstanding.Usingthereactingsystemofthecrowd18,thevirtualhumansareabletotakethebus:theyreactwhenthebusarrivesatthebusstop.Thebusin-quiresaboutthestationwherethehumanwantstostepout,andwhenthislocationisreached,itsendsamessagetothehumanstellingthemtogetoffthebus.Thehumanskeeponreachingpointsontheirpaths,andthebuscontinuesonits

Farencetal./AnInformedEnvironment

way.Thepathsforhumanstakingthebuswerecalculatedusingthepathcreationtool,withthecriteriaoffastestpathinthecity.

5.1.2.TheTrainStation

Anotherscene,thetrainstation,wascreatedusingthesamerules2,thedatabasecontaining42ENV’sand142points.Thetwofloorsinthestationaretheparticularityofthisscene,oneatzeroaltitude,andanotheroneunderground(minusfivemeters).Thehumanscangotoonefloorusingsmartobjectslikeescalators15.Inthiscase,pathcomputa-tionmustusecommonsurfacesbetweentheENVandthesmartobjectscomposition.Thelocationofpointsinspaceisreallycarriedoutin3D,asitisnotpossibletoprojectpointsontotheground,wedealthenwithrealinclinedplane.5.2.Integration

Wehaveintegratedthisworkintodifferentapplications.Themajoroneisacrowdmoduleinthecity,severalpathsarepre-computedandthecrowdusesthepathsdefinedbysur-faces,entry/exitpoints,tosimulateaninhabitedtown12,18.Allthesepathsareloadedbeforethesimulationandthecrowdsimulatordistributethisinformationtothedifferentgroups.

Anotherintegrationismadeduringsimulations,asde-finedin22.TheInformedEnvironmentisaclient,otherclientsarethecrowdmodule(withaguidedcrowd),arulebasedbehaviourtoolandasmartobjectapplication.Aserverdistributesthedifferentmessagesitreceivestotheclientabletoprovideinformationortheserviceassociatedtothemes-sage.FromthepointofviewoftheInformedEnvironmentclient,duringthesimulation,theservercansenditsrequestsconcerningthelocationofdifferentplaces,thelocationofobjectsorthelocationofanagentprovidingthe(x,y,z)pa-rameters.Basedonthiskindofsimplerequests,theEnvi-ronmentdatabaseandthepathplanningtoolprovidessomepaths.ThenpedestriansareguidedbyothermodulesusingtheInformedEnvironmenttodealwiththesemanticenviron-ment.Wehavemadesomesimulationsofaninhabitedsta-tion.Inthiscase,wehavesome“autonomous”pedestrianshavinginitialscriptincludingsomepathandobjectsdefini-tions.Thesemobilesmovewithoutinteractionofothermod-ulesduringthesimulation(onlywithsmartobjectsiftheseinteractionshavebeendefinedintheinitialscript)18.Otherpedestriansarenamed“guidedcrowd”andtheyfollowor-derprovidedbythedifferentclients.Thedatabaseisusedtoextractinformationforpath,objectorhelpforperception.6.ConclusionandFutureWork

Inthispaper,wehavepresentedanInformedEnvironmentthatcreatesadatabasededicatedtourbanlifesimulation.Usingasetofmanipulationtools,thedatabasepermitstheintegrationofwhatwecall“urbanknowledge”inorderto

simulatemorerealisticbehaviours.Moreover,forvarioustypesofmobileentities,wecancomputepathstomovethroughthecityaccordingtoarearules.Byusingdataorig-inatingfromtheenvironment,virtualhumansareabletoac-quireurbanbehaviour.Futureworkwillconcerninclusioninthedatabaseofmorecomplexbehaviourrulesaswellasac-tionstoperforminspecificplaces.Wealsoaimatinforming,viaanintelligentinterface,anywellsegmentedscenesafterthecreationstage.Theimprovementofpathcomputationsisplannedwithdifferentcriterionallowingchoicesbeetwendifferentpossibilitiesofpath.Acknowledgements

ThisresearchwassponsoredbytheSwissNationalResearchFoundation.TheauthorswouldliketothankOlivierAunefordesigningthescenesandhiscollaboration.WewouldalsoliketothankJoaquimEsmerado,LornaHerdaandIkSooLimfortheirproofreadings,SoraiaRauppMusseforherhelpfulcomments,suggestionsandcollaboration,ChristopheBordeuxandRalphPlaenkersfortheirhelpinusingLatex.References1.

M.A.AufaurePortier,P.Berthet,J.L.Moreno(1994),\"OptimizedNetworkModellingforRoutePlan-ning\Procedingofthver1.dvie4thEur.Conf.onGIS,EGIS94Paris1994p.1817-1824.

2.

O.Aune,\"Definitiond’unenvironnementsemantiquevirtuelpourdesacteursautonomes\InternalReportLIGEPFL,December1998,32pages.

3.

S.Bandi,D.Thalmann,SpaceDiscretizationforEffi-cientHumanNavigation,Proc.Eurographics’98,Com-puterGraphicsForum,Vol.17,No3,1998,pp.195-206.4.

C.Bordeux,R.Boulic,D.Thalmann,\"AnefficientandFlexiblePerceptionPipelineforAutonomousAgents\Eurographics’99.

5.

R.Boulic,D.Thalmann,N.Magnenat-Thalmann,\"Aglobalhumanwalkingmodelwithrealtimekinematicpersonification\TheVisualComputer,6(6),December1990.

6.

R.Boulic,P.Becheiraz,L.Emering,andD.Thalmann,\"IntegrationofMotionControlTechniquesforVirtualHumanandAvatarReal-TimeAnimation\Proc.VRST’97,ACMPress,1997,pp.111-118.

7.

S.Donikian(1997)VUEMS:\"AvirtualUrbanEnvi-ronmentModelingSystem\";inComputerAnimation97fromp.127-p.133.

8.

P.Doyle,B.Hayes_Roth(1997),\"AgentsinAnnotatedWorlds\";ReportNoKSL97_09KnowledgeSystemsLaboratoryStanfordUniversityCalifornia94305.

󰀁

cTheEurographicsAssociationandBlackwellPublishers1999.Farencetal./AnInformedEnvironment

9.

K.RHoward(1997),\"UnjammingTrafficwithCom-puters\";ScientificAmericanOctober1997.

10.R.Ingram,S.Benford,J.Bowers(1996),\"BuildingVir-tualCities:applyingurbanplanningprinciplestothedesignofvirtualenvironments\VRST96p.83-95.11.W.Jepson,R.Liggett,S.Friedman(1996),\"Virtual

ModelingofUrbanEnvironments\Vol.5Winter1996p.83-95.12.N.Farenc,S.R.Musse,E.Schweiss,M.Kallmann,O.

Aune,R.Boulic,andD.Thalmann,\"OneStepTowardsVirtualHumanManagementforUrbanEnvironmentsSimulation\ECAI’98-WorkshopofIntelligentVirtualEnvironments,1998.13.G.Francon,,\"Creationetanalysedegraphespourune

villevirtuelle\InternalReportLIGEPFL,Juin1998,34pages.14.T.Fuji,K.Imamura,T.Yasuda,S.Yokoi,J.Toriwaki

(1995),\"AVirtualSceneSystemforCityPlanning\ComputerGraphics:DevelopmentinVirtualEnviron-ments1995p.485-496.15.M.KallmannandD.Thalmann,\"ModelingObjects

forInteractionTasks\EGCAS’98-9thEurographicsWorkshoponAnimationandSimulation,1998,Lisboa,Portugal.16.Lozano-Perez,\"AnalgorithmforPathPlanning

Collision-FreePathsAmongPolyhedralObstacles\CommunicationoftheACM,Vol.22,Number10,p.560-570,1979.17.P.LMokhtarian(1997),\"NowThatTravelCanBeVir-tual,WillCongestionVirtuallyDisappear?\",Comput-ersScientificAmericanOctober1997.18.S.R.Musse,C.Babski,T.CapinandD.Thalmann,

\"CrowdModellinginCollaborativeVirtualEnviron-ments\".VRST’98November,1998.Taiwan.19.OpenInventorC++,ReferenceManual,“Theofficial

ReferenceDocumentforOpenInventor,release2”,Ad-disonWesley1994,ISBN0_201_62491_5.20.C.Prins,\"Algorithmesdegraphes\EditionEyrolls,

1994.21.T.A.Russ,R.M.MacGregor,B.Salemi(1996),

\"VEIL:CombiningSemanticknowledgewithImageUnderstanding\ARPAImageUnderstangingWork-shop199622.E.Schweiss,S.R.Musse,F.Garat,\"AnArchitecture

toguideCrowdsbasedonrule-basedsystems\Au-tonomousAgents’99,1999(toappear).

cTheEurographicsAssociationandBlackwellPublishers1999.󰀁