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:

[sourcecode language=’java’]

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);

}

[/sourcecode]

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:

[sourcecode language=’java’]

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 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]