X-Git-Url: http://git.mutantstargoat.com/user/nuclear/?p=csgray;a=blobdiff_plain;f=src%2Fgeom.c;h=bd340bf1ddd2e914f19f403b46866aa92ea88793;hp=ee7cb7da591213709f6a0933185c3806be8fdc68;hb=07f86df1b104515376419c7a214253fb435fc396;hpb=07ca36e28aa10804ba5a544276eb5a25f8105e0f

diff --git a/src/geom.c b/src/geom.c
index ee7cb7d..bd340bf 100644
--- a/src/geom.c
+++ b/src/geom.c
@@ -1,13 +1,20 @@
 #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();
@@ -15,21 +22,35 @@ struct hit *alloc_hit(void)
 	return hit;
 }
 
-void free_hit(struct hit *hit)
+struct hinterv *alloc_hits(int n)
+{
+	int i;
+	struct hinterv *list = 0;
+
+	for(i=0; i<n; i++) {
+		struct hinterv *hit = alloc_hit();
+		hit->next = list;
+		list = hit;
+	}
+	return list;
+}
+
+
+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:
@@ -50,10 +71,11 @@ struct hit *ray_intersect(struct ray *ray, csg_object *o)
 	return 0;
 }
 
-struct hit *ray_sphere(struct ray *ray, csg_object *o)
+struct hinterv *ray_sphere(struct ray *ray, csg_object *o)
 {
-	float a, b, c, d, sqrt_d, t0, t1, t, sq_rad;
-	struct hit *hit;
+	int i;
+	float a, b, c, d, sqrt_d, t[2], sq_rad, tmp;
+	struct hinterv *hit;
 	struct ray locray = *ray;
 
 	if(o->sph.rad == 0.0f) {
@@ -68,30 +90,47 @@ struct hit *ray_sphere(struct ray *ray, csg_object *o)
 	c = (locray.x * locray.x + locray.y * locray.y + locray.z * locray.z) - sq_rad;
 
 	d = b * b - 4.0f * a * c;
-	if(d < 1e-6) return 0;
+	if(d < EPSILON) return 0;
 
 	sqrt_d = sqrt(d);
-	t0 = (-b + sqrt_d) / (2.0f * a);
-	t1 = (-b - sqrt_d) / (2.0f * a);
-
-	if(t0 < 1e-6) t0 = t1;
-	if(t1 < 1e-6) t1 = t0;
-	t = t0 < t1 ? t0 : t1;
-	if(t < 1e-6) return 0;
-
-	hit = alloc_hit();
-	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 = hit->x / o->sph.rad;
-	hit->ny = hit->y / o->sph.rad;
-	hit->nz = hit->z / o->sph.rad;
+	t[0] = (-b + sqrt_d) / (2.0f * a);
+	t[1] = (-b - sqrt_d) / (2.0f * a);
+
+	if(t[0] < EPSILON && t[1] < EPSILON) {
+		return 0;
+	}
+
+	if(t[1] < t[0]) {
+		tmp = t[0];
+		t[0] = t[1];
+		t[1] = tmp;
+	}
+
+	hit = alloc_hits(1);
 	hit->o = o;
+	for(i=0; i<2; i++) {
+		float c[3] = {0, 0, 0};
+		float x, y, z;
+
+		mat4_xform3(c, o->ob.xform, c);
+
+		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 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;
 
@@ -99,64 +138,95 @@ struct hit *ray_cylinder(struct ray *ray, csg_object *o)
 	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);
 
+	ndotr = o->plane.nx * locray.dx + o->plane.ny * locray.dy + o->plane.nz * locray.dz;
+	if(fabs(ndotr) < EPSILON) return 0;
+
 	vx = o->plane.nx * o->plane.d - locray.x;
 	vy = o->plane.ny * o->plane.d - locray.y;
 	vz = o->plane.nz * o->plane.d - locray.z;
 
 	ndotv = o->plane.nx * vx + o->plane.ny * vy + o->plane.nz * vz;
-	if(fabs(ndotv) < 1e-6) return 0;
 
-	ndotr = o->plane.nx * locray.dx + o->plane.ny * locray.dy + o->plane.nz * locray.dz;
-	t = ndotr / ndotv;
-
-	if(t > 1e-6) {
-		hit = alloc_hit();
-		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;
+	t = ndotv / ndotr;
+	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.a);
+	hitb = ray_intersect(ray, o->un.b);
 
 	if(!hita) return hitb;
 	if(!hitb) return hita;
 
-	if(hita->t < hitb->t) {
-		free_hit(hitb);
-		return hita;
-	}
-	free_hit(hita);
-	return hitb;
+	res = interval_union(hita, hitb);
+	free_hit_list(hita);
+	free_hit_list(hitb);
+	return res;
 }
 
-struct hit *ray_csg_isect(struct ray *ray, csg_object *o)
+struct hinterv *ray_csg_isect(struct ray *ray, csg_object *o)
 {
-	return 0;
+	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 0;
+	}
+
+	res = interval_isect(hita, hitb);
+	free_hit_list(hita);
+	free_hit_list(hitb);
+	return res;
 }
 
-struct hit *ray_csg_sub(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;
 }
 
 
@@ -170,3 +240,114 @@ void xform_ray(struct ray *ray, float *mat)
 	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 hinterv *interval_union(struct hinterv *a, struct hinterv *b)
+{
+	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;
+	}
+
+	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;
+}
+
+static struct hinterv *interval_isect(struct hinterv *a, struct hinterv *b)
+{
+	struct hinterv *res;
+
+	if(a->end[0].t > b->end[1].t || a->end[1].t < b->end[0].t) {
+		/* disjoint */
+		return 0;
+	}
+
+	res = alloc_hits(1);
+
+	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;
+	}
+
+	/* partial overlap */
+	if(a->end[0].t < b->end[0].t) {
+		res->end[0] = b->end[0];
+		res->end[1] = a->end[1];
+	} else {
+		res->end[0] = a->end[0];
+		res->end[1] = b->end[1];
+	}
+	return res;
+}
+
+static struct hinterv *interval_sub(struct hinterv *a, struct hinterv *b)
+{
+	struct hinterv *res;
+
+	if(a->end[0].t >= b->end[0].t && a->end[1].t <= b->end[1].t) {
+		/* A in B */
+		return 0;
+	}
+
+	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);
+
+	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;
+	}
+
+	/* 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];
+	}
+
+	flip_hit(res->end + 0);
+	flip_hit(res->end + 1);
+	return res;
+}