Free games for graphing calculators: NumWorks, TI-Nspire CX, Casio fx-CG50 and soon TI-84 Plus CE. Balatro, Celeste, Hollow Knight, Minecraft and more.
C calculatorcalculator-gamescasiochesscrossy-roaddrive-madfx-cg50gamesgeometry-dashgraphing-calculatorndlessnumworksnumworks-appsnumworks-calculatornumworks-gamenumworks-gamestetristi-84-plus-ceti-nspire
/* Strip-based z-buffered renderer for Fancade voxel objects (orthographic camera). */
#pragma GCC optimize ("O2") /* (drawn every frame: fast, while the rest of the game is built small) */
#include <string.h>
#include <math.h>
#ifdef HOST
#include <stdio.h>
#include <stdlib.h>
#endif
#include "render.h"
#include "world.h"
#include "platform.h"
#include "vm.h"
#include "physics.h"
const uint8_t palette_rgb[34][3] = {
{0, 0, 0}, {29, 29, 40}, {63, 63, 80}, {101, 103, 121}, {144, 147, 164}, {191, 194, 205}, {255, 255, 255},
{148, 83, 94}, {192, 109, 128}, {225, 153, 152}, {253, 181, 168}, {255, 219, 197}, {255, 243, 242},
{192, 54, 80}, {255, 74, 104}, {255, 154, 154}, {201, 80, 64}, {255, 112, 83}, {255, 168, 129},
{232, 168, 0}, {255, 213, 0}, {255, 255, 122}, {0, 136, 76}, {66, 195, 79}, {181, 255, 110},
{0, 108, 218}, {0, 142, 255}, {0, 193, 255}, {104, 83, 162}, {140, 111, 217}, {176, 138, 255},
{235, 112, 171}, {255, 149, 206}, {255, 185, 232}};
Camera cam;
uint16_t sky565;
static vec3 light_to; /* direction towards the light */
static const float AMB[3] = {0.764f, 0.773f, 0.839f};
static const float LEFF[3] = {0.444f, 0.423f, 0.304f};
/* the strip's colours: on main's stack (render_set_buffer); the depth of the strip being drawn: on
* render_strip's stack (the calculator gives apps 32 KB of stack apart from their RAM, and some calculator
* software gives apps less RAM than 23.2's 148928 bytes) */
static uint16_t *cbuf;
static uint16_t *zbuf;
void render_set_buffer(uint16_t *b) { cbuf = b; }
typedef uint32_t __attribute__((may_alias)) u32a;
static int strip_y0, strip_y1; /* current strip rows [y0, y1) */
static int clip_x0, clip_x1;
/* per object, per frame: screen rows covered and part cache offset */
typedef struct {
int16_t ymin, ymax;
uint16_t pcache;
} RObj;
static RObj *robj;
uint16_t rgb565(int r, int g, int b) {
if (r > 255) r = 255;
if (g > 255) g = 255;
if (b > 255) b = 255;
if (r < 0) r = 0;
if (g < 0) g = 0;
if (b < 0) b = 0;
return (uint16_t)((r >> 3) << 11 | (g >> 2) << 5 | (b >> 3));
}
void shade_color(int pal, vec3 n, int *r, int *g, int *b) {
float k = vdot(n, light_to);
if (k < 0) k = 0;
const uint8_t *c = palette_rgb[pal];
*r = (int)(c[0] * (AMB[0] + k * LEFF[0]) + 0.5f);
*g = (int)(c[1] * (AMB[1] + k * LEFF[1]) + 0.5f);
*b = (int)(c[2] * (AMB[2] + k * LEFF[2]) + 0.5f);
}
static uint16_t axis_col[34 * 6];
static uint8_t axis_ok[34 * 6 / 8 + 1];
void light_set(const quat *rot) {
vec3 d = qrot(*rot, v3(0, 0, 1));
light_to = vscale(d, -1);
memset(axis_ok, 0, sizeof axis_ok);
}
/* ------------------------------------------------------------------ camera */
void cam_default(void) {
cam.focus = v3(0, 0, 0);
cam.rot = qeuler(22.5f, 22.5f, 0);
cam.range = 50;
cam.perspective = 0;
cam.shake = v3(0, 0, 0);
cam.cx = SCREEN_W * 0.5f;
cam.cy = SCREEN_H * 0.5f;
cam.zoom_mul = 1;
cam.roll = 0;
quat l = qeuler(45, -45, 0);
light_set(&l);
cam_update();
}
void cam_update(void) {
cam.right = qrot(cam.rot, v3(1, 0, 0));
cam.up = qrot(cam.rot, v3(0, 1, 0));
cam.fwd = qrot(cam.rot, v3(0, 0, 1));
float zoom = cam.range * 0.1f;
if (zoom < 0.1f) zoom = 0.1f;
cam.scale = (SCREEN_H * 0.5f) / zoom * cam.zoom_mul;
if (cam.roll != 0) {
float c = cosf(cam.roll), sn = sinf(cam.roll);
vec3 r = cam.right, u = cam.up;
cam.right = vadd(vscale(r, c), vscale(u, sn));
cam.up = vsub(vscale(u, c), vscale(r, sn));
}
}
void cam_view(float cx, float cy, float zoom_mul, float roll) {
cam.cx = cx;
cam.cy = cy;
cam.zoom_mul = zoom_mul;
cam.roll = roll;
cam_update();
}
void cam_set(const vec3 *pos, const quat *rot, const float *range, int perspective) {
if (pos) cam.focus = *pos;
if (rot) cam.rot = qnorm(*rot);
if (range) cam.range = *range;
cam.perspective = perspective;
cam_update();
}
vec3 cam_world_to_screen(vec3 p) {
vec3 d = vsub(p, cam.focus);
return v3(cam.cx + vdot(d, cam.right) * cam.scale, cam.cy - vdot(d, cam.up) * cam.scale,
vdot(d, cam.fwd));
}
void cam_screen_to_world(float sx, float sy, vec3 *near, vec3 *far) {
float x = (sx - cam.cx) / cam.scale, y = (cam.cy - sy) / cam.scale;
vec3 b = vadd(cam.focus, vadd(vscale(cam.right, x), vscale(cam.up, y)));
*near = vsub(b, vscale(cam.fwd, 50));
*far = vadd(b, vscale(cam.fwd, 150));
}
/* --------------------------------------------------------------- raster */
#define ZOFF 48.0f
#define ZSCALE 512.0f
static inline int iceil(float v) {
#if defined(__arm__) && defined(__ARM_FP)
/* one VCVTP instruction (FPv5); past 2^31 the result is what the old (int)v + (v > (float)(int)v) gave */
int i = (int)__builtin_lceilf(v);
if (__builtin_expect(i == INT32_MAX, 0) && v > 2147483648.0f) i = INT32_MIN;
return i;
#else
int i = (int)v;
return i + (v > (float)i);
#endif
}
/* Rasterise the parallelogram P0 + s*U + t*V (s, t in [0,1)) with a planar depth.
* ds/dx, ds/dy, dt/dx, dt/dy map screen offsets from P0 to (s, t); ix* are 1/(ds/dx), 1/(dt/dx). */
typedef struct {
float dsdx, dsdy, dtdx, dtdy, isx, itx;
} PInv;
/* Fancade's floor, an endless plane at y = 0, hides whatever is below it: while an object reaching below it is
* drawn, world y at a pixel is fl_k + fl_x * x + fl_y * y + fl_z * depth */
static bool fl_on;
static float fl_k, fl_x, fl_y, fl_z;
/* the rows y0 <= y < y1 of the strip covered by a parallelogram (see raster); `plain`: both pairs of edges
* slant and the floor is off (most quads), so those tests drop out of the row loop */
static inline __attribute__((always_inline)) void raster_rows(int y0, int y1, float X0, float Y0, const PInv *pi,
float z0, float zx, float zy, uint16_t color, bool plain) {
/* depth in fixed point: Z(x,y) = (z0 + zx*(x - X0) + zy*(y - Y0) + ZOFF) * ZSCALE */
float zbase = (z0 + ZOFF - zx * X0 - zy * Y0) * ZSCALE;
int32_t dz = (int32_t)(zx * ZSCALE * 256.0f);
float dy = y0 + 0.5f - Y0;
float sr = pi->dsdy * dy, tr = pi->dtdy * dy; /* s, t at (X0, row centre) */
for (int y = y0; y < y1; y++, sr += pi->dsdy, tr += pi->dtdy) {
float xl, xr;
if (plain || pi->isx != 0) {
float a = -sr * pi->isx, b = (1 - sr) * pi->isx;
if (a < b) xl = a, xr = b;
else xl = b, xr = a;
} else {
if (sr < 0 || sr >= 1) continue;
xl = -1e9f, xr = 1e9f;
}
if (plain || pi->itx != 0) {
float a = -tr * pi->itx, b = (1 - tr) * pi->itx;
if (a > b) {
float t = a;
a = b;
b = t;
}
if (a > xl) xl = a;
if (b < xr) xr = b;
} else if (tr < 0 || tr >= 1) {
continue;
}
if (xl >= xr) continue;
int x0 = iceil(X0 + xl - 0.5f), x1 = iceil(X0 + xr - 0.5f);
if (x0 < clip_x0) x0 = clip_x0;
if (x1 > clip_x1) x1 = clip_x1;
float yc = y + 0.5f;
if (!plain && fl_on) {
/* world y along the row: a + b * (pixel centre x) */
float a = fl_k + fl_y * yc + fl_z * (z0 - zx * X0 + zy * (yc - Y0)), b = fl_x + fl_z * zx, e = -0.01f - a;
if (b > 1e-7f) {
int xa = iceil(e / b - 0.5f);
if (xa > x0) x0 = xa;
} else if (b < -1e-7f) {
int xb = iceil(e / b - 0.5f);
if (xb < x1) x1 = xb;
} else if (e > 0) {
continue;
}
}
if (x0 >= x1) continue;
float zs = zbase + (zx * (x0 + 0.5f) + zy * yc) * ZSCALE;
if (zs < 0) zs = 0;
int32_t z = (int32_t)(zs * 256.0f);
int row = (y - strip_y0) * SCREEN_W;
uint16_t *c = cbuf + row + x0, *ce = cbuf + row + x1;
uint16_t *zp = zbuf + row + x0;
int32_t zend = z + dz * (x1 - x0 - 1);
if (z >= 0 && zend >= 0 && z < (65535 << 8) && zend < (65535 << 8)) {
for (; c < ce; c++, zp++, z += dz) {
uint16_t zz = (uint16_t)(z >> 8);
if (zz <= *zp) {
*zp = zz;
*c = color;
}
}
} else {
for (; c < ce; c++, zp++, z += dz) {
int32_t zz = z >> 8;
if (zz < 0) zz = 0;
if (zz > 65535) zz = 65535;
if ((uint16_t)zz <= *zp) {
*zp = (uint16_t)zz;
*c = color;
}
}
}
}
}
/* The rows of the strip a parallelogram P0 + s*U + t*V (s, t in [0,1)) covers, from its corners' heights
* (U and V's heights uy and vy); false when none. (Not inlined, and without fused multiply-adds: the heights
* are rounded as they were when this was part of raster.) */
__attribute__((noinline, optimize("fp-contract=off"))) static bool quad_rows(float Y0, float uy, float vy, int *py0,
int *py1) {
float ymin = Y0, ymax = Y0;
float ya = Y0 + uy, yb = Y0 + vy, yc2 = Y0 + uy + vy;
if (ya < ymin) ymin = ya;
if (ya > ymax) ymax = ya;
if (yb < ymin) ymin = yb;
if (yb > ymax) ymax = yb;
if (yc2 < ymin) ymin = yc2;
if (yc2 > ymax) ymax = yc2;
int y0 = iceil(ymin - 0.5f), y1 = iceil(ymax - 0.5f);
if (y0 < strip_y0) y0 = strip_y0;
if (y1 > strip_y1) y1 = strip_y1;
*py0 = y0;
*py1 = y1;
return y0 < y1;
}
#if NP_SOFT_FLOAT
#include "np_fixed.h"
/* (calculators without a floating-point unit) raster_rows' plain case in integers: where s and t leave [0, 1) along a
* row is a straight line down the rows, stepped in 16.16, and the depth likewise; false when a place could pass 8192
* pixels (raster_rows then) */
static bool raster_rows_fx(int y0, int y1, float X0, float Y0, const PInv *pi, float z0, float zx, float zy,
uint16_t color) {
float dy = y0 + 0.5f - Y0, ks = -pi->dsdy * pi->isx, kt = -pi->dtdy * pi->itx, rows = (float)(y1 - y0);
if (fabsf(X0) > 8192 || fabsf(pi->isx) > 8192 || fabsf(pi->itx) > 8192 || fabsf(ks) * (fabsf(dy) + rows) > 8192 ||
fabsf(kt) * (fabsf(dy) + rows) > 8192)
return false;
int32_t as = (int32_t)fx_from_float(ks * dy, 16), dks = (int32_t)fx_from_float(ks, 16);
int32_t at = (int32_t)fx_from_float(kt * dy, 16), dkt = (int32_t)fx_from_float(kt, 16);
int32_t ws = (int32_t)fx_from_float(pi->isx, 16), wt = (int32_t)fx_from_float(pi->itx, 16);
int32_t xo = (int32_t)fx_from_float(X0 - 0.5f, 16);
/* the depth (raster_rows' z, before its 8 bits) at x = 0 of each row, and its steps, with 16 more bits */
float zbase = (z0 + ZOFF - zx * X0 - zy * Y0) * ZSCALE;
int32_t dz = (int32_t)(zx * ZSCALE * 256.0f);
int64_t zr = fx_from_float((zbase + (zx * 0.5f + zy * (y0 + 0.5f)) * ZSCALE) * 256.0f, 16);
int64_t dzx = fx_from_float(zx * ZSCALE * 256.0f, 16), dzy = fx_from_float(zy * ZSCALE * 256.0f, 16);
for (int y = y0; y < y1; y++, as += dks, at += dkt, zr += dzy) {
int32_t xl = as, xr = as + ws, a = at, b = at + wt;
if (xl > xr) xl = xr, xr = as;
if (a > b) a = b, b = at;
if (a > xl) xl = a;
if (b < xr) xr = b;
if (xl >= xr) continue;
int x0 = (xo + xl + 0xFFFF) >> 16, x1 = (xo + xr + 0xFFFF) >> 16;
if (x0 < clip_x0) x0 = clip_x0;
if (x1 > clip_x1) x1 = clip_x1;
if (x0 >= x1) continue;
int64_t zs = zr + dzx * x0;
int32_t z = zs < 0 ? 0 : (int32_t)(zs >> 16);
int row = (y - strip_y0) * SCREEN_W;
uint16_t *c = cbuf + row + x0, *ce = cbuf + row + x1;
uint16_t *zp = zbuf + row + x0;
int32_t zend = z + dz * (x1 - x0 - 1);
if (z >= 0 && zend >= 0 && z < (65535 << 8) && zend < (65535 << 8)) {
for (; c < ce; c++, zp++, z += dz) {
uint16_t zz = (uint16_t)(z >> 8);
if (zz <= *zp) {
*zp = zz;
*c = color;
}
}
} else {
for (; c < ce; c++, zp++, z += dz) {
int32_t zz = z >> 8;
if (zz < 0) zz = 0;
if (zz > 65535) zz = 65535;
if ((uint16_t)zz <= *zp) {
*zp = (uint16_t)zz;
*c = color;
}
}
}
}
return true;
}
#endif
/* Rasterise the rows y0 <= y < y1 (quad_rows) of the parallelogram with corner (X0, Y0) and a planar depth. */
static void raster(int y0, int y1, float X0, float Y0, const PInv *pi, float z0, float zx, float zy, uint16_t color) {
#if NP_SOFT_FLOAT
if (pi->isx != 0 && pi->itx != 0 && !fl_on && raster_rows_fx(y0, y1, X0, Y0, pi, z0, zx, zy, color)) return;
#endif
if (pi->isx != 0 && pi->itx != 0 && !fl_on) raster_rows(y0, y1, X0, Y0, pi, z0, zx, zy, color, true);
else raster_rows(y0, y1, X0, Y0, pi, z0, zx, zy, color, false);
}
/* --------------------------------------------------------- object drawing */
typedef struct {
float ox, oy, oz; /* screen x, y, depth of rest origin (0,0,0) */
float bx[3], by[3], bz[3]; /* screen delta per rest unit along x,y,z */
uint8_t vis; /* visible local face directions */
uint16_t col[34 * 6]; /* shaded colours cache: filled lazily */
uint8_t colok[34 * 6 / 8 + 1];
vec3 n[6];
float zx[6], zy[6];
float fa[6], fb[6], fc[6], fd[6], fia[6], fic[6]; /* per face: (s,t) per screen unit, for 1 voxel quads */
uint8_t ident; /* unrotated: shared colour cache */
float hx, hy; /* half the width and height of a cell on screen, plus a pixel */
} ObjXf;
static ObjXf xf;
static void setup_xf(const Obj *o) {
const Shape *s = o->shape;
vec3 ax[3] = {qrot(o->rot, v3(1, 0, 0)), qrot(o->rot, v3(0, 1, 0)), qrot(o->rot, v3(0, 0, 1))};
for (int k = 0; k < 3; k++) {
xf.bx[k] = vdot(ax[k], cam.right) * cam.scale;
xf.by[k] = -vdot(ax[k], cam.up) * cam.scale;
xf.bz[k] = vdot(ax[k], cam.fwd);
}
/* origin of rest space: world = pos + R*(rest - com) => rest 0 maps to pos - R*com */
vec3 w0 = vsub(o->pos, qrot(o->rot, s->origin));
vec3 d = vsub(w0, vadd(cam.focus, cam.shake));
xf.ox = cam.cx + vdot(d, cam.right) * cam.scale;
xf.oy = cam.cy - vdot(d, cam.up) * cam.scale;
xf.oz = vdot(d, cam.fwd);
xf.hx = 0.5f * (fabsf(xf.bx[0]) + fabsf(xf.bx[1]) + fabsf(xf.bx[2])) + 1;
xf.hy = 0.5f * (fabsf(xf.by[0]) + fabsf(xf.by[1]) + fabsf(xf.by[2])) + 1;
{
vec3 lo = vsub(s->bmin, s->origin), hi = vsub(s->bmax, s->origin);
vec3 m = v3(fmaxf(-lo.x, hi.x), fmaxf(-lo.y, hi.y), fmaxf(-lo.z, hi.z));
fl_on = o->pos.y * o->pos.y < vdot(m, m) || o->pos.y < 0;
vec3 f = vadd(cam.focus, cam.shake);
fl_x = cam.right.y / cam.scale;
fl_y = -cam.up.y / cam.scale;
fl_z = cam.fwd.y;
fl_k = f.y - fl_x * cam.cx - fl_y * cam.cy;
}
xf.vis = 0;
for (int f = 0; f < 6; f++) {
vec3 n = vscale(ax[f >> 1], (f & 1) ? -1.0f : 1.0f);
xf.n[f] = n;
float nf = vdot(n, cam.fwd);
if (nf < -1e-4f) {
int axis = f >> 1, ua = axis == 0 ? 1 : 0, va = axis == 2 ? 1 : 2;
float eux = xf.bx[ua] * 0.125f, euy = xf.by[ua] * 0.125f, evx = xf.bx[va] * 0.125f, evy = xf.by[va] * 0.125f;
float det = eux * evy - euy * evx;
if (fabsf(det) < 1e-6f) continue;
float id = 1.0f / det;
xf.fa[f] = evy * id;
xf.fb[f] = -evx * id;
xf.fc[f] = -euy * id;
xf.fd[f] = eux * id;
xf.fia[f] = fabsf(xf.fa[f]) > 1e-6f ? 1.0f / xf.fa[f] : 0;
xf.fic[f] = fabsf(xf.fc[f]) > 1e-6f ? 1.0f / xf.fc[f] : 0;
xf.vis |= 1 << f;
float nr = vdot(n, cam.right), nu = vdot(n, cam.up);
xf.zx[f] = -nr / (cam.scale * nf);
xf.zy[f] = nu / (cam.scale * nf);
}
}
xf.ident = fabsf(o->rot.x) + fabsf(o->rot.y) + fabsf(o->rot.z) < 1e-5f;
if (!xf.ident) memset(xf.colok, 0, sizeof xf.colok);
}
static uint16_t face_color(int pal, int f) {
int i = pal * 6 + f;
if (xf.ident) {
if (!(axis_ok[i >> 3] & (1 << (i & 7)))) {
int r, g, b;
shade_color(pal, xf.n[f], &r, &g, &b);
axis_col[i] = rgb565(r, g, b);
axis_ok[i >> 3] |= 1 << (i & 7);
}
return axis_col[i];
}
if (!(xf.colok[i >> 3] & (1 << (i & 7)))) {
int r, g, b;
shade_color(pal, xf.n[f], &r, &g, &b);
xf.col[i] = rgb565(r, g, b);
xf.colok[i >> 3] |= 1 << (i & 7);
}
return xf.col[i];
}
static const float inv_n[9] = {0, 1, 0.5f, 1.0f / 3, 0.25f, 0.2f, 1.0f / 6, 1.0f / 7, 0.125f};
static void draw_part(const Shape *s, int pi) {
uint32_t k = s->key[pi];
const Block *b = blocks[s->blk[pi]];
int cx = PK_X(k) * 8, cy = PK_Y(k) * 8, cz = PK_Z(k) * 8, comp = PK_C(k);
/* quick strip reject using the cell's centre and size on screen (rows first) */
float vx = (cx + 4) * 0.125f, vy = (cy + 4) * 0.125f, vz = (cz + 4) * 0.125f;
float sy = xf.oy + xf.by[0] * vx + xf.by[1] * vy + xf.by[2] * vz;
if (sy + xf.hy < strip_y0 || sy - xf.hy > strip_y1) return;
float sx = xf.ox + xf.bx[0] * vx + xf.bx[1] * vy + xf.bx[2] * vz;
if (sx + xf.hx < clip_x0 || sx - xf.hx > clip_x1) return;
uint8_t occ = s->occ ? s->occ[pi] : 0;
for (int f = 0; f < 6; f++) {
if (!(xf.vis & (1 << f)) || !b->nq[f]) continue;
const uint8_t *q = b->fq[f];
int axis = f >> 1, ua = axis == 0 ? 1 : 0, va = axis == 2 ? 1 : 2;
int pos = !(f & 1);
float euy = xf.by[ua] * 0.125f, evy = xf.by[va] * 0.125f;
int i = 0, n = b->nq[f];
/* a face against a full face of the same object: its outer layer is hidden. The quads come in layer
order (tools/model.py), so that layer is a run at the end (or the start) of the list. */
bool hidden = occ & (1 << f);
if (hidden && !pos)
while (i < n && (q[0] & 7) == 0) i++, q += 3;
for (; i < n; i++, q += 3) {
uint32_t w = q[0] | q[1] << 8 | (uint32_t)q[2] << 16;
int layer = w & 7, u = (w >> 3) & 7, v = (w >> 6) & 7, du = ((w >> 9) & 7) + 1, dv = ((w >> 12) & 7) + 1;
if (hidden && pos && layer == 7) break;
int col = (w >> 15) & 63, qc = (w >> 21) & 7;
if (qc != comp) continue;
float p[3];
p[axis] = (float)(layer + pos);
p[ua] = (float)u;
p[va] = (float)v;
/* the rows it covers first: most quads of a part on a strip's edge miss the strip */
float vx = (cx + p[0]) * 0.125f, vy = (cy + p[1]) * 0.125f, vz = (cz + p[2]) * 0.125f;
float Y = xf.oy + xf.by[0] * vx + xf.by[1] * vy + xf.by[2] * vz;
int y0, y1;
if (!quad_rows(Y, euy * du, evy * dv, &y0, &y1)) continue;
float X = xf.ox + xf.bx[0] * vx + xf.bx[1] * vy + xf.bx[2] * vz;
float Z = xf.oz + xf.bz[0] * vx + xf.bz[1] * vy + xf.bz[2] * vz;
PInv pv;
float iu = inv_n[du], iv = inv_n[dv];
pv.dsdx = xf.fa[f] * iu;
pv.dsdy = xf.fb[f] * iu;
pv.dtdx = xf.fc[f] * iv;
pv.dtdy = xf.fd[f] * iv;
pv.isx = xf.fia[f] * du;
pv.itx = xf.fic[f] * dv;
raster(y0, y1, X, Y, &pv, Z, xf.zx[f], xf.zy[f], face_color(col, f));
}
}
}
/* per frame cache of the strips each part may touch (one byte per part: first << 4 | last), kept in
* the free arena space which is untouched while rendering */
static uint8_t *pc_base;
static uint32_t pc_avail, pc_used;
static void draw_object(Obj *ob, RObj *o) {
setup_xf(ob);
const Shape *s = ob->shape;
if (o->pcache == 0xFFFF && pc_used + s->np <= pc_avail && pc_used + s->np < 0xFFFF) {
uint8_t *pc = pc_base + pc_used;
float r = xf.hy;
for (int i = 0; i < s->np; i++) {
uint32_t k = s->key[i];
float vy = PK_Y(k) + 0.5f, vx = PK_X(k) + 0.5f, vz = PK_Z(k) + 0.5f;
float sy = xf.oy + xf.by[0] * vx + xf.by[1] * vy + xf.by[2] * vz;
int a = (int)floorf((sy - r) * (1.0f / STRIP_H)), b = (int)floorf((sy + r) * (1.0f / STRIP_H));
if (b < 0 || a > SCREEN_H / STRIP_H - 1) {
pc[i] = 0xF0;
continue;
}
if (a < 0) a = 0;
if (b > 15) b = 15;
pc[i] = (uint8_t)(a << 4 | b);
}
o->pcache = (uint16_t)pc_used;
pc_used += s->np;
}
if (o->pcache != 0xFFFF) {
const uint8_t *pc = pc_base + o->pcache;
int st = strip_y0 / STRIP_H;
for (int i = 0; i < s->np; i++)
if (st >= (pc[i] >> 4) && st <= (pc[i] & 15)) draw_part(s, i);
} else {
for (int i = 0; i < s->np; i++) draw_part(s, i);
}
fl_on = false;
}
/* ------------------------------------------------------------------ frame */
static bool obj_screen_bounds(const Obj *o, int *y0, int *y1, int *x0, int *x1);
bool render_init_level(void) {
robj = arena_alloc(sizeof(RObj) * (obj_cap ? obj_cap : 1));
if (!robj) return false;
int r = palette_rgb[level.bg][0], g = palette_rgb[level.bg][1], b = palette_rgb[level.bg][2];
r = r + (255 - r) * 2 / 5;
g = g + (255 - g) * 2 / 5;
b = b + (255 - b) * 2 / 5;
/* the background of the levels built on Fancade's floor, as seen in the original */
static const uint8_t floor_bg[][4] = {
{2, 63, 63, 77}, {4, 132, 135, 153}, {5, 172, 175, 191}, {7, 89, 58, 73}, {8, 150, 87, 102}, {22, 18, 114, 76}};
for (unsigned i = 0; i < sizeof floor_bg / sizeof floor_bg[0]; i++)
if (floor_bg[i][0] == level.bg) r = floor_bg[i][1], g = floor_bg[i][2], b = floor_bg[i][3];
sky565 = rgb565(r, g, b);
return true;
}
static bool obj_screen_bounds(const Obj *o, int *y0, int *y1, int *x0, int *x1) {
const Shape *s = o->shape;
float mnx = 1e9f, mxx = -1e9f, mny = 1e9f, mxy = -1e9f;
for (int c = 0; c < 8; c++) {
vec3 pt = v3(c & 1 ? s->bmax.x : s->bmin.x, c & 2 ? s->bmax.y : s->bmin.y, c & 4 ? s->bmax.z : s->bmin.z);
vec3 w = obj_world(o, pt);
vec3 d = vsub(w, vadd(cam.focus, cam.shake));
float sx = cam.cx + vdot(d, cam.right) * cam.scale;
float sy = cam.cy - vdot(d, cam.up) * cam.scale;
if (sx < mnx) mnx = sx;
if (sx > mxx) mxx = sx;
if (sy < mny) mny = sy;
if (sy > mxy) mxy = sy;
}
*x0 = (int)mnx - 1;
*x1 = (int)mxx + 1;
*y0 = (int)mny - 1;
*y1 = (int)mxy + 1;
return !(mxx < 0 || mnx > SCREEN_W || mxy < 0 || mny > SCREEN_H);
}
/* ------------------------------------------------------------------ shadows */
/* Moving objects (and the props following them, like the tyres) cast Fancade style shadows on the
* ground below: the box faces lit by the sun are projected along the light onto the plane found by a
* raycast, and ground pixels at that depth are darkened to their ambient only colour. The faces are
* projected strip by strip, for the casters whose shadow reaches the strip: none is ever left out (they
* used to be kept in a list of at most 512 for the frame, and the faces past it were dropped, so shadows
* came and went). */
#define MAX_CASTERS 32
#define SHADOW_TOL 40 /* depth units */
static struct {
int16_t obj, floor;
int16_t y0, y1; /* the screen rows its shadow can reach */
float ground;
} casters[MAX_CASTERS];
static int ncasters;
static uint8_t smask[SCREEN_W * STRIP_H / 8];
static float sh_zx, sh_zy; /* screen depth gradient of a horizontal plane */
static bool sh_any;
/* the screen rows the shadow of o on the plane y = g can reach: its bounds' corners projected along d */
static void shadow_rows(const Obj *o, float g, vec3 d, int16_t *y0, int16_t *y1) {
const Shape *s = o->shape;
float mn = 1e9f, mx = -1e9f;
for (int c = 0; c < 8; c++) {
vec3 pt = v3(c & 1 ? s->bmax.x : s->bmin.x, c & 2 ? s->bmax.y : s->bmin.y, c & 4 ? s->bmax.z : s->bmin.z);
vec3 w = obj_world(o, pt);
vec3 q = vsub(vadd(w, vscale(d, (g - w.y) / d.y)), vadd(cam.focus, cam.shake));
float sy = cam.cy - vdot(q, cam.up) * cam.scale;
if (sy < mn) mn = sy;
if (sy > mx) mx = sy;
}
*y0 = (int16_t)(mn < -1000 ? -1000 : mn > 1000 ? 1000 : mn - 2);
*y1 = (int16_t)(mx < -1000 ? -1000 : mx > 1000 ? 1000 : mx + 2);
}
static void find_casters(void) {
ncasters = 0;
vec3 d = vscale(light_to, -1);
if (d.y > -0.05f) return;
vec3 n = v3(0, 1, 0);
float nf = vdot(n, cam.fwd);
if (fabsf(nf) < 1e-4f) return;
sh_zx = -vdot(n, cam.right) / (cam.scale * nf);
sh_zy = vdot(n, cam.up) / (cam.scale * nf);
/* dynamic objects first, then small moved props close to them */
int ndyn = 0;
for (int pass = 0; pass < 2; pass++, ndyn = ncasters)
for (int i = 0; i < nobj && ncasters < MAX_CASTERS; i++) {
const Obj *o = &objs[i];
if (!(o->flags & OF_VISIBLE) || (o->flags & (OF_DEAD | OF_TEMPLATE)) || robj[i].ymin > robj[i].ymax) continue;
if (pass == 0 && !(o->flags & OF_DYNAMIC)) continue;
if (pass == 1) {
if ((o->flags & OF_DYNAMIC) || !(o->flags & OF_MOVED) || o->shape->np > 48) continue;
bool near = false;
for (int c = 0; c < ndyn && !near; c++) {
const Obj *q = &objs[casters[c].obj];
float dx = q->pos.x - o->pos.x, dy = q->pos.y - o->pos.y;
near = dx * dx + dy * dy < 9;
}
if (!near) continue;
}
const Shape *s = o->shape;
vec3 from = obj_world(o, vscale(vadd(s->bmin, s->bmax), 0.5f)), hit;
int ho;
bool fl = false;
if (!phys_raycast_ex(from, v3(from.x, from.y - 12, from.z), &hit, &ho, i)) {
if (from.y > 12 || from.y < 0) continue;
hit.y = 0; /* Fancade's floor */
fl = true;
}
casters[ncasters].obj = (int16_t)i;
casters[ncasters].floor = fl;
casters[ncasters].ground = hit.y;
shadow_rows(o, hit.y, d, &casters[ncasters].y0, &casters[ncasters].y1);
ncasters++;
}
}
/* mark pixels of the parallelogram whose stored depth matches the plane */
static void raster_mark(float X0, float Y0, float ux, float uy, float vx, float vy, float z0, bool floor) {
float det = ux * vy - uy * vx;
if (fabsf(det) < 1e-3f) return;
float id = 1.0f / det;
PInv pv;
pv.dsdx = vy * id;
pv.dsdy = -vx * id;
pv.dtdx = -uy * id;
pv.dtdy = ux * id;
pv.isx = fabsf(pv.dsdx) > 1e-6f ? 1.0f / pv.dsdx : 0;
pv.itx = fabsf(pv.dtdx) > 1e-6f ? 1.0f / pv.dtdx : 0;
const PInv *pi = &pv;
float ymin = Y0, ymax = Y0;
float ya = Y0 + uy, yb = Y0 + vy, yc2 = Y0 + uy + vy;
if (ya < ymin) ymin = ya;
if (ya > ymax) ymax = ya;
if (yb < ymin) ymin = yb;
if (yb > ymax) ymax = yb;
if (yc2 < ymin) ymin = yc2;
if (yc2 > ymax) ymax = yc2;
int y0 = iceil(ymin - 0.5f), y1 = iceil(ymax - 0.5f);
if (y0 < strip_y0) y0 = strip_y0;
if (y1 > strip_y1) y1 = strip_y1;
if (y0 >= y1) return;
float zbase = (z0 + ZOFF - sh_zx * X0 - sh_zy * Y0) * ZSCALE;
float dy = y0 + 0.5f - Y0;
float sr = pi->dsdy * dy, tr = pi->dtdy * dy;
for (int y = y0; y < y1; y++, sr += pi->dsdy, tr += pi->dtdy) {
float xl, xr;
if (pi->isx != 0) {
float a = -sr * pi->isx, b = (1 - sr) * pi->isx;
if (a < b) xl = a, xr = b;
else xl = b, xr = a;
} else {
if (sr < 0 || sr >= 1) continue;
xl = -1e9f, xr = 1e9f;
}
if (pi->itx != 0) {
float a = -tr * pi->itx, b = (1 - tr) * pi->itx;
if (a > b) {
float t = a;
a = b;
b = t;
}
if (a > xl) xl = a;
if (b < xr) xr = b;
} else if (tr < 0 || tr >= 1) {
continue;
}
if (xl >= xr) continue;
int x0 = iceil(X0 + xl - 0.5f), x1 = iceil(X0 + xr - 0.5f);
if (x0 < clip_x0) x0 = clip_x0;
if (x1 > clip_x1) x1 = clip_x1;
if (x0 >= x1) continue;
float zs = zbase + (sh_zx * (x0 + 0.5f) + sh_zy * (y + 0.5f)) * ZSCALE;
float dz = sh_zx * ZSCALE;
int row = (y - strip_y0) * SCREEN_W;
const uint16_t *zp = zbuf + row;
for (int x = x0; x < x1; x++, zs += dz) {
int d = (int)zs - zp[x];
if ((d <= SHADOW_TOL && d >= -SHADOW_TOL) || (floor && zp[x] == 0xFFFF)) smask[(row + x) >> 3] |= (uint8_t)(1 << ((row + x) & 7));
}
sh_any = true;
}
}
/* project a lit face (corner p, edges u, v in world space) onto the plane y = g, and mark it in the strip */
static void shadow_face(vec3 p, vec3 u, vec3 v, float g, vec3 d, bool floor) {
float k = (g - p.y) / d.y;
if (k < 0) return; /* face below the ground plane */
vec3 p0 = vadd(p, vscale(d, k));
vec3 u0 = vsub(u, vscale(d, u.y / d.y)), v0 = vsub(v, vscale(d, v.y / d.y));
vec3 q = vsub(p0, vadd(cam.focus, cam.shake));
float X = cam.cx + vdot(q, cam.right) * cam.scale;
float Y = cam.cy - vdot(q, cam.up) * cam.scale;
float uy = -vdot(u0, cam.up) * cam.scale, vy = -vdot(v0, cam.up) * cam.scale;
float ymin = Y + fminf(0, uy) + fminf(0, vy), ymax = Y + fmaxf(0, uy) + fmaxf(0, vy);
if (ymax + 1 < strip_y0 || ymin - 1 >= strip_y1) return;
float z = vdot(q, cam.fwd) - 0.01f;
float ux = vdot(u0, cam.right) * cam.scale, vx = vdot(v0, cam.right) * cam.scale;
raster_mark(X, Y, ux, uy, vx, vy, z, floor);
}
/* the shadow of caster c in this strip */
static void shadow_caster(int c) {
vec3 d = vscale(light_to, -1);
const Obj *o = &objs[casters[c].obj];
const Shape *s = o->shape;
float g = casters[c].ground;
vec3 ax[3] = {qrot(o->rot, v3(1, 0, 0)), qrot(o->rot, v3(0, 1, 0)), qrot(o->rot, v3(0, 0, 1))};
bool lit[6];
for (int f = 0; f < 6; f++) lit[f] = vdot(ax[f >> 1], light_to) * ((f & 1) ? -1.0f : 1.0f) > 1e-3f;
for (int i = 0; i < s->np; i++) {
uint32_t k = s->key[i];
const Block *b = blocks[s->blk[i]];
int comp = PK_C(k);
uint8_t occ = s->occ ? s->occ[i] : 0;
/* use the collision boxes, or the component bounds when the block has none */
int nb = b->nbox;
for (int j = 0; j < (nb ? nb : 1); j++) {
float lo[3], hi[3];
if (nb) {
const uint8_t *bx = b->boxes + 3 * j;
uint32_t w = bx[0] | bx[1] << 8 | (uint32_t)bx[2] << 16;
if ((int)(w & 7) != comp) continue;
lo[0] = ((w >> 3) & 7), lo[1] = ((w >> 6) & 7), lo[2] = ((w >> 9) & 7);
hi[0] = ((w >> 12) & 7) + 1, hi[1] = ((w >> 15) & 7) + 1, hi[2] = ((w >> 18) & 7) + 1;
} else {
const uint8_t *bb = b->bb + comp * 6;
if (bb[0] > bb[3]) continue;
lo[0] = bb[0], lo[1] = bb[1], lo[2] = bb[2];
hi[0] = bb[3] + 1, hi[1] = bb[4] + 1, hi[2] = bb[5] + 1;
}
vec3 rest = v3(PK_X(k) + lo[0] / 8, PK_Y(k) + lo[1] / 8, PK_Z(k) + lo[2] / 8);
vec3 p0 = obj_world(o, rest);
vec3 e[3] = {vscale(ax[0], (hi[0] - lo[0]) / 8), vscale(ax[1], (hi[1] - lo[1]) / 8),
vscale(ax[2], (hi[2] - lo[2]) / 8)};
for (int f = 0; f < 6; f++) {
if (!lit[f]) continue;
int a = f >> 1, ua = a == 0 ? 1 : 0, va = a == 2 ? 1 : 2;
/* a face against a full face of the same object adds nothing to its shadow */
if ((occ >> f & 1) && ((f & 1) ? lo[a] == 0 : hi[a] == 8)) continue;
vec3 p = (f & 1) ? p0 : vadd(p0, e[a]);
shadow_face(p, e[ua], e[va], g, d, casters[c].floor);
}
}
}
}
static void draw_shadows(void) {
bool any = false;
for (int c = 0; c < ncasters && !any; c++) any = casters[c].y1 >= strip_y0 && casters[c].y0 < strip_y1;
if (!any) return;
memset(smask, 0, sizeof smask);
sh_any = false;
for (int c = 0; c < ncasters; c++)
if (casters[c].y1 >= strip_y0 && casters[c].y0 < strip_y1) shadow_caster(c);
if (!sh_any) return;
int n = (strip_y1 - strip_y0) * SCREEN_W;
for (int i = 0; i < n; i += 8) {
uint8_t m = smask[i >> 3];
if (!m) continue;
for (int k = 0; k < 8; k++)
if (m & (1 << k)) {
uint16_t c = cbuf[i + k];
int r = (c >> 11) * 23 >> 5, gg = ((c >> 5) & 63) * 23 >> 5, bl = (c & 31) * 26 >> 5;
cbuf[i + k] = (uint16_t)(r << 11 | gg << 5 | bl);
}
}
}
void render_prepare(int rx0, int rx1) {
pc_base = arena_top(&pc_avail);
pc_used = 0;
for (int i = 0; i < nobj; i++) {
Obj *o = &objs[i];
RObj *r = &robj[i];
r->pcache = 0xFFFF;
r->ymin = 1;
r->ymax = 0;
if (!(o->flags & OF_VISIBLE) || (o->flags & OF_DEAD) || !o->shape->np) continue;
int y0, y1, x0, x1;
if (!obj_screen_bounds(o, &y0, &y1, &x0, &x1)) continue;
if (x1 < rx0 || x0 > rx1) continue;
r->ymin = (int16_t)(y0 < -32000 ? -32000 : y0);
r->ymax = (int16_t)(y1 > 32000 ? 32000 : y1);
}
find_casters();
}
uint16_t *render_buffer(void) { return cbuf; }
uint16_t *render_strip(int sy, int n, int x0, int x1) {
uint16_t depth[SCREEN_W * STRIP_H] __attribute__((aligned(4)));
zbuf = depth;
strip_y0 = sy;
strip_y1 = sy + n;
clip_x0 = x0;
clip_x1 = x1;
if (x0 == 0 && x1 == SCREEN_W) {
/* whole rows: fill two pixels per word */
uint32_t sky2 = sky565 | (uint32_t)sky565 << 16;
u32a *c = (u32a *)cbuf, *z = (u32a *)zbuf;
for (int i = 0; i < n * SCREEN_W / 2; i++) c[i] = sky2, z[i] = 0xFFFFFFFFu;
} else {
for (int r = 0; r < n; r++) {
uint16_t *c = cbuf + r * SCREEN_W, *z = zbuf + r * SCREEN_W;
for (int x = x0; x < x1; x++) {
c[x] = sky565;
z[x] = 0xFFFF;
}
}
}
for (int i = 0; i < nobj; i++) {
RObj *r = &robj[i];
if (r->ymin > r->ymax || r->ymax < strip_y0 || r->ymin >= strip_y1) continue;
draw_object(&objs[i], r);
}
draw_shadows();
zbuf = NULL;
return cbuf;
}
void render_frame(void (*post)(uint16_t *px, int y, int n)) {
render_prepare(0, SCREEN_W);
for (int sy = 0; sy < SCREEN_H; sy += STRIP_H) {
int n = SCREEN_H - sy < STRIP_H ? SCREEN_H - sy : STRIP_H;
render_strip(sy, n, 0, SCREEN_W);
if (post) post(cbuf, sy, n);
plat_push(0, sy, SCREEN_W, n, cbuf);
}
}