Introduction

Mixed Reality faces a problem. To cover the whole planet with all its inhabitants, we have to overcome a scalability issue.

The simplest attempts to connect all users virtually is to “host” everyone on the same server. But at some point the server runs out of resources. The user limit is very low. In gaming, a server can handle at most a few thousand users. So we need to add more servers - we need a distributed system.

Scaling

In gaming, there are several ways to deal with scalability. One solution is shards, used by games such as World of Warcraft. Shards distribute users over many copies of a world, with a server hosting one shard. This is great because it allows many play at the same time, but groups of users exist in separate worlds. If they aren’t in the same shard they aren’t playing together.

An alternative approach is to divide worlds into zones, each zone hosted by a server. This solution was successfully implemented in Second Life. However, the approach has its drawbacks: people want to socialize and concentrate in crowds. Many zones remain empty while a few become overcrowded. The overcrowded zones face the same scalability issues, and the empty zones are under-utilized.

The problem, we think, must be re-examined. With Mixed Reality, handling worlds and handling the digital avatars should be addressed separately. Google Earth for instance is a sort of empty virtual world, which can be used to host many users.

Within virtual worlds users perform many actions, such as moving and dancing. It would be too costly to send these events to everyone. The server should compute who can see each avatar and send their actions only to their neighbours. But as avatars move their positional configuration changes. This computation can be costly: the server needs to quickly calculate neighbourhoods from a haystack of moving avatars. The bottleneck resides in the avatar movements from one position to another. In this context we came up with a new solution where servers are allocated to groups of users based on their geographic proximity.

Mapping users into neighbourhoods

In a virtual world users are concerned with what is happening nearby (just like the real world). So for each avatar there is a neighbouring zone around its position and they must be notified of all the events produced by those located in their neighbourhood.

Neighbourhoods must also be symmetrical - you must see your neighbour, and she must see you. Both of you should be able to interact with environmental objects.

In a crowded space you pay attention to people in the immediate proximity. If you are in an open space you can see someone far away.

So given a set of avatar positions, what is a good way to connect them?

We know that connecting user only to their nearest peers is the most efficient method. Moreover, any direction you look in, you should see who is the closest. Fortunately, Delaunay triangulation is a great method to solve these problems. Delaunay Triangulation is a classical computational geometry tool, widely used in computer graphics. This is also the basic data structure of exaQuark, the platform we have designed to scale virtual worlds.

An important feature of this approach is that it preserves locality: moving an object produces only local changes and only neighbours are concerned with the event.

Scaling predictably

In Wold of Warcraft they succeed to balance the load by evenly distributing the users among realms. In Second Life the problem is that the zones do not match the distribution of the avatars.

Ideally, each zone should handle the same load, so the zones should not be shaped by the geography. They should be shaped by avatar distribution. And because avatars move, we can expect the distribution to change in time; this is why we need zones that are shaped dynamically.

In exaQuark, a zone is the space covering a group of avatars, selected by proximity. Each zone handles roughly the same number of avatars, ensuring load balancing.

Each zone handled by one server, never exceeding the server’s capacity. Because each zone communicates only with its neighbouring zones to maintain the frontier, we can add as many servers as we need. The more people are connecting, the more servers we add.

Using exaQuark, we are confident that virtual and hybrid worlds with millions will be common in a near future.