将3D int数组转换为Java中的Octree

Question

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

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

这里的一个16 * 16 * 16块具有低于Y = 8设置为1的所有位置的屏幕截图（红色块）

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

我添加了一个调试器的OctNode发生器代码以查找取出访问块数组需要多少次，然后返回。

它仅仅为了生成8个子节点就访问了超过800万次的块数组。

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

超过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的数组，其值为所有不同的数值，那么除了第一个单元格外，你将在每个单元格上进行递归，因此你将在顶层调用生成（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; 
    } 
}