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]

Advertisements

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.


Mini Book Review: Graphics Programming in Windows (Charles Petzold)

November 14, 2008

Graphics Programming in Windows

My personal library is overcrowded, so over the years I have found it necessary to dispose of many books on outmoded technology. This book by Charles Petzold is different. Indeed, its unparalleled coverage of graphics programming techniques make it worth every inch of the space it takes up on my shelf.

Indeed, this book is a timeless classic. Although this it was written some time in the 1990s, its contents apply equally well to modern versions of Windows. Of course, it lacks details of the innovations that have occurred since it was written, but the programming techniques that it espouses will be as useful now as ever they were. Indeed, it is hard to find fault with a single example given in this volume.

Some people may find the book a little brief in places. Indeed, it does lack the depth of cover found in Petzold’s other books. Nevertheless, this book is without comparison in its subject area. If anyone is looking for a book on Windows Graphics, you’d be hard pressed to find one that is as informative as this one.

Sadly, Amazon lists this book as out of print. But, if you can obtain a copy of this book, I urge you to buy it. You won’t be sorry.

In short, highly recommended!