ken@turtleva.UUCP (Ken Turkowski) (12/16/83)
echo x - hsalgs/hiq_tiler.c
cat >hsalgs/hiq_tiler.c <<'!Funky!Stuff!'
/* ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
hiq_tiler.c - "Universal" anti-aliasing tiler for convex polygons with
an arbitrary number of parameters/vertex.
Entries:
- hiq_tiler(npts,pts,npars,pix_proc)
short npts,npars; void (*pix_proc)();
double pts[];
NOTE!!! needs to be loaded with BB file providing pix_proc(),
getseg() and putseg() and numerous tiler support routines.
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ */
#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 (*pix_proc)(); /* pointer to pixel write procedure */
/* parameters for image placement in big buffer memory */
extern short Xofset,Yofset;
extern short hres,vres,Y_pos,xleft,xrght;
/* polygon edge data structure */
typedef struct { short lnth;
double x,ht,par[MAX_PARS - PAR1];
} edge_position;
/* +++++++++++++++++++++++++ HIQ_TILER +++++++++++++++++++++++++++++++++++ */
hiq_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; }
pix_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++; }
hiq_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 */
}
/* +++++++++++++++++++++++++++++ HIQ_SCANSEG +++++++++++++++++++++++++++++ */
hiq_scanseg(lbot,ltop,rtop,rbot,npars,newln) /*trapezoidal section of scan seg*/
edge_position *lbot,*ltop,*rtop,*rbot; short npars,newln;
{ short i,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,*v5,*v6,midlft,midrgt;
/* 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); }
/* get interpolated cross-trapezoid position at inner vertices */
if (same_slope) /* get intermediate pts on opposite sides */
{ double fraction,denom,fabs();
v6 = v4; v5 = v3; v3 = &midlft; v4 = &midrgt;
denom = v5->x - v1->x;
if(fabs(denom) < SUBPIX) fraction = 1.;
else fraction = (v2->x - v1->x) / denom;
v3->x = v2->x;
for (i=0; i<npars; i++)
v3->par[i] = v1->par[i] + fraction * (v5->par[i] - v1->par[i]);
denom = v6->x - v2->x;
if(fabs(denom) < SUBPIX) fraction = 1.;
else fraction = (v5->x - v2->x) / denom;
v4->x = v5->x;
for (i=0; i<npars; i++)
v4->par[i] = v2->par[i] + fraction * (v6->par[i] - v2->par[i]);
}
else /* get intermediate pts on wider side */
{ double fraction,denom,fabs();
v6 = v4; v4 = v3; v3 = &midlft; v5 = &midrgt;
denom = v6->x - v1->x;
if(fabs(denom) < SUBPIX) fraction = 1.;
else fraction = (v2->x - v1->x) / denom;
v3->x = v2->x;
for (i=0; i<npars; i++)
v3->par[i] = v1->par[i] + fraction * (v6->par[i] - v1->par[i]);
if(fabs(denom) < SUBPIX) fraction = 1.;
else fraction = (v4->x - v1->x) / denom;
v5->x = v4->x;
for (i=0; i<npars; i++)
v5->par[i] = v1->par[i] + fraction * (v6->par[i] - v1->par[i]);
}
/* call shader for nonzero length segments */
if ((v2->x - v1->x) > SUBPIX) hiq_shader(v1,v1, 0.,v2,v3,left_ht,npars);
if ((v4->x - v3->x) > SUBPIX) hiq_shader(v2,v3,left_ht,v4,v5,rght_ht,npars);
if ((v6->x - v5->x) > SUBPIX) hiq_shader(v4,v5,rght_ht,v6,v6, 0.,npars);
}
/* +++++++++++++++++++++++ HIQ_SHADER +++++++++++++++++++++++++++++++++++++++ */
hiq_shader(toplft,botlft,lht,toprgt,botrgt,rht,npars)
/* shade segment - trapezoid with sloping
top, aligned with scanline at bottom and
with vertical sides assumed */
edge_position *toplft,*botlft,*toprgt,*botrgt; double lht,rht; short npars;
{ short xleft,xrght;
xleft = toplft->x; xrght = toprgt->x;
/* --------------------------
| single pixel spanned |
-------------------------- */
if (xleft == xrght)
{ double cvr;
cvr = (toprgt->x - toplft->x) * (lht + rht) / 2;
(*pix_proc)(xleft,cvr,toplft->par,botlft->par,toprgt->par,botrgt->par);
}
/* ------------------------
| two pixels spanned |
------------------------ */
else if (xleft - xrght == 1)
{ double lcvr,rcvr,midhght;
lcvr = xleft + 1 - toplft->x; rcvr = toprgt->x - xrght;
midhght = lht + (rht - lht) * lcvr / (lcvr + rcvr);
lcvr = lcvr * (lht + midhght) / 2.;
rcvr = rcvr * (rht + midhght) / 2.;
(*pix_proc)(xleft,lcvr,toplft->par,botlft->par,toprgt->par,botrgt->par);
(*pix_proc)(xrght,rcvr,toplft->par,botlft->par,toprgt->par,botrgt->par);
}
/* ---------------------
| Multiple pixels |
--------------------- */
else
{ double tp_px1[MAX_PARS] ,tp_px2[MAX_PARS],
bt_px1[MAX_PARS] ,bt_px2[MAX_PARS],
top_inc[MAX_PARS],bot_inc[MAX_PARS],
*ltop,*lbot,*rtop,*rbot,*temp;
short i,ix; double adj,xlnth,ht,hxinc,cvr;
xlnth = (toprgt->x - toplft->x); /* ---- do left pixel ----- */
hxinc = (rht - lht) / xlnth; /* height increment / pixel */
adj = xleft + 1 - toplft->x;
ht = lht + hxinc * adj;
for (i=0; i<npars; i++) /* increments */
{ top_inc[i] = (toprgt->par[i] - toplft->par[i]) / xlnth;
bot_inc[i] = (botrgt->par[i] - botlft->par[i]) / xlnth;
tp_px2[i] = toplft->par[i] + adj * top_inc[i];
bt_px2[i] = toplft->par[i] + adj * top_inc[i];
}
cvr = (xleft + 1 - toplft->x) * (lht + ht) / 2; /* part pixel covrge */
(*pix_proc)(xleft,cvr,toplft->par,botlft->par,tp_px2,bt_px2);
rtop = tp_px2; rbot = bt_px2; ltop = tp_px1; lbot = bt_px1;
for (ix=xleft+1; ix<=xrght; ix++) /* loop through rest of pixels */
{ temp = ltop; ltop = rtop; rtop = temp; /* switch pointers */
temp = lbot; lbot = rbot; rbot = temp;
if (ix != xrght) /* middle pixel */
{ cvr = ht + hxinc/2.;
for (i=0; i<npars; i++) rtop[i] = ltop[i] + top_inc[i];
for (i=0; i<npars; i++) rbot[i] = lbot[i] + bot_inc[i];
ht += hxinc;
}
else /* rightmost pixel */
{ cvr = (toprgt->x - ix) * (ht + rht)/2.;
rtop = toprgt->par; rbot = botrgt->par;
}
(*pix_proc)(ix,cvr,ltop,lbot,rtop,rbot);
}
}
}
!Funky!Stuff!