1

練習用に LWJGL を使用して Java でボクセル エンジンを作成していますが、チャンク管理システムで行き詰まっています。より具体的には、最適なレンダリングのために、ブロック ID の整数の 3D 配列であるチャンクをオクツリーに変換しようとしています。

これまでのところ、システムは機能していますが、非常に非効率的です。

これは 16*16*16 チャンクのスクリーンショットで、y=8 より下のすべての位置が 1 に設定されています (赤いブロック)。

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

OctNode ジェネレーター コードにデバッガーを追加して、チャンク配列へのアクセスに必要な回数を調べたところ、8392704が返されました。

8 つの子ノードを生成するためだけに、チャンク配列に 800 万回以上アクセスしました。

y=4 未満のブロックのみを持つようにチャンク配列を設定すると、プログラムはほぼ 30 秒間黒い画面になり、デバッガーは1623199744の配列アクセスを返します。

68 個の子ノードを生成するためだけに、16 億回を超える配列呼び出し。

明らかに、配列呼び出しの数を減らす必要がありますが、それは確かですが、どうやってそれを行うのかわかりません。ソース コード全体を見たい場合は、プロジェクトの 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;
    }
}

残念ながら、それが私が説明できる最善の方法です。同じことをより簡単かつ迅速に行う方法を指摘できれば、それはすばらしいことです。

4

1 に答える 1

1

ツリーを分割する頻度が高すぎます。すべてが異なる値を持つ 16x16x16 の配列がある場合、最初のセルを除くすべてのセルで再帰を実行するため、1 回だけではなく、最上位レベルで生成 (16x16x16-1) 回を呼び出します。配列の値はchildren何度も上書きされます。もちろん、次のレベルダウンなどで無駄な作業を繰り返します。

現在の octree ノードを再分割する決定を、ネストされた 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;
    }
}
于 2015-03-31T06:28:18.653 に答える