// Möbius Ladder and Curl. Created by Reinder Nijhoff 2021 - @reindernijhoff
//
// https://turtletoy.net/turtle/6ce99160fe

// Forked from "Möbius Ladder" by llemarie
// https://turtletoy.net/turtle/b141d327fc

// LL 2021

Canvas.setpenopacity(.6);

const turtle = new Turtle();
turtle.traveled = 0;

const radius = 0.7; // min=0.01, max=1, step=0.01
const minRadius = 0.1; // min=0.01, max=1, step=0.01
const maxPathLength = 75;  // min=1, max=100, step=0.1
const maxTries = 200;

const grid  = new PoissonDiscGrid(radius);

const scene = 5;       // min=0, max=6, step=1 (Sphere,Torus,Sphere+Torus,Knot,Metaballs,Mobius,Box)

const MAX_STEPS = 100;
const MAX_DIST = 100;
const SURF_DIST = .001;

function length2(v2) { return Math.sqrt(v2[0]*v2[0] + v2[1]*v2[1]); }
function length3(v3) { return Math.sqrt(v3[0]*v3[0] + v3[1]*v3[1] + v3[2]*v3[2]); }
function normalize3(v3) { var l = length3(v3); if (l<0.00001) l=1; return [v3[0]/l, v3[1]/l, v3[2]/l]; }
function mul2(a2, f) { return [a2[0]*f, a2[1]*f]; }
function mul3(a3, f) { return [a3[0]*f, a3[1]*f, a3[2]*f]; }
function add3(a3, b3) { return [a3[0]+b3[0], a3[1]+b3[1], a3[2]+b3[2]]; }
function sub3(a3, b3) { return [a3[0]-b3[0], a3[1]-b3[1], a3[2]-b3[2]]; }
function cross3(a3, b3) { return [ a3[1] * b3[2] - a3[2] * b3[1], a3[2] * b3[0] - a3[0] * b3[2], a3[0] * b3[1] - a3[1] * b3[0] ]; }
function fract3(v3) { return [ Math.trunc(v3[0]), Math.trunc(v3[1]), Math.trunc(v3[2]) ]; }
function abs3(v3) { return [ Math.abs(v3[0]), Math.abs(v3[1]), Math.abs(v3[2]) ]; }
function dot3(a3, b3) { return a3[0] * b3[0] + a3[1] * b3[1] + a3[2] * b3[2]; }
function mul_mat2(v2, m22) { return [ v2[0] * m22[0] + v2[1] * m22[1], v2[0] * m22[2] + v2[1] * m22[3] ]; }
function clamp(x, min, max) { return Math.min(max, Math.max(min, x)); }
function smoothstep(edge0, edge1, x) { x = clamp((x - edge0) / (edge1 - edge0), 0.0, 1.0); return x * x * (3 - 2 * x); }
function tri3(x3) { return abs3(sub3(fract3(x3), .5)); }
function mix(x, y, a) { return x * (1-a) + y * a; }
function smin(a, b , s) { var h = clamp( 0.5 + 0.5*(b-a)/s, 0. , 1.); return mix(b, a, h) - h*(1.0-h)*s; }

function rotation_mat22(a) {
    var s = Math.sin(a);
    var c = Math.cos(a);
    return [c, -s, s, c];
}

function mat2_r2(th) {
    var a2 = [ Math.sin(1.5707963 + th), Math.sin(th) ];
    return [ a2[0], a2[1], -a2[1], a2[0] ];
}

function GetRayDir(uv2, p3, l3, z) {
    var f3 = normalize3(sub3(l3, p3));
    var r3 = normalize3(cross3([0,1,0], f3));
    var u3 = cross3(f3, r3);
    var c3 = mul3(f3, z);
    var i3 = add3(add3(c3, mul3(r3, uv2[0])), mul3(u3, uv2[1]));
    var d3 = normalize3(i3);
    return d3;
}

// Box
function sdBox(p3, s3) {
    p3 = sub3(abs3(p3), s3);
    var r = Math.min(Math.max(p3[0], Math.max(p3[1], p3[2])), 0);
    var q3 = [Math.max(p3[0], 0), Math.max(p3[1], 0), Math.max(p3[2], 0)];
    q3 = add3(q3, [r,r,r]);
	return length3(q3);
}

// Torus
function sdTorus(p3, r1, r2) {
    var cp2 = [ length2([p3[0], p3[2]]) - r1, p3[1] ];
    var d = length2(cp2) - r2;

    return d;
}

// Knot
function sdKnot(p3, r1, r2, twist, split) {
    var cp2 = [ length2([p3[0], p3[2]]) - r1, p3[1] ];
    
    var a = Math.atan2(p3[2], p3[0]); // polar angle between -pi and pi
    cp2 = mul_mat2(cp2, rotation_mat22(a * twist));
    cp2[1] = Math.abs(cp2[1]) - split;

    var d = length2(cp2) - r2;

    return d * .8;
}

// Sphere
function sdSphere(p3, r) {
    var d = length3(p3) - r;
    return d;
}

// Mobius
// Adapted from https://www.shadertoy.com/view/XldSDs
function sdMobius(q3) {
    const toroidRadius = 0.8; // The object's disc radius.
    const polRot = 0.5; // Poloidal rotations.
    const ringNum = 16; // Number of quantized objects embedded between the rings.
    
    var p3 = [...q3];
    var a = Math.atan2(p3[2], p3[0]);
    
    var xz = [ p3[0], p3[2] ];
    var r2 = mat2_r2(a);
    xz = mul_mat2(xz, r2);
    p3[0] = xz[0]; p3[2] = xz[1];

    p3[0] -= toroidRadius;
    
    var xy = [ p3[0], p3[1] ];
    r2 = mat2_r2(a*polRot);
    xy = mul_mat2(xy, r2);
    p3[0] = xy[0]; p3[1] = xy[1];

    p3 = abs3(sub3(abs3(p3), [.25, .25, .25]));

    var rail = Math.max(Math.max(p3[0], p3[1]) - .07, (Math.max(p3[1]-p3[0], p3[1] + p3[0])*.7071 - .075));
    
    p3 = [...q3];

    var ia = Math.floor(ringNum * a / 6.2831853);  
  	ia = (ia + .5) / ringNum * 6.2831853; 

    xz = [ p3[0], p3[2] ];
    r2 = mat2_r2(ia);
    xz = mul_mat2(xz, r2);
    p3[0] = xz[0]; p3[2] = xz[1];

    p3[0] -= toroidRadius;

    xy = [ p3[0], p3[1] ];
    r2 = mat2_r2(a*polRot);
    xy = mul_mat2(xy, r2);
    p3[0] = xy[0]; p3[1] = xy[1];

    p3 = abs3(p3);
    var ring = Math.max(p3[0], p3[1]);
    ring = Math.max(Math.max(ring - .275, p3[2] - .03), -(ring - .2));
    
    return smin(ring, rail, .03); 
}

function sdMetaBalls(p3, r, spread) {
    let d = MAX_DIST;
    
    balls = [ [spread * 0.3, spread * 0.5, 0], [0, spread * -0.5, spread * 0.01], [spread * 0.7, 0, 0], [spread * -0.55, 0, 0] ];
    
    for (b in balls) {
        const q3 = add3(p3, balls[b]);
        d = smin(d, sdSphere(q3, r), 0.45);
    }
    
    return d;
}

function map(p3) {
    let d = MAX_DIST;
    
    if (scene == 0 || scene == 2) d = Math.min(d, sdSphere(p3, 0.7));
    
    if (scene == 1 || scene == 2) d = Math.min(d, sdTorus(p3, 0.8, 0.05));

    if (scene == 3) d = Math.min(d, sdKnot(p3, 0.7, 0.1, 2.5, .2));

    if (scene == 4) d = Math.min(d, sdMetaBalls(p3, 0.23, 0.8));

    if (scene == 5) d = Math.min(d, sdMobius(p3));

    if (scene == 6) d = Math.min(d, sdBox(p3, [0.5,0.5,0.5]));
    if (scene == 6) d = smin(d, sdBox(add3(p3, [0.6, 0.6, -0.6]), [0.2,0.2,0.2]), 0.5);
    
    return d;
}

function calcNormal(p3) {
    const e = 0.1 * SURF_DIST;
    return normalize3([ 
         map(add3(p3, [e,0,0])) - map(add3(p3, [-e,0,0])),
         map(add3(p3, [0,e,0])) - map(add3(p3, [0,-e,0])),
         map(add3(p3, [0,0,e])) - map(add3(p3, [0,0,-e]))]);
}

function RayMarch(ro3, rd3) {
	var dO = 0;
    
    for (var i = 0; i < MAX_STEPS; i++)
    {
    	var p3 = add3(ro3, mul3(rd3, dO));
        var dS = map(p3);
        dO += dS;
        if (dO > MAX_DIST) return MAX_DIST;
        if (Math.abs(dS)<SURF_DIST) break;
    }
    
    return dO;
}


function getRay(p2) {
     // Convert to -1 to 1
    const uv2 = [ p2[0] / 100, p2[1] / 100 ];

    // Ray origin
    let ro3 = [0, -0.2, -1.2];
    if (scene == 3) ro3 = [ 0, -1, -1 ];
    if (scene == 4) ro3 = [ 0, 0, -1 ];
    if (scene == 5) ro3 = [ 0, -1, -1.5 ];
    if (scene == 6) ro3 = [ -1, -1, -1 ];

    let l3 = [ 0, 0.0, 0 ];
    if (scene == 3) l3 = [ 0, 0.4, 0 ];
    if (scene == 5) l3 = [ 0, 0.4, 0 ];

    // Ray direction
    var rd3 = GetRayDir(uv2, ro3, l3, 1.);
    return [ro3, rd3];
}

// p: 2D point in -100 to 100 range
function zFunc(p2) {
    const [ro3, rd3] = getRay(p2);

    // Get distance to intersection
    return RayMarch(ro3, rd3);
}

function getLighting(p2, dist) {
    const [ro3, rd3] = getRay(p2);
    const p3 = add3(ro3, mul3(rd3, dist));
    const n3 = calcNormal(p3);
    
    // return .5*n3[0]+.5;
    return .5*dot3(n3, [0.9,0,-.436])+.5;
}

function getRadius(p2) {
    const l = getLighting(p2, zFunc(p2));
    return (minRadius * l + radius * (1-l)) / 2;
}


function curlNoise(x, y) {
    const eps = 0.1;
    
    const dx = (zFunc([x, y + eps]) - zFunc([x, y - eps]))/(2 * eps);
    const dy = (zFunc([x + eps, y]) - zFunc([x - eps, y]))/(2 * eps);
    
    const l = Math.hypot(dx, dy) * 10;
    return [dx / l, -dy / l];	
}

function walk(i) {
    const p = turtle.pos();

    const curl = curlNoise(p[0], p[1]);
    const dest = [p[0]+curl[0], p[1]+curl[1]];
    dest[2] = getRadius(dest);
    
    if (turtle.traveled < maxPathLength && Math.abs(dest[0]) < 110 && Math.abs(dest[1]) < 110 && grid.insert(dest)) {
        turtle.goto(dest);
        turtle.traveled += Math.hypot(curl[0], curl[1]);
    } else {
        turtle.traveled = 0;
        let r, i = 0;
        do { 
            r =[Math.random()*200-100, Math.random()*200-100];
            r[2] = getRadius(r);
            i ++;
        } while(!grid.insert(r) && i < maxTries);
        if (i >= maxTries) {
            return false;
        }
        turtle.jump(r);
    }
    return true;
}

////////////////////////////////////////////////////////////////
// Poisson-Disc utility code. Created by Reinder Nijhoff 2019
// https://turtletoy.net/turtle/b5510898dc
////////////////////////////////////////////////////////////////
function PoissonDiscGrid(radius) {
    class PoissonDiscGrid {
        constructor(radius) {
            this.cellSize = 1/Math.sqrt(2)/radius;
            this.cells = [];
            this.queue = [];
        }
        insert(p) {
            const x = p[0]*this.cellSize|0, y=p[1]*this.cellSize|0;
            for (let xi = x-1; xi<=x+1; xi++) {
                for (let yi = y-1; yi<=y+1; yi++) {
                    const ps = this.cell(xi,yi);
                    for (let i=0; i<ps.length; i++) {
                        if ((ps[i][0]-p[0])**2 + (ps[i][1]-p[1])**2 < (ps[i][2]+p[2])**2) {
                            return false;
                        }
                    }
                }       
            }
            this.queue.push([p, x, y]);
            if (this.queue.length > 10) {
                const d = this.queue.shift();
                this.cell(d[1], d[2]).push(d[0]);
            }
            return true;
        }
        cell(x,y) {
            const c = this.cells;
            return (c[x]?c[x]:c[x]=[])[y]?c[x][y]:c[x][y]=[];
        }
    }
    return new PoissonDiscGrid(radius);
}