ken@turtleva.UUCP (Ken Turkowski) (12/22/83)
echo x - hsalgs/rgbtiler.c
cat >hsalgs/rgbtiler.c <<'!Funky!Stuff!'
/* ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
rgbtiler.c - simpler anti-aliasing tiler for convex polygons
Entries:
- rgbtilinit(size,divisions,frmnum) - gets ptr to big buffer, initializes.
- rgbtiler(npts,pts) - short npts; struct { double x,y,z,r,g,b; } pts[];
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ */
#define HRES 640
#define VRES 484
#define SUBPIX .01 /* minimum allowable width or height */
#define MAXLONG 0x7FFFFFFF
#define MAXFLOAT 0xFFFF7FFF /* yes, that's right (look in the VAX manual) */
#define TRUE 1
#define FALSE 0
#define SQR(x) ((x)*(x))
/* parameters for image placement in big buffer memory (used by shiny_tlr.c) */
short Xofset,Yofset,rgb_24bit,rgb_16bit,bw_8bit,bw_4bit,field;
short hres,vres,Y_pos,xleft,xrght,cvr[642];
double red[642],grn[642],blu[642];
/* polygon edge data structure */
typedef struct { double x,r,g,b,ht; short lnth; } edge_position;
/* +++++++++++++++++++++++++ RGBTILINIT ++++++++++++++++++++++++++++++++++++ */
rgbtilinit(bits,divisions,frmnum) /* init tiler, set pointer to frame buffer */
short bits,divisions,frmnum;
{ short i; double pow(),sqrt(); long array[4];
static short palred[256],palgrn[256],palblu[256]; /* pallette */
if (bbopen() < 0) exit();
switch (bits)
{ case 4 : { bw_4bit = TRUE; break; }
case 8 : { bw_8bit = TRUE; break; }
case 16 : { rgb_16bit = TRUE; break; }
case 24 : { rgb_24bit = TRUE; break; }
case 32 : { rgb_24bit = TRUE; break; }
}
if (frmnum == 0)
{ if (bw_4bit)
for (i=0; i<16; i++) /* special pallette for 4-bit images */
{ short j;
palred[i] = palgrn[i] = palblu[i] = 4096. * pow(i/256.,.43);
j = i << 4;
palred[j] = palgrn[j] = palblu[j] = palred[i];
}
else 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] = bits; array[3] = 1;
bbwrite(0,502,array,4); /* load animation control */
divisions = sqrt((double)divisions);
hres = (32/divisions)*20; vres = 484/divisions;
field = frmnum % (32/bits); frmnum /= 32/bits;
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);
}
/* +++++++++++++++++++++++++ RGBTILER ++++++++++++++++++++++++++++++++++++++ */
rgbtiler(npts,pts) /* tile a convex polygon with vertices taken clockwise */
short npts;
struct { double x,y,z,r,g,b,xn,yn,zn,t; } pts[];
{
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();
if (npts < 3) { printf(" degenerate polygon\n"); return; }
top = 0.0; bot = VRES; lft = HRES; rgt = 0.;
for(i=0; i<npts; i++) /* scale to screen and find topmost vertex */
{ pts[i].x = hres * (pts[i].x + 1.) + SUBPIX + Xofset;
pts[i].y = vres * (pts[i].y + 1.) + SUBPIX + Yofset;
if (pts[i].y > top) { top = pts[i].y; top_pt = i; }
if (pts[i].y < bot) bot = pts[i].y; /* get bounding box */
if (pts[i].x < lft) lft = pts[i].x; /* for size check */
if (pts[i].x > rgt) rgt = pts[i].x;
/* convert to 8-bit color values */
pts[i].r *= 255.; pts[i].g *= 255.; pts[i].b *= 255.;
}
if ((top - bot < SUBPIX) || (rgt - lft < SUBPIX)) /* ignore tiny polys */
{ printf(" rejected eensy polygon\n"); return; }
/* printf(" new poly left %g, rght %g, top %g, bottom %g\n",
lft,rgt,top,bot); /* diagnostic */
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 = HRES; xrght = 0; /* initialize segment extremes */
ptcnt = 0; /* zero processed point count */
r_edge.x = l_edge.x = pts[top_pt].x; /* load top postion */
r_edge.r = l_edge.r = pts[top_pt].r;
r_edge.g = l_edge.g = pts[top_pt].g;
r_edge.b = l_edge.b = pts[top_pt].b;
r_edge.ht = l_edge.ht = pts[top_pt].y - floor(pts[top_pt].y);
/* ----------------------- scan loop --------------------------------- */
while(ptcnt <= npts)
{
/* get left side bottom positions */
copy(&l_edge,&l_old,next_line); /* copy to top positions */
if ((l_edge.lnth > 0) && next_line) increment(&l_edge,&l_incr,lpt,pts);
else if (l_edge.lnth <= 0) /* get new edge block if nec. */
{ bmkedge(&lpt,pts,&l_edge,&l_incr,npts-1,npts); ptcnt++; }
/* get right side bottom positions */
copy(&r_edge,&r_old,next_line); /* copy to top positions */
if ((r_edge.lnth > 0) && next_line) increment(&r_edge,&r_incr,rpt,pts);
else if (r_edge.lnth <= 0) /* get new edge block if nec. */
{ bmkedge(&rpt,pts,&r_edge,&r_incr,npts+1,npts); ptcnt++; }
scanseg(&l_edge,&l_old,&r_old,&r_edge,next_line | top_line);
if ((l_edge.ht == 0.) && (r_edge.ht == 0.)) /* outpt seg if line done */
{ next_line = TRUE; putseg(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(xleft,xrght); /* store away bottom segment */
}
/* ++++++++++++++++++++++++++++ COPY ++++++++++++++++++++++++++++++++++++ */
copy(bot,top,newln) /* copy bottom-of-scanline pos. to top-of-scanline pos. */
edge_position *bot,*top;
{ top->x = bot->x; top->ht = newln? 1. : bot->ht;
top->r = bot->r; top->g = bot->g; top->b = bot->b;
}
/* +++++++++++++++++++++++++++ INCREMENT ++++++++++++++++++++++++++++++++++ */
increment(edge,incr,ptr,pts) /* increment edge block */
edge_position *edge,*incr; short ptr;
struct { double x,y,z,r,g,b,xn,yn,zn,t; } pts[];
{ double floor();
if (edge->lnth > 1)
{ edge->x += incr->x;
edge->r += incr->r; edge->g += incr->g; edge->b += incr->b;
edge->lnth--;
}
else
{ edge->x = pts[ptr].x;
edge->r = pts[ptr].r; edge->g = pts[ptr].g; edge->b = pts[ptr].b;
edge->ht = pts[ptr].y - floor(pts[ptr].y);
edge->lnth = 0;
}
}
/* +++++++++++++++++++++++++++++ SCANSEG +++++++++++++++++++++++++++++ */
scanseg(lbot,ltop,rtop,rbot,newln) /* trapezoidal section of scan segment */
edge_position *lbot,*ltop,*rtop,*rbot; short 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(xleft,xrght); }
else { if (new_rght > xrght) { getseg(xrght+1,new_rght);
xrght = new_rght; }
if (new_left < xleft) { getseg(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);
if ((v3->x - v2->x) > SUBPIX) shader(v2,left_ht,v3,rght_ht);
if ((v4->x - v3->x) > SUBPIX) shader(v3,rght_ht,v4, 0.);
}
/* +++++++++++++++++++++++ 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 ));
}
/* ++++++++++++++++++++++++ GETSEG +++++++++++++++++++++++++++++++++++++++ */
getseg(xleft,xrght) /* read and unpack section of scanline */
short xleft,xrght;
{ short i; unsigned long line[642];
bbread(xleft,Y_pos,&line[xleft],xrght-xleft+1);
for (i=xleft; i<=xrght; i++)
{ cvr[i] = line[i] >> 24; red[i] = (line[i] >> 16) & 255;
grn[i] = (line[i] >> 8) & 255; blu[i] = line[i] & 255;
}
}
/* ++++++++++++++++++++++++ PUTSEG ++++++++++++++++++++++++++++++++++++++++ */
putseg(xleft,xrght) /* pack up and write a section of scanline */
short xleft,xrght;
{ short i; unsigned long line[642];
for (i=xleft; i<=xrght; i++)
{ line[i] = ( cvr[i] << 24) | ((short)red[i] << 16) |
((short)grn[i] << 8) | (short)blu[i];
/* printf(" %d",cvr[i]); /* diagnostic */
}
bbwrite(xleft,Y_pos,&line[xleft],xrght-xleft+1);
/* printf(" line %d \n",Y_pos); /* diagnostic */
}
/* +++++++++++++++++++++++ SHADER ++++++++++++++++++++++++++++++++++++++++ */
shader(left,lht,rght,rht) /* shade segment - trapezoid with sloping
top, aligned with scanline at bottom and
with vertical sides assumed */
edge_position *left,*rght; double lht,rht;
{ short xleft,xrght;
xleft = left->x; xrght = rght->x;
/* printf(" segment from %d to %d \n",xleft,xrght); /* diagnostic */
/* --------------------------
| single pixel spanned |
-------------------------- */
if (xleft == xrght)
{ double cvrge;
cvrge = (rght->x - left->x) * (lht + rht) / 2;
pixout(xleft,left,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.;
pixout(xleft,left,lcvrge);
pixout(xrght,rght,rcvrge);
}
/* ---------------------
| Multiple pixels |
--------------------- */
else
{ edge_position pixel;
short ix; double adj,xlnth,rxinc,gxinc,bxinc,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 */
pixout(xleft,left,cvrge);
rxinc = (rght->r - left->r) / xlnth; /* color increments */
gxinc = (rght->g - left->g) / xlnth;
bxinc = (rght->b - left->b) / xlnth;
pixel.r = left->r + adj * rxinc;
pixel.g = left->g + adj * gxinc;
pixel.b = left->b + adj * bxinc;;
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 */
pixout(ix,&pixel,cvrge);
if (ix != xrght) /* middle pixel */
{ pixel.r += rxinc; pixel.g += gxinc;
pixel.b += bxinc; ht += hxinc;
}
}
}
}
/* ++++++++++++++++++++++++ BMKEDGE ++++++++++++++++++++++++++++++++ */
bmkedge(ptr,pts,edge,incmnts,ptrinc,npts) /* calculate edge block for tiler */
short *ptr,ptrinc,npts;
struct { double x,y,z,r,g,b,xn,yn,zn,t; } pts[];
edge_position *edge,*incmnts;
{
short opt; double floor();
opt = *ptr; *ptr = (*ptr + ptrinc) % npts; /* increment vertex ptr. */
edge->lnth = floor(pts[opt].y) - floor(pts[*ptr].y); /* lines spanned */
if (edge->lnth <= 0) /* -------- all in one scanline -------- */
{ edge->x = pts[*ptr].x; /* load edge posns. */
edge->r = pts[*ptr].r; edge->g = pts[*ptr].g; edge->b = pts[*ptr].b;
edge->ht = pts[*ptr].y - floor(pts[*ptr].y);
return;
}
else /* ----- multiple scanlines ----------- */
{ double blnd,ydif;
ydif = pts[opt].y - pts[*ptr].y;
incmnts->x = (pts[*ptr].x - pts[opt].x) / ydif;
incmnts->r = (pts[*ptr].r - pts[opt].r) / ydif;
incmnts->g = (pts[*ptr].g - pts[opt].g) / ydif;
incmnts->b = (pts[*ptr].b - pts[opt].b) / ydif;
blnd = pts[opt].y - floor(pts[opt].y); /* adjust to scanline */
edge->x = pts[opt].x + incmnts->x * blnd;
edge->r = pts[opt].r + incmnts->r * blnd;
edge->g = pts[opt].g + incmnts->g * blnd;
edge->b = pts[opt].b + incmnts->b * blnd;
edge->ht = 0.;
}
}
/* ++++++++++++++++++++++++++ PIXOUT +++++++++++++++++++++++++++++++++ */
pixout(X,pixel,covrge)
short X; edge_position *pixel; double covrge;
{ double oldcvr;
if (!rgb_24bit) error(" only 24-bit rgb output just now");
oldcvr = cvr[X]; /* get previous pixel coverage */
if (oldcvr == 0.)
{ cvr[X] = covrge * 255. + .5;
if (cvr[X] > 0)
{ red[X] = pixel->r; grn[X] = pixel->g; blu[X] = pixel->b; }
}
else if (oldcvr < 255.)
{ oldcvr /= 255.; /* convert to 0. <= oldcvr <= 1. */
if ((oldcvr + covrge) >= 1.) /* pixel fully covered */
{ covrge = 1. - oldcvr; cvr[X] = 255; }
else /* pixel partially covered */
{ double adj;
adj = oldcvr + covrge; cvr[X] = adj * 255. + .5;
oldcvr /= adj; covrge /= adj;
}
red[X] = red[X] * oldcvr + pixel->r * covrge;
grn[X] = grn[X] * oldcvr + pixel->g * covrge;
blu[X] = blu[X] * oldcvr + pixel->b * covrge;
}
}
!Funky!Stuff!