算法以適應矩形最少到不規則形狀

Question

我有呈現許許多多立方體在一個3維網格呈現應用。這本質上是低效的，因爲每個立方體代表4個頂點，並且通常立方體相鄰，從而創建可以由單個矩形表示的一個表面。

要填充區域我使用的3維陣列，其中0值表示空的空間和非0值表示塊。

例如（其中X表示其中，立方體將被放置）

OOOXXXOOOO 
OOXXXXXXXO 
OOXXXXXXXO 
OOXXXXOOOO 

將目前被表示爲21個立方體，或252點的三角形，而它可以很容易被表示爲（其中每個字母表示一個矩形的一部分）

OOOAAAOOOO 
OOBAAACCCO 
OOBAAACCCO 
OOBAAAOOOO 

這僅僅是一個3個矩形，或26點的三角形。

這些網格的典型尺寸是128x128x128，所以很明顯，如果我可以在合理的時間內將形狀有效地縮小到最少的矩形，我將從大幅度的性能提升中受益，但我對於想法對於算法。

使用Dynamic programming - Largest square block將是一種選擇，但它不會產生最佳答案，但如果解決方案太複雜而無法有效執行，那麼這將不得不順利進行。

最終我將有多種類型的多維數據集（例如綠色，棕色，藍色，在陣列中使用不同的非0號引用），所以如果可能的話，將與多個類別的工作一個版本將是非常有益的。

Answer 1

也許一些「八叉樹」，如：

建立一個64x64x64格在你的128x128x128電網所以第一網格的每個單元「包含」第二高度的細胞。

對於每個小區，則64x64x64網格，進行這樣的：

• 如果高度所含細胞具有相同的值，把該值在64x64x64網格。
• 否則單獨繪製每個單元格並將-1放置在64x64x64網格中。

現在在64x64x64上構建一個32x32x32網格並重復。

然後16x16x16，8x8x8，型4x4x4，2x2x2的，1x1x1就大功告成了:)

當然，如果八叉樹被計算一勞永逸，不是每個渲染操作將是最好的。