填充三角形的算法
Algorithm to fill triangle
我正在考虑光栅化三角算法。 ( triangle_rasterization_lesson )
我写了以下代码：
void triangle(int xa, int ya, int xb, int yb, int xc, int yc, TGAImage &image, TGAColor color)
{
line(xa, ya, xb, yb, image, color);
line(xa, ya, xc, yc, image, color);
line(xb, yb, xc, yc, image, color);
for (int x = xa; x<=xb; x++)
{
for (int y = ya; y<=yb; y++)
{
line(xc, yc, x, y, image, white);
}
}
}
使用 triangle(100, 100, 100, 400, 400, 100, image, red); 它可以正常工作。
但是，如果我将 X(xa, ya) 和 Z(xc, yc) 坐标交换为不填满我的方块。
使用 triangle(70, 50, 200, 100, 20, 150, image, red); 绘制三角形，但填充 comes out of bounds.
问题出在哪里？
你每次循环都将 x 和 y 增加一个。但是你不能对每个三角形都这样做。取决于 x 增加时的三角形角度，也许 y 减少。例如，如果三角形有 90 度，则不会增加 x 或 y。我不能很好地解释自己但是有代码和图像解释：
http://www.sunshine2k.de/coding/java/TriangleRasterization/TriangleRasterization.html
如果它有一点帮助，这是我在 VCL/GDI:
中三角形的古老 C++ 源代码
//---------------------------------------------------------------------------
class gfx_main
{
public:
Graphics::TBitmap *bmp;
int **pyx,xs,ys;
gfx_main();
~gfx_main();
void resize(int _xs=-1,int _ys=-1);
void troj(int x0,int y0,int x1,int y1,int x2,int y2,int col); // this is filled triangle
void _troj_line(int *pl,int *pr,int x0,int y0,int x1,int y1); // this is just subroutine
};
//---------------------------------------------------------------------------
gfx_main::gfx_main()
{
bmp=new Graphics::TBitmap;
pyx=NULL;
resize(1,1);
}
//---------------------------------------------------------------------------
gfx_main::~gfx_main()
{
delete bmp;
if (pyx) delete[] pyx;
}
//---------------------------------------------------------------------------
void gfx_main::resize(int _xs,int _ys)
{
if (pyx) delete[] pyx;
if ((_xs>0)&&(_ys>0)) { bmp->Width=_xs; bmp->Height=_ys; }
xs=bmp->Width;
ys=bmp->Height;
bmp->HandleType=bmDIB;
bmp->PixelFormat=pf32bit;
pyx=new int*[ys];
for (int y=0;y<ys;y++) pyx[y]=(int*)bmp->ScanLine[y];
}
//---------------------------------------------------------------------------
//--- rasterisations: -------------------------------------------------------
//---------------------------------------------------------------------------
void gfx_main::_troj_line(int *pl,int *pr,int x0,int y0,int x1,int y1)
{
int *pp;
int x,y,kx,ky,dx,dy,k,m,p;
// DDA variables (d)abs delta,(k)step direction
kx=0; dx=x1-x0; if (dx>0) kx=+1; if (dx<0) { kx=-1; dx=-dx; }
ky=0; dy=y1-y0; if (dy>0) ky=+1; if (dy<0) { ky=-1; dy=-dy; }
// target buffer according to ky direction
if (ky>0) pp=pl; else pp=pr;
// integer DDA line start point
x=x0; y=y0;
// fix endpoints just to be sure (wrong division constants by +/-1 can cause that last point is missing)
pp[y1]=x1; pp[y0]=x0;
if (dx>=dy) // x axis is major
{
k=dy+dy;
m=(dy-dx); m+=m;
p=m;
for (;;)
{
pp[y]=x;
if (x==x1) break;
x+=kx;
if (p>0) { y+=ky; p+=m; } else p+=k;
}
}
else{ // y axis is major
k=dx+dx;
m=(dx-dy); m+=m;
p=m;
for (;;)
{
pp[y]=x;
if (y==y1) break;
y+=ky;
if (p>0) { x+=kx; p+=m; } else p+=k;
}
}
}
//---------------------------------------------------------------------------
int rgb2bgr(int col)
{
union
{
BYTE db[4];
int dd;
} c;
BYTE q;
c.dd=col;
q=c.db[0]; c.db[0]=c.db[2]; c.db[2]=q;
return c.dd;
}
//---------------------------------------------------------------------------
void gfx_main::troj(int x0,int y0,int x1,int y1,int x2,int y2,int col)
{
col=rgb2bgr(col);
int *pl,*pr; // left/right buffers
pl=new int[ys];
pr=new int[ys];
int x,y,yy0,yy1,xx0,xx1;
// boundary line coordinates to buffers
_troj_line(pl,pr,x0,y0,x1,y1);
_troj_line(pl,pr,x1,y1,x2,y2);
_troj_line(pl,pr,x2,y2,x0,y0);
// y range
yy0=y0; if (yy0>y1) yy0=y1; if (yy0>y2) yy0=y2;
yy1=y0; if (yy1<y1) yy1=y1; if (yy1<y2) yy1=y2;
// fill with horizontal lines
for (y=yy0;y<=yy1;y++)
{
if (pl[y]<pr[y]) { xx0=pl[y]; xx1=pr[y]; }
else { xx1=pl[y]; xx0=pr[y]; }
for (x=xx0;x<=xx1;x++)
pyx[y][x]=col;
}
delete[] pl;
delete[] pr;
}
//---------------------------------------------------------------------------
用法示例：
// init
gfx_main gfx;
gfx.resize(640,480);
// clear screen
TCanvas *scr=gfx.bmp->Canvas;
scr->Pen ->Color=clAqua;
scr->Font ->Color=clYellow;
scr->Brush->Color=clBlack;
scr->FillRect(TRect(0,0,xs,ys));
// triangle
troj(10,10,120,60,70,100,clAqua);
// here gfx.bmp holds the rendered image ...
来源基于此：
- how to rasterize rotated rectangle (in 2d by setpixel)
- Display an array of color in C
[edit1]
如果你感兴趣，这里是这个的 3D 端口（带深度缓冲）：
- How to hide invisible elements of the 3d drawing?
此算法有效：
void function fill_triangle(x1,y1,x2,y2,x3,y3)
//get length of all sides
d1 = sqrt(((y2-y1)**2)+((x2-x1)**2))
d2 = sqrt(((y3-y2)**2)+((x3-x2)**2))
d3 = sqrt(((y1-y3)**2)+((x1-x3)**2))
if(((d1<d2)or(d1=d2))and((d1<d2)or(d1=d2))) //the first side is the shortest
tx = x1
ty = y1
vx = (x2-x1)/d1
vy = (y2-y1)/d1
counter = 0
while(counter<d1)
draw_line(x3,y3,tx,ty)
//drawing a line from point(x3,y3) to point(tx,ty).
tx = tx + vx
ty = ty + vy
counter = counter + 1
else if((d2<d3)or(d2=d3)) //the second side is the shortest
tx = x2
ty = y2
vx = (x3-x2)/d2
vy = (y3-y2)/d2
counter = 0
while(counter<d2)
draw_line(x1,y1,tx,ty)
tx = tx + vx
ty = ty + vy
counter = counter + 1
else // the third side is shortest
tx = x3
ty = y3
vx = (x1-x3)/d3
vy = (y1-y3)/d3
counter = 0
while(counter<d3)
draw_line(x2,y2,tx,ty)
tx = tx + vx
ty = ty + vy
counter = counter + 1
它正在做什么的直观解释：
我正在考虑光栅化三角算法。 ( triangle_rasterization_lesson )
我写了以下代码：
void triangle(int xa, int ya, int xb, int yb, int xc, int yc, TGAImage &image, TGAColor color)
{
line(xa, ya, xb, yb, image, color);
line(xa, ya, xc, yc, image, color);
line(xb, yb, xc, yc, image, color);
for (int x = xa; x<=xb; x++)
{
for (int y = ya; y<=yb; y++)
{
line(xc, yc, x, y, image, white);
}
}
}
使用 triangle(100, 100, 100, 400, 400, 100, image, red); 它可以正常工作。
但是，如果我将 X(xa, ya) 和 Z(xc, yc) 坐标交换为不填满我的方块。
使用 triangle(70, 50, 200, 100, 20, 150, image, red); 绘制三角形，但填充 comes out of bounds.
问题出在哪里？
你每次循环都将 x 和 y 增加一个。但是你不能对每个三角形都这样做。取决于 x 增加时的三角形角度，也许 y 减少。例如，如果三角形有 90 度，则不会增加 x 或 y。我不能很好地解释自己但是有代码和图像解释：
http://www.sunshine2k.de/coding/java/TriangleRasterization/TriangleRasterization.html
如果它有一点帮助，这是我在 VCL/GDI:
中三角形的古老 C++ 源代码//---------------------------------------------------------------------------
class gfx_main
{
public:
Graphics::TBitmap *bmp;
int **pyx,xs,ys;
gfx_main();
~gfx_main();
void resize(int _xs=-1,int _ys=-1);
void troj(int x0,int y0,int x1,int y1,int x2,int y2,int col); // this is filled triangle
void _troj_line(int *pl,int *pr,int x0,int y0,int x1,int y1); // this is just subroutine
};
//---------------------------------------------------------------------------
gfx_main::gfx_main()
{
bmp=new Graphics::TBitmap;
pyx=NULL;
resize(1,1);
}
//---------------------------------------------------------------------------
gfx_main::~gfx_main()
{
delete bmp;
if (pyx) delete[] pyx;
}
//---------------------------------------------------------------------------
void gfx_main::resize(int _xs,int _ys)
{
if (pyx) delete[] pyx;
if ((_xs>0)&&(_ys>0)) { bmp->Width=_xs; bmp->Height=_ys; }
xs=bmp->Width;
ys=bmp->Height;
bmp->HandleType=bmDIB;
bmp->PixelFormat=pf32bit;
pyx=new int*[ys];
for (int y=0;y<ys;y++) pyx[y]=(int*)bmp->ScanLine[y];
}
//---------------------------------------------------------------------------
//--- rasterisations: -------------------------------------------------------
//---------------------------------------------------------------------------
void gfx_main::_troj_line(int *pl,int *pr,int x0,int y0,int x1,int y1)
{
int *pp;
int x,y,kx,ky,dx,dy,k,m,p;
// DDA variables (d)abs delta,(k)step direction
kx=0; dx=x1-x0; if (dx>0) kx=+1; if (dx<0) { kx=-1; dx=-dx; }
ky=0; dy=y1-y0; if (dy>0) ky=+1; if (dy<0) { ky=-1; dy=-dy; }
// target buffer according to ky direction
if (ky>0) pp=pl; else pp=pr;
// integer DDA line start point
x=x0; y=y0;
// fix endpoints just to be sure (wrong division constants by +/-1 can cause that last point is missing)
pp[y1]=x1; pp[y0]=x0;
if (dx>=dy) // x axis is major
{
k=dy+dy;
m=(dy-dx); m+=m;
p=m;
for (;;)
{
pp[y]=x;
if (x==x1) break;
x+=kx;
if (p>0) { y+=ky; p+=m; } else p+=k;
}
}
else{ // y axis is major
k=dx+dx;
m=(dx-dy); m+=m;
p=m;
for (;;)
{
pp[y]=x;
if (y==y1) break;
y+=ky;
if (p>0) { x+=kx; p+=m; } else p+=k;
}
}
}
//---------------------------------------------------------------------------
int rgb2bgr(int col)
{
union
{
BYTE db[4];
int dd;
} c;
BYTE q;
c.dd=col;
q=c.db[0]; c.db[0]=c.db[2]; c.db[2]=q;
return c.dd;
}
//---------------------------------------------------------------------------
void gfx_main::troj(int x0,int y0,int x1,int y1,int x2,int y2,int col)
{
col=rgb2bgr(col);
int *pl,*pr; // left/right buffers
pl=new int[ys];
pr=new int[ys];
int x,y,yy0,yy1,xx0,xx1;
// boundary line coordinates to buffers
_troj_line(pl,pr,x0,y0,x1,y1);
_troj_line(pl,pr,x1,y1,x2,y2);
_troj_line(pl,pr,x2,y2,x0,y0);
// y range
yy0=y0; if (yy0>y1) yy0=y1; if (yy0>y2) yy0=y2;
yy1=y0; if (yy1<y1) yy1=y1; if (yy1<y2) yy1=y2;
// fill with horizontal lines
for (y=yy0;y<=yy1;y++)
{
if (pl[y]<pr[y]) { xx0=pl[y]; xx1=pr[y]; }
else { xx1=pl[y]; xx0=pr[y]; }
for (x=xx0;x<=xx1;x++)
pyx[y][x]=col;
}
delete[] pl;
delete[] pr;
}
//---------------------------------------------------------------------------
用法示例：
// init
gfx_main gfx;
gfx.resize(640,480);
// clear screen
TCanvas *scr=gfx.bmp->Canvas;
scr->Pen ->Color=clAqua;
scr->Font ->Color=clYellow;
scr->Brush->Color=clBlack;
scr->FillRect(TRect(0,0,xs,ys));
// triangle
troj(10,10,120,60,70,100,clAqua);
// here gfx.bmp holds the rendered image ...
来源基于此：
- how to rasterize rotated rectangle (in 2d by setpixel)
- Display an array of color in C
[edit1]
如果你感兴趣，这里是这个的 3D 端口（带深度缓冲）：
- How to hide invisible elements of the 3d drawing?
此算法有效：
void function fill_triangle(x1,y1,x2,y2,x3,y3)
//get length of all sides
d1 = sqrt(((y2-y1)**2)+((x2-x1)**2))
d2 = sqrt(((y3-y2)**2)+((x3-x2)**2))
d3 = sqrt(((y1-y3)**2)+((x1-x3)**2))
if(((d1<d2)or(d1=d2))and((d1<d2)or(d1=d2))) //the first side is the shortest
tx = x1
ty = y1
vx = (x2-x1)/d1
vy = (y2-y1)/d1
counter = 0
while(counter<d1)
draw_line(x3,y3,tx,ty)
//drawing a line from point(x3,y3) to point(tx,ty).
tx = tx + vx
ty = ty + vy
counter = counter + 1
else if((d2<d3)or(d2=d3)) //the second side is the shortest
tx = x2
ty = y2
vx = (x3-x2)/d2
vy = (y3-y2)/d2
counter = 0
while(counter<d2)
draw_line(x1,y1,tx,ty)
tx = tx + vx
ty = ty + vy
counter = counter + 1
else // the third side is shortest
tx = x3
ty = y3
vx = (x1-x3)/d3
vy = (y1-y3)/d3
counter = 0
while(counter<d3)
draw_line(x2,y2,tx,ty)
tx = tx + vx
ty = ty + vy
counter = counter + 1
它正在做什么的直观解释：