git.mutantstargoat.com Git - dosrtxon/blob - src/polyclip.c

   1 #include <stdio.h>
   2 #include <math.h>
   3 #include <assert.h>
   4 #include "polyclip.h"
   5
   6 struct ray {
   7         float origin[3];
   8         float dir[3];
   9 };
  10
  11 static int clip_edge(struct g3d_vertex *poly, int *vnumptr,
  12                 const struct g3d_vertex *v0, const struct g3d_vertex *v1,
  13                 const struct cplane *plane);
  14 static int clip_edge_frustum(struct g3d_vertex *poly, int *vnumptr,
  15                 const struct g3d_vertex *v0, const struct g3d_vertex *v1, int fplane);
  16 static float distance_signed(float *pos, const struct cplane *plane);
  17 static int intersect(const struct ray *ray, const struct cplane *plane, float *t);
  18 static int inside_frustum_plane(const struct g3d_vertex *v, int fplane);
  19
  20
  21 int clip_poly(struct g3d_vertex *vout, int *voutnum,
  22                 const struct g3d_vertex *vin, int vnum, struct cplane *plane)
  23 {
  24         int i, nextidx, res;
  25         int edges_clipped = 0;
  26
  27         *voutnum = 0;
  28
  29         for(i=0; i<vnum; i++) {
  30                 nextidx = i + 1;
  31                 if(nextidx >= vnum) nextidx = 0;
  32                 res = clip_edge(vout, voutnum, vin + i, vin + nextidx, plane);
  33                 if(res == 0) {
  34                         ++edges_clipped;
  35                 }
  36         }
  37
  38         if(*voutnum <= 0) {
  39                 assert(edges_clipped == 0);
  40                 return -1;
  41         }
  42
  43         return edges_clipped > 0 ? 0 : 1;
  44 }
  45
  46
  47 int clip_frustum(struct g3d_vertex *vout, int *voutnum,
  48                 const struct g3d_vertex *vin, int vnum, int fplane)
  49 {
  50         int i, nextidx, res;
  51         int edges_clipped = 0;
  52
  53         if(vnum == 1) {
  54                 /* special case: point clipping */
  55                 return inside_frustum_plane(vin, fplane) ? 1 : -1;
  56         }
  57
  58         *voutnum = 0;
  59
  60         for(i=0; i<vnum; i++) {
  61                 nextidx = i + 1;
  62                 if(nextidx >= vnum) nextidx = 0;
  63                 res = clip_edge_frustum(vout, voutnum, vin + i, vin + nextidx, fplane);
  64                 if(res == 0) {
  65                         ++edges_clipped;
  66                 }
  67         }
  68
  69         if(*voutnum <= 0) {
  70                 assert(edges_clipped == 0);
  71                 return -1;
  72         }
  73
  74         return edges_clipped > 0 ? 0 : 1;
  75 }
  76
  77 #define LERP_VATTR(res, v0, v1, t) \
  78         do { \
  79                 (res)->nx = (v0)->nx + ((v1)->nx - (v0)->nx) * (t); \
  80                 (res)->ny = (v0)->ny + ((v1)->ny - (v0)->ny) * (t); \
  81                 (res)->nz = (v0)->nz + ((v1)->nz - (v0)->nz) * (t); \
  82                 (res)->u = (v0)->u + ((v1)->u - (v0)->u) * (t); \
  83                 (res)->v = (v0)->v + ((v1)->v - (v0)->v) * (t); \
  84                 (res)->r = (v0)->r + ((v1)->r - (v0)->r) * (t); \
  85                 (res)->g = (v0)->g + ((v1)->g - (v0)->g) * (t); \
  86                 (res)->b = (v0)->b + ((v1)->b - (v0)->b) * (t); \
  87         } while(0)
  88
  89
  90 /* returns:
  91  *  1 -> both inside
  92  *  0 -> straddling and clipped
  93  * -1 -> both outside
  94  *
  95  *  also returns the size of the polygon through vnumptr
  96  */
  97 static int clip_edge(struct g3d_vertex *poly, int *vnumptr,
  98                 const struct g3d_vertex *v0, const struct g3d_vertex *v1,
  99                 const struct cplane *plane)
 100 {
 101         float pos0[3], pos1[3];
 102         float d0, d1, t;
 103         struct ray ray;
 104         int i, vnum = *vnumptr;
 105
 106         pos0[0] = v0->x; pos0[1] = v0->y; pos0[2] = v0->z;
 107         pos1[0] = v1->x; pos1[1] = v1->y; pos1[2] = v1->z;
 108
 109         d0 = distance_signed(pos0, plane);
 110         d1 = distance_signed(pos1, plane);
 111
 112         for(i=0; i<3; i++) {
 113                 ray.origin[i] = pos0[i];
 114                 ray.dir[i] = pos1[i] - pos0[i];
 115         }
 116
 117         if(d0 >= 0.0) {
 118                 /* start inside */
 119                 if(d1 >= 0.0) {
 120                         /* all inside */
 121                         poly[vnum++] = *v1;     /* append v1 */
 122                         *vnumptr = vnum;
 123                         return 1;
 124                 } else {
 125                         /* going out */
 126                         struct g3d_vertex *vptr = poly + vnum;
 127
 128                         intersect(&ray, plane, &t);
 129
 130                         vptr->x = ray.origin[0] + ray.dir[0] * t;
 131                         vptr->y = ray.origin[1] + ray.dir[1] * t;
 132                         vptr->z = ray.origin[2] + ray.dir[2] * t;
 133                         vptr->w = 1.0f;
 134
 135                         LERP_VATTR(vptr, v0, v1, t);
 136                         vnum++; /* append new vertex on the intersection point */
 137                 }
 138         } else {
 139                 /* start outside */
 140                 if(d1 >= 0) {
 141                         /* going in */
 142                         struct g3d_vertex *vptr = poly + vnum;
 143
 144                         intersect(&ray, plane, &t);
 145
 146                         vptr->x = ray.origin[0] + ray.dir[0] * t;
 147                         vptr->y = ray.origin[1] + ray.dir[1] * t;
 148                         vptr->z = ray.origin[2] + ray.dir[2] * t;
 149                         vptr->w = 1.0f;
 150
 151                         LERP_VATTR(vptr, v0, v1, t);
 152                         vnum++; /* append new vertex on the intersection point */
 153
 154                         /* then append v1 ... */
 155                         poly[vnum++] = *v1;
 156                 } else {
 157                         /* all outside */
 158                         return -1;
 159                 }
 160         }
 161
 162         *vnumptr = vnum;
 163         return 0;
 164 }
 165
 166
 167 static float distance_signed(float *pos, const struct cplane *plane)
 168 {
 169         float dx = pos[0] - plane->x;
 170         float dy = pos[1] - plane->y;
 171         float dz = pos[2] - plane->z;
 172         return dx * plane->nx + dy * plane->ny + dz * plane->nz;
 173 }
 174
 175 static int intersect(const struct ray *ray, const struct cplane *plane, float *t)
 176 {
 177         float orig_pt_dir[3];
 178
 179         float ndotdir = plane->nx * ray->dir[0] + plane->ny * ray->dir[1] + plane->nz * ray->dir[2];
 180         if(fabs(ndotdir) < 1e-6) {
 181                 *t = 0.0f;
 182                 return 0;
 183         }
 184
 185         orig_pt_dir[0] = plane->x - ray->origin[0];
 186         orig_pt_dir[1] = plane->y - ray->origin[1];
 187         orig_pt_dir[2] = plane->z - ray->origin[2];
 188
 189         *t = (plane->nx * orig_pt_dir[0] + plane->ny * orig_pt_dir[1] + plane->nz * orig_pt_dir[2]) / ndotdir;
 190         return 1;
 191 }
 192
 193 /* homogeneous frustum clipper helpers */
 194
 195 static int inside_frustum_plane(const struct g3d_vertex *v, int fplane)
 196 {
 197         switch(fplane) {
 198         case CLIP_LEFT:
 199                 return v->x >= -v->w;
 200         case CLIP_RIGHT:
 201                 return v->x <= v->w;
 202         case CLIP_BOTTOM:
 203                 return v->y >= -v->w;
 204         case CLIP_TOP:
 205                 return v->y <= v->w;
 206         case CLIP_NEAR:
 207                 return v->z >= -v->w;
 208         case CLIP_FAR:
 209                 return v->z <= v->w;
 210         }
 211         assert(0);
 212         return 0;
 213 }
 214
 215 static float intersect_frustum(const struct g3d_vertex *a, const struct g3d_vertex *b, int fplane)
 216 {
 217         switch(fplane) {
 218         case CLIP_LEFT:
 219                 return (-a->w - a->x) / (b->x - a->x + b->w - a->w);
 220         case CLIP_RIGHT:
 221                 return (a->w - a->x) / (b->x - a->x - b->w + a->w);
 222         case CLIP_BOTTOM:
 223                 return (-a->w - a->y) / (b->y - a->y + b->w - a->w);
 224         case CLIP_TOP:
 225                 return (a->w - a->y) / (b->y - a->y - b->w + a->w);
 226         case CLIP_NEAR:
 227                 return (-a->w - a->z) / (b->z - a->z + b->w - a->w);
 228         case CLIP_FAR:
 229                 return (a->w - a->z) / (b->z - a->z - b->w + a->w);
 230         }
 231
 232         assert(0);
 233         return 0;
 234 }
 235
 236 static int clip_edge_frustum(struct g3d_vertex *poly, int *vnumptr,
 237                 const struct g3d_vertex *v0, const struct g3d_vertex *v1, int fplane)
 238 {
 239         int vnum = *vnumptr;
 240         int in0, in1;
 241         float t;
 242
 243         in0 = inside_frustum_plane(v0, fplane);
 244         in1 = inside_frustum_plane(v1, fplane);
 245
 246         if(in0) {
 247                 /* start inside */
 248                 if(in1) {
 249                         /* all inside */
 250                         poly[vnum++] = *v1;     /* append v1 */
 251                         *vnumptr = vnum;
 252                         return 1;
 253                 } else {
 254                         /* going out */
 255                         struct g3d_vertex *vptr = poly + vnum;
 256
 257                         t = intersect_frustum(v0, v1, fplane);
 258
 259                         vptr->x = v0->x + (v1->x - v0->x) * t;
 260                         vptr->y = v0->y + (v1->y - v0->y) * t;
 261                         vptr->z = v0->z + (v1->z - v0->z) * t;
 262                         vptr->w = v0->w + (v1->w - v0->w) * t;
 263
 264                         LERP_VATTR(vptr, v0, v1, t);
 265                         ++vnum; /* append new vertex on the intersection point */
 266                 }
 267         } else {
 268                 /* start outside */
 269                 if(in1) {
 270                         /* going in */
 271                         struct g3d_vertex *vptr = poly + vnum;
 272
 273                         t = intersect_frustum(v0, v1, fplane);
 274
 275                         vptr->x = v0->x + (v1->x - v0->x) * t;
 276                         vptr->y = v0->y + (v1->y - v0->y) * t;
 277                         vptr->z = v0->z + (v1->z - v0->z) * t;
 278                         vptr->w = v0->w + (v1->w - v0->w) * t;
 279
 280                         LERP_VATTR(vptr, v0, v1, t);
 281                         ++vnum; /* append new vertex on the intersection point */
 282
 283                         /* then append v1 ... */
 284                         poly[vnum++] = *v1;
 285                 } else {
 286                         /* all outside */
 287                         return -1;
 288                 }
 289         }
 290
 291         *vnumptr = vnum;
 292         return 0;
 293 }