# Perception-Based Filtering for MMOGs

Authors: Souad El Merhebi; Jean-Christophe Hoelt; Patrice Torguet; Jean-Pierre Jessel
Journal: International Journal of Computer Games Technology
 (2008)

---

## Abstract

Online games have exploded in the last few years. These games face several
problems linked to scalability and interactivity. In fact, online games should provide
a quick feedback of users' interactions as well as a coherent view of the shared
world. However, the search for enhanced scalability dramatically increases message
exchange. Such an increase consumes processing power and bandwidth, and thus
limits interactivity, consistency, and scalability. To reduce the rate of message exchange,
distributed virtual environment systems use filtering techniques such as interest
management that filters messages according to users' interests in the world.
These interests are influenced by perceptual facts which we study in this paper
in order to build upon them a perception-based filtering technique. This technique satisfies
users' needs by precisely providing an exact filtering which is more efficient
than other techniques.


---

## Body

## 1. Introduction

Online game players interact within a shared virtual world through
their avatars. Players' interactions change the state of their avatars and may
affect the state of the world. To insure coherency, all players should observe
the same state of the shared world at the same moment. Therefore, the activity
of a player must be communicated to the other players. This must be done as
quickly as possible to provide an interactive game in which players have a
quick feedback of their interactions.On the other hand, online games, especially massively
multiplayer online games (MMOGs), need to be more and more scalable. However,
increasing the number of participants tends to dramatically increase the number
of update messages. A higher amount of message exchange requires higher
bandwidth and more processing power, which slows down the system and makes it
less interactive “lagging” [1]. The system should therefore be adapted to these
limited resources. This can be done by minimizing exchanged messages and the
number of their recipients.Distributed virtual environments (DVEs) systems take
advantage of the fact that participants neither perceive nor are interested in
the whole virtual world. This is due to many reasons: world's design, distances
that separate avatars, limitation of avatars' awareness, and so forth.
Sometimes, developers themselves create these limitations to enhance the
scalability of the system (shards, fog, etc.). Limitations of awareness define
the interests of players within the world. This provides an interesting basis
to design message filtering whose concept is to deliver messages only to
concerned participants, this is called interest management.The perception of an avatar within its world expresses
or contributes to expressing its interest. Perception-based filtering [2] defines the perceptual
interests of avatars in an exact way. This paper completes the study of
perception-based filtering by including a more general perception model and
providing deeper mathematical analysis backed up with the results of an
experimental evaluation.In Section2, we present a brief overview of related
work. Section 3 describes the relation between awareness and perception.
Section 4 describes perception-based filtering. In Section 5, we present the
translation of perception rules into existing interest management techniques.
Section 6 presents the experimental and analytical evaluation of
perception-based filtering. Finally, Section 7 presents conclusions and
outlines future work.


## 2. Related Work

Interest management techniques have been implemented
within military DVE systems as well as in games. They use the division of space
or the definition of individual interests of avatars, or a combination of the
two approaches.NPSNET [3] divides the environment into hexagonal cells and
specifies for each entity an area of interest (AOI), which is a circle centered
on the entity. An entity is only aware of entities within the hexagons that
overlap its AOI.MASSIVE implements the spatial model of interaction
[4] which assigns an
aura to each object for each medium (graphics, audio, etc.). Spatial model's
filtering is achieved in two stages. The first detects auras' collision of
couples of objects. This entails a possibility of interaction and leads to the
second stages which consists, in the negotiations, of levels of awareness
between users. The level of awareness of entity A toward entity B is a function
of A's focus and B's nimbus, the focus being the observer's allocation of
attention and the nimbus the observed's manifestation or observability. The
negotiations of awareness levels decide the existence of awareness on
each side. If there is awareness, its level can influence the attribution of
resources (e.g., bandwidth, audio quality, etc.). Whenever a change occurs, the
couple has to negotiate again to know whether a change in awareness took place.
For performance and development cost reasons, this model is often used in a
simplified way which only uses auras to determine awareness of avatars, even if
this entails the exclusive establishment of symmetrical relations.Effect management [5] is a variation of the spatial model of interaction
which preserves the attractive feature of asymmetric awareness, while offering
the possibility of not defining foci and nimbi functions if there are no
resource accommodations. Effect management determines the existence of
awareness on the two sides distinctly in the first stage. The second stage
(i.e., awareness level computation) will only be dedicated to the determination
of the nonnull awareness level through foci and nimbi negotiations if
needed. To achieve that, the first stage associates with each entity a viewing
zone which reflects the ability to perceive and an effect zone which reflects
the ability to be perceived instead of combining the two abilities within the
aura. When the viewing zone of an entity A overlaps the effect zone of
an entity B, A becomes aware of B.HLA [6, 7] uses interest management through a runtime
infrastructure (RTI) service: the data distribution management (DDM). This
service first allows the expression of entities' interest and availability by
defining subscription and publication zones. Then, it computes intersections
between zones and deliver updates according to those computations (i.e., an
update is only sent to the entities whose subscription zones intersect with its
publication zone). DDM uses a multidimensional coordinate system in which
entities define their interests and availability. This system can use a fixed
or hierarchical grid.Other DVE systems and online games use division of
space without the individual definition of entities' interests into
zones. Some of them also associate to each division
or  share a server in order to enhance scalability.
Such systems are SPLINE [8], RING [9], Ultima Online, Neverwinter Nights, Silkroad Online,
World of Warcraft, and so forth.Our study focuses on the definition of individual
interests of avatars because this approach provides a more exact filtering than
division of space. As we have seen, many interest management techniques define their
users' interests in individual zones because they are simple, natural and not
expensive. However, these systems define the extents of their zones in an
empirical way. This leads to imprecise filtering which makes avatars receive
more or fewer messages than they actually need. In fact, if an avatar does not
receive all the messages that interest it, the player's experience will be less
realistic and interactive. Otherwise, if avatars receive messages that do not
interest them, the system and the network will be overloaded with unnecessary
messages. Thus, in both cases the empirical definition of zone extents will
harm the simulation. For these reasons, it is very important to have a
mechanism that determines the interests of users in a precise way. Our previous
study of perception-based filtering [2] defined the limits of avatars' perception and
presented a translation of these limits into zones in other interest management
techniques. In this paper, we will complete this study by presenting a more
general perception model and by providing a comparative analysis backed up with
experimental results between the perception-based filtering and the other
interest management techniques.


## 3. Relation between Awareness and Perception

The perceptibility of an avatar (its ability to be
perceived, its manifestation) depends on its importance in the world. This
importance may be related to the avatar's situation (an aircraft is easily
perceived in a clear sky) or its function (a speaker in a stadium is seen and
heard by all the audience). Most importantly, an avatar is noticed due to its
physical manifestation: its size.On the other hand, not all avatars have the same
capacity of awareness because of their structure, function or behavior. An
avatar can simulate a short-sighted person, another represents a person
carrying binoculars. We can also have a well-positioned entity or a fast
entity. These entities have different degrees of perception.Therefore, an avatar's awareness of another depends on
the perception of the observer, the perceptibility of the observed and the
distance that separates the couple. This awareness may only depend on these
factors in case of the absence of others. This relationship was expressed in
some interest management techniques such as area of interest management,
spatial model of interaction, and effect management through the use of zones.


## 4. Perception-Based Filtering

Computer graphics' developers use many algorithms to
perform visibility tests. In the following, we will study these algorithms to
see if they may specify convenient message filtering parameters.Computer graphics determines that an object is not
visible due to the following widely used properties.(i)
P1 is outside of camera's view volume.(ii)
P2 is hidden by other objects.(iii)
P3 covers less than one pixel on the
screen.
P1 cannot
define an efficient filtering technique for DVEs because when a player turns
his head, he may quickly visualize a lot of new avatars. Therefore, P1 does not define stable filtering parameters that prevent an avatar from
frequent and thus expensive changes of interests.P2 may be
interesting because it can eliminate an important amount of message exchange.
Many techniques, based on this property, have been used in computer graphics.
These techniques can be used for message filtering for DVEs. For example, it is
possible to use occlusion queries on recent GPUs [10] or precomputed potentially
visible sets [11] (as
used in Quake(tm) [12]
and RING [9], e.g.). However, the implementation of these techniques is difficult and
they require complex computations when they are done dynamically (especially on
a client/server architecture because the server performs filtering for many
entities during each simulation frame).P3 offers a
simpler method: knowing player A's screen resolution and the 3D-engine camera
parameters, we can easily determine the projection of avatar B's bounding
sphere on the screen. If the size of the projected sphere is less than a
certain threshold (which may be set to the size of one pixel, e.g.), A
will not see B. This will be the basis of our perception-based filtering.


### 4.1. Maximal Distance of Perception

Let us take the standard approach of a virtual camera
using a projection plane as it is defined in OpenGL and Direct3D. The camera is
defined by its angle of view (or field of view—fov), which is the angular
extent of the virtual scene that is rendered (see Figure1). This defines a
viewing volume (a pyramid), which is then divided into smaller volumes, one for
each pixel. Given this, we can determine the angle of view covered by a pixel
for a specific player from the virtual camera's field of view (fov) and the
number of pixels covered by the user's viewport (SSize). The
whole screen covers 100% of the field of view, therefore a single pixel covers
approximately an average angle θ (The camera model induces a distortion for the
pixels that are far from the center of the screen. We will consider this
distortion negligible in our study.):(1)θ=fovSSize.Figure 1
Angle of view
of a virtual camera.On the other hand, we can compute the angular extentα of a 3D object projection on the screen
(Figure 2). To compute this extent, we can see in Figure 3 that the
relationship between the angle α (view angle covered by the object), the
“opposite" side R (the bounding sphere radius), and the “adjacent"
side D (distance between object and camera) is(2)tan(α2)=RD.Figure 2
Angular
extents of a pixel and a sphere.Figure 3
Angular
extent of a 3D object.By using our filtering criteria, P3 allows an object to be seen when the size of its projection is superior to one
or several pixels. The minimal number of perceived pixels depends on the
viewing capacity of the user. A user with an enhanced capacity of view can see
an object if its projection covers one pixel, while a short-sighted user will
need a projection superior to several pixels to be able to see a projected
object.When the size of the projected sphere is bigger than a
pixel this is exactly the same as having the angular extent “α” bigger than the angle covered by one pixel
“θ” (Figure 2). For a short-sighted user, this
maximal angle will be multiplied by the minimal number of pixels seen by the
user “n”. Knowing that α and n⋅θ are always smaller than π,
we have(3)α≥n⋅θ⟺tan(α2)≥tan(n⋅θ2)⟺RD≥tan(n⋅θ2)⟺D≤Rtan(n⋅θ/2).This inequality
shows that an observer can see an object if the distance that separates them is
less or equal to “R/tan(n⋅θ/2)." This gives the maximal distance of
perception under which the user sees the other avatar;(4)Dmax=Rtan(n⋅θ/2)=R⋅V,whereV=1tan(n⋅θ/2).This maximal distance depends on the player's viewing
capacityV and on the observed avatar's size R.The number of visible avatars is directly related to
the player's viewing capacity. However, it is possible that at a certain moment
during the game, the system or a user becomes no longer able to handle more message
transfers. To prevent this, we allow it to artificially reduce the values of
perception distance by using the filtering coefficient “FC” that varies
between 0 and 1:(5)Dmax=R⋅V⋅FC.


### 4.2. Filtering Mechanism

To be able to use perception-based filtering, a server
(in client/server architectures) or clients (in peer-to-peer architectures)
compute the maximal distance of perception that the observing avatar has of the
observed avatar (a simple multiplication). Then, they compare this maximal
distance of perception to the distance that separates the two avatars to deduce
if the perception takes place or not.


## 4.1. Maximal Distance of Perception

Let us take the standard approach of a virtual camera
using a projection plane as it is defined in OpenGL and Direct3D. The camera is
defined by its angle of view (or field of view—fov), which is the angular
extent of the virtual scene that is rendered (see Figure1). This defines a
viewing volume (a pyramid), which is then divided into smaller volumes, one for
each pixel. Given this, we can determine the angle of view covered by a pixel
for a specific player from the virtual camera's field of view (fov) and the
number of pixels covered by the user's viewport (SSize). The
whole screen covers 100% of the field of view, therefore a single pixel covers
approximately an average angle θ (The camera model induces a distortion for the
pixels that are far from the center of the screen. We will consider this
distortion negligible in our study.):(1)θ=fovSSize.Figure 1
Angle of view
of a virtual camera.On the other hand, we can compute the angular extentα of a 3D object projection on the screen
(Figure 2). To compute this extent, we can see in Figure 3 that the
relationship between the angle α (view angle covered by the object), the
“opposite" side R (the bounding sphere radius), and the “adjacent"
side D (distance between object and camera) is(2)tan(α2)=RD.Figure 2
Angular
extents of a pixel and a sphere.Figure 3
Angular
extent of a 3D object.By using our filtering criteria, P3 allows an object to be seen when the size of its projection is superior to one
or several pixels. The minimal number of perceived pixels depends on the
viewing capacity of the user. A user with an enhanced capacity of view can see
an object if its projection covers one pixel, while a short-sighted user will
need a projection superior to several pixels to be able to see a projected
object.When the size of the projected sphere is bigger than a
pixel this is exactly the same as having the angular extent “α” bigger than the angle covered by one pixel
“θ” (Figure 2). For a short-sighted user, this
maximal angle will be multiplied by the minimal number of pixels seen by the
user “n”. Knowing that α and n⋅θ are always smaller than π,
we have(3)α≥n⋅θ⟺tan(α2)≥tan(n⋅θ2)⟺RD≥tan(n⋅θ2)⟺D≤Rtan(n⋅θ/2).This inequality
shows that an observer can see an object if the distance that separates them is
less or equal to “R/tan(n⋅θ/2)." This gives the maximal distance of
perception under which the user sees the other avatar;(4)Dmax=Rtan(n⋅θ/2)=R⋅V,whereV=1tan(n⋅θ/2).This maximal distance depends on the player's viewing
capacityV and on the observed avatar's size R.The number of visible avatars is directly related to
the player's viewing capacity. However, it is possible that at a certain moment
during the game, the system or a user becomes no longer able to handle more message
transfers. To prevent this, we allow it to artificially reduce the values of
perception distance by using the filtering coefficient “FC” that varies
between 0 and 1:(5)Dmax=R⋅V⋅FC.


## 4.2. Filtering Mechanism

To be able to use perception-based filtering, a server
(in client/server architectures) or clients (in peer-to-peer architectures)
compute the maximal distance of perception that the observing avatar has of the
observed avatar (a simple multiplication). Then, they compare this maximal
distance of perception to the distance that separates the two avatars to deduce
if the perception takes place or not.


## 5. Determining Radiuses of Interest Zones

As we have seen in Section2, many interest management
techniques use zones to determine avatars' interests and manifestations. Until
now, these techniques have determined the radiuses of their zones empirically.
In this section, we propose mechanisms that determine these radiuses based on
our perception rules. This translation has two goals: providing a mechanism to
determine the size of zones for these used filtering techniques and
establishing a fair ground to compare the perception-based filtering with the
existing interest management techniques.The condition that the zones should strictly fulfil to
express perception is that whenever an avatar sees another with
perception-based filtering, it should be able to see it with the parallel
interest management techniques (area of interest management, spatial model of
interaction or effect management, etc.). If this entails a reception of
unnecessary information, this can be tolerated. But not receiving important
update messages cannot be tolerated.In Figure4, we can see the translation of perception
rules into various interest management techniques. The computation of these
radiuses varies according to the techniques, but it always depends on the
perception and perceptibility of all the avatars of the environment. In the
following, we analyze these dependencies and their impact on filtering.Figure 4
Translation of
perception rules in various interest management techniques.


### 5.1. Area of Interest Management

The area of interest management allows an avatar to
see the avatars that are within its area of interest (AOI). To have a fair
translation, whenever an avatar sees another with perception-based filtering,
it should see it with area of interest management. Therefore, if the distance
between two avatars is smaller thanDmax,
the AOI of the viewing avatar should cover the other avatar (see Figure 5).
Consequently, the radius of the AOI should be greater than or equal to all the Dmax.
To optimize filtering, we choose the largest Dmax that the avatar has as its AOI radius.Figure 5
Determining the
AOI radius.S being the set of games'
avatars:(6)AOI(A)=max{Dmax(A,n),∀n∈S}.This may entail excessive information reception
because if we have an important avatar, all the avatars will enlarge their AOIs
to be able to see it when it is distant. This will make the avatars receive
information of small and distant avatars that they are not supposed to see.


### 5.2. Spatial Model of Interaction

The spatial model of interaction allows two avatars to
see each other when their auras collide. The sizes of the auras will be defined
following the ruleR.“A sees B with perception-based filtering" means
that the distance between A and B is less than or equal to the corresponding Dmax:(7)D(A,B)≤Dmax(A,B).And “A sees B with the spatial model of
interaction" means that the auras of A and B collide:(8)D(A,B)≤Aura(A)+Aura(B),where Aura(N) is the radius of
N's aura.A condition that makesR possible
is(9)C:Aura(A)+Aura(B)≥Dmax(A,B) because(10)D(A,B)≤Dmax(A,B),Dmax(A,B)≤Aura(A)+Aura(B)⇒D(A,B)≤Aura(A)+Aura(B).So conditionC allows the satisfaction of rule R.
Therefore, S being the set of the game's avatars, the
general rule will be(11)∀a∈S,∀b∈S,Aura(a)+Aura(b)≥Dmax(a,b).This rule gives a set of constraints which define a
system of inequalities. For example, if we take a game with three avatar types:
a person (P), an eagle-eyed person (EE), and a truck (T), the following constraints will be
raised:(12)2*Aura(P)≥Dmax(P,P),(to enable two persons to see
each other when they should),(13)Aura(P)+Aura(EE)≥Dmax(P,EE)(to enable a person to see an
eagle-eyed person),(14)Aura(P)+Aura(T)≥Dmax(P,T),Aura(EE)+Aura(P)≥Dmax(EE,P),2×Aura(EE)≥Dmax(EE,EE),Aura(EE)+Aura(T)≥Dmax(EE,T),Aura(T)+Aura(P)≥Dmax(T,P),Aura(T)+Aura(EE)≥Dmax(T,EE),2×Aura(T)≥Dmax(T,T).These constraints define a system of linear
inequalities which has an infinity of solutions. Our goal is to find the
optimal solution that minimizes the number of possible interactions between
avatars. This number is proportional to the possibility of auras' collisions,
which makes it proportional to the total area covered by all avatars'
auras:(15)AA=∑n∈SπAura(n)2.Such a system can be solved in many ways. We used
Newton's method for the solution of systems of equalities and inequalities
[13], parameterized to
minimize the value of AA.


### 5.3. Effect Management

Effect
management offers better precision because for each avatar we distinguish the
ability to see (perception) from the ability of being seen (perceptibility),
this gives more precise constraints. A similar demonstration to that of the
spatial model of interaction gives the following translation
condition:(16)D(A,B)≤V(A)+E(B), where V(A) is the radius of an avatar A's viewing zone
and E(B) is the radius of an avatar's B effect zone.So,S being the set of the game's avatars, the
system takes this form:(17)∀a∈S,∀b∈S,E(a)+V(b)≥Dmax(a,b).If we take our previous example, we will have the
following system of inequalities:(18)V(P)+E(P)≥Dmax(P,P),(to enable persons to see each
other)(19)V(P)+E(EE)≥Dmax(P,EE),(to enable a person to see an
eagle-eyed person)(20)V(P)+E(T)≥Dmax(P,T),V(EE)+E(P)≥Dmax(EE,P),V(EE)+E(EE)≥Dmax(EE,EE),V(EE)+E(T)≥Dmax(EE,T),V(T)+E(P)≥(maxT,P),V(T)+E(EE)≥Dmax(T,EE),V(T)+E(T)≥Dmax(T,T).The system can be solved by minimizing the area
covered by the effect and viewing zones:(21)AEV=∑n∈SπC(n)2+πE(n)2.


## 5.1. Area of Interest Management

The area of interest management allows an avatar to
see the avatars that are within its area of interest (AOI). To have a fair
translation, whenever an avatar sees another with perception-based filtering,
it should see it with area of interest management. Therefore, if the distance
between two avatars is smaller thanDmax,
the AOI of the viewing avatar should cover the other avatar (see Figure 5).
Consequently, the radius of the AOI should be greater than or equal to all the Dmax.
To optimize filtering, we choose the largest Dmax that the avatar has as its AOI radius.Figure 5
Determining the
AOI radius.S being the set of games'
avatars:(6)AOI(A)=max{Dmax(A,n),∀n∈S}.This may entail excessive information reception
because if we have an important avatar, all the avatars will enlarge their AOIs
to be able to see it when it is distant. This will make the avatars receive
information of small and distant avatars that they are not supposed to see.


## 5.2. Spatial Model of Interaction

The spatial model of interaction allows two avatars to
see each other when their auras collide. The sizes of the auras will be defined
following the ruleR.“A sees B with perception-based filtering" means
that the distance between A and B is less than or equal to the corresponding Dmax:(7)D(A,B)≤Dmax(A,B).And “A sees B with the spatial model of
interaction" means that the auras of A and B collide:(8)D(A,B)≤Aura(A)+Aura(B),where Aura(N) is the radius of
N's aura.A condition that makesR possible
is(9)C:Aura(A)+Aura(B)≥Dmax(A,B) because(10)D(A,B)≤Dmax(A,B),Dmax(A,B)≤Aura(A)+Aura(B)⇒D(A,B)≤Aura(A)+Aura(B).So conditionC allows the satisfaction of rule R.
Therefore, S being the set of the game's avatars, the
general rule will be(11)∀a∈S,∀b∈S,Aura(a)+Aura(b)≥Dmax(a,b).This rule gives a set of constraints which define a
system of inequalities. For example, if we take a game with three avatar types:
a person (P), an eagle-eyed person (EE), and a truck (T), the following constraints will be
raised:(12)2*Aura(P)≥Dmax(P,P),(to enable two persons to see
each other when they should),(13)Aura(P)+Aura(EE)≥Dmax(P,EE)(to enable a person to see an
eagle-eyed person),(14)Aura(P)+Aura(T)≥Dmax(P,T),Aura(EE)+Aura(P)≥Dmax(EE,P),2×Aura(EE)≥Dmax(EE,EE),Aura(EE)+Aura(T)≥Dmax(EE,T),Aura(T)+Aura(P)≥Dmax(T,P),Aura(T)+Aura(EE)≥Dmax(T,EE),2×Aura(T)≥Dmax(T,T).These constraints define a system of linear
inequalities which has an infinity of solutions. Our goal is to find the
optimal solution that minimizes the number of possible interactions between
avatars. This number is proportional to the possibility of auras' collisions,
which makes it proportional to the total area covered by all avatars'
auras:(15)AA=∑n∈SπAura(n)2.Such a system can be solved in many ways. We used
Newton's method for the solution of systems of equalities and inequalities
[13], parameterized to
minimize the value of AA.


## 5.3. Effect Management

Effect
management offers better precision because for each avatar we distinguish the
ability to see (perception) from the ability of being seen (perceptibility),
this gives more precise constraints. A similar demonstration to that of the
spatial model of interaction gives the following translation
condition:(16)D(A,B)≤V(A)+E(B), where V(A) is the radius of an avatar A's viewing zone
and E(B) is the radius of an avatar's B effect zone.So,S being the set of the game's avatars, the
system takes this form:(17)∀a∈S,∀b∈S,E(a)+V(b)≥Dmax(a,b).If we take our previous example, we will have the
following system of inequalities:(18)V(P)+E(P)≥Dmax(P,P),(to enable persons to see each
other)(19)V(P)+E(EE)≥Dmax(P,EE),(to enable a person to see an
eagle-eyed person)(20)V(P)+E(T)≥Dmax(P,T),V(EE)+E(P)≥Dmax(EE,P),V(EE)+E(EE)≥Dmax(EE,EE),V(EE)+E(T)≥Dmax(EE,T),V(T)+E(P)≥(maxT,P),V(T)+E(EE)≥Dmax(T,EE),V(T)+E(T)≥Dmax(T,T).The system can be solved by minimizing the area
covered by the effect and viewing zones:(21)AEV=∑n∈SπC(n)2+πE(n)2.


## 6. Experimental Results

To implement perception-based filtering, we used
Architecture for Systems of Simulation and Training in Teleoperation (ASSET)
[14], a prototyping
system supporting the design and evaluation of new teleoperation systems by
using virtual reality components. In our context, ASSET is used in simulation
mode only thus becoming a generic client/server-based DVE system.We compared the performance of perception-based
filtering with those of area of interest management and spatial model of
interaction in its simple version and effect management. The level of realism
is constant with the four techniques, since it is fixed by the perception rules
while the communication load varies following the filtering technique and this
is what interests us.


### 6.1. Experimental Environment

We used for our
experiments 100 nodes of a cluster of Grid'5000 [15], which is a grid of
thousands of CPUs distributed at 9 sites France wide. Nodes have Rocks Linux
3.3.0 as operating systems and are connected by a Gigabit Ethernet network. The
nodes are IBM eServer 325 shipped with AMD Opteron 246 CPUs (2.0 GHz/1 MB/400 MHz), 2 GB memory, 2x Gigabit Ethernet (1 in use) and Myrinet-2000
(M3F-PCIXF-2) network cards.An experiment is a two-minute simulation with a
simulation step of 200 milliseconds. We carried out the experiments varying the
number of clients. We repeated the experiments several times and averaged the
resulting values. During an experiment, the server collects various
experimental data such as the number of exchanged messages and the server's
load.The server was always allocated a dedicated node.
However, since the number of clients in a single simulation got up to 160 (and
we only have 100 nodes available), we eventually had to run two clients on the
same node.


### 6.2. Simulation Parameters

The virtual
environment is a 20000 × 20000 square. The behavior of avatars is autonomous
following a random acceleration with a privileged direction. An avatar can be a
normal person, an eagle-eyed person (with good visual ability) or a truck. The
person and the driver of the truck have a limited viewing capacity, while the
eagle-eyed person has an enhanced viewing capacity. Furthermore, the truck has
a larger size, thus it has a stronger chance of being seen than the others.


#### 6.2.1. Perception-Based Filtering

For
perception-based filtering, we consider that the field of view is equal to 120
degrees and the screen is 1024 pixels large. This gives us the angle covered by
one pixel,(22)θ=fovNbPixelsX=1201024=0.117.We consider that the eagle-eyed person is able to see
the details on the screen up to one pixel(n=1). His viewing capacity
is of(23)Veagle=1tan(neagle⋅θ2)=1tan(1⋅0.1172)=1tan(0.058)=977.8.To obtain the maximal distance of perception that the
avatar has of a person, we multiply the radius of the person with the visual
capacity of the avatar:(24)Dmax(eagle,person)=Rperson⋅Veagle=1.022⋅977.8=1000.On the other hand, the maximal distance of perception
that an eagle-eyed person has of a truck depends on the truck's bounding sphere
radius:(25)Dmax(eagle,truck)=Rtruck⋅Veagle=2.045⋅977.8=2000.The avatars with a normal viewing capacity (the person
and the driver of the truck) will see less clearly on the screen. We will
consider that their minimal threshold of perception is of two pixels(n=2).
Thus, we have(26)Vperson=1tan(nperson⋅θ2)=1tan(2⋅0.1172)=1tan(0.117)=488.9.This influences all the maximal distances of
perception of the person.Table1 lists the maximal distances of
perception of our environment. We can see for example that the maximal distance
of perception that a person has of a truck is 1000.Table 1DmaxPersonTruckEagle-eyedPerson (P)5001000500Truck (T)5001000500Eagle-eyed (EE)100020001000


#### 6.2.2. Area of Interest Management

By using the
rules of translation defined above, we defined the radiuses of the areas of
interest for our avatars in Table2.Table 2AvatarPersonTruckEagle-eyedAOI100010002000


#### 6.2.3. Spatial Model of Interaction

The system of
inequalities related to the spatial model of interaction was solved using a
solver which gave the results listed in Table3.Table 3AvatarPersonTruckEagle-eyedAura25010001000


#### 6.2.4. Effect Management

Table4 shows the optimal solution of the corresponding system of inequalities.Table 4AvatarPersonTruckEagle-eyedViewing zone2502501000Effect zone2501000250


### 6.3. Results

#### 6.3.1. The Impact of Filtering

Figure6 shows
the rate of messages sent by the server with and without filtering. We notice
that all the filtering techniques succeeded in reducing the rate of outgoing
messages. This pushes further the bottleneck on the server that is due to the
cost of sending messages when there is no filtering used. However, filtering
techniques postpone the bottleneck but do not eliminate it. The bottleneck is
related to the load of filtering that is equivalent in all the filtering
techniques (Figure 7).Figure 6
Network
bandwidth with and without filtering.Figure 7
Server's load
with and without filtering.We should note that we use a Gigabit network. If the
network had a narrower bandwidth, the bottleneck without filtering would take
place a lot sooner because of the network load and not the server load.


#### 6.3.2. Evaluation of Perception-Based Filtering

Figure8 compares the rate of messages sent by the
server with the four filtering techniques. We can notice that the
perception-based technique presents the lowest rate of sent messages. This
exact filtering performed by our technique allows the server to use less upload
bandwidth and makes users receive fewer messages. This makes the application
less expensive and more interactive.Figure 8
Sent messages.


#### 6.3.3. Analysis

We have seen that perception-based filtering achieves
better results than the other filtering techniques. This is due to the fact
that perception-based filtering performs an exact filtering and delivers to
each user only data that he is able to perceive while others do not.(i)
The area of interest management does not allow
avatars to express their manifestations. For these reasons, the AOI of an avatar
depends on all the existing avatars. Therefore, if we have an important avatar
that is seen from a long distance, the AOIs of all the avatars should be large
enough to cover this avatar when it is distant. Thus, these AOIs will cover
small and distant avatars that should not be seen.(ii)
The spatial model of interaction combines the
ability to see and the ability to be seen within the aura. This prevents
avatars from establishing asymetrical relations. Therefore, an important avatar
which is seen by everyone will be forced to see everyone.(iii)
Effect management does not suffer from the
shortcomings of the previous techniques. That is why it offers a better rate of
filtering than both of them. However, it still has an excessive rate of message
exchange due to the sizes of effect and viewing zones which depend on each
other because of the system of inequalities.Figure9 gives a concrete example of the inexact
filtering.Figure 9
Dmax translation into various interest management
techniques.Let us consider the scenario of an eagle-eyed person
who is standing at a distance of 2000 away from a truck and of 1100 from a
normal person. We will study the perception of the eagle-eyed toward the two
other avatars.With perception rules, our observer can see the truck
because they are at a distance (2000) which is equal to the observer's maximal
distance of perception of the truck. However, the distance that separates him
from the other person (1100) is superior to the corresponding maximal distance
of perception (1000). Therefore, the eagle-eyed person receives the update of
the truck but not that of the other person.With area of interest management, the observer's AOI
covers the truck and the person. So the observer will receive the update of the
person, while he is not supposed to see him.With the spatial model of interaction, the aura of the
observer overlaps the auras of the two other avatars. Thus, he receives the
messages of the other two avatars.With effect management, the viewing zone of the
observer overlaps the effect zones of both the truck and the person. So the
observer also receives unnecessary updates.This concrete comparison further details the causes of
the advantage of percepetion-based filtering over the other interest management
techniques.


## 6.1. Experimental Environment

We used for our
experiments 100 nodes of a cluster of Grid'5000 [15], which is a grid of
thousands of CPUs distributed at 9 sites France wide. Nodes have Rocks Linux
3.3.0 as operating systems and are connected by a Gigabit Ethernet network. The
nodes are IBM eServer 325 shipped with AMD Opteron 246 CPUs (2.0 GHz/1 MB/400 MHz), 2 GB memory, 2x Gigabit Ethernet (1 in use) and Myrinet-2000
(M3F-PCIXF-2) network cards.An experiment is a two-minute simulation with a
simulation step of 200 milliseconds. We carried out the experiments varying the
number of clients. We repeated the experiments several times and averaged the
resulting values. During an experiment, the server collects various
experimental data such as the number of exchanged messages and the server's
load.The server was always allocated a dedicated node.
However, since the number of clients in a single simulation got up to 160 (and
we only have 100 nodes available), we eventually had to run two clients on the
same node.


## 6.2. Simulation Parameters

The virtual
environment is a 20000 × 20000 square. The behavior of avatars is autonomous
following a random acceleration with a privileged direction. An avatar can be a
normal person, an eagle-eyed person (with good visual ability) or a truck. The
person and the driver of the truck have a limited viewing capacity, while the
eagle-eyed person has an enhanced viewing capacity. Furthermore, the truck has
a larger size, thus it has a stronger chance of being seen than the others.


### 6.2.1. Perception-Based Filtering

For
perception-based filtering, we consider that the field of view is equal to 120
degrees and the screen is 1024 pixels large. This gives us the angle covered by
one pixel,(22)θ=fovNbPixelsX=1201024=0.117.We consider that the eagle-eyed person is able to see
the details on the screen up to one pixel(n=1). His viewing capacity
is of(23)Veagle=1tan(neagle⋅θ2)=1tan(1⋅0.1172)=1tan(0.058)=977.8.To obtain the maximal distance of perception that the
avatar has of a person, we multiply the radius of the person with the visual
capacity of the avatar:(24)Dmax(eagle,person)=Rperson⋅Veagle=1.022⋅977.8=1000.On the other hand, the maximal distance of perception
that an eagle-eyed person has of a truck depends on the truck's bounding sphere
radius:(25)Dmax(eagle,truck)=Rtruck⋅Veagle=2.045⋅977.8=2000.The avatars with a normal viewing capacity (the person
and the driver of the truck) will see less clearly on the screen. We will
consider that their minimal threshold of perception is of two pixels(n=2).
Thus, we have(26)Vperson=1tan(nperson⋅θ2)=1tan(2⋅0.1172)=1tan(0.117)=488.9.This influences all the maximal distances of
perception of the person.Table1 lists the maximal distances of
perception of our environment. We can see for example that the maximal distance
of perception that a person has of a truck is 1000.Table 1DmaxPersonTruckEagle-eyedPerson (P)5001000500Truck (T)5001000500Eagle-eyed (EE)100020001000


### 6.2.2. Area of Interest Management

By using the
rules of translation defined above, we defined the radiuses of the areas of
interest for our avatars in Table2.Table 2AvatarPersonTruckEagle-eyedAOI100010002000


### 6.2.3. Spatial Model of Interaction

The system of
inequalities related to the spatial model of interaction was solved using a
solver which gave the results listed in Table3.Table 3AvatarPersonTruckEagle-eyedAura25010001000


### 6.2.4. Effect Management

Table4 shows the optimal solution of the corresponding system of inequalities.Table 4AvatarPersonTruckEagle-eyedViewing zone2502501000Effect zone2501000250


## 6.2.1. Perception-Based Filtering

For
perception-based filtering, we consider that the field of view is equal to 120
degrees and the screen is 1024 pixels large. This gives us the angle covered by
one pixel,(22)θ=fovNbPixelsX=1201024=0.117.We consider that the eagle-eyed person is able to see
the details on the screen up to one pixel(n=1). His viewing capacity
is of(23)Veagle=1tan(neagle⋅θ2)=1tan(1⋅0.1172)=1tan(0.058)=977.8.To obtain the maximal distance of perception that the
avatar has of a person, we multiply the radius of the person with the visual
capacity of the avatar:(24)Dmax(eagle,person)=Rperson⋅Veagle=1.022⋅977.8=1000.On the other hand, the maximal distance of perception
that an eagle-eyed person has of a truck depends on the truck's bounding sphere
radius:(25)Dmax(eagle,truck)=Rtruck⋅Veagle=2.045⋅977.8=2000.The avatars with a normal viewing capacity (the person
and the driver of the truck) will see less clearly on the screen. We will
consider that their minimal threshold of perception is of two pixels(n=2).
Thus, we have(26)Vperson=1tan(nperson⋅θ2)=1tan(2⋅0.1172)=1tan(0.117)=488.9.This influences all the maximal distances of
perception of the person.Table1 lists the maximal distances of
perception of our environment. We can see for example that the maximal distance
of perception that a person has of a truck is 1000.Table 1DmaxPersonTruckEagle-eyedPerson (P)5001000500Truck (T)5001000500Eagle-eyed (EE)100020001000


## 6.2.2. Area of Interest Management

By using the
rules of translation defined above, we defined the radiuses of the areas of
interest for our avatars in Table2.Table 2AvatarPersonTruckEagle-eyedAOI100010002000


## 6.2.3. Spatial Model of Interaction

The system of
inequalities related to the spatial model of interaction was solved using a
solver which gave the results listed in Table3.Table 3AvatarPersonTruckEagle-eyedAura25010001000


## 6.2.4. Effect Management

Table4 shows the optimal solution of the corresponding system of inequalities.Table 4AvatarPersonTruckEagle-eyedViewing zone2502501000Effect zone2501000250


## 6.3. Results

### 6.3.1. The Impact of Filtering

Figure6 shows
the rate of messages sent by the server with and without filtering. We notice
that all the filtering techniques succeeded in reducing the rate of outgoing
messages. This pushes further the bottleneck on the server that is due to the
cost of sending messages when there is no filtering used. However, filtering
techniques postpone the bottleneck but do not eliminate it. The bottleneck is
related to the load of filtering that is equivalent in all the filtering
techniques (Figure 7).Figure 6
Network
bandwidth with and without filtering.Figure 7
Server's load
with and without filtering.We should note that we use a Gigabit network. If the
network had a narrower bandwidth, the bottleneck without filtering would take
place a lot sooner because of the network load and not the server load.


### 6.3.2. Evaluation of Perception-Based Filtering

Figure8 compares the rate of messages sent by the
server with the four filtering techniques. We can notice that the
perception-based technique presents the lowest rate of sent messages. This
exact filtering performed by our technique allows the server to use less upload
bandwidth and makes users receive fewer messages. This makes the application
less expensive and more interactive.Figure 8
Sent messages.


### 6.3.3. Analysis

We have seen that perception-based filtering achieves
better results than the other filtering techniques. This is due to the fact
that perception-based filtering performs an exact filtering and delivers to
each user only data that he is able to perceive while others do not.(i)
The area of interest management does not allow
avatars to express their manifestations. For these reasons, the AOI of an avatar
depends on all the existing avatars. Therefore, if we have an important avatar
that is seen from a long distance, the AOIs of all the avatars should be large
enough to cover this avatar when it is distant. Thus, these AOIs will cover
small and distant avatars that should not be seen.(ii)
The spatial model of interaction combines the
ability to see and the ability to be seen within the aura. This prevents
avatars from establishing asymetrical relations. Therefore, an important avatar
which is seen by everyone will be forced to see everyone.(iii)
Effect management does not suffer from the
shortcomings of the previous techniques. That is why it offers a better rate of
filtering than both of them. However, it still has an excessive rate of message
exchange due to the sizes of effect and viewing zones which depend on each
other because of the system of inequalities.Figure9 gives a concrete example of the inexact
filtering.Figure 9
Dmax translation into various interest management
techniques.Let us consider the scenario of an eagle-eyed person
who is standing at a distance of 2000 away from a truck and of 1100 from a
normal person. We will study the perception of the eagle-eyed toward the two
other avatars.With perception rules, our observer can see the truck
because they are at a distance (2000) which is equal to the observer's maximal
distance of perception of the truck. However, the distance that separates him
from the other person (1100) is superior to the corresponding maximal distance
of perception (1000). Therefore, the eagle-eyed person receives the update of
the truck but not that of the other person.With area of interest management, the observer's AOI
covers the truck and the person. So the observer will receive the update of the
person, while he is not supposed to see him.With the spatial model of interaction, the aura of the
observer overlaps the auras of the two other avatars. Thus, he receives the
messages of the other two avatars.With effect management, the viewing zone of the
observer overlaps the effect zones of both the truck and the person. So the
observer also receives unnecessary updates.This concrete comparison further details the causes of
the advantage of percepetion-based filtering over the other interest management
techniques.


## 6.3.1. The Impact of Filtering

Figure6 shows
the rate of messages sent by the server with and without filtering. We notice
that all the filtering techniques succeeded in reducing the rate of outgoing
messages. This pushes further the bottleneck on the server that is due to the
cost of sending messages when there is no filtering used. However, filtering
techniques postpone the bottleneck but do not eliminate it. The bottleneck is
related to the load of filtering that is equivalent in all the filtering
techniques (Figure 7).Figure 6
Network
bandwidth with and without filtering.Figure 7
Server's load
with and without filtering.We should note that we use a Gigabit network. If the
network had a narrower bandwidth, the bottleneck without filtering would take
place a lot sooner because of the network load and not the server load.


## 6.3.2. Evaluation of Perception-Based Filtering

Figure8 compares the rate of messages sent by the
server with the four filtering techniques. We can notice that the
perception-based technique presents the lowest rate of sent messages. This
exact filtering performed by our technique allows the server to use less upload
bandwidth and makes users receive fewer messages. This makes the application
less expensive and more interactive.Figure 8
Sent messages.


## 6.3.3. Analysis

We have seen that perception-based filtering achieves
better results than the other filtering techniques. This is due to the fact
that perception-based filtering performs an exact filtering and delivers to
each user only data that he is able to perceive while others do not.(i)
The area of interest management does not allow
avatars to express their manifestations. For these reasons, the AOI of an avatar
depends on all the existing avatars. Therefore, if we have an important avatar
that is seen from a long distance, the AOIs of all the avatars should be large
enough to cover this avatar when it is distant. Thus, these AOIs will cover
small and distant avatars that should not be seen.(ii)
The spatial model of interaction combines the
ability to see and the ability to be seen within the aura. This prevents
avatars from establishing asymetrical relations. Therefore, an important avatar
which is seen by everyone will be forced to see everyone.(iii)
Effect management does not suffer from the
shortcomings of the previous techniques. That is why it offers a better rate of
filtering than both of them. However, it still has an excessive rate of message
exchange due to the sizes of effect and viewing zones which depend on each
other because of the system of inequalities.Figure9 gives a concrete example of the inexact
filtering.Figure 9
Dmax translation into various interest management
techniques.Let us consider the scenario of an eagle-eyed person
who is standing at a distance of 2000 away from a truck and of 1100 from a
normal person. We will study the perception of the eagle-eyed toward the two
other avatars.With perception rules, our observer can see the truck
because they are at a distance (2000) which is equal to the observer's maximal
distance of perception of the truck. However, the distance that separates him
from the other person (1100) is superior to the corresponding maximal distance
of perception (1000). Therefore, the eagle-eyed person receives the update of
the truck but not that of the other person.With area of interest management, the observer's AOI
covers the truck and the person. So the observer will receive the update of the
person, while he is not supposed to see him.With the spatial model of interaction, the aura of the
observer overlaps the auras of the two other avatars. Thus, he receives the
messages of the other two avatars.With effect management, the viewing zone of the
observer overlaps the effect zones of both the truck and the person. So the
observer also receives unnecessary updates.This concrete comparison further details the causes of
the advantage of percepetion-based filtering over the other interest management
techniques.


## 7. Conclusions and Future Work

We have presented the perception-based filtering
technique. This technique will help developers determine their avatars'
perceptual interests in a precise way. We have also presented a translation of
perception rules into interest management techniques which define the interests
of players by using zones. We have then compared the performance of
perception-based filtering with other techniques and we found that our
technique further reduces the amount of exchanged messages. We have also
described the reasons why our technique offers such advantages.Perception-based filtering presents an additional
advantage related to the dynamic change of interests. In fact, perception-based
filtering allows avatars to change their abilities to perceive or be perceived
without having to change a lot of simulation parameters. Furthermore, any
change of ability of one avatar with the other techniques will induce a new
system of inequalities that should be solved to give a new set of filtering
parameters.However, perception-based filtering only expresses
perceptual factors while the other techniques allow to express other
characteristics in addition to perception (function, behaviour, etc.). This is
why we intend to extend our research to the auditive and functional domains.



---

*Source: 243107-2008-05-05.xml*