10 static struct hinterv *interval_union(struct hinterv *a, struct hinterv *b);
11 static struct hinterv *interval_isect(struct hinterv *a, struct hinterv *b);
12 static struct hinterv *interval_sub(struct hinterv *a, struct hinterv *b);
14 /* TODO custom hit allocator */
15 struct hinterv *alloc_hit(void)
17 struct hinterv *hit = calloc(sizeof *hit, 1);
19 perror("failed to allocate ray hit node");
25 struct hinterv *alloc_hits(int n)
28 struct hinterv *list = 0;
31 struct hinterv *hit = alloc_hit();
39 void free_hit(struct hinterv *hit)
44 void free_hit_list(struct hinterv *hit)
47 struct hinterv *tmp = hit;
53 struct hinterv *ray_intersect(struct ray *ray, csg_object *o)
57 return ray_sphere(ray, o);
59 return ray_cylinder(ray, o);
61 return ray_plane(ray, o);
63 return ray_csg_un(ray, o);
65 return ray_csg_isect(ray, o);
67 return ray_csg_sub(ray, o);
74 struct hinterv *ray_sphere(struct ray *ray, csg_object *o)
77 float a, b, c, d, sqrt_d, t[2], sq_rad, tmp;
79 struct ray locray = *ray;
81 if(o->sph.rad == 0.0f) {
84 sq_rad = o->sph.rad * o->sph.rad;
86 xform_ray(&locray, o->ob.inv_xform);
88 a = locray.dx * locray.dx + locray.dy * locray.dy + locray.dz * locray.dz;
89 b = 2.0f * (locray.dx * locray.x + locray.dy * locray.y + locray.dz * locray.z);
90 c = (locray.x * locray.x + locray.y * locray.y + locray.z * locray.z) - sq_rad;
92 d = b * b - 4.0f * a * c;
93 if(d < EPSILON) return 0;
96 t[0] = (-b + sqrt_d) / (2.0f * a);
97 t[1] = (-b - sqrt_d) / (2.0f * a);
99 if(t[0] < EPSILON && t[1] < EPSILON) {
112 float c[3] = {0, 0, 0};
115 mat4_xform3(c, o->ob.xform, c);
117 x = ray->x + ray->dx * t[i];
118 y = ray->y + ray->dy * t[i];
119 z = ray->z + ray->dz * t[i];
121 hit->end[i].t = t[i];
125 hit->end[i].nx = (x - c[0]) / o->sph.rad;
126 hit->end[i].ny = (y - c[1]) / o->sph.rad;
127 hit->end[i].nz = (z - c[2]) / o->sph.rad;
133 struct hinterv *ray_cylinder(struct ray *ray, csg_object *o)
135 struct ray locray = *ray;
137 xform_ray(&locray, o->ob.inv_xform);
141 struct hinterv *ray_plane(struct ray *ray, csg_object *o)
143 float vx, vy, vz, ndotv, ndotr, t;
145 struct ray locray = *ray;
147 xform_ray(&locray, o->ob.inv_xform);
149 ndotr = o->plane.nx * locray.dx + o->plane.ny * locray.dy + o->plane.nz * locray.dz;
150 if(fabs(ndotr) < EPSILON) return 0;
152 vx = o->plane.nx * o->plane.d - locray.x;
153 vy = o->plane.ny * o->plane.d - locray.y;
154 vz = o->plane.nz * o->plane.d - locray.z;
156 ndotv = o->plane.nx * vx + o->plane.ny * vy + o->plane.nz * vz;
164 hit->o = hit->end[0].o = hit->end[1].o = o;
166 hit->end[0].x = ray->x + ray->dx * t;
167 hit->end[0].y = ray->y + ray->dy * t;
168 hit->end[0].z = ray->z + ray->dz * t;
170 hit->end[0].nx = hit->end[1].nx = o->plane.nx;
171 hit->end[0].ny = hit->end[1].ny = o->plane.ny;
172 hit->end[0].nz = hit->end[1].nz = o->plane.nz;
174 hit->end[1].t = FLT_MAX;
175 hit->end[1].x = ray->x + ray->dx * 10000.0f;
176 hit->end[1].y = ray->y + ray->dy * 10000.0f;
177 hit->end[1].z = ray->z + ray->dz * 10000.0f;
181 struct hinterv *ray_csg_un(struct ray *ray, csg_object *o)
183 struct hinterv *hita, *hitb, *res;
185 hita = ray_intersect(ray, o->un.a);
186 hitb = ray_intersect(ray, o->un.b);
188 if(!hita) return hitb;
189 if(!hitb) return hita;
191 res = interval_union(hita, hitb);
197 struct hinterv *ray_csg_isect(struct ray *ray, csg_object *o)
199 struct hinterv *hita, *hitb, *res;
201 hita = ray_intersect(ray, o->isect.a);
202 hitb = ray_intersect(ray, o->isect.b);
210 res = interval_isect(hita, hitb);
216 struct hinterv *ray_csg_sub(struct ray *ray, csg_object *o)
218 struct hinterv *hita, *hitb, *res;
220 hita = ray_intersect(ray, o->un.a);
221 hitb = ray_intersect(ray, o->un.b);
224 if(!hitb) return hita;
226 res = interval_sub(hita, hitb);
233 void xform_ray(struct ray *ray, float *mat)
237 mat4_copy(m3x3, mat);
240 mat4_xform3(&ray->x, mat, &ray->x);
241 mat4_xform3(&ray->dx, m3x3, &ray->dx);
244 static void flip_hit(struct hit *hit)
251 static struct hinterv *interval_union(struct hinterv *a, struct hinterv *b)
253 struct hinterv *res, *res2;
255 if(a->end[0].t > b->end[1].t || a->end[1].t < b->end[0].t) {
260 if(a->end[0].t < b->end[0].t) {
273 res->end[0] = a->end[0].t <= b->end[0].t ? a->end[0] : b->end[0];
274 res->end[1] = a->end[1].t >= b->end[1].t ? a->end[1] : b->end[1];
278 static struct hinterv *interval_isect(struct hinterv *a, struct hinterv *b)
282 if(a->end[0].t > b->end[1].t || a->end[1].t < b->end[0].t) {
289 if(a->end[0].t <= b->end[0].t && a->end[1].t >= b->end[1].t) {
295 if(a->end[0].t > b->end[0].t && a->end[1].t < b->end[1].t) {
302 /* partial overlap */
303 if(a->end[0].t < b->end[0].t) {
304 res->end[0] = b->end[0];
305 res->end[1] = a->end[1];
307 res->end[0] = a->end[0];
308 res->end[1] = b->end[1];
313 static struct hinterv *interval_sub(struct hinterv *a, struct hinterv *b)
317 if(a->end[0].t >= b->end[0].t && a->end[1].t <= b->end[1].t) {
322 if(a->end[0].t < b->end[0].t && a->end[1].t > b->end[1].t) {
325 res->end[0] = a->end[0];
326 res->end[1] = b->end[0];
327 res->next->end[0] = b->end[1];
328 res->next->end[1] = a->end[1];
334 if(a->end[0].t > b->end[1].t || a->end[1].t < b->end[0].t) {
341 /* partial overlap */
342 if(a->end[0].t <= b->end[0].t) {
343 res->end[0] = a->end[0];
344 res->end[1] = b->end[0];
346 res->end[0] = b->end[1];
347 res->end[1] = a->end[1];
350 flip_hit(res->end + 0);
351 flip_hit(res->end + 1);