---

Translated from "fr dossier 2002 / Projet NeL - 3D - Génération de grandes étendues de terrain" — the Ligo brick system for large-scale terrain production. {.is-info}

Nevrax specializes in the development of massively multiplayer online video games. These games allow several thousand players to confront each other in the same virtual universe. This universe is persistent, meaning it is always possible to connect to it and that the universe is in perpetual evolution. This universe, composed of large expanses of terrain and cities, must be large enough to contain the entire game.

In 2001, Nevrax developed an innovative technology for representing terrain in three dimensions.

Terrain created with the technology developed by Nevrax.

The goal of this project is to study a technology for producing large expanses of this type of terrain.

The visual quality of virtual worlds is in perpetual increase and is the subject of significant research by companies developing these universes.

The reasons for this high level of innovation are:

• The increasing quality of hardware technologies available to video game technology developers (computing power of computers and consoles, display speed of processors equipping computer graphics cards).
• An ever-increasing level of quality demanded by players regarding realism and quality of three-dimensional graphics, immersion in the game universe, performance and complexity of video games.
• A very strong competitive environment on an international scale.

The terrain surface of massively multiplayer online games is no exception to these rules. The goal of this research project is to enable Nevrax to reach a technological level superior to the competition in this area, in order to meet user quality demands and allow the game it develops to reach a new level of complexity and interest.

In massively multiplayer online games, the surface of the world the player can visit is enormous. Indeed, these games allow several thousand people to play in the same universe at the same time. The game must remain interesting for several months and for this, it is important to continuously offer vast and unexplored locations. The main technical challenge of this project is to research the technical solutions for creating a large game surface.

Since game production is limited in time, it is necessary to study a solution for generating the large expanses of terrain needed quickly and efficiently.

The 3D terrain representation is part of the image of the universe given to the player by the software. The variety of locations allows the player to orient themselves correctly in the game. Another technical challenge is to research technological solutions for generating terrain of good graphical quality while ensuring that the scenery is not too repetitive, but rather provides varied and identifiable locations.

A massively multiplayer game also includes cities. It is necessary for the solution studied to allow easy placement of cities and villages in the terrain.

A commonly used method is to represent the terrain using a two-dimensional isometric view. The terrain is divided into equally sized cells.

The terrain editor of the game Starcraft.

A set of terrain bricks is used to dress the grid. The bricks are arranged in sets, like 'plain', 'plateau', 'marsh', etc.

Brick set selector in Starcraft.

Once a brick set has been chosen, it is possible to 'paint' the terrain with the mouse. Each terrain cell is assigned a randomly chosen brick from the previously selected set. When the user clicks on the terrain grid, a brick is placed. If they move the mouse, bricks are placed along the path drawn by the mouse. A uniform expanse is obtained very quickly.

The user can then change brick sets and continue painting. The software automatically handles the transitions between the two brick sets. The brick sets are used to differentiate the heights of the game plateau. A large terrain is thus obtained, varied in form, by reusing a maximum of graphical material.

A finalized Starcraft terrain.

Creating the base bricks is not trivial. Each brick is a two-dimensional image. Bricks have a unit size but can generally measure a multiple of that size.

Bricks are classified into sets. For each set, a series of generic bricks is generally drawn to serve as a background layer. In a second step, more specific bricks are added with details and objects.

Different natures of bricks in Starcraft.

Two bricks from the same set must be able to be placed side by side. Certain graphical constraints must be respected for the bricks to join correctly.

To be able to transition from brick set A to brick set B, it is necessary to build a specific A→B transition brick set. There are several ways to build this transition set.

The simplest method consists of building three types of transition bricks. With these three bricks, it is possible to transition from brick set A to brick set B in all circumstances. The disadvantage of this method is that it produces terrain with rounded and monotonous shapes.

The three basic transition bricks.

The three basic bricks placed on terrain.

A more sophisticated method uses nine types of transitions. Instead of the border between brick sets being at 50% of the edge, it can now be at 33% or 66%. The terrain placement software will randomly choose 33% or 66% during placement. This triples the number of bricks needed to solve all cases, but terrain shape gains in diversity.

The nine basic bricks placed on terrain.

The nine basic bricks placed on terrain.

This method has been successfully implemented in many games like Warcraft, Starcraft, Diablo, and also Ultima Online for online games. It allows building large game surfaces in record time. Unfortunately, this method generates two-dimensional terrain. Nevrax is looking for a method adapted to its three-dimensional terrain display technology.

Warcraft II.

Starcraft.

Diablo 2.

Ultima Online.

Another popular method for modeling large terrain surfaces is the displacement texture. This method consists of drawing a large image whose pixel color indicates the desired terrain height. Modeling a landscape amounts to drawing its topology from above.

The intensity of a point in the image affects the height of the terrain.

The terrain corresponding to the image above.

It is generally possible to specify the terrain texture to use based on position or altitude (grass, snow, desert, sea).

Editing the texture based on altitude.

In the game, the display software generates a polygon grid around the player and deforms it in height using the displacement texture. The grid is adaptively subdivided at each movement using an algorithm of the type developed by Hoppe [Hoppe1].

Example of a deformed grid.

It is also possible to randomly generate the displacement texture using fractal algorithms — the landscapes are then quasi-infinite in size, but terrain control becomes very difficult, which is problematic for a game since it is necessary to master the game space to place interactive elements.

Fractal terrain.

It is quick to build large amounts of three-dimensional terrain using displacement textures. Often limited to valleys and hills, the generated terrain is generally quite monotonous. Controlling its shape is more difficult than using a brick system. Since hill slopes are difficult to control, it is difficult to generate good quality collisions on the terrain, which can be a significant constraint on game rules as the player is free to go wherever they want.

This technique is used in many games, like Star Wars Galaxies and EverQuest 2.

Star Wars Galaxies.

EverQuest 2.

Bibliography:

• [Hoppe1] Hoppe, H. "Smooth View-dependent Level-of-detail Control and its application to terrain rendering"
• [Duchaineau] Duchaineau, M. et al. "ROAMing Terrain: Real-time Optimally Adapting Meshes". October 19, 1997
• [Lee] Lee, A. "Displaced Subdivision Surfaces" Computer Graphics Proceedings 2000
• [Bézier] Foley, van Dam. "Computer Graphics", second Edition. ISBN 0-201-84840-6

Objectives:

• The solution must allow building large expanses of terrain
• The solution must allow fast editing and precise terrain control
• The solution must allow obtaining varied terrain giving the player the ability to orient themselves
• The solution must propose a method for placing cities and villages

Constraints:

• The solution must use the three-dimensional terrain display technology developed by Nevrax
• The method must allow easy control of terrain collisions

No existing terrain generation solution achieves these objectives while respecting the constraints. Research work is therefore necessary to find an adapted solution.

The solution will be oriented towards a system based on three-dimensional terrain bricks. We then face many problems:

Bricks in the same set must be geometrically compatible.

The textures at the edges of bricks must be compatible to avoid visible color discontinuities between two bricks.

Example of two 3D bricks with color discontinuities.

Example of two 3D bricks without color discontinuities.

The first problem to solve is therefore finding a way to build bricks with such color constraints in three dimensions.

Building transition bricks between two brick sets

Once placed side by side, the three-dimensional edges composing the bricks must have exactly the same structure so they can be joined without visible holes.

Example of 3D transition bricks with a bad geometric join.

Example of 3D transition bricks with a good geometric join.

As in two-dimensional isometric terrain systems using bricks, it must be possible to build transition brick sets between two brick sets.

The second problem to solve is finding a method for building transition bricks respecting the geometric constraints in three dimensions.

Assembling bricks on the terrain

Once the bricks are built, they must be placed on terrain. It is not possible to display the entire terrain at once — the display software only allows displaying part of it. However, it is necessary to have an overview of the terrain while building it.

Furthermore, it must be possible to modify each brick as desired to have total control over the terrain shape.

The third problem to solve is finding a way to assemble bricks on the terrain while keeping an overview.

The following research tasks were performed:

• Development of a 3D brick editor
• Development of a transition brick editor
• Development of a terrain editor for placing prefabricated bricks

Develop a brick editor respecting the geometric constraints in three dimensions. In two-dimensional isometric brick terrains, the brick editor is just a traditional drawing program. Here, the tool must be in a three-dimensional editor.

To create a brick set, a template must first be modeled for the bricks of this set. The template will then be used to validate the color constraints.

A new template.

The user can display four ghost copies of the template that are placed around the original template. The ghost copies are references to the template, meaning they always have the same structure as the original template.

A template with ghost copies.

The user then only needs to modify the template's color. Automatically, the references update and show the user the constraints to respect.

A brick with ghost copies in the painting tool.

The user can then create a first brick. The tool generates the brick by copying the brick set template. The user can modify it as desired. They can also paint it while checking with the template's ghost copies that the color constraints are respected.

Example of a finalized brick.

This method gives good results. It is relatively easy to create new zones. It is very simple to duplicate a zone and specialize it. The graphical constraints are easy to respect because the tool guides the user throughout the brick creation process.

This first task allowed us to model the basic bricks. Now the transition bricks need to be modeled.

This task occupied one programmer full-time for four weeks.

Develop a brick editor respecting the three-dimensional geometric constraints for transitions between two brick sets. In two-dimensional isometric brick terrains, the brick editor is just a traditional drawing program. Here, the tool must be in a three-dimensional editor. The geometric constraint is very strong here because it is not just a matter of texture alignment but also geometric alignment.

To create a transition brick set between two brick sets, a template must first be modeled for the nine bricks of this set. The templates will then be used to validate the color and geometry constraints. The tool generates nine basic zones.

Nine new transition bricks.

The user can quickly display one of the transition bricks, then display the four ghost copies of the respective templates that are placed around the selected brick's template.

Transition brick with ghost zones in initial position.

The user must first model the transition edges. To do this, they move the points of the zone's grid. The templates placed around update automatically. The user can easily verify that the geometry respects the constraints.

Several steps in the creation of a transition brick.

The finalized transition brick.

As in the previous task, the user can modify the zone's color.

The transition brick with two ghost copies in the painting tool.

The user can then create a first brick. The tool generates the brick by copying the brick set template. The user can modify it as desired. They can also paint it while checking with the template's ghost copies that the color constraints are respected.

A second "traversable" version of a transition brick.

This method gives good results. It is relatively easy to create new transition zones. It is very simple to duplicate a zone and specialize it. The graphical constraints are easy to respect because the tool guides the user throughout the brick creation process.

This second task allowed us to model the transition bricks between two brick sets. Now that all bricks are modeled, we will focus on the terrain editor.

This task occupied one programmer full-time for five weeks.

In two-dimensional isometric terrain editors, bricks are just small images. The editing software handles small amounts of graphical resources. In the case of the three-dimensional terrain editor needed here, the graphical resources, composed of thousands of polygons, are heavy. It is not possible to display the entire three-dimensional terrain — the display software only allows displaying part of it.

It is also necessary to find a method for having better control over the terrain shape than in traditional brick terrain editors.

All terrain bricks are converted to images. It is these images that will be manipulated in the editor, not the three-dimensional terrain.

Several bricks seen from above in two dimensions.

Each brick is associated with a brick set name like 'set = plateau', 'set = canyon', 'set = valley' but also other parameters like 'generic = true/false', 'village = true/false', etc. The user selects the bricks they want to use by composing these expressions in a logical relation.

The brick selector.

Then, when painting, bricks are randomly chosen from the subset selected.

Several bricks placed randomly.

The user can also select the border type (33% or 66%) for each transition brick border using a handle system.

Once the terrain is modeled in the two-dimensional editor, a tool generates the three-dimensional version displayable by the game software.

This method was retained for production although it suffers from some drawbacks. The main problem comes from the fact that editing is done in two dimensions and it is difficult to properly perceive the overall terrain shape with a top-down view.

This task allowed us to obtain the tool for building the large expanses of terrain needed for the game developed by Nevrax, Ryzom.

This task occupied one programmer full-time for eight weeks.

The researched solution allows efficiently building large expanses of three-dimensional terrain using a brick system.

Editing gives as fine control as possible over the terrain shape. Transition bricks are easily controllable unlike existing editors. It is thus possible to choose between traversable or non-traversable transitions to control collisions.

It is simple to copy and specialize an already existing brick. This allows building unique bricks that give the player landmarks and allow them to orient themselves in the world.

It is possible to build large bricks that can contain a city or village and place them with a single mouse click in the terrain editor.

The solution generates terrain compatible with the display technology previously developed by Nevrax.