From dfc6ebacd7bcc1e6b9e7168c3e4824d241d2d5c8 Mon Sep 17 00:00:00 2001
From: John Tsiombikas <nuclear@member.fsf.org>
Date: Sun, 8 May 2022 07:40:40 +0300
Subject: [PATCH] initial raytracing experiment

---
 Makefile               |    8 +-
 pull.bat               |    1 +
 push.bat               |    3 +
 src/darray.c           |  122 ++++++++++++++++++++++
 src/darray.h           |   48 +++++++++
 src/demo.h             |    1 +
 src/dos/logger.c       |   54 +++++++++-
 src/dos/logger.h       |    3 +
 src/dos/main.c         |    9 ++
 src/glut/main.c        |    5 +
 src/scr/raytrace.c     |  104 +++++++++++++++++++
 src/scr/rt.c           |  261 ++++++++++++++++++++++++++++++++++++++++++++++++
 src/scr/rt.h           |   81 +++++++++++++++
 src/screen.c           |    4 +
 src/util.c             |   33 ++++++
 src/util.h             |   14 +++
 tools/scripts/fixmknam |    7 ++
 17 files changed, 750 insertions(+), 8 deletions(-)
 create mode 100644 push.bat
 create mode 100644 src/darray.c
 create mode 100644 src/darray.h
 create mode 100644 src/scr/raytrace.c
 create mode 100644 src/scr/rt.c
 create mode 100644 src/scr/rt.h
 create mode 100755 tools/scripts/fixmknam

diff --git a/Makefile b/Makefile
index ea8473f..c1a8cad 100644
--- a/Makefile
+++ b/Makefile
@@ -8,12 +8,12 @@ srcobj = src/bsptree.obj src/cfgopt.obj src/console.obj src/demo.obj &
 	src/dynarr.obj src/gfxutil.obj src/metasurf.obj src/noise.obj &
 	src/rbtree.obj src/screen.obj src/tinyfps.obj src/treestor.obj &
 	src/image.obj src/ts_text.obj src/util.obj src/util_s.obj src/cpuid.obj &
-	src/cpuid_s.obj src/data.obj
+	src/cpuid_s.obj src/darray.obj src/data.obj
 scrobj = src/scr/bump.obj src/scr/fract.obj src/scr/greets.obj &
 	src/scr/grise.obj src/scr/hairball.obj src/scr/infcubes.obj &
 	src/scr/metaball.obj src/scr/plasma.obj src/scr/polytest.obj &
 	src/scr/smoketxt.obj src/scr/thunder.obj src/scr/tilemaze.obj &
-	src/scr/tunnel.obj src/scr/cybersun.obj
+	src/scr/tunnel.obj src/scr/cybersun.obj src/scr/raytrace.obj src/scr/rt.obj
 csprobj = cspr/dbgfont.obj cspr/confont.obj
 
 incpath = -Isrc -Isrc/dos -Isrc/3dgfx -Ilibs -Ilibs/imago/src -Ilibs/anim/src &
@@ -30,12 +30,12 @@ srcobj = src\bsptree.obj src\cfgopt.obj src\console.obj src\demo.obj &
 	src\dynarr.obj src\gfxutil.obj src\metasurf.obj src\noise.obj &
 	src\rbtree.obj src\screen.obj src\tinyfps.obj src\treestor.obj &
 	src\image.obj src\ts_text.obj src\util.obj src\util_s.obj src\cpuid.obj &
-	src\cpuid_s.obj src\data.obj
+	src\cpuid_s.obj src\darray.obj src\data.obj
 scrobj = src\scr\bump.obj src\scr\fract.obj src\scr\greets.obj &
 	src\scr\grise.obj src\scr\hairball.obj src\scr\infcubes.obj &
 	src\scr\metaball.obj src\scr\plasma.obj src\scr\polytest.obj &
 	src\scr\smoketxt.obj src\scr\thunder.obj src\scr\tilemaze.obj &
-	src\scr\tunnel.obj src\scr\cybersun.obj
+	src\scr\tunnel.obj src\scr\cybersun.obj src\scr\raytrace.obj src\scr\rt.obj
 csprobj = cspr\dbgfont.obj cspr\confont.obj
 
 incpath = -Isrc -Isrc\dos -Isrc\3dgfx -Ilibs -Ilibs\imago\src -Ilibs\anim\src &
diff --git a/pull.bat b/pull.bat
index 9ded3c7..e3e1236 100644
--- a/pull.bat
+++ b/pull.bat
@@ -1,6 +1,7 @@
 rsync -uv 192.168.0.4::dosdemo/Makefile Makefile
 rsync -uv 192.168.0.4::dosdemo/src/*.c src
 rsync -uv 192.168.0.4::dosdemo/src/*.h src
+rsync -uv 192.168.0.4::dosdemo/src/*.asm src
 rsync -uv 192.168.0.4::dosdemo/src/dos/*.c src/dos
 rsync -uv 192.168.0.4::dosdemo/src/dos/*.h src/dos
 rsync -uv 192.168.0.4::dosdemo/src/dos/*.asm src/dos
diff --git a/push.bat b/push.bat
new file mode 100644
index 0000000..f541c4d
--- /dev/null
+++ b/push.bat
@@ -0,0 +1,3 @@
+del ddsrc.zip
+zip -r ddsrc.zip . -i *.c -i *.h -i *.asm -i *.s -i *.S -i *.inl -i *akefile* -i *.bat -i packsrc -i unpsrc -x *.swp -x libs/*
+scp2dos -g ddsrc.zip nuclear@192.168.0.4:code/demoscene/dosdemo
diff --git a/src/darray.c b/src/darray.c
new file mode 100644
index 0000000..66c0715
--- /dev/null
+++ b/src/darray.c
@@ -0,0 +1,122 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include "darray.h"
+#include "util.h"
+
+
+/* The array descriptor keeps auxilliary information needed to manipulate
+ * the dynamic array. It's allocated adjacent to the array buffer.
+ */
+struct arrdesc {
+	int nelem, szelem;
+	int max_elem;
+	int bufsz;	/* not including the descriptor */
+};
+
+#define DESC(x)		((struct arrdesc*)((char*)(x) - sizeof(struct arrdesc)))
+
+void *darr_alloc(int elem, int szelem)
+{
+	struct arrdesc *desc;
+
+	desc = malloc_nf(elem * szelem + sizeof *desc);
+	desc->nelem = desc->max_elem = elem;
+	desc->szelem = szelem;
+	desc->bufsz = elem * szelem;
+	return (char*)desc + sizeof *desc;
+}
+
+void darr_free(void *da)
+{
+	if(da) {
+		free(DESC(da));
+	}
+}
+
+void *darr_resize_impl(void *da, int elem)
+{
+	int newsz;
+	struct arrdesc *desc;
+
+	if(!da) return 0;
+	desc = DESC(da);
+
+	newsz = desc->szelem * elem;
+	desc = realloc_nf(desc, newsz + sizeof *desc);
+
+	desc->nelem = desc->max_elem = elem;
+	desc->bufsz = newsz;
+	return (char*)desc + sizeof *desc;
+}
+
+int darr_empty(void *da)
+{
+	return DESC(da)->nelem ? 0 : 1;
+}
+
+int darr_size(void *da)
+{
+	return DESC(da)->nelem;
+}
+
+
+void *darr_clear_impl(void *da)
+{
+	return darr_resize_impl(da, 0);
+}
+
+/* stack semantics */
+void *darr_push_impl(void *da, void *item)
+{
+	struct arrdesc *desc;
+	int nelem;
+
+	desc = DESC(da);
+	nelem = desc->nelem;
+
+	if(nelem >= desc->max_elem) {
+		/* need to resize */
+		int newsz = desc->max_elem ? desc->max_elem * 2 : 1;
+
+		da = darr_resize_impl(da, newsz);
+		desc = DESC(da);
+		desc->nelem = nelem;
+	}
+
+	if(item) {
+		memcpy((char*)da + desc->nelem * desc->szelem, item, desc->szelem);
+	}
+	desc->nelem++;
+	return da;
+}
+
+void *darr_pop_impl(void *da)
+{
+	struct arrdesc *desc;
+	int nelem;
+
+	desc = DESC(da);
+	nelem = desc->nelem;
+
+	if(!nelem) return da;
+
+	if(nelem <= desc->max_elem / 3) {
+		/* reclaim space */
+		int newsz = desc->max_elem / 2;
+
+		da = darr_resize_impl(da, newsz);
+		desc = DESC(da);
+		desc->nelem = nelem;
+	}
+	desc->nelem--;
+
+	return da;
+}
+
+void *darr_finalize(void *da)
+{
+	struct arrdesc *desc = DESC(da);
+	memmove(desc, da, desc->bufsz);
+	return desc;
+}
diff --git a/src/darray.h b/src/darray.h
new file mode 100644
index 0000000..b9a7051
--- /dev/null
+++ b/src/darray.h
@@ -0,0 +1,48 @@
+#ifndef DYNAMIC_ARRAY_H_
+#define DYNAMIC_ARRAY_H_
+
+void *darr_alloc(int elem, int szelem);
+void darr_free(void *da);
+void *darr_resize_impl(void *da, int elem);
+#define darr_resize(da, elem)	do { (da) = darr_resize_impl(da, elem); } while(0)
+
+int darr_empty(void *da);
+int darr_size(void *da);
+
+void *darr_clear_impl(void *da);
+#define darr_clear(da)			do { (da) = darr_clear_impl(da); } while(0)
+
+/* stack semantics */
+void *darr_push_impl(void *da, void *item);
+#define darr_push(da, item)		do { (da) = darr_push_impl(da, item); } while(0)
+void *darr_pop_impl(void *da);
+#define darr_pop(da)			do { (da) = darr_pop_impl(da); } while(0)
+
+/* Finalize the array. No more resizing is possible after this call.
+ * Use free() instead of dynarr_free() to deallocate a finalized array.
+ * Returns pointer to the finalized array.
+ * Complexity: O(n)
+ */
+void *darr_finalize(void *da);
+
+/* utility macros to push characters to a string. assumes and maintains
+ * the invariant that the last element is always a zero
+ */
+#define darr_strpush(da, c) \
+	do { \
+		char cnull = 0, ch = (char)(c); \
+		(da) = dynarr_pop_impl(da); \
+		(da) = dynarr_push_impl((da), &ch); \
+		(da) = dynarr_push_impl((da), &cnull); \
+	} while(0)
+
+#define darr_strpop(da) \
+	do { \
+		char cnull = 0; \
+		(da) = dynarr_pop_impl(da); \
+		(da) = dynarr_pop_impl(da); \
+		(da) = dynarr_push_impl((da), &cnull); \
+	} while(0)
+
+
+#endif	/* DYNAMIC_ARRAY_H_ */
diff --git a/src/demo.h b/src/demo.h
index 68cb967..af4870f 100644
--- a/src/demo.h
+++ b/src/demo.h
@@ -68,6 +68,7 @@ void demo_keyboard(int key, int press);
 
 /* defined in main_*.c */
 void demo_quit(void);
+void demo_abort(void);
 unsigned long get_msec(void);
 void set_palette(int idx, int r, int g, int b);
 
diff --git a/src/dos/logger.c b/src/dos/logger.c
index 70489ad..2d61070 100644
--- a/src/dos/logger.c
+++ b/src/dos/logger.c
@@ -5,17 +5,63 @@
 #include <fcntl.h>
 #include "logger.h"
 
+static int logfd = -1, orig_fd1 = -1;
+
 int init_logger(const char *fname)
 {
-	int fd;
-	if((fd = open(fname, O_CREAT | O_WRONLY | O_TRUNC, 0644)) == -1) {
+	if(logfd != -1) return -1;
+
+	if((logfd = open(fname, O_CREAT | O_WRONLY | O_TRUNC, 0644)) == -1) {
 		fprintf(stderr, "init_logger: failed to open %s: %s\n", fname, strerror(errno));
 		return -1;
 	}
 
+	orig_fd1 = dup(1);
 	close(1);
 	close(2);
-	dup(fd);
-	dup(fd);
+	dup(logfd);
+	dup(logfd);
+	return 0;
+}
+
+void stop_logger(void)
+{
+	if(logfd >= 0) {
+		close(logfd);
+		logfd = -1;
+	}
+	if(orig_fd1 >= 0) {
+		close(1);
+		close(2);
+		dup(orig_fd1);
+		dup(orig_fd1);
+		orig_fd1 = -1;
+	}
+}
+
+int print_tail(const char *fname)
+{
+	FILE *fp;
+	char buf[64];
+	long lineoffs[16];
+	int wr, rd, c;
+
+	if(!(fp = fopen(fname, "r"))) {
+		return -1;
+	}
+	lineoffs[wr++] = 0;
+	while(fgets(buf, sizeof buf, fp)) {
+		lineoffs[wr] = ftell(fp);
+		wr = (wr + 1) & 0xf;
+		if(wr == rd) {
+			rd = (rd + 1) & 0xf;
+		}
+	}
+
+	fseek(fp, lineoffs[rd], SEEK_SET);
+	while((c = fgetc(fp)) != -1) {
+		fputc(c, stdout);
+	}
+	fclose(fp);
 	return 0;
 }
diff --git a/src/dos/logger.h b/src/dos/logger.h
index 9ef9a85..56f6be7 100644
--- a/src/dos/logger.h
+++ b/src/dos/logger.h
@@ -6,6 +6,9 @@ extern "C" {
 #endif
 
 int init_logger(const char *fname);
+void stop_logger(void);
+
+int print_tail(const char *fname);
 
 #ifdef __cplusplus
 }
diff --git a/src/dos/main.c b/src/dos/main.c
index 0714297..ee28dc9 100644
--- a/src/dos/main.c
+++ b/src/dos/main.c
@@ -131,6 +131,15 @@ void demo_quit(void)
 	quit = 1;
 }
 
+void demo_abort(void)
+{
+	set_text_mode();
+	stop_logger();
+	printf("demo_abort called. see demo.log for details. Last lines:\n\n");
+	print_tail("demo.log");
+	abort();
+}
+
 #define TX(ev)	((ev)->motion.motion[0])
 #define TY(ev)	((ev)->motion.motion[1])
 #define TZ(ev)	((ev)->motion.motion[2])
diff --git a/src/glut/main.c b/src/glut/main.c
index 8d19192..a552832 100644
--- a/src/glut/main.c
+++ b/src/glut/main.c
@@ -153,6 +153,11 @@ void demo_quit(void)
 	exit(0);
 }
 
+void demo_abort(void)
+{
+	abort();
+}
+
 struct video_mode *video_modes(void)
 {
 	return vmodes;
diff --git a/src/scr/raytrace.c b/src/scr/raytrace.c
new file mode 100644
index 0000000..3d8465f
--- /dev/null
+++ b/src/scr/raytrace.c
@@ -0,0 +1,104 @@
+#include <stdio.h>
+#include <math.h>
+#include "demo.h"
+#include "screen.h"
+#include "gfxutil.h"
+#include "util.h"
+#include "cgmath/cgmath.h"
+#include "rt.h"
+
+static int init(void);
+static void destroy(void);
+static void start(long trans_time);
+static void draw(void);
+
+static struct screen scr = {
+	"raytrace",
+	init,
+	destroy,
+	start,
+	0,
+	draw
+};
+
+static cgm_vec3 raydir[120][160];
+static struct rtscene scn;
+
+struct screen *raytrace_screen(void)
+{
+	return &scr;
+}
+
+static int init(void)
+{
+	int i, j;
+	float z = 1.0f / tan(cgm_deg_to_rad(25.0f));
+
+	for(i=0; i<120; i++) {
+		cgm_vec3 *vptr = raydir[i];
+		float y = 1.0f - (float)i / 60.0f;
+		for(j=0; j<160; j++) {
+			vptr->x = ((float)j / 80.0f - 1.0f) * 1.333333f;
+			vptr->y = y;
+			vptr->z = z;
+			vptr++;
+		}
+	}
+
+	rt_init(&scn);
+
+	rt_color(1, 0, 0);
+	rt_specular(0.8f, 0.8f, 0.8f);
+	rt_shininess(30.0f);
+	rt_add_sphere(&scn, 0, 0, 0, 1);	/* x,y,z, rad */
+
+	rt_color(0.4, 0.4, 0.4);
+	rt_specular(0, 0, 0);
+	rt_shininess(1);
+	rt_add_plane(&scn, 0, 1, 0, -1);		/* nx,ny,nz, dist */
+
+	rt_color(1, 1, 1);
+	rt_add_light(&scn, -8, 15, -10);
+	return 0;
+}
+
+static void destroy(void)
+{
+	rt_destroy(&scn);
+}
+
+static void start(long start_time)
+{
+}
+
+static void draw(void)
+{
+	int i, j, r, g, b;
+	uint16_t pix, *fbptr = fb_pixels;
+
+	for(i=0; i<120; i++) {
+		for(j=0; j<160; j++) {
+			cgm_ray ray;
+			cgm_vec3 col;
+			ray.dir = raydir[i][j];
+			cgm_vcons(&ray.origin, 0, 0, -5);
+
+			if(ray_trace(&ray, &scn, 0, &col)) {
+				r = cround64(col.x * 255.0f) & 0xff;
+				g = cround64(col.y * 255.0f) & 0xff;
+				b = cround64(col.z * 255.0f) & 0xff;
+				if(r > 255) r = 255;
+				if(g > 255) g = 255;
+				if(b > 255) b = 255;
+				pix = PACK_RGB16(r, g, b);
+			} else {
+				pix = 0;
+			}
+			fbptr[0] = fbptr[1] = fbptr[320] = fbptr[321] = pix;
+			fbptr += 2;
+		}
+		fbptr += 320;
+	}
+
+	swap_buffers(0);
+}
diff --git a/src/scr/rt.c b/src/scr/rt.c
new file mode 100644
index 0000000..13f2dbe
--- /dev/null
+++ b/src/scr/rt.c
@@ -0,0 +1,261 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <math.h>
+#include <float.h>
+#include "rt.h"
+#include "util.h"
+#include "darray.h"
+
+static cgm_vec3 cur_col, cur_spec;
+static float cur_shin;
+static struct image *cur_tex;
+
+void rt_init(struct rtscene *scn)
+{
+	scn->obj = darr_alloc(0, sizeof *scn->obj);
+	scn->num_obj = 0;
+	scn->lt = darr_alloc(0, sizeof *scn->lt);
+	scn->num_lt = 0;
+
+	cgm_vcons(&cur_col, 1, 1, 1);
+	cgm_vcons(&cur_spec, 0, 0, 0);
+	cur_shin = 1;
+	cur_tex = 0;
+}
+
+void rt_destroy(struct rtscene *scn)
+{
+	darr_free(scn->obj);
+	darr_free(scn->lt);
+	memset(scn, 0, sizeof *scn);
+}
+
+
+void rt_color(float r, float g, float b)
+{
+	cgm_vcons(&cur_col, r, g, b);
+}
+
+void rt_specular(float r, float g, float b)
+{
+	cgm_vcons(&cur_spec, r, g, b);
+}
+
+void rt_shininess(float s)
+{
+	cur_shin = s;
+}
+
+static union rtobject *add_object(struct rtscene *scn, enum rt_obj_type type)
+{
+	union rtobject *obj;
+
+	obj = calloc_nf(1, sizeof *obj);
+	obj->type = type;
+
+	obj->x.mtl.kd = cur_col;
+	obj->x.mtl.ks = cur_spec;
+	obj->x.mtl.shin = cur_shin;
+	obj->x.mtl.tex = cur_tex;
+
+	darr_push(scn->obj, &obj);
+	scn->num_obj = darr_size(scn->obj);
+	return obj;
+}
+
+union rtobject *rt_add_sphere(struct rtscene *scn, float x, float y, float z, float r)
+{
+	union rtobject *obj = add_object(scn, RT_SPH);
+	cgm_vcons(&obj->s.p, x, y, z);
+	obj->s.r = r;
+	return obj;
+}
+
+union rtobject *rt_add_plane(struct rtscene *scn, float nx, float ny, float nz, float d)
+{
+	union rtobject *obj = add_object(scn, RT_PLANE);
+	cgm_vcons(&obj->p.n, nx, ny, nz);
+	obj->p.d = d;
+	return obj;
+}
+
+struct rtlight *rt_add_light(struct rtscene *scn, float x, float y, float z)
+{
+	struct rtlight *lt = calloc_nf(1, sizeof *lt);
+
+	cgm_vcons(&lt->p, x, y, z);
+	lt->color = cur_col;
+
+	darr_push(scn->lt, &lt);
+	scn->num_lt = darr_size(scn->lt);
+	return lt;
+}
+
+
+/* color is initialized to black */
+static void shade(struct rayhit *hit, struct rtscene *scn, int lvl, cgm_vec3 *color)
+{
+	int i;
+	float ndotl, vdotr, spec;
+	cgm_ray sray;
+	cgm_vec3 col, rdir;
+	struct rtlight *lt;
+	struct rtmaterial *mtl = &hit->obj->x.mtl;
+
+	sray.origin = hit->p;
+	cgm_vnormalize(&hit->n);
+	cgm_vnormalize(&hit->ray->dir);
+
+	for(i=0; i<scn->num_lt; i++) {
+		lt = scn->lt[i];
+		sray.dir = lt->p;
+		cgm_vsub(&sray.dir, &sray.origin);
+
+		if(ray_scene(&sray, scn, 1.0f, 0)) continue;
+
+		cgm_vnormalize(&sray.dir);
+		ndotl = cgm_vdot(&sray.dir, &hit->n);
+		if(ndotl < 0.0f) ndotl = 0.0f;
+
+		rdir = hit->ray->dir;
+		cgm_vreflect(&rdir, &hit->n);
+		vdotr = cgm_vdot(&sray.dir, &rdir);
+		if(vdotr < 0.0f) vdotr = 0.0f;
+		spec = pow(vdotr, mtl->shin);
+
+		color->x += (mtl->kd.x * ndotl + mtl->ks.x * spec) * lt->color.x;
+		color->y += (mtl->kd.y * ndotl + mtl->ks.y * spec) * lt->color.y;
+		color->z += (mtl->kd.z * ndotl + mtl->ks.z * spec) * lt->color.z;
+	}
+}
+
+int ray_trace(cgm_ray *ray, struct rtscene *scn, int lvl, cgm_vec3 *color)
+{
+	struct rayhit hit;
+
+	color->x = color->y = color->z = 0.0f;
+	if(!ray_scene(ray, scn, FLT_MAX, &hit)) {
+		return 0;
+	}
+	hit.ray = ray;
+	shade(&hit, scn, lvl, color);
+	return 1;
+}
+
+
+int ray_scene(cgm_ray *ray, struct rtscene *scn, float maxt, struct rayhit *hit)
+{
+	int i;
+
+	if(hit) {
+		struct rayhit hit0 = {FLT_MAX};
+
+		/* find nearest hit */
+		for(i=0; i<scn->num_obj; i++) {
+			if(ray_object(ray, scn->obj[i], maxt, hit) && hit->t < hit0.t) {
+				hit0 = *hit;
+			}
+		}
+
+		if(hit0.obj) {
+			*hit = hit0;
+			return 1;
+		}
+	} else {
+		/* find any hit */
+		for(i=0; i<scn->num_obj; i++) {
+			if(ray_object(ray, scn->obj[i], maxt, 0)) {
+				return 1;
+			}
+		}
+	}
+
+	return 0;
+}
+
+int ray_object(cgm_ray *ray, union rtobject *obj, float maxt, struct rayhit *hit)
+{
+	switch(obj->type) {
+	case RT_SPH:
+		return ray_sphere(ray, &obj->s, maxt, hit);
+	case RT_PLANE:
+		return ray_plane(ray, &obj->p, maxt, hit);
+	default:
+		break;
+	}
+	return 0;
+}
+
+#define SQ(x)	((x) * (x))
+int ray_sphere(cgm_ray *ray, struct rtsphere *sph, float maxt, struct rayhit *hit)
+{
+	float a, a2, b, c, d, sqrt_d, t1, t2;
+
+	a = SQ(ray->dir.x) + SQ(ray->dir.y) + SQ(ray->dir.z);
+	b = 2.0f * ray->dir.x * (ray->origin.x - sph->p.x) +
+		2.0f * ray->dir.y * (ray->origin.y - sph->p.y) +
+		2.0f * ray->dir.z * (ray->origin.z - sph->p.z);
+	c = SQ(sph->p.x) + SQ(sph->p.y) + SQ(sph->p.z) +
+		SQ(ray->origin.x) + SQ(ray->origin.y) + SQ(ray->origin.z) +
+		2.0f * (-sph->p.x * ray->origin.x - sph->p.y * ray->origin.y - sph->p.z * ray->origin.z) -
+		SQ(sph->r);
+
+	if((d = SQ(b) - 4.0f * a * c) < 0.0f) return 0;
+
+	sqrt_d = sqrt(d);
+	a2 = 2.0f * a;
+	t1 = (-b + sqrt_d) / a2;
+	t2 = (-b - sqrt_d) / a2;
+
+	if((t1 < 1e-5f && t2 < 1e-5f) || (t1 > maxt && t2 > maxt)) {
+		return 0;
+	}
+
+	if(hit) {
+		float t;
+		if(t1 < 1e-5f) {
+			t = t2;
+		} else if(t2 < 1e-5f) {
+			t = t1;
+		} else {
+			t = t1 < t2 ? t1 : t2;
+		}
+
+		hit->t = t;
+		cgm_raypos(&hit->p, ray, t);
+
+		hit->n.x = hit->p.x - sph->p.x;
+		hit->n.y = hit->p.y - sph->p.y;
+		hit->n.z = hit->p.z - sph->p.z;
+
+		hit->obj = (union rtobject*)sph;
+	}
+	return 1;
+}
+
+int ray_plane(cgm_ray *ray, struct rtplane *plane, float maxt, struct rayhit *hit)
+{
+	cgm_vec3 vo;
+	float t, ndotdir;
+
+	ndotdir = cgm_vdot(&plane->n, &ray->dir);
+	if(fabs(ndotdir) < 1e-5) {
+		return 0;
+	}
+
+	vo.x = plane->n.x * plane->d - ray->origin.x;
+	vo.y = plane->n.y * plane->d - ray->origin.y;
+	vo.z = plane->n.z * plane->d - ray->origin.z;
+	t = cgm_vdot(&plane->n, &vo) / ndotdir;
+
+	if(t < 1e-5 || t > maxt) return 0;
+
+	if(hit) {
+		hit->t = t;
+		cgm_raypos(&hit->p, ray, t);
+		hit->n = plane->n;
+
+		hit->obj = (union rtobject*)plane;
+	}
+	return 1;
+}
diff --git a/src/scr/rt.h b/src/scr/rt.h
new file mode 100644
index 0000000..f619a88
--- /dev/null
+++ b/src/scr/rt.h
@@ -0,0 +1,81 @@
+#ifndef RT_H_
+#define RT_H_
+
+#include "image.h"
+#include "cgmath/cgmath.h"
+
+struct rtmaterial {
+	cgm_vec3 kd, ks;
+	float shin;
+	struct image *tex;
+};
+
+enum rt_obj_type { RT_SPH, RT_PLANE };
+
+#define OBJ_COMMON	\
+	enum rt_obj_type type; \
+	struct rtmaterial mtl
+
+struct rtany {
+	OBJ_COMMON;
+};
+
+struct rtsphere {
+	OBJ_COMMON;
+	cgm_vec3 p;
+	float r;
+};
+
+struct rtplane {
+	OBJ_COMMON;
+	cgm_vec3 n;
+	float d;
+};
+
+union rtobject {
+	enum rt_obj_type type;
+	struct rtany x;
+	struct rtsphere s;
+	struct rtplane p;
+};
+
+struct rtlight {
+	cgm_vec3 p, color;
+};
+
+struct rayhit {
+	float t;
+	cgm_vec3 p, n;
+	float u, v;
+	cgm_ray *ray;
+	union rtobject *obj;
+};
+
+struct rtscene {
+	union rtobject **obj;
+	int num_obj;
+	struct rtlight **lt;
+	int num_lt;
+};
+
+/* scene management */
+void rt_init(struct rtscene *scn);
+void rt_destroy(struct rtscene *scn);
+
+void rt_color(float r, float g, float b);
+void rt_specular(float r, float g, float b);
+void rt_shininess(float s);
+
+union rtobject *rt_add_sphere(struct rtscene *scn, float x, float y, float z, float r);
+union rtobject *rt_add_plane(struct rtscene *scn, float nx, float ny, float nz, float d);
+struct rtlight *rt_add_light(struct rtscene *scn, float x, float y, float z);
+
+/* returns 0 for no hit */
+int ray_trace(cgm_ray *ray, struct rtscene *scn, int lvl, cgm_vec3 *color);
+
+int ray_object(cgm_ray *ray, union rtobject *obj, float maxt, struct rayhit *hit);
+int ray_scene(cgm_ray *ray, struct rtscene *scn, float maxt, struct rayhit *hit);
+int ray_sphere(cgm_ray *ray, struct rtsphere *sph, float maxt, struct rayhit *hit);
+int ray_plane(cgm_ray *ray, struct rtplane *plane, float maxt, struct rayhit *hit);
+
+#endif	/* RT_H_ */
diff --git a/src/screen.c b/src/screen.c
index 15eb57c..2dc0b67 100644
--- a/src/screen.c
+++ b/src/screen.c
@@ -26,6 +26,7 @@ struct screen *greets_screen(void);
 struct screen *infcubes_screen(void);
 struct screen *hairball_screen(void);
 struct screen *cybersun_screen(void);
+struct screen *raytrace_screen(void);
 
 void start_loadscr(void);
 void end_loadscr(void);
@@ -83,6 +84,9 @@ int scr_init(void)
 	if(!(scr[idx++] = cybersun_screen())) {
 		return -1;
 	}
+	if(!(scr[idx++] = raytrace_screen())) {
+		return -1;
+	}
 	num_screens = idx;
 
 	assert(num_screens <= NUM_SCR);
diff --git a/src/util.c b/src/util.c
index a91bb95..515b4e6 100644
--- a/src/util.c
+++ b/src/util.c
@@ -1,3 +1,36 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <errno.h>
 #include "util.h"
 
 uint32_t perf_start_count, perf_interval_count;
+
+void *malloc_nf_impl(size_t sz, const char *file, int line)
+{
+	void *p;
+	if(!(p = malloc(sz))) {
+		fprintf(stderr, "%s:%d failed to allocate %lu bytes\n", file, line, (unsigned long)sz);
+		demo_abort();
+	}
+	return p;
+}
+
+void *calloc_nf_impl(size_t num, size_t sz, const char *file, int line)
+{
+	void *p;
+	if(!(p = calloc(num, sz))) {
+		fprintf(stderr, "%s:%d failed to allocate %lu bytes\n", file, line, (unsigned long)(num * sz));
+		demo_abort();
+	}
+	return p;
+}
+
+void *realloc_nf_impl(void *p, size_t sz, const char *file, int line)
+{
+	if(!(p = realloc(p, sz))) {
+		fprintf(stderr, "%s:%d failed to realloc %lu bytes\n", file, line, (unsigned long)sz);
+		demo_abort();
+	}
+	return p;
+}
diff --git a/src/util.h b/src/util.h
index 50148af..f93efc8 100644
--- a/src/util.h
+++ b/src/util.h
@@ -1,6 +1,7 @@
 #ifndef UTIL_H_
 #define UTIL_H_
 
+#include <stdlib.h>
 #include "inttypes.h"
 
 #ifdef __GNUC__
@@ -240,4 +241,17 @@ unsigned int get_cs(void);
 void get_msr(uint32_t msr, uint32_t *low, uint32_t *high);
 void set_msr(uint32_t msr, uint32_t low, uint32_t high);
 
+
+/* Non-failing versions of malloc/calloc/realloc. They never return 0, they call
+ * demo_abort on failure. Use the macros, don't call the *_impl functions.
+ */
+#define malloc_nf(sz)	malloc_nf_impl(sz, __FILE__, __LINE__)
+void *malloc_nf_impl(size_t sz, const char *file, int line);
+#define calloc_nf(n, sz)	calloc_nf_impl(n, sz, __FILE__, __LINE__)
+void *calloc_nf_impl(size_t num, size_t sz, const char *file, int line);
+#define realloc_nf(p, sz)	realloc_nf_impl(p, sz, __FILE__, __LINE__)
+void *realloc_nf_impl(void *p, size_t sz, const char *file, int line);
+
+
+
 #endif	/* UTIL_H_ */
diff --git a/tools/scripts/fixmknam b/tools/scripts/fixmknam
new file mode 100755
index 0000000..15c6118
--- /dev/null
+++ b/tools/scripts/fixmknam
@@ -0,0 +1,7 @@
+#!/bin/sh
+
+for i in `find . -name 'makefile*'`; do
+	name=`echo $i | sed 's/makefile/Makefile/'`
+	echo "$i -> $name"
+	mv $i $name
+done
-- 
1.7.10.4