// Forked from "FSD Raytraced Sphere #1" by imakerobots
// https://turtletoy.net/turtle/8f85afd31a

// Forked from "Floyd–Steinberg dithering" by imakerobots



// raytraced sphere part from https://turtletoy.net/turtle/11075dfee0
const canvas_size = 95;
const brown_rot = 360;
const brown_for_min = 1;
const brown_for_max = 10;

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

function get_image_intensity(x,y) {
    x /= canvas_size;
    y /= canvas_size;
    
    const rd = vec_normalize([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 = vec_add(ro, vec_mul(rd, dist));
        normal = vec_normalize(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 = vec_add(ro, vec_mul(rd, dist));
            normal = [0,1,0];
        }
    } 
    
    if (dist > 0 && dist < 100) {
        let vec_to_light = vec_sub(hit, light_position);
        const light_dist_sqr = vec_dot(vec_to_light, vec_to_light);
        
        vec_to_light = vec_mul(vec_to_light, -1/Math.sqrt(light_dist_sqr));
        
        let light = vec_dot(normal, vec_to_light);
        light *= 20 / light_dist_sqr;  // changed the intensity a bit
        
        // shadow ?
        if (plane_hit && intersect_sphere(hit, vec_to_light, sphere_pos, 1) > 0) {
            light = 0.01;  // added some ambient light.  make 0 for none.
        }
        
        return Math.sqrt(Math.min(1, Math.max(0,light)));
    } else {
        return 0;
    }
}


// math functions
function vec_normalize(a) {
    const l = Math.sqrt(vec_dot(a,a));
    return [a[0]/l,a[1]/l,a[2]/l];
}

function vec_add(a, b) {
    return [a[0]+b[0], a[1]+b[1], a[2]+b[2]]
}

function vec_mul(a, b) {
    return [a[0]*b, a[1]*b, a[2]*b]
}

function vec_sub(a, b) {
    return [a[0]-b[0], a[1]-b[1], a[2]-b[2]]
}

function vec_dot(a, b) {
    return a[0]*b[0]+a[1]*b[1]+a[2]*b[2];
}

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









const iterations=800; // min=1 max=5000, step=10

// dithering part from https://turtletoy.net/turtle/d47e2bad0c
const opacity=0.1;
var brightest;
Canvas.setpenopacity(opacity);

// Global code will be evaluated once.
const turtle = new Turtle();


function get_pixel(x,y) {
    return get_image_intensity( x,y );
}

function get_image(x,y) {
    y=Math.floor(y);
    x=Math.floor(x);
    return image[y*200+x];
}


function QuadTree_create(x0,y0,x1,y1) {
    var quad=[
        Math.floor(x0),
        Math.floor(y0),
        Math.floor(x1),
        Math.floor(y1),
        0,
        0
    ];

    var w=Math.floor(x1-x0);
    var h=Math.floor(y1-y0);
    var size=w*h;
    // find the average
    for(var y=0;y<h;++y) {
        for(var x=0;x<w;++x) {
            quad[4] += get_image(x0+x,y0+y);
        }
    }
    quad[4] /= size;
    // find the mean square error
    for(var y=0;y<h;++y) {
        for(var x=0;x<w;++x) {
            var d = get_image(x0+x,y0+y) - quad[4];
            quad[5] += d*d;
        }
    }
    quad[5] /= size;
    
    return quad;
}

function QuadTree_drawX(quad) {
    var w=(quad[2]+quad[0])/2;
    var h=(quad[3]+quad[1])/2;
    turtle.jump(w      -100,quad[1]-100);
    turtle.goto(w      -100,quad[3]-100);
    turtle.jump(quad[0]-100,h      -100);
    turtle.goto(quad[2]-100,h      -100);
}

function QuadTree_drawBox(quad) {
    turtle.jump(quad[0]-100,quad[1]-100);
    turtle.goto(quad[0]-100,quad[3]-100);
    turtle.goto(quad[2]-100,quad[3]-100);
    turtle.goto(quad[2]-100,quad[1]-100);
    turtle.goto(quad[0]-100,quad[1]-100);
}

function QuadTree_drawShaded(quad) {
    QuadTree_drawBox(quad);
    QuadTree_drawBox(quad);
    var left =quad[0]-100;
    var right=quad[2]-100;
    
    var intensity = 1-(quad[4]/brightest);
    if(intensity>0.01) {
        // fill the quad
        for(var i=0;i<intensity;i+=0.1) {
            for(var y=quad[1];y<quad[3];y+=0.1) {
                turtle.jump(left ,y-100);
                turtle.goto(right,y-100);
            }
        }
    }
}

function QuadTree_split(quad) {
    var w=(quad[2]-quad[0]);
    var h=(quad[3]-quad[1]);
    var w2=w/2;
    var h2=h/2;
    if(w2<=1||h2<=1) {
        finishedNodes.push(quad);
        return;
    }
    //QuadTree_drawX(quad);
    var x0=quad[0];
    var y0=quad[1];
    var x1=quad[2];
    var y1=quad[3];
    allNodes.push(QuadTree_create(x0   ,y0   ,x0+w2,y0+h2));
    allNodes.push(QuadTree_create(x0+w2,y0   ,x1   ,y0+h2));
    allNodes.push(QuadTree_create(x0+w2,y0+h2,x1   ,y1   ));
    allNodes.push(QuadTree_create(x0   ,y0+h2,x0+w2,y1   ));
}

// precalculate the raytraced image.
var image=[];
for(var y=0;y<200;++y) {
    for(var x=0;x<200;++x) {
        image[y*200+x] = get_pixel(x-100,y-100);
    }
}

// our list of active quads
var allNodes = [];
var finishedNodes = [];
// initialized with the root quad
allNodes.push(QuadTree_create(0,0,200,200));

// draw the outside quad
turtle.pendown();
turtle.jump(-100,-100);
turtle.goto(-100, 100);
turtle.goto( 100, 100);
turtle.goto( 100,-100);
turtle.goto(-100,-100);
//drawOriginal();

function drawOriginal() {
    // display the raytraced image
    for(var py=0;py<200;++py) {
        for(var px=0;px<200;++px) {
            if(image[py*200+px]<0.65) {
                turtle.jump(px-100,py-100);
                turtle.seth(45);
                turtle.forward(1);
            }
            if(image[py*200+px]<0.15) {
                turtle.jump(px-100,py-100);
                turtle.seth(45+90);
                turtle.forward(1);
            }
        }
    }
}

function walk(i) {
    // find the quadtree node with the biggest error  
    var worst=0;
    for(var j=1;j<allNodes.length;++j) {
        if(allNodes[worst][5] < allNodes[j][5]) {
            worst=j;
        }
    }
    // split the quad node and draw the split
    QuadTree_split(allNodes[worst]);
    // remember the error (maybe quit when error small enough?)
    var err=allNodes[worst][5];
    // take the worst off the list
    allNodes.splice(worst,1);

    if(i==iterations) {
        drawAllRemainingNodes();
        return false;
    }
    return true;
}

function drawAllRemainingNodes() {
    brightest=0;
    for(var j=0;j<allNodes.length;++j) {
        if(brightest<allNodes[j][4]) {
            brightest=allNodes[j][4];
        }
    }
    for(var j=0;j<finishedNodes.length;++j) {
        if(brightest<finishedNodes[j][4]) {
            brightest=finishedNodes[j][4];
        }
    }
    for(var j=0;j<allNodes.length;++j) {
        QuadTree_drawShaded(allNodes[j]);
    }
    for(var j=0;j<finishedNodes.length;++j) {
        QuadTree_drawShaded(finishedNodes[j]);
    }
}