“二维内存管理"的高效算法 [英] Efficient algorithm for "2D memory management"

问题描述

我正在开发基于 OpenGL 的应用程序，该应用程序需要能够动态生成一组不断变化的纹理.

I am working on an OpenGL-based app that needs to be able to generate a changing set of textures on the fly.

从我最初的阅读来看，为我需要绘制的每个图像使用单独的纹理是一个非常糟糕的主意，因为绑定纹理以便可用于渲染的操作非常慢.

From my initial reading it sounds like it would be a really bad idea to use a separate texture for each image that I need to draw as the operation of binding a texture so that is can be used for rendering is really slow.

首选的方法是将许多这些需要的图像组合成一个更大的图像，然后绑定该纹理一次，然后仅绘制其中的摘录(精灵).

The preferred approach would be to combine many of these needed images into a single bigger image and binding that texture once and drawing only excerpts from it (sprites).

不幸的是，我的图像可能有非常不同的大小，并且以某种不可预测的方式变得需要和过时.

Unfortunately my images can have very different sizes and become needed and obsolete in somewhat unpredictable ways.

所以，我需要的是一种内存管理器，它在我的纹理中维护一个已用和空闲区域的列表，并且可以为新的/过时的图像分配/处置区域.

So, what I need is a sort of memory manager that maintains a list of used and free regions in my texture(s) and can allocate/dispose areas for new/obsolete images.

这基本上是每个程序需要为内存管理做的事情(在堆中分配和处理不同大小的变量)，除了它是一个二维问题，因为我在一个大正方形内分配矩形而不是短线"更长的.

It's basically what every program needs to do for memory management (allocate and dispose variables of different size in the heap), except it's a 2D problem, since I'm allocating rectangles inside a big square rather than short "lines" in a longer one.

我要解决的问题是否有名称?是否有(或多个)标准/最佳实践方法?

Is there a name for the problem I am trying to solve and is there a (or multiple) standard/best-practice approach(es)?

(快速澄清:我不是在寻找处理引用计数等的方法来找出不再使用的图像.我正在寻找一种在补丁中保留新矩形的方法-现有的和差距的工作，最大限度地减少(消除?)其他矩形的任何重新排列.)

更新:

我想出了一个不同方法的想法，但决定将其发布为 新问题要调查.

推荐答案

这看起来类似于 2D 装箱问题 - 这是 NP-hard，但是您可以使用断头台切割启发式(请参阅 这里 的解释和here 一些源代码)在多项式时间内近似解决问题.

This looks similar to a 2D bin-packing problem - this is NP-hard, however you can use a guillotine cut heuristic (see here for an explanation and here for some source code) which approximately solves the problem in polynomial time.

标准的 2D 装箱算法不包括对象的删除.我的建议是维护一个可用空间的搜索树，并使用最适合或最适合的方法将新对象分配给可用空间，然后当一切变得足够碎片化时(例如，当您无法找到足够的可用空间来分配对象时)) 重新运行完整的装箱算法.如果完全重新排列对象是非常不受欢迎的，那么您可以将屏幕空间分成四等分(或十六分之一或其他)，并仅在屏幕上具有最多可用空间的部分重新运行装箱算法.

The standard 2D bin-packing algorithm doesn't include the deletion of objects. My recommendation is to maintain a search tree of free spaces and assign new objects to free space using first-fit or best-fit, then when everything becomes sufficiently fragmented (e.g. when you're not able to find enough free space to allocate an object) you re-run the full bin-packing algorithm. If a full rearrangement of objects is highly undesirable then you can instead split the screen space into quarters (or sixteenths or whatever) and only re-run the bin-packing algorithm on the portion(s) of the screen with the most free space.

这篇关于“二维内存管理"的高效算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！