将最少的矩形拟合为不规则形状的算法

Question

我有一个渲染应用程序，可以在 3 维网格中渲染大量的立方体。这本质上是低效的，因为每个立方体代表 4 个顶点，并且立方体通常相邻，创建一个可以由单个矩形表示的表面。

为了填充区域，我使用了一个 3 维数组，其中 0 值表示空白区域，非 0 值表示 block 。

例如(其中 X 表示放置立方体的位置)

OOOXXXOOOO
OOXXXXXXXO
OOXXXXXXXO
OOXXXXOOOO

目前可以表示为 21 个立方体或 252 个三角形，而它可以很容易地表示为(其中每个字母表示矩形的一部分)

OOOAAAOOOO
OOBAAACCCO
OOBAAACCCO
OOBAAAOOOO

这仅仅是 3 个矩形，或 26 个三角形。

这些网格的典型大小是 128x128x128，所以很明显，如果我能在合理的时间内有效地将形状减少到尽可能少的矩形，我将受益于巨大的性能提升，但我一直没有想法一种算法。

使用 Dynamic programming - Largest square block将是一种选择，但它不会产生最佳答案，但如果解决方案太复杂而无法有效执行，那么这将是必经之路。

最终我将拥有多种类型的立方体(例如，绿色、棕色、蓝色，在数组中使用不同的非 0 数字进行引用)，因此如果可能的话，一个适用于多个类别的版本将非常有帮助。

Answer 1

也许像这样的“八叉树”:

在 128x128x128 网格上构建一个 64x64x64 网格，以便第一个网格的每个单元格“包含”第二个网格的高度单元格。

对于 64x64x64 网格的每个单元格，像这样进行:

• 如果高度包含的单元格具有相同的值，则将该值放入 64x64x64 网格中。
• 否则单独绘制每个单元格并将 -1 放入 64x64x64 网格中。

现在在 64x64x64 的网格上构建一个 32x32x32 的网格并重复。

然后 16x16x16、8x8x8、4x4x4、2x2x2、1x1x1 就完成了:)

当然，最好一次性计算八叉树，而不是每次渲染操作。