Polyvox to Ogre Mesh

David Williams · **Joined:** Sun May 04, 2008 6:35 pm **Posts:** 1827

drwbns wrote:

...but why would I update a neighboring region for a single voxel?

The decision to draw any particular quad depends on two voxels. If two adjacent voxels are both solid or both empty then no quad is needed, but if one is solid and the other is empty then a quad is generated to represent the surface between them.

Now imagine that we have two adjacent voxels but in different regions. One is solid and the other is empty so a quad is generated between them, and it lies exactly on the region boundary. To which region should it belong? The answer isn't obvious, but in either case the problem now is that if either of our two voxels changes state then the quad should be removed. That is, changing a voxel on the edge of a region can mean that a neighbouring region needs to be regenerated.

By extension, a voxel in the corner of a region can be even more complex, requiring up to three neighbouring regions to be regenerated.

The simplest solution is that whenever you modify a voxel you should update that region and all neighbouring regions. Obviously this is slow, so once that works you can improve it to check whether a voxel is actually on the edge of a region.The maths here isn't too compex and I can elaborate once you verify that it is indeed the problem.

It would be nice if PolyVox made this easier though, perhaps a function which, for a given voxel, would tell you which Regions it affects. I've added this to the todo list.

drwbns · **Joined:** Wed Jan 11, 2012 7:33 pm **Posts:** 109

Hmm, so what you're saying is a quad may actually belong to a neighboring region that has no solid voxels?

I added a check to refresh neighboring regions but it's rather slow in release mode now, but on the other hand, seems to be drawing perfectly. Are there an speed enhancments I could try to speed up my program?

I'm still having some trouble when trying to do math on a negative Y value, it comes up as an incorrect value as such -

Code:

Ogre::Math::Floor(myPoint.GetY() / divisor)

is it because myPoint.GetY() is an unsigned int?

David Williams · **Joined:** Sun May 04, 2008 6:35 pm **Posts:** 1827

drwbns wrote:

Hmm, so what you're saying is a quad may actually belong to a neighboring region that has no solid voxels?

Yes, that's basically it.

drwbns wrote:

I added a check to refresh neighboring regions but it's rather slow in release mode now, but on the other hand, seems to be drawing perfectly. Are there an speed enhancments I could try to speed up my program?

Ok, so we've identified the problem. I assume you've fixed it by updating a region and all neighbouring regions when any voxels changes (i.e. when any voxel changes you update 27 regions)?. That's fine as a starting poit, but there are a couple of optimizations:

Check whether the voxel which has changed is actually on the edge of a region. If it is on the edge then neighbouring regions need to be updated, but if it's not (the most common case) then you only need to update the region you are in. If your region size is 32 (for example) then voxels 0, 31, 32, 63, 64, etc are on the edge of the region (extend this to three dimensions...)
When a single voxel changes you never need to update all 26 neighbours. At most you need to update 3 neighbours (I think?) in the case that it's a corner voxel.

drwbns wrote:

I'm still having some trouble when trying to do math on a negative Y value, it comes up as an incorrect value as such -

Code:

Ogre::Math::Floor(myPoint.GetY() / divisor)

is it because myPoint.GetY() is an unsigned int?

Perhaps, but you should also check the C++ rules for integer division (even if not unsigned). There's weird rules such as 8 / 3 = 2 (i.e. integer division always returns an integer result).

drwbns · **Joined:** Wed Jan 11, 2012 7:33 pm **Posts:** 109

I wrote a function to try to cut down on updating duplicate regions, but I now end up with a checkerboard mesh. One region visible, the next not and so on. It just adds any updated or created regions to a std::map and checks against that. But where is my logic flawed in doing that?

From what I can tell, I'm somehow ending up with regions that have no verts or indices to display a mesh from. Is it possible that every other region has it's verts in the neighboring region? This is getting confusing but I'm trying to cut down the draw time.

Code:

void WorldCraft::updateNeighbors(Vector3DInt32 polyMesh) {
   polysIter = polys.find(Vector3DInt32(polyMesh.getX() - 1, polyMesh.getY(), polyMesh.getZ()));
   if(polysIter == polys.end()){
      polys.insert(std::pair<Vector3DInt32, Vector3DInt32>(Vector3DInt32(polyMesh.getX() - 1, polyMesh.getY(), polyMesh.getZ()), Vector3DInt32(polyMesh.getX() - 1, polyMesh.getY(), polyMesh.getZ())));
      createOrUpdate(Vector3DInt32(polyMesh.getX() - 1, polyMesh.getY(), polyMesh.getZ()));
   }
   polysIter = polys.find(Vector3DInt32(polyMesh.getX() + 1, polyMesh.getY(), polyMesh.getZ()));
   if(polysIter == polys.end()){
      polys.insert(std::pair<Vector3DInt32, Vector3DInt32>(Vector3DInt32(polyMesh.getX() + 1, polyMesh.getY(), polyMesh.getZ()), Vector3DInt32(polyMesh.getX() + 1, polyMesh.getY(), polyMesh.getZ())));
      createOrUpdate(Vector3DInt32(polyMesh.getX() + 1, polyMesh.getY(), polyMesh.getZ()));
   }
   polysIter = polys.find(Vector3DInt32(polyMesh.getX(), polyMesh.getY()-1, polyMesh.getZ()));
   if(polysIter == polys.end()){
      polys.insert(std::pair<Vector3DInt32, Vector3DInt32>(Vector3DInt32(polyMesh.getX(), polyMesh.getY()-1, polyMesh.getZ()), Vector3DInt32(polyMesh.getX(), polyMesh.getY()-1, polyMesh.getZ())));
      createOrUpdate(Vector3DInt32(polyMesh.getX() , polyMesh.getY()- 1, polyMesh.getZ()));
   }
   polysIter = polys.find(Vector3DInt32(polyMesh.getX(), polyMesh.getY()+1, polyMesh.getZ()));
   if(polysIter == polys.end()){
      polys.insert(std::pair<Vector3DInt32, Vector3DInt32>(Vector3DInt32(polyMesh.getX(), polyMesh.getY()+1, polyMesh.getZ()), Vector3DInt32(polyMesh.getX(), polyMesh.getY()+1, polyMesh.getZ())));
      createOrUpdate(Vector3DInt32(polyMesh.getX() , polyMesh.getY()+ 1, polyMesh.getZ()));
   }
   polysIter = polys.find(Vector3DInt32(polyMesh.getX(), polyMesh.getY(), polyMesh.getZ()-1));
   if(polysIter == polys.end()){
      polys.insert(std::pair<Vector3DInt32, Vector3DInt32>(Vector3DInt32(polyMesh.getX(), polyMesh.getY(), polyMesh.getZ()-1), Vector3DInt32(polyMesh.getX(), polyMesh.getY(), polyMesh.getZ()-1)));
      createOrUpdate(Vector3DInt32(polyMesh.getX(), polyMesh.getY(), polyMesh.getZ() - 1));
   }
   polysIter = polys.find(Vector3DInt32(polyMesh.getX(), polyMesh.getY(), polyMesh.getZ()+1));
   if(polysIter == polys.end()){
      polys.insert(std::pair<Vector3DInt32, Vector3DInt32>(Vector3DInt32(polyMesh.getX(), polyMesh.getY(), polyMesh.getZ()+1), Vector3DInt32(polyMesh.getX(), polyMesh.getY(), polyMesh.getZ()+1)));
      createOrUpdate(Vector3DInt32(polyMesh.getX(), polyMesh.getY(), polyMesh.getZ() + 1));
   }
   
}

and here's my region filling code -

Code:

void WorldCraft::fillVoxelsBetween(Vector3DInt32 start, Vector3DInt32 end, Density8 tValue) {
   int startx, starty, startz, endx, endy, endz;
   int startxPoly, startyPoly, startzPoly, endxPoly, endyPoly, endzPoly;

   

   if(start.getX() < end.getX() ) { startx = start.getX(); endx = end.getX(); }  else { startx = end.getX(); endx = start.getX(); }
   if(start.getY() < end.getY() ) { starty = start.getY(); endy = end.getY(); }  else { starty = end.getY(); endy = start.getY(); }
   if(start.getZ() < end.getZ() ) { startz = start.getZ(); endz = end.getZ(); }  else { startz = end.getZ(); endz = start.getZ(); }

   for( int x = startx; x < endx; x++) {
      for ( int y = starty; y < endy; y ++) {
         for ( int z = startz; z < endz; z++) {
            volume.setVoxelAt(Vector3DInt32(x,y,z), tValue);
         }
      }
   }
   startxPoly = Ogre::Math::Floor(startx / divisor);
   startyPoly = Ogre::Math::Floor(starty / divisor);
   startzPoly = Ogre::Math::Floor(startz / divisor);
   endxPoly = Ogre::Math::Floor(endx / divisor);
   endyPoly = Ogre::Math::Floor(endy / divisor);
   endzPoly = Ogre::Math::Floor(endz / divisor);

   for( int x = startxPoly; x < endxPoly + 1; x++) {
      for ( int y = startyPoly; y < endyPoly + 1; y ++) {
         for ( int z = startzPoly; z < endzPoly + 1; z++) {
            
               polysIter = polys.find(Vector3DInt32(x,y,z));
               createOrUpdate(Vector3DInt32(x,y,z));
               if(polysIter == polys.end()){
                  polys.insert(std::pair<Vector3DInt32, Vector3DInt32>(Vector3DInt32(x,y,z), Vector3DInt32(x,y,z)));
                  
                  updateNeighbors(Vector3DInt32(x,y,z));
               }
         }
      }
   }
      CEGUI::Window * myWindow = mKeyDevices.windowManager->getWindow("Root/VertBuffer");
   myWindow->setText("");
   for(polysIter = polys.begin(); polysIter != polys.end(); polysIter++) {
      guiOutput(myWindow, const_cast<Vector3DInt32&>((*polysIter).first));
   }
   polys.clear();
}

David Williams · **Joined:** Sun May 04, 2008 6:35 pm **Posts:** 1827

I can't answer you're question directly because it's quite hard for me to spot a logic error in that kind of code (you're better off stepping through in the debugger), but I will share some ideas about a different approach to this problem

You said previously:

drwbns wrote:

...if I'm adding multiple voxels using a radius value...

Which implies to that you have some mechanism for setting multiple voxels at a time. When you do this, do you regenerate the mesh every time you set a voxel, or do you make all the voxel changes and then just regenerate the mesh once? Obviously the second approach is better.

Assuming you aready have the second approach, then you must have a way to mark voxels and/or regions as invalid and needing an update without actually performing the update yet. You should be able to extend this to handle your neighbouring regions problem. For example, when you mark voxel (x,y,z) as invalid you could also mark voxels (x-1, y, z), (x+1, y, z), (x, y-1, z), etc as invalid.

If the extra voxel are in the same regions then you are marking this region as invalid several times... but that doesn't matter because you still regenerate the mesh just once. And if they are in different regions then you've automatially handled the neighbouring regions problem.

I bring this up now because I just checked the Voxeliens code base and that's how I've done it. You can stick with your other approach if you prefer (there is no single right way to do it), but maybe this approach is easier to understand.

drwbns · **Joined:** Wed Jan 11, 2012 7:33 pm **Posts:** 109

Basically everything you're assuming to be correct is what I'm doing, hence my confusion with this approach. I'm iterating through all affected regions setting their densities for affected voxels, then iterating through the regions again creating or updating their meshes and any neighboring meshes. This approach worked but is slow because the duplicate neighbor updating. I'd like to draw an image to better illustrate what's happening and why of coarse neighbor checking is redundant but I think you understand why.

Granted I can get a fully completed mesh by not skipping any duplicate regions but what I can't understand is how marking my duplicate regions is creating an incomplete mesh. I'll just have to spend a little more time debugging to find the bug / solution, thanks

David Williams · **Joined:** Sun May 04, 2008 6:35 pm **Posts:** 1827

I think we're on the same page here, but allow me to summarise.

We agree that if a voxel is modified then we need to regenerate the mesh for it's corresponding region. If the modified voxel is on the edge of a region then the mesh for the neighbouring region also needs to be updated. The question simply how to track/decide which regions need to be modified when a given voxel is changed.
One solution (which we are now discarding) is to explicitly check whether the modifed voxel is on the edge of a region. If it is, then we mark both the current region and the neighbouring region as being invalid. How this marking takes place doesn't really matter - i.e. you could set a flag on the region or add it to a list of invalid regions. This solution should work but it seemms the logic is a little complex.
The alternative solution (which now seems desirable) is to always invalidate the region for the modified voxel and all neighbouring voxels. In most cases, the neighbouring voxels are actually going to be in the same region, and in so the region is marked as invalid multiple times (but we still know to only regenerate it once). In the case that the modified voxel is on the edge of the region, then one of the neighbouring voxels is in the neighbouring region. Hence this system is automatially invalidating the relevant neighbouring regions without us making an explicit check for this.

Sorry if I'm repeating myself here... just want to make sure the information is clear :-)

Assuming you do understand the above correctly then it's just a case of stepping through in the debugger as you say...

drwbns · **Joined:** Wed Jan 11, 2012 7:33 pm **Posts:** 109

I'm basically already using the alternative method of marking the entire region as invalid, along with neighboring regions. This works fine without a duplicate invalid region check - which is weird to me. But where I hit some trouble is in the negative Y regions - which is half my world obviously.

drwbns · **Joined:** Wed Jan 11, 2012 7:33 pm **Posts:** 109

I got my duplicate updated region checking working, but it's still really slow to draw large regions, any other tips that can speed up region / neighbor updates?

David Williams · **Joined:** Sun May 04, 2008 6:35 pm **Posts:** 1827

So you're now seeing the correct behaviour (no more graphical artifacts) and you're only updating the mesh for regions when really required? And now you are saying that the process of regenerating the mesh for a single region is taking too long?

Polyvox to Ogre Mesh

Who is online