我需要一个像素完美的三角形填充算法来避免混叠伪像

Question

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

我们正在寻找一种填充算法,该算法可以保证如果两个三角形共享一条边(具体来说,如果三角形的任意两个顶点相同),那么无论绘制顺序和锯齿是什么,线上都不会有空白的未拉伸像素两者之间.(如果某些像素被绘制两次,那就没问题.)在任意缩放下,结果应该看起来不错.某些三角形可能是非常薄的细长条,宽度低至1像素.

理想情况下,它也应该是一个合理有效的填充算法!

在三角形渲染中不会使用消除锯齿,因为最终图像需要为1位深度.

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

Answer 1

鉴于这些要求,看起来有一个简单的解决方案.

首先,栅格化三角形边.您可以使用Bresenham的线条绘制算法(如下面的代码中所示)或任何有效的方法.然后填写介于两者之间的区域.这将适用于任意薄的三角形.

为了确保没有间隙而不管绘制三角形的顺序如何,并且无论提供给三角形绘制代码的顶点的顺序如何,您希望在共享边的三角形中以相同的方式光栅化共享边.相同的方式每次都意味着相同的像素.

为了保证每次从相同的顶点坐标对中获得相同的像素时,您基本上想要建立一个固定的顺序,即建立一个规则,该规则始终从两个给定的顶点中选择相同的一个顶点而不管顺序如何.给他们的.

强制执行此顺序的一种简单方法是将线(三角形边)视为二维向量,如果它指向负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的OR的方向,如果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









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