---

Translated from "fr dossier 2002 / Projet NeL - 3D - Ombres portées dynamiques REVIEWED". Despite being filed under the 2002 dossier, this document was actually written in 2005, as evidenced by references to Doom 3 (2004) and World of Warcraft (2004). {.is-info}

Nevrax develops Ryzom, a 3D interactive MMORPG with a strong desire for immersion. One aspect of this game is to represent players who move, live, and fight creatures and other players in an imaginary world. Players and creatures are animated (walking, running, combat animations...) and can move around this world.

The research and development in 2001 allowed displaying large terrains and visually convincing interiors, with cast shadow precision and quality still unmatched to this day in an MMORPG. However, the display of these shadows is based on the principle of "precomputation" — since interiors and terrains are static (trees, hills, and cities do not move), the heavy shadow calculation could be done "offline", in a process that could take several hours depending on the zones to compute.

This principle therefore cannot apply to characters and creatures that live and move in the world. The representation of shadows greatly contributes to graphical credibility and therefore to immersion. Without shadows, characters give the impression of "floating" because the eye can interpret the character's distance on screen in multiple ways (is it small and close or is it large and far away?). Shadows allow "anchoring" characters to the ground, which is why the vast majority of games use a more or less advanced dynamic cast shadow system.

Mathematically exact dynamic shadow systems were too costly in 2002 and remain so today except in confined environments. This is why most games use approximate solutions such as the usual black circle more or less stuck on the ground beneath the creature or player's feet.

Nevrax therefore wanted a system that would display relatively precise and credible shadows (not a simple black circle), all at negligible machine time cost (as opposed to the hours of computation needed to calculate terrain and interior cast shadows). Furthermore, the system must be compatible with the fact that we display outdoor environments with a long view distance.

In early 2002, three major types of real-time dynamic cast shadow algorithms could be distinguished.

The first and simplest is to apply a so-called fake texture resembling a shadow on the ground. Usually a disc, some games like Warcraft 3 use a texture that more closely resembles a shadow. The main limitation of this technique is that the shadow remains very approximate and does not represent the animated state of the entity.

Warcraft 3 and its fake shadows.

The second is the use of Depth Shadow Maps. The general principle is that for each light source:

• Render the scene as seen from the light, and write into a texture (DepthShadowMap) the depth or Z (Depth) relative to that light.
• Then render the scene normally as seen from the camera, and test for each pixel whether it is closer or farther from the light using the DepthShadowMap. If it is closer to the light than the Z stored in the DepthShadowMap, then it is lit; otherwise it is hidden by some occluder.

This technique is robust and exact, but poses several problems:

• The scene must be rendered as many times as there are lights. Ryzom can have hundreds of light sources (street lamps, campfires, special effects, etc.), which is problematic since one cannot render a scene 100 times when it already takes about 30 ms to render once (i.e. 30 frames per second).
• DepthShadowMaps suffer from z-fighting, shadow map precision, aliasing, and can only produce HardShadows. In nature, light sources are not perfectly point-like and have a certain volume (the sun is not just a simple point). This affects the real appearance of cast shadows, which then appear blurred. These are called SoftShadows.

Depth Shadow Maps. Hard Shadows.

The third is the use of Stencil Shadow Volumes. The general principle is that for each light source:

• Compute for each object in the scene a Shadow Volume, which is a volume starting from the object's edges relative to the light and going to infinity along the light ray.
• Write the front and back faces of the shadow volume into the stencil buffer (a buffer the same size as the screen with a counter per pixel). Write +1 for front faces and -1 for back faces. In both cases, only write if the shadow volume pixel passes the Z-buffer test.
• A pixel is shadowed if the final stencil result is >0.

This technique is robust and exact but has the following advantages and disadvantages:

• Avoids the aliasing and z-fighting problems of Depth Shadow Maps.
• Still only produces HardShadows.
• Still requires the scene to be rendered as many times as there are light sources.
• Rendering shadow volumes into the stencil buffer is very costly in fill rate, as large faces are drawn. Furthermore, innocuous objects like prison bars can be terribly expensive, as they generate many large shadow volume faces to draw.

The best example of this technique is Doom 3, released in 2004. As the screenshot shows, the technique is well suited to this kind of game, as it takes place in a confined environment with a reduced number of light sources.

Doom 3: Shadow too sharp, confined environment, short view distance, single light.

• BATAGELO, H. C., AND JUNIOR, I. C. 1999. Real-time shadow generation using BSP trees and stencil buffers. In Proc. SIBGRAPI 99, 93-102.
• BILODEAU, B., AND SONGY, M. 1999. Real time shadows. At Creative Labs Sponsored Game Developer Conference, Creative Labs Inc.
• CARMACK, J. 2000. Published on the NVIDIA website.
• CROW, F. C. 1977. Shadow algorithms for computer graphics. In Proc. SIGGRAPH, ACM Press, ACM, 242-248.
• EVERITT, C., AND KILGARD, M. J. 2002. Practical and robust stenciled shadow volumes for hardware-accelerated rendering. Tech. rep., NVIDIA.
• HEIDMANN, T. 1991. Real shadows, real time. In IRIS Universe, vol. 18, Silicon Graphics, Inc, 23-31.
• KILGARD, M. J. 2001. Robust stencil shadow volumes. In Presentation at CEDEC, Tokyo.
• STAMMINGER, M., AND DRETTAKIS, G. 2002. Perspective shadow maps. In Proc. SIGGRAPH, ACM Press, ACM, 557-562.

Objectives:

• Render blurred cast shadows, or SoftShadows, on dynamic and/or animated objects.
• Have a principle compatible with the fact that characters and creatures can be displayed over more than 1000 meters and therefore be affected by lights.
• Allow display of such shadows on a large number of entities (256).

Constraints:

• RAM memory size
• Video card memory size (VRAM)
• Target processor capacity: Pentium 1 GHz
• Target graphics card capacity: GeForce 2 GTS
• Computation time allocated to shadow display (1 ms)

Most of these points had not been addressed in any research paper found, particularly the generation of soft shadows in less than one millisecond. It was therefore difficult to know whether a solution would be found for all of them.

We oriented towards a solution halfway between Depth Shadow Maps and fake shadows projected on the ground. By generating just the shadow occlusion in a texture (without the Z), and then applying a gaussian filter on top of it, we could hope to arrive at a correct approximation of the expected result.

However, the following problems had to be solved:

• Shadow generation must be as fast as possible, while:
  • There are 256 entities to manage (on average 64 visible on screen)
  • These entities must be animated before being rendered into the ShadowMap, which is very costly in CPU.
  • The size (in pixels) of the shadows to generate is problematic as we are limited in fill rate by the GPU.
• Shadow application on the scenery must be as fast as possible, while:
  • There are 256 entities to manage (on average 64 visible on screen)
  • We cannot afford to render the scenery as many times as there are cast shadows.

The following research tasks were performed:

1. Fast generation of SoftShadowMaps from animated characters
2. Fast application of SoftShadowMaps on scenery
3. Management of multiple lights on a single entity

The goal of this task is to have, for each entity E / light L pair, a reliable approximation of the blurred cast shadow (soft shadow) representation of L on E at time t.

The solution found was to combine the application speed of fake shadows with the precision of DepthShadowMaps.

The key points of the method used to render the soft shadow map of an entity are:

• Make an approximate rendering of the entity in its animation state at time t into a texture. Instead of rendering the actual color/texture of the entity, or rendering its depth (as in depth shadow maps), we only write black pixels on a white background.
• To accelerate rendering, several principles are used:
  • The skinning (skin animation on bones) used for this render is a lightweight skinning that uses only a single matrix per vertex (and therefore without weights), instead of 4 matrices per vertex with weights.
  • The mesh used for shadow rendering is a lightweight version of the original mesh. We use previous work done on MRM (CIR 2001). This allows rendering characters with 1000 faces instead of 4000.
• Once the occlusion map for the E/L pair (Entity/Light) is generated, this occlusion map is filtered via a gaussian blur. Since texture blurring is costly in fill rate, two optimizations were found:
  • We use the GPU's BiLinearFiltering to go 4 times faster, for an equivalent result. The idea is to offset texture coordinates by half a texel during the blur, so as to freely obtain the average of a texel with its 3 neighbors.
  • To avoid the very costly overhead of RenderTarget changes, we filter 8 cast shadows from 8 E/L pairs at the same time. We must then ensure that the shadows of one E/L pair do not overflow onto another by writing black borders before each blur pass.
• To limit computations, we allow only 8 shadow calculations per frame (30 frames per second) since we can potentially have 256 entities on screen. The algorithm is based on the shadow's distance to the camera and when it was last computed, to decide which shadow to calculate as a priority.

The method allows generating shadows that are both blurred (SoftShadow), representative of the entity's state, and very fast (on the order of 1 millisecond for 8 generated entities).

The first disadvantage is that this shadow can only be applied on scenery (no self-shadowing of entities on themselves), unlike DepthShadowMaps. However, the main effect remains seeing the shadow on the scenery, which was the goal.

The second disadvantage is the inconsistency between static cast shadows and dynamic cast shadows: the scenery can receive the addition of 2 shadows (static and dynamic) from a light source, when it should only be occluded once. Research and approximations were made to solve this problem in the following section.

The solution found offers an approximate but more than visually acceptable result. The limitations attached to it were resolved in the following tasks.

Once we have shadows representative of an entity's state relative to a light, they must be projected onto the scenery (terrain or interior) and integrated with the precomputed static shadows.

The key points of the method used to project the shadows of E/L pairs are:

• For terrain:
  • Coarse selection of Bezier patches.
  • Precise selection by face. Research showed that it is better to spend time precisely selecting faces (CPU cost) because shadow projection is very costly in fill rate: if an entity is close, the faces to display on screen are very large (GPU cost).
• For interiors:
  • Coarse face selection with a quad-grid.
  • Precise selection by face, for the same reasons explained above.
• Coherence between static and dynamic cast shadows:
  • The problem is that static elements relative to a light L are already shadowed via an offline calculation. If we re-multiply with the entity's shadow, the result is incorrect because the scenery then undergoes shadowing twice relative to light L.
  • To solve this problem, an approximate but visually acceptable method was found:
    • Since entities and their shadows are relatively small (human = 2 meters), we look beneath the entity at the ambient value At and the diffuse value Dt precomputed for the terrain.
    • Scenery pixel colors on screen can be described by the formula: pix = (At + Dt) * Texture
    • When a zone is shadowed relative to a light, only the ambient value should remain. We should therefore have only pix = At * Texture.
    • Since we multiply the shadow pixels with the pixels already on screen, the following formula results: ShadowColor = At / (At + Dt). The final result will be:
      • pix = ShadowColor * (At + Dt) * Texture
      • pix = At / (At + Dt) * (At + Dt) * Texture
      • pix = At * Texture
• Limitation of cast shadow size:
  • If a light is grazing relative to a surface (for example a steep hill with a 45-degree slope when the sun direction is parallel), infinitely large (or very large) cast shadows can result. This poses problems in terms of fill rate (GPU) and selection time (CPU).
  • To avoid this problem, shadow depth was limited to a maximum of 8 meters. To avoid cutoff problems at 8 meters, a second 1D clamp texture was used, which is a gradient from 7 to 8 meters, providing a soft and less noticeable cutoff.
  • Since most walkable scenery (and therefore where shadows will be cast) is flat, the maximum light angle from vertical was limited to 45 degrees, ensuring less frequent cutoffs. More grazing cast shadows are then incorrect but visually acceptable.
• Limitation of the number of shadow projections. As with generation, here we decided to project shadows only for the 16 nearest entities (out of 256 potentially visible on screen).

In the following screenshots, you can see the blur effect (SoftShadow) of the cast shadow on the terrain. You can also notice the considerable number of cast shadows on the terrain and the minimal impact this has on the frame rate (27 for the first without shadows and 29 for the second with).

The solution found is satisfactory. Depending on the location and the hardware (GPU), up to 16 entities can cast their shadow on the ground for less than 1 millisecond. Thanks to the priority system, only the nearest and therefore most interesting entities cast their shadow.

Limit the E/L pair computation to a single shadow calculation per entity E, regardless of the number of lights L.

In Ryzom, there can be multiple static or dynamic light sources. For performance reasons, the 3D engine only allows interaction of a maximum of 4 static or dynamic lights with each entity (the influence of lost lights is transferred to an additional global ambient approximating their impact).

However, with the results of previous tasks, it quickly became apparent that we could not decently support even 4 cast shadows per entity.

The solution was to create a virtual light representing the 4 lights that an entity can receive. The virtual light is simply created with weighting as follows:

Virtual Light Direction = (Sum of DirectionLight-i * IntensityLight-i * AttenuationLight-i) / (Sum of IntensityLight-i * AttenuationLight-i)

Virtual Light Color = (Sum of ColorLight-i * IntensityLight-i * AttenuationLight-i) / (Sum of IntensityLight-i * AttenuationLight-i)

The virtual light direction is directly used to compute the entity's cast shadow. The virtual light color later influences the shadow color calculation.

Thus, a single cast shadow is computed per entity, regardless of the number of lights it receives.

The results of this method are more than satisfactory. It offers coherent effects even if mathematically incorrect:

• During the night, if far from a street lamp, the light direction takes that of the moon.
• As one approaches the street lamp, the shadow direction progressively changes to eventually take almost exclusively the StreetLamp/Entity direction.
• Since the street lamp is a flickering light, its intensity and therefore its influence on the virtual light direction diminishes. Consequently, the direction changes slightly with the street lamp's flickering. What might appear as a bug turns out to be an interesting approximation, as the shadow then appears to be animated in correlation with the street lamp.

Shadow to the right and attenuated.	Shadow to the north and stronger.

This method divides by 4 on average the generation and projection time of E/L pairs, for a mathematically incorrect but visually coherent result.

In conclusion, the initial objectives were met. The strong memory and computation time constraints are respected, at the expense of mathematical accuracy of the shadows, but with a more than credible result. Furthermore, the technique allows the generation of approximate blurred shadows, much more realistic than the overly sharp shadows generated by standard solutions like Depth Shadow Maps and Stenciled Shadow Volumes.

We can compare the quality of our shadows with World of Warcraft (released in 2005). It uses the so-called fake circle technique beneath the character. Furthermore, World of Warcraft displays far fewer entities than us. By comparison, our shadows are much more realistic and coherent with the environment.

Simple fake circle (WoW).	Shadow representing the animation state (Ryzom).

Star Wars Galaxies uses Stenciled Shadow Volumes, which as can be seen here generate shadows that are far too sharp. Furthermore, many players complain about having to disable these shadows because they are far too costly.

Shadows too sharp (Star Wars Galaxies).	Soft Shadows (Ryzom).