我在帮助别人与用户界面代码，以可视化的数学图像分析。 在这个过程中，我们将分割二维形状的部分成三角形，并在UI上填充一些三角形。
我们正在寻找这保证了如果两个三角形共享边的（准确地说，如果三角形中的任意两个顶点是相同的），那么不管绘制顺序和混叠的出现将不会上线的空白，未提取的像素填充算法两者之间。 （如果一些像素绘制两次这是正常的。）结果应该在任意比例确定。 一些三角形可能在地方极薄的薄片，下降到1个像素宽。
理想的情况下，也应该是一个合理有效的填充算法！
抗混叠不会在三角形渲染中使用，作为最终的图像需要是1位深度。
上下文是图像识别应用程序，所以所有顶点坐标将是精确到一个像素。
给出的要求，它看起来像有一个简单的解决方案。
首先，光栅化三角形边。 您可以使用的布氏该行绘制算法（如下面的代码）或任何工作。 然后填写在该地区之间。 这将任意薄三角形工作。
为了确保不存在任何差距，不论顺序，其中三角形绘制的，也不论供给三角形绘制代码的顶点的顺序的，你想在三角形共享边缘以同样的方式光栅化共享边。 同样的方式意味着每次都在同像素。
为了保证你每次从同一对顶点得到相同的像素坐标，你基本上要建立一个固定的顺序，也就是建立一个规则，总是选择同一个顶点出在给定的顺序无关的两个这给他们。
一种简单的方法来执行该顺序是治疗您的线路（三角形的边），其为2-d矢量和翻转它的方向，如果它在的负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，我们选择增加Ÿ的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
+++
++++++++
++++++++++++
+++++++++++++++++
+++++++++++++++****---
+++++++++++++****-----------
++++++++++****-------------------
++++++*****----------------------------
+++****-------------------------------------
****---------------------------------------------
*-----------------------------------------------------
-
传说：
要注意的是，即使不会有尚待填补的空白（像素），其像素（在共享边缘）被覆盖（因为在它上面绘制的其他三角形）三角形可能显示为不相交的或形状不规则的，如果它太薄。 例：
2:20 12:8 59:15 4:17
*++++++
*+++++++++++++
*+++++++++++++++++++++
-*++++++++++++++++++++++++++++
-*++++++++++++++++++++++++++++++++++++
*+++++++++++++++++++++++++++++++++++++++++++
*+++++++++++++++++++++++++++++++++++++++++++++++++++
*+++++++++++++++++++++++++++++++++++++++++++++++++++++
*+++++++++++++++++++++++++++++++++++++++++++
-*+++++++++++++++++++++++++++++++
-*+++++++++++++++++++++
*++++++++++
*
您对相邻三角形的关注是一个有效的。 如果两个三角形共享边的，你要确保沿着边缘的每一个像素“属于”专门为一个三角形或其他。 如果这些像素中的一个不属于任何三角形，你有一定的差距。 如果属于两个三角形，你已经透支（这是低效）和颜色可能取决于三角形渲染（这可能是不确定的）的数量级上。
既然你不使用抗锯齿，这其实不是太难。 这与其说是你需要为认真执行了智能算法。
光栅化三角形的典型方式是计算水平段是从顶部至底部的三角形的一部分。 您可以通过保持当前的左右边缘的轨道，而且基本上做在每个扫描线的每个边缘的X截距计算做到这一点。 它也可以有两个Bresenhem风格的画线算法，运行起来完成。 实际上，光栅化达多次打电话给在某个扫描线绘制水平线段的功能y一些左侧坐标x0一些正确的坐标x1 。
void DrawHLine(int y, int x0, int x1);
通常什么做的是确保光栅四舍五入以一致的方式在x轴截距，使x坐标计算一致，无论他们是否是一个三角形的右边缘或相邻三角形的左边缘的一部分。 这保证了沿着共享边缘的每个像素将属于两个三角形。
我们通过调整解决双重所有权DrawHLine ，使其从填充像素x0包容高达x1 排斥 。 因此，在共享边缘所有这些双重拥有的像素被定义为属于在共享边缘右侧的三角形。
你所寻找的是一个floodfill算法。
这里有一个 。
另一个链接 。
你可以在google“floodfill算法”为多。
[编辑]
也许这个网站 [着色器为基础的线框图]可以提供一些更多的想法。
这不是最有效的，但你可以遍历包含三角形和测试，如果每个像素是三角形内的正方形。
伪代码：
for(x : minX -> maxX)
for(y : minY -> maxY)
if(triangle.contains(x,y))
drawPixel(x,y);
当其minX是三个顶点，类似的还有maxX的，MINY和美星之间的最小X坐标。
为了更快的算法，你可以做一些快速和肮脏的填充（如slashmais填注），然后再做到这一点了周围的边缘像素。
点式三角试验被描述在这里 。
这是一个很好的研究问题。 了解布氏画线算法。
http://en.wikipedia.org/wiki/Bresenham's_line_algorithm
