git.mutantstargoat.com Git - meshfrac/blob - src/geom.c

   1 #include <stdio.h>
   2 #include <assert.h>
   3 #include "geom.h"
   4 #include "dynarr.h"
   5
   6 float plane_dist(const struct plane *p, const cgm_vec3 *pt)
   7 {
   8         return fabs(plane_sdist(p, pt));
   9 }
  10
  11 float plane_sdist(const struct plane *p, const cgm_vec3 *pt)
  12 {
  13         cgm_vec3 v = p->pt;
  14         cgm_vsub(&v, pt);
  15         return cgm_vdot(&v, &p->norm);
  16 }
  17
  18 void midplane(struct plane *p, const cgm_vec3 *a, const cgm_vec3 *b)
  19 {
  20         p->norm = *b;
  21         cgm_vsub(&p->norm, a);
  22         cgm_vnormalize(&p->norm);
  23         p->pt.x = a->x + p->norm.x * 0.5f;
  24         p->pt.y = a->y + p->norm.y * 0.5f;
  25         p->pt.z = a->z + p->norm.z * 0.5f;
  26 }
  27
  28 void poly_normal(const struct poly *poly, cgm_vec3 *n)
  29 {
  30         cgm_vec3 va, vb;
  31
  32         va = poly->verts[1].pos;
  33         cgm_vsub(&va, &poly->verts[0].pos);
  34         vb = poly->verts[2].pos;
  35         cgm_vsub(&vb, &poly->verts[0].pos);
  36
  37         cgm_vcross(n, &va, &vb);
  38         cgm_vnormalize(n);
  39 }
  40
  41 void poly_plane(const struct poly *poly, struct plane *plane)
  42 {
  43         plane->pt = poly->verts[0].pos;
  44         poly_normal(poly, &plane->norm);
  45 }
  46
  47 int plane_poly(const struct plane *plane, struct poly *poly, float size)
  48 {
  49         static const float corn[][2] = {{1,1}, {-1,1}, {-1,-1}, {1, -1}};
  50         int i;
  51         cgm_vec3 up, right;
  52         struct vertex *vptr;
  53         size *= 0.5f;
  54
  55         if(!(poly->verts = dynarr_alloc(4, sizeof *poly->verts))) {
  56                 fprintf(stderr, "plane_poly: failed to allocate polygon vertices\n");
  57                 return -1;
  58         }
  59
  60         cgm_vcons(&up, 0, 1, 0);
  61         if(1.0f - fabs(cgm_vdot(&up, &plane->norm)) < 1e-2) {
  62                 cgm_vcons(&up, 0, 0, -1);
  63         }
  64         cgm_vcross(&right, &up, &plane->norm);
  65         cgm_vnormalize(&right);
  66         cgm_vcross(&up, &plane->norm, &right);
  67         cgm_vnormalize(&up);
  68
  69         vptr = poly->verts;
  70         for(i=0; i<4; i++) {
  71                 vptr->pos.x = plane->pt.x + (right.x * corn[i][0] + up.x * corn[i][1]) * size;
  72                 vptr->pos.y = plane->pt.y + (right.y * corn[i][0] + up.y * corn[i][1]) * size;
  73                 vptr->pos.z = plane->pt.z + (right.z * corn[i][0] + up.z * corn[i][1]) * size;
  74
  75                 vptr->norm = plane->norm;
  76                 vptr->uv.x = vptr->uv.y = 0;
  77                 vptr++;
  78         }
  79         return 0;
  80 }
  81
  82 float ray_plane(const cgm_ray *ray, const struct plane *plane)
  83 {
  84         float ndotdir, t;
  85         cgm_vec3 pptdir;
  86
  87         ndotdir = cgm_vdot(&plane->norm, &ray->dir);
  88         if(fabs(ndotdir) < 1e-4) {
  89                 return -1.0f;
  90         }
  91
  92         pptdir = plane->pt;
  93         cgm_vsub(&pptdir, &ray->origin);
  94         t = cgm_vdot(&plane->norm, &pptdir) / ndotdir;
  95         if(t < 1e-6) {
  96                 return -1.0f;
  97         }
  98         return t;
  99 }
 100
 101 float ray_poly(const cgm_ray *ray, const struct poly *poly)
 102 {
 103         float t;
 104         struct plane plane;
 105         cgm_vec3 hitp, vdir, edir, indir, vcross, incross;
 106         int i, nverts;
 107
 108         poly_plane(poly, &plane);
 109         if((t = ray_plane(ray, &plane)) < 0.0f) {
 110                 return -1.0f;
 111         }
 112         cgm_raypos(&hitp, ray, t);
 113
 114         /* see if the point is inside or outside the polygon */
 115         nverts = dynarr_size(poly->verts);
 116         for(i=0; i<nverts; i++) {
 117                 vdir = hitp;
 118                 cgm_vsub(&hitp, &poly->verts[i].pos);
 119                 edir = poly->verts[(i + 1) & nverts].pos;
 120                 cgm_vsub(&edir, &poly->verts[i].pos);
 121                 indir = poly->verts[(i + 2) & nverts].pos;
 122                 cgm_vsub(&indir, &poly->verts[i].pos);
 123
 124                 cgm_vcross(&vcross, &vdir, &edir);
 125                 cgm_vcross(&incross, &indir, &edir);
 126
 127                 if(cgm_vdot(&vcross, &incross) < 0.0f) {
 128                         return -1.0f;
 129                 }
 130         }
 131         return t;
 132 }
 133
 134 int init_poly(struct poly *p)
 135 {
 136         p->verts = dynarr_alloc(0, sizeof *p->verts);
 137         assert(p->verts);
 138         return p->verts ? 0 : -1;
 139 }
 140
 141 void destroy_poly(struct poly *p)
 142 {
 143         dynarr_free(p->verts);
 144 }
 145
 146 /* returns:
 147  *  1 -> both inside
 148  *  0 -> straddling and clipped
 149  * -1 -> both outside
 150  */
 151 static int clip_edge(struct poly *pout, const struct vertex *v0, const struct vertex *v1,
 152                 const struct plane *plane)
 153 {
 154         float d0, d1, t;
 155         cgm_ray ray;
 156         struct vertex vnew;
 157
 158         d0 = plane_sdist(plane, &v0->pos);
 159         d1 = plane_sdist(plane, &v1->pos);
 160
 161         ray.origin = v0->pos;
 162         ray.dir = v1->pos;
 163         cgm_vsub(&ray.dir, &v0->pos);
 164
 165         if(d0 >= 0.0) {
 166                 /* start inside */
 167                 if(d1 >= 0.0) {
 168                         /* all inside */
 169                         DYNARR_PUSH(pout->verts, v1);   /* append v1 */
 170                         return 1;
 171                 } else {
 172                         /* going out */
 173                         t = ray_plane(&ray, plane);
 174                         cgm_raypos(&vnew.pos, &ray, t);
 175
 176                         cgm_vlerp(&vnew.norm, &v0->norm, &v1->norm, t);
 177                         vnew.uv.x = cgm_lerp(v0->uv.x, v1->uv.x, t);
 178                         vnew.uv.y = cgm_lerp(v0->uv.y, v1->uv.y, t);
 179                         /* append new vertex on the intersection point */
 180                         DYNARR_PUSH(pout->verts, &vnew);
 181                 }
 182         } else {
 183                 /* start outside */
 184                 if(d1 >= 0) {
 185                         /* going in */
 186                         t = ray_plane(&ray, plane);
 187                         cgm_raypos(&vnew.pos, &ray, t);
 188
 189                         cgm_vlerp(&vnew.norm, &v0->norm, &v1->norm, t);
 190                         vnew.uv.x = cgm_lerp(v0->uv.x, v1->uv.x, t);
 191                         vnew.uv.y = cgm_lerp(v0->uv.y, v1->uv.y, t);
 192                         /* append new vertex on the intersection point */
 193                         DYNARR_PUSH(pout->verts, &vnew);
 194                         /* then append v1 ... */
 195                         DYNARR_PUSH(pout->verts, v1);
 196                 } else {
 197                         /* all outside */
 198                         return -1;
 199                 }
 200         }
 201
 202         return 0;
 203 }
 204
 205
 206 int clip_poly(struct poly *pout, const struct poly *pin, const struct plane *plane)
 207 {
 208         int i, nextidx, res = 0, vnum;
 209         int edges_clipped = 0;
 210
 211         DYNARR_CLEAR(pout->verts);
 212
 213         vnum = dynarr_size(pin->verts);
 214         for(i=0; i<vnum; i++) {
 215                 nextidx = i + 1;
 216                 if(nextidx >= vnum) nextidx = 0;
 217                 res = clip_edge(pout, pin->verts + i, pin->verts + nextidx, plane);
 218                 if(res == 0) {
 219                         ++edges_clipped;
 220                 }
 221         }
 222
 223         return edges_clipped > 0 ? 0 : 1;
 224
 225 }