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 float distance_signed(float *pos, const struct cplane *plane);
  14 static int intersect(const struct ray *ray, const struct cplane *plane, float *t);
  15
  16
  17 int clip_poly(struct g3d_vertex *vout, int *voutnum,
  18                 const struct g3d_vertex *vin, int vnum, struct cplane *plane)
  19 {
  20         int i;
  21         int edges_clipped = 0;
  22         int out_vnum = 0;
  23
  24         for(i=0; i<vnum; i++) {
  25                 int res = clip_edge(vout, &out_vnum, vin + i, vin + (i + 1) % vnum, plane);
  26                 if(res == 0) {
  27                         edges_clipped++;
  28                 }
  29         }
  30
  31         if(out_vnum <= 0) {
  32                 assert(edges_clipped == 0);
  33                 return -1;
  34         }
  35
  36         *voutnum = out_vnum;
  37         return edges_clipped > 0 ? 0 : 1;
  38 }
  39
  40 #define LERP_VATTR(res, v0, v1, t) \
  41         do { \
  42                 (res)->nx = (v0)->nx + ((v1)->nx - (v0)->nx) * (t); \
  43                 (res)->ny = (v0)->ny + ((v1)->ny - (v0)->ny) * (t); \
  44                 (res)->nz = (v0)->nz + ((v1)->nz - (v0)->nz) * (t); \
  45                 (res)->u = (v0)->u + ((v1)->u - (v0)->u) * (t); \
  46                 (res)->v = (v0)->v + ((v1)->v - (v0)->v) * (t); \
  47                 (res)->r = (v0)->r + ((v1)->r - (v0)->r) * (t); \
  48                 (res)->g = (v0)->g + ((v1)->g - (v0)->g) * (t); \
  49                 (res)->b = (v0)->b + ((v1)->b - (v0)->b) * (t); \
  50         } while(0)
  51
  52
  53 /* returns:
  54  *  1 -> both inside
  55  *  0 -> straddling and clipped
  56  * -1 -> both outside
  57  *
  58  *  also returns the size of the polygon through vnumptr
  59  */
  60 static int clip_edge(struct g3d_vertex *poly, int *vnumptr,
  61                 const struct g3d_vertex *v0, const struct g3d_vertex *v1,
  62                 const struct cplane *plane)
  63 {
  64         float pos0[3], pos1[3];
  65         float d0, d1, t;
  66         struct ray ray;
  67         int i, vnum = *vnumptr;
  68
  69         pos0[0] = v0->x; pos0[1] = v0->y; pos0[2] = v0->z;
  70         pos1[0] = v1->x; pos1[1] = v1->y; pos1[2] = v1->z;
  71
  72         d0 = distance_signed(pos0, plane);
  73         d1 = distance_signed(pos1, plane);
  74
  75         for(i=0; i<3; i++) {
  76                 ray.origin[i] = pos0[i];
  77                 ray.dir[i] = pos1[i] - pos0[i];
  78         }
  79
  80         if(d0 >= 0.0) {
  81                 /* start inside */
  82                 if(d1 >= 0.0) {
  83                         /* all inside */
  84                         poly[vnum++] = *v1;     /* append v1 */
  85                         *vnumptr = vnum;
  86                         return 1;
  87                 } else {
  88                         /* going out */
  89                         struct g3d_vertex *vptr = poly + vnum;
  90
  91                         intersect(&ray, plane, &t);
  92
  93                         vptr->x = ray.origin[0] + ray.dir[0] * t;
  94                         vptr->y = ray.origin[1] + ray.dir[1] * t;
  95                         vptr->z = ray.origin[2] + ray.dir[2] * t;
  96                         vptr->w = 1.0f;
  97
  98                         LERP_VATTR(vptr, v0, v1, t);
  99                         vnum++; /* append new vertex on the intersection point */
 100                 }
 101         } else {
 102                 /* start outside */
 103                 if(d1 >= 0) {
 104                         /* going in */
 105                         struct g3d_vertex *vptr = poly + vnum;
 106
 107                         intersect(&ray, plane, &t);
 108
 109                         vptr->x = ray.origin[0] + ray.dir[0] + t;
 110                         vptr->y = ray.origin[1] + ray.dir[1] + t;
 111                         vptr->z = ray.origin[2] + ray.dir[2] + t;
 112                         vptr->w = 1.0f;
 113
 114                         LERP_VATTR(vptr, v0, v1, t);
 115                         vnum++; /* append new vertex on the intersection point */
 116
 117                         /* then append v1 ... */
 118                         poly[vnum++] = *v1;
 119                 } else {
 120                         /* all outside */
 121                         return -1;
 122                 }
 123         }
 124
 125         *vnumptr = vnum;
 126         return 0;
 127 }
 128
 129
 130 static float distance_signed(float *pos, const struct cplane *plane)
 131 {
 132         float dx = pos[0] - plane->x;
 133         float dy = pos[1] - plane->y;
 134         float dz = pos[2] - plane->z;
 135         return dx * plane->nx + dy * plane->ny + dz * plane->nz;
 136 }
 137
 138 static int intersect(const struct ray *ray, const struct cplane *plane, float *t)
 139 {
 140         float orig_pt_dir[3];
 141
 142         float ndotdir = plane->nx * ray->dir[0] + plane->ny * ray->dir[1] + plane->nz * ray->dir[2];
 143         if(fabs(ndotdir) < 1e-4) {
 144                 *t = 0.0f;
 145                 return 0;
 146         }
 147
 148         orig_pt_dir[0] = plane->x - ray->origin[0];
 149         orig_pt_dir[1] = plane->y - ray->origin[1];
 150         orig_pt_dir[2] = plane->z - ray->origin[2];
 151
 152         *t = (plane->nx * orig_pt_dir[0] + plane->ny * orig_pt_dir[1] + plane->nz * orig_pt_dir[2]) / ndotdir;
 153         return 1;
 154 }