Triangle fill algorithm

Hi guys

I need a fast algorithm that fills a 2D triangle. I’m not using Graphics or Graphics2D for this.
This is what I want:

class ColorBuffer {
   private int[][] data;
   public void plot(int x,int y,int color) {
   // some other methods
class Renderer {
   public ColorBuffer buffer;
   // [...]
   public void fillTriangle(Point v1,Point v2,Point v3) {
      // that's what I need

Please include a source code if you can. :slight_smile:

And I want a pony.

If you’re looking for speed, the first thing you should fix is your ColorBuffer. 2D arrays are slower than a 1D array. Plot the pixel at (x,y) by indexing into a 1D array of length (width*height) by using this formula (x + y * width)

Decompose the triangle into two segments, “top half” and “bottom half” with appropriate
special cases.

Use the Bresenham algorithm to describe the left and right edges, draw one row at a time
from left to right.

This can be very fast (requires no multiplies) if implemented carefully, but be warned
that for extremely acute triangles, it can produce counterintuitive “triangles” that are
not one blob.

For extra credit, get the edge conditions correct so drawing a mesh of triangles
draws each pixel exactly once. Otherwise, attempts to draw a mesh will leave
stray pixels undrawn.

That’s exactly what I need. Thanks!