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.

Solution 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









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

Solution 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.

Solution 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.