Sunday 26 July 2015

Fixing a seams bug

I've been sitting on the "fix" for a bug with the seams for a while now, and since I can't figure out a better solution I'll share my current one.

The problem is that with my seams implementation described in the first post some configurations of chunks will cause additional polygons to be generates for the seam, causing an overlapping effect.


In this image the seams are all drawn in red and the main mesh in blue. You can clearly see the seam running down the middle of the screen is way too big, its about 10 or 12 voxels across at some points rather than just the two voxels (one from each chunk) we'd expect based on my first post.

This problem didn't become apparent until I started simplifying the main meshes. The mesh simplifier didn't work very well on the left hand mesh and so its almost entirely the original input mesh, the only reason the seam is visible is because I wiggled the camera around until the seam won the z-fight. That means the seam mesh exactly matches a part of the input mesh. On the right-hand side the simplifier did work and you can see the mesh and seam clearly don't match.

The problem is that my original algorithm produces an overlapping mesh when the surface happens to be close to chunk borders without actually crossing into the neighbouring chunks. Its a bit hard to explain with words alone so hopefully a couple of pictures will help.


I'll use 2D pictures since the same rules apply but they are much easier to draw. Here's the type of scenario I was imaging when I originally implemented the seams solution. There are seams between the 4 chunks here, and the nodes selected for each chunk are coloured. For each seam one node each is selected from the neighbouring chunks and the seam fills in the gap with no overlaps.


In this scenario there are cases where multiple nodes are selected from the neighbouring chunks. The two seams on the right-hand side are particularly bad with 3 & 4 nodes being selected. Selecting these extra nodes is problematic since the original algorithm goes like this:

  1. select all chunks nodes that touch the seam
  2. process all edges of all selected nodes to generate seam mesh
Step 2 means that when the seam with the red and yellow nodes is processed the red & yellow pair of nodes correctly generate the seam, and the red & yellow nodes match amongst themselves to produce an overlap with the original/main mesh.

When I first realised what the problem was I tried to solve the problem in step 1 by not selecting the additional nodes at all. That generally involved lost of convulated rules and not must success. I then realised I could solve the problem in step two: only process an edge from the seam nodes if at least two chunks were represented.

That is the reason I said "fix" in the first paragraph -- originally I thought this was a gigantic hack and there would be a much "cleaner" way to do this. But the longer I think about it the more this seems to be a valid solution, albeit fairly inefficient since all the selected nodes edges' are processed even if many will never produce a quad. 

The implementation for this is actually very simple, assuming the data layout I described originally: the data is contiguous and with no overlaps & each chunk can be uniquely ID'd by its minimum bounding box value. Those properties mean that given the min bounding box value for a node its trivial to determine which chunk it belongs to, and we have a unique ID to compare against the chunks the other 3 nodes sharing the edge belong to.


const ivec3 ChunkMinForPosition(const ivec3& p)
{
const unsigned int mask = ~(CHUNK_SIZE - 1);
return ivec3(p.x & mask, p.y & mask, p.z & mask);
}

Using ChunkMinForPosition we can get the chunk min for any position. In ContourEdgeProc this is added:

std::unordered_set<ivec3> chunks;
for (int i = 0; i < 4; i++)
{
chunks.insert(ChunkMinForPosition(node[i]->min));
}

// bit of a hack but it works: prevent overlapping seams by only
// processing edges that stradle multiple chunks
if (chunks.size() == 1)
{
return;
}


Before processing the edge gather all the chunk mins and ensure there are at least 2. Currently in my implementation the main mesh for the chunks is generated on the GPU so this code is only used to generate the seam mesh, if you still use the CPU code to generate the main mesh then you'll need to differentiate between the two and ensure you only do this check when building a seam mesh.

With that small addition the problem is completely resolved:


What do you think then: giant hack or neat solution?

11 comments:

  1. Replies
    1. The only thing I've released is the sample so far. I do have a vague plan to release the main project once I've cleaned some of it up though if that's what you're after.

      Delete
    2. Aye, I am. Looking to get into 3D game development with voxel-based environments, and I'm thinking of working either with C++ and Ogre3D, Python and Panda3D, or Haxe and H3D.

      Delete
    3. Cool -- sounds like your main aim is just to learn rather than trying to publish a game? I hope to get a release of this project out some time in the next couple of months, if you can wait that long. If you're wanting to get on with something in the mean time, you could start with my sample and try to expand it, that'll give you a good chance to learn a lot.

      On the other hand, if you just want a voxel engine you can use right now you might be better off having a look at Voxel Farm.

      Delete
    4. Voxel farm looks pretty nice, though because I might release my game idea under an open source license (maybe, maybe not), I'd stick to stuff that's friendlier licensing.

      Delete
  2. There seems to be a small problem with this solution.
    You avoid creating redundant quads within the same 2x2x2 chunk group, but there can still be overlapping polys coming from different groups.
    It's better to illustrate with a picture: http://imgur.com/a/RUo2K

    ReplyDelete
    Replies
    1. Thanks for the feedback.

      I'm not sure I 100% understand your point, but it looks like you have 2 overlapping chunks generating a seam, which may be where the confusion is.

      I don't think I'm getting any redundant quads because of the way the seam 'responsibility' is split between the chunks, you can see the sort of invert L shape this gives in 2D in earlier post.

      Delete
  3. This method helps, but not always. Artifacts sometimes appear. Any thoughts on what is the reason?

    https://imgur.com/ORGqpqT
    https://imgur.com/kcWRqab

    https://github.com/proton2/java-leven/blob/28c6847f4ac5f749f566fbacd2feed929da7517d/src/dc/AbstractDualContouring.java#L143

    ReplyDelete
  4. artifacts from seams appear on a steep mountainside

    https://imgur.com/O8raNb0

    ReplyDelete
  5. The following solution helped - disable the creation of polygons formed by cells belonging to neighboring chunks.

    // To avoid overlap seam mesh with chunk mesh. If all 4 nodes of seam belong to only one chunk, then this is not a seam.
    if(isSeam &&
    (node[0].getChunk().equals(node[1].getChunk()) &&
    node[1].getChunk().equals(node[2].getChunk()) &&
    node[2].getChunk().equals(node[3].getChunk()))
    ){
    return;
    }

    Thank man SVD https://sites.google.com/site/svdsprogrammerportfolio/home for advice!

    ReplyDelete
  6. https://github.com/proton2/java-leven/blob/e2c45af71620f160e6fe0ec3346f60a2ad80d117/src/dc/AbstractDualContouring.java#L172

    ReplyDelete