Converting a 3D int array to an Octree in Java

I'm creating a voxel engine in Java using LWJGL just for practice, but I'm getting stuck on the chunk management system. More specifically, I'm trying to convert a Chunk, which is just a 3D array of integers for the block id, into an Octree for optimal rendering.

So far, I have the system working, but it's horribly inefficient.

Here's a screenshot of a 16*16*16 chunk with all positions below y=8 set to 1 (the red blocks)

https://raw.githubusercontent.com/ninthworld/Octree/master/screenshot0.png

I added a debugger to the OctNode generator code to find out how many times it needed to access the chunk array, and it came back with 8392704.

It accessed the chunk array over 8 million times just to generate 8 children nodes.

When I set the chunk array to only have blocks below y=4, the program has a blackscreen for almost 30 seconds, and the debugger returns 1623199744 array accesses.

Over 1.6 billion array calls just to generate 68 children nodes.

I obviously need to reduce the number of array calls, that much is certain, but I'm not sure how I would go about doing that. Here's the github page for the project if you'd like to see the entire source code.

Here are the important parts of my code:

Main.java

    // Initialize Octree Object
    // This is just an extended OctNode object
    octree = new Octree(chunk);
    octree.generate(lookup);

OctNode.java

public void generate(){
    int value = -1;

    // Loop through an area an area of width*width*width
    for(int x=0; x<width; x++){
        for(int y=0; y<width; y++){
            for(int z=0; z<width; z++){

                // Get the value from the master array based on the node's
                // offset + the forloop'd area
                int store = array[x+(int)offset.x][y+(int)offset.y][z+(int)offset.z];

                // Basically sets the value variable to the value at 
                // 0, 0, 0 with respect to the offset
                if(value < 0)
                    value = store;

                // Then check if the current position's value is the
                // same as the first one found (int value), if it's not,
                // then this node needs to be subdivided
                if(store != value){

                    // Create 8 children for this node
                    children = new OctNode[8];

                    // And for each of the children...
                    for(int i=0; i<children.length; i++){

                        // Set their offset equal to this node's offset +
                        // this node's width/2 all with respect to it's
                        // individual quadrant (which is related to i)
                        Vector3f offS = new Vector3f(offset.x + (width/2f)*(i%2), offset.y + (width/2f)*((int)Math.floor(i/2f)%2), offset.z + (width/2f)*((int)Math.floor(i/4f)%2));

                        // Initialize the new child node
                        children[i] = new OctNode(array, (int)(width/2f), offS);

                        // And now do the same thing (recursion), but
                        // for a smaller area
                        children[i].generate();
                    }
                }
            }
        }
    }

    // This is only called if the node is completely made of one value
    if(children == null){
        data = value;
    }
}

That's the best I can explain it unfortunately. If you could point out an easier, faster way to do the same thing that would be amazing.

Solution

You are partitioning the tree too frequently. If you have a 16x16x16 array with all different values, you are going to recurse at every cell except the first, so you will call generate (16x16x16-1) times at the top level, rather than just once; the value of the children array will be overwritten many times over; of course, you will repeat the doing of unnecessary work at the next level down etc.

You should move the decision to subdivide the current octree node outside the nested for loops. For example:

public void generate(){
    // Assuming that width >= 1.
    int minValue = Integer.MAX_VALUE;
    int maxValue = Integer.MIN_VALUE;

    // Loop through an area an area of width*width*width
    // looking for min and max values in that area.
    for(int x=0; x<width; x++){
        for(int y=0; y<width; y++){
            for(int z=0; z<width; z++){
                int store = array[x+(int)offset.x][y+(int)offset.y][z+(int)offset.z];
                minValue = Math.min(minValue, store);
                maxValue = Math.max(maxValue, store);
            }
        }
    }

    if (minValue != maxValue) {
      // Subdivide if the min and maxValues are different,
      // as above.
      children = new OctNode[8];
      // etc.
    } else {
      data = minValue;
    }
}