// Forked from "Initial contact" by ge1doot
// https://turtletoy.net/turtle/97d9047c16
// ----------------------------------------------------
// Idea:
//   1. Build all boxes in full 3D (axis-aligned)
//   2. Project into camera space (true pinhole camera)
//   3. Depth-sort boxes from near to far
//   4. For each visible face, create a 2D polygon
//   5. Use a 2D polygon boolean engine (Reinder-style) to clip
//      already drawn polygons -> hidden line removal in screen space
//   6. Add hatching on selected faces
//
//

Canvas.setpenopacity(0.8);
const turtle = new Turtle();
turtle.penup();

// Basic 3D vector helpers

function vec3(x, y, z) { return { x:x, y:y, z:z }; }

function add(a, b) { return vec3(a.x + b.x, a.y + b.y, a.z + b.z); }
function sub(a, b) { return vec3(a.x - b.x, a.y - b.y, a.z - b.z); }
function mul(a, s) { return vec3(a.x * s, a.y * s, a.z * s); }

function dot(a, b) { return a.x*b.x + a.y*b.y + a.z*b.z; }

function cross(a, b) {
    return vec3(
        a.y*b.z - a.z*b.y,
        a.z*b.x - a.x*b.z,
        a.x*b.y - a.y*b.x
    );
}

function length(a) { return Math.hypot(a.x, a.y, a.z); }

function normalize(a) {
    const l = length(a) || 1;
    return vec3(a.x / l, a.y / l, a.z / l);
}

// Camera (pinhole with optional roll + fisheye)

const camera = {
    // Camera position and orientation in world space
    eye:    vec3(0, 80, -260),
    target: vec3(0,  0,   40),
    up:     vec3(0,  1,    0),

    // Field of view (radians) – big value = wide angle
    fov: 155 * Math.PI / 180,

    // Roll around viewing direction (radians)
    roll: (-8 * Math.random() * 16) * Math.PI / 180,   // small tilt to break symmetry

    // Simple fisheye coefficient (0 = no fisheye)
    fisheyeK: 0,

    // Internal precomputed values
    setup() {
        // Forward vector: where the camera looks
        const f = normalize(sub(this.target, this.eye));

        // Right and up vectors (orthonormal basis)
        let r = normalize(cross(f, this.up));
        let u = cross(r, f);

        // Apply roll around the forward axis (f)
        if (this.roll !== 0) {
            const c = Math.cos(this.roll);
            const s = Math.sin(this.roll);
            // Rotate r,u in their 2D plane
            const r2 = vec3(
                r.x * c + u.x * s,
                r.y * c + u.y * s,
                r.z * c + u.z * s
            );
            const u2 = vec3(
                u.x * c - r.x * s,
                u.y * c - r.y * s,
                u.z * c - r.z * s
            );
            r = r2; u = u2;
        }

        // Store camera basis
        this.f = f; // forward
        this.r = r; // right
        this.u = u; // up

        // Precompute tan(fov/2) and screen scaling factor
        this.tanHalfFov = Math.tan(this.fov * 0.5);
        this.screenScale = 230; // how big the world appears on canvas
    },

    // Project a world point into 2D screen coordinates.
    // Returns {x,y,z} or null when behind the camera.
    project(p) {
        // Vector from eye to point
        const d = sub(p, this.eye);

        // Camera-space coordinates (x,y along right/up, z along forward)
        const x = dot(d, this.r);
        const y = dot(d, this.u);
        const z = dot(d, this.f);

        // Clip points that are too close / behind the camera
        if (z <= 1e-2) return null;

        // Perspective divide
        let xn = x / (z * this.tanHalfFov);
        let yn = -y / (z * this.tanHalfFov);

        // Simple radial fisheye distortion
        if (this.fisheyeK !== 0) {
            const r2 = xn*xn + yn*yn;
            const factor = 1 + this.fisheyeK * r2;
            xn *= factor;
            yn *= factor;
        }

        return {
            x: xn * this.screenScale,
            y: yn * this.screenScale,
            z: z
        };
    }
};

camera.setup();

// Box primitive (axis-aligned) + face list

class Box {
    constructor(cx, cy, cz, sx, sy, sz) {
        this.c = vec3(cx, cy, cz);
        this.s = vec3(sx, sy, sz);
        this._verts = null;
        this.depth = 0;   // filled later with min camera-space z
    }

    // Lazy computation of the 8 corner vertices
    vertices() {
        if (this._verts) return this._verts;
        const c = this.c, s = this.s;
        this._verts = [
            vec3(c.x-s.x, c.y-s.y, c.z-s.z), // 0
            vec3(c.x+s.x, c.y-s.y, c.z-s.z), // 1
            vec3(c.x+s.x, c.y+s.y, c.z-s.z), // 2
            vec3(c.x-s.x, c.y+s.y, c.z-s.z), // 3
            vec3(c.x-s.x, c.y-s.y, c.z+s.z), // 4
            vec3(c.x+s.x, c.y-s.y, c.z+s.z), // 5
            vec3(c.x+s.x, c.y+s.y, c.z+s.z), // 6
            vec3(c.x-s.x, c.y+s.y, c.z+s.z), // 7
        ];
        return this._verts;
    }
}

// Each face: indices in the vertex array + "hatch" flag

const BOX_FACES = [
    { idx:[0,1,2,3], hatch:1 }, // front
    { idx:[0,4,5,1], hatch:1 }, // bottom / side
    { idx:[3,2,6,7], hatch:0 }, // top
    { idx:[0,3,7,4], hatch:0 }, // left
    { idx:[1,5,6,2], hatch:1 }, // right
    { idx:[4,7,6,5], hatch:0 }  // back
];

// 2D Polygon engine with occlusion + hatching
// (optimized but same idea as Reinder's original)

function Polygons() {
    // List of polygons already drawn on screen
    const polygonList = [];
    // Hash of lines already drawn (avoid double-drawing in overlapping areas)
    const linesDrawn  = Object.create(null);

    class Polygon {
        constructor() {
            this.cp = [];   // "clip path": polygon vertices [ [x,y], ... ]
            this.dp = [];   // segments to draw: [p0, p1, p0, p1, ...]
            this.aabb = null;
        }

        // Add all points at once and compute AABB
        addPoints(points) {
            const cp = this.cp;
            for (let i = 0; i < points.length; i++) cp.push(points[i]);
            this.aabb = this.computeAABB();
        }

        // Add outline segments from cp into dp
        addOutline(startIndex) {
            const cp = this.cp;
            const n = cp.length;
            for (let i = startIndex || 0; i < n; i++) {
                this.dp.push(cp[i], cp[(i + 1) % n]);
            }
        }

        // Compute axis-aligned bounding box [cx, cy, halfW, halfH]
        computeAABB() {
            const cp = this.cp;
            let xmin =  1e9, ymin =  1e9;
            let xmax = -1e9, ymax = -1e9;
            for (let i = 0; i < cp.length; i++) {
                const x = cp[i][0];
                const y = cp[i][1];
                if (x < xmin) xmin = x;
                if (x > xmax) xmax = x;
                if (y < ymin) ymin = y;
                if (y > ymax) ymax = y;
            }
            const area = (xmax - xmin) * (ymax - ymin);
            this.area = area;
            return [
                (xmin + xmax) * 0.5,
                (ymin + ymax) * 0.5,
                (xmax - xmin) * 0.5,
                (ymax - ymin) * 0.5
            ];
        }

        // Actually draw all segments in dp (with line de-duplication)
        draw(t) {
            const dp = this.dp;
            for (let i = 0; i < dp.length; i += 2) {
                const d0 = dp[i];
                const d1 = dp[i + 1];
                const x0 = d0[0], y0 = d0[1];
                const x1 = d1[0], y1 = d1[1];

                // Stable hash for undirected segment
                const hx0 = x0 < x1 ? x0 : x1;
                const hx1 = x0 < x1 ? x1 : x0;
                const hy0 = y0 < y1 ? y0 : y1;
                const hy1 = y0 < y1 ? y1 : y0;
                const line_hash =
                    hx0.toFixed(2) + "-" +
                    hx1.toFixed(2) + "-" +
                    hy0.toFixed(2) + "-" +
                    hy1.toFixed(2);

                if (!linesDrawn[line_hash]) {
                    t.penup();
                    t.goto(x0, y0);
                    t.pendown();
                    t.goto(x1, y1);
                    linesDrawn[line_hash] = true;
                }
            }
        }

        // Add hatching inside this polygon
        // "angle" is direction of the dominant edge,
        // "spacing" is distance between hatch lines
        addHatching(angle, spacing) {
            const MIN_SPACING = 0.1;
            const MIN_AREA = 20;
            spacing = Math.max(spacing, MIN_SPACING);
            if (this.area < MIN_AREA) return;  // no hash on micro-faces
            angle += Math.PI * 0.5;  // make lines perpendicular to given edge
            const tp = new Polygon();

            // Simple rectangular area covering our polygon
            const [cx, cy, hw, hh] = this.aabb;
            const l = Math.sqrt((hw*2)**2 + (hh*2)**2) * 0.5;

            tp.cp.push(
                [cx - hw, cy - hh],
                [cx + hw, cy - hh],
                [cx + hw, cy + hh],
                [cx - hw, cy + hh]
            );
            tp.aabb = tp.computeAABB();

            const cx2 = Math.sin(angle) * l;
            const cy2 = Math.cos(angle) * l;

            let px = cx - Math.cos(angle) * l;
            let py = cy - Math.sin(angle) * l;

            // Create a bunch of parallel lines that cover the AABB
            for (let d = 0; d < l * 2; d += spacing) {
                tp.dp.push(
                    [px + cx2, py - cy2],
                    [px - cx2, py + cy2]
                );
                px += Math.cos(angle) * spacing;
                py += Math.sin(angle) * spacing;
            }

            // Clip those lines by our polygon (difference=false -> intersection)
            tp.boolean(this, false);
            const dp = tp.dp;
            for (let i = 0; i < dp.length; i++) {
                this.dp.push(dp[i]);
            }
        }

        // Point-in-polygon test using ray casting
        inside(p) {
            const cp = this.cp;
            const n = cp.length;
            let int = 0;
            const far = [0.1, -10000];

            for (let i = 0; i < n; i++) {
                const a = cp[i];
                const b = cp[(i + 1) % n];

                // Avoid points extremely close to vertices (numerical issues)
                const dx = p[0] - a[0];
                const dy = p[1] - a[1];
                if (dx*dx + dy*dy <= 0.001) return false;

                if (this.segIntersect(p, far, a, b)) int++;
            }
            return (int & 1) !== 0;
        }

        // Clip this.dp by polygon p
        boolean(p, diff) {
            const src = this.dp;
            const ndp = [];
            const clipCP = p.cp;
            const cl = clipCP.length;

            for (let i = 0; i < src.length; i += 2) {
                const ls0 = src[i];
                const ls1 = src[i + 1];

                // Collect all intersection points with the clip polygon
                const ints = [];
                for (let j = 0; j < cl; j++) {
                    const a = clipCP[j];
                    const b = clipCP[(j + 1) % cl];
                    const pint = this.segIntersectionPoint(ls0, ls1, a, b);
                    if (pint) ints.push(pint);
                }

                if (ints.length === 0) {
                    // No intersection: test if the whole segment is inside or outside
                    if (diff === !p.inside(ls0)) {
                        ndp.push(ls0, ls1);
                    }
                } else {
                    // There are intersections: split the segment
                    ints.push(ls0, ls1);
                    const x0 = ls0[0], y0 = ls0[1];
                    const vx = ls1[0] - x0;
                    const vy = ls1[1] - y0;

                    // Sort points along the segment
                    ints.sort((pA, pB) => {
                        const da = (pA[0]-x0)*vx + (pA[1]-y0)*vy;
                        const db = (pB[0]-x0)*vx + (pB[1]-y0)*vy;
                        return da - db;
                    });

                    // Create sub-segments between consecutive intersection points
                    for (let j = 0; j < ints.length - 1; j++) {
                        const pA = ints[j];
                        const pB = ints[j+1];

                        const dx = pA[0]-pB[0];
                        const dy = pA[1]-pB[1];
                        if (dx*dx + dy*dy < 0.01) continue; // too small

                        const mid = [(pA[0]+pB[0])*0.5, (pA[1]+pB[1])*0.5];
                        if (diff === !p.inside(mid)) {
                            ndp.push(pA, pB);
                        }
                    }
                }
            }

            this.dp = ndp;
            return ndp.length > 0;
        }

        // 2D segment helpers
        segIntersectionPoint(p1, p2, p3, p4) {
            const x1=p1[0], y1=p1[1], x2=p2[0], y2=p2[1];
            const x3=p3[0], y3=p3[1], x4=p4[0], y4=p4[1];

            const d = (y4 - y3)*(x2 - x1) - (x4 - x3)*(y2 - y1);
            if (d === 0) return null;

            const ua = ((x4 - x3)*(y1 - y3) - (y4 - y3)*(x1 - x3)) / d;
            const ub = ((x2 - x1)*(y1 - y3) - (y2 - y1)*(x1 - x3)) / d;

            if (ua >= 0 && ua <= 1 && ub >= 0 && ub <= 1) {
                return [
                    x1 + ua * (x2 - x1),
                    y1 + ua * (y2 - y1)
                ];
            }
            return null;
        }

        segIntersect(p1, p2, p3, p4) {
            return this.segIntersectionPoint(p1, p2, p3, p4) !== null;
        }
    }

    // Simple AABB overlap test
    function aabbOverlap(a, b) {
        return (
            Math.abs(a[0] - b[0]) - (a[2] + b[2]) < 0 &&
            Math.abs(a[1] - b[1]) - (a[3] + b[3]) < 0
        );
    }

    return {
        create() { return new Polygon(); },
        draw(t, poly) {
            const aabb = poly.aabb;
            const list = polygonList;
            let visible = true;

            // Test against all polygons drawn so far
            for (let i = 0; i < list.length; i++) {
                const p1 = list[i];
                if (!aabbOverlap(aabb, p1.aabb)) continue;
                if (!poly.boolean(p1, true)) {
                    visible = false;
                    break;
                }
            }
            if (!visible) return;
            poly.draw(t);
            list.push(poly);
        }
    };
}

// Scene generation – "Initial Contact"

const polygons = Polygons();
const shapes   = [];

// Simple utility
function randRange(a, b) { return a + Math.random() * (b - a); }

// Add a building defined by base rectangle and height
function addBuilding(x, y, z, w, h, p) {
    // z is the "front" of the building, p is its depth
    const cx = x;
    const cy = y;
    const cz = z + p * 0.5;
    shapes.push(new Box(cx, cy, cz, w, h, p * 0.5));
}

// Build a mix of small, medium and very large blocks

const r = (d0, d1) => Math.round(Math.random() * (d1 - d0) + d0);
let w = 100;
for (let z = 400; z > -400; z -= 10) {
	addBuilding(
		r(-w, w), r(-w, w), z,
		r(2, 30), r(2, 30), r(2, 180)
	);
	if (z > -150 && z < 150) {
		for (let i = 0; i < 4; i++) {
			addBuilding(
				r(-400, 400), r(-w, w), z,
				r(2, 80), r(2, 30), r(2, 30)
			);
            addBuilding(
				r(-w, w), r(-400, 400), z,
				r(2, 30), r(2, 80), r(2, 30)
			);
		}
	}
}

// Depth sort in camera space (near to far)

// Depth = minimum camera-space z among the 8 vertices
for (const b of shapes) {
    const verts = b.vertices();
    let zmin = 1e9;
    for (let i = 0; i < verts.length; i++) {
        const d = sub(verts[i], camera.eye);
        const z = dot(d, camera.f);
        if (z < zmin) zmin = z;
    }
    b.depth = zmin;
}

// Sort so that closest boxes are drawn first
shapes.sort((a, b) => a.depth - b.depth);

// Project box faces -> build polygons -> occlusion + hatching

function drawBoxFaces(box) {
    const verts = box.vertices();

    for (let f = 0; f < BOX_FACES.length; f++) {
        const face = BOX_FACES[f];
        const ids  = face.idx;

        const pts2D = [];
        const proj3 = [];

        let skip = false;
        for (let i = 0; i < ids.length; i++) {
            const proj = camera.project(verts[ids[i]]);
            if (!proj) { skip = true; break; }
            proj3.push(proj);
            pts2D.push([proj.x, proj.y]);
        }
        if (skip) continue;

        // Backface culling using signed area in screen space
        // Depending on winding order you may need ">= 0" instead
        const p0 = proj3[0], p1 = proj3[1], p2 = proj3[2];
        const area = (p1.x - p0.x)*(p2.y - p0.y) - (p1.y - p0.y)*(p2.x - p0.x);
        if (area <= 0) continue;

        const poly = polygons.create();
        poly.addPoints(pts2D);

        // Optional hatching for some faces
        if (face.hatch) {

            // Hatch direction aligned with first edge
            const dx = p1.x - p0.x;
            const dy = p1.y - p0.y;
            const a  = Math.atan2(dy, dx);
            poly.addHatching(a, 0.1 + Math.random());
        }

        poly.addOutline(0);
        polygons.draw(turtle, poly);
    }
}

// Draw all boxes
for (const b of shapes) {
    drawBoxFaces(b);
}

// Turtletoy "walk" function, not used here
function walk(i) {
    return false;
}