From f4f8d2071921bb09ff0408fe70f0599cb1263319 Mon Sep 17 00:00:00 2001 From: John Tsiombikas Date: Tue, 27 Mar 2018 22:36:59 +0300 Subject: [PATCH] subtraction seems to work now --- src/csgray.c | 24 +++++- src/geom.c | 268 +++++++++++++++++++++++++++++++++++++++++----------------- src/geom.h | 28 +++--- src/main.c | 2 +- 4 files changed, 227 insertions(+), 95 deletions(-) diff --git a/src/csgray.c b/src/csgray.c index fe0228a..44c7eb9 100644 --- a/src/csgray.c +++ b/src/csgray.c @@ -350,7 +350,7 @@ static void shade(float *col, struct ray *ray, struct hit *hit) sray.dy = ldir[1]; sray.dz = ldir[2]; - if(1) {//!find_intersection(&sray, &tmphit) || tmphit.t > 1.0f) { + if(!find_intersection(&sray, &tmphit) || tmphit.t > 1.0f) { if((len = sqrt(ldir[0] * ldir[0] + ldir[1] * ldir[1] + ldir[2] * ldir[2])) != 0.0f) { float s = 1.0f / len; ldir[0] *= s; @@ -383,16 +383,32 @@ static void background(float *col, struct ray *ray) static int find_intersection(struct ray *ray, struct hit *best) { + int idx = 0; csg_object *o; - struct hit *hit; + struct hinterv *hit, *it; best->t = FLT_MAX; best->o = 0; o = oblist; while(o) { - if((hit = ray_intersect(ray, o)) && hit->t < best->t) { - *best = *hit; + if((hit = ray_intersect(ray, o))) { + it = hit; + while(it) { + if(it->end[0].t > 1e-6) { + idx = 0; + break; + } + if(it->end[1].t > 1e-6) { + idx = 1; + break; + } + it = it->next; + } + + if(it && it->end[idx].t < best->t) { + *best = it->end[idx]; + } } free_hit_list(hit); o = o->ob.next; diff --git a/src/geom.c b/src/geom.c index 1961aed..341e7c3 100644 --- a/src/geom.c +++ b/src/geom.c @@ -1,15 +1,20 @@ #include #include #include +#include #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(); @@ -17,13 +22,13 @@ struct hit *alloc_hit(void) 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; inext = list; list = hit; } @@ -31,21 +36,21 @@ struct hit *alloc_hits(int n) } -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: @@ -66,11 +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) { 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) { @@ -101,26 +106,31 @@ struct hit *ray_sphere(struct ray *ray, csg_object *o) 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; @@ -128,10 +138,10 @@ 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); @@ -146,24 +156,31 @@ struct hit *ray_plane(struct ray *ray, csg_object *o) 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); @@ -171,73 +188,166 @@ struct hit *ray_csg_un(struct ray *ray, csg_object *o) 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; } diff --git a/src/geom.h b/src/geom.h index 7405fa3..e3865d2 100644 --- a/src/geom.h +++ b/src/geom.h @@ -14,22 +14,28 @@ struct hit { float x, y, z; float nx, ny, nz; csg_object *o; +}; + +struct hinterv { + struct hit end[2]; + csg_object *o; - struct hit *next; + struct hinterv *next; }; -struct hit *alloc_hit(void); -void free_hit(struct hit *hit); -void free_hit_list(struct hit *hit); -struct hit *ray_intersect(struct ray *ray, csg_object *o); +struct hinterv *alloc_hits(int n); +void free_hit(struct hinterv *hv); +void free_hit_list(struct hinterv *hv); + +struct hinterv *ray_intersect(struct ray *ray, csg_object *o); -struct hit *ray_sphere(struct ray *ray, csg_object *o); -struct hit *ray_cylinder(struct ray *ray, csg_object *o); -struct hit *ray_plane(struct ray *ray, csg_object *o); -struct hit *ray_csg_un(struct ray *ray, csg_object *o); -struct hit *ray_csg_isect(struct ray *ray, csg_object *o); -struct hit *ray_csg_sub(struct ray *ray, csg_object *o); +struct hinterv *ray_sphere(struct ray *ray, csg_object *o); +struct hinterv *ray_cylinder(struct ray *ray, csg_object *o); +struct hinterv *ray_plane(struct ray *ray, csg_object *o); +struct hinterv *ray_csg_un(struct ray *ray, csg_object *o); +struct hinterv *ray_csg_isect(struct ray *ray, csg_object *o); +struct hinterv *ray_csg_sub(struct ray *ray, csg_object *o); void xform_ray(struct ray *ray, float *mat); diff --git a/src/main.c b/src/main.c index d6aac1c..301966f 100644 --- a/src/main.c +++ b/src/main.c @@ -48,7 +48,7 @@ int main(int argc, char **argv) csg_color(obj, 0.4, 0.7, 0.4); csg_add_object(obj); - obj = csg_null(-6, 10, 10); + obj = csg_null(-4, 10, 10); csg_emission(obj, 80, 80, 80); csg_add_object(obj); -- 1.7.10.4