Newsgroups: comp.os.msdos.djgpp,comp.graphics.algorithms
From: Elliott Oti <e DOT oti AT stud DOT warande DOT ruu DOT nl>
Subject: More compact SW polygon filler?
Sender: usenet AT fys DOT ruu DOT nl (News system Tijgertje)
Message-ID: <357889A3.3279@stud.warande.ruu.nl>
Date: Sat, 6 Jun 1998 00:13:23 GMT
Content-Transfer-Encoding: 7bit
Content-Type: text/plain; charset=us-ascii
Mime-Version: 1.0
Organization: Organz Are Private
Lines: 128
To: djgpp AT delorie DOT com
DJ-Gateway: from newsgroup comp.os.msdos.djgpp
Precedence: bulk

Greetings,

I know software polygon fillers are out of fashion these days, but I was
fooling around with a convex polygon filler today, trying to make it as
compact as possible (in terms of generated code, not source code). I
came up with the snippet below, as my best effort, and I wondered if any
other afficionado's have/can come up with even more compact, generalized
convex poly fillers? 

The sample below is in C and is for DOS. It compiles straight under
djgpp but should also work on a 16-bit DOS compiler (untested).
It is for 8-bpp single-colour polygons, but I've tried to abstract the
polygon type by using macro's, so that simple macro changes should
enable the same polygon filler to do hicolor/truecolor filling, or
texture-mapping, for instance. (This sort of abstraction begs for
templates and operator overloading :-).  

Cheers,
-- 
------------ Elliott Oti ---------------
   ------------- http://www.fys.ruu.nl/~oti  ---------

/*============  Convex polygon filler ================================*/
typedef struct
{
 int x,y;
} vertex;

#define EQ(b,a) b.x = a.x; b.y = a.y
#define ADD(b,a) b.x += a.x ; b.y += a.y
#define DIFF(a,b,c) if(a.y - b.y){ c.x = ((a.x - b.x ) << 16 )/(a.y -
b.y);\
                    c.y = 1; } else {c.x = (a.x - b.x ) << 16; c.y = 0;}
#define BUMP(a) a.x = a.x << 16
#define DRAWLINE(v1,v2,clr,scr)  if(v2.x > v1.x)\
        memset(scr[v1.y] + (v1.x >> 16),col,(v2.x - v1.x)>>16);\
        else memset(scr[v2.y] + (v2.x >> 16),col,(v1.x - v2.x)>>16)


void drawpoly(vertex *pts, int n, int col, void **screen)
{
  int top, bot, i, tl, tl2, tr, tr2;
  vertex left, right, dleft, dright;

  top = bot = 0;

  for( i=1 ; i<n ;i++ )
     {
        if( pts[i].y < pts[top].y )top = i;
        if( pts[i].y > pts[bot].y )bot = i;
     }

   EQ(left,pts[top]);
   EQ(right,pts[top]);
   BUMP(left);
   BUMP(right);
   tl = top;
   tr = top;
   tl2 = (tl + 1)%n;
   tr2 = (tr - 1 + n)%n;
   DIFF(pts[tl2], pts[tl], dleft);
   DIFF(pts[tr2], pts[tr], dright);

   while( left.y < pts[bot].y )
   {
      DRAWLINE(left,right,col,screen);

      ADD(left,dleft);
      ADD(right,dright);

     if(left.y == pts[tl2].y)
       {
        tl = tl2;
        tl2 = (tl + 1)%n;
        DIFF(pts[tl2], pts[tl], dleft);
       }

     if(right.y == pts[tr2].y)
       {
        tr = tr2;
        tr2 = (tr - 1 + n)%n;
        DIFF(pts[tr2], pts[tr], dright);
       }
    }
}


/*============== sample program ==========================*/

#include <stdio.h>
#include <dos.h>
#ifdef __DJGPP__
#include <sys/movedata.h>
#endif

int main()
{

 union REGS r;
 int time,i;
 char *screen[200];
 char buf[64000];
 vertex mypoly[4];

 mypoly[0].x = 10;   mypoly[0].y = 100;
 mypoly[1].x = 100;  mypoly[1].y = 10;
 mypoly[2].x = 150;  mypoly[2].y = 150;
 mypoly[3].x = 10;   mypoly[3].y = 170;

 memset(buf,0,64000);
 for(i=0;i<200;i++)screen[i] = buf + 320*i;

 drawpoly(mypoly, 4, 4 , (void *)screen);

 r.x.ax = 0x13;
 int86(0x10,&r,&r);
#ifdef __DJGPP__
 dosmemput(buf,64000,0xa0000);
#else
 _fmemcpy(MK_FP(0xa000,0),buf,64000);
#endif
 getch();
 r.x.ax = 0x3;
 int86(0x10,&r,&r);

return 0;
}
/*===========================================================*/