git.mutantstargoat.com Git - retroray/blob - src/gaw/polyclip.c

   1 /*
   2 RetroRay - integrated standalone vintage modeller/renderer
   3 Copyright (C) 2023  John Tsiombikas <nuclear@mutantstargoat.com>
   4
   5 This program is free software: you can redistribute it and/or modify
   6 it under the terms of the GNU General Public License as published by
   7 the Free Software Foundation, either version 3 of the License, or
   8 (at your option) any later version.
   9
  10 This program is distributed in the hope that it will be useful,
  11 but WITHOUT ANY WARRANTY; without even the implied warranty of
  12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13 GNU General Public License for more details.
  14
  15 You should have received a copy of the GNU General Public License
  16 along with this program.  If not, see <https://www.gnu.org/licenses/>.
  17 */
  18 #include <stdio.h>
  19 #include <math.h>
  20 #include <assert.h>
  21 #include "polyclip.h"
  22
  23 struct ray {
  24         float origin[3];
  25         float dir[3];
  26 };
  27
  28 static int clip_edge(struct vertex *poly, int *vnumptr,
  29                 const struct vertex *v0, const struct vertex *v1,
  30                 const struct cplane *plane);
  31 static int check_clip_edge(const struct vertex *v0,
  32                 const struct vertex *v1, const struct cplane *plane);
  33 static int clip_edge_frustum(struct vertex *poly, int *vnumptr,
  34                 const struct vertex *v0, const struct vertex *v1, int fplane);
  35 static float distance_signed(float *pos, const struct cplane *plane);
  36 static int intersect(const struct ray *ray, const struct cplane *plane, float *t);
  37 static int inside_frustum_plane(const struct vertex *v, int fplane);
  38
  39
  40 int clip_poly(struct vertex *vout, int *voutnum,
  41                 const struct vertex *vin, int vnum, struct cplane *plane)
  42 {
  43         int i, nextidx, res;
  44         int edges_clipped = 0;
  45
  46         *voutnum = 0;
  47
  48         for(i=0; i<vnum; i++) {
  49                 nextidx = i + 1;
  50                 if(nextidx >= vnum) nextidx = 0;
  51                 res = clip_edge(vout, voutnum, vin + i, vin + nextidx, plane);
  52                 if(res == 0) {
  53                         ++edges_clipped;
  54                 }
  55         }
  56
  57         if(*voutnum <= 0) {
  58                 assert(edges_clipped == 0);
  59                 return -1;
  60         }
  61
  62         return edges_clipped > 0 ? 0 : 1;
  63 }
  64
  65 int check_clip_poly(const struct vertex *v, int vnum, struct cplane *plane)
  66 {
  67         int i, nextidx, res = 0;
  68         int edges_clipped = 0;
  69
  70         for(i=0; i<vnum; i++) {
  71                 nextidx = i + 1;
  72                 if(nextidx >= vnum) nextidx = 0;
  73                 res = check_clip_edge(v + i, v + nextidx, plane);
  74                 if(res == 0) {
  75                         ++edges_clipped;
  76                 }
  77         }
  78         return edges_clipped ? 0 : res;
  79 }
  80
  81 int clip_frustum(struct vertex *vout, int *voutnum,
  82                 const struct vertex *vin, int vnum, int fplane)
  83 {
  84         int i, nextidx, res;
  85         int edges_clipped = 0;
  86
  87         if(vnum == 1) {
  88                 /* special case: point clipping */
  89                 return inside_frustum_plane(vin, fplane) ? 1 : -1;
  90         }
  91
  92         *voutnum = 0;
  93
  94         for(i=0; i<vnum; i++) {
  95                 nextidx = i + 1;
  96                 if(nextidx >= vnum) nextidx = 0;
  97                 res = clip_edge_frustum(vout, voutnum, vin + i, vin + nextidx, fplane);
  98                 if(res == 0) {
  99                         ++edges_clipped;
 100                 }
 101         }
 102
 103         if(*voutnum <= 0) {
 104                 assert(edges_clipped == 0);
 105                 return -1;
 106         }
 107
 108         return edges_clipped > 0 ? 0 : 1;
 109 }
 110
 111 #define LERP_VATTR(res, v0, v1, t) \
 112         do { \
 113                 (res)->nx = (v0)->nx + ((v1)->nx - (v0)->nx) * (t); \
 114                 (res)->ny = (v0)->ny + ((v1)->ny - (v0)->ny) * (t); \
 115                 (res)->nz = (v0)->nz + ((v1)->nz - (v0)->nz) * (t); \
 116                 (res)->u = (v0)->u + ((v1)->u - (v0)->u) * (t); \
 117                 (res)->v = (v0)->v + ((v1)->v - (v0)->v) * (t); \
 118                 (res)->r = (v0)->r + ((v1)->r - (v0)->r) * (t); \
 119                 (res)->g = (v0)->g + ((v1)->g - (v0)->g) * (t); \
 120                 (res)->b = (v0)->b + ((v1)->b - (v0)->b) * (t); \
 121         } while(0)
 122
 123
 124 /* returns:
 125  *  1 -> both inside
 126  *  0 -> straddling and clipped
 127  * -1 -> both outside
 128  *
 129  *  also returns the size of the polygon through vnumptr
 130  */
 131 static int clip_edge(struct vertex *poly, int *vnumptr,
 132                 const struct vertex *v0, const struct vertex *v1,
 133                 const struct cplane *plane)
 134 {
 135         float pos0[3], pos1[3];
 136         float d0, d1, t;
 137         struct ray ray;
 138         int i, vnum = *vnumptr;
 139
 140         pos0[0] = v0->x; pos0[1] = v0->y; pos0[2] = v0->z;
 141         pos1[0] = v1->x; pos1[1] = v1->y; pos1[2] = v1->z;
 142
 143         d0 = distance_signed(pos0, plane);
 144         d1 = distance_signed(pos1, plane);
 145
 146         for(i=0; i<3; i++) {
 147                 ray.origin[i] = pos0[i];
 148                 ray.dir[i] = pos1[i] - pos0[i];
 149         }
 150
 151         if(d0 >= 0.0) {
 152                 /* start inside */
 153                 if(d1 >= 0.0) {
 154                         /* all inside */
 155                         poly[vnum++] = *v1;     /* append v1 */
 156                         *vnumptr = vnum;
 157                         return 1;
 158                 } else {
 159                         /* going out */
 160                         struct vertex *vptr = poly + vnum;
 161
 162                         intersect(&ray, plane, &t);
 163
 164                         vptr->x = ray.origin[0] + ray.dir[0] * t;
 165                         vptr->y = ray.origin[1] + ray.dir[1] * t;
 166                         vptr->z = ray.origin[2] + ray.dir[2] * t;
 167                         vptr->w = 1.0f;
 168
 169                         LERP_VATTR(vptr, v0, v1, t);
 170                         vnum++; /* append new vertex on the intersection point */
 171                 }
 172         } else {
 173                 /* start outside */
 174                 if(d1 >= 0) {
 175                         /* going in */
 176                         struct vertex *vptr = poly + vnum;
 177
 178                         intersect(&ray, plane, &t);
 179
 180                         vptr->x = ray.origin[0] + ray.dir[0] * t;
 181                         vptr->y = ray.origin[1] + ray.dir[1] * t;
 182                         vptr->z = ray.origin[2] + ray.dir[2] * t;
 183                         vptr->w = 1.0f;
 184
 185                         LERP_VATTR(vptr, v0, v1, t);
 186                         vnum++; /* append new vertex on the intersection point */
 187
 188                         /* then append v1 ... */
 189                         poly[vnum++] = *v1;
 190                 } else {
 191                         /* all outside */
 192                         return -1;
 193                 }
 194         }
 195
 196         *vnumptr = vnum;
 197         return 0;
 198 }
 199
 200 /* same as above, but only checks for clipping and classifies the edge */
 201 static int check_clip_edge(const struct vertex *v0,
 202                 const struct vertex *v1, const struct cplane *plane)
 203 {
 204         float pos0[3], pos1[3];
 205         float d0, d1;
 206
 207         pos0[0] = v0->x; pos0[1] = v0->y; pos0[2] = v0->z;
 208         pos1[0] = v1->x; pos1[1] = v1->y; pos1[2] = v1->z;
 209
 210         d0 = distance_signed(pos0, plane);
 211         d1 = distance_signed(pos1, plane);
 212
 213         if(d0 > 0.0f && d1 > 0.0f) {
 214                 return 1;
 215         }
 216         if(d0 < 0.0f && d1 < 0.0f) {
 217                 return -1;
 218         }
 219         return 0;
 220 }
 221
 222 static float distance_signed(float *pos, const struct cplane *plane)
 223 {
 224         float dx = pos[0] - plane->x;
 225         float dy = pos[1] - plane->y;
 226         float dz = pos[2] - plane->z;
 227         return dx * plane->nx + dy * plane->ny + dz * plane->nz;
 228 }
 229
 230 static int intersect(const struct ray *ray, const struct cplane *plane, float *t)
 231 {
 232         float orig_pt_dir[3];
 233
 234         float ndotdir = plane->nx * ray->dir[0] + plane->ny * ray->dir[1] + plane->nz * ray->dir[2];
 235         if(fabs(ndotdir) < 1e-6) {
 236                 *t = 0.0f;
 237                 return 0;
 238         }
 239
 240         orig_pt_dir[0] = plane->x - ray->origin[0];
 241         orig_pt_dir[1] = plane->y - ray->origin[1];
 242         orig_pt_dir[2] = plane->z - ray->origin[2];
 243
 244         *t = (plane->nx * orig_pt_dir[0] + plane->ny * orig_pt_dir[1] + plane->nz * orig_pt_dir[2]) / ndotdir;
 245         return 1;
 246 }
 247
 248 /* homogeneous frustum clipper helpers */
 249
 250 static int inside_frustum_plane(const struct vertex *v, int fplane)
 251 {
 252         switch(fplane) {
 253         case CLIP_LEFT:
 254                 return v->x >= -v->w;
 255         case CLIP_RIGHT:
 256                 return v->x <= v->w;
 257         case CLIP_BOTTOM:
 258                 return v->y >= -v->w;
 259         case CLIP_TOP:
 260                 return v->y <= v->w;
 261         case CLIP_NEAR:
 262                 return v->z >= -v->w;
 263         case CLIP_FAR:
 264                 return v->z <= v->w;
 265         }
 266         assert(0);
 267         return 0;
 268 }
 269
 270 static float intersect_frustum(const struct vertex *a, const struct vertex *b, int fplane)
 271 {
 272         switch(fplane) {
 273         case CLIP_LEFT:
 274                 return (-a->w - a->x) / (b->x - a->x + b->w - a->w);
 275         case CLIP_RIGHT:
 276                 return (a->w - a->x) / (b->x - a->x - b->w + a->w);
 277         case CLIP_BOTTOM:
 278                 return (-a->w - a->y) / (b->y - a->y + b->w - a->w);
 279         case CLIP_TOP:
 280                 return (a->w - a->y) / (b->y - a->y - b->w + a->w);
 281         case CLIP_NEAR:
 282                 return (-a->w - a->z) / (b->z - a->z + b->w - a->w);
 283         case CLIP_FAR:
 284                 return (a->w - a->z) / (b->z - a->z - b->w + a->w);
 285         }
 286
 287         assert(0);
 288         return 0;
 289 }
 290
 291 static int clip_edge_frustum(struct vertex *poly, int *vnumptr,
 292                 const struct vertex *v0, const struct vertex *v1, int fplane)
 293 {
 294         int vnum = *vnumptr;
 295         int in0, in1;
 296         float t;
 297
 298         in0 = inside_frustum_plane(v0, fplane);
 299         in1 = inside_frustum_plane(v1, fplane);
 300
 301         if(in0) {
 302                 /* start inside */
 303                 if(in1) {
 304                         /* all inside */
 305                         poly[vnum++] = *v1;     /* append v1 */
 306                         *vnumptr = vnum;
 307                         return 1;
 308                 } else {
 309                         /* going out */
 310                         struct vertex *vptr = poly + vnum;
 311
 312                         t = intersect_frustum(v0, v1, fplane);
 313
 314                         vptr->x = v0->x + (v1->x - v0->x) * t;
 315                         vptr->y = v0->y + (v1->y - v0->y) * t;
 316                         vptr->z = v0->z + (v1->z - v0->z) * t;
 317                         vptr->w = v0->w + (v1->w - v0->w) * t;
 318
 319                         LERP_VATTR(vptr, v0, v1, t);
 320                         ++vnum; /* append new vertex on the intersection point */
 321                 }
 322         } else {
 323                 /* start outside */
 324                 if(in1) {
 325                         /* going in */
 326                         struct vertex *vptr = poly + vnum;
 327
 328                         t = intersect_frustum(v0, v1, fplane);
 329
 330                         vptr->x = v0->x + (v1->x - v0->x) * t;
 331                         vptr->y = v0->y + (v1->y - v0->y) * t;
 332                         vptr->z = v0->z + (v1->z - v0->z) * t;
 333                         vptr->w = v0->w + (v1->w - v0->w) * t;
 334
 335                         LERP_VATTR(vptr, v0, v1, t);
 336                         ++vnum; /* append new vertex on the intersection point */
 337
 338                         /* then append v1 ... */
 339                         poly[vnum++] = *v1;
 340                 } else {
 341                         /* all outside */
 342                         return -1;
 343                 }
 344         }
 345
 346         *vnumptr = vnum;
 347         return 0;
 348 }