path: root/src/render.zig

// This file is part of ZiRC
//
// Copyright (C) 2021, tslil clingman
//
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program. If not, see <https://www.gnu.org/licenses/>.

const std = @import("std");

const RenderWindow = @import("sfml").graphics.RenderWindow;
const Sprite = @import("sfml").graphics.Sprite;
const Texture = @import("sfml").graphics.Texture;
const Image = @import("sfml").graphics.Image;
const Colour = @import("sfml").graphics.Color;

const level = @import("level.zig");
const constants = @import("constants.zig");
const player = @import("player.zig");

fn playerDistComp(pos: [2]f32, lhs: level.Object, rhs: level.Object) bool {
    const lx = lhs.pos_x - pos[0];
    const ly = lhs.pos_y - pos[1];
    const rx = rhs.pos_x - pos[0];
    const ry = rhs.pos_y - pos[1];

    return (lx * lx + ly * ly > rx * rx + ry * ry);
}

fn fasterColourBlend(onto: Colour, from: Colour) Colour {
    const af: u16 = from.a;
    const of: u16 = onto.a;

    const ablend: u16 = @divTrunc(of * (255 - af), 255);
    const na: u16 = af + ablend;
    if (na == 0) return Colour.Black;

    const rf: u16 = from.r;
    const ro: u16 = onto.r;
    const gf: u16 = from.g;
    const go: u16 = onto.g;
    const bf: u16 = from.b;
    const bo: u16 = onto.b;

    // The most accurate i've found is
    const nr = @divTrunc(ro * ablend + rf * af, na);
    const ng = @divTrunc(go * ablend + gf * af, na);
    const nb = @divTrunc(bo * ablend + bf * af, na);

    // These computations are incorrect, but faster
    // const nr = (af * rf + (255 - af) * ro) / 255;
    // const ng = (af * gf + (255 - af) * go) / 255;
    // const nb = (af * bf + (255 - af) * bo) / 255;

    return Colour{
        .a = @intCast(u8, na),
        .r = @intCast(u8, nr),
        .g = @intCast(u8, ng),
        .b = @intCast(u8, nb),
    };
}

// The primary observation is: if a line segment AB disconnects the unit square,
// then it intersects another line segment CD in that square precisely when the
// C and D are on opposite sides of AB---cross product! We can calculate the
// intersection point using the usual matrix inversion/determinant story.
fn hitDistLocalCoords(
    ray0: [2]f32,
    ray1: [2]f32,
    vertices: []const [2]f32,
) ?f32 {
    const rdy = ray1[1] - ray0[1];
    const rdx = ray1[0] - ray0[0];
    const rdist = std.math.sqrt(rdx * rdx + rdy * rdy);

    var vp = vertices[0];
    var crossp: f32 = rdy * (vp[0] - ray0[0]) - rdx * (vp[1] - ray0[1]);

    if (crossp == 0) {
        // hit a vertex exactly
        const dx = vp[0] - ray0[0];
        const dy = vp[1] - ray0[1];
        return std.math.sqrt(dx * dx + dy * dy);
    }

    var return_val: ?f32 = null;
    var v : [2]f32 = undefined;
    var cross: f32 = 0;
    var i: usize = 1;
    while (i < vertices.len) : ({
        vp = v;
        crossp = cross;
        i += 1;
    }) {
        v = vertices[i];
        cross = rdy * (v[0] - ray0[0]) - rdx * (v[1] - ray0[1]);
        // if (cross == 0) {
        //     const dx = v[0] - ray0[0];
        //     const dy = v[1] - ray0[1];
        //     const new_distance = std.math.sqrt(dx * dx + dy * dy);
        //     if (return_val) |local_distance| {
        //         if (new_distance < local_distance) return_val = new_distance;
        //     } else {
        //         return_val = new_distance;
        //     }
        // } else
            {
            if (crossp * cross < 0) {
                // If the segment from ray0->ray1 has vp and v on opposite sides
                // of it then it intersects the line segment vp->v. This is not
                // true in general, but all coordinates are constrained to be in
                // the unit square so it is true here. With that we compute the
                // distance to the intersection from ray0
                const vdx = v[0] - vp[0];
                const vdy = v[1] - vp[1];

                const t = (vdx * (ray0[1] - vp[1]) - vdy * (ray0[0] - vp[0])) / (rdx * vdy - vdx * rdy);
                const new_distance = rdist * t;

                // const s = cross / (rdx * vdy - vdx * rdy);
                // const dx = v[0] + vdx * s - ray0[0];
                // const dy = v[1] + vdy * s - ray0[1];
                // const new_distance = std.math.sqrt(dx * dx + dy * dy);
                if (return_val) |local_distance| {
                    if (new_distance < local_distance) return_val = new_distance;
                } else {
                    return_val = new_distance;
                }
            }
        }
    }
    return return_val;
}

pub fn Renderer(PlaneWidth: f32, PlaneHeight: f32) type {
    const FOV: f32 = std.math.pi / 3.0;
    const PlanePixels = PlaneWidth * PlaneHeight;
    // given the desired width of the image, how far away must
    // the projection plane be from the camera?
    const FOV_SCALE = 2 * std.math.tan(FOV / 2);
    const PlaneDist = PlaneWidth / FOV_SCALE;

    return struct {
        z_buffer: [PlanePixels]f32,

        pub fn new() @This() {
            return Renderer(PlaneWidth, PlaneHeight){
                .z_buffer = [_]f32{std.math.inf(f32)} ** PlanePixels,
            };
        }

        pub fn renderWorld(
            self: *@This(),
            plyr: player.Player,
            window: RenderWindow,
            objects_image: Image,
            walls_image: Image,
            surfaces_image: Image,
            rendered_surfaces_texture: Texture,
            rendered_surfaces_sprite: Sprite,
            map: level.Map,
        ) !void {
            // Fist reset the z_buffer
            var i: usize = 0;
            while (i < self.z_buffer.len) : (i += 1) {
                self.z_buffer[i] = std.math.inf(f32);
            }

            var pixels = [_]Colour{Colour.Transparent} ** (PlaneWidth * PlaneHeight);

            // Draw all vertical and horizontal surfaces, and populate the z-buffer
            self.renderCells(plyr, walls_image, surfaces_image, map, &pixels);

            // use the z_buffer to render sprites
            self.renderObjects(plyr, objects_image, map, &pixels);

            try rendered_surfaces_texture.updateFromPixels(&pixels, null);
            window.draw(rendered_surfaces_sprite, null);
        }

        fn renderObjects(
            self: @This(),
            plyr: player.Player,
            objects_image: Image,
            map: level.Map,
            pixels: []Colour,
        ) void {
            const ppos_x = plyr.pos_x;
            const ppos_y = plyr.pos_y;
            const pheight = plyr.height;
            const pcos = std.math.cos(plyr.ang);
            const psin = std.math.sin(plyr.ang);

            std.sort.sort(level.Object, map.objects.items,
            // Wow, context with an arbitrary type! No macros, just
            // Zig all the way down!
            [2]f32{ ppos_x, ppos_y }, playerDistComp);

            for (map.objects.items) |obj| {
                const ox = obj.pos_x - ppos_x;
                const oy = obj.pos_y - ppos_y;

                // We compute the two coordinates of rotating by -self.ang, the
                // first of which gives the perpendicular distance to the plane
                // of projection, and the second of which gives the
                // (unprojected) centre of the object.
                const perp_distance = pcos * ox + psin * oy;
                const centre = psin * ox - pcos * oy;

                // NOTE: in the below we have applied the magic scaling factor
                // of FOV_SCALE. I don't understand how this compensates for the
                // linear interpolation incorrectness we do elsewhere, but
                // somehow it scales the *correct* values we compute above into
                // whatever agrees with the wall and floor rendering voodoo.

                // This quantity is independent of FOV_SCALE because it enters
                // both via centre and perp_distance
                const proj_centre = PlaneWidth / 2 + PlaneDist * centre / perp_distance;

                // Here's the magic adjustment
                const scaled_perp_distance = FOV_SCALE * perp_distance;
                const width = PlaneDist * obj.width / scaled_perp_distance;
                const left = proj_centre - width / 2;

                // TODO: prune before this?
                if (left + width < 0 or left >= PlaneWidth) continue;

                const height = PlaneDist * obj.height / scaled_perp_distance;
                const top = PlaneHeight / 2 + PlaneDist * (obj.height - pheight + obj.pos_z) / scaled_perp_distance;

                // TODO: likewise?
                if (top < 0 or top - height >= PlaneHeight) continue;

                // Something is on the screen, let's draw it!
                const start = std.math.max(0, left);
                const end = @floatToInt(usize, std.math.min(left + width, PlaneWidth - 1));

                const tex_y_step = constants.TextureDim / height;
                const tex_x_step = constants.TextureDim / width;
                const toff = obj.texture * @floatToInt(c_uint, constants.TextureDim);

                const thresh = top - height;
                const constrained_bottom = std.math.min(top, PlaneHeight);
                const pix_y = @floatToInt(usize, std.math.ceil(std.math.max(PlaneHeight - constrained_bottom - 1, 0)));
                var tex_x: f32 = std.math.clamp((start - left) / width, 0, 1) * constants.TextureDim;
                var col: usize = @floatToInt(usize, start);
                var bottom: f32 = 0;
                while (col < end) : ({
                    col += 1;
                    tex_x += tex_x_step;
                    bottom = constrained_bottom;
                }) {
                    const tx = @floatToInt(c_uint, tex_x);
                    var pix_index = @floatToInt(usize, PlaneWidth) * pix_y + col;
                    var texel_y = constants.TextureDim * (top - bottom) / height;
                    while (pix_index < PlanePixels and bottom > thresh) : ({
                        bottom -= 1;
                        texel_y += tex_y_step;
                        pix_index += @floatToInt(usize, PlaneWidth);
                    }) {
                        if (self.z_buffer[pix_index] > scaled_perp_distance) {
                            const ty = @floatToInt(c_uint, texel_y);
                            // TODO: There's an out of bounds in the pixel access here ...
                            const texel = objects_image.getPixel(.{ .x = toff + tx, .y = ty });
                            // TODO: Decide whether being accurate is as important as being fast
                            pixels[pix_index] = fasterColourBlend(pixels[pix_index], texel);
                        }
                    }
                }
            }
        }

        fn renderCells(
            self: *@This(),
            plyr: player.Player,
            walls_image: Image,
            surfaces_image: Image,
            map: level.Map,
            pixels: []Colour,
        ) void {
            // This is a TERRIBLE hack: for whatever reason *linearly*
            // interpolating on the direction vectors gives
            // perspective-correct-seeming walls!
            const cos_first = std.math.cos(plyr.ang + 0.5 * FOV);
            const cos_last = std.math.cos(plyr.ang - 0.5 * FOV);
            const sin_first = std.math.sin(plyr.ang + 0.5 * FOV);
            const sin_last = std.math.sin(plyr.ang - 0.5 * FOV);

            const cos_step = (cos_last - cos_first) / PlaneWidth;
            const sin_step = (sin_last - sin_first) / PlaneWidth;

            const ppos_x = plyr.pos_x;
            const ppos_y = plyr.pos_y;
            const pheight = plyr.height;

            var col: u16 = 0;
            var cosra = cos_first;
            var sinra = sin_first;
            while (col < PlaneWidth) : ({
                col += 1;
                cosra += cos_step;
                sinra += sin_step;
            }) {
                // Observe that sqrt(1+tan^2) = abs(1/cos) sqrt(cos^2+sin^2) =
                // abs(1/cos). Similarly so for cot, hence we obtain the
                // following lengths for the hypotenuses assuming that x
                // (respectively y) are unit length and the angle is ra. This
                // for whatever reasons still works when we linearly interpolate
                // on cos and sin!
                const dy_for_x_step = std.math.fabs(1 / cosra);
                const dx_for_y_step = std.math.fabs(1 / sinra);

                var step_x: i32 = -1;
                var step_y: i32 = -1;

                var dist_x: f32 = undefined;
                var dist_y: f32 = undefined;

                var ipos_x: i32 = @floatToInt(i32, std.math.floor(ppos_x));
                var ipos_y: i32 = @floatToInt(i32, std.math.floor(ppos_y));

                // looking right
                if (cosra >= 0) {
                    step_x = 1;
                    // assuming unit size grid cells
                    dist_y = (@intToFloat(f32, ipos_x) + 1 - ppos_x) * dy_for_x_step;
                } else {
                    dist_y = (ppos_x - @intToFloat(f32, ipos_x)) * dy_for_x_step;
                }

                if (sinra >= 0) {
                    step_y = 1;
                    dist_x = (@intToFloat(f32, ipos_y) + 1 - ppos_y) * dx_for_y_step;
                } else {
                    dist_x = (ppos_y - @intToFloat(f32, ipos_y)) * dx_for_y_step;
                }

                var top_of_floor: f32 = undefined;
                var bottom_of_ceiling: f32 = undefined;

                var distance: f32 = 0;
                var next_distance: f32 = 0;
                var hit_horizontal: bool = undefined;
                var next_hit_horizontal: bool = undefined;

                if (dist_y < dist_x) {
                    hit_horizontal = false;
                    distance = dist_y;
                    dist_y += dy_for_x_step;
                    ipos_x += step_x;
                } else {
                    hit_horizontal = true;
                    distance = dist_x;
                    dist_x += dx_for_y_step;
                    ipos_y += step_y;
                }

                if (dist_y < dist_x) {
                    next_hit_horizontal = false;
                    next_distance = dist_y;
                } else {
                    next_hit_horizontal = true;
                    next_distance = dist_x;
                }

                var highest_drawn: f32 = 0;
                var lowest_drawn: f32 = PlaneHeight - 1;
                var still_drawing = true;

                while (still_drawing and map.inBounds(ipos_x, ipos_y)) : ({
                    // Find the next cell on our path
                    if (dist_y < dist_x) {
                        hit_horizontal = false;
                        distance = dist_y;
                        dist_y += dy_for_x_step;
                        ipos_x += step_x;
                    } else {
                        hit_horizontal = true;
                        distance = dist_x;
                        dist_x += dx_for_y_step;
                        ipos_y += step_y;
                    }

                    if (dist_y < dist_x) {
                        next_distance = dist_y;
                        next_hit_horizontal = false;
                    } else {
                        next_distance = dist_x;
                        next_hit_horizontal = true;
                    }
                }) {
                    const cell = map.lookup(ipos_x, ipos_y);

                    // Are we drawing vertical surfaces?
                    if (cell.floor_height > 0 or cell.draw_down) {
                        const ray0: [2]f32 = if (hit_horizontal)
                            [2]f32{
                                std.math.modf(distance * cosra + ppos_x).fpart,
                                (if (step_y > 0) 0 else 1),
                            }
                        else
                            [2]f32{
                                (if (step_x > 0) 0 else 1),
                                std.math.modf(distance * sinra + ppos_y).fpart,
                            };

                        const ray1: [2]f32 = if (next_hit_horizontal)
                            [2]f32{
                                std.math.modf(next_distance * cosra + ppos_x).fpart,
                                (if (step_y > 0) 1 else 0),
                            }
                        else
                            [2]f32{
                                (if (step_x > 0) 1 else 0),
                                std.math.modf(next_distance * sinra + ppos_y).fpart,
                            };

                        if (hitDistLocalCoords(ray0, ray1, cell.vertices)) |local_dist| {
                            // TODO: Correct for fisheye?
                            const adj_distance = distance + local_dist;

                            // project the top of the bottom and the bottom of the top
                            top_of_floor = PlaneHeight / 2 + PlaneDist * (cell.floor_height - pheight) / adj_distance;
                            bottom_of_ceiling = PlaneHeight / 2 + PlaneDist * (cell.ceiling_height - pheight) / adj_distance;

                            const draw_lower = cell.floor_height > 0 and top_of_floor > highest_drawn;
                            const draw_upper = cell.draw_down and bottom_of_ceiling < lowest_drawn;

                            // Are we able to see any vertical faces?
                            if (draw_upper or draw_lower) {
                                // we need the distance to calculate the
                                // fractional part of the relevant coordinate
                                // for texture mapping of the walls

                                // TODO: Now that walls are polygonal, what
                                // should texture mapping mean?
                                var texfrac : f32 = 0.5;
                                // if (hit_horizontal) {
                                //     texfrac = adj_distance * cosra + ppos_x;
                                // } else {
                                //     texfrac = adj_distance * sinra + ppos_y;
                                // }
                                // texfrac = std.math.modf(texfrac).fpart;

                                // we also want to be sure that we're consistently
                                // orienting textures, in this case clockwise
                                // if ((hit_horizontal and sinra < 0) or (!hit_horizontal and cosra > 0)) texfrac = 1 - texfrac;

                                const texstrip = @floatToInt(c_uint, constants.TextureDim * texfrac);

                                // height of a unit-height wall at this distance
                                const nominal_length = PlaneDist / adj_distance;
                                // used for texel indexing
                                const inv_nom_len = adj_distance / PlaneDist;

                                const td = @floatToInt(c_uint, constants.TextureDim);
                                if (draw_lower) {
                                    // which texture index?
                                    const t_lower_off = cell.lower_texture * td;
                                    // Note the bizarre rounding we have to do to avoid artifacts
                                    const constrained_top = std.math.floor(std.math.min(top_of_floor, lowest_drawn));
                                    const proj_height = cell.floor_height * nominal_length;
                                    const constrained_bottom = std.math.max(highest_drawn, top_of_floor - proj_height);
                                    const stop = @floatToInt(usize, PlaneWidth * (PlaneHeight - constrained_bottom)) + col;
                                    const pix_y = @floatToInt(usize, std.math.ceil(std.math.max(PlaneHeight - constrained_top - 1, 0)));
                                    var pix_index = pix_y * @floatToInt(usize, PlaneWidth) + col;
                                    var texel_y: f32 = std.math.max((top_of_floor - constrained_top) / nominal_length, 0);

                                    // now we have what we need to draw the face,
                                    // and update the z-buffer.
                                    while (pix_index < stop) : ({
                                        pix_index += @floatToInt(usize, PlaneWidth);
                                        texel_y += inv_nom_len;
                                    }) {
                                        const ty = @floatToInt(c_uint, std.math.modf(texel_y).fpart * constants.TextureDim);
                                        const texel = walls_image.getPixel(.{ .x = t_lower_off + texstrip, .y = ty });

                                        pixels[pix_index] = texel;
                                        self.z_buffer[pix_index] = adj_distance;
                                    }
                                    highest_drawn = constrained_top;
                                }

                                if (draw_upper) {
                                    const proj_default_end = PlaneHeight / 2 + PlaneDist * (level.Cell.DEFAULT_HEIGHT - pheight) / adj_distance;
                                    const constrained_top = std.math.min(lowest_drawn, proj_default_end);
                                    const constrained_bottom = std.math.ceil(std.math.max(bottom_of_ceiling, highest_drawn));
                                    const stop = @floatToInt(usize, PlaneWidth * (PlaneHeight - constrained_bottom)) + col;
                                    const t_upper_off = cell.upper_texture * td;
                                    const pix_y = @floatToInt(usize, std.math.ceil(std.math.max(PlaneHeight - constrained_top - 1, 0)));
                                    var pix_index = pix_y * @floatToInt(usize, PlaneWidth) + col;
                                    var texel_y: f32 = constants.TextureDim - (constrained_top - constrained_bottom) / nominal_length;
                                    while (pix_index < stop) : ({
                                        pix_index += @floatToInt(usize, PlaneWidth);
                                        texel_y += inv_nom_len;
                                    }) {
                                        const ty = @floatToInt(c_uint, std.math.modf(texel_y).fpart * constants.TextureDim);
                                        const texel = walls_image.getPixel(.{ .x = t_upper_off + texstrip, .y = ty });

                                        pixels[pix_index] = texel;
                                        self.z_buffer[pix_index] = adj_distance;
                                    }
                                    lowest_drawn = constrained_bottom;
                                }
                            }
                        }
                    }

                    // do we potentially draw floor and or ceiling for this cell?
                    if (highest_drawn < PlaneHeight / 2 or (cell.draw_down and lowest_drawn > PlaneHeight / 2)) {
                        // Note: next_top can never exceed PlaneHeight / 2 in
                        // the body of the next block. If the wall is taller
                        // than us the back edge is lower than the front one so
                        // this check will fail as we just drew it (or higher
                        // than it). If the wall is shorter then the back edge
                        // is at most the horizon. Similarly so for next_bottom
                        const next_top = PlaneHeight / 2 + PlaneDist * (cell.floor_height - pheight) / next_distance;
                        const next_bottom = PlaneHeight / 2 + PlaneDist * (cell.ceiling_height - pheight) / next_distance;

                        // draw floor?
                        if (false and next_top > highest_drawn) {
                            const toff = cell.floor_texture * @floatToInt(c_uint, constants.TextureDim);

                            top_of_floor = std.math.ceil(std.math.min(std.math.min(next_top, lowest_drawn), PlaneHeight / 2 - 1));
                            const thresh = std.math.ceil(highest_drawn);

                            const itop = @floatToInt(usize, std.math.max(top_of_floor, 0));
                            const ptop = @floatToInt(usize, PlaneHeight) - itop - 1;
                            var pix_index = ptop * @floatToInt(usize, PlaneWidth) + col;
                            while (top_of_floor > thresh) : ({
                                top_of_floor -= 1;
                                pix_index += @floatToInt(usize, PlaneWidth);
                            }) {
                                const row_dist = (pheight - cell.floor_height) * PlaneDist / (PlaneHeight / 2 - top_of_floor);
                                // draw the correct pixel
                                const sx = std.math.modf(ppos_x + row_dist * cosra);
                                const sy = std.math.modf(ppos_y + row_dist * sinra);
                                const px = @floatToInt(c_uint, constants.TextureDim * std.math.fabs(sx.fpart));
                                const py = @floatToInt(c_uint, constants.TextureDim * std.math.fabs(sy.fpart));
                                const val = surfaces_image.getPixel(.{ .x = toff + px, .y = py });
                                pixels[pix_index] = val;

                                // record in the z_buffer only if we're above the floor!
                                if (cell.floor_height > 0) self.z_buffer[pix_index] = row_dist;
                            }
                            highest_drawn = next_top;
                        }

                        // draw ceiling?
                        if (false and cell.draw_down and next_bottom < lowest_drawn) {
                            const toff = cell.ceiling_texture * @floatToInt(c_uint, constants.TextureDim);

                            bottom_of_ceiling = std.math.ceil(lowest_drawn);
                            const thresh = std.math.max(std.math.max(next_bottom, highest_drawn), PlaneHeight / 2 - 1);

                            const itop = @floatToInt(usize, bottom_of_ceiling);
                            const ptop = @floatToInt(usize, PlaneHeight) - itop - 1;
                            var pix_index = ptop * @floatToInt(usize, PlaneWidth) + col;

                            while (bottom_of_ceiling > thresh) : ({
                                bottom_of_ceiling -= 1;
                                pix_index += @floatToInt(usize, PlaneWidth);
                            }) {
                                const row_dist = (cell.ceiling_height - pheight) * PlaneDist / (bottom_of_ceiling - PlaneHeight / 2);

                                const sx = std.math.modf(ppos_x + row_dist * cosra);
                                const sy = std.math.modf(ppos_y + row_dist * sinra);
                                const px = @floatToInt(c_uint, constants.TextureDim * std.math.fabs(sx.fpart));
                                const py = @floatToInt(c_uint, constants.TextureDim * std.math.fabs(sy.fpart));
                                const val = surfaces_image.getPixel(.{ .x = toff + px, .y = py });
                                pixels[pix_index] = val;

                                if (cell.draw_down) self.z_buffer[pix_index] = row_dist;
                            }
                            lowest_drawn = next_bottom;
                        }
                    }
                }
                // Have we filled this column?
                if (top_of_floor > lowest_drawn or bottom_of_ceiling < highest_drawn) {
                    still_drawing = false;
                }
            }
        }
    };
}