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?