Sunday 28 September 2014

Dual Contouring: Seams & LOD for Chunked Terrain

There was a mistake in the original version of this post, the second last selectionFunc was a duplicate of the previous entry in the table. The table has now been corrected. Apologies to anyone who was tearing their hair out trying to debug that one!

Introduction

A couple of years ago I read these blog posts (1, 2) on 0 FPS, and like a lot of programmers decided I should write one of these voxel renderers. I implemented Marching Cubes first, but I was unhappy with the way terrain looked using MC -- it was far too blocky. I then implemented Naive Surface Nets and was pleased that I now had smooth terrain, but I soon discovered that Surface Nets couldn't support sharp features, like a 90 degree angle. That meant it would never be possible to have both a smooth terrain and a realistic looking building produced by the Surface Nets algorithm. I was aware of Dual Contouring from the 0 FPS posts, and my main source of information Miguel Cepero's Procedural World blog. Dual Contouring sounded like a significant step up in difficulty from Surface Nets, and I was quite skeptical about how feasible it would be to use Dual Contouring in a game. I never tried to upgrade my renderer to use DC and my interest in the project faded.

Then about a year ago, EverQuest Next was announced. Far from using blocky Minecraft style graphics EQN looked like a typical AAA game. I wanted to know how this was possible, and quickly discovered that I already knew -- it was based on the Procedural World project. I realised Miguel was really on to something here, and the next day started on a new voxel renderer. I set myself a goal: learn how this technology worked by creating a Dual Contouring renderer that would be capable of handling large terrains.


It's taken quite a while but I achieved my goal, and my renderer can produce large destructible terrains, like this one:

Early on I ran into one of the major problems with using Dual Contouring to generate terrain. Rather than looking like the finished version in the picture above, my terrain was full of cracks.


Initially I used a nasty hack to work around this problem, and went on with other features. The hack annoyed me and caused a lot of complications. I knew to achieve the final goal I would need to solve the problem properly. The remainder of this post explains the problem in detail and the solution I eventually implemented.

The Problem

It’s not practical to store the entire world as a single entity, attempting to do so with such a large terrain will very quickly lead to poor performance as the size of the data and the time required to process it grows and grows. To work around these performance problems the standard technique is to organise the world space into a grid of equally sized cube chunks. Each chunk is responsible for representing a small part of the world, and can be processed in isolation. Using chunks allows modifications to the terrain to be processed quickly, and provides a starting point for building a Level of Detail (LOD) system.


In order to create the mesh for the terrain, each chunk is responsible for generating a mesh which represents the terrain inside the chunk’s bounding box. To generate the mesh an octree is constructed. The first stage in the octree generation is to evaluate each 1x1x1 cube, or voxel, which exists inside the chunk’s bounds. If any of the voxels is determined to contain the surface of the terrain then a leaf node of the octree is generated, with each leaf node containing a single vertex of the terrain mesh. Once all the leaf nodes are created the octree is constructed upwards until the root node (which has the same bounding box as the chunk) is created. The octree can then be traversed (or contoured) to produce the mesh for each chunk.


I then ran into the problem: there were cracks in between the individual meshes I had generated. I was a bit confused by this: I had organised the terrain into chunks, with each chunk generating a mesh. There are no gaps between the chunks, so why were there cracks in the mesh?


I often find the easiest way to think through a problem is to consider the simplest case possible. Here the problem is cracks appearing in the terrain, so I’ll use the simplest terrain possible to think through the problem. The simplest terrain is a flat plane, e.g. height(x, z) = 100, which will generate a flat plane along the x and z axes through the points where y = 100. It looks like this:



Using this flat plane terrain makes thinking about the problem easier. We can essentially think about the problem in 2D, with quadtrees instead of octrees. Each chunk can then be imagined something like this:

The thick black line represents the chunks' bounding box. The thin grey lines represent the leaf node, with the red circles representing the vertices belonging to the nodes.

When the mesh is generated each chunk , and so each octree, is considered in isolation. The generated meshes will then look like this:

Triangles are generated by connecting the leaf nodes' vertices

The Solution

The cracks in between the meshes are caused by the contouring each chunk's octree without considering the neighbouring octrees. In order to fill in the cracks these nodes would need to be contoured as part of the same octree.

Nodes which contribute to the seams are highlighted blue

Again using the flat plane terrain as a model, we can imagine the chunks in the world laid out like a grid. Each square in the grid also contains another smaller square, representing the mesh. In order to render the terrain properly, all the cracks between the chunks need to be filled in, creating a seam. Ideally each chunk would be responsible for a small part of the seam which would allow the global problem of the cracks to be localised, with each chunk handling a piece of the seam. This would mean that the advantages of the chunked approach (reducing the size of data sets, enabling parallelisation, etc) would not be lost while solving the cracks problem the chunks introduce.

A grid of chunks. The black line represents the chunk bounding box, and the green squares represent the mesh

After a few false starts, I realised there was a way to organise the seam for the flat plane which would allow all the cracks to be removed while also keeping the generation of the seam a responsibility of each chunk.


If you imagine a sort of L shape being attached to each chunk then the gaps between the mesh will all be removed, without any overlapping being introduced:

A seam is added for the bottom left chunk.

By having each chunk generate and be responsible for a small piece of the seam, a full mesh for the terrain can be created and managed without adversely affecting performance.

To generate the seam for each mesh we need to first collect all the nodes which could possibly contribute to the seam. I think the easiest way to manage this is to construct the seam on the maximum faces & edges of the chunk’s bounding box. We need to consider the chunk itself and the seven neighbouring chunks which share a face or an edge. In order to avoid creating overlapping meshes we need to ensure that only nodes which contribute to the seam are selected. Going back to the flat plane terrain again, we can work this out.


First we need to select any nodes in the chunk which have either the maximum x, y, or z value which matches the chunk’s own maximum x, y, or z value.

Leaf nodes are selected from the chunk

Next from each neighbour we need to select the nodes which are adjacent to the original chunk. For the chunk which is adjacent on the x axis this would be any node which has a minimum x value equal to the maximum x value of the original chunk:


Leaf nodes from the X-axis neighbour are selected
Then for the Z axis:


Leaf nodes from the Z-axis neighbour are selected
And finally the X and Z axes:


A single leaf node is selected from the X & Z axes neighbour

This process can be extended to three dimensions and 7 neighbours, each with a relevant selection criteria. I often find code easier to understand than descriptions. This is C++11.

vector<OctreeNode*> FindSeamNodes(Chunk* chunk)
{
  const ivec3 baseChunkMin = chunk->getMin();
  const ivec3 seamValues = baseChunkMin + vec3(CHUNK_SIZE);

  const ivec3 OFFSETS[8] = 
  { 
      ivec3(0,0,0), ivec3(1,0,0), ivec3(0,0,1), ivec3(1,0,1), 
      ivec3(0,1,0), ivec3(1,1,0), ivec3(0,1,1), ivec3(1,1,1) 
  };

  auto selectionFuncs[8] =
  {
    [&](const ivec3& min, const ivec3& max) 
    { 
      return max.x == seamValues.x || max.y == seamValues.y || max.z == seamValues.z;
    }
    
    [&](const ivec3& min, const ivec3& max) 
    { 
      return min.x == seamValues.x; 
    }
    
    [&](const ivec3& min, const ivec3& max) 
    { 
      return min.z == seamValues.z; 
    }
    
    [&](const ivec3& min, const ivec3& max) 
    { 
      return min.x == seamValues.x && min.z == seamValues.z; 
    }

    [&](const ivec3& min, const ivec3& max) 
    { 
      return min.y == seamValues.y; 
    }
    
    [&](const ivec3& min, const ivec3& max) 
    { 
      return min.x == seamValues.x && min.y == seamValues.y; 
    }

    [&](const ivec3& min, const ivec3& max) 
    { 
      return min.y == seamValues.y && min.z == seamValues.z; 
    }
    
    [&](const ivec3& min, const ivec3& max) 
    { 
      return min.x == seamValues.x && min.y == seamValues.y && min.z == seamValues.z; 
    }
  };

  vector<OctreeNode*> seamNodes;
  for (int i = 0; i < 8; i++)
  {
    const ivec3 offsetMin = OFFSETS[i] * CHUNK_SIZE;
    const ivec3 chunkMin = baseChunkMin + offsetMin;
    if (Chunk* c = GetChunk(chunkMin))
    {
      auto chunkNodes = c->findNodes(selectionFuncs[i])
      seamNodes.insert(end(seamNodes), begin(chunkNodes), end(chunkNodes));
    }
  }

  return seamNodes;
}

The selectionFuncs array holds a lambda function that is used to select only the relevant nodes from each chunk’s octree. The findNodes function is quite simple. Due to the octree structure all parent nodes of the seam nodes that are to be selected will also meet the selection criteria from selectionFuncs[i].
void Octree_FindNodes(OctreeNode* node, FindNodesFunc& func, vector<OctreeNode*>& nodes)
{
    if (!node)
    {
        return;
    }

    const ivec3 max = node->min + ivec3(node->size);
    if (!func(node->min, max))
    {
        return;
    }
    
    if (node->type == Leaf)
    {
        nodes.push_back(node);
    }
    else
    {
        for (int i = 0; i < 8; i++)
            Octree_FindNodes(node->children[i], func, nodes);
    }
}

typedef std::function<bool(const ivec3&, const ivec3&)> FilterNodesFunc; 

vector<OctreeNode*> Chunk::findNodes(FilterNodesFunc filterFunc)
{
    vector<OctreeNode*> nodes;
    Octree_FindNodes(octreeRoot, filterFunc, nodes);
    return nodes;
}

Once all the seam nodes have been gathered, a new octree can be created which contains all the seam nodes. The octree is then used to generate a new mesh just as the chunk’s octree was originally. Repeating this process for each chunk ensures that there are no cracks between the chunk meshes.
Four chunk seams have been generated, filling in the cracks
Unfortunately this scheme does introduce a dependency between the chunks. If a chunk modified then its possible that a seam owned by a neighbouring chunk may need to be updated too. Modifications to the terrain are constrained by a bounding box which allows most of these potential updates to be skipped -- they are only necessary when the operation bounding box is near a particular neighbour.


One of the features of the Dual Contouring method is its support for simplifying (i.e. removing triangles) from the extracted mesh. The simplification process is an operation performed on the octree whereby leaf nodes with a common parent are removed and the parent node replaced, creating a new leaf node twice the size of the removed leafs. There are a few different ways I can think of to use the simplification to create different levels of detail, for now I’m using the simplest one I could think of. Each LOD (starting from 0) all existing leaf nodes are removed, and their parents are replaced by new leaf nodes. Each round of simplifcation reduces the polycount farily significantly, which allows for a really basic LOD system. The current detail level for each chunk is calculated based on the distance to the camera, so that as the distance increases the chunks use a more or less simplified mesh.


As a consequence there will be neighbouring chunks with differently sized leaf nodes:
Neighbouring chunks with differently sized leaf nodes

Typically when dealing with voxel-based mesh generation this a tricky problem to solve. If you’re using Marching Cubes you’ll need to use something like the TransVoxel algorithm to be able to stitch the chunk meshes together, for instance. In this case however, we don’t need to do anything different at all -- the Dual Contouring algorithm works with the differently sized leaf nodes in each octree. The process is exactly as before, all the seam nodes of the neighbouring chunks are gathered, a new octree is constructed and the mesh generated. Just as before the seam mesh completely covers the crack without generating any overlapping polygons.
Chunks with different levels of detail are stitched together by the seams


63 comments:

  1. Great post! I have pretty much the same algorithm (I run simplify on everything first), one thing I have noticed as an artifact is that on the chunk boundaries if I have a flat surface the skirt ends up overlapping the something that the contourer also generated a triangle for. It hasn't been a problem yet (no z fighting) but its something I want to rid myself of eventually.

    Eg:
    https://drive.google.com/file/d/0B4dhc9v7qn-hTFVFZmFFQTNWSDA/edit?usp=sharing

    ReplyDelete
    Replies
    1. Thanks! Good to see other people using DC :) It's hard to tell from the screenshot, I think you meant the bits of the mesh that don't contribute to the grid shape? Could it be that those are the seams, but they are on the Y axis and just happen to cover quite a large area? That is the surface just happens to be right on the shared face of two chunks -- in that case it would be correct. Unless those areas are there when you draw without the seam/skirts, that is :)

      Delete
  2. Very nice :)
    Could you do a tutorial on implementing Dual Contouring? I am trying to but can't figure it out :( Especially the QEF...
    Would be very nice! Afaik, there is no tutorial on that so far.
    Have a nice day!

    ReplyDelete
    Replies
    1. I think my second post should cover that: http://ngildea.blogspot.co.uk/2014/11/implementing-dual-contouring.html

      If not feel free to ask some more questions and I'll try to answer them :)

      Delete
    2. Thank you so much! I think you provide just what I need! Except maybe an explanation on how to write the algorithm to solve QEF's, but apart from that, combined with your reference code, awesome! Thanks again :)

      Delete
  3. I don't understand how do you add the seam nodes to the new Octree... I mean the seams nodes should be the leaves of some internal node but you don't keep track of that. According to the code you have provided in the second post I cannot understand how to regenerate the mesh using the new seam nodes because I don't know how to generate a new octree that also has the seam nodes. Can you explain please?

    ReplyDelete
  4. The seam nodes are leaf nodes of the chunk's octree. For each chunk you collect all the seam nodes for that chunk, then collect the seam nodes from each of the neighbour chunks. At this point you have a collection of leaf nodes which make up the seam.

    The next step is to construct a brand new octree using only the collected nodes. You do this by constructing the octree upwards, starting from the collected leaf nodes. Typically the root node of this octree will be twice the size of a chunk.

    Once this octree is created the contouring algorithm is run as before, generating the mesh data (vertices & triangles). Once this is done you can discard the octree.

    There are some more subtle details, e.g. whether to clone the leaf nodes or just re-use the existing ones, but that is the general idea. Hope that helps!

    ReplyDelete
    Replies
    1. Does the construction of the new octree weigh on the computation? I mean constructing a new octree with the size equals to double of the size of the original octree starting from the leaf shouldn't be computationally heavy?
      If you discard the octree after the generation of the mesh, then how can you modify the mesh if some modifies are applied to the seam?
      Maybe I missed something. Some code could help. Thanks for your great help!

      Delete
    2. Its not free of course but it shouldn't be too expensive. I have a background thread that handles the edits and the LOD switches.

      When a modification happens I throw away the current octree and build a new one from the updated chunk data. The octree is then available if I need to generate a new mesh for the LOD switches. Currently I solve the QEFs for all the nodes up to a certain node size (currently size=16 I think) so that I can set the nodes as "active" for the current LOD or not, i.e. for LOD 0 the size=1 nodes are active, for LOD1 the size=2 nodes are active, etc.

      I'm not sure how viable that is for you in terms of performance. I have some other ideas that I'm planning on trying out.

      Delete
  5. "The next step is to construct a brand new octree using only the collected nodes. You do this by constructing the octree upwards, starting from the collected leaf nodes. Typically the root node of this octree will be twice the size of a chunk."

    is there any chance you can go into detail how you do this? or even share the code?

    ReplyDelete
    Replies
    1. Do you mean the whole thing or just the octree construction?

      Delete
    2. the octre construction, i have the seam nodes in list but i cant find a elegant way to build up the octree for DC,
      i try to create a empty octree and fill in the nodes from upside down, but somehow it gets a mess...
      now i wanna start from scretch but i cant find a direct way without iterate through the list over and over again

      Delete
    3. Ok. The key thing is to realise that because the octree is regular we can work out the size and min position of the parent of any node.

      The parent's size is easy, just 2 * node->size. We can then use that size, node->min and the chunk min to calculate the parent's min value. I.e.

      ivec3 parentPos = node->min - ((node->min - chunkMin) % parentSize);

      That first moves the node's min position into local space then mods it by the parent size such that each element has the value either 0 or node->size. If we subtract that from node->min then we'll get the parent's min value.

      (This is like doing construction of the nodes in the downward build, but backwards. There the code is something like child->min = parent->min + (child->size * CHILD_MIN_OFFSET[i])).

      Once you've can calculate the parent min for any node its easy: you iterate through your list of node and find the parent min for each one. Create the parent node the first time it's needed and update the child nodes as appropriate. Repeat that until you run out of nodes or hit a specific size for the root node.

      Delete
    4. thank you very much for your reply, ill give it a try tomorow (its 23:30 here ^^)

      are you still into your voxel project? its sad there is only 2 blog posts here.
      i can't find alot people using dual contouring and refering to code as much as you do

      Delete
    5. Cool, let me know how you get on.

      Yep, still working away on it. The latest thing I've been doing is a change to how the LOD system works combined with a different approach to the mesh simplification, now doing that using an edge collapse method rather than via the octree.

      Yeah, I know there are not many sources which was one of my motivations. And I also find it annoying when there's no source so I've tried to be as explicit as possible. I often find code easier to understand than a natural language explanation. I have been meaning to do some more posts, is there anything in particular you want me to talk about?

      Delete
    6. What confuses me most is how this placing of stuff inside the voxel will be done at the end.
      Will it all come to placing density functions inside the world?
      When they place whole buildings in voxelfarm is this all density functions? or are there are easyer aproaches?
      i came up with the idea of using 3dim voxel arrays and the density function would just be a hashfunction into this array but im still not at the point to test this stuff.
      So would be interesting to know how you think about this stuff if you already have some ideas.
      Otherwise you could also just connect to the "tutorial" like style and just extend the code project. I think there is no other Voxel Tutorial with full source out there and voxel attention is growing and growing

      Delete
    7. it seems i still havent understood your explaination complete

      http://pastebin.com/pNDr94wT

      im at this point right now, okay i now know i can create the parent node, but how im supposed to save my parent notes?
      will i create 1 tree and always go through this tree and check if the parent node already exist?
      or will i save them into a list and go over that list again doing the same?
      it seems i have huge problem to get this "building tree upwoards" into my head...i never implemented this befor just used it in algorithms ^^

      Delete
    8. Well I've not got that far myself yet but I think Voxel Farm produces polygonal models which are then converted into a density field. That can then be imported into the work by doing something like a CSG add operation.

      Yes that's the start of it. You need to keep the parent nodes in a structure so you can look them up as needed (e.g. a hash map) and update the child pointers. For each level of the octree you'd have a new collection of parent nodes (since the output of one round is the input of the next).

      Delete
    9. okay thank you alot. i hope i can work it out tomorow, so i can go on ^^ so much work for some small seams xD

      its so bad i first implemented everything in marching cubes and i where much much further into this project...but then i realized marching cubes wont fit at the end...eventho my octree marching cubes was realy fast compared to the DC implementation i got right now

      Delete
    10. http://pastebin.com/zZaKRRsU

      here is the ugly scetchy version of my seamOctree creation.
      But it seems that i dont get the childs into the right index.

      inside the public void ContourEdgeProc(OctreeNode[] node, int dir, List indexBuffer) function where u select the edgeNodes
      for ContourEdgeProc it doesnt select the right positions (but it does for your normal build octree)
      so i think i somehow mess up putting the leaf nodes into the right child nodes? but i can't find the misstake. i never get 4 edgeNodes without one beeing null and therefore my seam has 0 indices (the vertice list seems correct)

      Delete
    11. do you see the misstake i do? eventho its very ugly and c#

      Delete
    12. Nothing jumps out at me, but you are finding the child index differently. I just do something like this:

      int index = -1;
      for (int i = 0; i < 8; i++)
      {
      ivec3 childMin = parentPos + (childSize * CHILD_MIN_OFFSETS[i]);
      if (childMin == node.min)
      {
      index = i;
      break;
      }
      }

      assert(index != -1);

      You should make a test case and step through it with a debugger to make sure its generating sensible results. E.g. create a leaf node at (0,0,0) and make sure you can construct any number of parents, then try with 2 nodes etc and see if you find where it breaks.

      Delete
    13. yeah your indexing seems to fix it.
      the seams work great but now i have 2 spots where squares misses and its so anoying to find this misstake in debugging :-/ i realy dont understand since all other seams work great

      Delete
    14. oh nvm, i think i got it. the two holes would have been filled by another seam, but the chunks for this seam are not all created.
      only have 2x2x2 chunks atm ^^ stupid me

      Delete
    15. how do you controll the maximum lod? i thought it would be enough to set a limit for the min size but somehow i dont get anything usefull for a different setting then 1 as min size

      if (node.size == node.minLOD) {
      return ConstructLeaf(node);
      }

      isn't it enough to replace this in constructnodes and construct leav nodes?

      Delete
    16. oh it seems that the lod setting is correct, but somehow my seam generation doesn't work with different size chunks O.o

      Delete
    17. I'm not sure what you mean. What I do is create the 'drawinfo' for nodes up to a certain size (I think up to size=16 atm) by adding together all the child QEFs and then solving for the node. You then need to be careful to only traverse the tree to a certain depth when doing the mesh generation steps. E.g. at LOD1 you might traverse to all the size=2 nodes, for LOD2 the size=4 nodes, etc.

      Delete
    18. it seems that i complelty missunderstood your blogposts about the implementation. Nothing works as i expected it to work :-/ maybe i should have done it from scratch in the naive way how ive done it with machring cubes.
      I just dont get this octree implementation in my mind...
      I still have overlapping faces in my seams and i dont know where they come from and also some holes.

      and i thought it would be enough to only create leave nodes at the deph of the tree where i want my minimum size when building the octreenodes. i dont understand why i need to create all down to size 1 and then add the low LOD drawinfos additionaly in the parent nodes by adding the child nodes together?

      Delete
    19. Well you seem to be describing the process backwards for one thing. You don't create "create down" to the size=1 one nodes as those are the initial nodes you start with. Its not possible to generate any other size of node on the tree without first creating the leaf nodes. (You could of course create say the size=4 nodes directly by sampling at that size but you've just traded one set of problems for another.)

      Is is possible you're using the wrong node size when generating the seams? E.g. if you are creating the seam for a chunk, when selecting the nodes from a neighbour you must select the nodes according to the neighbours' current LOD setting not the original chunk. So your input to the ConstructUpwards method would be a set of nodes with possibly varying sizes. E.g. you may have the chunk nodes which have size=1 and then neighbour nodes whose size=2. You need to handle that case when constructing the octree upwards too.

      Delete
    20. when i create the seam tree i give the function a number for size starting with 1 and incrementing every function call with new parent list.
      when i check my seam nodes, if the node size is > actual checking size i just put it into the parent node list without changing, only if size == checking size i create a parent note if its not already in parent list, otherwise i just put into existing parent node.
      i thoght that would solve the case you descripe.

      i think the main problem is that i do what you said, i just sample the depht function at size == lod nodes when creating my trees instead of building them all the way down to 1 and combine them upward to the target lod.
      at the moment i dont realy get it how to do it, eventho you already descripted it very detailed.
      i think i have confused myself to much atm

      Delete
    21. damn after one week i found the misstake wich made the last holes in my seams...and it seems its not a misstake by me.
      could it be possible that you posted a wrong version of your code?

      these lambda function cases are from your blog

      [&](const ivec3& min, const ivec3& max)
      {
      return min.x == seamValues.x && min.y == seamValues.y;
      }

      [&](const ivec3& min, const ivec3& max)
      {
      return min.x == seamValues.x && min.y == seamValues.y;
      }

      i think the second case should be return min.z == seamValues.z && min.y == seamValues.y;
      because thats the case you want there, and i always had a hole at the max.z && max.x cases, changing this filled the holes.

      Delete
    22. i meant i had a hole at the z && y stripe of the seams

      Delete
    23. Yeah it does look like a repeated case. I'll need to double check it against the actual code. Have you got it working then?

      Delete
    24. Check it against the my code and yes it is indeed a mistake! I'll update the post.

      Delete
    25. yes i replaced the case with the real one and all holes where closed

      Delete
    26. is there a chance you can post the function where you create the lod nodes?
      my implementation looks pretty much like simplify octree but it somehow messes up my whole tree when executed xD

      http://pastebin.com/b9AqicFT

      Delete
    27. Here's mine: http://pastebin.com/b9AqicFT

      I couldn't see anything obviously wrong with yours. Do you mean the mesh generation goes wonky, or the actual structure of the tree gets messed up? My func assumes that the all the nodes already exist and so its just changing the type of some and adding a drawInfo, not actually altering the structure of the tree (in terms of adding/removing nodes, setting child nodes etc).

      Delete
    28. Oh, and FindDominantMaterial just does what you'd expect, counts the material at each corner and returns the highest.

      Delete
    29. yeah i already managed it,i forgot to change the seamchunk creation to also search for the new lod nodes ^^

      but it was anyways interesting to see yours with the material id's.

      it would be very interesting if you could make a blogpost about multimaterials and material blending. I find very less about this and finaly the best solution i found was creating 3 copys of each triangle that contains differen materials, and texture them acording to the blending and with one of the materials per triangle

      Delete
    30. I've started writing the next post, an overview of the engine as it works in the latest video. I'll make sure to include a section on the material stuff.

      Delete
    31. very nice, can't wait to read it.

      i now run into the problem that GenerateMeshFromOctree treats my Lod nodes as Leaf/Pseudo nodes...
      somehow i cant figure out to get GenerateVertexIndices and ContourCellProc to skip the lod nodes that have a size bigger then a minSize

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

    ReplyDelete
  7. Thanks so much for going over this topic in such depth. Its been a lot of help!

    ReplyDelete
  8. What's the advantage of generating a whole new seam octree to fill the holes instead of just pushing the existing octrees closer together?

    ReplyDelete
    Replies
    1. The octrees exactly divide the space, they're already as close as they can be. What you describe would be overlapping the octrees. That might work but I can imagine there would be artefacts at the seams.

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

    ReplyDelete
  10. What reason of this error?

    Viewer_Initialise
    Build program failed: CL_BUILD_PROGRAM_FAILURE (-11)
    Error: unable to build density field program for voxelsPerChunk=64
    'CL_BUILD_PROGRAM_FAILURE' (-11)

    ReplyDelete
  11. deep debug show me so:
    "C:\Users\username\AppData\Local\Temp\OCL6596T3.cl", line 295: catastrophic error:
    cannot open source file "cl/hg_sdf.glsl"
    #include "cl/hg_sdf.glsl"
    ^
    1 catastrophic error detected in the compilation of "C:\Users\username\AppData\Local\Temp\OCL6596T3.cl".
    Compilation terminated.
    Frontend phase failed compilation.

    Is anybody know about reason?

    ReplyDelete
  12. Nothing works in VS 2019.
    Problems with all the latest libraries for 2019
    Remotery, Bullet Physics, Dear ImGui, OpenCL SDK, GLEW, GLM, SDL.

    All source need to be refactored to actual in 2019 VC++ and libraryes.

    ReplyDelete
    Replies
    1. I assume you are talking about the code I've released for the project, but you don't actually state this.

      I'm not responsible for the external libraries, I imagine they have some sort of solution for using them across different versions of VS, or you could compile each of them (using later versions if the ones I've used don't compile).

      As for code in the project not being compatible with VS2019 you'll need to fix that yourself.

      Delete
  13. I tell about https://github.com/nickgildea/leven
    This is the most interesting and detailed voxels project of all that I have met. Unfortunately, under VS2019 and under VS2013 there are errors in cl scripts. I solved the problems with the Remotery, Bullet Physics and Dear ImGui libraries simply by disabling them, but unfortunately I failed to fix deep compiler errors in cl scripts.

    ReplyDelete
    Replies
    1. Ok. I'm glad you like it.

      Sorry I can't be much help with the OpenCL problems. Is it possible you are missing a file or have the layout incorrect?

      "C:\Users\username\AppData\Local\Temp\OCL6596T3.cl", line 295: catastrophic error:
      cannot open source file "cl/hg_sdf.glsl"
      #include "cl/hg_sdf.glsl"

      Assuming the above error is still the problem. If there's a different error if you paste it here I can try to help.

      Delete
    2. You'd see the above error if the files aren't in the expected places. You should have a layout like this:

      ./assets/
      ./cl/
      ./shaders/
      ./level.exe

      That is those 3 folders should be siblings of the executable. If you've just built it in VS and tried running it you'd get that error. You can make VS launch in the correct directory in the Debug settings, something like "working directory" or "starting directory" (by default it'd be the Release/ folder).

      Delete
    3. Unfortunately, it turned out that OpenСL works differently on different video adapters. On some, it's ok. On others - errors in OpenСL scripts.

      Delete
  14. Even the executable file prebuilt-win64.zip does not start. It said:
    Viewer_Initialise
    Build program failed: CL_BUILD_PROGRAM_FAILURE (-11)
    Error: unable to build density field program for voxelsPerChunk=64
    'CL_BUILD_PROGRAM_FAILURE' (-11)

    ReplyDelete
  15. Hi Nick,
    Thank you for post this blog. Btw, could you share the full source code for this?
    Many thanks.

    ReplyDelete
    Replies
    1. Hey, yeah all the code is here https://github.com/nickgildea/leven

      Delete
    2. Thank you, Nick.
      Btw, How can modify the code to disable the LOD processing? In other words, I want to see high detailed terrain regardless the eye position.

      Delete
    3. Ahh, I've get it by replace `if (nodeDistance >= d)` with `if (node->size_ < 512)`. It works. Amazing.

      Delete
  16. My solution https://www.youtube.com/watch?v=ewr7YZyBYnI
    (github under video)

    ReplyDelete
  17. This comment has been removed by the author.

    ReplyDelete
  18. Fantastic write-ups. I'm trying to understand some key differences between marching cubes & dual contouring, so correct me if I'm wrong: it appears that dual contouring does NOT have the same issue as marching cubes for generating huge amounts of (essentially) duplicate vertices, resulting in highly non-manifold meshes. By "duplicate vertices" I mean vertices generated at identical or near-identical positions that could have been 1 vertex shared by triangles instead. In my experience, MC seems to create these at almost every(?) vertex generated regardless of voxel field input, which makes smooth shading impossible. On the other hand, my research seems to indicate that DC only creates non-manifold meshes in particular cases of the SDFs used, such as if the input shapes are smaller than the cell size that a single voxel represents. Let me know if that's true about DC or if there's something I'm misunderstanding.

    ReplyDelete