适合不规则形状的最少矩形算法

Question

3

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

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

例如（其中X表示放置立方体的位置）。

OOOXXXOOOO
OOXXXXXXXO
OOXXXXXXXO
OOXXXXOOOO

目前可能用21个立方体或252个三角形来表示，但它可以很容易地表示为（其中每个字母表示矩形的一部分）

OOOAAAOOOO
OOBAAACCCO
OOBAAACCCO
OOBAAAOOOO

这只是由3个矩形或26个三角形组成的简单网格。

这些网格的典型大小为128x128x128，因此如果我能在合理的时间内有效地将形状减少到最少的矩形，则可以获得巨大的性能提升，但我对算法没有任何想法。

使用动态规划-最大正方形块是一种选择，但它不会得出最优解，尽管如果解决方案过于复杂而无法高效执行，则必须采用该方法。

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

- Nick Udell

你的网格中是否只有一个“形状”？ - Nicolas Repiquet

可能会生成孤立的“岛屿”X（我使用Ken Perlin的simplex noise生成这些地图） - Nick Udell

1

如果你正在渲染，难道不应该选择最少的顶点而不是最少的矩形吗？你可以抛弃所有在你的体积内部的顶点...（除非你有透明度） - ltjax

好的，我不确定为什么我打算以这种方式绘制它了。 - Nick Udell

参见： - Keith

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Nicolas Repiquet · Answer 1

或许可以使用“八叉树”这样的方法：

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

对于64x64x64网格中的每个单元格，请按以下方式进行：

现在，在64x64x64上建立一个32x32x32网格并重复此过程。

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

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