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