From: John Tsiombikas Date: Tue, 27 Mar 2018 11:25:18 +0000 (+0300) Subject: almost there X-Git-Url: http://git.mutantstargoat.com/user/nuclear/?p=csgray;a=commitdiff_plain;h=07ca36e28aa10804ba5a544276eb5a25f8105e0f almost there --- diff --git a/.gitignore b/.gitignore index 9c71b18..2b603fd 100644 --- a/.gitignore +++ b/.gitignore @@ -2,3 +2,4 @@ *.d *.swp csgray +*.ppm diff --git a/src/csgimpl.h b/src/csgimpl.h new file mode 100644 index 0000000..d6cb7a4 --- /dev/null +++ b/src/csgimpl.h @@ -0,0 +1,67 @@ +#ifndef CSGIMPL_H_ +#define CSGIMPL_H_ + +#include "csgray.h" + +enum { + OB_NULL, + OB_SPHERE, + OB_CYLINDER, + OB_PLANE, + OB_BOX, + OB_UNION, + OB_INTERSECTION, + OB_SUBTRACTION +}; + +struct object { + int type; + + float r, g, b; + float emr, emg, emb; + float roughness; + float opacity; + + float xform[16], inv_xform[16]; + + csg_object *next; + + void (*destroy)(csg_object*); +}; + +struct sphere { + struct object ob; + float rad; +}; + +struct cylinder { + struct object ob; + float rad; +}; + +struct plane { + struct object ob; + float nx, ny, nz; + float d; +}; + +struct csgop { + struct object ob; + csg_object *a, *b; +}; + +union csg_object { + struct object ob; + struct sphere sph; + struct cylinder cyl; + struct plane plane; + struct csgop un, isect, sub; +}; + +struct camera { + float x, y, z; + float tx, ty, tz; + float fov; +}; + +#endif /* CSGIMPL_H_ */ diff --git a/src/csgray.c b/src/csgray.c index 0713c06..47f2a8b 100644 --- a/src/csgray.c +++ b/src/csgray.c @@ -2,67 +2,22 @@ #include #include #include -#include "csgray.h" +#include "csgimpl.h" #include "matrix.h" +#include "geom.h" -enum { - OB_NULL, - OB_SPHERE, - OB_CYLINDER, - OB_PLANE, - OB_BOX, - OB_UNION, - OB_INTERSECTION, - OB_SUBTRACTION -}; - -struct object { - int type; - - float r, g, b; - float emr, emg, emb; - float roughness; - float opacity; - - float xform[16]; - - struct object *next; - struct object *clist, *ctail; - struct object *parent; -}; - -struct sphere { - struct object ob; - float rad; -}; - -struct plane { - struct object ob; - float nx, ny, nz; - float d; -}; - -union csg_object { - struct object ob; - struct sphere sph; - struct plane plane; -}; - -struct camera { - float x, y, z; - float tx, ty, tz; - float fov; -}; +static void calc_primary_ray(struct ray *ray, int x, int y, int w, int h, float aspect); +static int ray_trace(struct ray *ray, float *col); +static void shade(float *col, struct ray *ray, struct hit *hit); +static void background(float *col, struct ray *ray); +static int find_intersection(struct ray *ray, struct hit *best); static struct camera cam; -static csg_object *root; +static csg_object *oblist; int csg_init(void) { - if(!(root = csg_null(0, 0, 0))) { - return -1; - } - + oblist = 0; csg_view(0, 0, 5, 0, 0, 0); csg_fov(50); @@ -71,8 +26,12 @@ int csg_init(void) void csg_destroy(void) { - csg_free_object(root); - root = 0; + while(oblist) { + csg_object *o = oblist; + oblist = oblist->ob.next; + csg_free_object(o); + } + oblist = 0; } void csg_view(float x, float y, float z, float tx, float ty, float tz) @@ -101,63 +60,47 @@ int csg_save(const char *fname) return 0; /* TODO */ } -#define OBPTR(o) ((struct object*)(o)) - -void csg_add_object(csg_object *parent, csg_object *child) +void csg_add_object(csg_object *o) { - if(!parent) { - parent = root; - } - - if(parent->ob.clist) { - parent->ob.ctail->next = OBPTR(child); - parent->ob.ctail = OBPTR(child); - } else { - parent->ob.clist = parent->ob.ctail = OBPTR(child); - } - child->ob.parent = OBPTR(parent); + o->ob.next = oblist; + oblist = o; } -void csg_remove_object(csg_object *parent, csg_object *child) +int csg_remove_object(csg_object *o) { - csg_object *c; + csg_object dummy, *n; - if(!parent) { - parent = root; - } + dummy.ob.next = oblist; + n = &dummy; - c = (csg_object*)parent->ob.clist; - while(c->ob.next) { - if(c->ob.next == OBPTR(child)) { - c->ob.next = child->ob.next; - child->ob.next = 0; - child->ob.parent = 0; - return; + while(n->ob.next) { + if(n->ob.next == o) { + n->ob.next = o->ob.next; + return 1; } - c = (csg_object*)c->ob.next; + n = n->ob.next; } + return 0; } void csg_free_object(csg_object *o) { - csg_object *c = (csg_object*)o->ob.clist; - while(c) { - csg_object *tmp = c; - c = (csg_object*)c->ob.next; - csg_free_object(tmp); + if(o->ob.destroy) { + o->ob.destroy(o); } free(o); } -static union csg_object *alloc_object(void) +static union csg_object *alloc_object(int type) { csg_object *o; if(!(o = calloc(sizeof *o, 1))) { return 0; } - o->ob.type = OB_NULL; + o->ob.type = type; mat4_identity(o->ob.xform); + mat4_identity(o->ob.inv_xform); csg_emission(o, 0, 0, 0); csg_color(o, 1, 1, 1); @@ -169,29 +112,74 @@ static union csg_object *alloc_object(void) csg_object *csg_null(float x, float y, float z) { - return alloc_object(); + return alloc_object(OB_NULL); } csg_object *csg_sphere(float x, float y, float z, float r) { csg_object *o; - if(!(o = alloc_object())) { + if(!(o = alloc_object(OB_SPHERE))) { return 0; } o->sph.rad = r; mat4_translation(o->ob.xform, x, y, z); + mat4_copy(o->ob.inv_xform, o->ob.xform); + mat4_inverse(o->ob.inv_xform); return o; } csg_object *csg_cylinder(float x0, float y0, float z0, float x1, float y1, float z1, float r) { - return 0; + csg_object *o; + float dx, dy, dz; + int major; + + if(!(o = alloc_object(OB_CYLINDER))) { + return 0; + } + + dx = x1 - x0; + dy = y1 - y0; + dz = z1 - z0; + + if(fabs(dx) > fabs(dy) && fabs(dx) > fabs(dz)) { + major = 0; + } else if(fabs(dy) > fabs(dz)) { + major = 1; + } else { + major = 2; + } + + o->cyl.rad = r; + mat4_lookat(o->ob.xform, x0, y0, z0, x1, y1, z1, 0, major == 2 ? 1 : 0, major == 2 ? 0 : 1); + mat4_copy(o->ob.inv_xform, o->ob.xform); + mat4_inverse(o->ob.inv_xform); + return o; } csg_object *csg_plane(float x, float y, float z, float nx, float ny, float nz) { + csg_object *o; + float len; + + if(!(o = alloc_object(OB_PLANE))) { + return 0; + } + + len = sqrt(nx * nx + ny * ny + nz * nz); + if(len != 0.0f) { + float s = 1.0f / len; + nx *= s; + ny *= s; + nz *= s; + } + + o->plane.nx = nx; + o->plane.ny = ny; + o->plane.nz = nz; + o->plane.d = x * nx + y * ny + z * nz; return 0; } @@ -200,44 +188,144 @@ csg_object *csg_box(float x, float y, float z, float xsz, float ysz, float zsz) return 0; } - csg_object *csg_union(csg_object *a, csg_object *b) { - return 0; + csg_object *o; + + if(!(o = alloc_object(OB_UNION))) { + return 0; + } + o->un.a = a; + o->un.b = b; + return o; } csg_object *csg_intersection(csg_object *a, csg_object *b) { - return 0; + csg_object *o; + + if(!(o = alloc_object(OB_INTERSECTION))) { + return 0; + } + o->isect.a = a; + o->isect.b = b; + return o; } csg_object *csg_subtraction(csg_object *a, csg_object *b) { - return 0; + csg_object *o; + + if(!(o = alloc_object(OB_SUBTRACTION))) { + return 0; + } + o->sub.a = a; + o->sub.b = b; + return o; } void csg_emission(csg_object *o, float r, float g, float b) { + o->ob.emr = r; + o->ob.emg = g; + o->ob.emb = b; } void csg_color(csg_object *o, float r, float g, float b) { + o->ob.r = r; + o->ob.g = g; + o->ob.b = b; } void csg_roughness(csg_object *o, float r) { + o->ob.roughness = r; } void csg_opacity(csg_object *o, float p) { + o->ob.opacity = p; } -void csg_render_pixel(int x, int y, float *color) +void csg_render_pixel(int x, int y, int width, int height, float aspect, float *color) { + struct ray ray; + + calc_primary_ray(&ray, x, y, width, height, aspect); + ray_trace(&ray, color); } void csg_render_image(float *pixels, int width, int height) { + int i, j; + float aspect = (float)width / (float)height; + + for(i=0; ix = px; + ray->y = py; + ray->z = cam.z; + + ray->dx = ray->dy = 0.0f; + ray->dz = -1.0f; +} + +static int ray_trace(struct ray *ray, float *col) +{ + struct hit hit; + + if(!find_intersection(ray, &hit)) { + background(col, ray); + return 0; + } + + shade(col, ray, &hit); + return 1; +} + +static void shade(float *col, struct ray *ray, struct hit *hit) +{ + col[0] = 1.0f; + col[1] = col[2] = 0.0f; +} + +static void background(float *col, struct ray *ray) +{ + col[0] = col[1] = col[2] = 0.0f; +} + +static int find_intersection(struct ray *ray, struct hit *best) +{ + csg_object *o; + struct hit *hit; + + best->t = 1e-6f; + best->o = 0; + + o = oblist; + while(o) { + if((hit = ray_intersect(ray, o)) && hit->t < best->t) { + *best = *hit; + } + free_hit(hit); + o = o->ob.next; + } + + return best->o != 0; } diff --git a/src/csgray.h b/src/csgray.h index 651b64e..196ecc2 100644 --- a/src/csgray.h +++ b/src/csgray.h @@ -12,8 +12,8 @@ void csg_fov(float fov); int csg_load(const char *fname); int csg_save(const char *fname); -void csg_add_object(csg_object *parent, csg_object *child); -void csg_remove_object(csg_object *parent, csg_object *child); +void csg_add_object(csg_object *o); +int csg_remove_object(csg_object *o); void csg_free_object(csg_object *o); csg_object *csg_null(float x, float y, float z); @@ -31,7 +31,7 @@ void csg_color(csg_object *o, float r, float g, float b); void csg_roughness(csg_object *o, float r); void csg_opacity(csg_object *o, float p); -void csg_render_pixel(int x, int y, float *color); +void csg_render_pixel(int x, int y, int width, int height, float aspect, float *color); void csg_render_image(float *pixels, int width, int height); #endif /* CSGRAY_H_ */ diff --git a/src/geom.c b/src/geom.c new file mode 100644 index 0000000..ee7cb7d --- /dev/null +++ b/src/geom.c @@ -0,0 +1,172 @@ +#include +#include +#include +#include "geom.h" +#include "matrix.h" + +/* TODO custom hit allocator */ +struct hit *alloc_hit(void) +{ + struct hit *hit = calloc(sizeof *hit, 1); + if(!hit) { + perror("failed to allocate ray hit node"); + abort(); + } + return hit; +} + +void free_hit(struct hit *hit) +{ + free(hit); +} + +void free_hit_list(struct hit *hit) +{ + while(hit) { + struct hit *tmp = hit; + hit = hit->next; + free_hit(tmp); + } +} + +struct hit *ray_intersect(struct ray *ray, csg_object *o) +{ + switch(o->ob.type) { + case OB_SPHERE: + return ray_sphere(ray, o); + case OB_CYLINDER: + return ray_cylinder(ray, o); + case OB_PLANE: + return ray_plane(ray, o); + case OB_UNION: + return ray_csg_un(ray, o); + case OB_INTERSECTION: + return ray_csg_isect(ray, o); + case OB_SUBTRACTION: + return ray_csg_sub(ray, o); + default: + break; + } + return 0; +} + +struct hit *ray_sphere(struct ray *ray, csg_object *o) +{ + float a, b, c, d, sqrt_d, t0, t1, t, sq_rad; + struct hit *hit; + struct ray locray = *ray; + + if(o->sph.rad == 0.0f) { + return 0; + } + sq_rad = o->sph.rad * o->sph.rad; + + xform_ray(&locray, o->ob.inv_xform); + + a = locray.dx * locray.dx + locray.dy * locray.dy + locray.dz * locray.dz; + b = 2.0f * (locray.dx * locray.x + locray.dy * locray.y + locray.dz * locray.z); + 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; + + 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; + hit->o = o; + return hit; +} + +struct hit *ray_cylinder(struct ray *ray, csg_object *o) +{ + struct ray locray = *ray; + + xform_ray(&locray, o->ob.inv_xform); + return 0; /* TODO */ +} + +struct hit *ray_plane(struct ray *ray, csg_object *o) +{ + float vx, vy, vz, ndotv, ndotr, t; + struct hit *hit = 0; + struct ray locray = *ray; + + xform_ray(&locray, o->ob.inv_xform); + + 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; + } + return hit; +} + +struct hit *ray_csg_un(struct ray *ray, csg_object *o) +{ + struct hit *hita, *hitb; + + hita = ray_intersect(ray, o->un.a); + hitb = ray_intersect(ray, o->un.a); + + if(!hita) return hitb; + if(!hitb) return hita; + + if(hita->t < hitb->t) { + free_hit(hitb); + return hita; + } + free_hit(hita); + return hitb; +} + +struct hit *ray_csg_isect(struct ray *ray, csg_object *o) +{ + return 0; +} + +struct hit *ray_csg_sub(struct ray *ray, csg_object *o) +{ + return 0; +} + + +void xform_ray(struct ray *ray, float *mat) +{ + float m3x3[16]; + + mat4_copy(m3x3, mat); + mat4_upper3x3(m3x3); + + mat4_xform3(&ray->x, mat, &ray->x); + mat4_xform3(&ray->dx, m3x3, &ray->dx); +} diff --git a/src/geom.h b/src/geom.h new file mode 100644 index 0000000..7405fa3 --- /dev/null +++ b/src/geom.h @@ -0,0 +1,36 @@ +#ifndef GEOM_H_ +#define GEOM_H_ + +#include "csgray.h" +#include "csgimpl.h" + +struct ray { + float x, y, z; + float dx, dy, dz; +}; + +struct hit { + float t; + float x, y, z; + float nx, ny, nz; + csg_object *o; + + struct hit *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 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); + +void xform_ray(struct ray *ray, float *mat); + +#endif /* GEOM_H_ */ diff --git a/src/main.c b/src/main.c index 9837073..7cff960 100644 --- a/src/main.c +++ b/src/main.c @@ -30,9 +30,9 @@ int main(int argc, char **argv) oa = csg_sphere(0, 0, 0, 1); ob = csg_sphere(0, 1, 0, 0.8); - oc = csg_intersection(oa, ob); + oc = csg_union(oa, ob); - csg_add_object(0, oc); + csg_add_object(oc); csg_render_image(pixels, width, height); save_image(out_fname, pixels, width, height);