Unreliable tetrahedron renderer

I set myself the following additional goal (devised by me):

Write a program to display simple 3D shapes in a terminal. In its current form, the program draws a regular tetrahedron, which can be looked at from different angles. The result tends to flicker on terminals with slow output speeds; using ncurses would have prevented this. The task was appropriate because it involves reading (characters), writing and arithmetic. Although I have some experience with C, I had none with C++, so I tried to use new language features where I could. The program expects a 24x80 character terminal. It took me more than 150 minutes to write, but I had fun.

The solution is in the files: Makefile (an adaptation of an adaptation of one I found online a while ago) main.cc vec_ops.hh vec_ops.cc render.hh render.cc world_setup.hh world_setup.cc input.hh input.cc

// Here begins file Makefile

CXXFLAGS=-Wall -g -std=c++11
.DEFAULT:= all
.PHONY: all

OBJECTS=main.o vec_ops.o render.o world_setup.o input.o

all: main

main: $(OBJECTS)
	c++ $(CXXFLAGS) $(OBJECTS) -o main 

clean:
	rm *.o main


// Here begins file main.cc

#include 
#include 

#include "render.hh"
#include "world_setup.hh"
#include "input.hh"

/*
 * Controls:
 * Camera up: W
 * Camera down: S
 * Camera left: A
 * Camera right: D
 * Rotate camera left/right: E/R
 * Rotate camera up/down: F/V
 */

int main(int argc, char *argv[])
{

	/* These should be even for convenience */
	int screen_x = 80;
	int screen_y = 24;
	Renderer renderer(screen_y, screen_x, 3.0, 100);

	setup(&renderer);
	input_setup();

	while (1) {
		handle_input(&renderer);
		Render_symbol ***a = renderer.render();
		for (int i = 0; i < screen_y; ++i)
		std::cout << "n";
		for (int i = 0; i < screen_y; ++i) {
			for (int j = 0; j < screen_x; ++j) {
				std::cout << (*a)[i][j].get_string();
			}
			std::cout << "n";
		}
		/* Limit framerate. Still doesn't play nicely on slow terminals */
		struct timespec u = {.tv_sec = 0, .tv_nsec = 1670000l};
		nanosleep (&u, 0);

	}


	return 0;
}

// Here begins file vec_ops.hh

#ifndef VEC_OPS_H_I
#define VEC_OPS_H_I

/*
 * Implemented using vector rather than double[3] because vector
 * is C++-specific
 */
#include 
/* Only need operations for vectors of doubles */
double vec_dot(std::vector a, std::vector b);
std::vector vec_add(std::vector a, std::vector b);
/* It is convenient to have a separate subtraction function. Returns a - b */
std::vector vec_sub(std::vector a, std::vector b);
std::vector vec_mult(std::vector a, double b);
std::vector vec_cross(std::vector a, std::vector b);
/* returns the reciprocal vector of a for the pair of 2d vectors (a, b) */
std::vector vec_recip2(std::vector a, std::vector b);

/* For debugging purposes */
void vec_print(std::vector a);
#endif

// Here begins file vec_ops.cc

#include 
#include 

#include "vec_ops.hh"

/* Calculates scalar product of two vectors of doubles */
double vec_dot(std::vector a, std::vector b)
{
	size_t s = a.size();
	if (s - b.size()) {
		/*
		 * Inner product undefined for vectors of different dimensions. Should
		 * never even be called with such arguments, so failing silently is
		 * okay
		 */
		return 0.0;
	}

	double r = 0;

	for (size_t i = 0; i < s; ++i) 
		r += a[i] * b[i];
	return r;

}

/* Performs vector addition of two vectors of doubles */

std::vector vec_add(std::vector a, std::vector b)
{
	size_t s = a.size();
	if (s - b.size()) {
		/*
		 * Addition undefined for vectors of different dimensions. Should
		 * never even be called with such arguments, so failing silently is
		 * okay
		 */
		return std::vector(a);
	}

	std::vector r (s);

	for (size_t i = 0; i < s; ++i) 
		r[i] = a[i] + b[i];
	return r;

}

/* It is convenient to have a separate subtraction function. Returns a - b */
std::vector vec_sub(std::vector a, std::vector b)
{
	return vec_add(a, vec_mult(b, -1.0));
}

/* Multiplies the vector a by the scalar b */
std::vector vec_mult(std::vector a, double b)
{
	std::vector r (a);
	for (size_t i = 0; i < r.size(); ++i)
		r[i] *= b;
	return r;

}

void vec_print(std::vector a)
{
	std::cout << "[";
	for (size_t i = 0; i < a.size(); ++i) {
		if (i)
			std::cout << ", ";
		std::cout << a[i];
	}
	std::cout << "]";
	/* No trailing newline so that it can be printed inline */
	return;
}

/* Calculates vector product of two vectors of length 3 */
std::vector vec_cross(std::vector a, std::vector b)
{
	size_t sa = a.size();
	if ((sa - 3) || (sa - b.size())) {
		return std::vector(sa, 0);
	}
	std::vector r(3, 0);
	for (size_t i = 0; i < 3; ++i) 
		r[i] = a[(i + 1) % 3] * b[(i + 2) % 3] - b[(i + 1) % 3] * a[(i + 2) % 3];
	return r;

}


std::vector vec_recip2(std::vector a, std::vector b)
{
	if ((a.size() - b.size()) || (a.size() - 2))
		return std::vector(a.size(), 0);

	std::vector r({-1.0*b[1], b[0]});
	return vec_mult(r, 1.0/vec_dot(r, a));
}

// Here begins file render.hh

#ifndef RENDER_H_I
#define RENDER_H_I

#include 
#include 

/* These are the colour codes for ANSI terminal colours */
enum fg_colour {
	fg_none = 0,
	fg_black = 30,
	fg_red = 31,
	fg_green = 32,
	fg_yellow = 33,
	fg_blue = 34,
	fg_magenta = 35,
	fg_cyan = 36,
	fg_white = 37,
	/* Bright colours */
	fg_b_black = 90,
	fg_b_red = 91,
	fg_b_green = 92,
	fg_b_yellow = 93,
	fg_b_blue = 94,
	fg_b_magenta = 95,
	fg_b_cyan = 96,
	fg_b_white = 97
};

enum bg_colour {
	bg_none = 0,
	bg_black = 40,
	bg_red = 41,
	bg_green = 42,
	bg_yellow = 43,
	bg_blue = 44,
	bg_magenta = 45,
	bg_cyan = 46,
	bg_white = 47,
	/* Bright colours */
	bg_b_black = 100,
	bg_b_red = 101,
	bg_b_green = 102,
	bg_b_yellow = 103,
	bg_b_blue = 104,
	bg_b_magenta = 105,
	bg_b_cyan = 106,
	bg_b_white = 107
};

/* Describes what to draw on the screen when a shape is rendered */
class Render_symbol {
	public:
		Render_symbol(char c, enum fg_colour f,	enum bg_colour b);
		std::string get_string();
		/*
		 * For use in Renderer.render() to check whether to overwrite a symbol
		 * because it is covered by something nearer
		 */
		double distance;
	private:
		enum fg_colour fg;
		enum bg_colour bg;
		char character;
};

/*
 * Triangle would look almost exactly the same as a struct, but I'm trying to
 * write something that looks like C++ and not C.
 * Triangles are used to make 3D shapes for rendering.
 */
class Triangle {
	public:
		Triangle(std::vector v[3], Render_symbol line, Render_symbol fill);
		std::vector vertices[3];
		Render_symbol line_symbol;
		Render_symbol fill_symbol;
};

/* Describes a 3D shape */
class Render_object {
	public:
		Render_object();
		std::vector triangles;
		void add_triangle(std::vector verts[3], char line_c = '*',
				enum fg_colour line_fg = fg_none,
				enum bg_colour line_bg = bg_none, char fill_c = ' ',
				enum fg_colour fill_fg = fg_none,
				enum bg_colour fill_bg = bg_none);
};

/*
 * Contains camera information, the list of things to render, and the array of
 * Render_symbols resulting from 3D rendering. Arguments are screen dimensions
 * (in characters), and distance from back of camera to plane
 * (render() works by intersecting lines (from the point at the back of the
 * camera to objects) with a plane, so depth determines field of vision with a 
 * fixed screen width of 5.0)
 */
class Renderer {
	public:
		Renderer(int scr_y, int scr_x, double c_depth, int max_objects);
		/* Returns a pointer to added object in case it needs modifying */
		Render_object *add_object(Render_object obj);
		/*
		 * render() returns a reference to screen, the array of Render_symbols
		 * produced
		 */
		Render_symbol ***render();
		/*
		 * Array is more suitable than a vector here: lacks dynamic
		 * reallocation, but pointers don't spontaneously get invalidated
		 */
		Render_object *render_objects;
		int screen_x, screen_y;

		std::vector camera_pos;
		/* Camera angle to x-axis in xy plane*/
		double camera_xangle;
		/* Camera angle to z-axis */
		double camera_zangle;
	private:
		/* Takes a reference to avoid copying argument */
		void draw_triangle(Triangle *t);
		std::vector *screen_project(Triangle *t);
		/*
		 * Works out if a point (y, x) is inside the triangle spanned by u1 and
		 * u2 with one vertex at r0
		 */
		int is_inside(std::vector r0, std::vector u1,
				std::vector u2, int y, int x);

		/*
		 * Calculates the distance (from the back of the camera) of the point
		 * (y, x) of a triangle with a vertex at r0 and spanned by u1, u2
		 * with the other vertices a distance dc1 or dc2 further from the origin
		 * than r0, given the distance dist0 of r0 from the origin.
		 */
		double dist_calc(std::vector r0, std::vector u1,
				std::vector u2, double dist0, double dc1, double dc2,
				int y, int x);

		double camera_depth;
		/*
		 * Screen will not be in a valid state until render() has been invoked
		 * at least once. Screen memory is allocated when Renderer is
		 * constructed, and there is no mechanism to free it because Renderer
		 * is supposed to be constantly in use.
		 * Entries are ordered (column, row), with (0, 0) in top left-hand
		 * corner of screen, as that is convenient for output.
		 */
		Render_symbol **screen;
		int n_objects, max_objects;
};

#endif

// Here begins file render.cc

#include 
#include 
#include 
#include 
#include 


#include "render.hh"
#include "vec_ops.hh"


Render_symbol::Render_symbol(char c, enum fg_colour f,
		enum bg_colour b)
{
	character = c;
	fg = f;
	bg = b;
	/* Everything should overwrite an unwritten tile */
	distance = std::numeric_limits::infinity();
}

std::string Render_symbol::get_string()
{
	/*
	 * Can get away with e.g. x1b[0;41m, but not x1b[41;0m as a colour
	 * code. The brackets *are* important; otherwise, e.g. 'm' and
	 * this->character get added together
	 */
	return (((((std::string("x1b[") + std::to_string(this->fg)) +
		(this->bg ? std::string(";") + std::to_string(this->bg) : "")) + 'm') +
		this->character) + "x1b[0m");
}

/*
 * Need to specify that local variables line, fill should be created with
 * auto-generated copy constructors, apparently
 */
Triangle::Triangle(std::vector v[3], Render_symbol line,
		Render_symbol fill) : line_symbol(line), fill_symbol(fill)
{
	/* Copy v into list of vertices.*/
	for (int i = 0; i < 3; ++i) {
		this->vertices[i] = std::vector(v[i]);
	}

}

Render_object::Render_object()
{
	this->triangles = std::vector();
}

void Render_object::add_triangle(std::vector verts[3], char line_c,
		enum fg_colour line_fg, enum bg_colour line_bg,
		char fill_c, enum fg_colour fill_fg,
		enum bg_colour fill_bg)
{
	Render_symbol sym_line(line_c, line_fg, line_bg);
	Render_symbol sym_fill(fill_c, fill_fg, fill_bg);
	this->triangles.emplace_back(Triangle(verts, sym_line, sym_fill));
}

Renderer::Renderer(int scr_y, int scr_x, double c_d, int max_objects)
	: camera_pos(3, 0)
{
	this->max_objects = max_objects;
	this->n_objects = 0;
	this->render_objects = (Render_object *) calloc(max_objects,
			sizeof(Render_object));

	this->camera_xangle = 0.0;
	this->camera_zangle = 0.0;
	this->screen_x = scr_x;
	this->screen_y = scr_y;
	this->camera_depth = c_d;

	this->screen = (Render_symbol **) calloc(sizeof(Render_symbol *), scr_y);
	for(int i = 0; i < scr_y; ++i)
		screen[i] = (Render_symbol *) calloc(sizeof(Render_symbol), scr_x);

}

Render_object *Renderer::add_object(Render_object obj)
{
	/* Returns 0 on failure */
	if (this->n_objects - this->max_objects) {
		int n = this->n_objects;
		this->render_objects[n_objects++] = obj;
		return &(render_objects[n]);
	}
	return 0;

}

/* The return value of this function should not be modified. */
Render_symbol ***Renderer::render()
{
	/* First, clear screen */
	for (int i = 0; i < this->screen_y; ++i) {
		for (int j = 0; j < this->screen_x; ++j) {
			this->screen[i][j] = Render_symbol(' ', fg_none, bg_none);
		}
	}

	/* Iterate through objects and draw them */
	Render_object *render_objs = this->render_objects;
	/* Not calling size every iteration of a loop is probably good */
	int n_objs = this->n_objects;
	for (int i = 0; i < n_objs; ++i) {
		std::vector triangles = render_objs[i].triangles;
		size_t n_tria = triangles.size();
		for(size_t j = 0; j < n_tria; ++j) {
			this->draw_triangle(&triangles[j]);
		}
	}
	return &(this->screen);
}

void Renderer::draw_triangle(Triangle *t)
{
	/*
	 * 1: find on-screen coordinates and distances from screen of triangle
	 * vertices
	 */

	std::vector *scs = this->screen_project(t);
	if (!scs)
		return;

	/* Triangles are thin and cannot be seen side-on */
	for (int i = 0; i < 3; ++i) {
		for (int j = i+1; j <3; ++j) {
			if ((scs[i][0] - scs[j][0]) || (scs[i][1] - scs[j][1]))
				continue;
			return;
		}
	}

	/*
	 * 2: shade in area bounded by all cells intersected by edges of triangle,
	 * recording approximate distance from each cell to triangle (this is not a
	 * serious program, so a little laziness is excusable).
	 */
	/*
	 * Coordinates are relative to centre of screen in scs, but need to convert
	 * to characters (8pxX15px on my terminal) to write to screen. Multiply by
	 * screen_x/2.5 (for x) (5 unit wide camera plane) or (8/15)*screen_x/(2.5)
	 * (for y)
	 */
	double ys = 15.0/8.0;
	double scr_x_c = this->screen_x / 5.0;
	double scr_y_c = scr_x_c / ys;

	for (int i = 0; i < 3; ++i) {
		scs[i][1] *= scr_x_c;
		scs[i][0] *= scr_y_c;
	}


	double ymin = floor(std::min(scs[0][0], std::min(scs[1][0], scs[2][0])));
	double ymax = ceil(std::max(scs[0][0], std::max(scs[1][0], scs[2][0])));
	double xmin = floor(std::min(scs[0][1], std::min(scs[1][1], scs[2][1])));
	double xmax = ceil(std::max(scs[0][1], std::max(scs[1][1], scs[2][1])));

	/* Use convex combination trickery to shade triangle only */
	double dist0 = scs[0][2];
	double dc1 = scs[1][2] - dist0;
	double dc2 = scs[2][2] - dist0;

	std::vector r0({scs[0][0], scs[0][1]});

	std::vector u1 = vec_sub(scs[1], scs[0]);
	u1.pop_back();
	std::vector u2 = vec_sub(scs[2], scs[0]);
	u2.pop_back();


	/* Features corrections to avoid drawing off-screen */
	for (int y = (int) std::max(-1.0*screen_y/2, floor(ymin));
			y <= std::min(1.0*screen_y/2 - 1.0, ceil(ymax)); ++y) {

		for (int x = (int) std::max(-1.0*screen_x/2, floor(xmin));
				x <= std::min(1.0*screen_x/2 - 1.0, ceil(xmax)); ++x) {

			/* Map coordinates to array indices */
			int yp = screen_y/2 - 1 - y;
			int xp = x + screen_x/2;
			double dist = this->dist_calc(r0, u1, u2, dist0, dc1, dc2, y, x);
			/* Nearer things cover farther ones */
			if (dist >= screen[yp][xp].distance) {
				continue;
			}
			if (this->is_inside(r0, u1, u2, y, x)) {
				/* Check if this is at the edge of a triangle */
				int edge = 0;
				for (int p = -1; p <= 1 && !edge; p+=2) {
					for (int q = -1; q <=1 && !edge; q+=2) {
						if (!(this->is_inside(r0, u1, u2, y+p, x+q))) {
							this->screen[yp][xp] = Render_symbol(t->line_symbol);
							this->screen[yp][xp].distance = dist;
							edge = 1;
						}
					}
				}
				if (edge)
					continue;
				/* If this isn't the edge of a triangle, draw accordingly */
				this->screen[yp][xp] = Render_symbol(t->fill_symbol);
				this->screen[yp][xp].distance = dist;
			}
		}
	}
}
std::vector *Renderer::screen_project(Triangle *t)
{
	/*
	 * Return value is pointer to static variable to avoid repeated allocations;
	 * don't need result of using this on two triangles at the same time, so
	 * no problem. Returns 0 if line from a vertex to camera never intersects
	 * camera plane; that's not a problem as in that case, the triangle is
	 * either behind the plane or intersects the camera; either way, this is
	 * not normal.
	 */

	/* Components: screen x coordinate, screen y coordinate, distance from scr */
	static std::vector ret[3];
	
	double d = this->camera_depth;
	double cx = this->camera_xangle;
	double cz = this->camera_zangle;
	double a, b, l, q;
	std::vector C0 = this->camera_pos;
	std::vector Cr({cos(cx), sin(cx), 0});
	std::vector Cu({sin(-cz)*sin(cx), sin(cz)*cos(cx), cos(cz)});
	std::vector Cf = vec_cross(Cu, Cr);

	for (int i = 0; i < 3; ++i) {
		/* I worked this out on paper; explaining it in comments would be a pain */
		std::vector P = t->vertices[i];
		std::vector A = vec_sub(P, C0);
		q = vec_dot(A, Cf);

		if (!q or (vec_dot(Cf, A) < 0))
			return 0;

		l = d/q;
		b = vec_dot(A, Cr) * l;
		a = vec_dot(A, Cu) * l;

		ret[i] = std::vector({a, b, vec_dot(vec_sub(C0, P),
					vec_sub(C0, P))});
	}
	return ret;
}

int Renderer::is_inside(std::vector r0, std::vector u1,
		std::vector u2, int y, int x)
{
	/*
	 * These are guaranteed to exist because we earlier eliminated the case 
	 * where any of scs[0] [1] or [2] have equal [0] and [1] components
	 */
	std::vector v1 = vec_recip2(u1, u2);
	std::vector v2 = vec_recip2(u2, u1);

	std::vector r = vec_sub(std::vector({y*1.0, x*1.0}),
			r0);
	double c1 = vec_dot(r, v1);
	double c2 = vec_dot(r, v2);
	return (c1 <= 1.0 && c1 >= 0.0 && c2 <=1.0 && c2 >= 0.0 && (c1 + c2) <= 1.0);
}


double Renderer::dist_calc(std::vector r0, std::vector u1,
		std::vector u2, double dist0, double dc1, double dc2,
		int y, int x)
{
	std::vector v1 = vec_recip2(u1, u2);
	std::vector v2 = vec_recip2(u2, u1);
	std::vector r = vec_sub(std::vector({y*1.0, x*1.0}), r0);
	return (dist0 + dc1*vec_dot(r, v1) + dc2*vec_dot(r, v2));

}

// Here begins file world_setup.hh

#ifndef WORLD_SETUP_I
#define WORLD_SETUP_I

#include "render.hh"

/* Function to create something to look at */
void setup(Renderer *renderer);

#endif

// Here begins file world_setup.cc

#include 
#include 
#include "world_setup.hh"
#include "vec_ops.hh"

void setup(Renderer *renderer)
{

	Render_object obj;
	/* Draw a regular tetrahedron */
	
	double length = 15.0;
	std::vector base({0.0, 60.0, -5.0});
	std::vector vertices[4] = {{0.0, -1.0, 0.0},
									   {-cos(M_PI/6), sin(M_PI/6), 0.0},
									   {cos(M_PI/6), sin(M_PI/6), 0.0},
									   {0.0, 0.0, sqrt(2.0/3.0)}};
	for (int i = 0; i < 4; ++i) {
		vertices[i] = vec_add(vec_mult(vertices[i], length), base);
	}
	for (int i = 0; i < 4; ++i) {
		for (int j = i + 1; j < 4; ++j) {
			for (int k = j + 1; k < 4; ++k) {
				std::vector p[3] = {vertices[i], vertices[j],
					vertices[k]};
				obj.add_triangle(p, '-', fg_red, bg_none, '*', fg_none, bg_white);
			}
		}
	}


	renderer->add_object(obj);
	return;

}

// Here begins file input.hh

#ifndef INPUT_H_I
#define INPUT_H_I

#include "render.hh"

/* sets up terminal for input */
void input_setup();

/* Provides non-blocking input handling */
void handle_input(Renderer *renderer);

#endif

// Here begins file input.cc

#include 
#include 
#include 
#include 

#include "input.hh"
#include "vec_ops.hh"

static void move_lateral(Renderer *rend, double distance);
static void move_vertical(Renderer *rend, double distance);

void input_setup()
{
	struct termios t_conf;
	tcgetattr(0, &t_conf);
	/* Disable canonical mode to read input character by character */
	t_conf.c_lflag &= ~ICANON;
	/* Disable input echoing */
	t_conf.c_lflag &= ~ECHO;
	/* Minimum read size: zero characters (allows non-blocking read) */
	t_conf.c_cc[VMIN] = 0;
	/* Reading times out immediately */
	t_conf.c_cc[VTIME] = 0;
	tcsetattr(0, TCSANOW, &t_conf);
}


void handle_input(Renderer *renderer)
{
	/* Check for user input */
	char in = 0;
   	read(0, &in, 1);
	while (in) {
		switch (in) {
			case 'a':
				move_lateral(renderer, -0.2);
				break;
			case 'd':
				move_lateral(renderer, 0.2);
				break;
			case 'w':
				move_vertical(renderer, 0.2);
				break;
			case 's':
				move_vertical(renderer, -0.2);
				break;
			case 'e':
				renderer->camera_xangle += 0.02;
				break;
			case 'r':
				renderer->camera_xangle -= 0.02;
				break;
			case 'f':
				renderer->camera_zangle -= 0.02;
				break;
			case 'v':
				renderer->camera_zangle += 0.02;
				break;

		}

		in = 0;
		read(0, &in, 1);
	}
}


static void move_lateral(Renderer *rend, double distance)
{
	std::vector lat_vec({cos(rend->camera_xangle),
			sin(rend->camera_xangle), 0});
	lat_vec = vec_mult(lat_vec, distance);
	rend->camera_pos = vec_add(rend->camera_pos, lat_vec);
}

static void move_vertical(Renderer *rend, double distance)
{
	std::vector vert_vec({-sin(rend->camera_zangle) *
			sin(rend->camera_xangle),
			sin(rend->camera_zangle) * cos(rend->camera_xangle),
			cos(rend->camera_zangle)});

	vert_vec = vec_mult(vert_vec, distance);
	rend->camera_pos = vec_add(rend->camera_pos, vert_vec);
}