VectorStorm Blog

Not a lot of coding time today, so I just tackled a few speed issues that had arisen in the last few days.

The major one is that now that full procedural objects are being baked together into a single mesh (instead of lots of individual sub-meshes), the process of optimising those super-meshes was very slow.  The worst-cast situation at the moment is undoubtedly the starting area building, which is made up of about 600 triangles in total, or 1800 vertices, before being optimised down for rendering.  (I know, this doesn’t sound like a lot of triangles or vertices.  But due to its focus on procedural geometry, MT2 has to do a lot of model processing during runtime which other games can do outside of the game)

Optimising these procedural models mostly consists of checking all those generated vertices, to see if any of them are close enough together to be  merged together.  This means that for every element in the list, you need to check it against every other element in the list.  And when you have 1800 vertices, that’s an awful lot of checking.  Computer science folks call this O(n^2).  I just call it “really, painfully slow”.  Building that model freezes MT2 for about three seconds, on my computer.

What I’ve done is to add a simple cell structure to the mesh optimisation step.  Basically, imagine that the model is being built inside an 8x8x8 grid of cubes.  This way, vertices don’t have to be checked against every other vertex in the model — they only need to be checked against other vertices which are located in the same cell that they are.  This optimisation has sped up the creation of the “starting point” model from about three seconds to about half a second.  Which is still much too long, but it’s an awful lot better!  I’m going to have to think more about how to improve the speed further.