I need a pixel-perfect triangle fill algorithm to avoid aliasing artifacts

Question

I'm assisting someone with user interface code to visualise a mathematical image analysis. During this process we'll be segmenting part of a 2D shape into triangles, and filling some of these triangles in on the UI.

We're looking for a fill algorithm which guarantees that if two triangles share an edge (specifically, if any two vertices of the triangles are identical), then regardless of drawing order and aliasing there will be not be blank, undrawn pixels on the line between the two. (It's alright if some pixels are drawn twice.) The result should look OK under arbitrary scaling. Some triangles may be extremely thin slivers in places, down to 1 pixel wide.

Ideally it should also be a reasonably efficient fill algorithm!

Anti-aliasing will not be used in triangle rendering, as the final image needs to be 1-bit depth.

The context is an image-recognition application, so all vertex coordinates will be accurate to one pixel.

Hammered

Can't you simply draw the triangles with a default filling procedure (of your library) and then do a single post-processing operation than fills the missing pixels? – Bootlick

@elmes: That would be an acceptable approach, but that still leaves 'good algorithm for identifying the missing pixels' as the question. (I am hoping that somebody who knows more about graphics than I do knows a triangle-rasterization algorithm that prevents it from being a problem in the first place.) – Hammered

Well, do you know the color of the background? Even if you don't, you can try a simple erode / dilate post-processing. – Bootlick

We'll either have white pixels on a black background, or vice-versa, on a per-image basis (we can invert trivially, of course). However, we don't want to erode / dilate (or similar), because we don't want to alter the exterior edge where the triangles are not adjacent. – Hammered

Well, I don't know of any 'smart' algorithm .. maybe others will help you more ;-) I'd try a conditional dilation though. – Bootlick

Why not just use OpenGL to do the drawing? Seems like it would be faster, and there's a "quality hint" you can use as well. Though, I don't know what requirements you have, so ignore this if project requirements dictate otherwise. – Cockrell

@AaronMiller: A good option, but made impossible by other project constraints. – Hammered

This question has an accepted answer already but for the benefit of others looking here: devmaster.net/posts/6145/advanced-rasterization looks like one of the best algorithms on the internet. I implemented it and it works great. Haven't done any benchmarks yet but it claims to be fast too, and work with no overdraw. Fun fact: it's a 10 years old forum thread and people are still using it and commenting :) – Fredi

The link referenced by @Fredi is now broken, but the article can still be found here: web.archive.org/web/20140226060757/http://devmaster.net/posts/… – Nolie

Answer 1

Given the requirements, it looks like there's a simple solution.

First, rasterize the triangle edges. You can use the Bresenham's line drawing algorithm for that (as in the code below) or anything that works. Then fill in the area in-between. This will work with arbitrarily thin triangles.

To make sure there are no gaps irrespective of the order in which triangles are drawn and irrespective of the order of the vertices supplied to the triangle-drawing code you want to rasterize shared edges in the same way in the triangles sharing an edge. Same way means the same pixels every time.

To guarantee that every time you get the same pixels from the same pairs of vertex coordinates you basically want to establish a fixed order, that is, establish a rule that would always choose the same one vertex out of the two given irrespective of the order in which they are given.

One simple way to enforce this order is to treat your line (triangle edge) as a 2-d vector and flip its direction if it points in the direction of negative y's or is parallel to the x axis and points in the direction of negative x's. Time for some ASCII art! :)

      3   2   1
       \  |  /
        \ | /
         \|/
4 --------+--------- 0
         /|\
        / | \
       /  |  \
      5   6   7

        4 -> 0
        5 -> 1
        6 -> 2
        7 -> 3

See, here line segment, say, 1 and line segment 5 are really the same kind of thing, the only difference is the direction from the endpoint at the origin to the other endpoint. So we reduce these cases in half by turning segments 4 through 7 into segments 0 through 3 and get rid of the direction ambiguity. IOW, we choose to go in the direction of increasing y's OR, if y's are the same on the edge, in the direction of increasing x's.

Here's how you could do it in code:

#include <stddef.h>
#include <limits.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <time.h>

#define SCREEN_HEIGHT 22
#define SCREEN_WIDTH  78

// Simulated frame buffer
char Screen[SCREEN_HEIGHT][SCREEN_WIDTH];

void SetPixel(long x, long y, char color)
{
  if ((x < 0) || (x >= SCREEN_WIDTH) ||
      (y < 0) || (y >= SCREEN_HEIGHT))
  {
    return;
  }

  if (Screen[y][x] == ' ')
    Screen[y][x] = color;
  else
    Screen[y][x] = '*';
}

void Visualize(void)
{
  long x, y;

  for (y = 0; y < SCREEN_HEIGHT; y++)
  {
    for (x = 0; x < SCREEN_WIDTH; x++)
    {
      printf("%c", Screen[y][x]);
    }

    printf("\n");
  }
}

typedef struct
{
  long x, y;
  unsigned char color;
} Point2D;


// min X and max X for every horizontal line within the triangle
long ContourX[SCREEN_HEIGHT][2];

#define ABS(x) ((x >= 0) ? x : -x)

// Scans a side of a triangle setting min X and max X in ContourX[][]
// (using the Bresenham's line drawing algorithm).
void ScanLine(long x1, long y1, long x2, long y2)
{
  long sx, sy, dx1, dy1, dx2, dy2, x, y, m, n, k, cnt;

  sx = x2 - x1;
  sy = y2 - y1;

/*
      3   2   1
       \  |  /
        \ | /
         \|/
4 --------+--------- 0
         /|\
        / | \
       /  |  \
      5   6   7

        4 -> 0
        5 -> 1
        6 -> 2
        7 -> 3
*/
  if (sy < 0 || sy == 0 && sx < 0)
  {
    k = x1; x1 = x2; x2 = k;
    k = y1; y1 = y2; y2 = k;
    sx = -sx;
    sy = -sy;
  }

  if (sx > 0) dx1 = 1;
  else if (sx < 0) dx1 = -1;
  else dx1 = 0;

  if (sy > 0) dy1 = 1;
  else if (sy < 0) dy1 = -1;
  else dy1 = 0;

  m = ABS(sx);
  n = ABS(sy);
  dx2 = dx1;
  dy2 = 0;

  if (m < n)
  {
    m = ABS(sy);
    n = ABS(sx);
    dx2 = 0;
    dy2 = dy1;
  }

  x = x1; y = y1;
  cnt = m + 1;
  k = n / 2;

  while (cnt--)
  {
    if ((y >= 0) && (y < SCREEN_HEIGHT))
    {
      if (x < ContourX[y][0]) ContourX[y][0] = x;
      if (x > ContourX[y][1]) ContourX[y][1] = x;
    }

    k += n;
    if (k < m)
    {
      x += dx2;
      y += dy2;
    }
    else
    {
      k -= m;
      x += dx1;
      y += dy1;
    }
  }
}

void DrawTriangle(Point2D p0, Point2D p1, Point2D p2)
{
  long y;

  for (y = 0; y < SCREEN_HEIGHT; y++)
  {
    ContourX[y][0] = LONG_MAX; // min X
    ContourX[y][1] = LONG_MIN; // max X
  }

  ScanLine(p0.x, p0.y, p1.x, p1.y);
  ScanLine(p1.x, p1.y, p2.x, p2.y);
  ScanLine(p2.x, p2.y, p0.x, p0.y);

  for (y = 0; y < SCREEN_HEIGHT; y++)
  {
    if (ContourX[y][1] >= ContourX[y][0])
    {
      long x = ContourX[y][0];
      long len = 1 + ContourX[y][1] - ContourX[y][0];

      // Can draw a horizontal line instead of individual pixels here
      while (len--)
      {
        SetPixel(x++, y, p0.color);
      }
    }
  }
}

int main(void)
{
  Point2D p0, p1, p2, p3;

  // clear the screen
  memset(Screen, ' ', sizeof(Screen));

  // generate random triangle coordinates

  srand((unsigned)time(NULL));

  // p0 - p1 is going to be the shared edge,
  // make sure the triangles don't intersect
  for (;;)
  {
    p0.x = rand() % SCREEN_WIDTH;
    p0.y = rand() % SCREEN_HEIGHT;

    p1.x = rand() % SCREEN_WIDTH;
    p1.y = rand() % SCREEN_HEIGHT;

    p2.x = rand() % SCREEN_WIDTH;
    p2.y = rand() % SCREEN_HEIGHT;

    p3.x = rand() % SCREEN_WIDTH;
    p3.y = rand() % SCREEN_HEIGHT;

    {
      long vsx = p0.x - p1.x;
      long vsy = p0.y - p1.y;
      long v1x = p0.x - p2.x;
      long v1y = p0.y - p2.y;
      long v2x = p0.x - p3.x;
      long v2y = p0.y - p3.y;
      long z1 = vsx * v1y - v1x * vsy;
      long z2 = vsx * v2y - v2x * vsy;
      // break if p2 and p3 are on the opposite sides of p0-p1
      if (z1 * z2 < 0) break;
    }
  }

  printf("%ld:%ld %ld:%ld %ld:%ld %ld:%ld\n\n",
         p0.x, p0.y,
         p1.x, p1.y,
         p2.x, p2.y,
         p3.x, p3.y);

  // draw the triangles

  p0.color = '-';
  DrawTriangle(p0, p3, p1);
  p1.color = '+';
  DrawTriangle(p1, p2, p0);

  Visualize();

  return 0;
}

Sample output:

30:10 5:16 16:6 59:17







                +++
               ++++++++
              ++++++++++++
             +++++++++++++++++
            +++++++++++++++****---
          +++++++++++++****-----------
         ++++++++++****-------------------
        ++++++*****----------------------------
       +++****-------------------------------------
      ****---------------------------------------------
     *-----------------------------------------------------
                                                           -

Legend:

• "+" - pixels of triangle 1
• "-" - pixels of triangle 2
• "*" - pixels of the edge shared between triangles 1 and 2

Beware that even though there will be no unfilled gaps (pixels), the triangle whose pixels (on the shared edge) get overwritten (because of the other triangle drawn on top of it) may show up as disjoint or awkwardly shaped if it's too thin. Example:

2:20 12:8 59:15 4:17









            *++++++
           *+++++++++++++
          *+++++++++++++++++++++
         -*++++++++++++++++++++++++++++
        -*++++++++++++++++++++++++++++++++++++
        *+++++++++++++++++++++++++++++++++++++++++++
       *+++++++++++++++++++++++++++++++++++++++++++++++++++
      *+++++++++++++++++++++++++++++++++++++++++++++++++++++
     *+++++++++++++++++++++++++++++++++++++++++++
    -*+++++++++++++++++++++++++++++++
   -*+++++++++++++++++++++
   *++++++++++
  *

Adamec

+1 for extensive ASCII and a thorough explanation of even the simplest concepts. We'll probably do something just like this. (Because many of our triangles are thin slices, disjoint or awkward shapes are inevitable no matter what approach we use; that's fine as long as our fill picks something appropriate and doesn't leave gaps.) – Hammered

Answer 2

Your concern about adjacent triangles is a valid one. If two triangles share an edge, you want to be sure that every pixel along that edge "belongs" exclusively to one triangle or the other. If one of those pixels doesn't belong to either triangle, you have a gap. If it belongs to both triangles, you have overdraw (which is inefficient) and the color might depend on the order the triangles are rendered (which may not be deterministic).

Since you're not using anti-aliasing, this actually isn't too hard. It's not so much a smart algorithm you need as a careful implementation.

The typical way to rasterize a triangle is to compute horizontal segments that are part of the triangle from the top to the bottom. You do this by keeping track of the current left and right edges, and essentially doing an x-intercept calculation for each edge at each scanline. It can also be done with two Bresenhem-style line-drawing algorithms running together. Effectively, the rasterization amounts to several calls to a function that draws a horizontal line segment at some scanline y from some left coordinate x0 to some right coordinate x1.

void DrawHLine(int y, int x0, int x1);

Typically what's done is to make sure the rasterizer rounds off the x-intercepts in a consistent manner, so that the x-coordinates are computed consistently regardless of whether they are part of the right edge of one triangle or the left edge of the adjacent triangle. This guarantees that every pixel along the shared edge will belong to both triangles.

We resolve the double-ownership by tweaking DrawHLine so that it fills the pixels from x0 inclusive up to x1 exclusive. So all those doubly-owned pixels on the shared edge are defined to belong to the triangle on the right of the shared edge.

Embolden

Answer 3

I realize that link-only answers are discouraged, but I have written about this exact problem on my blog. Fabian Giesen also discusses it as part of his excellent series, Optimizing Software Occlusion Culling.

The gist of it is that you should select a fill rule, which determines how to break the tie for pixels shared between two faces. One such fill rule is specified and well-documented for Microsoft's Direct3D API. It can be implemented using an algorithm similar to Bresenham's line algorithm, but a bit of extra care must be given to the rounding and edge cases.

Even the accepted answer here does not handle negative-x slopes in a consistent way, although since your output is just 1-bit and you don't need to interpolate any attributes, it will probably not matter much.

Predecease

Answer 4

It's not the most efficient, but you could loop over a square containing the triangle and test if each pixel is within the triangle.

Pseudocode:

for(x : minX -> maxX)
    for(y : minY -> maxY)
        if(triangle.contains(x,y))
            drawPixel(x,y);

Where minX is the minimum X coordinate between the three vertices and similarly for maxX, minY and maxY.

For a faster algorithm you could do some quick and dirty filling (e.g. slashmais flood filling) first and then do this for the pixels around the edges.

The point-in-triangle test is described here.

Argil

Answer 5

This is a well studied problem. Learn about the bresenham line drawing algorithm.

http://en.wikipedia.org/wiki/Bresenham's_line_algorithm

Fielder

Answer 6

My answer satisfies the the hypothesis. What Adrian McCarthy said in his answer is true. My algorithm is based on a similar idea and it is valid. Even in my opinion it is not fair not to take into account the overwriting of a pixel. However, I do not represent horizontal lines of N-1 Pixels, otherwise the triangle, if it is a "splinter" it would not be represented.

For example: suppose we have two adjacent triangles:

ABC [A (27.15) -B (32.15) -C (37.15)];
DEF [A (29.15) -B (32.15) -C (35.15)];

the representation will overlap, but the result should be a horizontal segment of the type:

++-------------------------++

So it is not enough to exclude the last pixel to avoid overwriting.

To represent a filled triangle, so that you can use the function created to represent filled polygons (example: a quadrilateral), since they can always be divided into triangles, it is necessary to be able to exclude the representation of a side, otherwise, it would happen that one side of a triangle is overwritten by the side of the adjacent triangle (problems in displaying transparent polygons). This, which I propose to you, is the C implementation of my algorithm for the representation of any type of triangles. I advise you to try it, because it is fast, although quite complex, and efficient. it is my variant of the Bresenham algorithm. The implementation of the routine representing a horizontal segment, I remaind it to you (i've replaced the call to Put(Shadow)HorizLine (), for the representation of the horizontal segment, with the Line () instruction, because my implementation of DrawHLine() can't be inserted in this post; however here I use Line() instruction only to draw horizontal segment).

This function initially provided for the use of buffers in RAM in my own format, called OBP, which differs from the RASTER format only for 2 reasons: the scan lines are aligned with the 16 Bytes. there is a 16 Byte header, before the data (8-Bit for each Pixel); this header contains the size of the image in the first 2 Words (in the assembly implementation, you can choose, so whether to make the most of the CPU registers, instead of the variables in RAM, since a 32 Bit register can contain both dimensions and, on medium-sized scales of an image, the geometric position of a point can also be contained in a 32 Bit register). Here the only thing that needs to be done is to rewrite the call to the Line() function, due to the fact that to specify the color of one side of the triangle, which may be different from the others, transparent or absent, it is necessary to modify an attribute of an object, instead of passing the color directly as a parameter to the line() function, although once it was possible to call the SetColor() function, which is only indicative here.

Her is the header (triangle.h):

#define R_OBP_Al 16 /* 16 Byte alignment; it must always be 2^N */
#define DimOBP_H 16 /* 16 Byte of OBP HEADER; it must always be >=4 */

#define True 1 /* Boolean value for true condition */
#define False 0 /* Boolean value for false condition */

typedef char TShadowTable[256]; /* Array for shadows */
typedef TShadowTable *T_Shadow_Table_Ptr; /* Pointer to an array for shadows */

typedef struct {short int X;
                short int Y;} T_Coord_XY;
typedef struct {unsigned short int X;
                unsigned short int Y;} T_Pos_Coord_XY;
typedef struct {unsigned short int DimX;
                unsigned short int DimY;} T_Dim_XY;
typedef struct {T_Pos_Coord_XY XY; /* Coordinates of the clipping-region */
                T_Dim_XY Dim_XY; /* Dimensions of the clipping-region */ } T_Clipp_Rect;

typedef T_Clipp_Rect *T_Clipp_Rect_Ptr; /* Pointer to clipping-region's type */

typedef struct {T_Coord_XY XY; /* Coordinates of the rectangle */
                T_Dim_XY Dim_XY; /* Dimensions of the rectangle */ } T_Rect;

typedef T_Rect *T_Rect_Ptr; /* Pointer to a rectangle */

typedef char Boolean; /* Boolean type */

void Triangle_Wind(short int X1,
                   short int Y1,
                   short int X2,
                   short int Y2,
                   short int X3,
                   short int Y3,
                   short int FillColor,
                   short int BrdColAB,
                   short int BrdColBC,
                   short int BrdColCA
                /* , T_Shadow_Table_Ptr ShadowTable,
                   void *OBPVBuff
                   T_Clipp_Rect_Ptr Clipp */);

Here is the function and the example (triangle.c):

#include <graphics.h>
#include <conio.h>
#include <string.h>
#include <stdio.h>
#include "triangle.h"

static int *DefColors[16]=
             {0FF000000H, /* Black */
              0FF7F0000H, /* Blue */
              0FF007F00H, /* Green */
              0FF7F7F00H, /* Cyan */
              0FF00007FH, /* Red */
              0FF7F007FH, /* Magenta */
              0FF007F7FH, /* Brown */
              0FF7F7F7FH, /* LightGray */
              0FF3F3F3FH, /* DarkGray */
              0FFFF0000H, /* LightBlue */
              0FF00FF00H, /* LightGreen */
              0FFFFFF00H, /* LightCyan */
              0FF0000FFH, /* LightRed */
              0FFFF00FFH, /* LightMagenta */
              0FF00FFFFH, /* Yellow */
              0FFFFFFFFH  /* White */ };

int main(void)
{
 /* int gd = DETECT;
    int gm;

    initgraph(&gd, &gm, "C:\\TC\\BGI"); */

 Triangle_Wind(80,80,320,200,160,300,
               4,1,2,7);

 getch();
 /* closegraph(); */
 return 0;
}
/* Here it is the body of the triangle routine: */

void Triangle_Wind(short int X1,
                   short int Y1,
                   short int X2,
                   short int Y2,
                   short int X3,
                   short int Y3,
                   short int FillColor,
                   short int BrdColAB,
                   short int BrdColBC,
                   short int BrdColCA
                /* , T_Shadow_Table_Ptr ShadowTable,
                   void *OBPVBuff
                   T_Clipp_Rect_Ptr Clipp */)

{short int A=0;
 short int B=1;
 short int C=2; /* Identificat. vertici triangoli per ordinam. colori */

 short int C1=BrdColAB;
 short int C2=BrdColBC;
 short int C3=BrdColCA; /* Var. temp. per i colori */

 short int XT; /* X1-XT è il segmento orizzontale da disegnare */

 short int OY2; /* Valore iniziale coord. Y 2° vertice del triangolo */

 short int B1L;
 short int B1H; /* Coord. X 1° e ultimo punto 1° bordo (segm. orizz.) */
 short int B2L;
 short int B2H; /* Coord. X 1° e ultimo punto  2° bordo (segm. orizz.) */

 short int D0; /* Dimensione 1° bordo (segm. orizz.) */
 short int D1; /* Dimensione parte centrale segm. orizz. */
 short int D2; /* Dimensione 2° bordo (segm. orizz.) */

 short int Tmp; /* Variabile temporanea x scambio di 2 variabili */

 short int Col1; /* Colore 1° bordo segm. orizz. */
 short int Col2; /* Colore 2° bordo segm. orizz. */

 short int CntX1; /* Contat. per coord. X 1° punto segm. orizz. (Bresenham) */
 short int IncX1; /* Increm. contat. per coord. X 1° punto segm. or. (Bresenham) */
 short int CntY1; /* Contat. per coord. Y 1° punto segm. orizz. (Bresenham) */
 short int Lim1; /* Limite per contat. coord. X e Y 1° punto segm. or. (Bresenham) */
 short int DirX1; /* Increm. coord. X 1° punto segm. orizz. */
 short int IncY1; /* Increm. contat. per coord. Y 1° punto segm. or. (Bresenham) */
 short int FX1; /* Valore iniziale coord. X1 segm. orizz. X1-XT */

 short int CntXT; /* Contat. per coord. X 2° punto segm. orizz. (Bresenham) */
 short int IncXT; /* Increm. contat. per coord. X 2° punto segm. or. (Bresenham) */
 short int CntYT; /* Contat. per coord. Y 2° punto segm. orizz. (Bresenham) */
 short int LimT; /* Limite per contat. coord. X e Y 2° punto segm. or. (Bresenham) */
 short int DirXT; /* Increm. coord. X 2° punto segm. orizz. */
 short int IncYT; /* Increm. contat. per coord. Y 2° punto segm. or. (Bresenham) */
 short int FXT; /* Valore iniziale coord. XT segm. orizz. X1-XT */

 T_Rect Segm; /* Record per la rappresentazione di un segm. orizz. */

 Boolean F1; /* 1° cond. iniz. (eccezione), rappresentaz. triang. */
 Boolean F24; /* 2° cond. iniz. (eccezione), rappresentaz. triang. */
 Boolean Overflow=False; /* FALSE: Calcola segm. orizz.; TRUE: Ha finito */
 Boolean Internal; /* Variabile temp.; salva il val. iniz. di Overflow */
 Boolean Finished=True; /* FALSE: 2° semi-triang.; TRUE: 1° semi-triang.} */

 /* Ordina i vertici in base alla coordinata Y */

 if (Y1>Y2)
  {Tmp=X1;
   X1=X2;
   X2=Tmp;
   Tmp=Y1;
   Y1=Y2;
   Y2=Tmp;
   Tmp=A;
   A=B;
   B=Tmp;}

 if (Y2>Y3)
  {Tmp=X2;
   X2=X3;
   X3=Tmp;
   Tmp=Y2;
   Y2=Y3;
   Y3=Tmp;
   Tmp=B;
   B=C;
   C=Tmp;}

 if (Y1>Y2)
  {Tmp=X1;
   X1=X2;
   X2=Tmp;
   Tmp=Y1;
   Y1=Y2;
   Y2=Tmp;
   Tmp=A;
   A=B;
   B=Tmp;}

 /* Calcola il colore effettivo dei lati A-B, B-C e C-A del triangolo */

 switch (27*A+9*B+C)
  {case 19:{BrdColAB=C3;
            BrdColCA=C1;
            break;}
   case 29:{BrdColBC=C3;
            BrdColCA=C2;
            break;}
   case 45:{BrdColAB=C2;
            BrdColBC=C3;
            BrdColCA=C1;
            break;}
   case 55:{BrdColAB=C3;
            BrdColBC=C1;
            BrdColCA=C2;
            break;}
   case 63:{BrdColAB=C2;
            BrdColBC=C1;
            break;
           }}

 /* Calc. incr. e limiti, inizial. i cont. lato A-C (Bresenham) */

 DirXT=-1;
 IncXT=X1-X3;
 if (X1<X3)
  {DirXT=1;
   IncXT=-IncXT;}
 IncXT+=1;
 CntXT=IncXT>>1;

 IncYT=Y3-Y1+1;
 CntYT=IncYT>>1;

 LimT=IncXT;
 if (IncXT<IncYT)
  LimT=IncYT;

 /* Imposta i valori iniziali delle var. locali */

 XT=X1;
 OY2=Y2;

 F1=(Y1>=Y2) || (Y2!=Y3);
 F24=((Y1!=Y2) || (Y2>=Y3)) &&
     ((Y1>=Y2) || (Y2>=Y3));

 /* Disegna il primo vertice del triangolo */

 if ((X1=X2) && (X2=X3) &&
     (Y1=Y2) && (Y2=Y3))
  {/* Segm->XY->X=X1;
      Segm->XY->Y=Y1;
      Segm->Dim_XY->DimX=1; */

   Col1=BrdColAB;
   if (Col1<0)
    Col1=BrdColCA;
   if (Col1<0)
    Col1=FillColor;
   if (Col1>=0)
    {setcolor(DefColors[Col1]);
     line(X1,Y1,X1,Y1);}

   /* if (Col1<256)
       PutHorizLine(&Segm,OBPVBuff,Col1,Clipp)
      else
       PutShadowHorizLine(&Segm,OBPVBuff,ShadowTable,Clipp); */}

 /* Disegna il triangolo */

 do

 {/* Calc. incr. e limiti, inizial. i cont. lato A-B (Bresenham) */

  DirX1=-1;
  IncX1=X1-X2;
  if (X1<X2)
   {DirX1=1;
    IncX1=-IncX1;}
  IncX1+=1;
  CntX1=IncX1>>1;

  IncY1=Y2-Y1+1;
  CntY1=IncY1>>1;

  Lim1=IncX1;
  if (IncX1<IncY1)
   Lim1=IncY1;

  FX1=X1;
  FXT=XT;

  /* Rappresenta un semi-triangolo */

  while ((X1!=X2) || (Y1!=Y2))
   {

    /* Calcola i 4 estremi del segmento orizzontale da disegnare */

    do
    {Internal=Overflow;

     if (Overflow)
      {CntY1-=Lim1;
       CntYT-=LimT;

       Y1+=1;}

     Overflow=True;

     Tmp=CntY1+IncY1;

     if (Tmp<Lim1)
      {CntY1=Tmp;
       CntX1+=IncX1;

       if (CntX1>=Lim1)
        {CntX1-=Lim1;
         X1+=DirX1;}

       Overflow=False;}

     Tmp=CntYT+IncYT;

     if (Tmp<LimT)
      {CntYT=Tmp;
       CntXT+=IncXT;

       if (CntXT>=LimT)
        {CntXT-=LimT;
         XT+=DirXT;}

       Overflow=False;}

     if (Internal)
      {FX1=X1;
       FXT=XT;}

    } while (!Overflow);

    /* Ordina (ord. ascend.) i 4 estremi del segmento orizzontale */

    B1L=FX1;
    B1H=X1;

    if (B1L>B1H)
     {Tmp=B1L;
      B1L=B1H;
      B1H=Tmp;}

    B2L=FXT;
    B2H=XT;

    if (B2L>B2H)
     {Tmp=B2L;
      B2L=B2H;
      B2H=Tmp;}

    Col1=BrdColAB;
    Col2=BrdColCA;

    if ((B2L<B1L) || (B2H<B1H))
     {Tmp=B1L;
      B1L=B2L;
      B2L=Tmp;
      Tmp=B1H;
      B1H=B2H;
      B2H=Tmp;
      Tmp=Col1;
      Col1=Col2;
      Col2=Tmp;}

    /* Calcola la posizione e la dimensione dei 2 bordi del segm. orizz. */

      D1=B1H-B1L+1;
      D0=B2L-B1H-1;
      D2=B2H-B2L+1;

    /* Ove possibile, unisce bordi con parte centrale del segm. orizz. */

      if (D0>0)
       {if (FillColor==Col2) /* Parte0 unita a parte2, parte0 esistente */
         {D0+=D2;
          D2=0;}

        if (Col1==FillColor) /* Parte0 unita a parte1, parte0 esistente */
         {B1H=B1L-1;
          D0+=D1;
          D1=0;}}
      else
       {D0=0;

        if (Col1==Col2) /* Parte1 unita a parte2, parte0 inesistente */
         {D1=B2H-B1L+1;
          D2=0;}}

    /* Rappresenta il primo bordo del segm. orizz. */

    /* Segm->XY->Y=Y1;

       Segm->XY->X=B1L;
       Segm->Dim_XY->DimX=D1; */

    if ((Col1>=0) && (D1>0))
    {setcolor(DefColors[Col1]);
     line(B1L,Y1,B1L+D1-1,Y1);}

    /* if (Col1<256)
        PutHorizLine(&Segm,OBPVBuff,Col1,Clipp)
       else
        PutShadowHorizLine(&Segm,OBPVBuff,ShadowTable,Clipp); */

    /* Rappresenta la parte centrale del segm. orizz. */

    if (((Y1!=OY2) ||
         (!Finished || F1) && (Finished || F24)) && (D0>0))
     {

      /* Segm->XY->X=B1H+1;
         Segm->Dim_XY->DimX=D0; */

      if ((FillColor>=0) && (D0!=0))
      {setcolor(DefColors[FillColor]);
       line(B1H+1,Y1,B1H+D0,Y1);}

      /* if (FillColor<256)
          PutHorizLine(&Segm,OBPVBuff,FillColor,Clipp)
         else
          PutShadowHorizLine(&Segm,OBPVBuff,ShadowTable,Clipp); */
     }

    /* Rappresenta il secondo bordo del segm. orizz. */

    /* Segm->XY->X=B2L;
       Segm->Dim_XY->DimX=D2; */

    if ((Col2>=0) && (D2>0))
    {setcolor(DefColors[Col2]);
     line(B2L,Y1,B2L+D2-1,Y1);}

    /* if (Col2<256)
        PutHorizLine(&Segm,OBPVBuff,Col2,Clipp)
       else
        PutShadowHorizLine(&Segm,OBPVBuff,ShadowTable,Clipp); */

   }

  X2=X3;
  Y2=Y3;

  BrdColAB=BrdColBC;

  Finished=!Finished;

 } while (!Finished);

}

Tacy

Answer 7

What you are looking for is a floodfill algorithm.

Here's one.

Another link.

You can google 'floodfill-algorithm' for more.

[edit]

Maybe this site[Shader-Based Wireframe Drawing] can offer some more ideas.

Earhart

Simple seed-based flood fills are out, because some triangles will have angles acute enough to run into the 'trapped pixels near the point' problem. (Also, finding an interior start pixel reliably can be an issue in itself in angled 'slim' triangles.) However, your link to the quickfill discussion is interesting; we'll take a proper look. – Hammered

@Tynam: It could be possible to use the pixel-scanning technique(s) to examine interesting areas for unfilled pixels, e.g. very acute angles or pixel-wide triangles: if the unfilled pixel lies within at least one boundary, then it should be filled. That could mean doing a line-scan of the entire triangle for unfilled pixels (scan lines starting from an arbitrary side and parallel to it with end-points inclusive of the other two sides should do the trick). – Earhart