Copying and rotating a bitmap from a holding buffer to a display buffer is a common problem in computer graphics. If the holding buffer is the same size as the display buffer, blank pixels for which no data is stored in the holding buffer will be rotated on to the display buffer. This causes the corners of the display to appear blank or to hold garbage (Fig. 1). The common solution to this problem is to allocate an oversized holding buffer to hold all data that might be rotated on to the display.
The minimum size for this buffer is (2r)^2, where
In this equation h is the
height of the display buffer and w is the width, in pixels. No data outside of a circle of radius r
and centered on the center of the display buffer will ever appear in the output. Any data outside
this circle represents wasted RAM (Fig. 2). The amount of data wasted is the area of a unit circle
subtracted from the area of the oversized buffer. So (2r)^2 - pi*r^2 = 21.5% of the buffer is wasted space.
If a circular sparse array can be used, the space wasted by corners can be eliminated. In the C programming language such an array can be constructed.
In C, a two dimensional array can be set up by creating an array of pointers then pointing each pointer to a buffer. The buffers can be allocated at run time, and each buffer can have a different size. Bresenham's circle method can be used to determine the correct size of each buffer.
At first glance it sounds as if yes, this would create a circular sparse array, but indexing it would be a nightmare. But by using C's ability to perform pointer arithmetic, a pointer can be set to the center of the pointer array, and each pointer in that array can be set to the center of its buffer. Thus the center of the circular sparse array is at the origin, and is accessed with the syntax array[y][x].
Figure 3 shows a diagram of an actual circular sparse array created by the code accompanying this article. This circular sparse array was set up for debugging purposes, and was for an output buffer with a size of 10 pixels by 10 pixels. This array is somewhat larger than would be expected in order to account for some rounding error in Bresenham's method and the rotation code.
The implementation of the round sparse array is not difficult. It is very similar to the standard Bresenham's circle code.
First r is found using the size of the output buffer and the pythagorean theorem. After that the pointer array can be allocated. There needs to be 2r pointers in that array. Then the Bresenham's code can be started. The code accompanying this article also allocates two more arrays, which hold the positive and negative indices for each row. These arrays are used when loading the circular sparse array with a bitmap. After the circular sparse array is loaded one of the index arrays is deallocated.
There is a limitation in the current code, due to its implementation in DOS, which requires that one of the auxiliary arrays remain intact. Due to DOS's segmented memory scheme, each buffer needs to be allocated separately. A pointer to the first element of each buffer needs to be stored to be able to deallocate the buffer. If round arrays are implemented on a 32 bit system, the entire circular sparse array can be allocated in one chunk. One array of pointers is still needed for indexing the array, but the second array can be eliminated. Only a single pointer, pointing to the start of the array, is now needed for deallocating the array.
The main portion of the buffer creation code is exactly the same as Bresenham's circle code. But instead of calling a function to plot pixels a function is called to allocate memory. This function is worth looking at.
The memory allocation function takes two parameters, x and y. Like the standard Bresenham's circle algorithm, symmetry is used to reduce the number of calls to this function. Thus each call to the function can allocate four buffers.
When drawing circles, often times many calls are made that place pixels on the same pixel row, but with different x coordinates. Since we only need to allocate RAM once for each pixel row, a check is put in place to make sure RAM is not already allocated for the current pixel row.
Several extra pixels are allocated for each row to account for rounding error. There is rounding error in Bresenham's algorithm, which would require one or two extra pixels per row. But there could be rounding additional error in the rotation algorithm. Three extra pixels are allocated per row, two on the left side, one on the right. For an output buffer of 1024 * 768 these extra pixels account for less than 1% of the RAM used by the circular sparse array.
Once a buffer is allocated, a pointer from the pointer array is set to the center of the buffer. Since with the current implementation each buffer contains an even number of pixels, the pointer is set to the next pixel past the halfway point. This is why the indices indicated in figure 3 are not symmetric.
As indicated above, the code as it stands could be modified to use somewhat less RAM. This code was developed to run on a number of platforms, including DOS, which uses segmented memory. In DOS a single buffer cannot be greater than 64 kilobytes in size, so the code was designed to break the circular array into smaller chunks.
Two auxiliary arrays are kept to give the largest and smallest index of each row. These arrays are referenced when the circular sparse array is loaded. After the sparse array is loaded one of the index arrays is deallocated, but the other must be kept. That array is the only reference we have to the beginning of each row, and so it is needed to deallocate the array.
If the concern about 64K buffers is eliminated, for example by using a more modern operating system, then the final size of the circular sparse array can be determined algebraically before Bresenham's code is called. The entire buffer can be allocated in a single chunk of contiguous RAM, and Bresenham's code could be used to partition the buffer into rows. Then only a single pointer needs to be kept to deallocate the buffer. The two auxilliary index arrays could then be freed as soon as the sparse array is loaded.
If the above modification is made the programmer can change the pointer array into an array of indices, each index indicating the center of each row. This approach is not recommended since an additional math operation will then need to be performed for each pixel access. On most systems an integer is the same size as a pointer, so there is no space savings to this approach. The only advantage of using integer indices over pointers is that it makes the programmer's task slightly easier.
Another possible modification would be to load the sparse array as it is being allocated, thus entirely eliminating the auxiliary arrays. This is not easy since the standard Bresenham's code does not allocate rows in order. To make this approach work Bresenham's code will have to be modified to start at the top of the circle and work its way down. When drawing a standard circle this approach would increase the math needed significantly, and thus increase the time needed to draw the circle. But when loading the sparse array, the time needed to read data from the file is so much longer than the time needed to perform the math that no significant slow down is expected. This may be a worthwhile modification.
As described in the first section, the conventional rectangular array takes up (2r)^2 pixels, where the circular sparse array takes up pi*r^2 pixels. The variable r is the radius of the sparse array, which is found by taking half the length and width of the output buffer and applying the pythagorean theorem. Not counting overhead, there is a savings of 21.5%.
To account for overhead, first assume a 32 bit architecture. The pointer array adds an additional 8r bytes, since the pixel array contains 2r pointers, and each pointer is 4 bytes. Each auxiliary index array takes the same amount of space, but since with the proper modifications the auxiliary arrays will be eliminated after the sparse array is loaded, these arrays will not be counted in the overhead. With this modification one extra pointer is still needed to deallocate the sparse array.
Each row has four extra pixels added to it to account for rounding error. Assuming 8 bits per pixel, this accounts for an additional 4r bytes. The total RAM required for the circular sparse array is pi*r^2 + 12r + 4 pixels, as opposed to (2r)^2 for the conventional rectangular buffer.
Assuming a 1024 * 768 output buffer and 8 bits per pixel, r would be 640. The conventional rectangular buffer would be 1,638,400 bytes. The circular sparse array would be 1,286,797 + 7680 + 4 = 1,294,481 bytes. This gives a savings of 21%.
There is a slight performance hit. For each pixel access there are two pointer dereferences, where for the conventional rectangular buffer there is only one. If rotation speed is paramount this should be kept in mind. However if RAM limitations are an overriding concern the round sparse array might be well worth while.
This page last update on 12/21/96
Return to Image Processing Index