I'm using the marching square algorithm (2D version of marching cubes) to generate vertices.

I end up with vertices arranged in a grid.

I want to enable destructible terrain, and the way i was planning on doing this was to start simple - have one vertex buffer with the whole map, and edit the bits that change. In cases where I need to remove vertices I was thinking about just making them transparent so I can still render the whole map in one go.

Firstly, is this approach reasonable?

Secondly, I want to design my VB so that if I need to change vertices in 3x3, 5x5 or 7x7 etc. grids the locations of the vertices in the VB are close together.

Now, from university I vaguely remember an image compression algorithm that walked the image in an unusual way, which i think could apply. Basically it walked in a U / horseshoe direction. It would place a U over the image, large enough to cover the whole thing, then it would break the U up into 4 quadrants, and use a smaller U to walk those, and so on until it got down to the pixel level, or in my case it got down to a single grid unit.

Does this sound feasible? What is that algorithm called? (I can't remember the name and haven't found via general searching).

  • \$\begingroup\$ It sounds like Hilbert's curve \$\endgroup\$ Jan 21, 2012 at 22:52
  • \$\begingroup\$ That's it! Thanks. I'm still undecided whether to go with that option, or a quad-tree type structure. \$\endgroup\$ Jan 22, 2012 at 12:08

1 Answer 1


It is feasible and the algorithm is called quadtree, for future reference, the 3D version is called octree and is essentially the same algorithm. You would likely store the vertexbuffer as several buffers in this method however, this way recreating part of the scenery will be less complicated and can be done by simply recreating one of the vertexbuffers. A google search should net you many tutorials and examples on both of these. Hope it helps.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .