From: ph+@cs.cmu.edu (Paul Heckbert)
Subject: Re: Help with perspective texture mapping on polygons, please help
Organization: School of Computer Science, Carnegie Mellon
Date: Tue, 13 Oct 1992 19:11:01 GMT

In article <718762533snx@rjck.UUCP> rob@rjck.UUCP (Robert J.C. Kyanko) writes:
> I am trying to write a program which will do correct perspective texture
> mapping onto polygons.  ... I'm hung on how to determine the
> homogeneous 'W' from the four corners of my quadrilateral.

I can answer this by re-posting something I put on comp.graphics a year ago.

---

From: witiph@dutiws.tudelft.nl [OBSOLETE ADDRESS] (Paul Heckbert)
Newsgroups: comp.graphics
Subject: Re: Texture Mapping Triangles in Perspective
Date: 27 Nov 91 10:35:40 GMT [REVISED 13 Oct 92]
Organization: T W I, Delft University of Technology

Previously, jason@monet.uwaterloo.ca (Jason Fischl) writes:
>
> I'm trying to implement a system which will texture map an image
> onto a triangular mesh and display it in perspective.
> Initially what I've done is to linearly interpolate the texture
> coordinates u,v along the sides of each triangle and then across
> each scan line. ...
> Unfortunately this causes problems with the perpsective.  So my question
> is, what is a good quick implementation of a better way of doing it.  
> How can I find an inverse mapping from (x,y) screen space onto
> (u,v) texture space in my specific case where the polygons are triangles. 
> Also, is there any code out there for doing texture mapping?

See the chapter called "Generic Convex Polygon Scan Conversion and Clipping"
that I wrote for the book "Graphics Gems".  It gives skeleton C code for
scan converting convex polygons with texture mapping (and Gouraud
and Phong shading) and other things.  Here's a summary of the relevant
ideas to your problem:

Assuming that you're using a perspective projection, and your polygons are
parameterized affinely in world space (that is, world space x, y, and z
can each be written in the form A*u+B*v+C) then instead of interpolating
u and v linearly, you should be using what I call "rational linear
interpolation": linear interpolation of a numerator and denominator,

where
	u = unum/den
	v = vnum/den

and unum, vnum, and den have the form:

	unum = a*x + b*y + c
	vnum = d*x + e*y + f
	den  = g*x + h*y + i

(where x, y, and z here denote screen space).
Instead of linearly interpolating u and v across the polygon, you linearly
interpolate these three quantities, unum, vnum, and den along polygon
edges and across the scanline, then do the two indicated divisions to
compute u and v.

The only question remaining is: how do you compute unum, vnum, and den
initially at the polygon vertices?  That turns out to be quite simple.
At some stage in your software you probably already transform an object
space homogeneous point (xo, yo, zo, 1) to homogeneous screen space
yielding (xw, yw, zw, w), then do clipping, then do a homogeneous
divide, and then scan convert.  The only additional work needed to
compute texture parameters is, before discarding w, compute

	unum = u/w
	vnum = v/w
	den = 1/w

at each vertex.  With these formulas, you should be off and running.

The above method is used in the C code I put in the Graphics
Gems book, and is also discussed in detail in a recent paper with Henry
Moreton, who pointed out the simple divide-by-w formula, and in my
Master's thesis.  You can get the C code (along with other source
from the book "Graphics Gems") by anonymous ftp from princeton.edu
with the following:

	ftp princeton.edu
	LOGIN: anonymous
	PASSWORD: dumpbush
	cd pub/Graphics/GraphicsGems/Gems/src
	binary
	mget README P*
	...
	quit
	more README

and if "ftp princeton.edu" doesn't work, try "ftp 128.112.128.1".
[  The password "dumpbush" is critical; nothing will happen otherwise :-)  ]

An aside: when is linear interpolation of attributes appropriate?  It
is only appropriate when the mapping between screen space x,y and the
attribute is affine (linear plus a constant).  Incidentally, linear
interpolation for Gouraud and Phong shading on polygons with more than
three sides gives results that are, in general, not rotation-invariant,
so in this sense linear interpolation is not ``correct'' for those
purposes.  The errors caused by linear-interpolated Gouraud and Phong
shading are invisible in most images, however, unlike the errors of
linear-interpolated perspective texture coordinates, which typically
cause a distracting ``rubber sheet'' effect.

References in UNIX "refer" format:

    %A Paul S. Heckbert
    %T Generic Convex Polygon Scan Conversion and Clipping
    %E Andrew Glassner
    %B Graphics Gems
    %I Academic Press
    %C Boston
    %D 1990
    %P 84-86, 667-680
    %K polygon, render, texture mapping, clip

    %A Paul S. Heckbert
    %A Henry P. Moreton
    %T Interpolation for Polygon Texture Mapping and Shading
    %B State of the Art in Computer Graphics: Visualization and Modeling
    %E David F. Rogers
    %E Rae A. Earnshaw
    %I Springer-Verlag
    %C New York
    %D 1991
    %P 101-111
    %K perspective, scan conversion

    %A Mark Segal
    %A Carl Korobkin
    %A Rolf van Widenfelt
    %A Jim Foran
    %A Paul Haeberli
    %T Fast Shadows and Lighting Effects using Texture Mapping
    %J Computer Graphics
    (SIGGRAPH '92 Proceedings)
    %V 26
    %N 2
    %D July 1992
    %P 249-252
    %K perspective, scan conversion

    %A Paul S. Heckbert
    %T Fundamentals of Texture Mapping and Image Warping
    %R Master's thesis, UCB/CSD 89/516
    %I CS Division, EECS Dept, UC Berkeley
    %D May 1989

---

-Paul

Paul Heckbert						    ph@cs.cmu.edu
Computer Science Dept., Carnegie Mellon University
5000 Forbes Ave, Pittsburgh PA 15213-3891, USA

In case you don't have ftp access, here's some C code:

---

The general method for using these routines is: load data into the ver-
tices, set the polygon's mask to indicate which attributes are in use, call
the clipper, modify the vertex attributes (typically a homogeneous divide),
set the polygon's mask to indicate which attributes are still in use, call
the scan converter, supplying a callback procedure that is called by
poly_scan at each pixel, and in the pixel routine, unload data from the
interpolated point, using it to draw into a raster image.

There are four files of generic code:

     poly.h       Polygon data structure.

     poly.c       Utility subroutines to print polygons.

     poly_scan.c  Scan convert a convex, planar polygon by uniform sampling
                  at pixel centers.

     poly_clip.c  Clip a convex, planar polygon to a screen space paral-
                  lelepiped.

and two files giving simple examples of their use:

     scantest.c   Gouraud shading with z-buffer using poly_scan.

     fancytest.c  Phong shading and texture mapping using poly_clip and
                  poly_scan.


You can change anything in the Poly_vert structure definition except the
screen space position fields sx, sy, sz, and sw, which are required by
poly_scan and poly_clip.  All fields of Poly_vert should be doubles.  Note
that incorrect settings of the interpolation mask can result in meaningless
attribute values or wasted compute time.  For C environments that don't
have the bcopy routine, use '#define bcopy(from, to, nbytes) memcpy(to,
from, nbytes)'.

---

# to unpack, cut here and run the following shell archive through sh
# contents: Makefile poly.h scantest.c fancytest.c poly_scan.c
# poly_clip.c poly.c
#
echo extracting Makefile
sed 's/^_//' <<'EOF15037' >Makefile
_# Makefile for scantest, test program for generic convex polygon scan conversion
_#
_# Note: fancytest.c needs a main routine and several auxiliary routines
_# in order to be compiled.
_
_CFLAGS = $(GENCFLAGS)
_
_scantest: scantest.o poly_scan.o poly.o
_	$(CC) $(CFLAGS) -o scantest scantest.o poly_scan.o poly.o -lm
_
_clean:
_	/bin/rm -f scantest.o poly_clip.o poly_scan.o poly.o scantest
EOF15037
echo extracting poly.h
sed 's/^_//' <<'EOF15038' >poly.h
_/* poly.h: definitions for polygon package */
_
_#ifndef POLY_HDR
_#define POLY_HDR
_
_#define POLY_NMAX 8		/* max #sides to a polygon; change if needed */
_
_typedef struct {		/* A POLYGON VERTEX */
_    double sx, sy, sz, sw;	/* screen space position (sometimes homo.) */
_    double x, y, z;		/* world space position */
_    double u, v, q;		/* texture position (sometimes homogeneous) */
_    double r, g, b;		/* (red,green,blue) color */
_    double nx, ny, nz;		/* world space normal vector */
_} Poly_vert;
_/* update poly.c if you change this structure */
_
_typedef struct {		/* A POLYGON */
_    int n;			/* number of sides */
_    int mask;			/* interpolation mask for vertex elems */
_    Poly_vert vert[POLY_NMAX];	/* vertices */
_} Poly;
_/*
_ * mask is an interpolation mask whose kth bit indicates whether the kth
_ * double in a Poly_vert is relevant.
_ * For example, if the valid attributes are sx, sy, and sz, then set
_ *	mask = POLY_MASK(sx) | POLY_MASK(sy) | POLY_MASK(sz);
_ */
_
_typedef struct {		/* A BOX (TYPICALLY IN SCREEN SPACE) */
_    double x0, x1;		/* left and right */
_    double y0, y1;		/* top and bottom */
_    double z0, z1;		/* near and far */
_} Poly_box;
_
_typedef struct {		/* WINDOW: A DISCRETE 2-D RECTANGLE */
_    int x0, y0;			/* xmin and ymin */
_    int x1, y1;			/* xmax and ymax (inclusive) */
_} Window;
_
_#define POLY_MASK(elem) (1 << (&poly_dummy->elem - (double *)poly_dummy))
_
_#define POLY_CLIP_OUT 0		/* polygon entirely outside box */
_#define POLY_CLIP_PARTIAL 1	/* polygon partially inside */
_#define POLY_CLIP_IN 2		/* polygon entirely inside box */
_
_extern Poly_vert *poly_dummy;	/* used superficially by POLY_MASK macro */
_
_void	poly_print(/* str, p */);
_void	poly_vert_label(/* str, mask */);
_void	poly_vert_print(/* str, v, mask */);
_int	poly_clip_to_box(/* p1, box */);
_void	poly_clip_to_halfspace(/* p, q, index, sign, k, name */);
_void	poly_scan(/* p, win, pixelproc */);
_
_#endif
EOF15038
echo extracting scantest.c
sed 's/^_//' <<'EOF15039' >scantest.c
_/*
_ * scantest.c: use poly_scan() for Gouraud shading and z-buffer demo.
_ * Given the screen space X, Y, and Z of N-gon on command line,
_ * print out all pixels during scan conversion.
_ * This code could easily be modified to actually read and write pixels.
_ *
_ * Paul Heckbert	Dec 1989
_ */
_
_#include <stdio.h>
_#include <math.h>
_#include "poly.h"
_
_#define XMAX 1280	/* hypothetical image width */
_#define YMAX 1024	/* hypothetical image height */
_
_#define FRANDOM() ((rand()&32767)/32767.)   /* random number between 0 and 1 */
_
_static void pixelproc();
_
_main(ac, av)
_int ac;
_char **av;
_{
_    int i;
_    Poly p;
_    static Window win = {0, 0, XMAX-1, YMAX-1};	/* screen clipping window */
_
_    if (ac<2 || ac != 2+3*(p.n = atoi(av[1]))) {
_	fprintf(stderr, "Usage: scantest N X1 Y1 Z1 X2 Y2 Z2 ... XN YN ZN\n");
_	exit(1);
_    }
_    for (i=0; i<p.n; i++) {
_	p.vert[i].sx = atof(av[2+3*i]);	/* set screen space x,y,z */
_	p.vert[i].sy = atof(av[3+3*i]);
_	p.vert[i].sz = atof(av[4+3*i]);
_	p.vert[i].r = FRANDOM();	/* random vertex colors, for kicks */
_	p.vert[i].g = FRANDOM();
_	p.vert[i].b = FRANDOM();
_    }
_    /* interpolate sx, sy, sz, r, g, and b in poly_scan */
_    p.mask = POLY_MASK(sx) | POLY_MASK(sy) | POLY_MASK(sz) |
_	POLY_MASK(r) | POLY_MASK(g) | POLY_MASK(b);
_
_    poly_print("scan converting the polygon", &p);
_    
_    poly_scan(&p, &win, pixelproc);	/* scan convert! */
_}
_
_static void pixelproc(x, y, point)	/* called at each pixel by poly_scan */
_int x, y;
_Poly_vert *point;
_{
_    printf("pixel (%d,%d) screenz=%g rgb=(%g,%g,%g)\n",
_	x, y, point->sz, point->r, point->g, point->b);
_
_    /*
_     * in real graphics program you could read and write pixels, e.g.:
_     *
_     *	if (point->sz < zbuffer_read(x, y)) {
_     *	    image_write_rgb(x, y, point->r, point->g, point->b);
_     *	    zbuffer_write(x, y, point->sz);
_     *  }
_     */
_}
EOF15039
echo extracting fancytest.c
sed 's/^_//' <<'EOF15040' >fancytest.c
_/*
_ * fancytest.c: subroutine illustrating the use of poly_clip and poly_scan
_ * for Phong-shading and texture mapping.
_ *
_ * Note: lines enclosed in angle brackets '<', '>' should be replaced
_ * with the code described.
_ * Makes calls to hypothetical packages "shade", "image", "texture", "zbuffer".
_ *
_ * Paul Heckbert	Dec 1989
_ */
_
_#include <stdio.h>
_#include <math.h>
_#include "poly.h"
_
_#define XMAX 1280	/* hypothetical image width */
_#define YMAX 1024	/* hypothetical image height */
_#define LIGHT_INTEN 255		/* light source intensity */
_
_void pixelproc();
_
_fancytest()
_{
_    int i;
_    double WS[4][4];	/* world space to screen space transform */
_    Poly p;		/* a polygon */
_    Poly_vert *v;
_
_    static Poly_box box = {0, XMAX, 0, YMAX, -32678, 32767.99};
_	/* 3-D screen clipping box, continuous coordinates */
_
_    static Window win = {0, 0, XMAX-1, YMAX-1};
_	/* 2-D screen clipping window, discrete coordinates */
_
_    <initialize world space position (x,y,z), normal (nx,ny,nz), and texture
_     position (u,v) at each vertex of p; set p.n>
_    <set WS to world-to-screen transform>
_
_    /* transform vertices from world space to homogeneous screen space */
_    for (i=0; i<p.n; i++) {
_	v = &p.vert[i];
_	mx4_transform(v->x, v->y, v->z, 1., WS, &v->sx, &v->sy, &v->sz, &v->sw);
_    }
_
_    /* interpolate sx, sy, sz, sw, nx, ny, nz, u, v in poly_clip */
_    p.mask = POLY_MASK(sx) | POLY_MASK(sy) | POLY_MASK(sz) | POLY_MASK(sw) |
_	POLY_MASK(nx) | POLY_MASK(ny) | POLY_MASK(nz) |
_	POLY_MASK(u) | POLY_MASK(v);
_
_    poly_print("before clipping", &p);
_    if (poly_clip_to_box(&p, &box) == POLY_CLIP_OUT)	/* clip polygon */
_	return;						/* quit if off-screen */
_
_    /* do homogeneous division of screen position and texture position */
_    for (i=0; i<p.n; i++) {
_	v = &p.vert[i];
_	v->sx /= v->sw;
_	v->sy /= v->sw;
_	v->sz /= v->sw;
_	v->u /= v->sw;
_	v->v /= v->sw;
_	v->q = 1./v->sw;
_    }
_    /*
_     * previously we ignored q (assumed q=1), henceforth ignore sw (assume sw=1)
_     * Interpolate sx, sy, sz, nx, ny, nz, u, v, q in poly_scan
_     */
_    p.mask &= ~POLY_MASK(sw);
_    p.mask |= POLY_MASK(q);
_
_    poly_print("scan converting the polygon", &p);
_    poly_scan(&p, &win, pixelproc);	/* scan convert! */
_}
_
_static void pixelproc(x, y, pt)		/* called at each pixel by poly_scan */
_int x, y;
_Poly_vert *pt;
_{
_    int sz, u, v, inten;
_    double len, nor[3], diff, spec;
_
_    sz = pt->sz;
_    if (sz < zbuffer_read(x, y)) {
_	len = sqrt(pt->nx*pt->nx + pt->ny*pt->ny + pt->nz*pt->nz);
_	nor[0] = pt->nx/len;		/* unitize the normal vector */
_	nor[1] = pt->ny/len;
_	nor[2] = pt->nz/len;
_	shade(nor, &diff, &spec);	/* compute specular and diffuse coeffs*/
_	u = pt->u/pt->q;		/* do homogeneous div. of texture pos */
_	v = pt->v/pt->q;
_	inten = texture_read(u, v)*diff + LIGHT_INTEN*spec;
_	image_write(x, y, inten);
_	zbuffer_write(x, y, sz);
_    }
_}
_
_/* mx4_transform: transform 4-vector p by matrix m yielding q: q = p*m */
_
_mx4_transform(px, py, pz, pw, m, qxp, qyp, qzp, qwp)
_double px, py, pz, pw, m[4][4], *qxp, *qyp, *qzp, *qwp;
_{
_    *qxp = px*m[0][0] + py*m[1][0] + pz*m[2][0] + pw*m[3][0];
_    *qyp = px*m[0][1] + py*m[1][1] + pz*m[2][1] + pw*m[3][1];
_    *qzp = px*m[0][2] + py*m[1][2] + pz*m[2][2] + pw*m[3][2];
_    *qwp = px*m[0][3] + py*m[1][3] + pz*m[2][3] + pw*m[3][3];
_}
EOF15040
echo extracting poly_scan.c
sed 's/^_//' <<'EOF15041' >poly_scan.c
_/*
_ * 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 <stdio.h>
_#include <math.h>
_#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<p->n; i++)		/* find top vertex (y points down) */
_	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<ly && y<ry) {	    /* do scanlines till end of l or r edge */
_	    if (y>=win->y0 && y<=win->y1)
_		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<win->x0) lx = win->x0;
_    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;
_}
EOF15041
echo extracting poly_clip.c
sed 's/^_//' <<'EOF15042' >poly_clip.c
_/*
_ * Generic Convex Polygon Scan Conversion and Clipping
_ * by Paul Heckbert
_ * from "Graphics Gems", Academic Press, 1990
_ */
_
_/*
_ * poly_clip.c: homogeneous 3-D convex polygon clipper
_ *
_ * Paul Heckbert	1985, Dec 1989
_ */
_
_#include "poly.h"
_
_#define SWAP(a, b, temp)	{temp = a; a = b; b = temp;}
_#define COORD(vert, i) ((double *)(vert))[i]
_
_#define CLIP_AND_SWAP(elem, sign, k, p, q, r) { \
_    poly_clip_to_halfspace(p, q, &v->elem-(double *)v, sign, sign*k); \
_    if (q->n==0) {p1->n = 0; return POLY_CLIP_OUT;} \
_    SWAP(p, q, r); \
_}
_
_/*
_ * poly_clip_to_box: Clip the convex polygon p1 to the screen space box
_ * using the homogeneous screen coordinates (sx, sy, sz, sw) of each vertex,
_ * testing if v->sx/v->sw > box->x0 and v->sx/v->sw < box->x1,
_ * and similar tests for y and z, for each vertex v of the polygon.
_ * If polygon is entirely inside box, then POLY_CLIP_IN is returned.
_ * If polygon is entirely outside box, then POLY_CLIP_OUT is returned.
_ * Otherwise, if the polygon is cut by the box, p1 is modified and
_ * POLY_CLIP_PARTIAL is returned.
_ */
_
_int poly_clip_to_box(p1, box)
_register Poly *p1;
_register Poly_box *box;
_{
_    int x0out = 0, x1out = 0, y0out = 0, y1out = 0, z0out = 0, z1out = 0;
_    register int i;
_    register Poly_vert *v;
_    Poly p2, *p, *q, *r;
_
_    /* count vertices "outside" with respect to each of the six planes */
_    for (v=p1->vert, i=p1->n; i>0; i--, v++) {
_	if (v->sx < box->x0*v->sw) x0out++;	/* out on left */
_	if (v->sx > box->x1*v->sw) x1out++;	/* out on right */
_	if (v->sy < box->y0*v->sw) y0out++;	/* out on top */
_	if (v->sy > box->y1*v->sw) y1out++;	/* out on bottom */
_	if (v->sz < box->z0*v->sw) z0out++;	/* out on near */
_	if (v->sz > box->z1*v->sw) z1out++;	/* out on far */
_    }
_
_    /* check if all vertices inside */
_    if (x0out+x1out+y0out+y1out+z0out+z1out == 0) return POLY_CLIP_IN;
_
_    /* check if all vertices are "outside" any of the six planes */
_    if (x0out==p1->n || x1out==p1->n || y0out==p1->n ||
_	y1out==p1->n || z0out==p1->n || z1out==p1->n) {
_	    p1->n = 0;
_	    return POLY_CLIP_OUT;
_	}
_
_    /*
_     * now clip against each of the planes that might cut the polygon,
_     * at each step toggling between polygons p1 and p2
_     */
_    p = p1;
_    q = &p2;
_    if (x0out) CLIP_AND_SWAP(sx, -1., box->x0, p, q, r);
_    if (x1out) CLIP_AND_SWAP(sx,  1., box->x1, p, q, r);
_    if (y0out) CLIP_AND_SWAP(sy, -1., box->y0, p, q, r);
_    if (y1out) CLIP_AND_SWAP(sy,  1., box->y1, p, q, r);
_    if (z0out) CLIP_AND_SWAP(sz, -1., box->z0, p, q, r);
_    if (z1out) CLIP_AND_SWAP(sz,  1., box->z1, p, q, r);
_
_    /* if result ended up in p2 then copy it to p1 */
_    if (p==&p2)
_	bcopy(&p2, p1, sizeof(Poly)-(POLY_NMAX-p2.n)*sizeof(Poly_vert));
_    return POLY_CLIP_PARTIAL;
_}
_
_/*
_ * poly_clip_to_halfspace: clip convex polygon p against a plane,
_ * copying the portion satisfying sign*s[index] < k*sw into q,
_ * where s is a Poly_vert* cast as a double*.
_ * index is an index into the array of doubles at each vertex, such that
_ * s[index] is sx, sy, or sz (screen space x, y, or z).
_ * Thus, to clip against xmin, use
_ *	poly_clip_to_halfspace(p, q, XINDEX, -1., -xmin);
_ * and to clip against xmax, use
_ *	poly_clip_to_halfspace(p, q, XINDEX,  1.,  xmax);
_ */
_
_void poly_clip_to_halfspace(p, q, index, sign, k)
_Poly *p, *q;
_register int index;
_double sign, k;
_{
_    register int m;
_    register double *up, *vp, *wp;
_    register Poly_vert *v;
_    int i;
_    Poly_vert *u;
_    double t, tu, tv;
_
_    q->n = 0;
_    q->mask = p->mask;
_
_    /* start with u=vert[n-1], v=vert[0] */
_    u = &p->vert[p->n-1];
_    tu = sign*COORD(u, index) - u->sw*k;
_    for (v= &p->vert[0], i=p->n; i>0; i--, u=v, tu=tv, v++) {
_	/* on old polygon (p), u is previous vertex, v is current vertex */
_	/* tv is negative if vertex v is in */
_	tv = sign*COORD(v, index) - v->sw*k;
_	if (tu<=0. ^ tv<=0.) {
_	    /* edge crosses plane; add intersection point to q */
_	    t = tu/(tu-tv);
_	    up = (double *)u;
_	    vp = (double *)v;
_	    wp = (double *)&q->vert[q->n];
_	    for (m=p->mask; m!=0; m>>=1, up++, vp++, wp++)
_		if (m&1) *wp = *up+t*(*vp-*up);
_	    q->n++;
_	}
_	if (tv<=0.)		/* vertex v is in, copy it to q */
_	    q->vert[q->n++] = *v;
_    }
_}
EOF15042
echo extracting poly.c
sed 's/^_//' <<'EOF15043' >poly.c
_/*
_ * poly.c: simple utilities for polygon data structures
_ */
_
_#include "poly.h"
_
_Poly_vert *poly_dummy;		/* used superficially by POLY_MASK macro */
_
_/*
_ * poly_print: print Poly p to stdout, prefixed by the label str
_ */
_
_void poly_print(str, p)
_char *str;
_Poly *p;
_{
_    int i;
_
_    printf("%s: %d sides\n", str, p->n);
_    poly_vert_label("        ", p->mask);
_    for (i=0; i<p->n; i++) {
_	printf("   v[%d] ", i);
_	poly_vert_print("", &p->vert[i], p->mask);
_    }
_}
_
_void poly_vert_label(str, mask)
_char *str;
_int mask;
_{
_    printf("%s", str);
_    if (mask&POLY_MASK(sx))   printf("   sx  ");
_    if (mask&POLY_MASK(sy))   printf("   sy  ");
_    if (mask&POLY_MASK(sz))   printf("   sz  ");
_    if (mask&POLY_MASK(sw))   printf("   sw  ");
_    if (mask&POLY_MASK(x))    printf("   x   ");
_    if (mask&POLY_MASK(y))    printf("   y   ");
_    if (mask&POLY_MASK(z))    printf("   z   ");
_    if (mask&POLY_MASK(u))    printf("   u   ");
_    if (mask&POLY_MASK(v))    printf("   v   ");
_    if (mask&POLY_MASK(q))    printf("   q   ");
_    if (mask&POLY_MASK(r))    printf("   r   ");
_    if (mask&POLY_MASK(g))    printf("   g   ");
_    if (mask&POLY_MASK(b))    printf("   b   ");
_    if (mask&POLY_MASK(nx))   printf("   nx  ");
_    if (mask&POLY_MASK(ny))   printf("   ny  ");
_    if (mask&POLY_MASK(nz))   printf("   nz  ");
_    printf("\n");
_}
_
_void poly_vert_print(str, v, mask)
_char *str;
_Poly_vert *v;
_int mask;
_{
_    printf("%s", str);
_    if (mask&POLY_MASK(sx)) printf(" %6.1f", v->sx);
_    if (mask&POLY_MASK(sy)) printf(" %6.1f", v->sy);
_    if (mask&POLY_MASK(sz)) printf(" %6.2f", v->sz);
_    if (mask&POLY_MASK(sw)) printf(" %6.2f", v->sw);
_    if (mask&POLY_MASK(x))  printf(" %6.2f", v->x);
_    if (mask&POLY_MASK(y))  printf(" %6.2f", v->y);
_    if (mask&POLY_MASK(z))  printf(" %6.2f", v->z);
_    if (mask&POLY_MASK(u))  printf(" %6.2f", v->u);
_    if (mask&POLY_MASK(v))  printf(" %6.2f", v->v);
_    if (mask&POLY_MASK(q))  printf(" %6.2f", v->q);
_    if (mask&POLY_MASK(r))  printf(" %6.4f", v->r);
_    if (mask&POLY_MASK(g))  printf(" %6.4f", v->g);
_    if (mask&POLY_MASK(b))  printf(" %6.4f", v->b);
_    if (mask&POLY_MASK(nx)) printf(" %6.3f", v->nx);
_    if (mask&POLY_MASK(ny)) printf(" %6.3f", v->ny);
_    if (mask&POLY_MASK(nz)) printf(" %6.3f", v->nz);
_    printf("\n");
_}
EOF15043
exit
Newsgroups: comp.graphics
From: andy@osea.demon.co.uk (Andrew Haveland-Robinson)