Monday, September 2, 2013

Voxel Instancing

Instancing is a dirty trick widely used in computer graphics. We are always trying to push the limits in terms of what we can render on screen. Instancing allows to repeat the same object many times in one scene. The object's model is stored only once in memory and we only need to store addition information for each of its occurrences in the scene. That is, their position and orientation. It makes a big difference. Without instancing most of the richness you see in current game worlds would be gone. Boulders, patches of vegetation, even trees and sometimes entire buildings are heavily instanced.

Instancing is a dirty trick because there is no instancing in the real world. Each pebble in that river bed is unique. We use this shortcut in virtual worlds because somehow it still does the trick. Maybe our brain is not able to detect these are all copies of the same object, or maybe it is something we just forgive because nobody has been able to show us anything better.

To the occurrence of each object we call an instance. The source model for all the same instances we can call a "class". This is pretty much the same concepts you find in object oriented programming.

In most game engines, which store all models as polygons, instancing is done at the polygonal level. In my case I saw the same advantages would apply if you had them in voxel form. Their memory footprint is constant, and they a blazing fast to bring into the world.

Translated to voxels, the class stores the voxel values that define the object. This can be done either in a regular grid, or an adaptive grid like an octree. Or, in any other form that makes sense to you. In my case I store them compressed using some form of Run-Length-Encoding. These classes may take one or two megabytes each, in compressed form. Each instance is a much smaller piece of information. It just needs to record where the instance is and to which class it belongs to.

You have seen a lot of this instancing system already in my videos and screenshots. It is how trees are made. But until now, only trees were using instancing. I had my tree generation tool produce the compressed classes directly.

This weekend I added a new feature to the Voxel Studio tool. It can now load a 3D mesh and create the instance data for it. Thanks to this I can have more interesting instances, like giant boulders, dilapidated houses, ruins, even pine trees!

Here are a few screenshots showing how a few instances can spice up the landscape. The last two show how you can carve and edit the instanced voxels. They are no different than voxels coming from any other source.










65 comments:

  1. I've got to admit I spent a few microseconds wondering if those pics were rendered or real life. Whatever the heck you're doing (I'm not an initiate) it's looking absolutely fantastic.

    ReplyDelete
    Replies
    1. Thanks! Incidentally, how is your eyesight? ;)

      Delete
    2. Interestingly enough, I think I might be getting used to how wonderful your engine makes stuff look, I remember when I first saw your engine that for a very short moment, I was looking at real photos. Now on the other hand, I can clearly see it is computer generated.

      Im not saying your engine has decreased in quality, I am merely remarking how it is interesting how the perception of something can change in the human brain =P.

      Delete
    3. Its probably the same kind of thing you get in a lot of places. For instance there are people who can tell you amazingly detailed reports of what spices are in the food they are eating, whether its training or a natural skill. A more computer based comes from me liking to listen to TotalBiscuits content patch and he tends to go into how he can tell the difference between 60fps and 120fps and honestly I probably can't tell anything beyond it looking nice once its gets past maybe 30fps because I just don't play games where its needed. Its a matter of once you know the subject you can more easily discern the smaller details. Though of course for these images even though I can tell they are fake they are definitely some of the closest to real photo quality I have seen in this context and they stay in good taste unlike some photos that look like they decided the uncanny valley should be a real place.

      Delete
  2. Sounds good. I'm a little surprised this feature wasn't in the engine already, but I guess you've just been making great progress in other areas instead. Nice to know that you'll be able to add numerous boulders and ruins to the generated orlds.

    That fourth image looks really great. Even with the square patches of rock in the distance, it really makes me want to go and explore.

    ReplyDelete
  3. I think the ideas laid out on this paper http://www.cse.chalmers.se/~kampe/highResolutionSparseVoxelDAGs.pdf (Siggraph 2013) on storing voxel data as a DAG instead of a tree and with it remove redundancy from identical structures could potentially be interesting in the context of instancing. It would remain to be worked out how to store the instance transforms in the structure, but the idea sounds appealing.

    ReplyDelete
    Replies
    1. But what if you need to store more than just color data per voxel? You'd need multiple DAGs?

      Delete
    2. You could do something like store a pointer in each node to a map, and that map would index from child mask -> voxel attributes.

      Delete
    3. Also the paper describes how a separate DAG can be used for material data. You could also simply differentiate voxels with different materials applied in the original DAG, but then you'd need a unique key for every combination of materials. The paper authors didn't do any investigation into this area.

      Delete
  4. Can you easy merge two different objects? If you have 2 different rocks and you can merge them in one object, you will have infinite number of new rocks. It can be apply to any other objects like tree.

    ReplyDelete
  5. Yet more great stuff!

    I take it you require the orientation to be fixed and the positions snapped to the grid? (Otherwise I don't see the advantage of pre-converting meshes to RLE form.)

    ReplyDelete
  6. please please release a demo, i want to make worlds in this and then walk around them desperately.

    have you thought of a baking system for this ? so you could do megamesh style art workflow? so for instance modelling something in zbrush, importing the ludicrously high mesh into voxel studio and then having voxel studio voxelize that but also generate a normal map to accoutn for any other detail loss?

    ReplyDelete
    Replies
    1. Look for Ever Quest Landmark. It is using voxel farm and will be out soon.

      Delete
  7. How difficult is it to convert a traditional polygonal object into a voxel object?

    Also, is it possible to alter instanced voxel models based upon where they are added? For example, if you put a stone down on a snowy terrain with no geometry above it, the top surfaces of the stone generate a textured snow layer, or if that same stone exists in a dark/wet area, layers of moss/etc grow on said stone.

    Also, is it possible to alter smoothing values on said voxel objects based on position? If you're plopping the same stone at the bottom of a river, the stone would look out of place if it wasn't worn smooth.

    ReplyDelete
    Replies
    1. I would be surprised if the answer was yes.

      Delete
    2. It is not difficult to convert polygonal objects into voxel form. There are some requirements to the polygonal model, for instance it must be properly closed to make sure it actually represents a volumetric thing, not just a surface.

      Different materials can be applied to the instanced voxels. This already happens in the engine.

      About changing the voxels depending on where they land, it is not practical. The main reason why we use instance is for higher speed and lower memory requirements. If we now need to take time to modify instanced voxels it would take some processing time and also storage, because now we would need to remember whatever changes we have done to these voxels. At this point there are better things than this type of straight voxel instancing.

      Delete
    3. This comment has been removed by the author.

      Delete
    4. I see, I imagined that environmental effects could have been generated for the instanced objects at the same time as the ground geometry.

      i.e. you generate all the world voxels first (ground/instanced/etc), then apply base textures and the progressive layered textures which follow the generation rules (slope/environment/etc).

      Delete
  8. So once you build a piece of terrain, do you persist the voxel values (density) in memory until that terrain is unloaded, or do you throw it out and regenerate it again if needed?

    ReplyDelete
    Replies
    1. Nothing generated persists. The data for a given chunk of terrain is briefly in memory while the polygonal mesh is computed. The mesh is sent to the GPU and the voxel data is discarded right away.

      Delete
    2. But if you throw away the voxel data, doesn't that make it difficult to do user edits?

      Delete
    3. User edits aren't generated, thus they persist.

      Delete
    4. @Robin Yes, of course, but new user edits have to interact with (ie intersect) the pre-existing, generated world.

      The proper triangles need to be deleted, created, altered, etc. If you did't persist spatial mappings into the vertex and index buffers, you can't easily do that.

      Delete
    5. It's a procedurally generated voxel world, that maps a polygonal mesh over the voxel elements using dual contouring.

      Since the generation algorithm isn't changing, it will generate the same terrain in that spot every time it is called for. When the engine encounters a modified/saved voxel space, it skips over that space and loads the saved data.

      Delete
    6. It is like Robin says, with a small twist. A modified voxel space is stored as a differential from the procedural baseline. So when the engine encounters a modified/saved space, it still generates the procedural voxels for it, then applies the saved modifications.

      Delete
    7. Does it do that to prevent holes if/when the time to load edited terrain takes too long?

      Delete
    8. Nope, loading goes in parallel with generation. This is so you need to store less data.

      Delete
    9. Perhaps I need to clarify my question.

      I am not talking about long term representation, but rather the precise moment when the player interactively (say) erases a block (ie draws a block of air).

      At this point, the code must either:

      a) regenerate the entire (256x256x256 ?) clip-map of triangles, this time respecting the newly missing block, or
      b) using persisted spatial mapping (eg octtree), quickly delete/alter/add only the affected vertices and triangles in the user's geo buffers.

      It just seemed wasteful to me to regenerate the entire chunk. Is regeneration so fast it's already at interactive speed? Thanks in advance for satisfying my curiosity!

      Delete
    10. Another way of presenting the question would be: you've shown several interactive videos where you rapidly place a string of new intersecting volumes, (even smoothing them on occasion).

      The UI is so responsive that's it's hard to believe you are regenerating the entire ~ 25^3 meters of terrain mesh in the user vicinity with each mouse click. Am I wrong to doubt that? Or are you instead doing only local updates to the geo? Wouldn't such local updates require an octtree or similar spatial mapping to the polygons?

      Delete
    11. The whole regenerating upon edit makes a bit of sense if you look at the past of this engine, before it went editable and real-time generation, it was meant to be streamed over the internet, so it would be logical to not send over all the voxel data (Because frankly, voxel data costs a lot of memory)
      I reckon the choice between regenerating and storing all voxels largely depends on what you want to spend more, CPU/GPU power or memory storage. And memory goes out of the window pretty quickly if you have loads of voxels, good quality textures and other stuff I reckon.

      But I am in no way even close to an expert, so if something doesn't actually work as I say it, disregard it please =P. I'm just making educated guesses here.

      Delete
    12. @Kamica The last thing I want to do is criticize any design decisions. :D
      I'm just trying to make the math add up in my head.

      Watch this video: http://www.youtube.com/watch?feature=player_embedded&v=EuLOJBUBMqw#t=40

      See how he goes click-click-click and removes or adds lots of blocks from the world in rapid succession? Do you think there is time to regenerate 25 cubic meters of terrain with each click? I don't, that's why I asked the question about tiny local updates using something like an octtree. :D

      Cheers!

      Delete
    13. Yes, all the procedural layer are generated from scratch every time you click. This is not only the terrain, also the instancing layer and the architecture (LSystems) layer. It is pretty fast, the average chunk takes around 20 milliseconds from scratch to GPU-ready mesh. If you have multiple cores, each core will process a different chunk. So a whole update is around 40 milliseconds or so worst case.

      Delete
    14. Ha ha! Score one for Kamica.
      Miguel you are amazing!
      Not just because your system runs so efficiently, but also that you take the time to answer these kinds of questions.

      This blog inspired me to make a voxel toy for my four year old daughter. :D

      Delete
    15. @Miguel Since the speedup from multi-core is near-maximal, does that imply you are no longer relying on OpenCL for much of the work?

      Delete
    16. Yes, correct. When generation happens 100% on the client (like in my last demos) I found OpenCL is not that good. I found the driver support was a bit shaky. Also I want to max the rendering as much as possible. The GPU can be 100% busy rendering, doing shadows, improved materials, etc. At this point I can generate more detail with CPUs than what I can render at 60 or 120 FPS, so does not make too much sense to divert GPU power from rendering.

      Maybe later. I am thinking of a new generation for this tech that could move some of this work back to GPU, but not sure now.

      Delete
    17. How the heck do you manage to make those larger Octs? Do you have to sample the density at the finest resolution, and then filter it over and over again until it's at the correct higher resolution? A large oct could consist of millions of samples if done at the finest resolution, correct?

      Delete
    18. @Anonymous Looks to me like he just samples each LOD ring at half the rate (in each dimension) of the preceding one. ie, an octtree leaf for level 4 would be 8 times larger than an octtree cell for level 3.
      No need for fine grain sampling at far distances.
      http://procworld.blogspot.com/2011/10/clipmaps.html

      Delete
    19. Yes, but that would mean that the # of samples would remain constant for every LOD. For instance, level 4 leaves would be 8x smaller than level 3 leaves. Now assume each level has the same number of octs, as the individual leaves get larger as you go up LOD's. Say we have 16x16x16 leaves, so assuming we do what you said, we would sample 32x32x32 times. So in essence, a LOD 2 would take as many samples as an LOD5. The only reason I don't think it's done this way is because in the videos, the larger octs seem to take a lot longer.

      Delete
    20. Well, if he only has four cores, he's going to dedicate them to the four highest LODs first.
      Are you sure that's not all you're seeing wrt delay?
      Btw, which video are you referring to?

      What you've stated about sample numbers is in sync with my understanding, each LOD is the same size (give or take boundary stitching).

      Delete
    21. Number of sample points is constant regardless of LOD.

      Not sure from where you got this idea some cells take longer that other to generate. Can you specify?

      Delete
    22. I just assumed you were sampling at the finest level even for larger octs because you are able to retain those thin trees in the distance. This is apparently not the case. So if you have a thin tree completely within a large oct, and you only sampled the corners, you could totally miss it. If you sampled at the finest level, you would be able to detect it, but again this is not the case. So do you have some way of detecting a thin feature within a larger oct? I see that manifold dual contouring can allow this, as it allows more than one vertex per oct.

      http://faculty.cs.tamu.edu/schaefer/research/dualsimp_tvcg.pdf

      Delete
    23. I'm sorry, manifold DC is mostly for dealing with the nonmanifold surfaces, not dealing with preserving fine features. Getting my stuff mixed up!

      Delete
    24. @Anonymous Miguel posted in August that his solution for distant trees and LODs was to make sure each trunk surrounds a very coarse edge. If you are verrrry careful you can presumably detect that the distances between trees have a large common denominator.
      http://procworld.blogspot.com/2013/08/lean-trees.html

      Delete
    25. I guess I'm just wondering if simplification is done via filtering like on 0fps, or the article I posted.

      Delete
  9. This comment has been removed by the author.

    ReplyDelete
  10. Hi Miguel,
    I have a question which might be difficult for you to answer, but I would appreciate any insight you can give in this matter.
    Whenever I look at you videos and images I am astounded by how immersive and beautiful the world are. And that's not just the technical quality of your stuff but also how convincingly real the landscape and environment feel.
    However, when I play any of the available games where your tech has somehow been used (T.U.G and Starforge) I am slighly let down by the procedural world represented. Neither game has a world as believable/beautiful as the one shown in your material. Also, the performance of both titles doesn't in any way match the performance seen in your videos.
    I understand that T.U.G has chosen another direction for its style and that both games are very much works in progress. But could you in anyway elaborate on what can realistically be expected regarding the looks and performance of VoxelFarm environments once one starts putting a game on top of it? And also why there is such a gap in visual fidelity between those games and your output?
    I appreciate your blog very much and am following it with great interest. Your tech will possibly be part of the next paradigm shift in games.

    Best regards,
    Emil

    ReplyDelete
    Replies
    1. It is actually simple. But before getting into specifics, note I cannot elaborate on why you feel the environments in TUG and StarForge lacking. This is subjective and different people may have a different feel.

      The TUG alpha you have played does not use VoxelFarm anymore. They licensed the engine in full source code and study it, then chose to write their own solution from scratch. So what you see there is not VoxelFarm.

      As for StarForge, they do use the engine but since it is still a work in progress they have not tuned the generation yet. I believe they still have one type of terrain (equivalent to what I had back in January 2013), only one biome, not much variety in terms of materials, plants, etc. It also does not help they are running a much older version of the engine (version 1, from Jan 2013) which does not compare favorably with the latest version you see in my videos, or the videos from EverQuest next.

      To sum it up: Starforge is still working on it, TUG chose a very different path.

      Delete
  11. This comment has been removed by the author.

    ReplyDelete
  12. This is great, I loved your jab at Pine Trees :)

    Instancing directly from Mesh is great to have in the engine, it will simplify the delivery pipelines for your future developer base.

    Despite the absolutely stellar world generation you have created in the engine, and the algorithms you've been perfecting over the years, some "details" in the world will need the instancing capability to bring the visual fidelity even further.

    You touched on the megabyte footprint of an instance. Can you briefly expand upon how this impacts performance? Ie. how many of these "instances" do you think is reasonable/realistic under current hardware? 2-5 or 20-50?

    The reason I ask, is to get a feel for the art design thought process that will be needed, to evaluate how many instances can be added, for those things that the world generation won't do.

    Like the following hypothetical: "We've identified how we're going to generate the alien world looking world. We need to add a number of 'tree' types that we can't produce with the standard L-system model, plus we've got those alien 'anthills' peppering the landscape, the rock up-thusts, and the unique shiny metallic 'boulders' that fell to the ground eons ago before the planet's nebulous atmosphere emerged."

    Don't waste much time on this, I just thought it'd be interesting to know how much or little the instances should be used to fill out the landscape :)

    Great work as always!

    ReplyDelete
    Replies
    1. I believe the answer is, it is up to the game developers discretion. It is my understanding that the instances can be procedurally generated as well. So this way you can fill a world with as many unique plants/rocks as you wish and the memory/loading impact is affected by the quantity/complexity of the types of instances rather then individual instances.

      Reading through the blog, it appears as if Miguel is currently revamping his instancing base so that procedurally generated cities/etc have a firm foundation to be developed off of.

      Delete
    2. This demo is using 31 instance objects, including rocks and trees. They take around 90 Megs in RAM. They are compressed and they are used in compressed form. The compression ratio is around x10, so we are talking about 900 Megs worth of voxel data.

      Each instance has a palette of materials, so you can have the same instance rendered using different properties. That gets some additional mileage from the instance set.

      The compression can be improved a lot. I did not have the time or need to do a second iteration on this yet.

      Delete
    3. @Robin, Yes, sounds awesome, this kind of emphasis will pay off for him. I loved the recent discussion re: roads and rivers... and Miguel's response that he would post more later gave me chills! :)

      @Miguel, Thanks for the detail... sounds very promising!

      Delete
  13. OMG screenshots are amazing...

    ReplyDelete
  14. Hi Miguel,

    Out of curiousity, how many hours a week would you say you have been dedicating to this project?

    ReplyDelete
  15. Ah, thanks thats good news, I am sort of at the beginning of a similar undertaking. But with work and family the going has been pretty slow, so I was wondering if a project of this magnitude is even achievable.

    ReplyDelete
  16. Can you move objects with a character?

    ReplyDelete
  17. So, will this still be released as some kind of Unity asset or are those plans scrapped now with EQ's licensing?

    ReplyDelete
    Replies
    1. Not sure about the Unity asset store at this point. If we had a full C# port could make sense. For now it is running as a DLL, which limits it to Windows and Unity Pro.

      Delete
    2. Perhaps it can be recompiled for more platforms? Mac shouldn't be too hard and given how advanced it is, I think mobile platforms can be ruled out. Needing the Pro version isn't a problem for a lot of people I think.

      What about general licensing for use with whatever engine? That is, to release a dll and the .h files needed to use it and provide some kind of flexible licensing, like cryengine?

      Delete
  18. I was wondering for quite a long time, where did your buildings go???
    Your terrains are always amazing but buildings and huge cities just seem a whole lot more interesting... I miss them :(

    I have a few technical questions :) :

    1) Voxel instancing is an interesting concept, albeit very memory consuming. What if you instance just the 3d models and then voxelize them if anything gets edited?

    2) Are you going to add some interactive/dynamic elements to the engine?

    3) How do your instances/buildings integrate into the world? Do you just replace (or do a union) the voxels/generation function if the coordinates fall into the instance's collision box?

    4) Are trees completely out of voxels? Even the branches?

    ReplyDelete
    Replies
    1. Buildings are coming back big time, don't worry.

      Your questions:

      1) I do this in some cases. Problem is voxelization is slower. I only use it for the output of LSystems (like in buildings) where it covers larger spaces and you certainly need each instance to be different. With instancing can do a massive number of entities at very little processing cost.

      2) Like making a hole in a building? :)

      3) It is a union.

      4) Tree trunks and their branches are voxel. Leaves are sprites.

      Delete
    2. @Miguel said, "Buildings are coming back big time, don't worry."

      Woo Hoo!!! The scenery has become beautiful, fantastic really... but you captured my undivided attention with a voxel cathedral and city states :)

      Delete
  19. I have found instancing to be invaluable, and there are many ways to use it while still preserving variation. When you think about it, it really is all just another form of compression - you take groups of similar properties and reference them rather than making copies of them. The design pattern that best applies to this is called the Flyweight pattern.

    http://en.wikipedia.org/wiki/Flyweight_pattern

    ReplyDelete
  20. Flyweight?

    http://www.youtube.com/watch?v=Qw9oX-kZ_9k

    ReplyDelete