Category : C Source Code
Archive : GRAFGEM1.ZIP
Filename : POLY_SCA.C
Output of file : POLY_SCA.C contained in archive : GRAFGEM1.ZIP
* Generic Convex Polygon Scan Conversion and Clipping
* by Paul Heckbert
* from "Graphics Gems", Academic Press, 1990
*/
/*
* poly_scan.c: point-sampled scan conversion of convex polygons
*
* Paul Heckbert 1985, Dec 1989
*/
#include
#include
#include "poly.h"
/*
* poly_scan: Scan convert a polygon, calling pixelproc at each pixel with an
* interpolated Poly_vert structure. Polygon can be clockwise or ccw.
* Polygon is clipped in 2-D to win, the screen space window.
*
* Scan conversion is done on the basis of Poly_vert fields sx and sy.
* These two must always be interpolated, and only they have special meaning
* to this code; any other fields are blindly interpolated regardless of
* their semantics.
*
* The pixelproc subroutine takes the arguments:
*
* pixelproc(x, y, point)
* int x, y;
* Poly_vert *point;
*
* All the fields of point indicated by p->mask will be valid inside pixelproc
* except sx and sy. If they were computed, they would have values
* sx=x+.5 and sy=y+.5, since sampling is done at pixel centers.
*/
void poly_scan(p, win, pixelproc)
register Poly *p; /* polygon */
Window *win; /* 2-D screen space clipping window */
void (*pixelproc)(); /* procedure called at each pixel */
{
register int i, li, ri, y, ly, ry, top, rem, mask;
double ymin;
Poly_vert l, r, dl, dr;
if (p->n>POLY_NMAX) {
fprintf(stderr, "poly_scan: too many vertices: %d\n", p->n);
return;
}
ymin = HUGE;
for (i=0; i
if (p->vert[i].sy < ymin) {
ymin = p->vert[i].sy;
top = i;
}
li = ri = top; /* left and right vertex indices */
rem = p->n; /* number of vertices remaining */
y = ceil(ymin-.5); /* current scan line */
ly = ry = y-1; /* lower end of left & right edges */
mask = p->mask & ~POLY_MASK(sy); /* stop interpolating screen y */
while (rem>0) { /* scan in y, activating new edges on left & right */
/* as scan line passes over new vertices */
while (ly<=y && rem>0) { /* advance left edge? */
rem--;
i = li-1; /* step ccw down left side */
if (i<0) i = p->n-1;
incrementalize_y(&p->vert[li], &p->vert[i], &l, &dl, y, mask);
ly = floor(p->vert[i].sy+.5);
li = i;
}
while (ry<=y && rem>0) { /* advance right edge? */
rem--;
i = ri+1; /* step cw down right edge */
if (i>=p->n) i = 0;
incrementalize_y(&p->vert[ri], &p->vert[i], &r, &dr, y, mask);
ry = floor(p->vert[i].sy+.5);
ri = i;
}
while (y
if (l.sx<=r.sx) scanline(y, &l, &r, win, pixelproc, mask);
else scanline(y, &r, &l, win, pixelproc, mask);
y++;
increment(&l, &dl, mask);
increment(&r, &dr, mask);
}
}
}
/* scanline: output scanline by sampling polygon at Y=y+.5 */
static scanline(y, l, r, win, pixelproc, mask)
int y, mask;
Poly_vert *l, *r;
Window *win;
void (*pixelproc)();
{
int x, lx, rx;
Poly_vert p, dp;
mask &= ~POLY_MASK(sx); /* stop interpolating screen x */
lx = ceil(l->sx-.5);
if (lx
rx = floor(r->sx-.5);
if (rx>win->x1) rx = win->x1;
if (lx>rx) return;
incrementalize_x(l, r, &p, &dp, lx, mask);
for (x=lx; x<=rx; x++) { /* scan in x, generating pixels */
(*pixelproc)(x, y, &p);
increment(&p, &dp, mask);
}
}
/*
* incrementalize_y: put intersection of line Y=y+.5 with edge between points
* p1 and p2 in p, put change with respect to y in dp
*/
static incrementalize_y(p1, p2, p, dp, y, mask)
register double *p1, *p2, *p, *dp;
register int mask;
int y;
{
double dy, frac;
dy = ((Poly_vert *)p2)->sy - ((Poly_vert *)p1)->sy;
if (dy==0.) dy = 1.;
frac = y+.5 - ((Poly_vert *)p1)->sy;
for (; mask!=0; mask>>=1, p1++, p2++, p++, dp++)
if (mask&1) {
*dp = (*p2-*p1)/dy;
*p = *p1+*dp*frac;
}
}
/*
* incrementalize_x: put intersection of line X=x+.5 with edge between points
* p1 and p2 in p, put change with respect to x in dp
*/
static incrementalize_x(p1, p2, p, dp, x, mask)
register double *p1, *p2, *p, *dp;
register int mask;
int x;
{
double dx, frac;
dx = ((Poly_vert *)p2)->sx - ((Poly_vert *)p1)->sx;
if (dx==0.) dx = 1.;
frac = x+.5 - ((Poly_vert *)p1)->sx;
for (; mask!=0; mask>>=1, p1++, p2++, p++, dp++)
if (mask&1) {
*dp = (*p2-*p1)/dx;
*p = *p1+*dp*frac;
}
}
static increment(p, dp, mask)
register double *p, *dp;
register int mask;
{
for (; mask!=0; mask>>=1, p++, dp++)
if (mask&1)
*p += *dp;
}
Very nice! Thank you for this wonderful archive. I wonder why I found it only now. Long live the BBS file archives!
This is so awesome! 😀 I’d be cool if you could download an entire archive of this at once, though.
But one thing that puzzles me is the “mtswslnkmcjklsdlsbdmMICROSOFT” string. There is an article about it here. It is definitely worth a read: http://www.os2museum.com/wp/mtswslnk/