2D SDF and Contour Lines

A quick experiment to visualize a 2D Signed Distance Field (SDF) using the Contour Lines utility code from Metaball Contour Lines

For more 2D SDF functions see: iquilezles.org/www/articles/distfunctions2d/distfunctions2d.htm

#contourlines #sdf #signeddistancefields

Log in to post a comment.

// 2D SDF and Contour Lines. Created by Reinder Nijhoff 2020 - @reindernijhoff
//
// https://turtletoy.net/turtle/1ddbf02c17
//

const scene = 1; // min=1, max=4, step=1
const precision = .5;

const turtle = new Turtle(-45,-10);
const text = new Text();
const segments = text.print(turtle, "Hello, world\n    ~~", 0.5);

const def = [];
for (let i=0; i<500; i++) def.push([Math.random()*100-50,Math.random()*100-50, 2 + Math.random() * 15]);

function sdCircle( p, r ) {
    return length(p) - r;
}
function sdHexagram( p, r ) {
    const kx = -0.5, ky =0.8660254038, kz = 0.5773502692, kw = 1.7320508076;
    p = abs(p);
    p = sub(p, scale([kx, ky], 2*Math.min(dot([kx, ky],p), 0)));
    p = sub(p, scale([ky, kx], 2*Math.min(dot([ky, kx],p), 0)));
    p = sub(p, [Math.min(Math.max(p[0],r*kz),r*kw),r]);
    return length(p)*Math.sign(p[1]);
}
function sdBox( p, b ) {
    const d = sub(abs(p), b);
    const o = Math.min(Math.max(d[0],d[1]),0);
    return length(add(max(d, [0, 0]), [o,o]));
}
function sdSegment( p, a, b ) {
    const pa = sub(p, a), ba = sub(b, a);
    const h = Math.max(0, Math.min(1, dot(pa,ba)/dot(ba,ba)));
    return length(sub(pa, scale(ba,h)));
}

function map(p) {
    p = add(scale(p, 0.713), [1e-8, 1e-8]);
    let d = 10000;
    switch(scene) {
        case 1:
            for (let i=0; i<400; i++) {
                d = Math.min(d, sdCircle(sub(p, def[i]), def[i][2]));
            }
            break;
        case 2:
            for (let i=0; i<10; i++) {
                d = Math.min(d, sdBox(sub(p, def[i]), [def[i][2], def[i+1][2]]));
            }
            break;
        case 3:
            for (let i=0; i<10; i++) {
                d = Math.min(d, sdHexagram(sub(p, def[i]), def[i][2]));        
            }
            break;
        case 4:
            for (let i=0; i<segments.length; i++) {
                d = Math.min(d, sdSegment(p, segments[i][0], segments[i][1]));
            }
            break;
    }
    return d;
}

const cache = new Float64Array((300/precision*2)**2);
cache.fill(1000);

function cachedMap(p) {
    const id = ((((p[0]+150)/precision*2)|0) + ((((p[1]+150)/precision*2)|0) * 300/precision*2));
    if (cache[id] < 500) {
        return cache[id];
    } else {
        return cache[id] = map(p);
    }
}


function walk(i) {
    const pairs = ContourLines(i - 20, precision, cachedMap);
    const lines = mergePairs(pairs);

    lines.forEach(line => {
        turtle.jump(line[0]);
        for (let i=1; i<line.length; i++)
            turtle.goto(line[i]);
    });
    return i < 150;
}

function mergePairs(pairs) {
    const np = [];
    while (pairs.length) {
        const l = pairs.pop(), eps = 1e-16;
        np.push(l);
        lineadded:
        for (let p0 = l[l.length-1], i=0; i<pairs.length; i++) {
            const p1 = pairs[i];
            if (dist_sqr(p0, p1[0]) <= eps) {
                l.push(pairs.splice(i, 1)[0][1]);
                continue lineadded;
            }
            if (dist_sqr(p0, p1[1]) <= eps) {
                l.push(pairs.splice(i, 1)[0][0]);
                continue lineadded;
            }
        }
    }
    return np;
}

////////////////////////////////////////////////////////////////
// Contour Lines utility code. Created by Reinder Nijhoff 2020
// 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 lerp(v1, v2, 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 = 1, italic = 0, kerning = 1) {
            const r = [];
            t.radians();
            t.up();
            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 => {
                    	p.map( (s, i) => {
                    	    const p0 = [t.x(), t.y()];
                        	t.goto(this.rotAdd([(s[0]-s[1]*italic)*scale - lt, s[1]*scale], pos, h));
                        	if (i>0) r.push([p0, [t.x(), t.y()]]);
                        });
                    });
                    pos = this.rotAdd([(rt - lt)*kerning, 0], pos, h);
                }
            });
            t.down();
            return r;
        }
        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();
}

////////////////////////////////////////////////////////////////
// 2D math functions
////////////////////////////////////////////////////////////////

function max(a, b) { return [Math.max(a[0], b[0]), Math.max(a[1], b[1])]; }
function min(a, b) { return [Math.min(a[0], b[0]), Math.min(a[1], b[1])]; }
function abs(a) { return [Math.abs(a[0]), Math.abs(a[1])]; }
function cross(a, b) { return [a[1]*b[2]-a[2]*b[1], a[2]*b[0]-a[0]*b[2], a[0]*b[1]-a[1]*b[0]]; }
function midpoint(a, b) { return [(a[0]+b[0])*.5, (a[1]+b[1])*.5]; }
function equal(a,b) { return .001>dist_sqr(a,b); }
function scale(a,b) { return [a[0]*b,a[1]*b]; }
function add(a,b) { return [a[0]+b[0],a[1]+b[1]]; }
function sub(a,b) { return [a[0]-b[0],a[1]-b[1]]; }
function mul(a,b) { return [a[0]*b[0],a[1]*b[1]]; }
function dot(a,b) { return a[0]*b[0]+a[1]*b[1]; }
function dist_sqr(a,b) { return (a[0]-b[0])**2+(a[1]-b[1])**2; }
function dist(a,b) { return Math.sqrt(dist_sqr(a,b)); }
function length(a) { return Math.sqrt(dot(a,a)); }
function normalize(a) { return scale(a, 1/length(a)); }
function lerp(a,b,t) { return [a[0]*(1-t)+b[0]*t,a[1]*(1-t)+b[1]*t]; }