将 3D int 数组转换为 Java 中的八叉树

Question

我正在使用 LWJGL 在 Java 中创建体素引擎只是为了练习，但我被块管理系统卡住了。更具体地说，我正在尝试将块（块 ID 的 3D 整数数组）转换为八叉树以实现最佳渲染。

到目前为止，我的系统可以正常工作，但效率非常低。

这是一个 16*16*16 块的屏幕截图，其中 y=8 以下的所有位置都设置为 1（红色块）

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

我在 OctNode 生成器代码中添加了一个调试器，以找出它需要访问块数组的次数，结果返回 8392704。

为了生成8个子节点，访问chunk数组超过800万次

当我设置块数组只有y=4以下的块时，程序黑屏了将近30秒，调试器returns 1623199744数组访问。

超过 16 亿次数组调用仅生成 68 个子节点。

我显然需要减少数组调用的次数，这是肯定的，但我不确定我将如何去做。 Here's the github page for the project if you'd like to see the entire source 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;
    }
}

不幸的是，这是我能解释的最好的了。如果您能指出一种更简单、更快速的方法来完成同样的事情，那将是非常棒的。

Answer 1

您对树的分区过于频繁。如果您有一个包含所有不同值的 16x16x16 数组，您将在除第一个单元格之外的每个单元格处递归，因此您将在顶层调用 generate (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;
    }
}

将 3D int 数组转换为 Java 中的八叉树

Converting a 3D int array to an Octree in Java

java

arrays

optimization

lwjgl

octree