Reducing J2ME Size with Advanced PNG Compression

June 15, 2009

One way to reduce the size of a J2ME application is through better compression of the PNG images you are using.

I currently use the excellent Paint.Net to create my images. Unfortunately, it doesn’t compress PNG output very effectively. It is particularly poor with monochrome images. Ideally, these would be saved in 2-bit color mode, but the best Paint.Net can do is 8-bit color. Surprisingly, this limitation is not unique to Paint.Net: numerous other tools have the same limitation. For example, I have created a monochrome image (containing a bitmapped font) and this was saved by Paint.Net using 8-bit color. It weighed in at 2352 bytes.

One of Paint.Net’s best features is its support for a wide range of plugins. One of these is able to host a PNG compressor called OptiPng. This is able to save 2-bit color and reduce the file down to just 928 bytes. A huge improvement.

Better still, a stand-alone little utility called PngGantlet uses the incredible PNGOOUT compressor to achieve even better results. It was able to shrink this image down to a mere 806 bytes: that’s just 34% of the size of the original image, with no loss of quality.

This is all the more impressive when you consider that the same image as a BMP file comes in at a massive 14,902 bytes (806 = 5.4% of 14902).

Here’s a summary of my results:

File Size (bytes) ~%
BMP 14,902 633%
Original PNG Image 2352 100%
OptiPNG 928 39%
PngGantlet 806 34%

One caveat – these figures don’t take into account the additional compression that is undertaken to convert the final application into a .jar file. I assume this compression will be less effective on the final 806-byte file than the original 2353-byte file.

Nevertheless, I don’t doubt that applying the compressor to all my images will result in a significantly smaller application.

Advertisements

A Better J2ME fillTriangle

June 2, 2009

I recently wrote about my alternative fillTriangle method.

Pattern Fill

The reason I created this method was to support older devices that don’t have a built-in version of fillTriangle. However, the implementation could be useful on more modern devices where we need more control over the way that the trinangle is rendered. For example, the buit-in version of fillTriangle only enables us to paint triangles with a solid colour. On the other hand, my routine can be customised to to enable us to fill triangles with a pattern.

A simple example is to paint triangles with horizontal stripes. To do this, we can take my original code and replace the drawHorizontalLine method with this code:

    protected void drawHorizontalLine(int x1, int x2, int y)
    {
        // For odd numbered lines...
        if ((y & 1) == 1)
        {
            // Paint magenta.
            graphics.setColor(255,0,255);
        } else {
            // Paint yellow.
            graphics.setColor(255,255,0);
        }
        // Draw the line.
        graphics.drawLine(x1, y, x2, y);
    }

Something like this could be adapted to produce alternative patterns (which I leave as an irritating excercises for the reader).

Pixel Accuracy

In that article, I mentioned that my method isn’t pixel perfect because of rounding error. The problem is that java’s integer division always rounds down. For exmaple, using java integer arithmetic, 1 / 3 = 0 and 2 / 3 = 0. I suggested previously that one way to overcome this is to use a fixed point library. However there is another way to eliminate the rounding errors.

I noticed that the rounding errors could be overcome if we could add 0.5 to the result before rounding occurs. Of course, you can’t add a fraction using integer arithmetic! Nevertheless, with a little algebraic magic, we can achieve the same result.

At the moment we have:

result = floor(n / d)

But the correct answer is:

result = floor (n/d + 1/2)

Which is equivalent to:

result = floor( (2n + d) / 2d )

No more fractions!

This means we can change all the divisions in my original code to this new format. Thus:

sx = ax + ac_num * y / ac_den;

becomes:

sx = ax + (2 * ac_num * y + ac_den) / 2 * ac_den;

and so forth.

Here’s my updated code:

protected void fillTriangle(int ax, int ay, int bx, int by, int cx, int cy)
{
// http://www.geocities.com/wronski12/3d_tutor/tri_fillers.html

// Sort the points so that ay <= by <= cy int temp; if (ay > by)
{
temp = ax;
ax = bx;
bx = temp;
temp = ay;
ay = by;
by = temp;
}
if (by > cy)
{
temp = bx;
bx = cx;
cx = temp;
temp = by;
by = cy;
cy = temp;
}
if (ay > by)
{
temp = ax;
ax = bx;
bx = temp;
temp = ay;
ay = by;
by = temp;
}

// Calc the deltas for each edge.
int ab_num;
int ab_den;
if (by – ay > 0)
{
ab_num = (bx – ax);
ab_den = (by – ay);
}
else
{
ab_num = (bx – ax);
ab_den = 1;
}

int ac_num;
int ac_den;
if (cy – ay > 0)
{
ac_num = (cx – ax);
ac_den = (cy – ay);
}
else
{
ac_num = 0;
ac_den = 1;
}

int bc_num;
int bc_den;
if (cy – by > 0)
{
bc_num = (cx – bx);
bc_den = (cy – by);
}
else
{
bc_num = 0;
bc_den = 1;
}

// The start and end of each line.
int sx;
int ex;

// The heights of the two components of the triangle.
int h1 = by – ay;
int h2 = cy – by;

// Some calculations extracted from the loops.
int ab_num_x2 = ab_num * 2;
int ab_den_x2 = ab_den * 2;

int ac_num_x2 = ac_num * 2;
int ac_den_x2 = ac_den * 2;

int bc_num_x2 = bc_num * 2;
int bc_den_x2 = bc_den * 2;

// If a is to the left of b…
if (ax < bx) { // For each row of the top component... for (int y = 0; y < h1; y++) { sx = ax + (ac_num_x2 * y + ac_den) / ac_den_x2; ex = ax + (ab_num_x2 * y + ab_den) / ab_den_x2; drawHorizontalLine(sx, ex, ay + y); } // For each row of the bottom component... for (int y = 0; y < h2; y++) { int y2 = h1 + y; sx = ax + (ac_num_x2 * y2 + ac_den) / ac_den_x2; ex = bx + (bc_num_x2 * y + bc_den) / bc_den_x2; drawHorizontalLine(sx, ex, by + y); } } else { // For each row of the bottom component... for (int y = 0; y < h1; y++) { sx = ax + (ab_num_x2 * y + ab_den) / ab_den_x2; ex = ax + (ac_num_x2 * y + ac_den) / ac_den_x2; drawHorizontalLine(sx, ex, ay + y); } // For each row of the bottom component... for (int y = 0; y < h2; y++) { int y2 = h1 + y; sx = bx + (bc_num_x2 * y + bc_den) / bc_den_x2; ex = ax + (ac_num_x2 * y2 + ac_den) / ac_den_x2; drawHorizontalLine(sx, ex, by + y); } } } [/sourcecode]


MIDP 1.0 fillTriangle Method

June 1, 2009

One of the (many) limitations of MIDP 1.0 is that it lacks the fillTriangle that is present in MIDP 2.0. Below is a replacement method that works on MIDP 1.0 devices. It is based on notes published by Michal Wronski.

Michal’s algorithm depends on floating-point math – also unavailable in MIDP 1.0. With a little refactoring I was able to create an integer-only approximation. Sadly, rounding errors mean that my routine isn’t pixel perfect. An alternative that would give more accurate results would be to use some kind of fixed-point library. Despite its shortcomings, however, my method is good enough for many practical purposes (including my own).

protected void drawHorizontalLine(int x1, int x2, int y)
{
graphics.drawLine(x1, y, x2, y);
}

protected void fillTriangle(int ax, int ay, int bx, int by, int cx, int cy)
{
// http://www.geocities.com/wronski12/3d_tutor/tri_fillers.html

// Sort the points so that ay <= by <= cy int temp; if (ay > by)
{
temp = ax;
ax = bx;
bx = temp;
temp = ay;
ay = by;
by = temp;
}
if (by > cy)
{
temp = bx;
bx = cx;
cx = temp;
temp = by;
by = cy;
cy = temp;
}
if (ay > by)
{
temp = ax;
ax = bx;
bx = temp;
temp = ay;
ay = by;
by = temp;
}

// Calc the deltas for each edge.
int ab_num;
int ab_den;
if (by – ay > 0)
{
ab_num = (bx – ax);
ab_den = (by – ay);
}
else
{
ab_num = (bx – ax);
ab_den = 1;
}

int ac_num;
int ac_den;
if (cy – ay > 0)
{
ac_num = (cx – ax);
ac_den = (cy – ay);
}
else
{
ac_num = 0;
ac_den = 1;
}

int bc_num;
int bc_den;
if (cy – by > 0)
{
bc_num = (cx – bx);
bc_den = (cy – by);
}
else
{
bc_num = 0;
bc_den = 1;
}

// The start and end of each line.
int sx;
int ex;

// The heights of the two components of the triangle.
int h1 = by – ay;
int h2 = cy – by;

// If a is to the left of b…
if (ax < bx) { // For each row of the top component... for (int y = 0; y < h1; y++) { sx = ax + ac_num * y / ac_den; ex = ax + ab_num * y / ab_den; drawHorizontalLine(sx, ex, ay + y); } // For each row of the bottom component... for (int y = 0; y < h2; y++) { int y2 = h1 + y; sx = ax + ac_num * y2 / ac_den; ex = bx + bc_num * y / bc_den; drawHorizontalLine(sx, ex, by + y); } } else { // For each row of the bottom component... for (int y = 0; y < h1; y++) { sx = ax + ab_num * y / ab_den; ex = ax + ac_num * y / ac_den; drawHorizontalLine(sx, ex, ay + y); } // For each row of the bottom component... for (int y = 0; y < h2; y++) { int y2 = h1 + y; sx = bx + bc_num * y / bc_den; ex = ax + ac_num * y2 / ac_den; drawHorizontalLine(sx, ex, by + y); } } } [/sourcecode] I release this code into the public domain. You can use it as you please.