// You can find the Turtle API reference here: https://turtletoy.net/syntax
Canvas.setpenopacity(1);

const randomSeed = 10000; //min=10000 max=100000 step=1
const rNebula = 70; //min=50 max=80 step=1
const rMaxSphere = 15; //min=1 max=70 step=1
const rMinSphere = 7; //min=1 max=70 step=1
const zIncrease = 1; //min=.1 max=3 step=.1
const nSpheres = 80; //min=1 max=200 step=1

const pi2 = Math.PI * 2;

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

// Seedable random number generator by David Bau: http://davidbau.com/archives/2010/01/30/random_seeds_coded_hints_and_quintillions.html
!function(a,b,c,d,e,f,g,h,i){function j(a){var b,c=a.length,e=this,f=0,g=e.i=e.j=0,h=e.S=[];for(c||(a=[c++]);d>f;)h[f]=f++;for(f=0;d>f;f++)h[f]=h[g=s&g+a[f%c]+(b=h[f])],h[g]=b;(e.g=function(a){for(var b,c=0,f=e.i,g=e.j,h=e.S;a--;)b=h[f=s&f+1],c=c*d+h[s&(h[f]=h[g=s&g+b])+(h[g]=b)];return e.i=f,e.j=g,c})(d)}function k(a,b){var c,d=[],e=typeof a;if(b&&"object"==e)for(c in a)try{d.push(k(a[c],b-1))}catch(f){}return d.length?d:"string"==e?a:a+"\0"}function l(a,b){for(var c,d=a+"",e=0;e<d.length;)b[s&e]=s&(c^=19*b[s&e])+d.charCodeAt(e++);return n(b)}function m(c){try{return o?n(o.randomBytes(d)):(a.crypto.getRandomValues(c=new Uint8Array(d)),n(c))}catch(e){return[+new Date,a,(c=a.navigator)&&c.plugins,a.screen,n(b)]}}function n(a){return String.fromCharCode.apply(0,a)}var o,p=c.pow(d,e),q=c.pow(2,f),r=2*q,s=d-1,t=c["seed"+i]=function(a,f,g){var h=[];f=1==f?{entropy:!0}:f||{};var o=l(k(f.entropy?[a,n(b)]:null==a?m():a,3),h),s=new j(h);return l(n(s.S),b),(f.pass||g||function(a,b,d){return d?(c[i]=a,b):a})(function(){for(var a=s.g(e),b=p,c=0;q>a;)a=(a+c)*d,b*=d,c=s.g(1);for(;a>=r;)a/=2,b/=2,c>>>=1;return(a+c)/b},o,"global"in f?f.global:this==c)};if(l(c[i](),b),g&&g.exports){g.exports=t;try{o=require("crypto")}catch(u){}}else h&&h.amd&&h(function(){return t})}(this,[],Math,256,6,52,"object"==typeof module&&module,"function"==typeof define&&define,"random");
Math.seedrandom(''+randomSeed);
// Add a seed in seedrandom, then Math.random will use this seed



let blobs = [];
for(let i = 0; i < nSpheres; i++) {
    blobs.push([
        getPoint(rNebula),
        rMinSphere+(Math.random() * Math.max(0, rMaxSphere - rMinSphere)),
        [[null, 0]], [[null, pi2]]
    ]);
}

function getPoint(rMax) {
    let u = Math.random();
    let v = Math.random();
    let theta = u * pi2;
    let phi = Math.acos(2 * v - 1);
    let r = Math.cbrt(Math.random()) * rMax;
    let sinTheta = Math.sin(theta);
    let cosTheta = Math.cos(theta);
    let sinPhi = Math.sin(phi);
    let cosPhi = Math.cos(phi);
    return [
        r * sinPhi * cosTheta,
        r * sinPhi * sinTheta,
        r * cosPhi
    ];
}

function processBlobs(blobs) {
        
    function rot2(a) { return [Math.cos(a), -Math.sin(a), Math.sin(a), Math.cos(a)]; }
    function trans2(m, a) { return [m[0]*a[0]+m[2]*a[1], m[1]*a[0]+m[3]*a[1]]; }
    const deepClone = (o) => JSON.parse(JSON.stringify(o));
    const isPointInBlob = (pt, blob) => ((blob[0][0] - pt[0])**2 + (blob[0][1] - pt[1])**2) <= (blob[1]**2);
    function radClip(a) {
        while(a < 0) { a += pi2; }
        while(a > pi2) { a -= pi2; }
        return a;
    }
    
    for(let i = 0; i < blobs.length; i++) {
        let currentBlob = deepClone(blobs[i]);
        for(let j = 0; j < blobs.length; j++) {
            if(i == j) continue;
            
            let otherBlob = deepClone(blobs[j]);
            otherBlob[0][0] -= currentBlob[0][0];
            otherBlob[0][1] -= currentBlob[0][1];
    
            let angle = 0;
            let dx = otherBlob[0][0];
            let dy = otherBlob[0][1];
            if(dx == 0) {
                angle = Math.PI * (dy > 0? .5: 1.5);
            } else {
                let dydx = dy/dx;
                angle = Math.atan(dy/dx);
                
                if(dx < 0) {
                    angle += Math.PI
                }
            }
            
            otherBlob[0] = trans2(rot2(angle), otherBlob[0]);
            dx = otherBlob[0][0];
            dy = otherBlob[0][1];
            
            if(dx == 0) continue; //blob has same center coordinates
    
            let x = (dx**2 - otherBlob[1]**2 + currentBlob[1]**2) / (2 * dx);
    
            if(Math.abs(x) > currentBlob[1] ) continue; // blob is further away than currentBlob
    
            //let y = Math.sqrt(currentBlob[1]**2 - x**2);
            if(Math.acos(x/currentBlob[1]) == NaN) continue;
            if(blobs[i][2].length == 1 && blobs[i][2][0][0] == null) {
                blobs[i][2] = [];
            }
            if(blobs[i][3].length == 1 && blobs[i][3][0][0] == null) {
                blobs[i][3] = [];
            }
            
            //inangle
            blobs[i][2].push([j, radClip(Math.acos(x/currentBlob[1]) + angle)]);
            //outangle
            blobs[i][3].push([j, radClip((Math.PI * 2 - Math.acos(x/currentBlob[1])) + angle)]);
        }
    }
    
    //remove all ins and outs from blobs that are in a blob that is not the blob itself or the intersection blob
    //for every blob
    for(let i = 0; i < blobs.length; i++) {
        
        //for every draw-start (in)
        for(let ins = 0; ins < blobs[i][2].length; ins++) {
            //for every other blob        
            for(let j = 0; j < blobs.length; j++) {
                //than the 'current' one (i)
                if(i == j) continue;
                //or the one associated with the draw-start (in)
                if(blobs[i][2][ins][0] == j) continue;
                
                //todo: check if point is in circle j, and if so, remove it from the list
                if(isPointInBlob([
                    blobs[i][0][0] + (Math.cos(blobs[i][2][ins][1]) * blobs[i][1]),
                    blobs[i][0][1] + (Math.sin(blobs[i][2][ins][1]) * blobs[i][1])
                ], blobs[j])) {
                    blobs[i][2] = blobs[i][2].filter((elm, idx) => idx != ins);
                    ins--;
                    j = blobs.length;
                }
            }
        }
        
        //for every draw-start (in)
        for(let outs = 0; outs < blobs[i][3].length; outs++) {
            //for every other blob        
            for(let j = 0; j < blobs.length; j++) {
                //than the 'current' one (i)
                if(i == j) continue;
                //or the one associated with the draw-start (in)
                if(blobs[i][3][outs][0] == j) continue;
                
                //todo: check if point is in circle j, and if so, remove it from the list
                if(isPointInBlob([
                    blobs[i][0][0] + (Math.cos(blobs[i][3][outs][1]) * blobs[i][1]),
                    blobs[i][0][1] + (Math.sin(blobs[i][3][outs][1]) * blobs[i][1])
                ], blobs[j])) {
                    blobs[i][3] = blobs[i][3].filter((elm, idx) => idx != outs);
                    outs--;
                    j = blobs.length;
                }
            }
        }
        blobs[i][2].sort((a, b) => (a[1] < b[1]) ? -1 : 1)
        blobs[i][3].sort((a, b) => (a[1] < b[1]) ? -1 : 1)
    }
    
    return blobs;
}

// The walk function will be called until it returns false.
function walk(ii) {
    let z = (ii * zIncrease) - rNebula - rMaxSphere;
    
    let cblobs = blobs.filter((c) => c[0][2] - c[1] <= z && c[0][2] + c[1] >= z)
    cblobs = JSON.parse(JSON.stringify(cblobs));
    for(let k = 0; k < cblobs.length; k++) {
        cblobs[k][1] = Math.sqrt(cblobs[k][1]**2 - (cblobs[k][0][2] - z)**2);
        cblobs[k][0][2] = z;
    }
    
    let circles = processBlobs(cblobs);
    
    for(let i = 0; i < circles.length; i++) {
        if(circles.length == 0) return false;
        
        for(let  j = 0; j < circles[i][2].length; j++) {
            drawCirclePart(turtle, circles[i], circles[i][2][j][1], circles[i][3][getFirstOutAfter(circles[i][3], circles[i][2][j][1])][1] );
        }
    }

    for(let i = 0; i < circles.length; i++) {    
        let max = Math.ceil(Math.PI / Math.asin(.5 / circles[i][1]));
        let pts = []
        for(let j = 0; j < max; j++) {
            pts.push(getBlobCoordinateAt(circles[i], pi2 * j / max));
        }
        const p = polygons.create();
        p.addPoints(...pts);
        polygons.draw(turtle, p);
    }

    return ii * zIncrease < (rNebula + rMaxSphere) * 2;
}

function getFirstOutAfter(outs, start) {
    let min = 2000;
    let idx = null;
    for(let i = 0; i < outs.length; i++) {
        let test = outs[i][1] + (outs[i][1] < start? pi2: 0);
        if(test < min) {
            min = test;
            idx = i;
        }
    }
    return idx;
}

function drawCirclePart(turtle, blob, from = 0, to = pi2) {
    const p = polygons.create();

    if(to < from) { to += pi2; }
    let step = pi2 / Math.ceil(Math.PI / Math.asin(.5 / blob[1]));
    let a = 0;
    for(a = from + step; a <= to; a+=step) {
        p.addSegments(getBlobCoordinateAt(blob, a-step), getBlobCoordinateAt(blob, a));
    }
    p.addSegments(getBlobCoordinateAt(blob, a-step), getBlobCoordinateAt(blob, to));

    polygons.draw(turtle, p);
}

const getBlobCoordinateAt = (blob, angle) => [
    blob[0][0] + (Math.cos(angle) * blob[1]),
    ((blob[0][1] + (Math.sin(angle) * blob[1])) / 3) + blob[0][2]
];


////////////////////////////////////////////////////////////////
// Polygon Clipping utility code - Created by Reinder Nijhoff 2019
// (Polygon binning by Lionel Lemarie 2021)
// https://turtletoy.net/turtle/a5befa1f8d
////////////////////////////////////////////////////////////////
function Polygons(){const t=[],s=25,e=Array.from({length:s**2},t=>[]),n=class{constructor(){this.cp=[],this.dp=[],this.aabb=[]}addPoints(...t){let s=1e5,e=-1e5,n=1e5,h=-1e5;(this.cp=[...this.cp,...t]).forEach(t=>{s=Math.min(s,t[0]),e=Math.max(e,t[0]),n=Math.min(n,t[1]),h=Math.max(h,t[1])}),this.aabb=[s,n,e,h]}addSegments(...t){t.forEach(t=>this.dp.push(t))}addOutline(){for(let t=0,s=this.cp.length;t<s;t++)this.dp.push(this.cp[t],this.cp[(t+1)%s])}draw(t){for(let s=0,e=this.dp.length;s<e;s+=2)t.jump(this.dp[s]),t.goto(this.dp[s+1])}addHatching(t,s){const e=new n;e.cp.push([-1e5,-1e5],[1e5,-1e5],[1e5,1e5],[-1e5,1e5]);const h=Math.sin(t)*s,o=Math.cos(t)*s,a=200*Math.sin(t),i=200*Math.cos(t);for(let t=.5;t<150/s;t++)e.dp.push([h*t+i,o*t-a],[h*t-i,o*t+a]),e.dp.push([-h*t+i,-o*t-a],[-h*t-i,-o*t+a]);e.boolean(this,!1),this.dp=[...this.dp,...e.dp]}inside(t){let s=0;for(let e=0,n=this.cp.length;e<n;e++)this.segment_intersect(t,[.1,-1e3],this.cp[e],this.cp[(e+1)%n])&&s++;return 1&s}boolean(t,s=!0){const e=[];for(let n=0,h=this.dp.length;n<h;n+=2){const h=this.dp[n],o=this.dp[n+1],a=[];for(let s=0,e=t.cp.length;s<e;s++){const n=this.segment_intersect(h,o,t.cp[s],t.cp[(s+1)%e]);!1!==n&&a.push(n)}if(0===a.length)s===!t.inside(h)&&e.push(h,o);else{a.push(h,o);const n=o[0]-h[0],i=o[1]-h[1];a.sort((t,s)=>(t[0]-h[0])*n+(t[1]-h[1])*i-(s[0]-h[0])*n-(s[1]-h[1])*i);for(let n=0;n<a.length-1;n++)(a[n][0]-a[n+1][0])**2+(a[n][1]-a[n+1][1])**2>=.001&&s===!t.inside([(a[n][0]+a[n+1][0])/2,(a[n][1]+a[n+1][1])/2])&&e.push(a[n],a[n+1])}}return(this.dp=e).length>0}segment_intersect(t,s,e,n){const h=(n[1]-e[1])*(s[0]-t[0])-(n[0]-e[0])*(s[1]-t[1]);if(0===h)return!1;const o=((n[0]-e[0])*(t[1]-e[1])-(n[1]-e[1])*(t[0]-e[0]))/h,a=((s[0]-t[0])*(t[1]-e[1])-(s[1]-t[1])*(t[0]-e[0]))/h;return o>=0&&o<=1&&a>=0&&a<=1&&[t[0]+o*(s[0]-t[0]),t[1]+o*(s[1]-t[1])]}};return{list:()=>t,create:()=>new n,draw:(n,h,o=!0)=>{reducedPolygonList=function(n){const h={},o=200/s;for(var a=0;a<s;a++){const c=a*o-100,r=[0,c,200,c+o];if(!(n[3]<r[1]||n[1]>r[3]))for(var i=0;i<s;i++){const c=i*o-100;r[0]=c,r[2]=c+o,n[0]>r[2]||n[2]<r[0]||e[i+a*s].forEach(s=>{const e=t[s];n[3]<e.aabb[1]||n[1]>e.aabb[3]||n[0]>e.aabb[2]||n[2]<e.aabb[0]||(h[s]=1)})}}return Array.from(Object.keys(h),s=>t[s])}(h.aabb);for(let t=0;t<reducedPolygonList.length&&h.boolean(reducedPolygonList[t]);t++);h.draw(n),o&&function(n){t.push(n);const h=t.length-1,o=200/s;e.forEach((t,e)=>{const a=e%s*o-100,i=(e/s|0)*o-100,c=[a,i,a+o,i+o];c[3]<n.aabb[1]||c[1]>n.aabb[3]||c[0]>n.aabb[2]||c[2]<n.aabb[0]||t.push(h)})}(h)}}}