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         if(t[0] < EPSILON) t[0] = EPSILON;
 105         if(t[1] < EPSILON) t[1] = EPSILON;
 106
 107         hitlist = hit = alloc_hits(2);
 108         for(i=0; i<2; i++) {
 109                 float c[3] = {0, 0, 0};
 110                 mat4_xform3(c, o->ob.xform, c);
 111
 112                 hit->t = t[i];
 113                 hit->x = ray->x + ray->dx * t[i];
 114                 hit->y = ray->y + ray->dy * t[i];
 115                 hit->z = ray->z + ray->dz * t[i];
 116                 hit->nx = (hit->x - c[0]) / o->sph.rad;
 117                 hit->ny = (hit->y - c[1]) / o->sph.rad;
 118                 hit->nz = (hit->z - c[2]) / o->sph.rad;
 119                 hit->o = o;
 120
 121                 hit = hit->next;
 122         }
 123         return hitlist;
 124 }
 125
 126 struct hit *ray_cylinder(struct ray *ray, csg_object *o)
 127 {
 128         struct ray locray = *ray;
 129
 130         xform_ray(&locray, o->ob.inv_xform);
 131         return 0;       /* TODO */
 132 }
 133
 134 struct hit *ray_plane(struct ray *ray, csg_object *o)
 135 {
 136         float vx, vy, vz, ndotv, ndotr, t;
 137         struct hit *hit = 0;
 138         struct ray locray = *ray;
 139
 140         xform_ray(&locray, o->ob.inv_xform);
 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         if(fabs(ndotv) < EPSILON) return 0;
 148
 149         ndotr = o->plane.nx * locray.dx + o->plane.ny * locray.dy + o->plane.nz * locray.dz;
 150         t = ndotr / ndotv;
 151
 152         if(t > EPSILON) {
 153                 hit = alloc_hits(1);
 154                 hit->t = t;
 155                 hit->x = ray->x + ray->dx * t;
 156                 hit->y = ray->y + ray->dy * t;
 157                 hit->z = ray->z + ray->dz * t;
 158                 hit->nx = o->plane.nx;
 159                 hit->ny = o->plane.ny;
 160                 hit->nz = o->plane.nz;
 161                 hit->o = o;
 162         }
 163         return hit;
 164 }
 165
 166 struct hit *ray_csg_un(struct ray *ray, csg_object *o)
 167 {
 168         struct hit *hita, *hitb;
 169
 170         hita = ray_intersect(ray, o->un.a);
 171         hitb = ray_intersect(ray, o->un.b);
 172
 173         if(!hita) return hitb;
 174         if(!hitb) return hita;
 175
 176         if(hita->t < hitb->t) {
 177                 free_hit_list(hitb);
 178                 return hita;
 179         }
 180         free_hit_list(hita);
 181         return hitb;
 182 }
 183
 184 struct hit *ray_csg_isect(struct ray *ray, csg_object *o)
 185 {
 186         return 0;
 187 }
 188
 189 struct hit *ray_csg_sub(struct ray *ray, csg_object *o)
 190 {
 191         return 0;
 192 }
 193
 194
 195 void xform_ray(struct ray *ray, float *mat)
 196 {
 197         float m3x3[16];
 198
 199         mat4_copy(m3x3, mat);
 200         mat4_upper3x3(m3x3);
 201
 202         mat4_xform3(&ray->x, mat, &ray->x);
 203         mat4_xform3(&ray->dx, m3x3, &ray->dx);
 204 }