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

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #include <math.h>
   4 #include "geom.h"
   5 #include "matrix.h"
   6
   7 #define EPSILON         1e-6f
   8
   9 /* TODO custom hit allocator */
  10 struct hit *alloc_hit(void)
  11 {
  12         struct hit *hit = calloc(sizeof *hit, 1);
  13         if(!hit) {
  14                 perror("failed to allocate ray hit node");
  15                 abort();
  16         }
  17         return hit;
  18 }
  19
  20 struct hit *alloc_hits(int n)
  21 {
  22         int i;
  23         struct hit *list = 0;
  24
  25         for(i=0; i<n; i++) {
  26                 struct hit *hit = alloc_hit();
  27                 hit->next = list;
  28                 list = hit;
  29         }
  30         return list;
  31 }
  32
  33
  34 void free_hit(struct hit *hit)
  35 {
  36         free(hit);
  37 }
  38
  39 void free_hit_list(struct hit *hit)
  40 {
  41         while(hit) {
  42                 struct hit *tmp = hit;
  43                 hit = hit->next;
  44                 free_hit(tmp);
  45         }
  46 }
  47
  48 struct hit *ray_intersect(struct ray *ray, csg_object *o)
  49 {
  50         switch(o->ob.type) {
  51         case OB_SPHERE:
  52                 return ray_sphere(ray, o);
  53         case OB_CYLINDER:
  54                 return ray_cylinder(ray, o);
  55         case OB_PLANE:
  56                 return ray_plane(ray, o);
  57         case OB_UNION:
  58                 return ray_csg_un(ray, o);
  59         case OB_INTERSECTION:
  60                 return ray_csg_isect(ray, o);
  61         case OB_SUBTRACTION:
  62                 return ray_csg_sub(ray, o);
  63         default:
  64                 break;
  65         }
  66         return 0;
  67 }
  68
  69 struct hit *ray_sphere(struct ray *ray, csg_object *o)
  70 {
  71         int i;
  72         float a, b, c, d, sqrt_d, t[2], sq_rad, tmp;
  73         struct hit *hit, *hitlist;
  74         struct ray locray = *ray;
  75
  76         if(o->sph.rad == 0.0f) {
  77                 return 0;
  78         }
  79         sq_rad = o->sph.rad * o->sph.rad;
  80
  81         xform_ray(&locray, o->ob.inv_xform);
  82
  83         a = locray.dx * locray.dx + locray.dy * locray.dy + locray.dz * locray.dz;
  84         b = 2.0f * (locray.dx * locray.x + locray.dy * locray.y + locray.dz * locray.z);
  85         c = (locray.x * locray.x + locray.y * locray.y + locray.z * locray.z) - sq_rad;
  86
  87         d = b * b - 4.0f * a * c;
  88         if(d < EPSILON) return 0;
  89
  90         sqrt_d = sqrt(d);
  91         t[0] = (-b + sqrt_d) / (2.0f * a);
  92         t[1] = (-b - sqrt_d) / (2.0f * a);
  93
  94         if(t[0] < EPSILON && t[1] < EPSILON) {
  95                 return 0;
  96         }
  97
  98         if(t[1] < t[0]) {
  99                 tmp = t[0];
 100                 t[0] = t[1];
 101                 t[1] = tmp;
 102         }
 103
 104         hitlist = hit = alloc_hits(2);
 105         for(i=0; i<2; i++) {
 106                 float c[3] = {0, 0, 0};
 107                 mat4_xform3(c, o->ob.xform, c);
 108
 109                 hit->t = t[i];
 110                 hit->x = ray->x + ray->dx * t[i];
 111                 hit->y = ray->y + ray->dy * t[i];
 112                 hit->z = ray->z + ray->dz * t[i];
 113                 hit->nx = (hit->x - c[0]) / o->sph.rad;
 114                 hit->ny = (hit->y - c[1]) / o->sph.rad;
 115                 hit->nz = (hit->z - c[2]) / o->sph.rad;
 116                 hit->o = o;
 117
 118                 hit = hit->next;
 119         }
 120         return hitlist;
 121 }
 122
 123 struct hit *ray_cylinder(struct ray *ray, csg_object *o)
 124 {
 125         struct ray locray = *ray;
 126
 127         xform_ray(&locray, o->ob.inv_xform);
 128         return 0;       /* TODO */
 129 }
 130
 131 struct hit *ray_plane(struct ray *ray, csg_object *o)
 132 {
 133         float vx, vy, vz, ndotv, ndotr, t;
 134         struct hit *hit = 0;
 135         struct ray locray = *ray;
 136
 137         xform_ray(&locray, o->ob.inv_xform);
 138
 139         ndotr = o->plane.nx * locray.dx + o->plane.ny * locray.dy + o->plane.nz * locray.dz;
 140         if(fabs(ndotr) < EPSILON) return 0;
 141
 142         vx = o->plane.nx * o->plane.d - locray.x;
 143         vy = o->plane.ny * o->plane.d - locray.y;
 144         vz = o->plane.nz * o->plane.d - locray.z;
 145
 146         ndotv = o->plane.nx * vx + o->plane.ny * vy + o->plane.nz * vz;
 147
 148         t = ndotv / ndotr;
 149
 150         if(t > EPSILON) {
 151                 hit = alloc_hits(1);
 152                 hit->t = t;
 153                 hit->x = ray->x + ray->dx * t;
 154                 hit->y = ray->y + ray->dy * t;
 155                 hit->z = ray->z + ray->dz * t;
 156                 hit->nx = o->plane.nx;
 157                 hit->ny = o->plane.ny;
 158                 hit->nz = o->plane.nz;
 159                 hit->o = o;
 160         }
 161         return hit;
 162 }
 163
 164 struct hit *ray_csg_un(struct ray *ray, csg_object *o)
 165 {
 166         struct hit *hita, *hitb;
 167
 168         hita = ray_intersect(ray, o->un.a);
 169         hitb = ray_intersect(ray, o->un.b);
 170
 171         if(!hita) return hitb;
 172         if(!hitb) return hita;
 173
 174         if(hita->t < hitb->t) {
 175                 free_hit_list(hitb);
 176                 return hita;
 177         }
 178         free_hit_list(hita);
 179         return hitb;
 180 }
 181
 182 struct hit *ray_csg_isect(struct ray *ray, csg_object *o)
 183 {
 184         return 0;
 185 }
 186
 187 static struct hit *first(struct hit *hlist)
 188 {
 189         return hlist;
 190 }
 191
 192 static struct hit *last(struct hit *hlist)
 193 {
 194         while(hlist->next) {
 195                 hlist = hlist->next;
 196         }
 197         return hlist;
 198 }
 199
 200 struct hit *ray_csg_sub(struct ray *ray, csg_object *o)
 201 {
 202         struct hit *hita, *hitb, *lasthit, tmp;
 203
 204         hita = ray_intersect(ray, o->sub.a);
 205         hitb = ray_intersect(ray, o->sub.b);
 206
 207         if(!hita) return 0;
 208         if(!hitb) return hita;
 209
 210         if(first(hita)->t < first(hitb)->t) {
 211                 free_hit_list(hitb);
 212                 return hita;
 213         }
 214         if(first(hita)->t < (lasthit = last(hitb))->t) {
 215                 /* overlapping */
 216                 tmp = *hitb;
 217                 *hitb = *lasthit;
 218
 219                 free_hit_list(tmp.next);
 220
 221                 hitb->nx = -hitb->nx;
 222                 hitb->ny = -hitb->ny;
 223                 hitb->nz = -hitb->nz;
 224
 225                 free_hit_list(hita);
 226                 return hitb;
 227         }
 228
 229         free_hit_list(hitb);
 230         return hita;
 231 }
 232
 233
 234 void xform_ray(struct ray *ray, float *mat)
 235 {
 236         float m3x3[16];
 237
 238         mat4_copy(m3x3, mat);
 239         mat4_upper3x3(m3x3);
 240
 241         mat4_xform3(&ray->x, mat, &ray->x);
 242         mat4_xform3(&ray->dx, m3x3, &ray->dx);
 243 }