RING:AClient-ServerSystem
`forMulti-UserVirtualEnvironments
`ThomasA.Funkhouser
`AT&TBellLaboratoriesz
`Abstract
`sharedvirtualenvironment.Applicationsforthesesystems
`includedistributedtrainingsimulations,collaborativedesign,
`Thispaperdescribestheclient-serverdesign,implementation
`virtualmeetings,andmultiplayergames.
`andexperimentalresultsforasystemthatsupportsreal-time
`Adi(cid:14)cultchallengeinmulti-uservisualsimulationismain-
`visualinteractionbetweenalargenumberofusersinashared
`tainingconsistentstateamongalargenumberofworksta-
` Dvirtualenvironment.Thekeyfeatureofthesystemisthat
`tionsdistributedoverawide-areanetwork.Sincethreedi-
`server-basedvisibilityalgorithmscomputepotentialvisualin-
`mensionalrenderingatinteractiveratesrequiresfastaccess
`teractionsbetweenentitiesrepresentingusersinordertore-
`tothegeometricdatabase,sharedportionsofthevirtualen-
`ducethenumberofmessagesrequiredtomaintainconsistent
`vironment(includingdynamicentitystates)arereplicatedon
`stateamongmanyworkstationsdistributedacrossawide-area
`everyparticipatingworkstation.Asaresult,wheneverany
`network.Whenanentitychangesstate,updatemessagesare
`entitychangesstate(e.g.,moves)ormodi(cid:12)estheshareden-
`sentonlytoworkstationswithentitiesthatcanpotentially
`vironment,anappropriateupdatemustbeappliedtoevery
`perceivethechange{i.e.,onestowhichtheupdateisvisi-
`copyofthedatabaseinordertomaintainconsistentstate
`ble.Initialexperimentsshowaxdecreaseinthenumberof
`(seeFigure ).
`messagesprocessedbyclientworkstationsduringtestswith
` entitiesinteractinginalargedenselyoccludedvirtual
`environment.
`CRCategoriesandSubjectDescriptors:
`[ComputerGraphics]:I. .Three-DimensionalGraphics
`andRealism{VirtualReality.
`AdditionalKeyWordsandPhrases:Visualsimulation,
`multi-usersystems,virtualreality, Dvirtualenvironments,
`real-timegraphics,client-serverdesign,distributedsystems.
` Introduction
`Inamulti-uservisualsimulationsystem,usersrunaninterac-
`tiveinterfaceprogramon(usuallydistinct)workstationscon-
`nectedtoeachotherviaanetwork.Theinterfaceprogram
`simulatestheexperienceofimmersioninavirtualenviron-
`mentbyrenderingimagesoftheenvironmentasperceived
`fromtheuser'ssimulatedviewpoint.Eachuserisrepresented
`inthesharedvirtualenvironmentbyanentityrenderedon
`everyotheruser'sworkstation,andmulti-userinteractionis
`supportedbymatchinguseractionstoentityupdatesinthe
`zMountainAvenue,
`A-,MurrayHill,NJ
` ,
`funk@research.att.com
`
`Figure :Multi-usersystemsmustmaintainconsistencybe-
`tweenentities(A,B,C,andD)replicatedonmultiplework-
`stations.
`Implementingvisualsimulationsystemsforlargenumbers
`ofusersisespeciallychallengingbecauseupdatescanoccurat
`extremelyhighrates.IfNentitiesmovethroughasharedvir-
`tualenvironmentsimultaneously,eachmodifyingitsposition
`and/ororientationMtimespersecond,thenM(cid:3)Nupdates
`aregeneratedtoashareddatabasepersecond.Moreover,
`updatesmustbepropagatedtoparticipatingworkstationsin
`nearreal-timesincelargevariancesordelaysinupdatescan
`resultinvisuallyperceptiblejerkyorlatentmotion,andthus
`maybedisturbingtousers.Asaresult,general-purposedis-
`tributeddatabasesystemsarenotadequateforuseinmulti-
`uservisualsimulationapplications,andspecial-purposemes-
`sagingprotocolsaretypicallyusedtomaintainconsistentstate
`inmulti-uservisualsimulationsystems[ , ].
`
`B
`
`
`
`A C D
`
`
`
`
`
`
`
`
`
`
`D
`
`
`
`
`A B C
`A
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`B C D
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`C
`
`
`
`
`
`
`A B D
`
`
`
`
`
`
`
`
`
`
` Shared 3D
`Virtual Environment
`
`0001
`
`BUNGIE - EXHIBIT 1037
`Bungie, Inc. v. Worlds Inc.
`IPR2015-01264, -01268, -01269, -01319, -01321, & -01325
`
`

`
`A
`
`
`
`B C D
`
`
`
`
`
`
`
`
`
`
`BB
`
`A
`
`B
`
`
`
`A C D
`
`
`
`
`
`
`
`
`
`
`D
`
`C
`
`D
`
`C
`
`A
`
`BB
`
`D
`
`
`
`A B C
`
`
`
`
`
`
`
`
`
`
`C
`
`Point−to−Point
` Connections
`
`D
`
`A
`
`BB
`
`C
`
`
`
`A B D
`
`
`
`
`
`
`
`
`
`
` Previouswork
`Numerousexperimentalvirtualrealitysystemsandmulti-
`playergameshavebeendevelopedforrealtimeinteraction
`insharedvirtualenvironments.Unfortunately,mostexisting
`systemsdonotscalewelltolargenumbersofsimultaneous
`users.RealityBuiltForTwo[],VEOS[],andMRToolkit[ ]
`aremulti-uservirtualrealitysystemsthatmaintainconsis-
`tentstateamongNworkstationsbysendingapoint-to-point
`messagetoeachofN- workstationswheneveranyentityin
`thedistributedsimulationchangesstate.Thisapproachyields
`O(N)updatemessagesduringeverysimulationstep(seeFig-
`ure),andthusdoesnotscaletomanysimultaneoususers
`beforethenetworkgetssaturated.
`Figure:Systemsusingpoint-to-pointconnectionspass
`O(N)updatemessages(labeledarrows)duringeachsimu-
`lationstep.
`SIMNET[],NPSNET[ ],andVERN[ ]usebroadcast
`messagestosendupdatestoallotherworkstationsparticipat-
`inginavirtualenvironmentatonce.Although,thisapproach
`cutsdownonthetotalnumberofmessagestransmittedto
`O(N),everyworkstationstillmustprocessamessagewhen-
`everanyentityinthedistributedsimulationchangesstate
`(seeFigure ).Sinceeveryworkstationmuststoredataand
`processupdatemessagesand/orsimulatebehaviorforallN
`entitiesduringeverysimulationstep,thesesystemsdonot
`scalebeyondthecapabilitiesoftheleastpowerfulparticipat-
`ingworkstation.ExperienceswithSIMNETandNPSNET
`showthatasigni(cid:12)cantpercentageofeveryworkstation'spro-
`cessingcapabilityisusedjusttoreadupdatemessagesfrom
`otherworkstationsduringlargesimulations;and,therefore,
`broadcastprotocolsarenotpracticalformorethanafewhun-
`dredusersoninexpensiveworkstations[ ].
`Inordertosupportverylargenumbersofusers(> )in-
`teractingsimultaneouslyinadistributedvirtualenvironment
`itisnecessarytodevelopasystemdesignandcommunication
`protocolthatdoesnotrequiresendingupdatemessagesto
`allparticipatinghostsforeveryentitystatechange.Kazman
`hasproposedasystemdesign,calledWAVES,inwhichmes-
`sagemanagersmediatecommunicationbetweenhosts,possi-
`blycullingirrelevantmessages[ , ].Hisapproachisvery
`similartotheonepresentedinthispaper.Onedi(cid:11)erenceis
`thatthispaperpresentsalgorithmsandexperimentalresults
`forvisibility-basedmessagecullingduringlargesimulations.
`
` Only B is
`visible to A
`
`A
`
`B
`
`Figure :SystemsusingbroadcastmessagespassonlyO(N)
`updateseachsimulationstep.But,everyworkstationstill
`mustprocesseveryupdatemessage.
` OverviewofApproach
`Thispaperdescribesasystem(calledRING)thatsupports
`interactionbetweenlargenumbersofusersinvirtualenvi-
`ronmentswithdenseocclusion(e.g.,buildings,cities,etc.).
`RINGtakesadvantageofthefactthatstatechangesmustbe
`propagatedonlytohostscontainingentitiesthatcanpossibly
`perceivethechange{i.e.,theonesthatcanseeit.Object-
`spacevisibilityalgorithmsareusedtocomputetheregionof
`in(cid:13)uenceforeachstatechange,andthenupdatemessagesare
`sentonlytothesmallsubsetofworkstationstowhichthe
`updateisrelevant.
`ThekeyideaisillustratedinFigure.Althoughentities
`A,B,C,andD((cid:12)lledcircles)allinhabitthesamevirtual
`environment,verylittlevisualinteraction(hatchedpolygons)
`ispossibleduetotheocclusionofwalls(solidlines).Infact,
`inthisexample,onlyonevisualinteractionispossible{entity
`AcanseeentityB.Therefore,onlyoneupdatemessagemust
`besentforeachupdatetoentityB'spositioninreal-time(to
`theworkstationwithentityA).Allotherentitiesneednot
`distributeanyupdatemessagesinreal-timesincetheyarenot
`visibletoanyotherentity.Fromthisexample,weseethatit
`ispossibletogreatlyreducethenumberofmessagespassedin
`real-timetomaintainconsistentstateamongmultipleentities
`inadenselyoccludedenvironmentusingline-of-sightvisibility
`todeterminetheregionofin(cid:13)uenceforeachupdate.
`Figure:Asystemthatcullsmessagesbasedonentity-entity
`visibilitymaybeabletoreducethenumberofmessagespro-
`cessedbyeachworkstationindenselyoccludedenvironments.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`D
`
`
`
`A B C
`
`
`
`
`
`
`
`
`
`
`A B C
`
`D
`
`A
`
`B C D
`
`C
`
`
`
`A B D
`
`
`
`
`
`
`
`
`
`
`Broadcast
` Network
`
`B C D
`
`A
`
`BA
`
`C
`D
`
`A
`
`
`
`B C D
`
`
`
`
`
`
`
`
`
`
`B
`
`
`
`A C D
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`C 
`
`D
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
` User C
`Visibility
`
`0002
`
`

`
`Client
`
`A
`
`
`
`B C D
`
`
`
`
`
`
`
`
`
`
`Client
`
`B
`
`
`
`A C D
`
`
`
`
`
`
`
`
`
`
`ThefollowingsectiondescribestheRINGsystemdesign.
`ResultsofexperimentswiththesystemarepresentedinSec-
`tion,whileadiscussionofalternateapproachesandpossible
`futureworkappearsinSection.Finally,Sectioncontains
`abriefsummaryandconclusion.
` RINGSystemDesign
`RINGrepresentsavirtualenvironmentasasetofindepen-
`dententitieseachofwhichhasageometricdescriptionand
`abehavior.Someentitiesarestatic(e.g.,terrain,buildings,
`etc.),whereasothershavedynamicbehaviorthatcanbeeither
`autonomous(e.g.,robots)orcontrolledbyauserviainput
`devices(e.g.,vehicles).Distributedsimulationoccurswhen
`multipleentitiesinteractinasharedvirtualenvironmentby
`sendingmessagestooneanothertoannounceupdatestotheir
`owngeometryorbehavior,modi(cid:12)cationstothesharedenvi-
`ronment,orimpactonotherentities.
`EveryRINGentityismanagedbyexactlyoneclientwork-
`station.Clientsexecutetheprogramsnecessarytogenerate
`behaviorfortheirentities.Theymaymapuserinputtocon-
`trolofparticularentitiesandmayincludeviewingcapabilities
`inwhichthevirtualenvironmentisdisplayedontheclient
`workstationscreenfromthepointofviewofoneormoreofits
`entities.Inadditiontomanagingtheirownentities(localen-
`tities),clientsmaintainsurrogatesforsomeentitiesmanaged
`byotherclients(remoteentities).Surrogatescontain(often
`simpli(cid:12)ed)representationsfortheentity'sgeometryandbe-
`havior.Whenaclientreceivesanupdatemessageforanen-
`titymanagedbyanotherclient,itupdatesthegeometricand
`behavioralmodelsfortheentity'slocalsurrogate.Between
`updates,surrogatebehaviorissimulatedbyeveryclient.
`Communicationbetweenclientsismanagedbyservers.
`Clientsdonotsendmessagesdirectlytootherclients,butin-
`steadsendthemtoserverswhichforwardthemtootherclient
`andserverworkstationsparticipatinginthesamedistributed
`simulation(seeFigure).Akeyfeatureofthisclient-server
`designisthatserverscanprocessmessagesbeforepropagating
`themtootherworkstations,culling,augmenting,oraltering
`them.Forinstance,aservermaydeterminethataparticular
`updatemessageisrelevantonlytoasmallsubsetofclients
`andthenpropagatethemessageonlytothoseclientsortheir
`servers.Inaddition,aservermaysendclientsauxiliarymes-
`sagesthatcontainstatusinformationhelpfulforfutureclient
`processing.Finally,aservermayreplacesomesetofmes-
`sagesintendedforaclientwithanother(possiblysimpler)set
`ofmessagesbettersuitedtotheclient'sperformancecapabil-
`ities.Theaimofthisclient-serverdesignistoshiftsomeof
`theprocessingburdenawayfromtheclientworkstationsand
`intoserverssothatlarger,morea(cid:11)ordable,multi-uservisual
`simulationsystemscanbebuiltusingprimarilylow-costclient
`workstations.
`Inthecurrentimplementation,RINGserversforwardup-
`datemessagesinreal-timeonlytootherserversandclients
`managingentitiesthatcanpossibly\see"thee(cid:11)ectsofthe
`update.Server-basedmessagecullingisimplementedusing
`precomputedline-of-sightvisibilityinformation.Priortothe
`multi-usersimulation,thesharedvirtualenvironmentispar-
`titionedintoaspatialsubdivisionofcellswhoseboundaries
`arecomprisedofthestatic,axis-alignedpolygonsofthevir-
`tualenvironment[ , ].Avisibilityprecomputationisper-
`
`Server
`
`Server
`
`
`
`
` Fast
`
`Network
`
`
`
`
`Server
`
`Client
`
`D
`
`
`
`A B C
`
`
`
`
`
`
`
`
`
`
`Client
`
`C
`
`
`
`A B D
`
`
`
`
`
`
`
`
`
`
`A
`
`B
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Figure:RINGserversmanagecommunicationbetween
`clients,possiblyculling,augmenting,oralteringmessages.
`formedinwhichthesetofcellspotentiallyvisibletoeachcell
`isdeterminedbytracingbeamsofpossiblesight-linesthrough
`transparentcellboundaries[ , ](seeFigure).During
`themulti-usersimulation,serverskeeptrackofwhichcells
`containwhichentitiesbyexchanging\periodic"updatemes-
`sageswhenentitiescrosscellboundaries.Real-timeupdate
`messagesarepropagatedonlytoserversandclientscontain-
`ingentitiesinsidesomecellvisibletotheonecontainingthe
`updatedentity.Sinceanentity'svisibilityisconservatively
`over-estimatedbytheprecomputedvisibilityofitscontaining
`cell,thisalgorithmallowsserverstoprocessupdatemessages
`quicklyusingcellvisibility\look-ups"ratherthanmoreexact
`real-timeentityvisibilitycomputationswhichwouldbetoo
`expensiveoncurrentlyavailableworkstations.
`Figure:Cell-to-cellvisibility(stipple)isthesetofcells
`reachedbysomesight-linefromanywhereinthesourcecell
`(darkbox)passingonlythroughtransparentportals(dash
`lines)andnoopaquewalls(blacklines).Itisauseful,pre-
`computedoverestimateofthevisibilityofanyentityresident
`inthesourcecell.
`AsanexampleofRINGserveroperation,considerthe(cid:13)ow
`ofmessagesbetweenclientsA,B,C,andDfortheentities
`showninFigureconnectedtoserversinthetopologyshown
`inFigure.Figureshowsthesurrogates(smallsquares
`labeledbyentity)and(cid:13)owofupdatemessages(arrowslabeled
`byentity)foreachofthefourentitiesinthisexample.
`
`############################
`############################
`############################
`
`############################
`
`
`
`
` ############################
`########
`"""""
`##############
`###########
`
`###########
`
`
`
`
` #####
`
`
`
`
`
`
`
`
`
`
`
` ############################
`########
`"""""
`##############
`###########
`
`########
`###########
`
`
`
`
` #####
`
`
`
`
`
`
`
`
`
`
`
` ############################
`########
`"""""
`##############
`###########
`
`########
`###########
`
`
`
`
` #####
`
`
`
`
`
`
`
`
`
`
`
`########
`"""""
`##############
`###########
`
`
`
` ########
`###########
`
`########
`"""""
`##############
`
`
` ###########
`
`
` ########
`###########
`
`########
`"""""
`##############
`
`
` ###########
`
`
` ########
`#####
`
`########
`
`
`
` ########
`"""""
`##############
`
`
` ###########
`#####
`
`########
`
`
`
`"""""
`##############
`
`
` ###########
`#####
`
`########
`
`
`
`"""""
`#####
`
`
`########
`
`
`#####
`
`
`###################
`
`
`########
`
`
`#####
`
`###################
`
`
`
`
`########
`
`#####
`
`###################
`
`
`
`#####
`
`
`###################
`#####
`
`
`###################
`#####
`
`
`###################
`#####
`
`
`
`###################
`#####
`
`
`
`#####
`
`
`
`
`##############
`
`
`
`
`##############
`
`
`##############
`
`
`
`
`##############
`
`
`
`
`##############
`
`
`
`
`###################
`
`
`
`######
`
`
`
`
`
` ########## #########
`
`
`
`
`
`
`
`######
`
`
`
`
`
` ########## #########
`
`
`
`
`
`
`
`######
`
`
`
`
`
` ########## #########
`
`
`
`
`
`
`######
`
`######
`######
`######
`######
`
`C
`
`D
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`0003
`
`

`
`(cid:15)IfentityAismodi(cid:12)ed:clientAsendsanupdatemessage
`toserverX.ServerXpropagatesthatmessagetoserver
`Y,butnottoserverZbecauseentitiesCandDarenot
`insidecellsinthecell-to-cellvisibilityofthecellcontain-
`ingentityA.ServerYforwardsthemessagetoClientB
`whichupdatesitslocalsurrogateforentityA.
`(cid:15)IfentityBismodi(cid:12)ed:clientBsendsanupdatemessage
`toserverY.ServerYthenpropagatesthatmessageto
`serversXandZ,whichforwardittoclientsAandC.
`ServerZdoesnotsendtheupdatemessagetoclientD
`becausethecellcontainingentityDisnotinthecell-to-
`cellvisibilityofthecellcontainingentityB.
`(cid:15)IfentityCismodi(cid:12)ed:clientCsendsanupdatemessage
`toserverZ.ServerZpropagatesthatmessagetoserver
`Y,whichthenforwardsthemessagetoClientB.ServerZ
`doesnotsendthemessagetoeitherserverXorclientD
`becauseneitherismanagingentitiesinthevisibilityset
`forentityC.
`(cid:15)IfentityDismodi(cid:12)ed:clientDsendsanupdatemessage
`toserverZ.ServerZdoesnotforwardthemessageto
`anyotherserverorclientbecausenootherentitycan
`potentiallyseeentityD.
`
`Client D
`
`D
`
`None
`
`
`
`
`D
`
`Client A
`A
`
`B
`
`
`
`
`A
`
`B
`
`Client B
`
`B
`
`
`A C
`
`
`
`
`
`
`
`A
`B
`C
`
`Server X
`
`Server Z
`
`A
`
`B
`
`CB
`
`Server Y
`
`C
`
`B
`
`Client C
`
`C
`
`B
`
`
`
`
`Figure:Flowofupdatemessages(labeledarrows)forup-
`datestoentitiesA,B,C,andDarrangedinavirtualenviron-
`mentasshowninFigure.
`RINGserversalloweachclientworkstationtomaintainsur-
`rogatesforonlythesubsetofremoteentitiesvisibletoatleast
`oneentitylocaltotheclient.Allotherremoteentitiesareir-
`relevanttotheclientsothereisnoneedtowastestorage
`spaceorbehavioralsimulationprocessingforthem.Tosup-
`portthisfeature,serverssendtheirclientsan\Add"message
`eachtimearemoteentityentersacellpotentiallyvisibleto
`oneoftheclient'slocalentitiesforthe(cid:12)rsttime.A\Remove"
`messageissentwhentheserverdeterminesthattheentityhas
`lefttheclient'svisibleregion.Asentitiesmovethroughthe
`environment,serversaugmentupdatemessageswith\Add"
`and\Remove"messagesnotifyingclientsthatremoteentities
`havebecomerelevantorirrelevanttotheclient'slocalenti-
`ties.Sincethesystemusesanunreliablenetworkprotocol,
`the\Add"and\Remove"messagesareconsideredhintsand
`
`neednotnecessarilybeprocessedbyclients.However,theyal-
`lowaclienttostoreandsimulateasmallsubsetoftheentities
`withlittleadditionalprocessingormessagetra(cid:14)c.
`TheprimaryadvantageoftheRINGsystemdesignisthat
`thestorage,processing,andnetworkbandwidthrequirements
`oftheclientworkstationsarenotdependentonthenumberof
`entitiesintheentiredistributedsimulation.Clientworksta-
`tionsmuststore,simulate,andprocessupdatemessagesonly
`forthesubsetofentitiesvisibletooneoftheclient'slocalen-
`tities.Indenselyoccludedvirtualenvironments,visiblesets
`tendtobeconstantsize(e.g.,howmanyroomsyoucansee
`lookingintothehallwayfromyouro(cid:14)ceusuallydoesnotde-
`pendonthesizeofyourbuildingorwhetheryourbuildingis
`surroundedbyalargecity),sotheburdenonindividualclient
`workstationsdoesnotgrowastheentiresystemdoes.
`Anotheradvantageisthathigh-levelmanagementofthe
`virtualenvironmentmaybeperformedbyserverswithoutthe
`involvementofeveryclient.Forinstance,addingorremoving
`anentitytoorfromthevirtualenvironmentrequiresnoti-
`(cid:12)cationofonlyoneserver.Thatserverhandlesnoti(cid:12)cation
`ofotherserversandclients.Also,theclient-serverdesignal-
`lowsuseofe(cid:14)cientnetworksandprotocolsavailablebetween
`serverworkstations,butnotuniversallyavailabletoallclient
`workstations.Forinstance,clientsmayconnecttoservers
`vialow-bandwidthnetworks,whileserverscommunicatewith
`eachotherviahigh-bandwidthnetworks.
`ThestorageandprocessingrequirementsofRINGservers
`arewithinpracticallimits.Unlikeclients,serversdonothave
`tostoredisplaydata(e.g.,polygons,textures,etc.).But,
`theymustmaintainspatialsubdivisionandvisibilityinforma-
`tionforthevirtualenvironment(typically<MBforlarge
`environments)andasurrogaterepresentationforeveryentity
`intheenvironment(currentlybytesperentity).Asserver
`storagerequirementsgrowlinearlywiththetotalnumberof
`entities,thesizeofserverworkstationmemorymaytheoreti-
`callylimitthenumberofentitiesthatareabletoshareavir-
`tualenvironmentsimultaneously.However,thisisnotlikely
`tobeaprobleminpracticesinceaworkstationwithMBof
`memorycanaccommodatenearlyonemillionentities.
`Serverworkstationprocessingisalsowithinreasonable
`bounds.Serversmustprocessmessagesinreal-timeonlyfor
`entitiesvisibletosomeentitymanagedbyoneoftheirclients;
`theyarenotrequiredtosimulateentitybehaviorbetweenup-
`dates;and,theydonotrenderimagesofthevirtualenviron-
`ment.Asaresult,thememorycapacityandprocessingpower
`ofstandardUNIXworkstationsareadequateforRINGservers
`indenselyoccludedvirtualenvironmentswithverylargenum-
`bersofsimultaneoususers.
`ThedisadvantageoftheRINGsystemdesignisthatex-
`tralatencyisintroducedwhenmessagesareroutedthrough
`servers. Ratherthansendingmessagesdirectlybetween
`clients,RINGrouteseachonethroughatleastoneserver,
`andpossiblytwo.Computationsareperformedintheservers
`beforemessagesarepropagatedfurtheraddingtolatency.So
`far,theextralatencyduetoserverprocessinghasnotbeen
`noticeableduringexperiments.Additionalworkwillhaveto
`bedonetoquantifythelatencycostsandtodeterminewhich
`typesofentityinteractionsaresensitivetolatencyissues.
`
`0004
`
`

`
`Client$Server
`#
`#
`Entities
`PerRoomEntitiesRooms Output
`Input
` .
` 
`
`.
` . 
` .
` 
`
`.
`.
` .
`
`
`.
` .
`. 
` 
`
`.
`.
`. 
` 
`
`.
` . 
`. 
`
`
`.
` .
`. 
` 
`
`.
`.
`.
` 
`
`.
`.
`.
` 
`
`.
` .
`.
`
`
`.
` .
`.
` 
`
`.
` .
`.
`
`
`.
` .
` .
` 
`
`.
` . 
` .
` 
`
`.
` . 
` .
`
`
`.
` .
` .
` 
`
`.
` .
` .
`
`
`.
`.
`.
` 
`
`.
`.
`.
`
`
`.
`.
`.
` 
`
`.
`.
`.
`
`
`.
`. 
`. 
`
`
`. 
` . 
`. 
` 
`
`. 
` .
`. 
`
`
`.
` . 
`. 
` 
`
`. 
` .
`. 
`
`
`.
` .
`.
`
`
`. 
`.
`Table :Averagemessageprocessingrates(messagespersec-
`ond)measuredinasingleclient(managingoneentity)during
`experimentswith, ,, ,and entitiesinvirtual
`environmentswith,, ,,,and\rooms."
`
`80
`
`70
`
`60
`
`50
`
`1024 Entities
` 512 Entities
` 256 Entities
`128 Entities
` 64 Entities
`
`Messages per Second
`
`40
`
`30
`
`20
`
`10
`
`0
`
`0
`
`2
`
`4
`6
`Entities per Room
`
`8
`
`10
`
`Figure :Averagerateofmessagessenttoasingleclient
`(managingoneentity)duringtestswith, ,, ,
`and entitiesinteractinginvirtualenvironmentswith,
`, ,,,and\rooms."Horizontalaxisrepresents
`thedensityofentitiesintheenvironment.
`
` ExperimentalResults
`Aprototypemulti-usersimulationsystemhasbeenimple-
`mentedwiththeclient-serverdesigndescribedintheprevious
`section.ThesystemrunsonSiliconGraphicsworkstations
`andusesUDP/IPdatagramsformessagepassing.Thissec-
`tionpresentsresultsofexperimentswiththissystemmanag-
`ingmanyentitiesinteractinginlargedenselyoccludedvirtual
`environments.Thevirtualenvironmentsusedintheseex-
`perimentsweremazesof\rooms"connectedby\hallways."
`Theywereconstructedbyinstancingasimple(cid:13)oor-plan ,,
`,, ,and timesinasquaretilingpattern.Eachtile
`containedrooms(countinghallways)andhadpoly-
`gons(seeFigure).Thelargestenvironmentusedinthese
`testshad , polygonswhichformed, cells.Thespa-
`tialsubdivisionandvisibilityinformationforthisenvironment
`took secondstocomputeandrequired .MBofstorage.
`Figure:Onetileofvirtualenvironmentusedintests.
`Experimentswererunwithseveralenvironmentsizesand
`variousnumbersofentities,clients,andserverstocharac-
`terizethescalabilityofthesystemdesign.Duringthese
`experiments,entitiesnavigatedthroughthevirtualenviron-
`ment\randomly"followingpiecewiselinearpathsinrandom-
`izeddirectionsforrandomizeddistances.Clientssentupdate
`messagesonlyforchangesinderivativesofentityposition
`and/ororientation(i.e.,dead-reckoning)whileotherclients
`simulatedintermediatepositionswithlinear\smooth-back."
`Updatemessagescontainingbytes(message-type[],entity-
`ID[],target-position[ ],target-orientation[ ],positional-
`velocity[],androtational-velocity[])weregeneratedforeach
`entityonceevery. secondsonaveragewiththis\random"
`navigationalbehavior.
`Toinvestigatethemessageprocessingrequirementsofasin-
`gleclientinRING,weperformedtestsmeasuringtheratesof
`messagesreceivedbyclientsmanagingoneentitynavigating
`throughvirtualenvironmentscontaining, ,, ,
`and entitiesmanagedbyotherclients.Eachtestwas
`repeatedinvirtualenvironmentscontaining,, ,,
`,androoms.PlatesIandIIcontainimagescaptured
`duringtestswith entitiesinaroomenvironment.Ta-
`ble andFigure showaverageratesofmessagesreceivedby
`individualclientsineachtest.InFigure ,pointsrepresent-
`ingthesamenumberoftotalentitiesareconnectedbylines,
`whilepointsrepresentingthesamedensityofentitiesareat
`thesamehorizontalpositionintheplot.
`
`
`
`
`
`
`
`
`
`
` 
`
`
`
`
`
`
`
`
`
`
`
`
`
` 
`
`
`
`Hallway
`
`
`
`
`
`
`
`
`
`
`
`
`
`
` 
`
`
`
`Room
`Room
`Room
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`  
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Room
`Room
`Room
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
` 
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
` 
`
`
`
`
`
`
`
`
` 
`
`
`
`
`
`
`
`
`
`
`
`
`
` 
`
`
`
`
`
`
`
`
`
` 
`
`
`
`
`
`
`
`
`
`
`
`
`
` 
`
`Room
`Room
`Room
`Room
`
`
`
`
`
`
`
`
`
`  
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`  
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`  
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`  
`
`
`Hallway
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Room
`Room
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Room
`Room
`Room
`Room
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Hallway
`
`
`
`
`
`
`
`
`
`
`
`
`  
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`  
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`  
`
`Hallway
`
`0005
`
`

`
`Asthenumberofserversincreases,thetotalnumberof
`messagesinputandoutputbyasingleserverdecreases.This
`phenomenonisaidedbythefactthatupdatemessagesare
`propagatedonlytoserversattachedtoclientswithentities
`thatcanpotentiallyseetheupdatedentity.Inthetestwith
` servers,%ofthereal-timeserver$servermessagesare
`culledduetovisibility(i.e.,the entitiesmanagedbyeach
`ofthe serverscumulativelysee%oftheenvironment).
`Theseresultsareencouragingsincevisibility-basedmessage
`cullingbecomesmoree(cid:11)ectiveasthenumberofserversin-
`creasesandlessofthemodelbecomesrelevanttoeachserver.
`Fromtheseresults,weconcludethatitispossibletobuild
`largemulti-uservisualsimulationsystemsusingaclient-server
`design.Wehavefoundthatserver-basedmessageprocessing
`algorithmswhichcullmessagesbasedonthethreedimensional
`geometryofthevirtualenvironmentcanbee(cid:11)ectiveatreduc-
`ingthenetworktra(cid:14)cintoclientworkstations.Asaresult,
`forsu(cid:14)cientlyoccludedvirtualenvironments,itispossibleto
`buildlarge,a(cid:11)ordablemulti-uservirtualenvironmentsusing
`inexpensiveclientworkstationswithlow-bandwidthnetwork
`connections,whilehigherperformanceworkstationsarere-
`quiredonlyfortherelativelyfewservers.
` Discussion
`Severalalternateapproachesandfutureextensionsarepossi-
`bleforthissystem.
`Multicast
`Inour(cid:12)rstexperimentswithmulti-uservirtualenvironments,
`weusedIPmulticasttosendupdatemessagesdirectlybe-
`tweenclients.Thegeneralideaistomapentitypropertiesinto
`multicastgroups,andsendupdatemessagesonlytorelevant
`groups[].Forinstance,Macedonia[ ]partitionsavirtual
`worldintoaDgridofhexagonalshapedcellseachofwhich
`isrepresentedbyaseparatemulticastgroup.Entitieslocalize
`theirvisualinteractionsbysendingupdatesonlytothemulti-
`castgrouprepresentingthecellinwhichtheyreside,andthey
`listenonlytomulticastgroupsrepresentingcellswithinsome
`radius.ThemulticastapproachissimilartotheRINGclient-server
`approachforwide-areanetworks.Inbothcases,intermediate
`machinesmaycullmessagesratherthanpropagatingthemto
`allparticipatingworkstations.However,usingmulticast,mes-
`sagecullingisdonebyroutersatthenetworklayer,whereas,
`inRING,messagecullingisdonebyservermachinesatthe
`applicationlayer(seeFigure ).Theadvantagesofthemul-
`ticastapproacharethat: )fewermessagesmustbepassed
`ifclientsareconnecteddirectlytoamulticast-capableLAN
`(e.g.,ethernet),and)latencyisreducedduetofastermes-
`sagerouting.Thedisadvantagesarethat: )delaysassociated
`withjoiningandleav