Added pgm drawing and got light ray tracing working

Still needs correct light simulation and reflections

9 files changed, 328 insertions, 50 deletions

diff --git a/main.c b/main.c
index 0f64c57..011f2c1 100644
--- a/main.c
+++ b/main.c
@@ -3,39 +3,47 @@
 #include <stdlib.h>
 
 #include "vector.h"
-#include "viewpoint.h"
 #include "ray.h"
+#include "scene.h"
+#include "pgm.h"
 
-typedef struct {
-	viewpoint_t view;
-} space_t;
+#define TESTW 1000
+#define TESTH 1000
+
+color_t back = {0, 0, 0};
 
 int main()
 {
-	printf("Starting\n");
-
+	//printf("Starting\n");
 	space_t s;
+	s.objects = NULL;
+	s.lights = NULL;
 
-	vector_set(&s.view.position, 10, 20, 10);
+	vector_set(&s.view.position, 0, 15, 10);
 	vector_set(&s.view.target, 0, 0, 0);
-	s.view.width = 100;
-	s.view.height = 100;
+	s.view.width = TESTW;
+	s.view.height = TESTH;
 
 	viewpoint_init(&s.view);
-
-	ray_t r;
-	r.start = &s.view.position;
-	viewpoint_ray(&s.view, &r.direction, 66, 33);
-
-	vector_print(&r.direction);
-
-	plane_t pl;
-	pl.start = vector_set(NULL, 0, 0, 12);
-	vector_set(&pl.norm, 6, 2, 0);
-	vector_scale_inv(&pl.norm, &pl.norm, vector_len(&pl.norm));
-	vector_print(&pl.norm);
-
-	printf("Intersect distance %f\n", ray_intersect_plane(&pl, &r));
-
+	
+	// Setup plane
+	add_sphere(&s, vector_set(NULL, 0, 0, 5), 5);
+	add_sphere(&s, vector_set(NULL, 10, 0, 5), 5);
+	add_plane(&s, vector_set(NULL, 0, 0, 2), vector_set(NULL, 0, 0, 1));
+	add_light(&s, vector_set(NULL, 10, 0, 20), color_set(NULL, 255, 255, 255));
+
+	pgm_write_header(stdout, TESTW, TESTH);
+	for (int y = TESTH; y; y--) {
+		for (int x = TESTW; x; x--) {
+			color_t *c = ray_trace(&s, x, y);
+
+			if (c) {
+				pgm_write_pixel(stdout, c);
+			} else {
+				pgm_write_pixel(stdout, &back);
+			}
+			free(c);
+		}
+	}
 	
 }
diff --git a/pgm.c b/pgm.c
new file mode 100644
index 0000000..058b445
--- /dev/null
+++ b/pgm.c
@@ -0,0 +1,27 @@
+#include "pgm.h"
+
+#include <stdio.h>
+#include <stdlib.h>
+
+int pgm_write_header(FILE *fp, unsigned int w, unsigned int h)
+{
+	return fprintf(fp, "P3\n%d %d\n255\n", w, h);
+}
+
+int pgm_write_pixel(FILE *fp, color_t *c)
+{
+	return fprintf(fp, "%d %d %d\n", c->r, c->g, c->b);
+}
+
+color_t *color_set(color_t *c, uint8_t r, uint8_t g, uint8_t b)
+{
+	if (!c) {
+		c = (color_t *) malloc(sizeof(c));
+	}
+
+	c->r = r;
+	c->g = g;
+	c->b = b;
+
+	return c;
+}
diff --git a/pgm.h b/pgm.h
new file mode 100644
index 0000000..b8900b8
--- /dev/null
+++ b/pgm.h
@@ -0,0 +1,16 @@
+#ifndef PGM_H
+#define PGM_H
+
+#include <stdio.h>
+#include <stdint.h>
+
+typedef struct {
+	uint8_t r, g, b;
+} color_t;
+
+color_t *color_set(color_t *c, uint8_t r, uint8_t g, uint8_t b);
+
+int pgm_write_header(FILE *fp, unsigned int w, unsigned int h);
+int pgm_write_pixel(FILE *fp, color_t *c);
+
+#endif
diff --git a/ray.c b/ray.c
index d2b15cc..3736773 100644
--- a/ray.c
+++ b/ray.c
@@ -1,3 +1,4 @@
+#include <stdio.h>
 #include <math.h>
 #include "vector.h"
 
@@ -5,7 +6,8 @@
 
 // https://en.wikipedia.org/wiki/Line%E2%80%93sphere_intersection
 // http://viclw17.github.io/2018/07/16/raytracing-ray-sphere-intersection/
-COORD_T ray_intersect_sphere(sphere_t *s, ray_t *ray)
+// https://www.scratchapixel.com/lessons/3d-basic-rendering/minimal-ray-tracer-rendering-simple-shapes/ray-sphere-intersection
+COORD_T ray_intersect_sphere(sphere_t *s, ray_t *ray, bool skip_dist)
 {
     // Vector between vector start and center of circle
     vector_t oc;
@@ -13,8 +15,8 @@ COORD_T ray_intersect_sphere(sphere_t *s, ray_t *ray)
 
     // Solve quadratic function
 	// TODO Not sure if this step i neccesary because dir is unit
-    COORD_T a = vector_dot(&ray->direction, &ray->direction);
-    COORD_T b = 2 * vector_dot(&oc, &ray->direction);
+    COORD_T a = vector_dot(ray->direction, ray->direction);
+    COORD_T b = 2 * vector_dot(&oc, ray->direction);
     COORD_T c = vector_dot(&oc, &oc) - s->radius * s->radius;
 
     COORD_T d = b * b - 4 * a * c;
@@ -23,29 +25,150 @@ COORD_T ray_intersect_sphere(sphere_t *s, ray_t *ray)
     if (d < 0) {
         return -1;
     }
+	if (skip_dist) {
+		return 1;
+	}
+
+    // Else take the closest intersection, reuse d
+	COORD_T q = (b > 0) ? 
+		-0.5 * (b + sqrt(d)) :
+		-0.5 * (b - sqrt(d));
+
+	COORD_T x0 = q / a;
+	COORD_T x1 = c / q;
+
+	// Take the correct result. If one is zero take the other.
+	if (x0 <= 0) {
+		if (x1 <= 0) {
+			return -1;
+		}
+
+		x0 = x1;
+	}
+
+	// If point is on sphere it will be zero close to zero
+	if (x0 < 1e-3) {
+		return -1;
+	}
 
-    // Else take the closest intersection
-    return (-b - sqrt(d) ) / (2.0 * a);
+	return x0;
 }
 
 // Requires that vectors are normalized
 // https://www.scratchapixel.com/lessons/3d-basic-rendering/minimal-ray-tracer-rendering-simple-shapes/ray-plane-and-ray-disk-intersection
-COORD_T ray_intersect_plane(plane_t *p, ray_t *ray)
+COORD_T ray_intersect_plane(plane_t *p, ray_t *ray, bool skip_dist)
 {
 	// If zero ray is parralel to plane
-	COORD_T nr = vector_dot(&p->norm, &ray->direction);
-	vector_print(&ray->direction);
+	COORD_T nr = vector_dot(p->norm, ray->direction);
 	//
 	// Take care of rounding errors
 	if (nr < ZERO_APROX && nr > -ZERO_APROX) {
 		return -1;
 	}
+	if (skip_dist) {
+		return 1;
+	}
 
 	// Calculate distance
 	vector_t tmp;
 	vector_copy(&tmp, p->start);
 	vector_sub(&tmp, &tmp, ray->start);
 
-	COORD_T t = vector_dot(&tmp, &p->norm) / nr;
+	COORD_T t = vector_dot(&tmp, p->norm) / nr;
 	return t;
 }
+
+COORD_T ray_intersect(object_t *o, ray_t *ray, bool skip_dist)
+{
+	switch (o->type) {
+		case TYPE_PLANE:
+			return ray_intersect_plane(&o->pl, ray, skip_dist);
+		case TYPE_SPHERE:
+			return ray_intersect_sphere(&o->sph, ray, skip_dist);
+		default:
+			printf("Unknown object type %d\n", o->type);
+			return -1;
+	}
+}
+
+// If chk is true, will return at first hit less than chk_dist
+object_t *ray_cast(space_t *s, ray_t *r, COORD_T *dist_ret, bool chk, COORD_T chk_dist)
+{
+	object_t *o = s->objects;
+
+	object_t *smallest = NULL;
+	COORD_T dist = 0;
+
+	while (o) {
+		COORD_T d = ray_intersect(o, r, false);
+
+		if (d > 0) {
+			if (chk && chk_dist > d) {
+				if (dist_ret) {
+					*dist_ret = d;
+				}
+				return o;
+			}
+			if (d < dist || smallest == NULL) {
+				dist = d;
+				smallest = o;
+			}
+		}
+		
+		o = o->next;
+	}
+
+	if (chk) {
+		return NULL;
+	}
+
+	if (dist_ret) {
+		*dist_ret = dist;
+	}
+	return smallest;
+}
+
+color_t *ray_trace(space_t *s, unsigned int x, unsigned int y)
+{
+	// Setup primary ray
+	ray_t r;
+	r.start = &s->view.position;
+	r.direction = vector_copy(NULL, NULL);
+	viewpoint_ray(&s->view, r.direction, x, y);
+
+	// Cast it
+	COORD_T dist;
+	object_t *o = ray_cast(s, &r, &dist, false, 0);
+	if (!o) {
+		return NULL;
+	}
+	//printf("dist: %f\n", dist);
+
+	// Calculate new ray point
+	r.start = vector_scale(NULL, r.direction, dist);
+	vector_add(r.start, r.start, &s->view.position);
+
+	// Cast light rays
+	light_t *l = s->lights;
+	while (l) {
+		vector_t tmp;
+		// Calculate distance to light
+		vector_sub(&tmp, l->pos, r.start);
+		COORD_T d = vector_len(&tmp);
+		
+		// Calculate unit
+		vector_scale_inv(&tmp, &tmp, vector_len(&tmp));
+
+		// Find obstacles
+		r.direction = &tmp;
+		object_t *obs = ray_cast(s, &r, NULL, true, d);
+
+		if (!obs) {
+			return color_set(NULL, 100, 100, o->type == TYPE_SPHERE ? 200 :0);
+		}
+			
+		l = l->next;
+	}
+
+	return NULL;
+}
diff --git a/ray.h b/ray.h
index 999923a..208dcfc 100644
--- a/ray.h
+++ b/ray.h
@@ -1,28 +1,22 @@
 #ifndef RAY_H
 #define RAY_H
 
+#include <stdbool.h>
+#include <stdint.h>
 #include "vector.h"
+#include "scene.h"
 
 typedef struct {
     // Start is not unique so it's a pointer to save copying time
     vector_t *start;
-
-    vector_t direction;
+    vector_t *direction;
 } ray_t;
 
-typedef struct {
-	vector_t *center;
-	COORD_T radius;
-} sphere_t;
-
-// TODO make this less inconsistent
-typedef struct {
-	vector_t *start;
-	vector_t norm;
-} plane_t;
-
+COORD_T ray_intersect(object_t *o, ray_t *ray, bool skip_dist);
+COORD_T ray_intersect_sphere(sphere_t *s, ray_t *ray, bool skip_dist);
+COORD_T ray_intersect_plane(plane_t *p, ray_t *ray, bool skip_dist);
 
-COORD_T ray_intersect_sphere(sphere_t *s, ray_t *ray);
-COORD_T ray_intersect_plane(plane_t *p, ray_t *ray);
+object_t *ray_cast(space_t *s, ray_t *r, COORD_T *dist_ret, bool chk, COORD_T chk_dist);
+color_t *ray_trace(space_t *s, unsigned int x, unsigned int y);
 
 #endif
diff --git a/scene.c b/scene.c
new file mode 100644
index 0000000..a75b329
--- /dev/null
+++ b/scene.c
@@ -0,0 +1,56 @@
+#include "scene.h"
+
+#include <stdlib.h>
+
+static inline void link_object(space_t *s, object_t *o)
+{
+	if (s) {
+		o->next = s->objects;
+		s->objects = o;
+	} else {
+		o->next = 0;
+	}
+}
+
+object_t *add_sphere(space_t *s, vector_t *c, COORD_T r)
+{
+	object_t *o = (object_t *) malloc(sizeof(object_t));
+
+	o->type = TYPE_SPHERE;
+	o->sph.center = c;
+	o->sph.radius = r;
+
+	link_object(s, o);
+
+	return o;
+}
+
+object_t *add_plane(space_t *s, vector_t *start, vector_t *dir)
+{
+	object_t *o = (object_t *) malloc(sizeof(object_t));
+
+	o->type = TYPE_PLANE;
+	o->pl.start = start;
+	o->pl.norm = dir;
+
+	link_object(s, o);
+
+	return o;
+}
+
+light_t *add_light(space_t *s, vector_t *pos, color_t *c)
+{
+	light_t *o = (light_t *) malloc(sizeof(light_t));
+
+	o->pos = pos;
+	o->col = c;
+
+	if (s) {
+		o->next = s->lights;
+		s->lights = o;
+	} else {
+		o->next = NULL;
+	}
+
+	return o;
+}
diff --git a/scene.h b/scene.h
new file mode 100644
index 0000000..1c6363b
--- /dev/null
+++ b/scene.h
@@ -0,0 +1,52 @@
+
+#ifndef SCENE_H
+#define SCENE_H
+
+#include <stdbool.h>
+#include <stdint.h>
+#include "vector.h"
+#include "viewpoint.h"
+#include "pgm.h"
+
+#define TYPE_SPHERE 1
+#define TYPE_PLANE 2
+
+typedef struct {
+	vector_t *center;
+	COORD_T radius;
+} sphere_t;
+
+typedef struct {
+	vector_t *start;
+	vector_t *norm;
+} plane_t;
+
+typedef struct light_s{
+	vector_t *pos;
+	color_t *col;
+
+	struct light_s *next;
+} light_t;
+
+// General object structure
+typedef struct object_s{
+	uint8_t type;
+	struct object_s *next;
+
+	union {
+		sphere_t sph;
+		plane_t pl;
+	};
+} object_t;
+
+typedef struct {
+	viewpoint_t view;
+	object_t *objects;
+	light_t *lights;
+} space_t;
+
+object_t *add_sphere(space_t *s, vector_t *c, COORD_T r);
+object_t *add_plane(space_t *s, vector_t *start, vector_t *dir);
+light_t *add_light(space_t *s, vector_t *pos, color_t *c);
+
+#endif
diff --git a/vector.h b/vector.h
index 5609215..2fcb648 100644
--- a/vector.h
+++ b/vector.h
@@ -2,7 +2,7 @@
 #define VECTOR_H
 	
 #define COORD_T float
-#define ZERO_APROX 1e-6
+#define ZERO_APROX 1e-5
 
 typedef struct {
 	COORD_T x;
diff --git a/viewpoint.c b/viewpoint.c
index d51e646..7786c12 100644
--- a/viewpoint.c
+++ b/viewpoint.c
@@ -4,7 +4,7 @@
 #include <math.h>
 #include <stdlib.h>
 
-static const vector_t up = {0, 1, 0};
+static const vector_t up = {0, 0, 1};
 
 void viewpoint_init(viewpoint_t *view)
 {
@@ -37,10 +37,12 @@ void viewpoint_init(viewpoint_t *view)
 	vector_sub(&view->blc, &view->blc, vector_scale(&v, &v, gy));
 
 	// Debug print
+	/*
 	printf("Calculated the following viewpoint stuff\n");
 	printf("qx"); vector_print(&view->qx);
 	printf("qy"); vector_print(&view->qy);
 	printf("blc"); vector_print(&view->blc);
+	*/
 }
 
 // Calculate ray for viewport w, h