A Better J2ME fillTriangle

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]