Greedy meshing in javascript

 I've been working on an extension of the Voxel mesh in three JS that I built in this blog post and I'm thinking of developing it into an upcoming game at ManicVoxels.com

To be able to expand the reach of the game to lower-power devices I needed to make the program more efficiently rendered. This would allow the players on the lower-powered devices to still have a reasonably sized world around them.

When looking at the Greedy meshing tutorial from 0fps I really struggled to work out what the algorithm was. I then realised what is actually going on; you start in the top left, you go as far right as you can and then you go as far down as you can. You then repeat this until you have a new mesh. Once I'd worked out what greedy meshing was doing I could start to code it up. I've also added an animation of the algorithm below. In the animation, you can see the cursor moving from the top left to the bottom right. As if goes if the square is to be included in a new mesh then we start to create the light blue rectangle. We then go right as far as we can until something blocks us. That is the width, we then go down that full width checking that the next row is fully compatible (all cells to be included). Once we've done that we go back to where we were, shifted right by the width of our new mesh chunk and continue. In the animation, we end up making 3 rectangles out of what would otherwise be 34 distinct squares (68 triangles).

The main challenge was that once I've worked out some form of 2D implementation starting in the top left going as far right as you can and then as far down as you can that's fine for one plain but then if you want to do that and the chunks in the game of 16 by 16 by 16 you want to for each plane so there's 17 of them for each direction you want to create these meshes but the vertices of the faces of that mesh need to have three-dimensional coordinates so you need to work out giving your coordinates on that plane what your coordinates will be in in the mesh.

The challenge here is that if you are using XY say for your 2D plane and you want to reuse that piece of code to do all of your 2D planes then in one instance you've got your X and Y being the X and Y globally with your Z increasing for each run as you step back through the Block and then for your X stepping backwards through the block with your with what is actually a plane in YZ if you use XY then as easy to get confused for a what does the Y mean. I got a little bit confused by that but other than that you can step through.

The next challenge is UV mapping and that's a whole different ball game! Once I managed to get the Greedy meshing I then needed to work out how to get how to attach the uvs to the Vertices.

The complexity here came from the fact that before going to a greedy meshing the texture on the Block came from using the UV to select it along the map of all textures. I couldn't do that once using greedy meshing because most of the faces will not be a single block and so if I tried to select with the uvs in the way that I did before the texture either that texture would be scaled to be a cross whatever size block it was so for example if a whole face than 16 by 16 chunk was was greedy meshing to one face then you might have a block which should be tiled 16 by 16 times and then instead you've just got one stretched across the whole of the 16 by 16 space so you then need to have something that will communicate the information to the shader. I ended up using the uvs in a very peculiar way that allowed me to communicate the position to the shader and then had a separate texture representing what each face was and passing that separately to the shader.

Encoding 3 numbers in 2:

In the above code, I'm using the fact that we kind of have 3 integers and 2 floats. The 3 integers are the coordinate of that UV point in the cube of the chunk. The two floats are then what would normally be called the UV. The fraction of the distance we are from one vertex to another. We can then stack the numbers in a similar way to how you can represent two 4 bit integers inside a large 1 byte integer, we are going to store an integer and a float inside a float.

This meant that we had to use a custom shader to unpack this unique method of packing information into the UVs and that is what I did.

... To be continued