不規則な形状に最小の矩形を適合させるアルゴリズム

Question

私は、3次元グリッドにたくさんのキューブをレンダリングするレンダリングアプリケーションを用意しています。これは、各キューブが4つの頂点を表し、しばしばキューブが隣接し、単一の矩形で表現できる1つのサーフェスを作成するため、本質的に非効率的です。

領域を設定するには、3次元配列を使用します。値0は空白を示し、0以外の値はブロックを示します。

それは容易

（各文字矩形の部分を表す）として表すことができるのに対し、（キューブが配置される場合、Xが表す）

OOOXXXOOOO 
OOXXXXXXXO 
OOXXXXXXXO 
OOXXXXOOOO 

は、現在、21個のキューブ、または252個の三角形として表されることになります

OOOAAAOOOO 
OOBAAACCCO 
OOBAAACCCO 
OOBAAAOOOO 

これは単なる3つの長方形または26の三角形です。

これらのグリッドの典型的なサイズは128x128x128ですので、妥当な時間内に可能な最小限の四角形に効率的にシェイプを縮小することができれば、大幅なパフォーマンス向上が得られることは明らかですが、アルゴリズムのために。

Dynamic programming - Largest square blockを使用すると1つのオプションになりますが、ソリューションが効率的に実行するには複雑すぎる場合は最適な回答にはなりません。

最終的には、複数の種類のキューブ（例：緑色、茶色、青色、配列内に異なる0以外の数字を使用して参照されます）があるので、可能であれば複数のカテゴリで機能するバージョンが非常に役に立ちます。

Answer 1

たぶん何か「オク」：

があなた128x128x128グリッド上64x64x64のグリッドを構築するので、第1グリッドの各セルは、第二の高細胞「が含まれて」。 64x64x64のグリッドの各セルに対して

、そのように進んでください。

• 高さは細胞が64x64x64のグリッドにその値を入れて、同じ値を持っている含まれている場合。
• そうでない場合は、各セルを個別に描画し、64x64x64グリッドに-1を入れます。

64x64x64の上に32x32x32グリッドを作成して繰り返します。

その後16x16x16、8×8×8、4x4x4、2x2x2の、1x1x1とあなたは:)もちろん

を行っているオクトツリーはすべてのためではなく、各レンダリング操作のために一回と計算されたならば、それが最善だろう。