home *** CD-ROM | disk | FTP | other *** search
/ Stars of Shareware: Raytrace & Morphing / SOS-RAYTRACE.ISO / programm / rad386 / radiosit / src / poly_cli.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-04-21  |  4.3 KB  |  135 lines
  1. /*
  2.  * Generic Convex Polygon Scan Conversion and Clipping
  3.  * by Paul Heckbert
  4.  * from "Graphics Gems", Academic Press, 1990
  5.  */
  6.  
  7. /*
  8.  * poly_clip.c: homogeneous 3-D convex polygon clipper
  9.  *
  10.  * Paul Heckbert    1985, Dec 1989
  11.  */
  12.  
  13. #include "poly.h"
  14.  
  15. #ifndef bcopy
  16. #define bcopy    memcpy
  17. #endif
  18.  
  19. #define SWAP(a, b, temp)    {temp = a; a = b; b = temp;}
  20. #define COORD(vert, i) ((double *)(vert))[i]
  21.  
  22. #define CLIP_AND_SWAP(elem, sign, k, p, q, r) { \
  23.     poly_clip_to_halfspace(p, q, &v->elem-(double *)v, sign, sign*k); \
  24.     if (q->n==0) {p1->n = 0; return POLY_CLIP_OUT;} \
  25.     SWAP(p, q, r); \
  26. }
  27.  
  28. /*
  29.  * poly_clip_to_box: Clip the convex polygon p1 to the screen space box
  30.  * using the homogeneous screen coordinates (sx, sy, sz, sw) of each vertex,
  31.  * testing if v->sx/v->sw > box->x0 and v->sx/v->sw < box->x1,
  32.  * and similar tests for y and z, for each vertex v of the polygon.
  33.  * If polygon is entirely inside box, then POLY_CLIP_IN is returned.
  34.  * If polygon is entirely outside box, then POLY_CLIP_OUT is returned.
  35.  * Otherwise, if the polygon is cut by the box, p1 is modified and
  36.  * POLY_CLIP_PARTIAL is returned.
  37.  */
  38.  
  39. int poly_clip_to_box(p1, box)
  40. register Poly *p1;
  41. register Poly_box *box;
  42. {
  43.     int x0out = 0, x1out = 0, y0out = 0, y1out = 0, z0out = 0, z1out = 0;
  44.     register int i;
  45.     register Poly_vert *v;
  46.     Poly p2, *p, *q, *r;
  47.  
  48.     /* count vertices "outside" with respect to each of the six planes */
  49.     for (v=p1->vert, i=p1->n; i>0; i--, v++) {
  50.     if (v->sx < box->x0*v->sw) x0out++;    /* out on left */
  51.     if (v->sx > box->x1*v->sw) x1out++;    /* out on right */
  52.     if (v->sy < box->y0*v->sw) y0out++;    /* out on top */
  53.     if (v->sy > box->y1*v->sw) y1out++;    /* out on bottom */
  54.     if (v->sz < box->z0*v->sw) z0out++;    /* out on near */
  55.     if (v->sz > box->z1*v->sw) z1out++;    /* out on far */
  56.     }
  57.  
  58.     /* check if all vertices inside */
  59.     if (x0out+x1out+y0out+y1out+z0out+z1out == 0) return POLY_CLIP_IN;
  60.  
  61.     /* check if all vertices are "outside" any of the six planes */
  62.     if (x0out==p1->n || x1out==p1->n || y0out==p1->n ||
  63.     y1out==p1->n || z0out==p1->n || z1out==p1->n) {
  64.         p1->n = 0;
  65.         return POLY_CLIP_OUT;
  66.     }
  67.  
  68.     /*
  69.      * now clip against each of the planes that might cut the polygon,
  70.      * at each step toggling between polygons p1 and p2
  71.      */
  72.     p = p1;
  73.     q = &p2;
  74.     if (x0out) CLIP_AND_SWAP(sx, -1., box->x0, p, q, r);
  75.     if (x1out) CLIP_AND_SWAP(sx,  1., box->x1, p, q, r);
  76.     if (y0out) CLIP_AND_SWAP(sy, -1., box->y0, p, q, r);
  77.     if (y1out) CLIP_AND_SWAP(sy,  1., box->y1, p, q, r);
  78.     if (z0out) CLIP_AND_SWAP(sz, -1., box->z0, p, q, r);
  79.     if (z1out) CLIP_AND_SWAP(sz,  1., box->z1, p, q, r);
  80.  
  81.     /* if result ended up in p2 then copy it to p1 */
  82.     if (p==&p2)
  83.     bcopy(&p2, p1, sizeof(Poly)-(POLY_NMAX-p2.n)*sizeof(Poly_vert));
  84.     return POLY_CLIP_PARTIAL;
  85. }
  86.  
  87. /*
  88.  * poly_clip_to_halfspace: clip convex polygon p against a plane,
  89.  * copying the portion satisfying sign*s[index] < k*sw into q,
  90.  * where s is a Poly_vert* cast as a double*.
  91.  * index is an index into the array of doubles at each vertex, such that
  92.  * s[index] is sx, sy, or sz (screen space x, y, or z).
  93.  * Thus, to clip against xmin, use
  94.  *    poly_clip_to_halfspace(p, q, XINDEX, -1., -xmin);
  95.  * and to clip against xmax, use
  96.  *    poly_clip_to_halfspace(p, q, XINDEX,  1.,  xmax);
  97.  */
  98.  
  99. void poly_clip_to_halfspace(p, q, index, sign, k)
  100. Poly *p, *q;
  101. register int index;
  102. double sign, k;
  103. {
  104.     register int m;
  105.     register double *up, *vp, *wp;
  106.     register Poly_vert *v;
  107.     int i;
  108.     Poly_vert *u;
  109.     double t, tu, tv;
  110.  
  111.     q->n = 0;
  112.     q->mask = p->mask;
  113.  
  114.     /* start with u=vert[n-1], v=vert[0] */
  115.     u = &p->vert[p->n-1];
  116.     tu = sign*COORD(u, index) - u->sw*k;
  117.     for (v= &p->vert[0], i=p->n; i>0; i--, u=v, tu=tv, v++) {
  118.     /* on old polygon (p), u is previous vertex, v is current vertex */
  119.     /* tv is negative if vertex v is in */
  120.     tv = sign*COORD(v, index) - v->sw*k;
  121.     if (tu<=0. ^ tv<=0.) {
  122.         /* edge crosses plane; add intersection point to q */
  123.         t = tu/(tu-tv);
  124.         up = (double *)u;
  125.         vp = (double *)v;
  126.         wp = (double *)&q->vert[q->n];
  127.         for (m=p->mask; m!=0; m>>=1, up++, vp++, wp++)
  128.         if (m&1) *wp = *up+t*(*vp-*up);
  129.         q->n++;
  130.     }
  131.     if (tv<=0.)        /* vertex v is in, copy it to q */
  132.         q->vert[q->n++] = *v;
  133.     }
  134. }
  135.