将最少矩形拟合到不规则形状的算法
我有一个渲染应用程序，可以在 3 维网格中渲染大量立方体。这本质上是低效的，因为每个立方体代表 4 个顶点，并且立方体通常是相邻的，从而创建一个可以由单个矩形表示的表面。
为了填充该区域，我使用了一个 3 维数组，其中 0 值表示空白空间，非 0 值表示一个块。
例如（其中 X 表示放置立方体的位置）
OOOXXXOOOO
OOXXXXXXXO
OOXXXXXXXO
OOXXXXOOOO
当前将表示为 21 个立方体，或 252 个三角形，而它可以很容易地表示为（其中每个字母表示矩形的一部分），
OOOAAAOOOO
OOBAAACCCO
OOBAAACCCO
OOBAAAOOOO
即仅 3 个矩形，或26个三角形。
这些网格的典型大小是 128x128x128，因此很明显，如果我能够在合理的时间内有效地将形状减少到尽可能少的矩形，我将受益于巨大的性能提升，但我一直在寻找算法的想法。
使用 动态规划 - 最大方块 是一种选择，但不会产生结果在最佳答案中，尽管如果解决方案太复杂而无法有效执行，那么这必须是要走的路。
最终我将拥有多种类型的立方体（例如绿色、棕色、蓝色，使用数组中不同的非 0 数字进行引用），因此如果可能的话，适用于多个类别的版本将非常有帮助。
I have a rendering application that renders lots and lots of cubes in a 3-dimensional grid. This is inherently inefficient as each cube represents 4 vertices, and often the cubes are adjacent, creating one surface that could be represented by a single rectangle.
To populate the area I use a 3-dimensional array, where a value of 0 denotes empty space and a non-0 value denotes a block.
e.g. (where X denotes where a cube would be placed)
OOOXXXOOOO
OOXXXXXXXO
OOXXXXXXXO
OOXXXXOOOO
would currently be represented as 21 cubes, or 252 triangles, whereas it could easily be represented as (where each letter denotes a part of a rectangle)
OOOAAAOOOO
OOBAAACCCO
OOBAAACCCO
OOBAAAOOOO
which is a mere 3 rectangles, or 26 triangles.
The typical size of these grids is 128x128x128, so it's clear I would benefit from a massive performance boost if I could efficiently reduce the shapes to the fewest rectangles possible in a reasonable amount of time, but I'm stuck for ideas for an algorithm.
Using Dynamic programming - Largest square block would be one option, but it wouldn't result in an optimal answer, although if the solution is too complex to perform efficiently then this would have to be the way to go.
Eventually I will have multiple types of cubes (e.g. green, brown, blue, referenced using different non-0 numbers in the array) so if possible a version that would work with multiple categories would be very helpful.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
也许是“八叉树”之类的东西：
在 128x128x128 网格上构建一个 64x64x64 网格，以便第一个网格的每个单元格“包含”第二个网格的高度单元格。
对于 64x64x64 网格中的每个单元格，请按以下步骤操作：
现在在 64x64x64 网格上构建一个 32x32x32 网格并重复。
然后是 16x16x16、8x8x8、4x4x4、2x2x2、1x1x1，你就完成了:)
当然，最好一次性计算八叉树，而不是每次渲染操作。
Maybe something "octree" like:
Build a 64x64x64 grid over your 128x128x128 grid so each cell of the first grid "contains" height cells of the second.
For each cell, of the 64x64x64 grid, proceed like that:
Now build a 32x32x32 grid over the 64x64x64 one and repeat.
Then 16x16x16, 8x8x8, 4x4x4, 2x2x2, 1x1x1 and you're done :)
Of course, it would be best if the octree was computed once and for all, not for each rendering operation.