// Raytraced sphere #5. Created by Reinder Nijhoff 2021
// @reindernijhoff
//
// https://turtletoy.net/turtle/2696d19370
//

// Forked from "Raytraced sphere #4" by reinder
// https://turtletoy.net/turtle/121df29c5c

Canvas.setpenopacity(0.7);

const radius = 1; // min=0.1, max=5, step=0.01
const minRadius = 0.1; // min=0.01, max=1, step=0.01
const maxPathLength = 50;  // min=1, max=100, step=0.1
const frequency = 1.5; //min=.1, max=10, step=.01
const curlStrength = 0.05; // min=0.001, max=1, step=0.001
const seed = 69; // min=1, max=100, step=1
const maxTries = 75;

const grid  = new PoissonDiscGrid(radius);
const noise = new SimplexNoise(seed);
const turtle = new Turtle();
turtle.traveled = 0;
turtle.direction = 1;

const canvas_size = 95;
const light_position = [-2,3,-4];
const ro = [0,0,-3.5];
const sphere_pos = [-.2,0,0];

function fbm(x, y) {
    x *= frequency / 100;
    y *= frequency / 100;
    let f = 1., v = 0.;
    for (let i=0; i<3; i++) {
        v += noise.noise2D([x * f, y * f]) / f;
        f *= 2; x += 32;
    }
    return v;
}

function curlNoiseM(x, y) {
    const eps = 0.01;
    
    let dx = (fbm(x, y + eps) - fbm(x, y - eps))/(2 * eps) * curlStrength;
    let dy = (fbm(x + eps, y) - fbm(x - eps, y))/(2 * eps) * curlStrength;
    
    dx += (get_image_intensity(x, y + eps) - get_image_intensity(x, y - eps))/(2 * eps);
    dy += (get_image_intensity(x + eps, y) - get_image_intensity(x - eps, y))/(2 * eps);
    
    const l = Math.hypot(dx, dy) * 10;
    const c = [dx / l, -dy / l];	
    
    return c;
}

function getRadius(p2) {
    const l = get_image_intensity(p2[0], p2[1]);
    return (minRadius * l + radius * (1-l)) / 2;
}

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

    const curl = curlNoiseM(p[0], p[1]);
    const dest = [p[0]+curl[0]*turtle.direction, p[1]+curl[1]*turtle.direction];
    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;
        turtle.direction = Math.sign(Math.random()-.5);
        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;
}

function get_image_intensity(x,y) {
    x /= canvas_size;
    y /= canvas_size;
    
    const rd = normalize3([x,-y,2]);
    let normal;
    let light = 0;
    let hit;
    let plane_hit = false;
    
    let dist = intersect_sphere(ro, rd, sphere_pos, 1);
    if (dist > 0) {
        hit = add3(ro, scale3(rd, dist));
        normal = normalize3(hit);
    } else {
        dist = 10000;
    }
    if (rd[1] < 0) {
       const plane_dist = -1/rd[1];
       if (plane_dist < dist) {
            dist = plane_dist;
            plane_hit = true;
            hit = add3(ro, scale3(rd, dist));
            normal = [0,1,0];
        }
    } 
    
    if (dist > 0 && dist < 10000) {
        let vec_to_light = sub3(hit, light_position);
        const light_dist_sqr = dot3(vec_to_light, vec_to_light);
        
        vec_to_light = scale3(vec_to_light, -1/Math.sqrt(light_dist_sqr));
        
        let light = dot3(normal, vec_to_light);
        if (!plane_hit) {
            light = Math.max(0, .3 + .7 * light) ** 2;
        }
        
        
        light *= 30 / light_dist_sqr;
        
        // shadow ?
        if (plane_hit && intersect_sphere(hit, vec_to_light, sphere_pos, 1) > 0) {
            light *= 0.01;
        }
        
        return  Math.exp(-2*Math.max(0,light));
    } else {
        return 1;
    }
}

const scale3=(a,b)=>[a[0]*b,a[1]*b,a[2]*b];
const len3=(a)=>Math.sqrt(dot3(a,a));
const normalize3=(a)=>scale3(a,1/len3(a));
const add3=(a,b)=>[a[0]+b[0],a[1]+b[1],a[2]+b[2]];
const sub3=(a,b)=>[a[0]-b[0],a[1]-b[1],a[2]-b[2]];
const dot3=(a,b)=>a[0]*b[0]+a[1]*b[1]+a[2]*b[2];

function intersect_sphere(ro, rd, center, radius) {
    const oc = sub3(ro, center);
	const b = dot3( oc, rd );
	const c = dot3( oc, oc ) - radius * radius;
	const h = b*b - c;
	if( h<0 ) return -1;
	return -b - Math.sqrt( h );
}

////////////////////////////////////////////////////////////////
// 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 * radius + 1)|0) {
                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);
}

////////////////////////////////////////////////////////////////
// Simplex Noise utility code. Created by Reinder Nijhoff 2020
// https://turtletoy.net/turtle/6e4e06d42e
// Based on: http://webstaff.itn.liu.se/~stegu/simplexnoise/simplexnoise.pdf
////////////////////////////////////////////////////////////////
function SimplexNoise(seed = 1) {
	const grad = [  [1, 1, 0], [-1, 1, 0], [1, -1, 0], [-1, -1, 0],
	            	[1, 0, 1], [-1, 0, 1], [1, 0, -1], [-1, 0, -1],
            		[0, 1, 1], [0, -1, 1], [0, 1, -1], [0, -1, -1] ];
	const perm = new Uint8Array(512);
            		
	const F2 = (Math.sqrt(3) - 1) / 2, F3 = 1/3;
	const G2 = (3 - Math.sqrt(3)) / 6, G3 = 1/6;

	const dot2 = (a, b) => a[0] * b[0] + a[1] * b[1];
	const sub2 = (a, b) => [a[0] - b[0], a[1] - b[1]];
	const dot3 = (a, b) => a[0] * b[0] + a[1] * b[1] + a[2] * b[2];
	const sub3 = (a, b) => [a[0] - b[0], a[1] - b[1], a[2] - b[2]];

	class SimplexNoise {
		constructor(seed = 1) {
			for (let i = 0; i < 512; i++) {
				perm[i] = i & 255;
			}
			for (let i = 0; i < 255; i++) {
				const r = (seed = this.hash(i+seed)) % (256 - i)  + i;
				const swp = perm[i];
				perm[i + 256] = perm[i] = perm[r];
				perm[r + 256] = perm[r] = swp;
			}
		}
		noise2D(p) {
			const s = dot2(p, [F2, F2]);
			const c = [Math.floor(p[0] + s), Math.floor(p[1] + s)];
			const i = c[0] & 255, j = c[1] & 255;
			const t = dot2(c, [G2, G2]);

			const p0 = sub2(p, sub2(c, [t, t]));
			const o  = p0[0] > p0[1] ? [1, 0] : [0, 1];
			const p1 = sub2(sub2(p0, o), [-G2, -G2]);
			const p2 = sub2(p0, [1-2*G2, 1-2*G2]);
			
			let n =  Math.max(0, 0.5-dot2(p0, p0))**4 * dot2(grad[perm[i+perm[j]] % 12], p0);
			    n += Math.max(0, 0.5-dot2(p1, p1))**4 * dot2(grad[perm[i+o[0]+perm[j+o[1]]] % 12], p1);
		    	n += Math.max(0, 0.5-dot2(p2, p2))**4 * dot2(grad[perm[i+1+perm[j+1]] % 12], p2);
			
			return 70 * n;
		}
		hash(i) {
            i = 1103515245 * ((i >> 1) ^ i);
            const h32 = 1103515245 * (i ^ (i>>3));
            return h32 ^ (h32 >> 16);
		}
	}
	return new SimplexNoise(seed);
}