Geek Answers Handbook

Triangle Fill Algorithm

I am thinking of a rasterization triangle algorithm. ( triangle_rasterization_lesson )

I am using the following code:

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); } } }

With triangle(100, 100, 100, 400, 400, 100, image, red); It works correctly. But if I change the coordinates of X (xa, ya) and Z (xc, yc), so as not to fill my square.

With triangle(70, 50, 200, 100, 20, 150, image, red); he draws a triangle, but the filling goes beyond.

Where is the problem?

0
algorithm graphics rasterizing
source share
2 answers

If this helps a bit, this is my ancient C ++ source for triangle in 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; } //---------------------------------------------------------------------------

usage example:

 // 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 ...

The source is based on this:

  • how to rasterize a rotating rectangle (in 2d using setpixel)
  • Display an array of colors in C
+1
source share

You increment x and y every cycle. But you cannot do this for every triangle. Depends on the angle of the triangle with increasing x, possibly y decreases. For example, if the triangle is 90 degrees, you will not increase x or y. I can’t explain myself very well, but there is code and an image:

http://www.sunshine2k.de/coding/java/TriangleRasterization/TriangleRasterization.html

0
source share

More articles:


All Articles