0
\$\begingroup\$

I am creating a quad tree to store my terrain in chunks and currently have the implementation working to an extent.

I am currently starting with a grid of triangle pairs that make squares and splitting this down into quads. I have my vertices split into quads, but I'm struggling with the indices.

enter image description here

Here is how I generate the plane

snip

This gives me one list of indices, and one list of vertices. This is taken by the quadtree and split into different vertex lists and stored in different nodes. This works fine and the vertices seem to be correct, however I'm not sure how to create the indices for each vertex list as before I was doing it based on the height and width of the whole terrain. How would I create an indices list for each node in the quadtree or is there a better way to do this?

If I just use the whole list of indices for each node, I get weird results

https://i.gyazo.com/43809a0f08e5732f68f4b3f67c9a3bef.png

Edit: There is an issue generating my plane, I am fixing this and seeing if it resolves my problem.

Edit: I have edited the topic title to something more suitable.

I have fixed my issue with the grid generation and I am using a smaller grid to make the issues more clear. I am using a 2x2 grid (9 verts, 24 indices, 8 tris) which is split into 4 quads (4 verts per quad, 2 tris per quad) and it's almost working, just a small issue with one of the sides. enter image description here

I know this is potentially duplicating verts on a small scale, but on a larger scale with culling, this should actually save performance. Can anyone spot what's going on? Vertex issue? When splitting the quads, should it be by triangle, vertices, or indices? What happens if we split by triangle and a triangle overlaps 2 quads (although this shouldn't happen)

\$\endgroup\$
1
\$\begingroup\$

As I have done what you are trying to do, ala quad tree and splitting into chunks. A couple of things.

For optimal performance, I have found that keep the vertex list as one buffer. Do your quadtree split on the indices. What this does is your indices dont have to be rebuilt and reflect the true index of the vertex in your mega buffer.

NOW, if you decide to split at a vertex level also, that is both index and vertex buffers per leaf in your quad, you will need to reindex.

This gets more complex if you dont have shared vertices at each grid point, but share the same vertex (that is, your neighboring quads share the same grid point), you will need to then split this up each time you split your node.

2nd Easiest way to go - and slowest.

Generate your grid with individual vertices per quad, that is 6 (3 per triangle).

Treat your vertices as triples, so when you do your quad tree subdivision you move the triples into the relevant node. Build your vertex list and then eliminate duplicate vertices sharing the same point and create your index list.

Easiest way I have found ...so far...

Build your Vertex list and associated index list.

Do your quad tree, reference the vertices via the index list (naturally), and split only the index buffer in triples (that is, split them on the central point of the triple). As this is a uniform grid, your triples should split evenly among your nodes.

From the screenshot, I am assuming you are splitting in your quadtree per vertex rather than per triple. My guess, please dont shoot me!

My game uses this -> https://www.facebook.com/InsaneSoftware.com.au/

the game uses quad trees (not as efficiently with index buffers at the moment!) but you can see the quad tree in action by playing with the f1 - f3 keys if you feel like seeing what I did.

Enjoy.

\$\endgroup\$
  • \$\begingroup\$ Hey thanks for the response! At the moment I am not fussed about absolute optimal performance as the quadtree is for frustum culling only for now. At the moment they are split on vertices yes, and I just pass the whole indices list to create the buffer (saves me having to reindex, bad idea). I like the idea of splitting on the indices though, could you give me a small example of how I can achieve this? I'm sure this would help a bunch with the approach. I have updated my OP if you'd like to read it. \$\endgroup\$ – user Sep 8 '17 at 12:53
  • \$\begingroup\$ I get how this would be done sort of, so we have one vertex buffer and split the indices into the quads (which would give me the triangles per quad), but what happens if the line that the indices creates crosses over 2 quads (although this should never happen right) \$\endgroup\$ – user Sep 8 '17 at 13:26
  • \$\begingroup\$ What i do is take the central point of each triangle and sort into the relevant node. Yes this sites cause the sawtooth effect but the goal is really to group them really into the leaf they should be on. There is probably one thing i missed you tell you. After sorting you should reevaluate the bounding box of each leaf and traverse back up your tree. At each node re evaluating the sum of the chidren. This means your bounding boxes may be slightly different to how you broke them up. \$\endgroup\$ – ErnieDingo Sep 8 '17 at 15:35
  • \$\begingroup\$ The index version of the tree is only slightly more complex. You evaluate your vertices through the indices. Easiest easy to come to terms with this method is to allocate your indices 1 to 1 with your verts. So basically when evaluating triangle you are referencing the vert indirectly. So instead of vertex[i] you would do vertex[indice[i]] \$\endgroup\$ – ErnieDingo Sep 8 '17 at 15:41
  • \$\begingroup\$ Ahh I see, well I'm going to give the indices approach a go first as that's how I have them set up at the moment. The other approach seems easier though. How would I get the central point of each triangle, is that just some maths to figure it out based on the vertices? Thanks for your help, I'll post some progress once I've implemented it. \$\endgroup\$ – user Sep 8 '17 at 16:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.