add rotating cheese

This adds the Cheese3D graphics api and makes the cheese command display a cheese rotating in 3d as a demo

10 files changed, 451 insertions, 41 deletions

diff --git a/Makefile b/Makefile
index 88d804e..5cc95f6 100644
--- a/Makefile
+++ b/Makefile
@@ -31,7 +31,10 @@ STAGE3_C = \
 	stage3/ps2.o \
 	stage3/thread.o \
 	stage3/shell.o \
-	stage3/version.o
+	stage3/version.o \
+	stage3/rng.o \
+	stage3/cheese3d.o \
+	stage3/cheese_demo.o
 
 STAGE3 = $(STAGE3_C) \
 	stage3/isr.o \
@@ -105,6 +108,7 @@ bochs: cuddles.img
 	echo c | bochs -q
 
 # to qemu slow: make QFLAGS="-icount shift=9,align=on,sleep=on" run
+# try QFLAGS="-enable-kvm" for better performance
 override QFLAGS += -drive format=raw,file=cuddles.img
 
 qemu: cuddles.img
diff --git a/stage3/cheese3d.c b/stage3/cheese3d.c
new file mode 100644
index 0000000..154ce58
--- /dev/null
+++ b/stage3/cheese3d.c
@@ -0,0 +1,148 @@
+#include "heap.h"
+#include "math3d.h"
+#include "cheese3d.h"
+#include "gfx.h"
+#include "memory.h"
+
+cheese3d_ctx cheese3d_create(u32 width, u32 height, u32 pitch, u32 bgcolor)
+{
+	return (cheese3d_ctx) {
+		.width = width,
+		.height = height,
+		.pitch = pitch,
+		.bgcolor = bgcolor,
+		.depth_buffer = malloc(gfx_info->width * gfx_info->height * sizeof(u32)),
+		.color_buffer = malloc(gfx_info->pitch * gfx_info->height),
+	};
+}
+
+cheese3d_ctx cheese3d_create_default(u32 bgcolor)
+{
+	return cheese3d_create(gfx_info->width, gfx_info->height, gfx_info->pitch, bgcolor);
+}
+
+void cheese3d_destroy(cheese3d_ctx ctx)
+{
+	free(ctx.depth_buffer);
+	free(ctx.color_buffer);
+}
+
+void cheese3d_clear(cheese3d_ctx ctx, bool color, bool depth)
+{
+	for (u32 x = 0; x < gfx_info->width; x++)
+	for (u32 y = 0; y < gfx_info->height; y++) {
+		if (color) ctx.depth_buffer[y * ctx.width + x] = 0.0;
+		if (depth) *(u32 *) (ctx.color_buffer + y * ctx.pitch + x * sizeof(u32)) = ctx.bgcolor;
+	}
+}
+
+void cheese3d_render(cheese3d_ctx ctx, usize num, vertex *vertices, texture *textures, float transform[4][4])
+{
+	for (usize i = 0; i < num; i += 3) {
+		float verts[3][4];
+		float min[2];
+		float max[2];
+
+		for (usize j = 0; j < 3; j++) {
+			float coord[4];
+			for (int k = 0; k < 3; k++)
+				coord[k] = vertices[i+j].pos[k];
+			coord[3] = 1.0;
+
+			mat_mul_vec(transform, coord);
+
+			verts[j][3] = 1/coord[3];
+			for (int k = 0; k < 3; k++)
+				verts[j][k] = coord[k] * verts[j][3];
+
+			for (int k = 0; k < 2; k++) {
+				if (j == 0 || verts[j][k] > max[k])
+					max[k] = verts[j][k];
+				if (j == 0 || verts[j][k] < min[k])
+					min[k] = verts[j][k];
+			}
+		}
+
+		// cull clockwise faces
+		float area = tri_area(verts[0], verts[1], verts[2]);
+		if (area < 0)
+			continue;
+
+		i32 i_min[2];
+		i32 i_max[2];
+		for (int k = 0; k < 2; k++) {
+			i32 size = k ? gfx_info->height : gfx_info->width;
+
+			i_min[k] = (0.5 + 0.5 * min[k]) * size;
+			i_max[k] = (0.5 + 0.5 * max[k]) * size;
+
+			if (i_max[k] >= size)
+				i_max[k] = size-1;
+			if (i_min[k] < 0)
+				i_min[k] = 0;
+		}
+
+		for (i32 y = i_min[1]; y <= i_max[1]; y++) {
+			float point[2] = {
+				0.0,
+				(float) y / gfx_info->height * 2.0 - 1.0
+			};
+			for (i32 x = i_min[0]; x <= i_max[0]; x++) {
+				point[0] = (float) x / gfx_info->width * 2.0 - 1.0;
+
+				float weights[3];
+				if ((weights[0] = tri_area(point, verts[1], verts[2])) < 0)
+					continue;
+				if ((weights[1] = tri_area(verts[0], point, verts[2])) < 0)
+					continue;
+				if ((weights[2] = tri_area(verts[0], verts[1], point)) < 0)
+					continue;
+
+				float depth = 0.0;
+				float w = 0.0;
+				float tex[2] = { 0.0, 0.0 };
+
+				for (int j = 0; j < 3; j++) {
+					weights[j] /= area;
+
+					depth += weights[j] * verts[j][2];
+					w += weights[j] * verts[j][3];
+					tex[0] += weights[j] * verts[j][3] * vertices[i+j].tex[0];
+					tex[1] += weights[j] * verts[j][3] * vertices[i+j].tex[1];
+				}
+
+				tex[0] /= w;
+				tex[1] /= w;
+
+				float *d = &ctx.depth_buffer[y * ctx.width + x];
+				if (*d > depth)
+					continue;
+				*d = depth;
+
+				texture *t = &textures[i];
+
+				i32 i_tex[2];
+				for (int k = 0; k < 2; k++) {
+					i32 size = k ? t->h : t->w;
+
+					i_tex[k] = tex[k] * size;
+
+					if (i_tex[k] >= size)
+						i_tex[k] = size-1;
+					if (i_tex[k] < 0)
+						i_tex[k] = 0;
+				}
+
+				*(u32 *) (ctx.color_buffer + y * ctx.pitch + x * sizeof(u32)) =
+					t->data[i_tex[1]*t->w+i_tex[0]];
+			}
+		}
+
+	}
+
+}
+
+void cheese3d_display(cheese3d_ctx ctx)
+{
+	memcpy((void *) (u64) gfx_info->framebuffer, ctx.color_buffer, gfx_info->pitch * gfx_info->height);
+}
diff --git a/stage3/cheese3d.h b/stage3/cheese3d.h
new file mode 100644
index 0000000..f93872f
--- /dev/null
+++ b/stage3/cheese3d.h
@@ -0,0 +1,37 @@
+#ifndef CHEESE3D_H
+#define CHEESE3D_H
+
+// Cheese3D is the cuddlesOS 3d graphics API
+
+#include "def.h"
+
+typedef struct {
+	float pos[3];
+	float tex[2];
+} vertex;
+
+typedef struct {
+	u32 w, h;
+	u32 *data;
+} texture;
+
+typedef struct {
+	u32 width;
+	u32 height;
+	u32 pitch;
+	u32 bgcolor;
+	float *depth_buffer;
+	void *color_buffer;
+} cheese3d_ctx;
+
+#define VERT(x, y, z, s, t) { { x, y, z }, { s, t } } // this exists to work with the QUAD macro
+#define QUAD(a, b, c, d) a, b, c, a, c, d
+
+cheese3d_ctx cheese3d_create(u32 width, u32 height, u32 pitch, u32 bgcolor);
+cheese3d_ctx cheese3d_create_default(u32 bgcolor);
+void cheese3d_destroy(cheese3d_ctx ctx);
+void cheese3d_clear(cheese3d_ctx ctx, bool color, bool depth);
+void cheese3d_render(cheese3d_ctx ctx, usize num, vertex *vertices, texture *textures, float transform[4][4]);
+void cheese3d_display(cheese3d_ctx ctx);
+
+#endif
diff --git a/stage3/cheese_demo.c b/stage3/cheese_demo.c
new file mode 100644
index 0000000..c545c70
--- /dev/null
+++ b/stage3/cheese_demo.c
@@ -0,0 +1,118 @@
+#include "cheese3d.h"
+#include "math3d.h"
+#include "heap.h"
+#include "rng.h"
+
+static u32 *make_cheese_texture(u32 tex_w, u32 tex_h)
+{
+	u32 *texture = malloc(tex_h * tex_w * sizeof *texture);
+	for (u32 y = 0; y < tex_h; y++)
+	for (u32 x = 0; x < tex_w; x++) {
+		texture[y*tex_w+x] = 0xFFFFDE74;
+	}
+
+	int holes = 25 + rand() % 5;
+	for (int i = 0; i < holes; i++) {
+		u32 xo = rand() % tex_w;
+		u32 yo = rand() % tex_h;
+		i32 radius = 20 + rand() % 5;
+
+		for (i32 xi = -radius; xi <= radius; xi++) {
+			i32 x = xi+xo;
+			if (!(x >= 0 && x < (i32)tex_w))
+				continue;
+			double hi = sin(acos((double) xi / (double) radius))*radius;
+			for (i32 yi = -hi; yi <= hi; yi++) {
+				i32 y = yi+yo;
+				if (!(y >= 0 && y < (i32)tex_h))
+					continue;
+				texture[y*tex_w+x] = 0xFFFCA425;
+			}
+		}
+	}
+
+	return texture;
+}
+
+void cheese_demo()
+{
+	cheese3d_ctx ctx = cheese3d_create_default(0xFF000000);
+
+	const u32 tex_w = 500;
+	const u32 tex_h = 375;
+
+	u32 crust_top = 0xFFFFD35F;
+	u32 crust_back = 0xFFF2B71B;
+	u32 *crust_right = make_cheese_texture(tex_w, tex_h);
+	u32 *crust_left = make_cheese_texture(tex_w, tex_h);
+
+	texture textures[24];
+	for (int i =  0; i <  6; i++) textures[i] = (texture) { 1, 1, &crust_top };
+	for (int i =  6; i < 12; i++) textures[i] = (texture) { 1, 1, &crust_back };
+	for (int i = 12; i < 18; i++) textures[i] = (texture) { tex_w, tex_h, crust_right };
+	for (int i = 18; i < 24; i++) textures[i] = (texture) { tex_w, tex_h, crust_left };
+
+	// triangles are counter-clockwise
+	vertex prism[24] = {
+		// top face
+		VERT(-0.5, +0.5, -0.5, 0.0, 0.0),
+		VERT(+0.5, +0.5, -0.5, 0.0, 0.0),
+		VERT( 0.0, +0.5, +0.5, 0.0, 0.0),
+		// bottom face (🥺)
+		VERT(-0.5, -0.5, -0.5, 0.0, 0.0),
+		VERT( 0.0, -0.5, +0.5, 0.0, 0.0),
+		VERT(+0.5, -0.5, -0.5, 0.0, 0.0),
+		// back face
+		QUAD(
+			VERT(-0.5, +0.5, -0.5, 0.0, 0.0),
+			VERT(-0.5, -0.5, -0.5, 0.0, 0.0),
+			VERT(+0.5, -0.5, -0.5, 0.0, 0.0),
+			VERT(+0.5, +0.5, -0.5, 0.0, 0.0)
+		),
+		// right face
+		QUAD(
+			VERT(+0.5, +0.5, -0.5, 0.0, 0.0),
+			VERT(+0.5, -0.5, -0.5, 0.0, 1.0),
+			VERT( 0.0, -0.5, +0.5, 1.0, 1.0),
+			VERT( 0.0, +0.5, +0.5, 1.0, 0.0)
+		),
+		// left face
+		QUAD(
+			VERT( 0.0, +0.5, +0.5, 1.0, 0.0),
+			VERT( 0.0, -0.5, +0.5, 1.0, 1.0),
+			VERT(-0.5, -0.5, -0.5, 0.0, 1.0),
+			VERT(-0.5, +0.5, -0.5, 0.0, 0.0)
+		),
+	};
+
+	float angle = 0;
+
+	for (;;) {
+		angle += 0.3;
+
+		float transform[4][4];
+		float tmp[4][4];
+
+		mat_perspective(transform, rad(45.0), (float)ctx.width/(float)ctx.height, 0.01, 25.0);
+
+		mat_translate(tmp, (float []) { 0.0, -0.0, 10.0 });
+		mat_mul(transform, tmp);
+
+		mat_rot_x(tmp, rad(-20));
+		mat_mul(transform, tmp);
+
+		mat_rot_y(tmp, rad(angle));
+		mat_mul(transform, tmp);
+
+		mat_scale(tmp, (float []){ 3.5, 3.0, 4.0 });
+		mat_mul(transform, tmp);
+
+		cheese3d_clear(ctx, true, true);
+		cheese3d_render(ctx, 24, prism, textures, transform);
+		cheese3d_display(ctx);
+	}
+
+	cheese3d_destroy(ctx);
+	free(crust_right);
+	free(crust_left);
+}
diff --git a/stage3/cheese_demo.h b/stage3/cheese_demo.h
new file mode 100644
index 0000000..5371220
--- /dev/null
+++ b/stage3/cheese_demo.h
@@ -0,0 +1,6 @@
+#ifndef CHEESE_DEMO_H
+#define CHEESE_DEMO_H
+
+void cheese_demo();
+
+#endif
diff --git a/stage3/math.h b/stage3/math.h
index 6f7ae58..b067409 100644
--- a/stage3/math.h
+++ b/stage3/math.h
@@ -18,6 +18,23 @@ static inline double sin(double x)
 	return x;
 }
 
+static inline double cos(double x)
+{
+	asm("fldl %1; fcos; fstpl %0":"=m"(x):"m"(x));
+	return x;
+}
+
+static inline double tan(double x)
+{
+	asm("fldl %1; fptan; fstpl %0; fstpl %0":"=m"(x):"m"(x));
+	return x;
+}
+
+static inline void sincos(double x, double *sin, double *cos)
+{
+	asm("fldl %2; fsincos; fstpl %0; fstpl %1":"=m"(*sin),"=m"(*cos):"m"(x));
+}
+
 static inline double rad(double x)
 {
 	return PI / 180.0 * x;
diff --git a/stage3/math3d.h b/stage3/math3d.h
new file mode 100644
index 0000000..5d9c759
--- /dev/null
+++ b/stage3/math3d.h
@@ -0,0 +1,102 @@
+#ifndef MATH3D_H
+#define MATH3D_H
+
+#include "math.h"
+
+static inline void mat_id(float mat[4][4])
+{
+	for (int i = 0; i < 4; i++)
+	for (int j = 0; j < 4; j++)
+		mat[i][j] = i == j ? 1.0 : 0.0;
+}
+
+static inline void mat_translate(float mat[4][4], float vec[3])
+{
+	mat_id(mat);
+	for (int i = 0; i < 3; i++)
+		mat[3][i] = vec[i];
+}
+
+static inline void mat_scale(float mat[4][4], float vec[3])
+{
+	mat_id(mat);
+	for (int i = 0; i < 3; i++)
+		mat[i][i] = vec[i];
+}
+
+static inline void mat_rot_x(float mat[4][4], float a)
+{
+	mat_id(mat);
+	mat[1][1] = cos(a); mat[2][1] = -sin(a);
+	mat[1][2] = sin(a); mat[2][2] = cos(a);
+}
+
+static inline void mat_rot_y(float mat[4][4], float a)
+{
+	mat_id(mat);
+	mat[0][0] = cos(a); mat[2][0] = sin(a);
+	mat[0][2] = -sin(a); mat[2][2] = cos(a);
+}
+
+static inline void mat_rot_z(float mat[4][4], float a)
+{
+	mat_id(mat);
+	mat[0][0] = cos(a); mat[1][0] = -sin(a);
+	mat[0][1] = sin(a); mat[1][1] = cos(a);
+}
+
+static inline void mat_copy(float dst[4][4], float src[4][4])
+{
+	for (int i = 0; i < 4; i++)
+	for (int j = 0; j < 4; j++)
+		dst[i][j] = src[i][j];
+}
+
+static inline void mat_mul(float a[4][4], float b[4][4])
+{
+	float out[4][4];
+	for (int i = 0; i < 4; i++)
+	for (int j = 0; j < 4; j++) {
+		out[i][j] = 0;
+		for (int k = 0; k < 4; k++)
+			out[i][j] += a[k][j] * b[i][k];
+	}
+	mat_copy(a, out);
+}
+
+static inline void vec_copy(float dst[4], float src[4])
+{
+	for (int i = 0; i < 4; i++)
+		dst[i] = src[i];
+}
+
+static inline void mat_mul_vec(float mat[4][4], float vec[4])
+{
+	float out[4];
+
+	for (int j = 0; j < 4; j++) {
+		out[j] = 0;
+		for (int k = 0; k < 4; k++)
+			out[j] += mat[k][j] * vec[k];
+	}
+
+	vec_copy(vec, out);
+}
+
+
+static inline void mat_perspective(float mat[4][4], float fov, float aspect, float near, float far)
+{
+	float a = 1.0 / tan(fov / 2.0);
+
+	mat_scale(mat, (float []) { a/aspect, a, -(far + near) / (far - near) });
+	mat[2][3] = -1.0;
+	mat[3][2] = -2.0 * far * near / (far - near);
+	mat[3][3] = 0.0;
+}
+
+static inline float tri_area(float a[2], float b[2], float c[2])
+{
+	return (b[0] - a[0])*(c[1] - a[1]) - (b[1] - a[1])*(c[0] - a[0]);
+}
+
+#endif
diff --git a/stage3/rng.c b/stage3/rng.c
new file mode 100644
index 0000000..a52b449
--- /dev/null
+++ b/stage3/rng.c
@@ -0,0 +1,9 @@
+#include "rng.h"
+
+int rand()
+{
+	static unsigned long int next = 1;
+
+	next = next * 1103515245 + 12345;
+	return (unsigned int) (next/65535) % 32768;
+}
diff --git a/stage3/rng.h b/stage3/rng.h
new file mode 100644
index 0000000..fe83ff7
--- /dev/null
+++ b/stage3/rng.h
@@ -0,0 +1,6 @@
+#ifndef RNG_H
+#define RNG_H
+
+int rand();
+
+#endif
diff --git a/stage3/shell.c b/stage3/shell.c
index 825723b..079580e 100644
--- a/stage3/shell.c
+++ b/stage3/shell.c
@@ -9,8 +9,9 @@
 #include "io.h"
 #include "math.h"
 #include "clock.h"
-#include "pic.h"
 #include "thread.h"
+#include "rng.h"
+#include "cheese_demo.h"
 
 static void cmd_echo(str arg)
 {
@@ -142,14 +143,6 @@ static void cmd_clear(str arg)
 	font_clear_screen();
 }
 
-int rand()
-{
-	static unsigned long int next = 1;
-
-	next = next * 1103515245 + 12345;
-	return (unsigned int) (next/65535) % 32768;
-}
-
 static void cmd_love(str arg)
 {
 	if (arg.len == 0)
@@ -237,37 +230,7 @@ void cmd_shutdown(str arg)
 void cmd_cheese(str arg)
 {
 	(void) arg;
-
-	const u32 texsize = 400;
-	u32 *texture = malloc(texsize * texsize * sizeof *texture);
-	for (u32 y = 0; y < texsize; y++)
-	for (u32 x = 0; x < texsize; x++) {
-		texture[y*texsize+x] = 0xfff5c92a;
-	}
-
-	int holes = 40 + rand() % 5;
-	for (int i = 0; i < holes; i++) {
-		u32 xo = rand() % texsize;
-		u32 yo = rand() % texsize;
-		i32 radius = 15 + rand() % 5;
-
-		for (i32 xi = -radius; xi <= radius; xi++) {
-			i32 x = xi+xo;
-			if (!(x >= 0 && x < (i32)texsize))
-				continue;
-			double hi = sin(acos((double) xi / (double) radius))*radius;
-			for (i32 yi = -hi; yi <= hi; yi++) {
-				i32 y = yi+yo;
-				if (!(y >= 0 && y < (i32)texsize))
-					continue;
-				texture[y*texsize+x] = 0xff302b24;
-			}
-		}
-	}
-
-	gfx_draw_img(gfx_info->width-texsize, 0, texsize, texsize, texture);
-
-	free(texture);
+	cheese_demo();
 }
 
 struct __attribute__((packed)) {