14
$\begingroup$

How do modern games do geometry level-of-detail for object meshes like characters, terrain, and foliage? There are two parts to my question:

  1. What does the asset pipeline look like? Do artists make a high-poly model which is later decimated? If so, what decimation algorithms are most popular? Are LOD meshes sometimes done by hand?
  2. How do engines transition between different object LODs at run time? Are there any smooth or progressive transitions?

The answer might be "different studios use different techniques." If so, please identify some of the most common practices. It would also be great if you could point me to whitepapers/slides that cover specific examples.

$\endgroup$
  • 1
    $\begingroup$ SIGGRAPH 2014 advances in real time rendering has a really interesting talk on call of duty's subdivision surfaces. You should check it out. Instead of having a high poly mesh that is made lower poly, they defined shapes analytically and added more triangles as needed $\endgroup$ – Alan Wolfe Sep 5 '15 at 3:09
  • $\begingroup$ We can talk about the state of the art in LOD algorithms and data structures here, but if the question is about how modern games do it specifically, you might have more luck asking in gamedev.se: gamedev.stackexchange.com $\endgroup$ – Pseudonym Sep 5 '15 at 6:02
  • 3
    $\begingroup$ I doubt that. Game dev is very graphics light. It's mostly unity and java questions with some path finding and fixed frame rate questions thrown in :p $\endgroup$ – Alan Wolfe Sep 5 '15 at 16:52
  • 1
    $\begingroup$ @Alan, Activision used a lot of state of the arts algorithm to create a real 3D strategic game not sn isometric Sprite base one which I am ok with that, but they did a great job in COD however it is still a bit sluggish and lazy even at the early levels with small number of assets (I am talking about their mobile game on an Iphone 5s). I think you need to learn OpenGLES expert features and underlying layers to succeed writing such a game. $\endgroup$ – Zich Sep 6 '15 at 6:58
  • $\begingroup$ I'm talking about their console version of call of duty in case that clears it up. $\endgroup$ – Alan Wolfe Sep 6 '15 at 13:53
22
$\begingroup$

For the geometry LOD most games simply switch between a number of predefined LOD meshes. For example "Infamous: Second Son" uses 3 LOD meshes (Adrian Bentley - "inFAMOUS: Second Son engine postmortem", GDC 2014) and "Killzone: Shadow Fall" uses 7 LOD meshes per character (Michal Valient - "Killzone: Shadow fall demo postmortem", Devstation2013). Most of them are generated, but more important ones (like main character) can be hand made. Meshes are often generated using a popular Simplygon middleware, but sometimes they are simply generated by graphics artists in their favorite 3D package.

Games with a large draw distance additionally use imposters for foliage, trees and high buildings (Adrian Bentley - "inFAMOUS: Second Son engine postmortem", GDC 2014). They also employ hierarchical LODs, which replace a set of objects with one. For example in "Just Cause 2" trees are first rendered individually as normal LOD meshes, then individually as imposters and finally as a single merged forest mesh (Emil Persson, Joel de Vahl - "Populating a Massive Game World", Siggraph2013) and in "Sunset Overdrive" distant parts of the world are replaced by single automatically offline generated mesh (Elan Ruskin - "Streaming Sunset Overdrive's Open World", GDC2015).

Another component of a LOD system is simplification of materials and shaders. For example "Killzone: Shadow Fall" disables tangent space and normal mapping for the distant LODs (Michal Valient - "Killzone: Shadow fall demo postmortem", Devstation2013). This usually is implemented by disabling globally a set of shader features per LOD, but for engines with shader graphs, where artists can create custom shaders, this needs to be done manually.

For the LOD transitions some games simply switch meshes and some use dithering for smooth LOD transitions - at the LOD switch two meshes are rendered: first gradually fades out and second fades in (Simon schreibt Blog - "Assassins Creed 3 – LoD Blending"). Classic CPU progressive mesh techniques aren't used as they require a costly mesh update and upload to GPU. Hardware Tessellation is used in a few titles, but only for the refinement of a most detailed LOD, as it's slow and in general case it can't replace predefined geometry LODs.

Terrain LODs are handled separately in order to exploit it's specific properties. Terrain geometry LOD is usually implemented using clipmaps (Marcin Gollent - "Landscape creation and rendering in REDengine 3"). Terrain material LODs either are handled similarly to mesh LODs or using some kind of a virtual texture Ka Chen - "Adaptive Virtual Texture Rendering In Far Cry 4.

Finally if you are interested to see real game LOD pipelines then just browse through documentation of any of the modern games engines: Unreal Engine 4 - "Creating and Using LODs", CryEgnine - Static LOD and Unity - LOD.

$\endgroup$
  • 1
    $\begingroup$ game engines usually have a set of pre defined methods and you can not get in to the core to actually changing the LOD algorithm. am I right? I was talking about the case you are writing a game yourself with OpenGL or SpriteKit framework, I dont know if one is able to customize LOD's algorithm in Unity or Unreal, is it possible? $\endgroup$ – Zich Sep 6 '15 at 18:19
3
$\begingroup$

LOD (Level of Detail) means managing objects in different display scales, which could be devided by two parts. However, you may use one of them and that would be enough for most cases.

  1. Show/hide layers ( group of objects of same type) depending on magnitude (display scale).

  2. Algebraic Geomery based method, called Generalization (which is an algorithm to simplify polygons). look at the following picture

    generalization

The most famous and efficient method to generalize (simplify) a polygon mesh is known as Descartes-Euler polyhedron theorem (Equation 4.5 sorry if I am refering to a book, that was best I can do) and is used by most of the spatial databases for example PostGIS modules in PostgreSQL. It simply removes smaller sides of a polygon and makes a very rounded one.(above picture)

To implement LOD in a game you need to save and manage the scale of your map (scene) during th zoom in/out operations. The scale changes from zero to infinity and you have to divide this into a particular number of ranges for example something like this:

  1. 1/zero = infinity to 1/50
  2. 1/50 to 1/100
  3. 1/100 to 1/1000
  4. 1/1000 to 1/infinity = 0

Then you need to define which types of your objects (layers) should be visible or invisible in each of the above ranges. For example a small type of object like a hydrant valve should not be visible when the user is in the fourth range because it will be very small at that scale and can not be discriminated so it doesn't matter if you skip drawing it on the screen.

So when a user uses zoom in and zoom out to change the magnification he moves through the above limits from one to the other range, and your game uses these display scales to manage level of details by showing or hiding objects on the scene. This makes a discrete solution that objects suddenly fade during your zoom out operation, however having the display scales and magnification ranges defined carefully, the user woudn't feel anything.

The above group of 4 ranges are just an example and you need to find the best for your own case by trial and error. There is no rule for that.

Sometimes the games use their own LOD methods, Subway Surfer for instant, shows a small, without texture rectangle to show a building at far, and by getting close suddenly it gets texture, gamer feels it. You didnt talk about your projection system which is very important also didn't talk about what kind of game you are creating.

However suppose you are implementing a full 3D game with openGl and you wish to filter some mesh before transfering them to graphic hardware, I am sure this will help you to reduce binding/unbinding operations with buffer objects and vertex arrays (VBO,VAO) while dealing with OpenGl.

Using only a layer managment or just implement Euler's Generalization

In most cases it is not necessary to implement a generalization algorithm, and filtering objects just works and gets you to the efficiency(refresh rate) you need, however it totally depends, case by case. Although it is an easy algorithm that just removes the small sides of a polygon, you need to define a threshold which is the product of magnitude and a constant number, so bigger sides get filtered in a much farther point of view.

Forgeting the layer manamgment and only implementing Eulers generalization algorithm, provides a very neat and continuous method in which you just check each sides and lines against a pre-defined threshold and show them only in case they are big enough to be discriminated on the screen.

P.S : magnification is a float number > 0 which is equal to 1/scale and the scale is usually < 1 since a 1:1 scale means you have real world lengths in your game.

$\endgroup$
  • $\begingroup$ Down voter, please consider you vote again, if it is still a -1, Consider leaving a comment for me.Thanks $\endgroup$ – Zich Sep 6 '15 at 13:00
  • $\begingroup$ I didnt downvote but part of me wonders what is the sate of the art here? So i cant up vote either. $\endgroup$ – joojaa Sep 6 '15 at 15:59
  • 1
    $\begingroup$ I've downvoted because it was hard to read and IMHO it's not relevant to LODs in games. After reconsidering I decided to cancel my donwvote by upwoting and simply add my own answer. $\endgroup$ – Krzysztof Narkowicz Sep 6 '15 at 18:02
  • $\begingroup$ State of the art suppose to mean a very outstanding job but different methods result differently on various cases, for example Call of duty has Layer management and mipmaping, however Dear haunting(DH 2014) uses background with parallax and a mipmaping which has pre rendered generalized textures. Subway surfer is completely a diffrent story, and I say state of the art to all of them, even though Subway Surfer discretely draws buildings and other urban objects or Call of duty is a bit sluggish while zooming or panning. I think they are all best in their case. $\endgroup$ – Zich Sep 6 '15 at 18:04
3
$\begingroup$

Iman already prepared a complete answer but I wish to add something to it

LOD can be done in two different way

  1. Continous which is called CLOD and is a polygon mesh optimization
  2. Discrete which almost every other algorithm than polygon mesh optimization, considered to be in this group.

For example mipmaping is a good,fast but heavy one that belongs to secound group at the above

here you may find a good explanation to mipmaping and implementation code with OpenGl.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.