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

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