Skip to content

Instantly share code, notes, and snippets.

@Sphinxxxx

Sphinxxxx/index.html

Created February 14, 2021 15:56
Show Gist options
  • Save Sphinxxxx/5d62355080ea6322d4acbc2542fe5315 to your computer and use it in GitHub Desktop.
Save Sphinxxxx/5d62355080ea6322d4acbc2542fe5315 to your computer and use it in GitHub Desktop.
Download ZIP
Low-poly image generator
Raw
index.html
<script>console.clear();</script>
<script src="//unpkg.com/vue@2"></script>
<script src="//unpkg.com/[email protected]/build/dat.gui.js"></script>
<script src="//unpkg.com/drag-tracker@1"></script>
<script src="//unpkg.com/[email protected]/build/jsfeat.js"></script>
<script src="//unpkg.com/kdbush@3"></script>
<script>
/*
tuple by Ry-♦
https://stackoverflow.com/a/21839292/1869660
*/
window.tuple = (function(){"use strict";let map=new Map();function tuple(){let current=map;let args=Object.freeze(Array.from(arguments));for(let item of args){if(current.has(item)){current=current.get(item);}else{let next=new Map();current.set(item,next);current=next;}}if(!current._myVal){current._myVal=args;}return current._myVal;}return tuple;})();
/*
(c) 2017, Vladimir Agafonkin
Simplify.js, a high-performance JS polyline simplification library
mourner.github.io/simplify-js
*/
window.simplify = (function(){"use strict";function n(n,r){var t=n[0]-r[0],u=n[1]-r[1];return t*t+u*u}function r(n,r,t){var u=r[0],i=r[1],f=t[0]-u,o=t[1]-i;if(0!==f||0!==o){var e=((n[0]-u)*f+(n[1]-i)*o)/(f*f+o*o);e>1?(u=t[0],i=t[1]):e>0&&(u+=f*e,i+=o*e)}return f=n[0]-u,o=n[1]-i,f*f+o*o}function t(r,t){for(var u,i=r[0],f=[i],o=1,e=r.length;e>o;o++)u=r[o],n(u,i)>t&&(f.push(u),i=u);return i!==u&&f.push(u),f}function u(n,t,i,f,o){for(var e,v=f,a=t+1;i>a;a++){var c=r(n[a],n[t],n[i]);c>v&&(e=a,v=c)}v>f&&(e-t>1&&u(n,t,e,f,o),o.push(n[e]),i-e>1&&u(n,e,i,f,o))}function i(n,r){var t=n.length-1,i=[n[0]];return u(n,0,t,r,i),i.push(n[t]),i}function f(n,r,u){if(n.length<=2)return n;var f=void 0!==r?r*r:1;return n=u?n:t(n,f),n=i(n,f)}return f})();
/*
https://github.com/mikolalysenko/cdt2d
A robust 2D constrained Delaunay triangulation library written in JavaScript
Copyright (c) 2015 Mikola Lysenko. The MIT License (MIT)
*/
window.cdt2d = (function(){"use strict";function r(r,n,t,e,a){for(var u=a+1;a>=e;){var o=e+a>>>1,i=r[o],s=void 0!==t?t(i,n):i-n;s>=0?(u=o,a=o-1):e=o+1}return u}function n(r,n,t,e,a){for(var u=a+1;a>=e;){var o=e+a>>>1,i=r[o],s=void 0!==t?t(i,n):i-n;s>0?(u=o,a=o-1):e=o+1}return u}function t(r,n,t,e,a){for(var u=e-1;a>=e;){var o=e+a>>>1,i=r[o],s=void 0!==t?t(i,n):i-n;0>s?(u=o,e=o+1):a=o-1}return u}function e(r,n,t,e,a){for(var u=e-1;a>=e;){var o=e+a>>>1,i=r[o],s=void 0!==t?t(i,n):i-n;0>=s?(u=o,e=o+1):a=o-1}return u}function a(r,n,t,e,a){for(;a>=e;){var u=e+a>>>1,o=r[u],i=void 0!==t?t(o,n):o-n;if(0===i)return u;0>=i?e=u+1:a=u-1}return-1}function u(r,n,t,e,a,u){return"function"==typeof t?u(r,n,t,void 0===e?0:0|e,void 0===a?r.length-1:0|a):u(r,n,void 0,void 0===t?0:0|t,void 0===e?r.length-1:0|e)}function o(r){var n={exports:{}};return r(n,n.exports),n.exports}function i(r,n,t){var e=r*n,a=K*r,u=a-r,o=a-u,i=r-o,s=K*n,f=s-n,h=s-f,v=n-h,l=e-o*h,c=l-i*h,p=c-o*v,g=i*v-p;return t?(t[0]=g,t[1]=e,t):[g,e]}function s(r,n){var t=r+n,e=t-r,a=t-e,u=n-e,o=r-a,i=o+u;return i?[i,t]:[t]}function f(r,n){var t=0|r.length,e=0|n.length;if(1===t&&1===e)return s(r[0],n[0]);var a,u,o=t+e,i=Array(o),f=0,h=0,v=0,l=Math.abs,c=r[h],p=l(c),g=n[v],d=l(g);d>p?(u=c,h+=1,t>h&&(c=r[h],p=l(c))):(u=g,v+=1,e>v&&(g=n[v],d=l(g))),t>h&&d>p||v>=e?(a=c,h+=1,t>h&&(c=r[h],p=l(c))):(a=g,v+=1,e>v&&(g=n[v],d=l(g)));for(var y,b,m,w,x,A=a+u,M=A-a,I=u-M,j=I,T=A;t>h&&e>v;)d>p?(a=c,h+=1,t>h&&(c=r[h],p=l(c))):(a=g,v+=1,e>v&&(g=n[v],d=l(g))),u=j,A=a+u,M=A-a,I=u-M,I&&(i[f++]=I),y=T+A,b=y-T,m=y-b,w=A-b,x=T-m,j=x+w,T=y;for(;t>h;)a=c,u=j,A=a+u,M=A-a,I=u-M,I&&(i[f++]=I),y=T+A,b=y-T,m=y-b,w=A-b,x=T-m,j=x+w,T=y,h+=1,t>h&&(c=r[h]);for(;e>v;)a=g,u=j,A=a+u,M=A-a,I=u-M,I&&(i[f++]=I),y=T+A,b=y-T,m=y-b,w=A-b,x=T-m,j=x+w,T=y,v+=1,e>v&&(g=n[v]);return j&&(i[f++]=j),T&&(i[f++]=T),f||(i[f++]=0),i.length=f,i}function h(r,n,t){var e=r+n,a=e-r,u=e-a,o=n-a,i=r-u;return t?(t[0]=i+o,t[1]=e,t):[i+o,e]}function v(r,n){var t=r.length;if(1===t){var e=J(r[0],n);return e[0]?e:[e[1]]}var a=Array(2*t),u=[.1,.1],o=[.1,.1],i=0;J(r[0],n,u),u[0]&&(a[i++]=u[0]);for(var s=1;t>s;++s){J(r[s],n,o);var f=u[1];N(f,o[0],u),u[0]&&(a[i++]=u[0]);var h=o[1],v=u[1],l=h+v,c=l-h,p=v-c;u[1]=l,p&&(a[i++]=p)}return u[1]&&(a[i++]=u[1]),0===i&&(a[i++]=0),a.length=i,a}function l(r,n){var t=r+n,e=t-r,a=t-e,u=n-e,o=r-a,i=o+u;return i?[i,t]:[t]}function c(r,n){var t=0|r.length,e=0|n.length;if(1===t&&1===e)return l(r[0],-n[0]);var a,u,o=t+e,i=Array(o),s=0,f=0,h=0,v=Math.abs,c=r[f],p=v(c),g=-n[h],d=v(g);d>p?(u=c,f+=1,t>f&&(c=r[f],p=v(c))):(u=g,h+=1,e>h&&(g=-n[h],d=v(g))),t>f&&d>p||h>=e?(a=c,f+=1,t>f&&(c=r[f],p=v(c))):(a=g,h+=1,e>h&&(g=-n[h],d=v(g)));for(var y,b,m,w,x,A=a+u,M=A-a,I=u-M,j=I,T=A;t>f&&e>h;)d>p?(a=c,f+=1,t>f&&(c=r[f],p=v(c))):(a=g,h+=1,e>h&&(g=-n[h],d=v(g))),u=j,A=a+u,M=A-a,I=u-M,I&&(i[s++]=I),y=T+A,b=y-T,m=y-b,w=A-b,x=T-m,j=x+w,T=y;for(;t>f;)a=c,u=j,A=a+u,M=A-a,I=u-M,I&&(i[s++]=I),y=T+A,b=y-T,m=y-b,w=A-b,x=T-m,j=x+w,T=y,f+=1,t>f&&(c=r[f]);for(;e>h;)a=g,u=j,A=a+u,M=A-a,I=u-M,I&&(i[s++]=I),y=T+A,b=y-T,m=y-b,w=A-b,x=T-m,j=x+w,T=y,h+=1,e>h&&(g=-n[h]);return j&&(i[s++]=j),T&&(i[s++]=T),s||(i[s++]=0),i.length=s,i}function p(r,n,t,e,a){this.a=r,this.b=n,this.idx=t,this.lowerIds=e,this.upperIds=a}function g(r,n,t,e){this.a=r,this.b=n,this.type=t,this.idx=e}function d(r,n){var t=r.a[0]-n.a[0]||r.a[1]-n.a[1]||r.type-n.type;return t?t:r.type!==V&&(t=U(r.a,r.b,n.b))?t:r.idx-n.idx}function y(r,n){return U(r.a,r.b,n)}function b(r,n,t,e,a){for(var u=H.lt(n,e,y),o=H.gt(n,e,y),i=u;o>i;++i){for(var s=n[i],f=s.lowerIds,h=f.length;h>1&&U(t[f[h-2]],t[f[h-1]],e)>0;)r.push([f[h-1],f[h-2],a]),h-=1;f.length=h,f.push(a);for(var v=s.upperIds,h=v.length;h>1&&U(t[v[h-2]],t[v[h-1]],e)<0;)r.push([v[h-2],v[h-1],a]),h-=1;v.length=h,v.push(a)}}function m(r,n){var t;return(t=r.a[0]<n.a[0]?U(r.a,r.b,n.a):U(n.b,n.a,r.a))?t:(t=n.b[0]<r.b[0]?U(r.a,r.b,n.b):U(n.b,n.a,r.b),t||r.idx-n.idx)}function w(r,n,t){var e=H.le(r,t,m),a=r[e],u=a.upperIds,o=u[u.length-1];a.upperIds=[o],r.splice(e+1,0,new p(t.a,t.b,t.idx,[o],u))}function x(r,n,t){var e=t.a;t.a=t.b,t.b=e;var a=H.eq(r,t,m),u=r[a],o=r[a-1];o.upperIds=u.upperIds,r.splice(a,1)}function A(r,n){for(var t=r.length,e=n.length,a=[],u=0;t>u;++u)a.push(new g(r[u],null,V,u));for(var u=0;e>u;++u){var o=n[u],i=r[o[0]],s=r[o[1]];i[0]<s[0]?a.push(new g(i,s,X,u),new g(s,i,W,u)):i[0]>s[0]&&a.push(new g(s,i,X,u),new g(i,s,W,u))}a.sort(d);for(var f=a[0].a[0]-(1+Math.abs(a[0].a[0]))*Math.pow(2,-52),h=[new p([f,1],[f,0],-1,[],[],[],[])],v=[],u=0,l=a.length;l>u;++u){var c=a[u],y=c.type;y===V?b(v,h,r,c.a,c.idx):y===X?w(h,r,c):x(h,r,c)}return v}function M(r,n){this.stars=r,this.edges=n}function I(r,n,t){for(var e=1,a=r.length;a>e;e+=2)if(r[e-1]===n&&r[e]===t)return r[e-1]=r[a-2],r[e]=r[a-1],void(r.length=a-2)}function j(r,n){for(var t=Array(r),e=0;r>e;++e)t[e]=[];return new M(t,n)}function T(r,n,t,e,a,u){var o=n.opposite(e,a);if(!(0>o)){if(e>a){var i=e;e=a,a=i,i=u,u=o,o=i}n.isConstraint(e,a)||rr(r[e],r[a],r[u],r[o])<0&&t.push(e,a)}}function q(r,n){for(var t=[],e=r.length,a=n.stars,u=0;e>u;++u)for(var o=a[u],i=1;i<o.length;i+=2){var s=o[i];if(!(u>s||n.isConstraint(u,s))){for(var f=o[i-1],h=-1,v=1;v<o.length;v+=2)if(o[v-1]===s){h=o[v];break}0>h||rr(r[u],r[s],r[f],r[h])<0&&t.push(u,s)}}for(;t.length>0;){for(var s=t.pop(),u=t.pop(),f=-1,h=-1,o=a[u],l=1;l<o.length;l+=2){var c=o[l-1],p=o[l];c===s?h=p:p===s&&(f=c)}0>f||0>h||rr(r[u],r[s],r[f],r[h])>=0||(n.flip(u,s),T(r,n,t,f,u,h),T(r,n,t,u,h,f),T(r,n,t,h,s,f),T(r,n,t,s,f,h))}}function C(r,n,t,e,a,u,o){this.cells=r,this.neighbor=n,this.flags=e,this.constraint=t,this.active=a,this.next=u,this.boundary=o}function F(r,n){return r[0]-n[0]||r[1]-n[1]||r[2]-n[2]}function S(r,n){for(var t=r.cells(),e=t.length,a=0;e>a;++a){var u=t[a],o=u[0],i=u[1],s=u[2];s>i?o>i&&(u[0]=i,u[1]=s,u[2]=o):o>s&&(u[0]=s,u[1]=o,u[2]=i)}t.sort(F);for(var f=Array(e),a=0;a<f.length;++a)f[a]=0;var h=[],v=[],l=Array(3*e),c=Array(3*e),p=null;n&&(p=[]);for(var g=new C(t,l,c,f,h,v,p),a=0;e>a;++a)for(var u=t[a],d=0;3>d;++d){var o=u[d],i=u[(d+1)%3],y=l[3*a+d]=g.locate(i,o,r.opposite(i,o)),b=c[3*a+d]=r.isConstraint(o,i);0>y&&(b?v.push(a):(h.push(a),f[a]=1),n&&p.push([i,o,-1]))}return g}function O(r,n,t){for(var e=0,a=0;a<r.length;++a)n[a]===t&&(r[e++]=r[a]);return r.length=e,r}function k(r,n,t){var e=S(r,t);if(0===n)return t?e.cells.concat(e.boundary):e.cells;for(var a=1,u=e.active,o=e.next,i=e.flags,s=e.cells,f=e.constraint,h=e.neighbor;u.length>0||o.length>0;){for(;u.length>0;){var v=u.pop();if(i[v]!==-a){i[v]=a,s[v];for(var l=0;3>l;++l){var c=h[3*v+l];c>=0&&0===i[c]&&(f[3*v+l]?o.push(c):(u.push(c),i[c]=a))}}}var p=o;o=u,u=p,o.length=0,a=-a}var g=O(s,i,n);return t?g.concat(e.boundary):g}function E(r){return[Math.min(r[0],r[1]),Math.max(r[0],r[1])]}function z(r,n){return r[0]-n[0]||r[1]-n[1]}function B(r){return r.map(E).sort(z)}function D(r,n,t){return n in r?r[n]:t}function G(r,n,t){Array.isArray(n)?(t=t||{},n=n||[]):(t=n||{},n=[]);var e=!!D(t,"delaunay",!0),a=!!D(t,"interior",!0),u=!!D(t,"exterior",!0),o=!!D(t,"infinity",!1);if(!a&&!u||0===r.length)return[];var i=Y(r,n);if(e||a!==u||o){for(var s=Z(r.length,B(n)),f=0;f<i.length;++f){var h=i[f];s.addTriangle(h[0],h[1],h[2])}return e&&nr(r,s),u?a?o?tr(s,0,o):s.cells():tr(s,1,o):tr(s,-1)}return i}var H={ge:function(n,t,e,a,o){return u(n,t,e,a,o,r)},gt:function(r,t,e,a,o){return u(r,t,e,a,o,n)},lt:function(r,n,e,a,o){return u(r,n,e,a,o,t)},le:function(r,n,t,a,o){return u(r,n,t,a,o,e)},eq:function(r,n,t,e,o){return u(r,n,t,e,o,a)}},J=i,K=+(Math.pow(2,27)+1),L=f,N=h,P=v,Q=c,R=o(function(r){function n(r,n){for(var t=Array(r.length-1),e=1;e<r.length;++e)for(var a=t[e-1]=Array(r.length-1),u=0,o=0;u<r.length;++u)u!==n&&(a[o++]=r[e][u]);return t}function t(r){for(var n=Array(r),t=0;r>t;++t){n[t]=Array(r);for(var e=0;r>e;++e)n[t][e]="m"+e+"["+(r-t-1)+"]"}return n}function e(r){return 1&r?"-":""}function a(r){if(1===r.length)return r[0];if(2===r.length)return"sum("+r[0]+","+r[1]+")";var n=r.length>>1;return"sum("+a(r.slice(0,n))+","+a(r.slice(n))+")"}function u(r){if(2===r.length)return["sum(prod("+r[0][0]+","+r[1][1]+"),prod(-"+r[0][1]+","+r[1][0]+"))"];for(var t=[],o=0;o<r.length;++o)t.push("scale("+a(u(n(r,o)))+","+e(o)+r[0][o]+")");return t}function o(r){for(var e=[],o=[],i=t(r),s=[],f=0;r>f;++f)0===(1&f)?e.push.apply(e,u(n(i,f))):o.push.apply(o,u(n(i,f))),s.push("m"+f);var h=a(e),v=a(o),l="orientation"+r+"Exact",c="function "+l+"("+s.join()+"){var p="+h+",n="+v+",d=sub(p,n);return d[d.length-1];};return "+l,p=Function("sum","prod","scale","sub",c);return p(L,J,P,Q)}function i(r){var n=g[r.length];return n||(n=g[r.length]=o(r.length)),n.apply(void 0,r)}function s(){for(;g.length<=f;)g.push(o(g.length));for(var n=[],t=["slow"],e=0;f>=e;++e)n.push("a"+e),t.push("o"+e);for(var a=["function getOrientation(",n.join(),"){switch(arguments.length){case 0:case 1:return 0;"],e=2;f>=e;++e)a.push("case ",e,":return o",e,"(",n.slice(0,e).join(),");");a.push("}var s=new Array(arguments.length);for(var i=0;i<arguments.length;++i){s[i]=arguments[i]};return slow(s);}return getOrientation"),t.push(a.join(""));var u=Function.apply(void 0,t);r.exports=u.apply(void 0,[i].concat(g));for(var e=0;f>=e;++e)r.exports[e]=g[e]}var f=5,h=1.1102230246251565e-16,v=(3+16*h)*h,l=(7+56*h)*h,c=o(3),p=o(4),g=[function(){return 0},function(){return 0},function(r,n){return n[0]-r[0]},function(r,n,t){var e,a=(r[1]-t[1])*(n[0]-t[0]),u=(r[0]-t[0])*(n[1]-t[1]),o=a-u;if(a>0){if(0>=u)return o;e=a+u}else{if(!(0>a))return o;if(u>=0)return o;e=-(a+u)}var i=v*e;return o>=i||-i>=o?o:c(r,n,t)},function(r,n,t,e){var a=r[0]-e[0],u=n[0]-e[0],o=t[0]-e[0],i=r[1]-e[1],s=n[1]-e[1],f=t[1]-e[1],h=r[2]-e[2],v=n[2]-e[2],c=t[2]-e[2],g=u*f,d=o*s,y=o*i,b=a*f,m=a*s,w=u*i,x=h*(g-d)+v*(y-b)+c*(m-w),A=(Math.abs(g)+Math.abs(d))*Math.abs(h)+(Math.abs(y)+Math.abs(b))*Math.abs(v)+(Math.abs(m)+Math.abs(w))*Math.abs(c),M=l*A;return x>M||-x>M?x:p(r,n,t,e)}];s()}),U=R[3],V=0,W=1,X=2,Y=A,Z=j,$=M.prototype;$.isConstraint=function(){function r(r,n){return r[0]-n[0]||r[1]-n[1]}var n=[0,0];return function(t,e){return n[0]=Math.min(t,e),n[1]=Math.max(t,e),H.eq(this.edges,n,r)>=0}}(),$.removeTriangle=function(r,n,t){var e=this.stars;I(e[r],n,t),I(e[n],t,r),I(e[t],r,n)},$.addTriangle=function(r,n,t){var e=this.stars;e[r].push(n,t),e[n].push(t,r),e[t].push(r,n)},$.opposite=function(r,n){for(var t=this.stars[n],e=1,a=t.length;a>e;e+=2)if(t[e]===r)return t[e-1];return-1},$.flip=function(r,n){var t=this.opposite(r,n),e=this.opposite(n,r);this.removeTriangle(r,n,t),this.removeTriangle(n,r,e),this.addTriangle(r,e,t),this.addTriangle(n,t,e)},$.edges=function(){for(var r=this.stars,n=[],t=0,e=r.length;e>t;++t)for(var a=r[t],u=0,o=a.length;o>u;u+=2)n.push([a[u],a[u+1]]);return n},$.cells=function(){for(var r=this.stars,n=[],t=0,e=r.length;e>t;++t)for(var a=r[t],u=0,o=a.length;o>u;u+=2){var i=a[u],s=a[u+1];t<Math.min(i,s)&&n.push([t,i,s])}return n};var _=o(function(r){function n(r,n){for(var t=Array(r.length-1),e=1;e<r.length;++e)for(var a=t[e-1]=Array(r.length-1),u=0,o=0;u<r.length;++u)u!==n&&(a[o++]=r[e][u]);return t}function t(r){for(var n=Array(r),t=0;r>t;++t){n[t]=Array(r);for(var e=0;r>e;++e)n[t][e]="m"+e+"["+(r-t-2)+"]"}return n}function e(r){if(1===r.length)return r[0];if(2===r.length)return"sum("+r[0]+","+r[1]+")";var n=r.length>>1;return"sum("+e(r.slice(0,n))+","+e(r.slice(n))+")"}function a(r,n){if("m"===r.charAt(0)){if("w"===n.charAt(0)){var t=r.split("[");return"w"+n.substr(1)+"m"+t[0].substr(1)}return"prod("+r+","+n+")"}return a(n,r)}function u(r){return r&!0?"-":""}function o(r){if(2===r.length)return["diff("+a(r[0][0],r[1][1])+","+a(r[1][0],r[0][1])+")"];for(var t=[],i=0;i<r.length;++i)t.push("scale("+e(o(n(r,i)))+","+u(i)+r[0][i]+")");return t}function i(r,n){for(var t=[],a=0;n-2>a;++a)t.push("prod(m"+r+"["+a+"],m"+r+"["+a+"])");return e(t)}function s(r){for(var a=[],u=[],s=t(r),f=0;r>f;++f)s[0][f]="1",s[r-1][f]="w"+f;for(var f=0;r>f;++f)0===(1&f)?a.push.apply(a,o(n(s,f))):u.push.apply(u,o(n(s,f)));for(var h=e(a),v=e(u),l="exactInSphere"+r,c=[],f=0;r>f;++f)c.push("m"+f);for(var p=["function ",l,"(",c.join(),"){"],f=0;r>f;++f){p.push("var w",f,"=",i(f,r),";");for(var g=0;r>g;++g)g!==f&&p.push("var w",f,"m",g,"=scale(w",f,",m",g,"[0]);")}p.push("var p=",h,",n=",v,",d=diff(p,n);return d[d.length-1];}return ",l);var d=Function("sum","diff","prod","scale",p.join(""));return d(L,Q,J,P)}function f(){return 0}function h(){return 0}function v(){return 0}function l(r){var n=g[r.length];return n||(n=g[r.length]=s(r.length)),n.apply(void 0,r)}function c(){for(;g.length<=p;)g.push(s(g.length));for(var n=[],t=["slow"],e=0;p>=e;++e)n.push("a"+e),t.push("o"+e);for(var a=["function testInSphere(",n.join(),"){switch(arguments.length){case 0:case 1:return 0;"],e=2;p>=e;++e)a.push("case ",e,":return o",e,"(",n.slice(0,e).join(),");");a.push("}var s=new Array(arguments.length);for(var i=0;i<arguments.length;++i){s[i]=arguments[i]};return slow(s);}return testInSphere"),t.push(a.join(""));var u=Function.apply(void 0,t);r.exports=u.apply(void 0,[l].concat(g));for(var e=0;p>=e;++e)r.exports[e]=g[e]}var p=6,g=[f,h,v];c()}),rr=_[4],nr=q,tr=k,er=C.prototype;er.locate=function(){var r=[0,0,0];return function(n,t,e){var a=n,u=t,o=e;return e>t?n>t&&(a=t,u=e,o=n):n>e&&(a=e,u=n,o=t),0>a?-1:(r[0]=a,r[1]=u,r[2]=o,H.eq(this.cells,r,F))}}();var ar=G;return ar})();
</script>
<main id="app">
<input type="file" id="sourceImg" accept="image/*" />
<div id="basic">
<span class="instructions">Click to add points to help triangulation<br />(drag a point into a corner to disable it)</span>
<div id="source-wrapper">
<canvas id="source" v-bind="size"></canvas>
<svg id="custom-points" v-bind="sizeSVG">
<drag-node v-for="(p, i) in options.customPoints" v-model="options.customPoints[i]"></drag-node>
</svg>
</div>
<svg id="low-poly" v-bind="sizeSVG" xmlns="http://www.w3.org/2000/svg" fill="currentColor" stroke="currentColor" stroke-width=".5">
<script type="text/x.poly-settings">{{ JSON.stringify(options) }}</script>
<polygon v-for="tri in triangles" :points="tri" :color="pickColor(tri)" />
</svg>
<span>
{{ triangles.length }} triangles<br />
<a href="#" @click="downloadSVG">Download SVG</a>
</span>
<span class="credit">Example photo by <a href="https://unsplash.com/@n0plex?utm_source=unsplash&amp;utm_medium=referral&amp;utm_content=creditCopyText">Daniil Lebedev</a> on <a href="https://unsplash.com/@n0plex?utm_source=unsplash&amp;utm_medium=referral&amp;utm_content=creditCopyText">Unsplash</a></span>
</div>
<details id="advanced">
<summary>Advanced</summary>
<div>
<div id="controls"></div>
<canvas id="edges" v-bind="size"></canvas>
<svg id="lines" v-bind="sizeSVG">
<g id="delaunay">
<polygon v-for="tri in triangles" :points="tri" />
</g>
<g id="polys">
<polyline v-for="(line, i) in polylines" :points="line" :style="{ stroke: debugColor(i) }" />
</g>
</svg>
</div>
</details>
</main>
Raw
script.js
(function() {
"use strict";
function log() {
const now = new Date(),
time = now.toLocaleTimeString() + '.' + now.getMilliseconds().toString().padEnd(3, '0');
console.log.apply(console, [time].concat(Array.from(arguments)));
}
function debugColor(i) {
//https://coolors.co/ffbe0b-fb5607-ff006e-8338ec-3a86ff-79ff4d
//https://learnui.design/tools/data-color-picker.html#divergent
const colors = [
[0xff, 0x00, 0x00],
[0xff, 0xff, 0x00],
[0x00, 0xff, 0x00],
[0x00, 0xff, 0xff],
[0x00, 0x00, 0xff],
[0xff, 0x00, 0xff],
];
const color = colors[i % colors.length];
return color;
}
const _state = {
options: {
canny: {
blur_radius: 4, //5,
low_threshold: 1,
high_threshold: 50, //80,
},
tracing: {
minLength: 18, //10,
lineTolerance: 4, //7,
clustering: 3,
useDelaunay: true,
},
customPoints: [[225, 0], [225, 100], [270, 88], [365, 150], [210, 195], [283, 213], [194, 248], [135, 270], [215, 355]],
},
image: {
width: 0,
height: 0,
traced: [],
},
};
//Somehow, canny calculations turn out slightly different in Firefox,
//and these settings look better on the example image:
if(navigator.userAgent.toLowerCase().includes('firefox')) {
_state.options.canny.blur_radius = 5;
_state.options.tracing.lineTolerance = 2;
_state.options.tracing.clustering = 4;
_state.options.customPoints = [[79, 0], [216, 0], [256, 0], [356, 154], [267, 148], [303, 250], [275, 190], [270, 109], [145, 285], [194, 248], [265, 345], [0, 400], [212, 169]];
}
let _img, _w, _h,
//Original image:
_ctxSource, _sourceData,
//Edge detection/tracing:
_ctx, _imageData, _data_u32, _bitmap;
function setImage(img) {
const firstImage = !_img;
_img = img;
_w = img.width;
_h = img.height;
const measure = Math.max(_w, _h);
if(measure > 600) {
const shrink = 600/measure;
_w = Math.round(_w * shrink);
_h = Math.round(_h * shrink);
}
_state.image.width = _w;
_state.image.height = _h;
if(!firstImage) {
_state.options.customPoints = [];
}
_ctx = document.querySelector('#edges').getContext("2d");
_ctxSource = document.querySelector('#source').getContext("2d");
_bitmap = new jsfeat.matrix_t(_w, _h, jsfeat.U8C1_t);
}
function setPixel(i, r, g, b) {
const alpha = 0xff << 24;
_data_u32[i] = alpha | (b << 16)| (g << 8) | r;
}
function render() {
_ctxSource.drawImage(_img, 0, 0, _w, _h);
_sourceData = _ctxSource.getImageData(0, 0, _w, _h);
const ctx = _ctx,
canny = _state.options.canny;
ctx.drawImage(_img, 0, 0, _w, _h);
_imageData = ctx.getImageData(0, 0, _w, _h);
log("grayscale");
jsfeat.imgproc.grayscale(_imageData.data, _w, _h, _bitmap);
var r = canny.blur_radius | 0;
var kernel_size = (r + 1) << 1;
log("gauss blur", r, kernel_size);
jsfeat.imgproc.gaussian_blur(_bitmap, _bitmap, kernel_size, 0);
log("canny edge");
jsfeat.imgproc.canny(
_bitmap,
_bitmap,
canny.low_threshold,
canny.high_threshold
);
// render result back to canvas
//log("render", _bitmap);
_data_u32 = new Uint32Array(_imageData.data.buffer);
let i = _bitmap.cols * _bitmap.rows,
pix = 0;
while (--i >= 0) {
pix = _bitmap.data[i] ? 160 : 0;
setPixel(i, pix, pix, pix);
}
ctx.putImageData(_imageData, 0, 0);
trace();
}
function trace() {
log('trace lines');
//Put our bitmap in a 2d grid:
const grid = [];
let i = 0;
for(let y = 0; y < _h; y++) {
const row = _bitmap.data.slice(i, i + _w);
grid.push(row);
i += _w;
}
//Trace continuous lines:
const traces = [];
for(let y = 0; y < _h; y++) {
for(let x = 0; x < _w; x++) {
const px = grid[y][x];
if(px) {
traces.push.apply(traces, _traceFrom(x, y, grid));
}
}
}
log('traced lines', traces.length); //.reduce((sum, x) => sum + x.length, 0));
const tracing = _state.options.tracing;
const importantLines = [];
traces.forEach(trace => {
if(trace.length < tracing.minLength) { return; }
//Mark pixels:
const [r, g, b] = debugColor(importantLines.length);
trace.forEach(([x, y]) => setPixel(y * _w + x, r, g, b));
importantLines.push(trace);
});
_ctx.putImageData(_imageData, 0, 0);
_state.image.traced = importantLines;
log('drawn lines', importantLines.length);
}
function _traceFrom(x_1, y_1, grid) {
//const lines = [];
const branches = [];
function checkPixel(x, y) {
return grid[y] && grid[y][x];
}
function findNext(x, y, findAll) {
const options = [];
//Check up/down/left/right first, and only diagonals if we don't find anything.
//This will let us trace "staircases" as one line, and not a series or intersections.
if(checkPixel(x, y - 1)) { options.push(tuple(x, y - 1)); }
if(checkPixel(x, y + 1)) { options.push(tuple(x, y + 1)); }
if(checkPixel(x - 1, y)) { options.push(tuple(x - 1, y)); }
if(checkPixel(x + 1, y)) { options.push(tuple(x + 1, y)); }
if(options.length && !findAll) { return options; }
if(checkPixel(x - 1, y - 1)) { options.push(tuple(x - 1, y - 1)); }
if(checkPixel(x + 1, y - 1)) { options.push(tuple(x + 1, y - 1)); }
if(checkPixel(x - 1, y + 1)) { options.push(tuple(x - 1, y + 1)); }
if(checkPixel(x + 1, y + 1)) { options.push(tuple(x + 1, y + 1)); }
return options;
}
function collect(a, b, branch) {
branch.push(tuple(a, b));
grid[b][a] = 0;
}
function addBranch(startX, startY) {
const branch = [];
collect(startX, startY, branch);
branches.push(branch);
return branch;
}
//Start by initing our main branch
addBranch(x_1, y_1);
for(let i = 0; i < branches.length; i++) {
const branch = branches[i];
let [x0, y0] = branch[0],
[x, y] = branch[branch.length - 1];
let nexts, pass = 1, endOfLine = false;
while(true) {
nexts = findNext(x, y);
//If we reach an intersection:
if((nexts.length > 1) && (branch.length > 1)) {
//This may just be a 1px branch/noise, or a small section where the edge is 2px wide.
//To test that, we look at all the pixels we can reach from the first step of a new branch.
//If there are no more pixels than we can reach from our current position,
//it's just noise and not an actual branch.
const currentReach = findNext(x, y, true);
let maxReach = -1, maxBranch, toDelete = [];
nexts = nexts.filter(([xx, yy]) => {
const branchReach = findNext(xx, yy, true),
branchHasNewPixels = branchReach.some(px => !currentReach.includes(px));
if(branchReach.length > maxReach) {
maxReach = branchReach.length;
maxBranch = tuple(xx, yy);
}
//If we decide this is just noise, clear the pixel so it's not picked up by a later traceFrom().
//Do that after this loop is finished, or else it will interfere with the other branches chance at a `maxReach`:
if(!branchHasNewPixels) { toDelete.push(tuple(xx, yy)); }
return branchHasNewPixels;
});
toDelete.forEach(([xx, yy]) => grid[yy][xx] = 0);
//If we filtered away all the branches, keep the one with more pixels.
//This lets us go around noisy corners or finish noisy line ends:
if(nexts.length === 0) { nexts = [maxBranch]; }
//This is a real intersection of branches:
if(nexts.length > 1) {
nexts.forEach(coord => {
const otherBranch = addBranch(x, y);
collect(coord[0], coord[1], otherBranch);
});
endOfLine = true;
}
}
//Keep following the current branch:
if(nexts.length && !endOfLine) {
[x, y] = nexts[0];
collect(x, y, branch);
}
else {
endOfLine = true;
}
if(endOfLine) {
if(pass === 1) {
//Reverse and trace in the other direction from our starting point;
branch.reverse();
x = x0;
y = y0;
pass = 2;
endOfLine = false;
}
else {
break;
}
}
}
}
return branches;
}
function cluster(points, tolerance) {
function avgPos(points) {
const len = points.length;
let sumX = 0, sumY = 0;
points.forEach(([x, y]) => {
sumX += x;
sumY += y;
});
return [sumX/len, sumY/len];
}
function dist2(a, b) {
const dx = a[0] - b[0],
dy = a[1] - b[1];
return dx * dx + dy * dy;
}
const clusters = [];
let pointInfos = points.map((p, i) => ({
xy: p,
//Below, we'll shrink this array of points step by step,
//so we need to keep track of all points' positions in the original array
//to report correct .pointIds at the end:
origIndex: i,
}));
//Find and combine the densest cluster of points,
//one at a time, until there are no clusters left:
const minClusterDistance2 = 4 * tolerance * tolerance;
let toRemove, failsafe = 0;
do {
toRemove = [];
failsafe++;
const newPoints = pointInfos.map(p => p.xy);
const index = new KDBush(newPoints);
const clusterCombos = new Set();
const tempClusters = newPoints.map(([x, y]) => {
const pointIds = index.within(x, y, tolerance),
population = pointIds.length;
//We get duplicates of most clusters
//(point A is right next to B, thus point B is also right next to A):
const combo = tuple(...pointIds);
if(clusterCombos.has(combo)) {
return null;
}
clusterCombos.add(combo);
//We can safely put aside clusters of population 1 (single points) right away.
//These will never be a part of any actual cluster on subsequent recalculations:
if(population === 1) {
const id = pointIds[0],
pointInfo = pointInfos[id];
toRemove.push(id);
clusters.push({
center: pointInfo.xy,
pointIds: [pointInfo.origIndex],
});
return null;
}
return { pointIds, population };
})
//Better to build a sorted array one item at a time in the loop above?
//https://stackoverflow.com/questions/1344500/efficient-way-to-insert-a-number-into-a-sorted-array-of-numbers
.filter(x => x).sort((a, b) => b.population - a.population);
//log('temp', failsafe, tempClusters);
//Now, we can combine the densest clusters into one point as long as the clusters don't overlap.
//If we find a group of overlapping clusters, we can only pick the largest one, and then recalculate.
let prevCenter;
for(const cl of tempClusters) {
const ids = cl.pointIds,
pop = cl.population,
center = avgPos(ids.map(i => newPoints[i]));
let doCombine = false;
if(prevCenter) {
const dist = dist2(center, prevCenter);
if(dist > minClusterDistance2) { doCombine = true; }
}
//This is the first and largest cluster. Always combine:
else {
doCombine = true;
}
if(!doCombine) { break; }
toRemove.push.apply(toRemove, ids);
clusters.push({
center,
pointIds: ids.map(i => pointInfos[i].origIndex),
});
prevCenter = center;
}
pointInfos = pointInfos.filter((p, i) => !toRemove.includes(i));
//log('clusters/points', clusters.length, pointInfos.length)
} while(pointInfos.length && (failsafe < 999));
return clusters;
}
function load() {
/* Edge/tracing settings */
(function controls() {
const canny = new dat.GUI({ autoPlace: false });
const cannyHeader = canny.addFolder('Canny edge detection');
cannyHeader.open();
cannyHeader.add(_state.options.canny, "blur_radius", 0, 10).step(1).onChange(render);
cannyHeader.add(_state.options.canny, "low_threshold", 1, 200).step(1).onChange(render);
cannyHeader.add(_state.options.canny, "high_threshold", 1, 200).step(1).onChange(render);
const tracing = new dat.GUI({ autoPlace: false });
const tracingHeader = tracing.addFolder('Line tracing');
tracingHeader.open();
tracingHeader.add(_state.options.tracing, "minLength", 0, 50).step(1).onChange(render);
tracingHeader.add(_state.options.tracing, "lineTolerance", 0, 10).step(1);//.onChange(trace);
tracingHeader.add(_state.options.tracing, "clustering", 0, 10).step(1);//.onChange(trace);
tracingHeader.add(_state.options.tracing, "useDelaunay").onChange(trace);
document.querySelector('#controls').insertAdjacentElement('afterbegin', tracing.domElement);
document.querySelector('#controls').insertAdjacentElement('afterbegin', canny.domElement);
})();
/* Additional points for triangulation */
const pointsPanel = document.querySelector('#custom-points');
function getSVGCoord(pos) {
//The SVGs (and canvases) are resized on small screens:
const w1 = pointsPanel.clientWidth, w2 = _state.image.width;
if(w1 && w2 && (w1 !== w2)) {
const stretch = w2 / w1;
return pos.map(xy => Math.round(xy * stretch));
}
return pos;
}
dragTracker({
container: pointsPanel,
selector: '[data-draggable]',
dragOutside: false,
callback: (node, pos) => {
//Dispatch a custom event which is handled by the node's Vue component...
var event = new CustomEvent('dragging', { detail: { pos: getSVGCoord(pos) } });
node.dispatchEvent(event);
},
});
pointsPanel.addEventListener('click', e => {
//console.log('click', e.target, e);
if(e.target === pointsPanel) {
const bounds = pointsPanel.getBoundingClientRect(),
x = event.clientX - bounds.left,
y = event.clientY - bounds.top;
_state.options.customPoints.push(getSVGCoord([x, y]));
}
})
/* Image uploading */
const img = new Image();
img.onload = e => {
setImage(img);
//Changing a canvas' size (which is done by Vue) clears its content,
//so make sure we render() *after* the size has changed:
setTimeout(() => {
render();
//Don't know why, but on a new image, it takes two renders for the result to "set":
render();
}, 0);
}
document.querySelector('#sourceImg').onchange = function(e) {
var url = URL.createObjectURL(this.files[0]);
img.src = url;
};
img.crossOrigin = "anonymous";
img.src = 'https://images.unsplash.com/photo-1589221158826-aed6c80c3f15?ixid=MXwxMjA3fDB8MHxwaG90by1wYWdlfHx8fGVufDB8fHw%3D&ixlib=rb-1.2.1&auto=format&fit=crop&w=1350&q=80';
}
Vue.component('drag-node', {
template: '<circle data-draggable @dragging="onDragging" :cx="coord[0]" :cy="coord[1]" :r="r" />',
props: {
coord: Array,
r: { default: 16 }
},
model: {
prop: 'coord',
event: 'do_it',
},
methods: {
onDragging(e) {
const point = e.detail.pos;
this.$emit('do_it', point);
},
},
});
new Vue({
el: '#app',
mounted() {
load();
},
data: _state,
computed: {
size() {
if(this.image.width) {
return { width: this.image.width, height: this.image.height };
}
},
sizeSVG() {
const size = this.size;
if(size) {
size.viewBox = [0, 0, this.image.width, this.image.height];
}
return size;
},
polylines() {
const tracing = this.options.tracing;
const polys = this.image.traced.map(trace => {
return simplify(trace, tracing.lineTolerance, true);
});
//Combine near-duplicate points:
if(tracing.clustering) {
const allPoints = polys.flatMap(poly => poly.map((xy, i) => {
return {
originalPoint: xy,
polyline: poly,
i,
};
}));
log('all', allPoints.length);
const clustered = cluster(allPoints.map(p => p.originalPoint), tracing.clustering);
log('cll', clustered.length/*, JSON.stringify(clustered.map(c => c.center))*/);
clustered.forEach(cluster => {
const center = tuple(...cluster.center);
cluster.pointIds.forEach(pointIndex => {
const pointInfo = allPoints[pointIndex],
poly = pointInfo.polyline;
if(center[0] < (pointInfo.originalPoint[0] - 50)) {
debugger
}
poly[pointInfo.i] = center;
})
})
}
return polys;
},
triangles() {
if(!this.polylines.length) { return []; }
const points = new Set(), edges = [];
this.polylines.forEach(poly => {
let p1 = tuple(...poly[0]), p2;
points.add(p1);
for(let i = 1; i < poly.length; i++) {
p2 = tuple(...poly[i]);
//The clustering of polylines may lead to a few
//back-to-back duplicate points, which we can skip:
if(p2 !== p1) {
points.add(p2);
edges.push([p1, p2]);
p1 = p2;
}
}
});
//Add helper points and corners, and then do a Constrained Delaunay triangulation:
this.options.customPoints.forEach(p => points.add(tuple(...p)));
points.add(tuple(0, 0))
.add(tuple(_w, 0))
.add(tuple(_w, _h))
.add(tuple( 0, _h));
const pointsArr = Array.from(points),
edgeIndexes = edges.map(edge => edge.map(p => pointsArr.indexOf(p)));
//console.log('cdt 2', JSON.stringify(pointsArr), JSON.stringify(edgeIndexes));
let delaunay;
try {
delaunay = cdt2d(pointsArr, edgeIndexes, { delaunay: this.options.tracing.useDelaunay });
}
catch(ex) {
//"TypeError: Cannot read property 'upperIds' of undefined"
delaunay = [];
}
const triangles = delaunay.map(tri => tri.map(i => pointsArr[i]));
log('triangles', triangles.length);
return triangles;
},
},
methods: {
debugColor(i) {
return `rgb(${debugColor(i)})`;
},
pickColor(triangle) {
const [x, y] = this.centroid(triangle).map(Math.round),
i = 4 * (y * _w + x);
const data = _sourceData.data,
r = data[i],
g = data[i + 1],
b = data[i + 2];
return `rgb(${[r, g, b]})`;
},
centroid(triangle) {
let x = 0, y = 0;
triangle.forEach(point => {
x += point[0];
y += point[1];
});
return [x/3, y/3];
},
downloadSVG(e) {
const svgContent = document.querySelector("#low-poly").outerHTML,
blob = new Blob([svgContent], {
type: "image/svg+xml"
}),
url = window.URL.createObjectURL(blob),
link = e.target;
link.target = "_blank";
link.download = "low-poly.svg";
link.href = url;
}
},
})
})();
Raw
style.scss
body {
font-family: Georgia, sans-serif;
input, button {
font: inherit
}
}
canvas, svg {
max-width: 100%;
height: auto;
}
#basic {
display: flex;
flex-flow: row wrap;
align-items: flex-end;
gap: .5em;
margin: .5em 0;
.instructions, .credit {
display: block;
width: 100%;
}
}
#source-wrapper {
position: relative;
#source {
display: block;
}
#custom-points {
position: absolute;
top:0; left:0;
[data-draggable] {
stroke: tomato;
stroke-width: 2;
fill: transparent;
cursor: move;
}
}
}
#advanced {
image-rendering: pixelated;
summary {
background: orange;
padding: .5em 1em;
}
#lines {
fill: none;
#delaunay {
fill: black;
stroke: gray;
}
#polys {
stroke-width: 2;
stroke-linecap: square;
}
}
.dg.main {
display: inline-block;
.close-button {
display: none;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment