Represent Surface Extractor Data As Quad-Tree

kklouzal · **Posted:** Mon Apr 28, 2014 4:04 am

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.

David Williams · **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?

kklouzal · **Posted:** Tue Apr 29, 2014 7:36 pm

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.

David Williams · **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).

kklouzal · **Posted:** Wed May 07, 2014 8:26 am

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

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);
      }
   }

milliams · **Posted:** Wed May 07, 2014 9:07 am

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.

kklouzal · **Posted:** Wed May 07, 2014 8:10 pm

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?

David Williams · **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?

Represent Surface Extractor Data As Quad-Tree

Who is online