It is currently Thu Nov 21, 2019 8:09 am


All times are UTC




Post new topic Reply to topic  [ 8 posts ] 
Author Message
 Post subject: Represent Surface Extractor Data As Quad-Tree
PostPosted: Mon Apr 28, 2014 4:04 am 
User avatar

Joined: Thu Sep 05, 2013 3:38 am
Posts: 51
Location: USA - Arizona
Hey everyone I'm struggling really hard with this and thought someone here might be able to help since it pertains to data retrieved directly from PolyVox.

I'm trying to take the vertex and index data retrieved with a MarchingCubesSurfaceExtractor and organize it into a Quad-Tree.

I can't figure out where to start. I've looked at numerous videos and articles on Quad-Trees and I'm drawing a blank..

Thank you very much for any help in the correct direction here.

_________________
Dream Big Or Go Home.
ENet - http://enet.bespin.org
Recast - https://github.com/memononen/recastnavigation
Irrlicht - http://irrlicht.sourceforge.net/forum
PolyVox - http://www.volumesoffun.com/phpBB3/
Help Me Help You.


Top
Offline Profile  
Reply with quote  
 Post subject: Re: Represent Surface Extractor Data As Quad-Tree
PostPosted: Tue Apr 29, 2014 2:50 pm 
Developer
User avatar

Joined: Sun May 04, 2008 6:35 pm
Posts: 1827
To be honest I'm not sure I understand your question (or even if it makes sense). Quadtrees are usually applied to 2D data (often images, also perhaps heightmap mesh data) but not usually to 3D data. Can you elaborate on why you want your mesh data in a quad tree and what exactly you mean by this? Is it related to the LOD stuff you have mentioned in the other thread?


Top
Offline Profile  
Reply with quote  
 Post subject: Re: Represent Surface Extractor Data As Quad-Tree
PostPosted: Tue Apr 29, 2014 7:36 pm 
User avatar

Joined: Thu Sep 05, 2013 3:38 am
Posts: 51
Location: USA - Arizona
Yes this is for LOD and Culling related things. I've herd people say that Quad-Trees can work for 3D objects however I've opted to go ahead and use an Octree since they are designed for 3D.

I understand Octree is just a data structure but I'm unsure on how to actually fill the tree with vertex/index data.

_________________
Dream Big Or Go Home.
ENet - http://enet.bespin.org
Recast - https://github.com/memononen/recastnavigation
Irrlicht - http://irrlicht.sourceforge.net/forum
PolyVox - http://www.volumesoffun.com/phpBB3/
Help Me Help You.


Top
Offline Profile  
Reply with quote  
 Post subject: Re: Represent Surface Extractor Data As Quad-Tree
PostPosted: Thu May 01, 2014 10:02 am 
Developer
User avatar

Joined: Sun May 04, 2008 6:35 pm
Posts: 1827
I guess you could say it's a slightly abstract concept, as it depends exactly what you are trying to do with it. Let's say you are using it for culling (simpler than LOD). A simple octree node class could look something like this:

Code:
class OctreeNode
{
public:
  Region region; // The space coveed by this node
  SurfaceMesh* mesh; // The mesh (if any) corresponding to this region
  OctreeNode* children[2][2][2]; The child nodes can also be null.
}


That's just off the top of my head, and there are more efficient ways to store it. You can construct such a tree with the root node covering your whole scene, and the recursively subdivide it until your leaf nodes are a certain size (say 16x16x16 voxels). You can then run a surface extractor on the leaf regions and store the resulting meshes in the leaf nodes. When rendering, you can first check the root node against your camera frustrum, and if it is visible then move on to check the children.

But it all gets a bit more complex when you want to eliminate empty node in the tree, and also keep it up to date with changes to the data. Probably you'll need to do some more reading here as it's a bit outside the scope of PolyVox (which just generates the mesh data).


Top
Offline Profile  
Reply with quote  
 Post subject: Re: Represent Surface Extractor Data As Quad-Tree
PostPosted: Wed May 07, 2014 8:26 am 
User avatar

Joined: Thu Sep 05, 2013 3:38 am
Posts: 51
Location: USA - Arizona
Okay, thank you very much!

I've now got a question about the surface extractor.

I've got my volume broken down into small chunks, each chunk has it's own SurfaceMesh thats filled from a surface extractor.
I'm iterating through each chunk and taking the vertices and indices from the surface mesh and combining them together.
When I render this it's just a mess of polygons.

So, when I use the surface extractor on each of the individual chunks does it number the extracted indices and position of vertices from within that small region or does it take into consideration what section from the whole volume I'm extracting out of?

Sorry that might not make sense :P

Code:
void Render(void)
   {
      // Maximum sector distance for rendering
      float SectorRenderDistance = 1000.0f;
      // Maximum chunk distance for rendering
      float ChunkRenderDistance = 800.0f;

      // Get camera position
      Camera = SMGR->getActiveCamera();
      PolyVox::Vector3DFloat CamPos(Camera->getPosition().X, Camera->getPosition().Y, Camera->getPosition().Z);

      // Vector of indices to render
      std::vector<uint32_t> indices;
      // Vector of vertices to render
      std::vector<PolyVox::PositionMaterialNormal> vertices;

      // Loop through all planets
      for (auto iPlanet : Planets)
      {
         // Check planet render distance
         Planet* ThisPlanet = iPlanet->GetPlanet();
         if ((CamPos - ThisPlanet->GetPlanetData()->PlanetPosition).length() <= PlanetRenderDistance)
         {
            // Loop through all planets sectors
            std::vector<Sector*> Sectors = ThisPlanet->GetSectors();
            for (auto Sec : Sectors)
            {
               // Check sector render distance
               if (wSpecs.WorldPosFromVoxelPos(Sec->GetCenterPos()).length() <= SectorRenderDistance)
               {
                  // Loop through all sectors chunks
                  std::vector<Chunk*> Chunks = Sec->GetChunks();
                  for (auto Chk : Chunks)
                  {
                     // Check if chunk not empty
                     if (!Chk->GetEmpty())
                     {
                        // Check chunk render distance
                        if (wSpecs.WorldPosFromVoxelPos(Chk->GetCenterPos()).length() <= ChunkRenderDistance)
                        {
                           // Get the chunks SurfaceMesh
                           PolyVox::SurfaceMesh<PolyVox::PositionMaterialNormal> Mesh_PolyVox = Chk->GetMesh();
                           // Grab its indices and vertices
                           std::vector<uint32_t> NewIndicies = Mesh_PolyVox.getIndices();
                           std::vector<PolyVox::PositionMaterialNormal> NewVertices = Mesh_PolyVox.getVertices();

                           // If there are indices and vertices
                           if (NewVertices.size() > 0 && NewIndicies.size() > 0)
                           {
                              // Add them into the vectors for rendering
                              indices.reserve(indices.size() + NewIndicies.size());
                              vertices.reserve(vertices.size() + NewVertices.size());
                              indices.insert(indices.end(), NewIndicies.begin(), NewIndicies.end());
                              vertices.insert(vertices.end(), NewVertices.begin(), NewVertices.end());
                           }
                        }
                     }
                  }
               }
            }
         }
      }
      //
      //
      // How many indices and vertices to render
      size_t VerticeSize = vertices.size();
      size_t IndiceSize = indices.size();

      // Make sure there are some to render
      if (VerticeSize > 0 && IndiceSize > 0)
      {
         //16 or 32 bit?
         if (VerticeSize <= 65536)
         {
            // May need to delete and recreate as either 16/32 bit
            MeshBuffer->getIndexBuffer().setType(irr::video::EIT_16BIT);
         }
         else{
            // May need to delete and recreate as either 16/32 bit
            MeshBuffer->getIndexBuffer().setType(irr::video::EIT_32BIT);
         }

         // Grab the vertex and index buffer
         irr::scene::IVertexBuffer& VBuff = MeshBuffer->getVertexBuffer();
         irr::scene::IIndexBuffer& IBuff = MeshBuffer->getIndexBuffer();

         // Set how many vertices and indices were using
         VBuff.set_used(VerticeSize);
         IBuff.set_used(IndiceSize);

         // Loop through each and set parametrs
         for (size_t i = 0; i < VerticeSize; ++i)
         {
            const PolyVox::Vector3DFloat position = vertices[i].getPosition();
            const PolyVox::Vector3DFloat normal = vertices[i].getNormal();
            VBuff[i].Pos.X = position.getX();
            VBuff[i].Pos.Y = position.getY();
            VBuff[i].Pos.Z = position.getZ();
            VBuff[i].Normal.X = normal.getX();
            VBuff[i].Normal.Y = normal.getY();
            VBuff[i].Normal.Z = normal.getZ();
            VBuff[i].TCoords = irr::core::vector2df(position.getX(), position.getZ());
            VBuff[i].Color = irr::video::SColor(255, 255, 255, 255);
         }
         for (size_t i = 0; i < IndiceSize; ++i)
         {
            IBuff.setValue(i, indices[i]);
         }

         // BoundingBox
         MeshBuffer->recalculateBoundingBox();

         // Setup a wireframe material
         Driver->setTransform(irr::video::ETS_WORLD, irr::core::IdentityMatrix);
         irr::video::SMaterial Mat1 = MeshBuffer->getMaterial();
         Mat1.setFlag(irr::video::EMF_LIGHTING, false);
         Mat1.setFlag(irr::video::EMF_WIREFRAME, true);
         Driver->setMaterial(Mat1);

         // Draw the MeshBuffer to screen
         Driver->drawMeshBuffer(MeshBuffer);
      }
   }

_________________
Dream Big Or Go Home.
ENet - http://enet.bespin.org
Recast - https://github.com/memononen/recastnavigation
Irrlicht - http://irrlicht.sourceforge.net/forum
PolyVox - http://www.volumesoffun.com/phpBB3/
Help Me Help You.


Last edited by kklouzal on Wed May 07, 2014 9:10 am, edited 1 time in total.

Top
Offline Profile  
Reply with quote  
 Post subject: Re: Represent Surface Extractor Data As Quad-Tree
PostPosted: Wed May 07, 2014 9:07 am 
Developer
User avatar

Joined: Sun May 11, 2008 4:29 pm
Posts: 198
Location: UK
When you run the surface extractor on each chunk you will get a new set of indices, starting from 0 each time. When passing that off to your rendering engine, you'll need to pass just the indices and vertices for 'chunk 1' and ask it to render that/make a renderable object from it. Then move on to 'chunk 2' and do the same. You can't extract all the indices and vertices for all the chunks and pass them to the renderer in one go otherwise you'll see the mess of polygons that you have.

_________________
Matt Williams
Linux/CMake guy


Top
Offline Profile  
Reply with quote  
 Post subject: Re: Represent Surface Extractor Data As Quad-Tree
PostPosted: Wed May 07, 2014 8:10 pm 
User avatar

Joined: Thu Sep 05, 2013 3:38 am
Posts: 51
Location: USA - Arizona
There's nothing I can do at this point to 'fix' the positioning of the vertices and indices? I have the position of the chunk, couldn't that be used somehow to scale the positions?

_________________
Dream Big Or Go Home.
ENet - http://enet.bespin.org
Recast - https://github.com/memononen/recastnavigation
Irrlicht - http://irrlicht.sourceforge.net/forum
PolyVox - http://www.volumesoffun.com/phpBB3/
Help Me Help You.


Top
Offline Profile  
Reply with quote  
 Post subject: Re: Represent Surface Extractor Data As Quad-Tree
PostPosted: Thu May 08, 2014 12:06 pm 
Developer
User avatar

Joined: Sun May 04, 2008 6:35 pm
Posts: 1827
It should be possible to combine chunks but you can't simply append the data. As Matt said, this is partly because each chunk has it's own index buffer which assumes the vertices start at 0, and also because each chunk is defined within it's own local coordinate system.

But with some thought you can fix it. Let's say you have chunks 'a' and 'b' each with their own vertex buffer and index buffer. If you append the vertices from vertex buffer 'b' onto the end of vertex buffer 'a', then index buffer 'a' is still valid (because the vertices in vertex buffer 'a' haven't moved). The vertices in vertex buffer 'b' however have all been shifted by the length of vertex buffer 'a', so you need to update the indices in index buffer 'b'. Does that make sense?

You would also need to modify the actual vertex positions in 'b' because they are relative to the lower corner of the region which generated them. The region which a mesh corresponds to is stored in the SurfaceMesh::m_Region member. You can move 'b's vertex positions into global space by adding b.m_Region.getLowerCorner(), and then move them into 'a's local space by subtracting a.m_Region.getLowerCorner().

As you can see this isn't exactly elegant, and the system hasn't really been designed with this in mind. So the other question is whether you really want to combine chunks this way, rather than just run the extractor again over the combined region?


Top
Offline Profile  
Reply with quote  
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 8 posts ] 

All times are UTC


Who is online

Users browsing this forum: No registered users and 1 guest


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