我需要一个像素完美的三角形填充算法来避免锯齿伪影 [英] I need a pixel-perfect triangle fill algorithm to avoid aliasing artifacts
问题描述
我正在使用用户界面代码协助某人将数学图像分析可视化.在此过程中，我们会将 2D 形状的一部分分割成三角形，并在 UI 上填充其中的一些三角形.
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.
我们正在寻找一种填充算法，它可以保证如果两个三角形共享一条边(具体来说，如果三角形的任意两个顶点相同)，那么无论绘制顺序和混叠如何，都不会出现空白的未绘制像素在两者之间的线上.(如果某些像素绘制两次也没关系.)在任意缩放下，结果应该看起来不错.某些三角形的某些地方可能非常细，宽度低至 1 像素.
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!
在三角形渲染中不会使用抗锯齿，因为最终图像需要为 1 位深度.
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.
推荐答案
鉴于需求，看起来有一个简单的解决方案.
Given the requirements, it looks like there's a simple solution.
首先，光栅化三角形边缘.您可以使用 Bresenham 的画线算法(如下面的代码所示)或任何有效的方法.然后填充中间的区域.这适用于任意细的三角形.
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.
无论三角形的绘制顺序如何，也不管提供给三角形绘制代码的顶点的顺序如何，为了确保没有间隙，您希望在共享边的三角形中以相同的方式栅格化共享边.Same way 表示每次都使用相同的像素.
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.
强制执行此顺序的一种简单方法是将您的线(三角形边)视为二维向量，如果它指向负 y 的方向或平行于 x 轴并指向该方向，则翻转其方向负 x 的.是时候学习一些 ASCII 艺术了！:)
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
看，这里的线段，比如说，1和线段5其实是同一种东西，唯一的区别就是从原点的端点到另一个端点的方向.因此，我们通过将第 4 至第 7 段转换为第 0 至 3 段并消除方向歧义，将这些情况减半.IOW，我们选择向y的OR增大的方向走，如果y在边上相同，则选择x的增大方向.
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("
");
}
}
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
",
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 之间共享的边的像素
请注意，即使没有未填充的间隙(像素)，其像素(在共享边上)被覆盖的三角形(因为在其顶部绘制了另一个三角形)可能会显示为不相交或形状笨拙，如果它太薄了.示例:
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
*++++++
*+++++++++++++
*+++++++++++++++++++++
-*++++++++++++++++++++++++++++
-*++++++++++++++++++++++++++++++++++++
*+++++++++++++++++++++++++++++++++++++++++++
*+++++++++++++++++++++++++++++++++++++++++++++++++++
*+++++++++++++++++++++++++++++++++++++++++++++++++++++
*+++++++++++++++++++++++++++++++++++++++++++
-*+++++++++++++++++++++++++++++++
-*+++++++++++++++++++++
*++++++++++
*
这篇关于我需要一个像素完美的三角形填充算法来避免锯齿伪影的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
