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

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