## Algorithm to draw filled triangle

7 posts / 0 new
Author
Message

I was looking for an algorithm to draw filled triangles, I found one from Adafruit's Graphics library, but I kept on looking for something more efficient. I found some code from http://www.sunshine2k.de/, it is based on the Bresenham's line algorithm and I optimized a bit further.

I have found that the Bresenham's algorithm, besides being more efficient (at least on a microcontroller), draws the triangles more accurately, particularly when drawing sharp edges.

Attached is the code for anyone interested.

## Attachment(s):

Last Edited: Wed. Oct 2, 2013 - 04:28 AM

Back in the days when I computed with a 64K Z80 machine, I found all sorts of uses for Bresenham's algorithm. Even in DOS, I once wanted a fading background, so I used Bresenham to pick what color to use based on how far from the edge.

The largest known prime number: 282589933-1

Good thing Intel and Atmel keep making faster processors so non-programmers like myself can still get projects done.

I recall writing a GLCD driver and for a "Filled Circle" my first approach, using a modified Bresenham's algorithm approach for drawing circles, was to just draw a bunch of circles with a radius of 0 to N.

Should have filled the entire circle nicely, if not very efficiently.

Of course it didn't work very well. The rounding errors lead to some pixels being skipped. It gave a nice Moire Pattern to the circle, but that wasn't what was being sought.

Just as well it didn't work too well, the second version was much more efficient.

So, Gabriel, What time is it? (Nice Job!)

JC

Yep... In case you are wondering why I need to draw triangles:

ganzziani wrote:
I was looking for an algorithm to draw filled triangles, I found one from Adafruit's Graphics library, but I kept on looking for something more efficient. I found some code from http://www.sunshine2k.de/, it is based on the Bresenham's line algorithm and I optimized a bit further.

I have found that the Bresenham's algorithm, besides being more efficient (at least on a microcontroller), draws the triangles more accurately, particularly when drawing sharp edges.

Attached is the code for anyone interested.

When I was experimenting with filled triangles (in DOS so there was "plenty" of data memory compared to AVRs), I did not calculate the scanlines in real time like the code you posted. I used a table with min and max X coordinates for a given scan line to draw horizontal lines, and min and max Y coordinate to know what scan lines from the table need to be drawn.

Then I just used regular Breshenham's line drawing algorithm to draw a line between two points, but instead of actually plotting pixels, it just updated the table with min/max X values for the given Y coordinate (scanline).

You could draw triangles by drawing three lines between endpoints into the scanline buffer and then process the buffer for drawing horizontal lines on screen between min/max X coordinates on each scanline.

DocJC wrote:

Of course it didn't work very well. The rounding errors lead to some pixels being skipped. It gave a nice Moire Pattern to the circle, but that wasn't what was being sought.

Just as well it didn't work too well, the second version was much more efficient.

Let me guess, the algorithm gives you coordinates of one octant, and then instead of plotting 8 pixels into mirrored coordinates you just draw horizontal lines between points?