Greedy Algorithm Question

Hey all you advanced coders out there.

If any of you know what and how the greedy algorithm works it would be greatly appreciated if you shot me some of your knowledge, as I have been searching for the past 4 hours and yet I have returned with nothing.

Let me explain what I am trying to do. In my voxel "engine", I wish to collect verticies and combine faces for both the rendered mesh and the collision mesh to give me more leeway in my future programming ventures. In short, for optimization.

I have stumbled across a goldmine of information with this piece of code :

Code (csharp):

1.  
2. public void RenderWithVAOGreedy(ShaderProgram program, bool draw = true)
3. {
4.     // This greedy algorithm is converted from PHP to C# from this article:
5.     // http://0fps.wordpress.com/2012/06/30/meshing-in-a-minecraft-game/
6.     //
7.     // The original source code can be found here:
8.     // https://github.com/mikolalysenko/mikolalysenko.github.com/blob/gh-pages/MinecraftMeshes/js/greedy.js
9.     if (chunkVAO == null)
10.     {
11.         List<Vector3> vertices = new List<Vector3>();
12.         List<int> elements = new List<int>();
13.  
14.         for (int d = 0; d < 3; d++)
15.         {
16.             int i, j, k, l, w, h, u = (d + 1) % 3, v = (d + 2) % 3;
17.             int[] x = new int[3];
18.             int[] q = new int[3];
19.             bool[] mask = new bool[32 * 32];
20.  
21.             q[d] = 1;
22.  
23.             for (x[d] = -1; x[d] < 32; )
24.             {
25.                 // Compute the mask
26.                 int n = 0;
27.                 for (x[v] = 0; x[v] < 32; ++x[v])
28.                 {
29.                     for (x[u] = 0; x[u] < 32; ++x[u])
30.                     {
31.                         mask[n++] = (0 <= x[d] ? data(x[0], x[1], x[2]) : false) !=
32.                             (x[d] < 32 - 1 ? data(x[0] + q[0], x[1] + q[1], x[2] + q[2]) : false);
33.                     }
34.                 }
35.  
36.                 // Increment x[d]
37.                 ++x[d];
38.  
39.                 // Generate mesh for mask using lexicographic ordering
40.                 n = 0;
41.                 for (j = 0; j < 32; ++j)
42.                 {
43.                     for (i = 0; i < 32; )
44.                     {
45.                         if (mask[n])
46.                         {
47.                             // Compute width
48.                             for (w = 1; i + w < 32  mask[n + w]; ++w) ;
49.  
50.                             // Compute height (this is slightly awkward
51.                             var done = false;
52.                             for (h = 1; j + h < 32; ++h)
53.                             {
54.                                 for (k = 0; k < w; ++k)
55.                                 {
56.                                     if (!mask[n + k + h * 32])
57.                                     {
58.                                         done = true;
59.                                         break;
60.                                     }
61.                                 }
62.                                 if (done) break;
63.                             }
64.  
65.                             // Add quad
66.                             x[u] = i; x[v] = j;
67.                             int[] du = new int[3];
68.                             int[] dv = new int[3];
69.                             du[u] = w;
70.                             dv[v] = h;
71.  
72.                             AddFace(new Vector3(x[0], x[1], x[2]),
73.                                     new Vector3(x[0] + du[0], x[1] + du[1], x[2] + du[2]),
74.                                     new Vector3(x[0] + du[0] + dv[0], x[1] + du[1] + dv[1], x[2] + du[2] + dv[2]),
75.                                     new Vector3(x[0] + dv[0], x[1] + dv[1], x[2] + dv[2]), vertices, elements);
76.  
77.                             // Zero-out mask
78.                             for (l = 0; l < h; ++l)
79.                             {
80.                                 for (k = 0; k < w; ++k)
81.                                 {
82.                                     mask[n + k + l * 32] = false;
83.                                 }
84.                             }
85.  
86.                             // Increment counters and continue
87.                             i += w; n += w;
88.                         }
89.                         else
90.                         {
91.                             ++i; ++n;
92.                         }
93.                     }
94.                 }
95.             }
96.         }
97.  
98.         Vector3[] vertex = vertices.ToArray();
99.         int[] element = elements.ToArray();
100.         Vector3[] normals = OpenGL.Geometry.CalculateNormals(vertex, element);
101.  
102.         chunkVAO = new VAO(program, new VBO<Vector3>(vertex), new VBO<Vector3>(normals), new VBO<int>(element, BufferTarget.ElementArrayBuffer, BufferUsageHint.StaticRead));
103.     }
104.  
105.     if (draw)
106.     {
107.         program["model_matrix"].SetValue(ModelMatrix);
108.  
109.         chunkVAO.Draw();
110.     }
111. }
112.  
113. private bool data(int x, int y, int z)
114. {
115.     return voxelData[x + 32 * y + 32 * 32 * z] != 0;
116. }
117.  

However, so much of it I do not understand or just cannot wrap my head around what goes where, because as you can see..... It is only barely documented. And I realize there are a few non-Unity language pieces in there.

This example is using a flat array, whereas I would like to somehow re-arrange it to work my chunk system in which Blocks are in the form chunkBlocks[x,y,z].

I realize that this is talking in terms of 2D space and is a method for finding the least amount of elements and then using that one (although not always optimal) and this is talking in terms of quads rather than triangles.

I'm not asking for a specific styled re-write just for me(although that would be amazing), I am just asking for some help with understanding what exactly it does.

I will be working on this trying to understand for the next few days, but if you can help me in any way I would be greatly appreciative.

Thanks
Myhi

 

While their code is indeed really hard to understand because there is no explanation of any of the variables, they do use a similar idea of what we are doing in Gunjitsu (gunjitsugame.com). We are not using a greedy algorithm however, but maybe this will help you anyways.

They compute the "mask" of each side in a simple bool array to know which points that should be rendered or not.

Lets say that you look at a 32x32x32 voxel chunk from above. You will then investigate the top layer (on the x,z) and go through each voxel and set your bool array to false or true based on its voxel info. If it is true it should be rendered out.

What we use this information for is finding the the largest possible areas that we can draw to save space/memory, because vertices, normals and such really takes up lots of space for large voxels worlds! I let you think of smart ways to finish this idea your self!

We started out using it for our collider mesh, as altering it runtime is soooo slow. We can now handle 64x64x64 chunks at runtime in a multiplayer game.

We also just implemented it for our render mesh and got a test level down with more than 60% space/memory usage.

Our method might not be greedy, but we always get the best possible result

 

Thank you very much for your response, it means a lot to me that you put in the effort to write about it!

Yes indeed it is very hard to understand their code as I have tried 3 times to adapt it to my own but to no avail! I have understood the part of cycling through arrays and combining verticies and I completely understand the concept, it is just putting it into practice and the smart ways to do it are hard to find!

Yes my mesh colliders are optimized through a buffer but I really need this so I can move on to further features as right now the 16x16x80 chunk collision mesh just don't cut it.

I'm sorry I must ask of you this as I can tell the exact optimization method you use is a good secret to safegaurd, but could you point me in the right direction for a smarter algorithm as I have been searching for around 12 hours straight However if not that is completely understandable and I shall keep hacking away at this code.

Thank you so much for your time and effort!
Myhi

 

Cannot really point you to any algorithm as i came up with the idea my self. And as it might be used in a University paper i am writing, i will wait explaining it till the paper is out.

But find as large "squares" as possible in your voxel layers. This can be achieved in different ways, i am sure you can figure that out with pen and paper

 

Thank you so much again! I'll keep hacking away at this code and if that doesn't work I will just work with rectangles and work my way up

 

Hi Myhijim,

I had a crack at this today and got most of the way there but there's still a bug in it.
I'm curious did you ever get an answer to your problem?