Преобразование массива 3D int в Octree в Java

Question

Я создаю воксельный движок в Java, используя LWJGL просто для практики, но я застреваю в системе управления чанками. В частности, я пытаюсь преобразовать Chunk, который представляет собой просто трехмерный массив целых чисел для идентификатора блока, в Octree для оптимального рендеринга.

Пока у меня работает система, но она ужасно неэффективна.

Вот скриншот фрагмента 16*16*16 со всеми позициями ниже y=8, установленными в 1 (красные блоки)

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

Я добавил отладчик в код генератора OctNode, чтобы узнать, сколько раз ему нужно было получить доступ к массиву чанков, и он вернулся с 8392704.

Он получил доступ к массиву чанков более 8 миллионов раз только для генерации 8 дочерних узлов.

Когда я установил в массиве чанков только блоки ниже y=4, программа имеет черный экран в течение почти 30 секунд, и отладчик возвращает 1623199744 обращений к массиву.

Более 1,6 миллиарда обращений к массиву только для генерации 68 дочерних узлов.

Очевидно, мне нужно уменьшить количество обращений к массиву, это наверняка, но я не уверен, как бы я поступил так. Вот страница github для проекта, если вы хотите увидеть весь исходный код.

Вот важные части моего кода:

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;
    }
}

Это лучшее, что я могу объяснить, к сожалению. Если бы вы могли указать более простой и быстрый способ сделать то же самое, что было бы удивительно.

Answer 1

Вы слишком часто разделяете дерево. Если у вас есть массив 16x16x16 со всеми различными значениями, вы будете выполнять рекурсию в каждой ячейке, кроме первой, так что вы будете вызывать генерировать (16x16x16-1) раз на верхнем уровне, а не один раз; значение children массив будет перезаписан много раз; конечно, вы будете повторять выполнение ненужной работы на следующем уровне и т. д.

Вы должны перенести решение о подразделении текущего узла октодерева вне вложенных циклов for. Например:

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;
    }
}