我需要一个像素完美的三角形填充算法，以避免锯齿假象 [英] I need a pixel-perfect triangle fill algorithm to avoid aliasing artifacts
问题描述
我在帮助别人想象的数学图像分析。
在这个过程中，我们会被分割二维形状的部分成三角形，并在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.
首先，光栅化三角形边缘。可以使用布氏该画线算法（如以下code）或任何工作。然后填写在该地区在两者之间。这将任意薄三角形工作。
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.
要确保不存在任何差距，不论顺序，其中三角形绘制也不论c您想在三角形同样的方式来栅格化共享边供给三角绘图$ C $顶点的顺序共享一个边缘。的同样的方式的意思是一样的像素每一次。
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.
一个简单的方法来执行这种顺序是治疗的线（三角形的边），其为2-D向量和翻转它的方向，如果它在负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，我们选择增加Ÿ的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.
下面是你如何能做到这一点在code：
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;
}
示例输出：
30:10 5:16 16:6 59:17
+++
++++++++
++++++++++++
+++++++++++++++++
+++++++++++++++****---
+++++++++++++****-----------
++++++++++****-------------------
++++++*****----------------------------
+++****-------------------------------------
****---------------------------------------------
*-----------------------------------------------------
-
注：
- + - 三角1个像素
- - - 三角2 像素
- * - 边缘的像素三角形1和2 之间共享
- "+" - 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
*++++++
*+++++++++++++
*+++++++++++++++++++++
-*++++++++++++++++++++++++++++
-*++++++++++++++++++++++++++++++++++++
*+++++++++++++++++++++++++++++++++++++++++++
*+++++++++++++++++++++++++++++++++++++++++++++++++++
*+++++++++++++++++++++++++++++++++++++++++++++++++++++
*+++++++++++++++++++++++++++++++++++++++++++
-*+++++++++++++++++++++++++++++++
-*+++++++++++++++++++++
*++++++++++
*
这篇关于我需要一个像素完美的三角形填充算法，以避免锯齿假象的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
