Edit: This is just for my own learning experience, it is NOT for performance reasons that I ask this question.
This is in regards to a Minecraft-like terrain engine. I store blocks in chunks (16x256x16 blocks in a chunk). When I generate a chunk, I use multiple procedural techniques to set the terrain and place objects. While generating, I keep one 1D array for the full chunk (solid or not) and a separate 1D array of solid blocks.
After generation, I iterate through the solid blocks checking their neighbors so I only generate block faces that don't have solid neighbors. I store which faces to generate in their own list (that's 6 lists, one per possible face/normal). When rendering a chunk, I render all lists in the camera's current chunk and only the lists facing the camera in all other chunks. I do this by storing all 6 lists in one buffer, then I simply change what ranges I draw.
Using a 2D atlas with this little shader trick Andrew Russell suggested, I want to merge similar faces together completely. That is, if they are in the same list (same normal), are adjacent to each other, have the same light level, etc. I know I will still end up with rectangles, but it should easily reduce my vertices count by 50% or better if my estimations are correct.
My assumption would be to have each of the 6 lists sorted by the axis they rest on, then by the other two axes (the list for the top of a block would be sorted by it's Y value, then X, then Z).
With this alone, I could quite easily merge strips of faces, but I'm looking to merge more than just strips together when possible. I've read up on this greedy meshing algorithm, but I am having a lot of trouble understanding it.
So, my question: To perform merging of faces as described (ignoring whether it's a bad idea for dynamic terrain/lighting), is there perhaps an algorithm that is simpler to implement? I would also quite happily accept an answer that walks me through the greedy algorithm in a much simpler way (a link or explanation).
I don't mind a slight performance decrease if it's easier to implement or even if it's only a little better than just doing strips. I worry that most algorithms focus on triangles rather than quads and using a 2D atlas the way I am, I don't know that I could implement something triangle based with my current skills.
PS: I already frustum cull per chunk and as described, I also cull faces between solid blocks. I don't occlusion cull yet and may never.
*Edit: I have implemented my own little technique, which probably has a name, but I simply go through my 6 lists which are sorted by the axes they rest on, followed by block type, and then by lighting level. I iterate through them, creating new rectangles as I go and grow them simultaneously (with a heavy bias towards a certain axis). It is definitely not optimal, but it is indeed quite fast and it does lower my vertex count by close to 50% on average. Byte56's comment is the closet I think to a real answer, but I can't select that for the answer/bounty.
Here is my fast and simplistic way I'm handling this problem AFTER generating the full initial terrain without much of any optimization. Assuming all squares given are the same image, light level, normal, etc.. each color is a different quad I would render. With my lists sorted the way they are, this is a very easy/fast approach.
