#include <stdio.h>
#include <stdlib.h>
#include <math.h>
+#include <float.h>
#include "geom.h"
#include "matrix.h"
#define EPSILON 1e-6f
+static struct hinterv *interval_union(struct hinterv *a, struct hinterv *b);
+static struct hinterv *interval_isect(struct hinterv *a, struct hinterv *b);
+static struct hinterv *interval_sub(struct hinterv *a, struct hinterv *b);
+
/* TODO custom hit allocator */
-struct hit *alloc_hit(void)
+struct hinterv *alloc_hit(void)
{
- struct hit *hit = calloc(sizeof *hit, 1);
+ struct hinterv *hit = calloc(sizeof *hit, 1);
if(!hit) {
perror("failed to allocate ray hit node");
abort();
return hit;
}
-struct hit *alloc_hits(int n)
+struct hinterv *alloc_hits(int n)
{
int i;
- struct hit *list = 0;
+ struct hinterv *list = 0;
for(i=0; i<n; i++) {
- struct hit *hit = alloc_hit();
+ struct hinterv *hit = alloc_hit();
hit->next = list;
list = hit;
}
}
-void free_hit(struct hit *hit)
+void free_hit(struct hinterv *hit)
{
free(hit);
}
-void free_hit_list(struct hit *hit)
+void free_hit_list(struct hinterv *hit)
{
while(hit) {
- struct hit *tmp = hit;
+ struct hinterv *tmp = hit;
hit = hit->next;
free_hit(tmp);
}
}
-struct hit *ray_intersect(struct ray *ray, csg_object *o)
+struct hinterv *ray_intersect(struct ray *ray, csg_object *o)
{
switch(o->ob.type) {
case OB_SPHERE:
return 0;
}
-struct hit *ray_sphere(struct ray *ray, csg_object *o)
+struct hinterv *ray_sphere(struct ray *ray, csg_object *o)
{
int i;
float a, b, c, d, sqrt_d, t[2], sq_rad, tmp;
- struct hit *hit, *hitlist;
+ struct hinterv *hit;
struct ray locray = *ray;
if(o->sph.rad == 0.0f) {
t[1] = tmp;
}
- hitlist = hit = alloc_hits(2);
+ hit = alloc_hits(1);
+ hit->o = o;
for(i=0; i<2; i++) {
float c[3] = {0, 0, 0};
- mat4_xform3(c, o->ob.xform, c);
+ float x, y, z;
- hit->t = t[i];
- hit->x = ray->x + ray->dx * t[i];
- hit->y = ray->y + ray->dy * t[i];
- hit->z = ray->z + ray->dz * t[i];
- hit->nx = (hit->x - c[0]) / o->sph.rad;
- hit->ny = (hit->y - c[1]) / o->sph.rad;
- hit->nz = (hit->z - c[2]) / o->sph.rad;
- hit->o = o;
+ mat4_xform3(c, o->ob.xform, c);
- hit = hit->next;
+ x = ray->x + ray->dx * t[i];
+ y = ray->y + ray->dy * t[i];
+ z = ray->z + ray->dz * t[i];
+
+ hit->end[i].t = t[i];
+ hit->end[i].x = x;
+ hit->end[i].y = y;
+ hit->end[i].z = z;
+ hit->end[i].nx = (x - c[0]) / o->sph.rad;
+ hit->end[i].ny = (y - c[1]) / o->sph.rad;
+ hit->end[i].nz = (z - c[2]) / o->sph.rad;
+ hit->end[i].o = o;
}
- return hitlist;
+ return hit;
}
-struct hit *ray_cylinder(struct ray *ray, csg_object *o)
+struct hinterv *ray_cylinder(struct ray *ray, csg_object *o)
{
struct ray locray = *ray;
return 0; /* TODO */
}
-struct hit *ray_plane(struct ray *ray, csg_object *o)
+struct hinterv *ray_plane(struct ray *ray, csg_object *o)
{
float vx, vy, vz, ndotv, ndotr, t;
- struct hit *hit = 0;
+ struct hinterv *hit;
struct ray locray = *ray;
xform_ray(&locray, o->ob.inv_xform);
ndotv = o->plane.nx * vx + o->plane.ny * vy + o->plane.nz * vz;
t = ndotv / ndotr;
-
- if(t > EPSILON) {
- hit = alloc_hits(1);
- hit->t = t;
- hit->x = ray->x + ray->dx * t;
- hit->y = ray->y + ray->dy * t;
- hit->z = ray->z + ray->dz * t;
- hit->nx = o->plane.nx;
- hit->ny = o->plane.ny;
- hit->nz = o->plane.nz;
- hit->o = o;
+ if(t < EPSILON) {
+ return 0;
}
+
+ hit = alloc_hits(1);
+ hit->o = hit->end[0].o = hit->end[1].o = o;
+ hit->end[0].t = t;
+ hit->end[0].x = ray->x + ray->dx * t;
+ hit->end[0].y = ray->y + ray->dy * t;
+ hit->end[0].z = ray->z + ray->dz * t;
+
+ hit->end[0].nx = hit->end[1].nx = o->plane.nx;
+ hit->end[0].ny = hit->end[1].ny = o->plane.ny;
+ hit->end[0].nz = hit->end[1].nz = o->plane.nz;
+
+ hit->end[1].t = FLT_MAX;
+ hit->end[1].x = ray->x + ray->dx * 10000.0f;
+ hit->end[1].y = ray->y + ray->dy * 10000.0f;
+ hit->end[1].z = ray->z + ray->dz * 10000.0f;
return hit;
}
-struct hit *ray_csg_un(struct ray *ray, csg_object *o)
+struct hinterv *ray_csg_un(struct ray *ray, csg_object *o)
{
- struct hit *hita, *hitb;
+ struct hinterv *hita, *hitb, *res;
hita = ray_intersect(ray, o->un.a);
hitb = ray_intersect(ray, o->un.b);
if(!hita) return hitb;
if(!hitb) return hita;
- if(hita->t < hitb->t) {
+ res = interval_union(hita, hitb);
+ free_hit_list(hita);
+ free_hit_list(hitb);
+ return res;
+}
+
+struct hinterv *ray_csg_isect(struct ray *ray, csg_object *o)
+{
+ struct hinterv *hita, *hitb, *res;
+
+ hita = ray_intersect(ray, o->isect.a);
+ hitb = ray_intersect(ray, o->isect.b);
+
+ if(!hita || !hitb) {
+ free_hit_list(hita);
free_hit_list(hitb);
- return hita;
+ return 0;
}
+
+ res = interval_isect(hita, hitb);
free_hit_list(hita);
- return hitb;
+ free_hit_list(hitb);
+ return res;
}
-struct hit *ray_csg_isect(struct ray *ray, csg_object *o)
+struct hinterv *ray_csg_sub(struct ray *ray, csg_object *o)
{
- return 0;
+ struct hinterv *hita, *hitb, *res;
+
+ hita = ray_intersect(ray, o->un.a);
+ hitb = ray_intersect(ray, o->un.b);
+
+ if(!hita) return 0;
+ if(!hitb) return hita;
+
+ res = interval_sub(hita, hitb);
+ free_hit_list(hita);
+ free_hit_list(hitb);
+ return res;
}
-static struct hit *first(struct hit *hlist)
+
+void xform_ray(struct ray *ray, float *mat)
{
- return hlist;
+ float m3x3[16];
+
+ mat4_copy(m3x3, mat);
+ mat4_upper3x3(m3x3);
+
+ mat4_xform3(&ray->x, mat, &ray->x);
+ mat4_xform3(&ray->dx, m3x3, &ray->dx);
+}
+
+static void flip_hit(struct hit *hit)
+{
+ hit->nx = -hit->nx;
+ hit->ny = -hit->ny;
+ hit->nz = -hit->nz;
}
-static struct hit *last(struct hit *hlist)
+static struct hinterv *interval_union(struct hinterv *a, struct hinterv *b)
{
- while(hlist->next) {
- hlist = hlist->next;
+ struct hinterv *res, *res2;
+
+ if(a->end[0].t > b->end[1].t || a->end[1].t < b->end[0].t) {
+ /* disjoint */
+ res = alloc_hits(2);
+ res2 = res->next;
+
+ if(a->end[0].t < b->end[0].t) {
+ *res = *a;
+ *res2 = *b;
+ } else {
+ *res = *b;
+ *res2 = *a;
+ }
+ res->next = res2;
+ res2->next = 0;
+ return res;
}
- return hlist;
+
+ res = alloc_hits(1);
+ res->end[0] = a->end[0].t <= b->end[0].t ? a->end[0] : b->end[0];
+ res->end[1] = a->end[1].t >= b->end[1].t ? a->end[1] : b->end[1];
+ return res;
}
-struct hit *ray_csg_sub(struct ray *ray, csg_object *o)
+static struct hinterv *interval_isect(struct hinterv *a, struct hinterv *b)
{
- struct hit *hita, *hitb, *lasthit, tmp;
+ struct hinterv *res;
- hita = ray_intersect(ray, o->sub.a);
- hitb = ray_intersect(ray, o->sub.b);
+ if(a->end[0].t > b->end[1].t || a->end[1].t < b->end[0].t) {
+ /* disjoint */
+ return 0;
+ }
- if(!hita) return 0;
- if(!hitb) return hita;
+ res = alloc_hits(1);
- if(first(hita)->t < first(hitb)->t) {
- free_hit_list(hitb);
- return hita;
+ if(a->end[0].t <= b->end[0].t && a->end[1].t >= b->end[1].t) {
+ /* B in A */
+ *res = *a;
+ res->next = 0;
+ return res;
+ }
+ if(a->end[0].t > b->end[0].t && a->end[1].t < b->end[1].t) {
+ /* A in B */
+ *res = *b;
+ res->next = 0;
+ return res;
}
- if(first(hita)->t < (lasthit = last(hitb))->t) {
- /* overlapping */
- tmp = *hitb;
- *hitb = *lasthit;
- free_hit_list(tmp.next);
+ /* partial overlap */
+ if(a->end[0].t < b->end[1].t) {
+ res->end[0] = b->end[1];
+ res->end[1] = a->end[0];
+ } else {
+ res->end[0] = a->end[1];
+ res->end[1] = a->end[0];
+ }
+ return res;
+}
- hitb->nx = -hitb->nx;
- hitb->ny = -hitb->ny;
- hitb->nz = -hitb->nz;
+static struct hinterv *interval_sub(struct hinterv *a, struct hinterv *b)
+{
+ struct hinterv *res;
- free_hit_list(hita);
- return hitb;
+ if(a->end[0].t >= b->end[0].t && a->end[1].t <= b->end[1].t) {
+ /* A in B */
+ return 0;
}
- free_hit_list(hitb);
- return hita;
-}
+ if(a->end[0].t < b->end[0].t && a->end[1].t > b->end[1].t) {
+ /* B in A */
+ res = alloc_hits(2);
+ res->end[0] = a->end[0];
+ res->end[1] = b->end[0];
+ res->next->end[0] = b->end[1];
+ res->next->end[1] = a->end[1];
+ return res;
+ }
+ res = alloc_hits(1);
-void xform_ray(struct ray *ray, float *mat)
-{
- float m3x3[16];
+ if(a->end[0].t > b->end[1].t || a->end[1].t < b->end[0].t) {
+ /* disjoint */
+ *res = *a;
+ res->next = 0;
+ return res;
+ }
- mat4_copy(m3x3, mat);
- mat4_upper3x3(m3x3);
+ /* partial overlap */
+ if(a->end[0].t <= b->end[0].t) {
+ res->end[0] = a->end[0];
+ res->end[1] = b->end[0];
+ } else {
+ res->end[0] = b->end[1];
+ res->end[1] = a->end[1];
+ }
- mat4_xform3(&ray->x, mat, &ray->x);
- mat4_xform3(&ray->dx, m3x3, &ray->dx);
+ flip_hit(res->end + 0);
+ flip_hit(res->end + 1);
+ return res;
}
projects / csgray / blobdiff