// LL 2021

const turtle = new Turtle();
const text = new Text();

//Canvas.setpenopacity(-1);

const detail_z = 201;   // min=1, max=301, step=2
const detail_xy = 1.5; // min=0.1, max=3, step=0.1
const passes = 2;      // min=1, max=3, step=1 (X, XY, XYZ)
const show_debug = 0;  /// min=0, max=1, step=1 (No,Yes)
const scene = 5;       // min=0, max=6, step=1 (Sphere,Torus,Sphere+Torus,Knot,Metaballs,Mobius,Box)

const range = [ -1.1, 1.1 ];

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

var debug_count = 0;
function debug_print(string) { if (debug_count++<100) console.log(string); }

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); 
}


// Terrain - doesn't work
function sdTerrain(p3)
{
    //return p3[1];
    
    var yzx = [ p3[1], p3[2], p3[0] ];
    var n = dot3(tri3(add3(mul3(p3,0.3), tri3(mul3(yzx, 0.15)))), [0.44, 0.44, 0.44]);
    p3 = mul3(p3, 1.57);//1.5773;// - n; // The "n" mixes things up more.
    var vec2 = mul_mat2([p3[1], p3[2]], [.866025, .5, -.5, .866025]);
    p3[1] = vec2[0]; p3[2] = vec2[1];
    vec2 = mul_mat2([p3[0], p3[2]], [.866025, .5, -.5, .866025]);
    p3[0] = vec2[0]; p3[2] = vec2[1];
    yzx = [ p3[1], p3[2], p3[0] ];
    n += dot3(tri3(add3(mul3(p3,0.45), tri3(mul3(yzx,0.225)))), [0.222, 0.222, 0.222]);
    
    return smoothstep(0.3, .95, n);
}

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

function map(p3)
{
    var 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 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;
}

var pass = -1;

function key(p2) { return p2[0] * 10000 + p2[1] * 10 + pass; }

var cache = {};
var miss = 0;
var hit = 0;
var line_count = 0;
var line_total_count = 0;
var pass_start = 0;

// p: 2D point in -100 to 100 range
function zFunc(p2)
{
    var key_p2 = key(p2);
    
    if (key_p2 in cache)
    {
        hit++;
        var dist = cache[key_p2];
        return dist;
    }
    else miss++;
    
    // Convert to -1 to 1
    var uv2 = [ p2[0] / 100, p2[1] / 100 ];

    // Ray origin
    var 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 ];

    var 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.);

    // Get distance to intersection
    var dist = RayMarch(ro3, rd3);

    if (dist < MAX_DIST)
    {
        // Get intersection point
        var p3 = add3(ro3, mul3(rd3, dist));
        dist = (p3[pass]-range[0]) / (range[1]-range[0]) * detail_z;
    }

    cache[key_p2] = dist;
    
    return dist;
    
    // Debug
    //return length2(uv2) * 10;
    //if (Math.sqrt(p[0]*p[0] + p[1]*p[1]) < 100) return 2; else return 0;
}

function floor(x) { return Math.round(x*10); }

function line_key(line)
{
    return floor(line[0][0]) * 1000000000 +  floor(line[0][1]) * 1000000 +  floor(line[1][0]) * 1000 + floor(line[1][1]);
}

var line_cache = {};
function is_good(line)
{
    var key = line_key(line);
    if (key in line_cache) return false;
    line_cache[key]=1;
    return true;
}

function walk(i)
{
    var old_pass = pass;
    pass = Math.floor(i / (detail_z+1));
    
    if (old_pass != pass)
    {
        var now = performance.now();
        if (show_debug && old_pass >= 0)
        {
            turtle.jump(-99, 97 - old_pass * 5);
            var percent1 = (line_count / line_total_count * 100).toFixed(1);
            var percent2 = (hit / (hit+miss) * 100).toFixed(1);
            var string =`Pass: ${old_pass}`;
            string += ` | Lines: ${line_count} (${percent1}%)`;
            //string +=` | Cache hit: ${hit} / ${hit+miss} (${percent2}%)`;
            var elapsed_s = ((now - pass_start)/1000).toFixed(1);
            string +=` | Time: ${elapsed_s} s`;
            text.print(turtle, string, .15);
            hit = 0; miss = 0; line_count = 0; line_total_count = 0;
        }
        pass_start = now;
    }
    if (pass >= passes) return false;
    
    const lines = ContourLines(i%detail_z, 1/detail_xy, zFunc);
    lines.forEach(line => {
        if (is_good(line))
        {
            turtle.jump(line[0]);
            turtle.goto(line[1]);
            line_count++;
        }
        line_total_count++;
    });
    
    if (show_debug)
    {
        const y = 99 - passes * 5, min_x = -90, max_x =  90;
        x1 = min_x + (max_x - min_x) * (i-1) / (detail_z * passes);
        x2 = min_x + (max_x - min_x) * (i-0) / (detail_z * passes);
        turtle.jump(x1, y);
        turtle.goto(x2, y);
    }
    
    return true;
}

// Metaball Contour Lines. Created by Reinder Nijhoff 2020 - @reindernijhoff
// The MIT License
// https://turtletoy.net/turtle/104c4775c5
function ContourLines(z, step, zFunc) {
    const intersectSegmentZ = (z, v1, v2) => {
    	if (v1[2] === v2[2]) return false;
    	const t = (z - v1[2]) / (v2[2] - v1[2]);
    	if (t <= 0 || t > 1) return false;
    	return [v1[0]+(v2[0]-v1[0])*t, v1[1]+(v2[1]-v1[1])*t];
    }
    const intersectTriangleZ = (z, p1, p2, p3) => {
        const p = [];
    	const v1 = intersectSegmentZ(z, p1, p2);
    	const v2 = intersectSegmentZ(z, p2, p3);
    	const v3 = intersectSegmentZ(z, p3, p1);
    	if (v1 && v2) p.push([v1, v2]);
        if (v1 && v3) p.push([v1, v3]);
    	if (v2 && v3) p.push([v2, v3]);
		return p;
    }
	const result = [];
	for (let x = -100; x <= 100; x += step) {
    	for (let y = -100; y <= 100; y += step) {
			const corners = [[x, y], [x+step, y], [x+step, y+step], [x, y+step]];
			corners.forEach( c => c[2] = zFunc(c) );
			const c3 = [x+step/2, y+step/2, zFunc([x+step/2, y+step/2])];
			for (let i=0; i<4; i++) {
			    result.push(...intersectTriangleZ(z, corners[i], corners[(i+1) & 3], c3));
			}
		}
	}
	return result;
}

////////////////////////////////////////////////////////////////
// Text utility code. Created by Reinder Nijhoff 2019
// https://turtletoy.net/turtle/1713ddbe99
////////////////////////////////////////////////////////////////

function Text() {
    class Text {
        print (t, str, scale) {
            t.radians();
            let pos = [t.x(), t.y()], h = t.h(), o = pos;
            str.split('').map(c => {
                const i = c.charCodeAt(0) - 32;
                if (i < 0 ) {
                    pos = o = this.rotAdd([0, 48*scale], o, h);
                } else if (i > 96 ) {
                    pos = this.rotAdd([16*scale, 0], o, h);
                } else {
                    const d = dat[i], lt = d[0]*scale, rt = d[1]*scale, paths = d[2];
                    paths.map( p => {
                        t.up();
                    	p.map( s=> {
                        	t.goto(this.rotAdd([s[0]*scale - lt, s[1]*scale], pos, h));
                        	t.down();
                        });
                    });
                    pos = this.rotAdd([rt - lt, 0], pos, h);
                }
            });
        }
        rotAdd (a, b, h) {
            return [Math.cos(h)*a[0] - Math.sin(h)*a[1] + b[0], 
                    Math.cos(h)*a[1] + Math.sin(h)*a[0] + b[1]];
        }
    }
    
const dat = ('br>eoj^jl<jqirjskrjq>brf^fe<n^ne>`ukZdz<qZjz<dgrg<cmqm>`thZhw<lZlw<qao_l^h^e_caccdeefg'+
'gmiojpkqmqporlshsercp>^vs^as<f^h`hbgdeeceacaab_d^f^h_k`n`q_s^<olmmlolqnspsrrspsnqlol>]wtgtfsereqfph'+
'nmlpjrhsdsbraq`o`makbjifjekckaj_h^f_eaecffhimporqssstrtq>eoj`i_j^k_kajcid>cqnZl\\j_hcghglhqjulxnz>c'+
'qfZh\\j_lcmhmllqjuhxfz>brjdjp<egom<ogem>]wjajs<ajsj>fnkojpiojnkokqis>]wajsj>fnjniojpkojn>_usZaz>`ti'+
'^f_dbcgcjdofrisksnrpoqjqgpbn_k^i^>`tfbhak^ks>`tdcdbe`f_h^l^n_o`pbpdofmicsqs>`te^p^jfmfogphqkqmppnrk'+
'shserdqco>`tm^clrl<m^ms>`to^e^dgefhekenfphqkqmppnrkshserdqco>`tpao_l^j^g_ebdgdlepgrjsksnrppqmqlping'+
'kfjfggeidl>`tq^gs<c^q^>`th^e_dadceegfkgnhpjqlqopqorlshserdqcocldjfhigmfoepcpao_l^h^>`tpeohmjjkikfjd'+
'hcecddaf_i^j^m_oapepjoomrjshserdp>fnjgihjikhjg<jniojpkojn>fnjgihjikhjg<kojpiojnkokqis>^vrabjrs>]wag'+
'sg<amsm>^vbarjbs>asdcdbe`f_h^l^n_o`pbpdofngjijl<jqirjskrjq>]xofndlcicgdfeehekfmhnknmmnk<icgefhfkgmh'+
'n<ocnknmpnrntluiugtdsbq`o_l^i^f_d`bbad`g`jambodqfrislsorqqrp<pcokompn>asj^bs<j^rs<elol>_tc^cs<c^l^o'+
'_p`qbqdpfoglh<chlhoipjqlqopqorlscs>`urcqao_m^i^g_eadccfckdnepgrismsorqprn>_tc^cs<c^j^m_oapcqfqkpnop'+
'mrjscs>`sd^ds<d^q^<dhlh<dsqs>`rd^ds<d^q^<dhlh>`urcqao_m^i^g_eadccfckdnepgrismsorqprnrk<mkrk>_uc^cs<'+
'q^qs<chqh>fnj^js>brn^nnmqlrjshsfreqdndl>_tc^cs<q^cl<hgqs>`qd^ds<dsps>^vb^bs<b^js<r^js<r^rs>_uc^cs<c'+
'^qs<q^qs>_uh^f_daccbfbkcndpfrhslsnrppqnrkrfqcpan_l^h^>_tc^cs<c^l^o_p`qbqepgohlici>_uh^f_daccbfbkcnd'+
'pfrhslsnrppqnrkrfqcpan_l^h^<koqu>_tc^cs<c^l^o_p`qbqdpfoglhch<jhqs>`tqao_l^h^e_caccdeefggmiojpkqmqpo'+
'rlshsercp>brj^js<c^q^>_uc^cmdpfrisksnrppqmq^>asb^js<r^js>^v`^es<j^es<j^os<t^os>`tc^qs<q^cs>asb^jhjs'+
'<r^jh>`tq^cs<c^q^<csqs>cqgZgz<hZhz<gZnZ<gznz>cqc^qv>cqlZlz<mZmz<fZmZ<fzmz>brj\\bj<j\\rj>asazsz>fnkc'+
'ieigjhkgjfig>atpeps<phnfleiegfehdkdmepgrislsnrpp>`sd^ds<dhffhekemfohpkpmopmrkshsfrdp>asphnfleiegfeh'+
'dkdmepgrislsnrpp>atp^ps<phnfleiegfehdkdmepgrislsnrpp>asdkpkpiognfleiegfehdkdmepgrislsnrpp>eqo^m^k_j'+
'bjs<gene>atpepuoxnylzizgy<phnfleiegfehdkdmepgrislsnrpp>ate^es<eihfjemeofpips>fni^j_k^j]i^<jejs>eoj^'+
'k_l^k]j^<kekvjyhzfz>are^es<oeeo<ikps>fnj^js>[y_e_s<_ibfdegeifjijs<jimfoeretfuius>ateees<eihfjemeofp'+
'ips>atiegfehdkdmepgrislsnrppqmqkphnfleie>`sdedz<dhffhekemfohpkpmopmrkshsfrdp>atpepz<phnfleiegfehdkd'+
'mepgrislsnrpp>cpgegs<gkhhjfleoe>bsphofleieffehfjhkmlompopporlsisfrep>eqj^jokrmsos<gene>ateeeofrhsks'+
'mrpo<peps>brdejs<pejs>_ubefs<jefs<jens<rens>bseeps<pees>brdejs<pejshwfydzcz>bspees<eepe<esps>cqlZj['+
'i\\h^h`ibjckekgii<j[i]i_jakbldlfkhgjkllnlpkrjsiuiwjy<ikkmkojqirhthvixjylz>fnjZjz>cqhZj[k\\l^l`kbjci'+
'eigki<j[k]k_jaibhdhfihmjilhnhpirjskukwjy<kkimiojqkrltlvkxjyhz>^vamakbhdgfghhlknlplrksi<akbidhfhhill'+
'nmpmrlsisg>brb^bscsc^d^dsese^f^fsgsg^h^hsisi^j^jsksk^l^lsmsm^n^nsoso^p^psqsq^r^rs').split('>').map(
    r=> { return [r.charCodeAt(0)-106,r.charCodeAt(1)-106, r.substr(2).split('<').map(a => {const ret 
    = []; for (let i=0; i<a.length; i+=2) {ret.push(a.substr(i, 2).split('').map(b => b.charCodeAt(0)
    -106));} return ret; })]; });

    return new Text();
}