私は、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以外の数字を使用して参照されます)があるので、可能であれば複数のカテゴリで機能するバージョンが非常に役に立ちます。
グリッドには「形状」が1つありますか? –
Xsの孤立した "島"が生成される可能性があります(Ken Perlinのシンプレックスノイズを使ってこれらのマップを生成しています) –
レンダリングしている場合、最小の矩形ではなく、あなたはおそらくあなたのボリューム内のすべての頂点を投げ捨てることができます...(透明性を持たない限り) – ltjax