Translated from "fr dossier 2001 / projet_3d_personnage". {.is-info}

The goal of this project is to research solutions for improving the three-dimensional display technology for characters in massively multiplayer online role-playing games. This technical domain has always received particular attention in games of this type.

Economic stakes

The visual quality of video games is in perpetual increase and is the subject of significant research by companies developing entertainment software.

The reasons for this high level of innovation are:

• The increasing quality of hardware technologies available to developers of entertainment software (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 3D graphics, immersion in the game universe, performance of entertainment software, and complexity of games.
• A very strong competitive environment on an international scale.

The representation of characters in three dimensions in MMORPGs 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 domain, in order to meet user quality demands and allow the game it develops to reach a new level of complexity and interest.

Among the most serious competitors in the MMORPG domain, we present the games Dark Age of Camelot and Everquest, the two most significant MMORPGs in terms of the state of the art for three-dimensional character representation.

Many characters

Dark Age of Camelot and Everquest use no technique to improve the display engine's performance when too many characters are on screen. For this reason, the display becomes choppy and unpleasant for the user during large raids or gatherings of many players. Players are forced to degrade the display quality as much as possible to obtain playable performance. During the largest gatherings, players are forced to "look at the ground" to avoid having too many characters in view. This problem is frequently raised by the MMORPG player community.

In Dark Age of Camelot, no technique improves display performance when too many characters are on screen.

Same observation for Everquest.

Customization

Everquest and Dark Age of Camelot allow players to customize their avatars.

In Everquest, the player can customize their character's feet, legs, torso, and back. For each body part, they can acquire an accessory and wear it over their clothing. Technically, this is achieved by superimposing accessories. The game first displays the basic body object, then the clothing over it. The drawback of this technique is that many polygons composing the different body objects are drawn but not visible, as they are hidden by other clothing. All these polygons could be used to better detail the characters.

For the face, Everquest allows the player to change eye color, change the face texture, and change the shape and color of hair. The texture is an image containing the drawn face that is applied to the object. It is not possible to change the shape of the face.

For size, Everquest offers three character sizes. Sizing is done by applying a simple uniform 3D homothety on the entire character.

In Everquest, two dwarves wear armor and boots. These clothes are displayed on top of their standard body.

In Dark Age of Camelot, the player can customize their character's base clothing with additional elements like gloves, a cape, etc. A black and white texture is applied to each body element. It can be multiplied by a color to customize its appearance. This technique allows giving a unique tint to the entire texture but does not allow coloring different parts of a body element with different colors. Moreover, the color variation is necessarily a multiplication of two colors, not a hue change. This produces textures with uniform tints, with variation only in luminosity but not saturation.

For size, Dark Age of Camelot offers choosing the character's size, performed by applying a simple uniform 3D homothety as in Everquest.

Graphical quality

The graphical quality choices for Everquest characters are basic. Characters are composed of few polygons and a single texture is applied to them.

An Everquest character.

Dark Age of Camelot characters are composed of more polygons. A single texture is still applied to draw them.

A Dark Age of Camelot character.

Neither Everquest nor Dark Age of Camelot offers a technique for deforming the face.

• [Hoppe1] Mesh optimization. H. Hoppe, T. DeRose, T. Duchamp, J. McDonald, W. Stuetzle. ACM SIGGRAPH 1993, pages 19-26.
• [Eck] Multiresolution analysis of arbitrary meshes. M. Eck, T. DeRose, T. Duchamp, H. Hoppe, T. Lounsbery, W. Stuetzle. ACM SIGGRAPH 1995, pages 173-182.
• [Hoppe2] Progressive meshes. H. Hoppe. ACM SIGGRAPH 1996, pages 99-108.
• [Hoppe3] Efficient minimization of new quadric metric for simplifying meshes with appearance attributes. H. Hoppe, S. Marschner. Microsoft Research Technical Report MSR-TR-2000-64, June 2000.
• [Pandemic] Pandemic Studio, "Pandemic Studios breaks the LOD barrier with Multi-Resolution Mesh technology". http://www.intel.com/labs/media/3dsoftware/casestudy.pdf
• [DeRose] DeRose, T., Kass, M., Truong, T. Subdivision Surfaces in Character Animation. Proceedings of the 25th annual conference on Computer Graphics, 1998, Pages 85-94.
• [Lee] Lee, A., Moreton, H., and Hoppe, H. Displaced Subdivision Surfaces. Computer Graphics Proceedings, SIGGRAPH 2000, 2000.
• [Lounsbery] Lounsbery, M., DeRose, T., Warren, J. Multiresolution Analysis for Surfaces of Arbitrary Topological Type. ACM Transactions on Graphics, Vol. 16, No. 1, January 1997, Pages 34-73.
• [Pulli] Pulli, K., and Segal, M. Fast Rendering

The main objective of this project is to achieve the display of high-quality three-dimensional characters (approximately 5000 polygons per character) with the constraint of maintaining good performance when the number of characters on screen is high, as is the case in MMORPGs.

The character will be animated and deformed as usual, using a bone skeleton. The number of bones will be significantly increased, as hands, hair, and all fingers must be animated.

The technique employed must also allow a high level of character customization as required by MMORPGs. It must be possible to change each body part and color them.

Finally, the technique employed must allow deformation of the character's face.

Numerous research papers propose various solutions for dynamically reducing the number of polygons used by a character [Hoppe1] [Eck] [Hoppe2] [Hoppe3] while obtaining a quality object. Some of these solutions, highly simplified, are implementable in real time [Pandemic], meaning they can be applied to video games. But no research provides a real-time solution to the approaches proposed in [Hoppe2]. Our main uncertainty on this subject is to research an algorithm and data structure applicable in real time to the problem of multi-resolution three-dimensional meshes.

Another technical uncertainty is finding a solution that allows modifying character body parts without using the "clothing superposition" technique, which we consider to be poorly performant. This technique must be compatible with the previously developed algorithm.

It is also necessary to find a clothing coloring system that is more efficient and produces better results than those used by competitors (Dark Age of Camelot) with a simple color multiplication.

The first task will consist of developing a data structure and algorithm for real-time polygon count reduction of a three-dimensional mesh, also allowing mesh deformation by a skeleton system and "blend shape" deformation.

The second task will consist of reinforcing the performance of the previous task through a system of extreme character simplification while keeping them animated.

The third task will consist of developing a system allowing the character to be split into joinable pieces in order to change different body parts.

The fourth task will consist of studying a method for coloring clothing texture pieces by manipulating the hue, saturation, and luminosity characteristics of colors.

Three-dimensional meshes are used to model volumes. They are composed of a set of points assembled into triangles.

Example of a three-dimensional mesh.

The goal of the algorithm to develop is to reduce the mesh complexity in real time. The techniques implemented until now [Pandemic] constructed a sorted list of mesh points ordered by simplification priority. To obtain a mesh at a given complexity level N, it suffices to read the first N points from the list.

In this example, a mesh with five points and four triangles is simplified to four points and two triangles. The right mesh is created by keeping only the first four points from the list.

The basic algorithm can only merge a point onto another already existing one. The main problem with this method is that at each simplification step, the mesh always has a subset of the original point list but never any new points.

The algorithm we use to precompile mesh simplification also proposes creating new points by merging two points into a new one, thus obtaining a simplified but much more faithful shape of the mesh.

Thus, a mesh of three thousand polygons and three thousand points is compiled as follows: the mesh is duplicated into ten copies. Each new copy has three hundred fewer points than its predecessor. A point array is created with, at the head, three hundred temporary points followed by the three thousand points of the first mesh, followed by new points involved in composing the second mesh, followed by new points for the third mesh, etc.

Traditional MRM point list structure:

┌──────────────────────────────────────────────────────┐
│           List of 3000 mesh points               │
└──────────────────────────────────────────────────────┘

Point list structure of a traditional multi-resolution mesh.

Our MRM point list structure:

┌────────────┬────────────┬────────────┬────────────┐       ┌─ ─ ─ ─ ─ ─┐
│  Buffer   │   3000    │ N points  │ N points  │       │ N points  │
│  of 300   │ points of │  of 2nd   │  of 3rd   │       │ of 10th   │
│ temporary │   1st     │   LOD     │   LOD     │  ...  │   LOD     │
│ points for│  mesh     │ not in    │ not in    │       │ not in    │
│ geomorph  │           │ 1st mesh  │ 2nd mesh  │       │ 9th mesh  │
└────────────┴────────────┴────────────┴────────────┘       └─ ─ ─ ─ ─ ─┘

Point list structure of our multi-resolution mesh.

So that transitions between two meshes of resolution N and N+1 are performed smoothly (without jumps or jitter), a geomorphing technique was added to the original algorithm. It consists of displaying the mesh at level N using a buffer of three hundred points for the points that will be modified at level N+1. At each display, the point buffer is recalculated to progressively bring the buffer points toward their final position at level N+1. Once this stage is reached, it is possible to display level N+1 without any visible jitter or jumps.

Skeleton deformation

To deform a mesh using a skeleton, it is necessary to know, for each mesh point, the list of bones influencing the point as well as, for each bone, the influence weight. By adding this information to the point structure in our list, it is entirely possible to use this algorithm with our multi-resolution mesh.

Blend shape deformation

Blend shape deformation consists of deforming a mesh using a second mesh of identical structure but with different point positions. The deformation consists of progressively moving the points of the first mesh toward the position of the target mesh. It is possible to use the blend shape deformation algorithm by compiling the target meshes into multi-resolution meshes in a data structure parallel to that of the original mesh.

Example of blend shape deformation.

The performance of the algorithm developed during this project proved conclusive. Indeed, at each mesh display, the algorithm modifies the position of three hundred points, which is entirely reasonable. It is now possible to display many characters without significant performance loss, unlike other MMORPGs. In case of overload, the character resolution is automatically reduced by the graphics engine.

The effects of polygon count reduction weakly degrade the visual quality of the mesh if this reduction is performed simultaneously with an increase in the mesh-to-camera distance. Thanks to the ability to create new points in the reduced mesh, the coherence of the simplified mesh relative to the original has been improved compared to that obtained by the algorithm previously used in real-time applications.

The memory footprint of the new multi-resolution mesh data structure is much heavier than that of the old algorithm. It can weigh up to three times the size of a traditional mesh data structure.

This algorithm allows the use of skeleton deformation or blend shape deformation algorithms.

When characters are very far from the camera (at a distance greater than forty meters), the mesh obtained by this algorithm is still too complex. Indeed, the mesh has too few points to be efficiently displayed by hardware acceleration. It is necessary to research an adequate solution for displaying distant characters.

Screenshots of the prototype developed to test the multi-resolution mesh and skeleton deformation.

Yoyo — 2 months. Matthieu — 1 month.

An extreme animated character simplification system was developed to display very distant characters with good performance. When multiple meshes have few points, they should be grouped and displayed together to make hardware acceleration more efficient.

For this system, meshes representing characters with very few polygons (less than one hundred polygons) were created. These meshes were pre-deformed to produce animations. We thus obtained a deformed mesh for each animation frame — twenty per second of animation.

During display, each mesh representing a distant character adds the points of its pre-deformed mesh to the global point list of distant characters. Once all meshes representing distant characters have added their points, all these meshes are drawn at once, which significantly increases display performance.

Batched draw — all distant characters in one vertex buffer:

┌────────────┐     ┌────────────┐     ┌────────────┐            ┌────────────┐
│ Points of │     │ Points of │     │ Points of │            │ Points of │
│  1st      │ ──▶ │  2nd      │ ──▶ │  3rd     │ ──▶ ... ──▶│  Nth      │
│ character │     │ character │     │ character │            │ character │
│  mesh     │     │  mesh     │     │  mesh     │            │  mesh     │
└────────────┘     └────────────┘     └────────────┘            └────────────┘

Before developing this system, highly simplified meshes were drawn one by one, which was inefficient given the very low number of points they were composed of.

Old approach — one draw call per character:

┌────────────┐  ┌────────────┐  ┌────────────┐  ┌────────────┐
│ Points of │  │ Points of │  │ Points of │  │ Points of │
│  1st      │  │  2nd      │  │  3rd      │  │  Nth      │
│ character │  │ character │  │ character │  │ character │
│  mesh     │  │  mesh     │  │  mesh     │  │  mesh     │
└────────────┘  └────────────┘  └────────────┘  └────────────┘

With this system, all meshes of very distant characters are drawn simultaneously.

This system increases display performance when the number of distant characters on screen is high.

The graphical quality of these characters is poor; this system should only be used when the object-to-camera distance is large.

Yoyo — 1 month.

Rather than personalizing the character through a clothing superposition technique, as in other games, it was decided to personalize the character by changing pieces of its body. The character is split as follows:

• Hair
• Head
• Torso
• Arms
• Forearms
• Hands
• Thighs
• Boots

Each body part is a new mesh using the multi-resolution mesh technique.

The main problem with this technique is that, each body part being independent, the degradation of the junction between parts is not synchronized. Holes then appear in the character mesh along the junctions.

Two meshes perfectly connected before degradation.

The two meshes after degradation of object 2.

To correct this problem, the junctions between meshes were identified. Then, their degradation was computed independently from that of the mesh. The junction degradation "guides" that of the rest of the mesh. Thus, the junction degradation is the same in all meshes.

The two meshes whose junction degrades synchronously.

This project allowed adapting our multi-resolution mesh technique to the character customization constraint for MMORPGs.

Yoyo — 1 month. Nicolas — 1 month.

The texture coloring technique used by Dark Age of Camelot is a simple color multiplication on a black and white texture. This technique does not allow modifying part of the texture and therefore cannot modify the texture with multiple colors. It also does not preserve the contrast and hue nuances in the texture. Finally, it is difficult to produce black or white as a coloring. The advantage of this technique is that it is easily implementable by computer graphics cards.

	x		=

Coloring technique used in Dark Age of Camelot.

A first technique close to the one explained above was initially tested. The goal was to color the texture with the same texture multiplication technique but using a mask to apply it only to certain parts of the texture. The interest of this technique lay in the fact that the graphics card could be used to perform the coloring. This technique was not retained as it did not allow performing multiple colorings on the same texture.

The method that was then developed is as follows: multiple masks identify the texture zones to color. The texture is converted to the LHS (luminosity, hue, saturation) color space. For each texture zone, the algorithm evaluates the average hue used in that zone, then calculates the deviation from this hue for each pixel in the zone to be colored. Then, the user provides the algorithm with the desired hue and variations in contrast and luminosity to modify this texture zone. The algorithm adds the user-chosen hue to the hue deviation calculated previously across the entire zone to be colored. It also allows retouching color saturation, contrast, and overall texture luminosity.

	MASQUE		=

The texture is first cut using a mask.

	REPLACE TINT		=

The hue is replaced by the new one, and corrections for color saturation, luminosity, and contrast are applied.

Some examples of colored textures.

The coloring technique developed is very convincing. It allows coloring different parts of a texture with different colors. It also allows achieving white and black colorings by using color saturation and luminosity.

This technique is not directly usable on the graphics card. The filtering must be performed before the texture is taken over by the card.

Yoyo — 1 month. Nicolas — 1 month.

Thanks to these four research axes, the three-dimensional character display technology developed allows real-time display of a large number of characters with good graphical quality. Each character can be customized by modifying or coloring clothing.

Our character display technology allows us to use more detailed three-dimensional meshes than in competing games.

Dark Age of Camelot (left).	Ryzom (right).

We improved the real-time multi-resolution mesh technique.

We provide a solution to the graphical overload problem when a large number of players are displayed on screen.

We propose new techniques for character customization at the clothing and color level.

Example of customization in Ryzom.