Алгоритм заполнения треугольника
Я думаю об алгоритме растеризации треугольника. ( triangle_rasterization_lesson)
Я wtote следующий код:
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); это рисует треугольник, но заполнение выходит за границы.
В чем проблема?
2 ответа
Решение
Если это немного поможет, вот мой древний источник C++ для треугольника в VCL/GDI:
//---------------------------------------------------------------------------
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 ...
Источник основан на этом:
Вы увеличиваете х и у каждый цикл. Но вы не можете сделать это для каждого треугольника. Зависит от угла треугольника при увеличении x, возможно при уменьшении y. Например, если треугольник имеет 90 градусов, вы не увеличите x или y. Я не могу объяснить себя очень хорошо, но есть объяснение кода и изображения:
http://www.sunshine2k.de/coding/java/TriangleRasterization/TriangleRasterization.html
Этот алгоритм работает:
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
Визуальное объяснение того, что он делает: