ken@turtleva.UUCP (Ken Turkowski) (12/22/83)
echo x - hsalgs/u_tiler.c
cat >hsalgs/u_tiler.c <<'!Funky!Stuff!'
/* ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
u_tiler.c - "Universal" anti-aliasing tiler for convex polygons with
an arbitrary number of parameters/vertex.
Entries:
- u_tiler(npts,pts,npars,px_proc)
short npts,npars; void (*px_proc)();
double pts[];
NOTE!!! needs to be loaded with BB file providing px_proc(),
getseg() and putseg().
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ */
#define MAX_HRES 640 /* maximum horizontal resolution */
#define MAX_VRES 484 /* maximum vertical resolution */
#define SUBPIX .01 /* minimum allowable width or height */
#define MAX_OPAQUE .02 /* maximum transmittance considered opaque */
#define MAXLTS 16 /* max number of light sources */
#define MAXLONG 0x7FFFFFFF
#define MAXFLOAT 0xFFFF7FFF /* yes, that's right (look in the VAX manual) */
#define TRUE 1
#define FALSE 0
#define X 0
#define Y 1
#define PAR1 3 /* array index of first non-specific parameter */
#define NORMS 12
#define NORM_PARMS 6
#define MAX_PARS NORMS + NORM_PARMS*MAXLTS /* max allowed number of parms */
#define sqr(x) ((x)*(x))
static void (*px_proc)(); /* pointer to pixel write procedure */
/* parameters for image placement in big buffer memory */
short Xofset,Yofset;
short hres,vres,Y_pos,xleft,xrght;
/* polygon edge data structure */
typedef struct { short lnth;
double x,ht,par[MAX_PARS - PAR1];
} edge_position;
/* +++++++++++++++++++++++++ U_TILINIT ++++++++++++++++++++++++++++++++++++ */
u_tilinit(divisions,frmnum) /* init tiler */
short divisions,frmnum;
{ short i; double pow(),sqrt(); unsigned long array[4];
static short palred[256],palgrn[256],palblu[256]; /* pallette */
if (bbopen() < 0) exit();
if (frmnum == 0)
{ for (i=0; i<256; i++)
palred[i] = palgrn[i] = palblu[i] = 4096. * pow(i/256.,.43);
bbpalw(palred,palgrn,palblu,0,256);
}
array[0] = frmnum; array[1] = divisions; array[2] = 24; array[3] = 1;
bbwrite(0,502,array,4); /* load animation control */
divisions = sqrt((double)divisions);
hres = (32/divisions)*20; vres = 484/divisions;
Xofset = (frmnum % divisions) * hres;
Yofset = (divisions-1 - (frmnum / divisions)) * vres;
hres /= 2; vres /= 2; /* use half-res for scaling later */
bbzoom(divisions, Xofset + hres, Yofset + vres + 1);
}
/* +++++++++++++++++++++++++ U_TILER +++++++++++++++++++++++++++++++++++ */
u_tiler(npts,pts,npars,pxl_proc) /* tile a convex poly, taken clockwise */
short npts,npars; double pts[]; void (*pxl_proc)();
{
edge_position l_edge,r_edge,l_incr,r_incr,l_old,r_old;
short i,lpt,rpt,ptcnt,top_pt,next_line,top_line;
double top,bot,lft,rgt,ceil(),floor(),fabs();
if (npts < 3) { printf(" degenerate polygon\n"); return; }
px_proc = pxl_proc; /* set pointer to pixel write procedure */
top = 0.0; bot = MAX_VRES; lft = MAX_HRES; rgt = 0.;
for(i=0; i<npts; i++) /* scale to screen and find topmost vertex */
{ short j;
j = i * npars; /* offset for vertex */
pts[j+X] = hres * (pts[j+X] + 1.) + SUBPIX + Xofset;
pts[j+Y] = vres * (pts[j+Y] + 1.) + SUBPIX + Yofset;
if (pts[j+Y] > top) { top = pts[j+Y]; top_pt = i; }
if (pts[j+Y] < bot) bot = pts[j+Y]; /* get bounding box */
if (pts[j+X] < lft) lft = pts[j+X]; /* for size check */
if (pts[j+X] > rgt) rgt = pts[j+X];
}
if ((top - bot < SUBPIX) || (rgt - lft < SUBPIX)) /* ignore tiny polys */
{ printf(" rejected eensy polygon\n"); return; }
l_edge.lnth = r_edge.lnth = 0; /* scanlines left */
lpt = top_pt; rpt = top_pt; /* vertex pointers */
Y_pos = floor(top); /* set to top scanline */
next_line = FALSE; top_line = TRUE;
xleft = MAX_HRES; xrght = 0; /* initialize segment extremes */
ptcnt = 0; /* zero processed point count */
r_edge.x = l_edge.x = pts[top_pt*npars+X]; /* load top position */
r_edge.ht = l_edge.ht = pts[top_pt*npars+Y] - floor(pts[top_pt*npars+Y]);
for (i=PAR1; i<npars; i++)
r_edge.par[i-PAR1] = l_edge.par[i-PAR1] = pts[top_pt*npars+i];
/* ----------------------- scan loop --------------------------------- */
while(ptcnt <= npts)
{
/* get left side bottom positions */
copy(&l_edge,&l_old,npars-PAR1,next_line);/* copy to top posns */
if ((l_edge.lnth > 0) && next_line)
increment(&l_edge,&l_incr,&pts[lpt*npars],npars-PAR1);
else if (l_edge.lnth <= 0) /* get new edge block if nec. */
{ mkedge(&lpt,pts,npars,&l_edge,&l_incr,npts-1,npts); ptcnt++; }
/* get right side bottom positions */
copy(&r_edge,&r_old,npars-PAR1,next_line);/* copy to top posns */
if ((r_edge.lnth > 0) && next_line)
increment(&r_edge,&r_incr,&pts[rpt*npars],npars-PAR1);
else if (r_edge.lnth <= 0) /* get new edge block if nec. */
{ mkedge(&rpt,pts,npars,&r_edge,&r_incr,npts+1,npts); ptcnt++; }
scanseg(&l_edge,&l_old,&r_old,&r_edge,npars-PAR1,next_line | top_line);
if ((l_edge.ht == 0.) && (r_edge.ht == 0.)) /* outpt seg if lin done */
{ next_line = TRUE; putseg(Y_pos,xleft,xrght); Y_pos--; }
else next_line = FALSE;
top_line = FALSE;
if ((Y_pos <= bot) && (ptcnt >= npts) &&
(l_edge.lnth == 0) && (r_edge.lnth == 0)) break; /* quit if done */
}
putseg(Y_pos,xleft,xrght); /* store away bottom segment */
}
/* ++++++++++++++++++++++++++++ COPY ++++++++++++++++++++++++++++++++++++ */
copy(bot,top,npars,newln)
/* copy bottom-of-scanline pos. to top-of-scanline pos. */
edge_position *bot,*top; short newln;
{ short i;
top->x = bot->x; top->ht = newln? 1. : bot->ht;
for (i=0; i<npars; i++) top->par[i] = bot->par[i];
}
/* +++++++++++++++++++++++++++ INCREMENT ++++++++++++++++++++++++++++++++++ */
increment(edge,incr,pts,npars) /* increment edge block */
edge_position *edge,*incr; short npars;
double pts[];
{ double floor(); short i;
if (edge->lnth > 1)
{ edge->x += incr->x;
edge->lnth--;
for (i=0; i<npars; i++) edge->par[i] += incr->par[i];
}
else
{ edge->x = pts[X];
edge->ht = pts[Y] - floor(pts[Y]);
edge->lnth = 0;
for (i=0; i<npars; i++) edge->par[i] = pts[PAR1 + i];
}
}
/* +++++++++++++++++++++++++++++ SCANSEG +++++++++++++++++++++++++++++ */
scanseg(lbot,ltop,rtop,rbot,npars,newln) /*trapezoidal section of scan segment*/
edge_position *lbot,*ltop,*rtop,*rbot; short npars,newln;
{ short left_top,rght_top,new_left,new_rght,same_slope;
double left_ht,rght_ht,get_ht();
edge_position *lb,*lt,*rt,*rb,*v1,*v2,*v3,*v4;
/* allow for twisted or counterclockwise polygons */
if (ltop->x > rtop->x) { lt=rtop; rt=ltop; } else { lt=ltop; rt=rtop; }
if (lbot->x > rbot->x) { lb=rbot; rb=lbot; } else { lb=lbot; rb=rbot; }
/* find leftmost and rightmost pixels */
left_top = (lt->x < lb->x)? TRUE : FALSE;
rght_top = (rt->x > rb->x)? TRUE : FALSE;
/* get section of scanline if new line or smaller left or bigger right */
new_left = left_top? lt->x : lb->x; new_rght = rght_top? rt->x : rb->x;
if (newln)
{ xleft = new_left; xrght = new_rght; getseg(Y_pos,xleft,xrght); }
else { if (new_rght > xrght) { getseg(Y_pos,xrght+1,new_rght);
xrght = new_rght; }
if (new_left < xleft) { getseg(Y_pos,new_left,xleft-1);
xleft = new_left; }
}
/* order left-to-right and calculate thickness at inner vertices */
if (left_top)
{ v1 = lt;
if (rght_top) if (lb->x < rb->x) { v2=lb; v3=rb;
same_slope = FALSE; }
else { v2=rb; v3=lb;
same_slope = FALSE; }
else if (lb->x < rt->x) { v2=lb; v3=rt;
same_slope = TRUE; }
else { v2=rt; v3=lb;
same_slope = TRUE; }
}
else
{ v1 = lb;
if (rght_top) if (lt->x < rb->x) { v2=lt; v3=rb;
same_slope = TRUE; }
else { v2=rb; v3=lt;
same_slope = TRUE; }
else if (lt->x < rt->x) { v2=lt; v3=rt;
same_slope = FALSE; }
else { v2=rt; v3=lt;
same_slope = FALSE; }
}
v4 = rght_top? rt : rb;
if (same_slope) { left_ht = get_ht(v1,v2,v3);
rght_ht = get_ht(v2,v3,v4); }
else { left_ht = get_ht(v1,v2,v4);
rght_ht = get_ht(v1,v3,v4); }
/* call shader for nonzero length segments */
if ((v2->x - v1->x) > SUBPIX) shader(v1, 0.,v2,left_ht,npars);
if ((v3->x - v2->x) > SUBPIX) shader(v2,left_ht,v3,rght_ht,npars);
if ((v4->x - v3->x) > SUBPIX) shader(v3,rght_ht,v4, 0.,npars);
}
/* +++++++++++++++++++++++ GET_HT +++++++++++++++++++++++++++++++++++++ */
double get_ht(v1,v2,v3) /* vertical distance from v2 to line from v1 to v3 */
edge_position *v1,*v2,*v3;
{ double fabs(),div;
div = v3->x - v1->x; if (div <= 0.) div = 1.;
return fabs( v2->ht - ( v1->ht + (v3->ht - v1->ht) *
(v2->x - v1->x) / div ));
}
/* +++++++++++++++++++++++ SHADER +++++++++++++++++++++++++++++++++++++++ */
shader(left,lht,rght,rht,npars) /* shade segment - trapezoid with sloping
top, aligned with scanline at bottom and
with vertical sides assumed */
edge_position *left,*rght; double lht,rht; short npars;
{ short xleft,xrght;
xleft = left->x; xrght = rght->x;
/* --------------------------
| single pixel spanned |
-------------------------- */
if (xleft == xrght)
{ double cvrge;
cvrge = (rght->x - left->x) * (lht + rht) / 2;
(*px_proc)(xleft,left->par,cvrge);
}
/* ------------------------
| two pixels spanned |
------------------------ */
else if (xleft - xrght == 1)
{ double lcvrge,rcvrge,midhght;
lcvrge = xleft + 1 - left->x; rcvrge = rght->x - xrght;
midhght = lht + (rht - lht) * lcvrge / (lcvrge + rcvrge);
lcvrge = lcvrge * (lht + midhght) / 2.;
rcvrge = rcvrge * (rht + midhght) / 2.;
(*px_proc)(xleft,left->par,lcvrge);
(*px_proc)(xrght,rght->par,rcvrge);
}
/* ---------------------
| Multiple pixels |
--------------------- */
else
{ double pixel[MAX_PARS],px_inc[MAX_PARS];
short i,ix; double adj,xlnth,ht,hxinc,cvrge;
xlnth = (rght->x - left->x); /* ---- do left pixel ----- */
hxinc = (rht - lht) / xlnth; /* height increment / pixel */
adj = xleft + 1 - left->x;
ht = lht + hxinc * adj;
cvrge = (xleft + 1 - left->x) * (lht + ht) / 2; /* part pixel covrge */
(*px_proc)(xleft,left->par,cvrge);
for (i=0; i<npars; i++) /* increments */
{ px_inc[i] = (rght->par[i] - left->par[i]) / xlnth;
pixel[i] = left->par[i] + adj * px_inc[i];
}
for (ix=xleft+1; ix<=xrght; ix++) /* - loop through rest of pixels - */
{ if (ix != xrght) cvrge = ht + hxinc/2.; /* middle pixel */
else cvrge = (rght->x - ix) * (ht + rht)/2.; /* rgt */
(*px_proc)(ix,pixel,cvrge);
if (ix != xrght) /* middle pixel */
{ for (i=0; i<npars; i++) pixel[i] += px_inc[i];
ht += hxinc;
}
}
}
}
/* ++++++++++++++++++++++++ MKEDGE ++++++++++++++++++++++++++++++++ */
mkedge(ptr,pts,npars,edge,incmnts,ptrinc,npts) /* calculate edge block */
short *ptr,npars,ptrinc,npts;
double pts[];
edge_position *edge,*incmnts;
{
short opt,i; double floor();
opt = *ptr; *ptr = (*ptr + ptrinc) % npts; /* increment vertex ptr. */
/* lines spanned */
edge->lnth = floor(pts[opt*npars + Y]) - floor(pts[(*ptr)*npars + Y]);
if (edge->lnth <= 0) /* -------- all in one scanline -------- */
{ edge->x = pts[(*ptr)*npars + X]; /* load edge posns. */
edge->ht = pts[(*ptr)*npars + Y] - floor(pts[(*ptr)*npars+ Y]);
for (i=0; i<npars-PAR1; i++)
edge->par[i] = pts[(*ptr)*npars + i + PAR1];
return;
}
else /* ----- multiple scanlines ----------- */
{ double adj,ydif;
ydif = pts[opt*npars + Y] - pts[(*ptr)*npars + Y];
incmnts->x = (pts[(*ptr)*npars + X] - pts[opt*npars + X]) / ydif;
for (i=0; i<npars-PAR1; i++)
incmnts->par[i] = (pts[(*ptr)*npars + i + PAR1]
- pts[ opt *npars + i + PAR1]) / ydif;
/* adjust to scanline */
adj = pts[opt*npars + Y] - floor(pts[opt*npars + Y]);
edge->x = pts[opt*npars + X] + incmnts->x * adj;
edge->ht = 0.;
for (i=0; i<npars-PAR1; i++)
edge->par[i] = pts[opt*npars + i + PAR1] + incmnts->par[i] * adj;
}
}
!Funky!Stuff!