---

Translated from "fr dossier 2002 / Projet NeL - 3D - Visualisation interieur REVIEWED" and "fr dossier 2001 / projet_3d_interieur_reviewed". Both versions are identical. {.is-info}

Nevrax develops Ryzom, a 3D interactive MMORPG with a strong desire for immersion. The first-person view was chosen because it allows a stronger involvement and immersion in the character the player embodies. The world of Ryzom is very vast, composed of plains and valleys, plateaus and steep cliffs, but also more confined places where players like to gather to exchange equipment and tell each other the fabulous stories they have experienced during their journeys.

To display such places, one could choose to handle the entire scene. This seems reasonable in an open space where one can see all players and scenery elements at all times. But the time taken to display a 3D scene grows in proportion to the number of objects present in the scene. Given that the NeL project, of which this is a part, is a real-time 3D display module, it is important to find a fast way to eliminate objects that will not be seen by the user, while maintaining great flexibility in terms of object placement.

The domain of application of this module is the optimal visualization of enclosed environments. Indeed, an enclosed environment is managed differently from a less confined one (see the terrain rendering postmortem on this subject). It enables us to display everything from an entire city down to a simple isolated house, and all interiors of mobile buildings (complex means of transport such as boats and hot air balloons).

While current games do not offer complex cities and are generally divided into two categories — indoor games and outdoor games — our vision is to adapt the algorithm type to the situation encountered.

The best known state of the art for quickly displaying an interior is the BSP [1] (Binary Space Partitioning), initiated by J. Carmack in Quake, which coupled with PVS (Potentially Visible Set) allows very fast selection of which rooms to display.

Advantages:

• Very fast display of static scenery
• All rooms are already sorted
• No designer intervention needed beyond creating the rooms

However, the disadvantages are numerous:

• Difficulty placing dynamic objects coherently in the tree for display without using a Z-buffer
• All pieces composing the BSP must be static
• Instancing is difficult (if a building is composed of 100 identical rooms, the BSP requires 100 copies of the same room in memory)
• Very long PVS precomputation time

Top-down visualization of a binary space partitioning.

There is another spatial partitioning frequently used: the octree.

Unlike a binary partitioning, the octree is a partitioning by cubes aligned most often on the reference axes. The generated tree is therefore no longer binary but has 8 branches at each node. The main advantage over BSP is that computation time is greatly reduced. The RenderWare [2] library, a competitor to NeL, uses an octree system for its static spatial partitioning and visibility tests. Having seen the discomfort of this method, the library was supplemented with a module called dPVS, which is much more performant and can handle the world in a more dynamic way.

Visualization of the leaves of an octree.

Finally, a technique that operates not in object space but in screen space was beginning to emerge: the Hierarchical Z-buffer. By displaying objects from front to back (from the camera), automatic visibility detection is performed (thanks to the Z-buffer). The advantages are numerous:

• No manual intervention
• No precomputation
• Instancing is possible
• Everything can be dynamic

However, the disadvantages are prohibitive:

• Slowness (at the time, hardware did not accelerate Z-buffer tests), increasing with image resolution.
• Objects must still be processed even if they are not visible (or this technique must be coupled with another object-space elimination technique).
• An image-space algorithm is well suited for visibility testing between camera and objects, but not as much for object-to-object interaction. This means that the image must be computed to determine the visibility interaction between two objects, which is very expensive in computation time. An object-space algorithm is more efficient at determining visibility between objects.

Visualization of the values contained in a hierarchical Z-buffer.

After reviewing these different techniques, it seemed important to us to design a new technique that would allow both ease and flexibility of use, fully dynamic environment management, and high computation and display speed.

• [1] Foley, van Dam, Feiner, Hughes, "Computer Graphics", principles and practice, The systems programming series, Second Edition in C, 1995, pp 675-680.
• [2] RenderWare: http://www.renderware.com/
• ACM Siggraph, "Computer Graphics", Proceedings, 2000, Conservative Visibility Preprocessing Using Extended Projections pp 229-238.

The objectives of the interior visibility system are first and foremost execution speed. Determining whether objects in the scene are present on screen as quickly as possible is an essential factor in a real-time 3D display engine. The second objective is flexibility: instancing and dynamic objects must be natively managed by the system.

The first question that arose was: will this system integrate with the one already in place for outdoor management? Indeed, it must be possible to switch from one visibility system to the other in a completely transparent way for the user. This required us to revisit our data flow design within the engine on several occasions.

The second question was which base technique to choose. If we want truly dynamic object management — for example, if we want to move entire buildings (houses on water, boats, etc.) — we need a system that handles both individual objects and groups of objects.

The overall problems were the determination of the algorithm type and managing to predict the extended behavior of this algorithm. Indeed, the algorithms used only partially met our expectations. We therefore chose as an approach to extend an already existing algorithm to suit our needs. Knowing that the literature on the subject is abundant, we selected algorithms that favored scene dynamism over those that were perfectly accurate but only applied to static structures with some dynamic objects.

1. Determination of the base algorithm type
2. Classic cluster system
3. Hierarchical cluster system
4. Dynamic cluster system

As seen previously, none of the currently implemented visibility algorithms allows fully dynamic management with the possibility of instancing, all at a modest CPU cost. We therefore had to start by choosing the algorithm that would serve as our starting point. After a thorough study of a large number of algorithms, all of which favored one representation mode or another, our choice settled on two base algorithms that could be improved for our needs: a Z-buffer testing system coupled with a hierarchical bounding box system, or a cluster/portal system to which we would add dynamism and hierarchy.

The evaluation of the first method was based on the ability to manage the Z-buffer at high speed, as this is the main weakness of the Z-buffer testing method: a large number of memory accesses are required for a single test. Sorting objects by increasing or decreasing distance can be done in O(m*n) with m fixed (generally 4). It is therefore access to this memory that is most critical. Unfortunately, the tests we conducted clearly demonstrated that this method was not usable for real time. We therefore did not pursue this method further. As long as graphics cards do not implement this technique natively, it cannot be considered as part of real-time hidden surface removal techniques.

The second method, a cluster/portal system, is already known to work in many games (such as ODT by Psygnosis, for example). Generation is done automatically based on the terrain. The problem we faced is that here the terrain does not align to any logical grid. The generation of these accelerators must therefore be manual — the people who draw 3D objects must also think about placing visibility accelerators. This is a problem that persists throughout the project, yet it allows optimization only where necessary, depending on the number of faces and objects to display. In its current state of the art, this method does not support instancing or dynamic scenery objects. It is, however, well suited to managing dynamic game objects.

This method was therefore chosen as the foundation for researching a completely flexible solution. Upon reflection, we did not foresee any problems with extending this method — though we could not predict everything.

The first goal was to have a classic cluster/portal system as one would expect to find in any game. This was achieved in a straightforward manner with the usual constraints.

A cluster/portal system is composed of two accelerator elements placed manually by 3D model designers. A cluster is a convex polyhedron surrounding a region of uniform visibility. In a house, it is a volume surrounding a room, for example. A portal is a convex polygon that joins two clusters. This polygon is also placed manually, as clusters are drawn roughly to encompass the player's movement space, while portals provide the precise visibility detection elements. In a room, a portal is a door or window linking the room space to an exterior space. A cluster therefore has several portals, and a portal is always shared by exactly 2 clusters — no more, no less. The basic cluster system can be viewed as a graph, with clusters as vertices and portals as edges.

The development method was to implement the basic principles within the flexible 3D engine architecture. This step was essential to begin the actual research.

Research began with the hierarchization of cluster systems. There can be multiple levels of detail that one does not necessarily want to traverse when at a given level. The most striking example is Ryzom itself: in the world there are multiple territories, in each territory there are multiple cities, and in those cities there are apartments. The basic idea is that when in a territory, one does not want to manage what happens in an apartment, nor in a city if the city is not visible.

The problem that arose is that a tree of graphs is neither easy to conceive, nor to traverse, nor to visualize. But after some unsuccessful attempts — due to the fact that hierarchical links were not homogeneous with links between clusters (a hierarchical link translates to a direct cluster-to-cluster link, whereas a link in a cluster system is a cluster-portal-cluster link) — we arrived at a hierarchical system. That was a first achievement. But suddenly, we had to handle an unforeseen case: the Fyros city.

The Fyros city is a city that is "open" to the exterior. That is, from inside you can see the territory, but from the territory you cannot see the interior of the city. The designers did not want to place portals on every cluster to see above the city — indeed, buildings protrude freely. The cluster system, which needed to be in an enclosed space to function correctly, had just suffered its first setback. We therefore decided to make the hierarchical link controllable at the level of every cluster. Each cluster can declare whether or not it is linked to its parent (its parent being a cluster system that encompasses it, and more specifically a cluster of the parent system). By controlling membership in a higher-level system containing the territory and the buildings, we had our correct and atypical visibility system. Atypical because it possessed cross-hierarchical interconnections. From the territory, one could see directly into the interior of a city building. Until then, we had only ever seen a purely top-down hierarchical system (territory > city > building > interior). In fact, this allowed us to create a graph of graphs. Each vertex being a cluster system, and the edges being "hierarchical" inter-system links.

We had reached an important point: no longer viewing a cluster system as a single entity that would control the visibility of an entire world, but as an atom of a more global system that would link these systems together through spatial logic. This was a great step forward. Now we needed to animate all of this.

Research continued with the management of dynamic objects within cluster systems. Objects can be instructed to evolve within a single cluster system or, conversely, to move across the system hierarchy. This allows interaction between the visibility module and the collision detection module. Indeed, clusters must be quick to produce so that the designer truly concentrates on the building's shape. It is therefore normal for clusters to be made roughly. The problem is that if a cluster extends beyond a building, when the user is apparently outside the building but within an interior cluster, the exterior will be removed in favor of interior display, creating a visual inconsistency. It is therefore logical to let the collision system — which is, in contrast, very precise — determine whether the user should be tested against the exterior or interior cluster system. Of course, automatic cluster system detection can also be chosen. In that case, detection attempts to start with the most recently added clusters (to account for possible graph loops).

With this done, dynamic objects could move within the system. It remained to be able to move the system itself and to allow instancing. The translation and rotation of an entire cluster system raised the problem of choosing axis-aligned bounding boxes for pre-sorting cluster systems and individual clusters. Furthermore, a moving cluster system must be able to notify its potential parents so they can update their position within their own systems. It is at this cost that we could have boats, caravans, and other leviathans.

It is worth noting that development did not proceed linearly and that difficulties encountered during research stimulated new approaches. The system for moving entire "buildings" is something very rare in interactive applications, as it often requires significant resources. With our method, since the building in its entirety is only visualized by the user when they enter it (or when it is within viewing range), we can easily envision means of transport that rival our imagination.

The progress achieved is therefore significant. We brought flexibility of movement to the entire visibility system, enabling effects rarely seen before — the movement of objects through the system and the movement of the system as a whole. This enables a global visibility system across the entire 3D world, interconnected with the outdoor terrain visibility system, and allows reuse of buildings and their associated accelerators.

Exterior (textured).

Fyros city displayed without a visibility system.

Display with object elimination thanks to the cluster system.

Worked example: the Larva.

Exterior (textured).

Exterior (wireframe mode).

Interior (textured).

Interior (wireframe mode).

Interior + Exterior (what would be seen without the dynamic cluster system).

Interior and exterior without visibility testing in wireframe mode.

The cluster system (from another angle).

The cluster system in wireframe mode (portals in red).

The cluster system in wireframe mode + exterior shell.