It is currently Tue Aug 11, 2020 9:37 pm


All times are UTC




Post new topic Reply to topic  [ 21 posts ]  Go to page Previous  1, 2, 3  Next
Author Message
 Post subject: Re: MeshDecimator bug after calling SurfaceMesh::extractSubs
PostPosted: Mon May 09, 2011 6:44 am 

Joined: Sun Jan 23, 2011 6:06 am
Posts: 92
Another bug

Now that I am finally working on using multiple materials, I have noticed decimating a mesh after using extractSubset would result in big holes in the meshes. I have fixed this myself, but it is just a straight hack, so rather than posting a solution I will just outline what I did to fix it and hopefully that can point you in the right direction to fix the real problem.

Firstly, the main location of the problem seems to be:

Code:
MeshDecimator.cpp

template<>
   POLYVOXCORE_API void MeshDecimator<PositionMaterial>::fillInitialVertexMetadata(std::vector<InitialVertexMetadata>& vecVertexMetadata)
{

...

   //Find neighbours which are duplicates.
   for(int ct = 0; ct < intVertices.size() - 1; ct++)
   {
      const IntVertex& v0 = intVertices[ct+0];
      const IntVertex& v1 = intVertices[ct+1];

      if((v0.x == v1.x) && (v0.y == v1.y) && (v0.z == v1.z))
      {
         vecVertexMetadata[v0.index].isOnMaterialEdge = true;
         vecVertexMetadata[v1.index].isOnMaterialEdge = true;
      }
         
   }

...
}


The issue being that many duplicates are NOT being detected using the above code, even after sorting.

My work around was to store duplication data directly in the vertex itself:

Code:
VertexTypes.cpp

#ifdef SWIG
   class PositionMaterial
#else
   class POLYVOXCORE_API PositionMaterial
#endif
   {
   public:   
      PositionMaterial();
      //PositionMaterial(Vector3DFloat positionToSet, float materialToSet);
      PositionMaterial(Vector3DFloat positionToSet, uint8_t materialToSet);   //--! DefiniteIntegral : change to uint8_t material
      PositionMaterial(Vector3DFloat positionToSet, uint8_t materialToSet, bool isMaterialDuplicate);   //--! DefiniteIntegral : add material duplicate flag

      //float getMaterial(void) const;
      uint8_t getMaterial(void) const;   //--! DefiniteIntegral: changed to uint8_t
      const Vector3DFloat& getPosition(void) const;

      //void setMaterial(float materialToSet);
      void setMaterial(uint8_t materialToSet);   //--! DefiniteIntegral: changed to uint8_t
      void setPosition(const Vector3DFloat& positionToSet);
   public:      
      //Nicely fits into four floats. //--! DefiniteIntegral : not anymore
      Vector3DFloat position;
      //float material;
      uint8_t material;   //--! DefiniteIntegral: changed to uint8_t to remove compiler warnings, not sure why float on CPU anyway

      bool mIsMaterialDuplicate;   //--! DefiniteIntegral: whether this vertex was added as a duplicate position with a different materialID or not
   };   


Noted above I have also changed material from float to uint8_t because the compiler warnings annoy me, but that is unrelated. Also I am using a bool for mIsMaterialDuplicate but really it should be a uint8_t to save memory space...

This required a change to the CubicSurfaceExtractor (no normals) to make use of the above flags. I have not bothered to alter extractors for cubic with normals, or marching cubes.

Code:
CubicSurfaceExtractor.inl

template <typename VoxelType>
   int32_t CubicSurfaceExtractor<VoxelType>::addVertex(float fX, float fY, float fZ, uint8_t uMaterialIn, Array<3, IndexAndMaterial>& existingVertices)
   {
      uint32_t uX = static_cast<uint32_t>(fX + 0.75f);
      uint32_t uY = static_cast<uint32_t>(fY + 0.75f);

      for(uint32_t ct = 0; ct < MaxQuadsSharingVertex; ct++)
      {
         IndexAndMaterial& rEntry = existingVertices[uX][uY][ct];

         int32_t iIndex = static_cast<int32_t>(rEntry.iIndex);
         uint8_t uMaterial = static_cast<uint8_t>(rEntry.uMaterial);

         //If we have an existing vertex and the material matches then we can return it.
         if((iIndex != -1) && (uMaterial == uMaterialIn))
         {
            return iIndex;
         }
         else
         {
            uint32_t temp;

            //--! DefiniteIntegral: check for existing vertex
            if(iIndex == -1)
            {
               // index is -1, so this is a brand new vertex for this position, no duplicate. so create vertex with duplication flag set FALSE
               temp = m_meshCurrent->addVertex(PositionMaterial(Vector3DFloat(fX, fY, fZ), uMaterialIn, false));
            }
            else
            {
               // alert previously added vertex that it is now set as a duplicate also
               m_meshCurrent->getRawVertexData()[iIndex].mIsMaterialDuplicate = true;

               // index is NOT -1, so vertex as this position already exists, but has a different material, so set duplication flag TRUE
               temp = m_meshCurrent->addVertex(PositionMaterial(Vector3DFloat(fX, fY, fZ), uMaterialIn, true));
            }

            //Note - Slightly dodgy casting taking place here. No proper way to convert to 24-bit int though?
            //If problematic in future then fix IndexAndMaterial to contain variables rather than bitfield.
            rEntry.iIndex = temp;
            rEntry.uMaterial = uMaterialIn;

            return temp;
         }
      }

      //If we exit the loop here then apparently all the slots were full but none of
      //them matched. I don't think this can happen so let's put an assert to make sure.
      assert(false);
      return 0;
   }




Finally, a change to the MeshDecimator duplicate checking code to examine the flag set above


Code:
MeshDecimator.cpp

template<>
   POLYVOXCORE_API void MeshDecimator<PositionMaterial>::fillInitialVertexMetadata(std::vector<InitialVertexMetadata>& vecVertexMetadata)
{

...

   //Find neighbours which are duplicates.
   for(int ct = 0; ct < intVertices.size() - 1; ct++)
   {
      const IntVertex& v0 = intVertices[ct+0];
      const IntVertex& v1 = intVertices[ct+1];

      //--! DefiniteIntegral: leaving this here anyway, though probably redundant now
      if((v0.x == v1.x) && (v0.y == v1.y) && (v0.z == v1.z))
      {
         vecVertexMetadata[v0.index].isOnMaterialEdge = true;
         vecVertexMetadata[v1.index].isOnMaterialEdge = true;
      }

      //--! DefiniteIntegral: since neighbor check above seems to be failing, try checking duplicate flag set when vertex created
      if(   m_pOutputMesh->m_vecVertices[v0.index].mIsMaterialDuplicate == true ||
         m_pOutputMesh->m_vecVertices[v1.index].mIsMaterialDuplicate == true)
      {
         vecVertexMetadata[v0.index].isOnMaterialEdge = true;
         vecVertexMetadata[v1.index].isOnMaterialEdge = true;
      }
         
   }

...
}



And with that mesh decimation works properly for me across multiple materials. I may have missed some changes I made that but is the main gist of it.

I realize you are going to re-write mesh decimation anyway, but just wanted to alert you to this, something to look out for.


Top
Offline Profile  
Reply with quote  
 Post subject: Re: MeshDecimator bug after calling SurfaceMesh::extractSubs
PostPosted: Mon May 09, 2011 6:54 am 

Joined: Sun Jan 23, 2011 6:06 am
Posts: 92
There are still small holes appearing in the meshes, this time it is again the region border check causing problems.

I have tried to debug this but failed so far, and now have run out of time.

Have a look at these screenshots:
ftp://definiteintegral.net/region_edge_decimation_gaps1.png
ftp://definiteintegral.net/region_edge_decimation_gaps2.png

The case for each of those gaps is identical - on a region border, with a flat area 2 or more voxels in length flush against the border, with a voxel in the next region forming a 'step' up or down. The result is extracted vertices that 1) are not on material edge 2) only touch 1 region border 3) do not change normal when collapsed. This means they pass for all collapse tests, even though they should not.

I am not sure how to fix this. I could with time, but for now I am just going to disable all region border collapses and move on.


Top
Offline Profile  
Reply with quote  
 Post subject: Re: MeshDecimator bug after calling SurfaceMesh::extractSubs
PostPosted: Mon May 09, 2011 9:10 pm 
Developer
User avatar

Joined: Sun May 04, 2008 6:35 pm
Posts: 1827
Thanks for your continued work :-)

Actually, in the past I did investigate the idea of having the surface extractors set flags in the vertex data which can later be used to determine when vertices are on a material or region edge. As noted in this post, the surface extractors have access to that information a lot more readily. But of course, it also increases coupling between the surface extractors and the decimator.

While I appriciate the improvements you are trying to make to the MeshDecimator, I should let you know that I have now started writing an improved surface extractor based on the principles in that thread. I've only been working on it for a couple of days, but it's already looking quite promising. If you can hang on a couple more days you should find it is a much better approach.


Top
Offline Profile  
Reply with quote  
 Post subject: Re: MeshDecimator bug after calling SurfaceMesh::extractSubs
PostPosted: Tue May 10, 2011 7:38 am 

Joined: Sun Jan 23, 2011 6:06 am
Posts: 92
Thanks for the update.

I was aware that you were going to re-write extraction/decimation, that's why I didn't put too much time into it. Just wanted to alert you to some problems with the old decimator so you could tackle them in the new one ;)


Top
Offline Profile  
Reply with quote  
 Post subject: Re: MeshDecimator bug after calling SurfaceMesh::extractSubs
PostPosted: Tue May 10, 2011 9:41 pm 
Developer
User avatar

Joined: Sun May 04, 2008 6:35 pm
Posts: 1827
Ok, the initial version of the new extractor has been checked into the trunk. It's called ImprovedCubicSurfaceExtractor, though this is only temporary so it can live alongside the old one. You should find it is a drop-in replacement for the old one.

This new version can optionally merge quads as it generates the mesh. This happens by default but can be suppressed via a constructor parameter.

The most interesting change is that it no longer performs the merging/decimation as a 3D process. What I mean by this is that it does not initally generate a single list of quads. Instead it generates many lists of quads, where all the quads in each list are on a single plane. So it generates one list for all the quads in (e.g.) slice 10 facing in the X direction, and another list for all quads in (e.g.) slice 7 facing in the Y direction.

The result of this is that it never needs to merge quads between different lists, and so merging is reduced from a 3D problem to a series of 2D problems.

Anyway, this is an early version but it already seems to work ok in my basic tests, and it seems to handle regions and materials properly.


Top
Offline Profile  
Reply with quote  
 Post subject: Re: MeshDecimator bug after calling SurfaceMesh::extractSubs
PostPosted: Wed May 11, 2011 2:55 am 

Joined: Sun Jan 23, 2011 6:06 am
Posts: 92
Awesome. If I get time I will try it in the next few days.


Top
Offline Profile  
Reply with quote  
 Post subject: Re: MeshDecimator bug after calling SurfaceMesh::extractSubs
PostPosted: Fri May 13, 2011 5:20 am 

Joined: Sun Jan 23, 2011 6:06 am
Posts: 92
WOW this new cubic surface extractor/decimator is great! The decimation seems faster, the decimated mesh is neater, triangle count is down, and I can't see any material or region edge problems. I will let you know if I come across anything.

Thanks David, you just made my day ;)


Top
Offline Profile  
Reply with quote  
 Post subject: Re: MeshDecimator bug after calling SurfaceMesh::extractSubs
PostPosted: Fri May 13, 2011 6:17 pm 

Joined: Sat Sep 18, 2010 9:45 pm
Posts: 189
I don't think you can do any sort of vertex coloring on the CPU side with this. I'm doing that right now in my app. I was going to eventually move this to the GPU with GPU texture sampling.


Top
Offline Profile  
Reply with quote  
 Post subject: Re: MeshDecimator bug after calling SurfaceMesh::extractSubs
PostPosted: Fri May 13, 2011 9:05 pm 
Developer
User avatar

Joined: Sun May 04, 2008 6:35 pm
Posts: 1827
DefiniteIntegral wrote:
WOW this new cubic surface extractor/decimator is great! The decimation seems faster, the decimated mesh is neater, triangle count is down, and I can't see any material or region edge problems. I will let you know if I come across anything.

Thanks David, you just made my day ;)


Yep, it's better in every way :-) Makes me wish I hadn't spent so much time on the MeshDecimator but that's just the way things go sometimes.

The bottleneck is now the extraction stage as the decimation stage now only accounts for about 20% of the total time. I mentioned somewhere before that the extraction was calling getVoxelAt() directly, and having changed this to use the Volume::Sampler it's now twice as fast. So I think there is no reason to use the old surface extractor or MeshDeecimator (at least for cubic meshes - it's still the only solution for smooth meshes).

beyzend wrote:
I don't think you can do any sort of vertex coloring on the CPU side with this. I'm doing that right now in my app. I was going to eventually move this to the GPU with GPU texture sampling.


This is a good point, but actually you can supress the decimation stage with a parameter to the constructor. In this case the output is the same as before, but it is still faster.


Top
Offline Profile  
Reply with quote  
 Post subject: Re: MeshDecimator bug after calling SurfaceMesh::extractSubs
PostPosted: Fri May 13, 2011 10:55 pm 
Developer
User avatar

Joined: Sun May 04, 2008 6:35 pm
Posts: 1827
I've commited some more improvements. There was a bug (also in the previous version) which allowed duplicate vertices to slip though, and this was hampering the decimation process. I've fixed this and now it decimates even more.

There's almost nothing left :-)


Top
Offline Profile  
Reply with quote  
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 21 posts ]  Go to page Previous  1, 2, 3  Next

All times are UTC


Who is online

Users browsing this forum: No registered users and 2 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
cron
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
Theme created StylerBB.net