c - 我需要一个像素完美的三角形填充算法来避免锯齿现象

Question

我正在协助某人使用用户界面代码来可视化数学图像分析。 在此过程中，我们会将 2D 形状的一部分分割成三角形，并在 UI 上填充其中的一些三角形。

我们正在寻找一种填充算法，它保证如果两个三角形共享一条边(具体来说，如果三角形的任何两个顶点相同)，那么无论绘制顺序和别名如何，都不会出现空白、未绘制的像素在两者之间的线上。 (如果某些像素被绘制两次也没关系。)结果在任意缩放下应该看起来不错。一些三角形在某些地方可能是极细的条子，宽度低至 1 像素。

理想情况下，它也应该是一种相当高效的填充算法!

在三角形渲染中不会使用抗锯齿，因为最终图像需要是 1 位深度。

上下文是一个图像识别应用程序，因此所有顶点坐标都将精确到一个像素。

Answer 1

鉴于需求，看起来有一个简单的解决方案。

首先，栅格化三角形的边。您可以为此使用 Bresenham 的画线算法(如以下代码所示)或任何可行的算法。然后填充中间的区域。这将适用于任意细的三角形。

为了确保没有间隙，无论三角形的绘制顺序如何，也无论提供给三角形绘制代码的顶点顺序如何，您都希望以共享边的三角形中相同的方式光栅化共享边. 相同方式表示每次都使用相同的像素。

为了保证每次从相同的顶点坐标对得到相同的像素，你基本上想要建立一个固定的顺序，也就是说，建立一个规则总是从给定的两个顶点中选择相同的一个，而不管它们给出的顺序。

执行此顺序的一种简单方法是将您的线(三角形边)视为二维 vector ，如果它指向负 y 方向或平行于 x 轴并指向方向，则翻转其方向的负 x。是时候来一些 ASCII 艺术了! :)

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

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

看，这里的线段，比如说1和5线段其实是同一种东西，区别只是从原点的端点到另一个端点的方向而已。因此，我们通过将段 4 到 7 转换为段 0 到 3 来将这些情况减少一半，并消除方向歧义。 IOW，我们选择朝增加 y 的方向前进，或者，如果边上的 y 相同，则朝增加 x 的方向前进。

以下是您可以在代码中实现的方法:

#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;
}

示例输出:

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







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

图例:

• "+"- 三角形1的像素
• "-"- 三角形2的像素
• "*"- 三角形 1 和 2 共享边的像素

请注意，即使没有未填充的间隙(像素)，其像素(在共享边上)被覆盖的三角形(因为在它上面绘制的另一个三角形)可能会显示为不相交或形状笨拙，如果它太薄了。示例:

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









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