Infinite Bitmap

Question

I'd like to build a bitmap during runtime. The bitmap should be scalable on all sides and pixel access should be quiet efficient.

Between and after the commands shown in the picture, Map.setPixel() and Map.getPixel() should set/return data saved in the bitmap.

I don't expect an implementation just a concept how to allocate memory in such a way that the setPixel()/getPixel is as fast as possible.

Answer 1

If the extend() operation needs to be reasonably fast, a Quadtree might be a good fit; it actually wouldn't even require explicit extend operations. Admittedly, it would not yield optimal performance for random access to individual pixels, but your comment says that your primary operation is iterating over the pixels, which a quadtree could do very fast, perhaps almost as fast as a matrix-based implementation (and faster if iteration does not always happen in the same way the matrix is laid out).

Your requirements actually sound like you're trying to implement a cellular automaton like the Game of Life. You might want to take a look at Hashlife, an extremely high-performing way to implement the Game of Life on an infinite grid. Note that it's based on a Quadtree, but does some very smart additional optimizations based on the locality of the game rules.

Answer 2

@SecStone said that there's enough time available for the expansion operation, so the easiest and most efficient way to store the pixels is using a single flat array or a two dimensional array, as pixels can be accessed in constant time then.

Answer 3

By Hand

If memory is not a very sparse resource, I consider working in bigger chunks.
Here's some pseudo-code.

class Chunk {
    Chunk new(int size) {...}
    void setPixel(int x, int y, int value) {...}
    int getPixel(int x, int y) {...}
}

class Grid {
    Map<int, Map<Chunk>> chunks;
    Grid new(int chunkSize) {...}
    void setPixel(int x, int y, int value) {
         getChunk(x,y).setPixel(x % chunkSize, y % chunkSize, value);//actually the modulo could be right in Chunk::setPixel and getPixel for more safety
    }
    int getPixel(int x, int y) { /*along the lines of setPixel*/ }
    private Chunk getChunk(int x, int y) {
         x /= chunkSize;
         y /= chunkSize;
         Map<Chunk> row = chunks.get(y);
         if (row == null) chunks.set(y, row = new Map<Chunk>());
         Chunk ret = row.get(x);
         if (ret == null) row.set(x, ret = new Chunk(chunkSize));
         return ret;
    }
}

This implementation is quite naive.
For one, it creates chunks in getPixel (basically it would be fine to simply return 0 or so, if no chunks was defined for that position). Secondly it is based on the assumption, that you have a sufficiently fast and scalable implementation of Map. To my knowledge every decent language has one.

Also you will have to play with the chunk size. For dense bitmaps, a big chunk size is good, for sparse bitmaps a smaller chunk size is better. In fact for very sparse ones, a "chunk size" of 1 is the best, rendering the "chunks" themselves obsolete and reducing the data structure to an int map of an int map of pixels.

Off the shelf

Another solution might be to look at some graphics libraries. They are actually quite good at drawing one 2D buffer into another. That would mean you'd simply allocate a bigger buffer and have the original drawn into it at the according coordinates.

As a general strategy: When having a "dynamically growing memory block", it is a good idea to allocate a multiple of it, once it is used up. This is rather memory intense, but significantly cuts allocation and copying costs. Most vector implementations allocate twice their size, when it's exceeded. So especially if you go with the off-the-shelf solution, don't extend you buffer just by 1 pixel, because only one pixel was requested. Allocated memory is cheap. Reallocating, copying and releasing is expensive.

Answer 4

Just a couple of points of advice:

• If you implement this as an array of some integral type (or an array of arrays of ...) you probably should grow the backing array by some number of bits / pixels each time to avoid having to shift the bits as you copy them. The down-side is that you use more space, but the proportion of wasted space drops as the bitmap gets bigger.

• If you use a Map-based data structure, you can finesse the problem of growing the bitmap by simply relocating the x,y coordinate arguments of the getPixel and setPixel calls.

• If you use a Map-based data structure, you only need map entries for the "ones". The "zeros" can indicated by the absence of an entry. This saves up a significant amount of space, especially if the bitmap is mostly zeros.

• You don't need to use a Map of Maps. You can encode an int x,y pair as a single long. An analogous process can be used to map an array of arrays to an array.

---

Finally, you need to balance 3 things:

1. the performance of getPixel and setPixel,
2. the performance of the extend* operations, and
3. the space utilization.

Answer 5

Before trying anything else more complicated, and unless you cannot hold everything in memory, keep things simple and use a two dimensional array together with the information about the origin of your coordinate system. To expand it, use the same strategy like, for example, the C++ std::vector does: make a distinction between the actual size of your array and the capacity of the array, and expand the capacity in chunks whenever the limit is reached. "capacity" here should be defined in terms of intervals (from_x, to_x), (from_y,to_y).

This may need a complete reallocation of the memory from time to time, but as long as this does not happen too often, it may be fast enough for your purpose (in fact, you have to try / profile this).

Answer 6

The absolute fastest way to do pixel access is a two-dimensional array of individually-addressable pixels.

For extensions, start with a simple implementation that reallocates and copies every time (since you'll need that code anyway). If profiling doesn't indicate that you're spending a lot of time at it, there's no need to refine it further.

If profiling reveals a need to keep the number of re-allocations down and you're not memory-constrained, consider over-allocating by a percentage in each direction and storing an offset to the origin. (E.g., if you start a new bitmap at 1x1 and allocate a 9x9 array to hold it, the initial x and y offsets would be 4.) The trade-off here is having to do extra math during pixel access to apply the offset.

If extensions turn out to be really expensive, you could try one or both of these:

• Handle vertical and horizontal extensions differently. Extending an array vertically in any direction can be accomplished by allocating a new block and doing a single copy of the entire existing array to the appropriate offset in the new memory. Compare that to horizontal extensions, where you have to do that operation once per row because the existing data isn't contiguous in the new block.

• Keep track of the most frequent amount and direction of extension. Use that information to select a new size and offset which will reduce the probability of having to do a re-allocate-and-copy for any extension.

Personally, I doubt you're going to need either of those unless the pixel-access-to-extension ratio is low.

Answer 7

• Constant size tiling (say, 256x256, but with infinite number of tiles)
• Provide a bitmap wrapper that allows negative pixel coordinates (to give the impression that an image can be expanded in all four directions without having to recompute/synchronize references to existing coordinate values)
  • The actual bitmap class (working beneath the wrapper), however, should only support absolute (non-negative) coordinates.
• Under the wrapper, provide tile-level (block-level) access using memory-mapped I/O
• In addition to Map.setPixel() and Map.getPixel() which modifies single pixel at a time, also provide methods which copies and modifies one rectangle of pixels at a time. This will allow the caller to choose the more efficient form of access depending on information available to the caller.
  • Commercial libraries also provide methods to update: one row of pixels, one column of pixels, scatter/gather updates, and arithmetic/logic blitter operations in one step (to minimize data copying).

(Let's not upvote the hilarious answers ...)

Answer 8

The most flexible and perhaps reliable implementation is a linked list with structs giving x-coordinate, y-coordinate, and bit value. I would build that first and get it working.

Then, if it is too slow and/or big, try the usual ways of speeding it up: array, matrix, bitmap, compression, caching, inversion, storing only '1' values, etc.

It is easier to make a slow correct implementaiton faster than it is to fix a buggy fast implementation. And while testing your 'fast' second implementation you've got a refernce standard to compare it against.

And, who knows, you'll probaby discover that the slow version is fast enough. As long as the entire structure fits in memory, things are amazingly fast already.

Answer 9

I propose the following implementation in Python:

class Map(dict): pass

It has the following advantages:

1. Get/Set access via map[(1,2)] can be considered O(1).
2. The need to explicitly extend the grid vanishes.
3. There is little space for bugs.
4. It is easily upgraded to 3D, if ever necessary.

Answer 10

If you actually need a bitmap of any arbitrary size - and I mean anything from 1x1 to 1000000x1000000 amd up, and need it expandable on demand... one possible way is to use a database. It may seem counter intuitive at first, but what you really have is a storage problem. A database will let you access individual pixels and store essentually any amount of data. I dont necessarily mean an SQL db, btw.

Will it be fast enough for your purposes? That I cant answer, as there's no context here regarding what you are doing with this bitmap. But if this is for screen display, consider that you'd generally only need to pull back the additional scan rows to display as the screen scrolls, not all the data.

That being said, I cant help but wonder if you're going about something wrong. Should you perhaps instead by using vector based graphic and tracking individual entieties in memory, and then rendering a bitmap only as big as needed for the screen?

Answer 11

Here's steps to make it work properly:

1. use forwarding from one interface to another to build a tree of objects which together represent the bitmap
2. every "extension" of the bitmap will allocate it's own memory and provide another interface for it

3. example implementation would be:

   template<class T, class P>
   class ExtendBottom {
   public:
      ExtendBottom(T &t, int count) : t(t), count(count),k(t.XSize(), count) { }
      P &At(int x, int y) const { if (y<t.YSize()) return t.At(x,y); else return k.At(x, y-t.YSize()); }
      int XSize() const { return t.XSize(); }
      int YSize() const { return t.YSize()+count; }
   private:
      T &t;
      int count;
      MemoryBitmap k;
   };
   

Obviously for real implementation, the XSize() and YSize() would not work, but you'll need MinX(), MaxX(), MinY(), MaxY() or something like that to keep index numbers consistent.