For loop within for loop is very slow

Archived Forums Questions & Answers
1

Ok. I’m trying to build a voxel (3D pixel) engine. What I have is a 3D array that stores whether or not a voxel is active and builds a cube at the corresponding vector. e.g:

if(voxel[x][y][z] == 1) {AddCube(); } // Looks through the 3D array and adds a cube to a mesh if the voxel is active.

The problem starts when I need to merge vertices. To make the final mesh look smooth vertices have to be detected and merged together if they overlap. The current cube has ~600 vertices. To merge them I have to run through every vertex, and then run through every vertex again to see if they overlap:

for(every vertex)
{
    for(every vertex)
    ... (if they overlap, merge them)
}

Unfortunately I have to do ANOTHER ‘for’ loop to then detect if a triangle has lost a vertex and then reassign the broken triangles. That’s THREE for looks of 600+ times, each handling large arrays…

I need to know if there is a faster way…

3 Answers

3
2

You need some sort of indexing.

Indexing is fundamental to programming anything involving large amounts of data. It is not a topic that can be covered here. A hashtable is an example of an indexing method - it allows you to look something up without having to iterate through all the items. In your case, it would seem you need an 3D index - a 3D array of lists of vertices such that you can quickly find nearby vertices.

 –
3

I don´t know if this would help or even make it worse, but you could destroy/reinstantiate the cubes that are outside a certain offset (like in a tilemap game where only part of the 2D array gets drawn).

4

If you are running this at runtime, you might also want to use a separate thread, aka a co-routine. Indexing would of course be the best way to speed things up.