Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!wuarchive!sdd.hp.com!spool.mu.edu!sol.ctr.columbia.edu!ucselx!crash!jcs
From: jcs@crash.cts.com (John Schultz)
Newsgroups: comp.sys.amiga.programmer
Subject: Re: fast line & polygon drawing...here's some routines...
Message-ID: <1991May11.092144.7553@crash.cts.com>
Date: 11 May 91 09:21:44 GMT
References: <1991May7.003110.1684@monu6.cc.monash.edu.au> <3367.tnews@templar.actrix.gen.nz>
Organization: Crash TimeSharing, El Cajon, CA
Lines: 133



Here's some newer (optimized) code to play with...
(Just the C front end to the assembly code just reposted)

  John

/* fill.c, processor poly filler   */
/* Copyright (c) 1991 John Schultz */
/* This is the latest version of the C interface to my processor
   polygon fill code.
*/

typedef struct shortpoint2d {
  short x,y;
} shortpoint2d;

#define WIDTH  320
#define HEIGHT 200

static short xmin[HEIGHT+1], xmax[HEIGHT+1];
static short * xt;

/******************* COUNTERCLOCKWISE POLYGONS ********************/
/**************** (This version does clockwise too) ***************/

void drawpolyc(shortpoint2d * vp,
               char * p,    /* PLANEPTR */
               short count,
               short color){
shortpoint2d * tmax, * tmin;
shortpoint2d * tp, * tpn;
shortpoint2d * last;
long cmp;
long orient;

/* Get last point */
  last = &vp[count-1];

/* Cross product to check for check for line case */
  if (count > 3) { /* Use Newell method */
    orient = 0;
    tp = vp; /* Point to first point */
    while (1) {
      if (tp == last)
        tpn = vp; /* Set next pointer to first point */
      else
        tpn = tp + 1; /* point to next. Compiler does: tp + sizeof(*tp) */
      orient += (tp->x - tpn->x)*(tp->y + tpn->y);
      if (tpn == vp) break; /* Come full circle */
      tp = tpn; /* go to next */
    } /* while */
  } else { /* Simple cross-product: triangle case */
    orient = (vp[1].x - vp[0].x)*(vp[2].y - vp[0].y) - 
             (vp[1].y - vp[0].y)*(vp[2].x - vp[0].x);
  } /* if count */

  if (orient == 0L) { /* Collinear: draw a line */
/* Find two points that aren't equal */
    cmp = *(long *)vp; /* First point */
    tp = vp + 1; /* Point to next (Compiler does: vp + sizeof(*vp) */
    while (1) {
      if ((cmp != (*(long *)tp)) || (tp == last)) break;
      tp++;      
    } /* while */
    drawline(p,vp->x,vp->y,tp->x,tp->y,color);
    return;
  } /* if line case */

/* Find miny,maxy */
  tmin = vp;   /* Point at first */
  tmax = vp;   /* "            " */
  tp = vp + 1; /* Point to next (Compiler does: vp + sizeof(*vp) */

  while (1) {
    if (tp->y < tmin->y) {
      tmin = tp;
    } else if (tp->y == tmin->y) {
      if (tp->x >= tmax->x) {
        tmin = tp;
      } /* if tp->x */
    } /* if tp->y */
    if (tp->y > tmax->y) {  /* MaxY */
      tmax = tp;
    } else if (tp->y == tmax->y) {
      if (tp->x < tmax->x) { /* Get maxY, minX */
        tmax = tp;
      } /* if tp->x */
    } /* if tmaxy */
    if (tp == last) break;
    tp++;
  };

  if (orient < 0) {

/* Fill tables */
  tp = tmin; /* Temp point starts at miny */
  xt = xmin; /* Fill xmin table first */
  while (1) {
    if (tp == last)
      tpn = vp; /* Set to first point */
    else
      tpn = tp + 1; /* Next. Compiler does: tp + sizeof(*tp) */
    fillline68k(tp->x,tp->y,tpn->x,tpn->y,xt);
    if (tpn == tmin) break; /* Come full circle, quit */
    if (tpn == tmax) xt = xmax; /* Fill max table */
    tp = tpn; /* Go to next */
  } /* while */

  } else {

/* Fill tables */
  tp = tmin; /* Temp point starts at miny */
  xt = xmax; /* Fill xmax table first */
  while (1) {
    if (tp == last)
      tpn = vp; /* Set to first point */
    else
      tpn = tp + 1; /* Next. Compiler does: tp + sizeof(*tp) */
    fillline68k(tp->x,tp->y,tpn->x,tpn->y,xt);
    if (tpn == tmin) break; /* Come full circle, quit */
    if (tpn == tmax) xt = xmin; /* Fill min table */
    tp = tpn; /* Go to next */
  } /* while */

  } /* if orient */

/* Draw polygon */
  scanconvpix(p,xmin,xmax,tmin->y,tmax->y,color);

} /* drawpolyc */

/* end fill.c */