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

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