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