算法以适应矩形最少到不规则形状

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就大功告成了:)

当然，如果八叉树被计算一劳永逸，不是每个渲染操作将是最好的。