Skip to content

Instantly share code, notes, and snippets.

@siriux

siriux/Readme.txt

Created October 22, 2018 08:55
Show Gist options
  • Save siriux/d5acb203e6ba181a17cd9da9bfa381b6 to your computer and use it in GitHub Desktop.
Save siriux/d5acb203e6ba181a17cd9da9bfa381b6 to your computer and use it in GitHub Desktop.
Download ZIP
GPU rasterizer simulator
Raw
Readme.txt
This is just to simulate and idea for a gpu algorithm to render vector curves with border and dashes.
Some code taken and modified from Pomax: https://github.com/Pomax
Raw
bezier.js
var Bezier=function(t){function n(i){if(r[i])return r[i].exports;var e=r[i]={exports:{},id:i,loaded:!1};return t[i].call(e.exports,e,e.exports,n),e.loaded=!0,e.exports}var r={};return n.m=t,n.c=r,n.p="",n(0)}([function(t,n,r){"use strict";t.exports=r(1)},function(t,n,r){"use strict";var i="function"==typeof Symbol&&"symbol"==typeof Symbol.iterator?function(t){return typeof t}:function(t){return t&&"function"==typeof Symbol&&t.constructor===Symbol&&t!==Symbol.prototype?"symbol":typeof t};!function(){function n(t,n,r,i,e){"undefined"==typeof e&&(e=.5);var o=y.projectionratio(e,t),s=1-o,u={x:o*n.x+s*i.x,y:o*n.y+s*i.y},a=y.abcratio(e,t),f={x:r.x+(r.x-u.x)/a,y:r.y+(r.y-u.y)/a};return{A:f,B:r,C:u}}var e=Math.abs,o=Math.min,s=Math.max,u=Math.cos,a=Math.sin,f=Math.acos,c=Math.sqrt,h=Math.PI,x={x:0,y:0,z:0},y=r(2),p=r(3),l=function(t){var n=t&&t.forEach?t:[].slice.call(arguments),r=!1;if("object"===i(n[0])){r=n.length;var o=[];n.forEach(function(t){["x","y","z"].forEach(function(n){"undefined"!=typeof t[n]&&o.push(t[n])})}),n=o}var s=!1,u=n.length;if(r){if(r>4){if(1!==arguments.length)throw new Error("Only new Bezier(point[]) is accepted for 4th and higher order curves");s=!0}}else if(6!==u&&8!==u&&9!==u&&12!==u&&1!==arguments.length)throw new Error("Only new Bezier(point[]) is accepted for 4th and higher order curves");var a=!s&&(9===u||12===u)||t&&t[0]&&"undefined"!=typeof t[0].z;this._3d=a;for(var f=[],c=0,h=a?3:2;c<u;c+=h){var x={x:n[c],y:n[c+1]};a&&(x.z=n[c+2]),f.push(x)}this.order=f.length-1,this.points=f;var p=["x","y"];a&&p.push("z"),this.dims=p,this.dimlen=p.length,function(t){for(var n=t.order,r=t.points,i=y.align(r,{p1:r[0],p2:r[n]}),o=0;o<i.length;o++)if(e(i[o].y)>1e-4)return void(t._linear=!1);t._linear=!0}(this),this._t1=0,this._t2=1,this.update()};l.fromSVG=function(t){var n=t.match(/[-+]?\d*\.?\d+(?:[eE][-+]?\d+)?/g).map(parseFloat),r=/[cq]/.test(t);return r?(n=n.map(function(t,r){return r<2?t:t+n[r%2]}),new l(n)):new l(n)},l.quadraticFromPoints=function(t,r,i,e){if("undefined"==typeof e&&(e=.5),0===e)return new l(r,r,i);if(1===e)return new l(t,r,r);var o=n(2,t,r,i,e);return new l(t,o.A,i)},l.cubicFromPoints=function(t,r,i,e,o){"undefined"==typeof e&&(e=.5);var s=n(3,t,r,i,e);"undefined"==typeof o&&(o=y.dist(r,s.C));var u=o*(1-e)/e,a=y.dist(t,i),f=(i.x-t.x)/a,c=(i.y-t.y)/a,h=o*f,x=o*c,p=u*f,v=u*c,d={x:r.x-h,y:r.y-x},m={x:r.x+p,y:r.y+v},g=s.A,z={x:g.x+(d.x-g.x)/(1-e),y:g.y+(d.y-g.y)/(1-e)},b={x:g.x+(m.x-g.x)/e,y:g.y+(m.y-g.y)/e},_={x:t.x+(z.x-t.x)/e,y:t.y+(z.y-t.y)/e},w={x:i.x+(b.x-i.x)/(1-e),y:i.y+(b.y-i.y)/(1-e)};return new l(t,_,w,i)};var v=function(){return y};l.getUtils=v,l.prototype={getUtils:v,valueOf:function(){return this.toString()},toString:function(){return y.pointsToString(this.points)},toSVG:function(t){if(this._3d)return!1;for(var n=this.points,r=n[0].x,i=n[0].y,e=["M",r,i,2===this.order?"Q":"C"],o=1,s=n.length;o<s;o++)e.push(n[o].x),e.push(n[o].y);return e.join(" ")},update:function(){this.dpoints=[];for(var t=this.points,n=t.length,r=n-1;n>1;n--,r--){for(var i,e=[],o=0;o<r;o++)i={x:r*(t[o+1].x-t[o].x),y:r*(t[o+1].y-t[o].y)},this._3d&&(i.z=r*(t[o+1].z-t[o].z)),e.push(i);this.dpoints.push(e),t=e}this.computedirection()},computedirection:function(){var t=this.points,n=y.angle(t[0],t[this.order],t[1]);this.clockwise=n>0},length:function(){return y.length(this.derivative.bind(this))},_lut:[],getLUT:function(t){if(t=t||100,this._lut.length===t)return this._lut;this._lut=[];for(var n=0;n<=t;n++)this._lut.push(this.compute(n/t));return this._lut},on:function(t,n){n=n||5;for(var r,i=this.getLUT(),e=[],o=0,s=0;s<i.length;s++)r=i[s],y.dist(r,t)<n&&(e.push(r),o+=s/i.length);return!!e.length&&(o/=e.length)},project:function(t){var n=this.getLUT(),r=n.length-1,i=y.closest(n,t),e=i.mdist,o=i.mpos;if(0===o||o===r){var s=o/r,u=this.compute(s);return u.t=s,u.d=e,u}var a,s,f,c,h=(o-1)/r,x=(o+1)/r,p=.1/r;for(e+=1,s=h,a=s;s<x+p;s+=p)f=this.compute(s),c=y.dist(t,f),c<e&&(e=c,a=s);return f=this.compute(a),f.t=a,f.d=e,f},get:function(t){return this.compute(t)},point:function(t){return this.points[t]},compute:function(t){if(0===t)return this.points[0];if(1===t)return this.points[this.order];var n=this.points,r=1-t;if(1===this.order)return f={x:r*n[0].x+t*n[1].x,y:r*n[0].y+t*n[1].y},this._3d&&(f.z=r*n[0].z+t*n[1].z),f;if(this.order<4){var i,e,o,s=r*r,u=t*t,a=0;2===this.order?(n=[n[0],n[1],n[2],x],i=s,e=r*t*2,o=u):3===this.order&&(i=s*r,e=s*t*3,o=r*u*3,a=t*u);var f={x:i*n[0].x+e*n[1].x+o*n[2].x+a*n[3].x,y:i*n[0].y+e*n[1].y+o*n[2].y+a*n[3].y};return this._3d&&(f.z=i*n[0].z+e*n[1].z+o*n[2].z+a*n[3].z),f}for(var c=JSON.parse(JSON.stringify(this.points));c.length>1;){for(var h=0;h<c.length-1;h++)c[h]={x:c[h].x+(c[h+1].x-c[h].x)*t,y:c[h].y+(c[h+1].y-c[h].y)*t},"undefined"!=typeof c[h].z&&(c[h]=c[h].z+(c[h+1].z-c[h].z)*t);c.splice(c.length-1,1)}return c[0]},raise:function(){for(var t,n,r,i=this.points,e=[i[0]],o=i.length,t=1;t<o;t++)n=i[t],r=i[t-1],e[t]={x:(o-t)/o*n.x+t/o*r.x,y:(o-t)/o*n.y+t/o*r.y};return e[o]=i[o-1],new l(e)},derivative:function(t){var n,r,i=1-t,e=0,o=this.dpoints[0];2===this.order&&(o=[o[0],o[1],x],n=i,r=t),3===this.order&&(n=i*i,r=i*t*2,e=t*t);var s={x:n*o[0].x+r*o[1].x+e*o[2].x,y:n*o[0].y+r*o[1].y+e*o[2].y};return this._3d&&(s.z=n*o[0].z+r*o[1].z+e*o[2].z),s},inflections:function(){return y.inflections(this.points)},normal:function(t){return this._3d?this.__normal3(t):this.__normal2(t)},__normal2:function(t){var n=this.derivative(t),r=c(n.x*n.x+n.y*n.y);return{x:-n.y/r,y:n.x/r}},__normal3:function(t){var n=this.derivative(t),r=this.derivative(t+.01),i=c(n.x*n.x+n.y*n.y+n.z*n.z),e=c(r.x*r.x+r.y*r.y+r.z*r.z);n.x/=i,n.y/=i,n.z/=i,r.x/=e,r.y/=e,r.z/=e;var o={x:r.y*n.z-r.z*n.y,y:r.z*n.x-r.x*n.z,z:r.x*n.y-r.y*n.x},s=c(o.x*o.x+o.y*o.y+o.z*o.z);o.x/=s,o.y/=s,o.z/=s;var u=[o.x*o.x,o.x*o.y-o.z,o.x*o.z+o.y,o.x*o.y+o.z,o.y*o.y,o.y*o.z-o.x,o.x*o.z-o.y,o.y*o.z+o.x,o.z*o.z],a={x:u[0]*n.x+u[1]*n.y+u[2]*n.z,y:u[3]*n.x+u[4]*n.y+u[5]*n.z,z:u[6]*n.x+u[7]*n.y+u[8]*n.z};return a},hull:function(t){var n,r=this.points,i=[],e=[],o=0,s=0,u=0;for(e[o++]=r[0],e[o++]=r[1],e[o++]=r[2],3===this.order&&(e[o++]=r[3]);r.length>1;){for(i=[],s=0,u=r.length-1;s<u;s++)n=y.lerp(t,r[s],r[s+1]),e[o++]=n,i.push(n);r=i}return e},split:function(t,n){if(0===t&&n)return this.split(n).left;if(1===n)return this.split(t).right;var r=this.hull(t),i={left:new l(2===this.order?[r[0],r[3],r[5]]:[r[0],r[4],r[7],r[9]]),right:new l(2===this.order?[r[5],r[4],r[2]]:[r[9],r[8],r[6],r[3]]),span:r};if(i.left._t1=y.map(0,0,1,this._t1,this._t2),i.left._t2=y.map(t,0,1,this._t1,this._t2),i.right._t1=y.map(t,0,1,this._t1,this._t2),i.right._t2=y.map(1,0,1,this._t1,this._t2),!n)return i;n=y.map(n,t,1,0,1);var e=i.right.split(n);return e.left},extrema:function(){var t,n,r=this.dims,i={},e=[];return r.forEach(function(r){n=function(t){return t[r]},t=this.dpoints[0].map(n),i[r]=y.droots(t),3===this.order&&(t=this.dpoints[1].map(n),i[r]=i[r].concat(y.droots(t))),i[r]=i[r].filter(function(t){return t>=0&&t<=1}),e=e.concat(i[r].sort(y.numberSort))}.bind(this)),e=e.sort(y.numberSort).filter(function(t,n){return e.indexOf(t)===n}),i.values=e,i},bbox:function(){var t=this.extrema(),n={};return this.dims.forEach(function(r){n[r]=y.getminmax(this,r,t[r])}.bind(this)),n},overlaps:function(t){var n=this.bbox(),r=t.bbox();return y.bboxoverlap(n,r)},offset:function(t,n){if("undefined"!=typeof n){var r=this.get(t),i=this.normal(t),e={c:r,n:i,x:r.x+i.x*n,y:r.y+i.y*n};return this._3d&&(e.z=r.z+i.z*n),e}if(this._linear){var o=this.normal(0),s=this.points.map(function(n){var r={x:n.x+t*o.x,y:n.y+t*o.y};return n.z&&i.z&&(r.z=n.z+t*o.z),r});return[new l(s)]}var u=this.reduce();return u.map(function(n){return n.scale(t)})},simple:function(){if(3===this.order){var t=y.angle(this.points[0],this.points[3],this.points[1]),n=y.angle(this.points[0],this.points[3],this.points[2]);if(t>0&&n<0||t<0&&n>0)return!1}var r=this.normal(0),i=this.normal(1),o=r.x*i.x+r.y*i.y;this._3d&&(o+=r.z*i.z);var s=e(f(o));return s<h/3},reduce:function(){var t,n,r=0,i=0,o=.01,s=[],u=[],a=this.extrema().values;for(a.indexOf(0)===-1&&(a=[0].concat(a)),a.indexOf(1)===-1&&a.push(1),r=a[0],t=1;t<a.length;t++)i=a[t],n=this.split(r,i),n._t1=r,n._t2=i,s.push(n),r=i;return s.forEach(function(t){for(r=0,i=0;i<=1;)for(i=r+o;i<=1+o;i+=o)if(n=t.split(r,i),!n.simple()){if(i-=o,e(r-i)<o)return[];n=t.split(r,i),n._t1=y.map(r,0,1,t._t1,t._t2),n._t2=y.map(i,0,1,t._t1,t._t2),u.push(n),r=i;break}r<1&&(n=t.split(r,1),n._t1=y.map(r,0,1,t._t1,t._t2),n._t2=t._t2,u.push(n))}),u},scale:function(t){var n=this.order,r=!1;if("function"==typeof t&&(r=t),r&&2===n)return this.raise().scale(r);var i=this.clockwise,e=r?r(0):t,o=r?r(1):t,s=[this.offset(0,10),this.offset(1,10)],u=y.lli4(s[0],s[0].c,s[1],s[1].c);if(!u)throw new Error("cannot scale this curve. Try reducing it first.");var a=this.points,f=[];return[0,1].forEach(function(t){var r=f[t*n]=y.copy(a[t*n]);r.x+=(t?o:e)*s[t].n.x,r.y+=(t?o:e)*s[t].n.y}.bind(this)),r?([0,1].forEach(function(e){if(2!==this.order||!e){var o=a[e+1],s={x:o.x-u.x,y:o.y-u.y},h=r?r((e+1)/n):t;r&&!i&&(h=-h);var x=c(s.x*s.x+s.y*s.y);s.x/=x,s.y/=x,f[e+1]={x:o.x+h*s.x,y:o.y+h*s.y}}}.bind(this)),new l(f)):([0,1].forEach(function(t){if(2!==this.order||!t){var r=f[t*n],i=this.derivative(t),e={x:r.x+i.x,y:r.y+i.y};f[t+1]=y.lli4(r,e,u,a[t+1])}}.bind(this)),new l(f))},outline:function(t,n,r,i){function e(t,n,r,i,e){return function(o){var s=i/r,u=(i+e)/r,a=n-t;return y.map(o,0,1,t+s*a,t+u*a)}}n="undefined"==typeof n?t:n;var o,s=this.reduce(),u=s.length,a=[],f=[],c=0,h=this.length(),x="undefined"!=typeof r&&"undefined"!=typeof i;s.forEach(function(o){_=o.length(),x?(a.push(o.scale(e(t,r,h,c,_))),f.push(o.scale(e(-n,-i,h,c,_)))):(a.push(o.scale(t)),f.push(o.scale(-n))),c+=_}),f=f.map(function(t){return o=t.points,o[3]?t.points=[o[3],o[2],o[1],o[0]]:t.points=[o[2],o[1],o[0]],t}).reverse();var l=a[0].points[0],v=a[u-1].points[a[u-1].points.length-1],d=f[u-1].points[f[u-1].points.length-1],m=f[0].points[0],g=y.makeline(d,l),z=y.makeline(v,m),b=[g].concat(a).concat([z]).concat(f),_=b.length;return new p(b)},outlineshapes:function(t,n,r){n=n||t;for(var i=this.outline(t,n).curves,e=[],o=1,s=i.length;o<s/2;o++){var u=y.makeshape(i[o],i[s-o],r);u.startcap.virtual=o>1,u.endcap.virtual=o<s/2-1,e.push(u)}return e},intersects:function(t,n){return t?t.p1&&t.p2?this.lineIntersects(t):(t instanceof l&&(t=t.reduce()),this.curveintersects(this.reduce(),t,n)):this.selfintersects(n)},lineIntersects:function(t){var n=o(t.p1.x,t.p2.x),r=o(t.p1.y,t.p2.y),i=s(t.p1.x,t.p2.x),e=s(t.p1.y,t.p2.y),u=this;return y.roots(this.points,t).filter(function(t){var o=u.get(t);return y.between(o.x,n,i)&&y.between(o.y,r,e)})},selfintersects:function(t){var n,r,i,e,o=this.reduce(),s=o.length-2,u=[];for(n=0;n<s;n++)i=o.slice(n,n+1),e=o.slice(n+2),r=this.curveintersects(i,e,t),u=u.concat(r);return u},curveintersects:function(t,n,r){var i=[];t.forEach(function(t){n.forEach(function(n){t.overlaps(n)&&i.push({left:t,right:n})})});var e=[];return i.forEach(function(t){var n=y.pairiteration(t.left,t.right,r);n.length>0&&(e=e.concat(n))}),e},arcs:function(t){t=t||.5;var n=[];return this._iterate(t,n)},_error:function(t,n,r,i){var o=(i-r)/4,s=this.get(r+o),u=this.get(i-o),a=y.dist(t,n),f=y.dist(t,s),c=y.dist(t,u);return e(f-a)+e(c-a)},_iterate:function(t,n){var r,i=0,e=1;do{r=0,e=1;var o,s,f,c,h,x=this.get(i),p=!1,l=!1,v=e,d=1,m=0;do{l=p,c=f,v=(i+e)/2,m++,o=this.get(v),s=this.get(e),f=y.getccenter(x,o,s),f.interval={start:i,end:e};var g=this._error(f,x,i,e);if(p=g<=t,h=l&&!p,h||(d=e),p){if(e>=1){if(f.interval.end=d=1,c=f,e>1){var z={x:f.x+f.r*u(f.e),y:f.y+f.r*a(f.e)};f.e+=y.angle({x:f.x,y:f.y},z,this.get(1))}break}e+=(e-i)/2}else e=v}while(!h&&r++<100);if(r>=100)break;c=c?c:f,n.push(c),i=d}while(e<1);return n}},t.exports=l}()},function(t,n,r){"use strict";!function(){var n=Math.abs,i=Math.cos,e=Math.sin,o=Math.acos,s=Math.atan2,u=Math.sqrt,a=Math.pow,f=function(t){return t<0?-a(-t,1/3):a(t,1/3)},c=Math.PI,h=2*c,x=c/2,y=1e-6,p=Number.MAX_SAFE_INTEGER,l=Number.MIN_SAFE_INTEGER,v={Tvalues:[-.06405689286260563,.06405689286260563,-.1911188674736163,.1911188674736163,-.3150426796961634,.3150426796961634,-.4337935076260451,.4337935076260451,-.5454214713888396,.5454214713888396,-.6480936519369755,.6480936519369755,-.7401241915785544,.7401241915785544,-.820001985973903,.820001985973903,-.8864155270044011,.8864155270044011,-.9382745520027328,.9382745520027328,-.9747285559713095,.9747285559713095,-.9951872199970213,.9951872199970213],Cvalues:[.12793819534675216,.12793819534675216,.1258374563468283,.1258374563468283,.12167047292780339,.12167047292780339,.1155056680537256,.1155056680537256,.10744427011596563,.10744427011596563,.09761865210411388,.09761865210411388,.08619016153195327,.08619016153195327,.0733464814110803,.0733464814110803,.05929858491543678,.05929858491543678,.04427743881741981,.04427743881741981,.028531388628933663,.028531388628933663,.0123412297999872,.0123412297999872],arcfn:function(t,n){var r=n(t),i=r.x*r.x+r.y*r.y;return"undefined"!=typeof r.z&&(i+=r.z*r.z),u(i)},between:function(t,n,r){return n<=t&&t<=r||v.approximately(t,n)||v.approximately(t,r)},approximately:function(t,r,i){return n(t-r)<=(i||y)},length:function(t){var n,r,i=.5,e=0,o=v.Tvalues.length;for(n=0;n<o;n++)r=i*v.Tvalues[n]+i,e+=v.Cvalues[n]*v.arcfn(r,t);return i*e},map:function(t,n,r,i,e){var o=r-n,s=e-i,u=t-n,a=u/o;return i+s*a},lerp:function(t,n,r){var i={x:n.x+t*(r.x-n.x),y:n.y+t*(r.y-n.y)};return n.z&&r.z&&(i.z=n.z+t*(r.z-n.z)),i},pointToString:function(t){var n=t.x+"/"+t.y;return"undefined"!=typeof t.z&&(n+="/"+t.z),n},pointsToString:function(t){return"["+t.map(v.pointToString).join(", ")+"]"},copy:function(t){return JSON.parse(JSON.stringify(t))},angle:function(t,n,r){var i=n.x-t.x,e=n.y-t.y,o=r.x-t.x,u=r.y-t.y,a=i*u-e*o,f=i*o+e*u;return s(a,f)},round:function(t,n){var r=""+t,i=r.indexOf(".");return parseFloat(r.substring(0,i+1+n))},dist:function(t,n){var r=t.x-n.x,i=t.y-n.y;return u(r*r+i*i)},closest:function(t,n){var r,i,e=a(2,63);return t.forEach(function(t,o){i=v.dist(n,t),i<e&&(e=i,r=o)}),{mdist:e,mpos:r}},abcratio:function(t,r){if(2!==r&&3!==r)return!1;if("undefined"==typeof t)t=.5;else if(0===t||1===t)return t;var i=a(t,r)+a(1-t,r),e=i-1;return n(e/i)},projectionratio:function(t,n){if(2!==n&&3!==n)return!1;if("undefined"==typeof t)t=.5;else if(0===t||1===t)return t;var r=a(1-t,n),i=a(t,n)+r;return r/i},lli8:function(t,n,r,i,e,o,s,u){var a=(t*i-n*r)*(e-s)-(t-r)*(e*u-o*s),f=(t*i-n*r)*(o-u)-(n-i)*(e*u-o*s),c=(t-r)*(o-u)-(n-i)*(e-s);return 0!=c&&{x:a/c,y:f/c}},lli4:function(t,n,r,i){var e=t.x,o=t.y,s=n.x,u=n.y,a=r.x,f=r.y,c=i.x,h=i.y;return v.lli8(e,o,s,u,a,f,c,h)},lli:function(t,n){return v.lli4(t,t.c,n,n.c)},makeline:function(t,n){var i=r(1),e=t.x,o=t.y,s=n.x,u=n.y,a=(s-e)/3,f=(u-o)/3;return new i(e,o,e+a,o+f,e+2*a,o+2*f,s,u)},findbbox:function(t){var n=p,r=p,i=l,e=l;return t.forEach(function(t){var o=t.bbox();n>o.x.min&&(n=o.x.min),r>o.y.min&&(r=o.y.min),i<o.x.max&&(i=o.x.max),e<o.y.max&&(e=o.y.max)}),{x:{min:n,mid:(n+i)/2,max:i,size:i-n},y:{min:r,mid:(r+e)/2,max:e,size:e-r}}},shapeintersections:function(t,n,r,i,e){if(!v.bboxoverlap(n,i))return[];var o=[],s=[t.startcap,t.forward,t.back,t.endcap],u=[r.startcap,r.forward,r.back,r.endcap];return s.forEach(function(n){n.virtual||u.forEach(function(i){if(!i.virtual){var s=n.intersects(i,e);s.length>0&&(s.c1=n,s.c2=i,s.s1=t,s.s2=r,o.push(s))}})}),o},makeshape:function(t,n,r){var i=n.points.length,e=t.points.length,o=v.makeline(n.points[i-1],t.points[0]),s=v.makeline(t.points[e-1],n.points[0]),u={startcap:o,forward:t,back:n,endcap:s,bbox:v.findbbox([o,t,n,s])},a=v;return u.intersections=function(t){return a.shapeintersections(u,u.bbox,t,t.bbox,r)},u},getminmax:function(t,n,r){if(!r)return{min:0,max:0};var i,e,o=p,s=l;r.indexOf(0)===-1&&(r=[0].concat(r)),r.indexOf(1)===-1&&r.push(1);for(var u=0,a=r.length;u<a;u++)i=r[u],e=t.get(i),e[n]<o&&(o=e[n]),e[n]>s&&(s=e[n]);return{min:o,mid:(o+s)/2,max:s,size:s-o}},align:function(t,n){var r=n.p1.x,o=n.p1.y,u=-s(n.p2.y-o,n.p2.x-r),a=function(t){return{x:(t.x-r)*i(u)-(t.y-o)*e(u),y:(t.x-r)*e(u)+(t.y-o)*i(u)}};return t.map(a)},roots:function(t,n){n=n||{p1:{x:0,y:0},p2:{x:1,y:0}};var r=t.length-1,e=v.align(t,n),s=function(t){return 0<=t&&t<=1};if(2===r){var a=e[0].y,c=e[1].y,x=e[2].y,y=a-2*c+x;if(0!==y){var p=-u(c*c-a*x),l=-a+c,d=-(p+l)/y,m=-(-p+l)/y;return[d,m].filter(s)}return c!==x&&0===y?[(2*c-x)/2*(c-x)].filter(s):[]}var g,d,z,b,_,w=e[0].y,E=e[1].y,S=e[2].y,M=e[3].y,y=-w+3*E-3*S+M,a=(3*w-6*E+3*S)/y,c=(-3*w+3*E)/y,x=w/y,e=(3*c-a*a)/3,k=e/3,O=(2*a*a*a-9*a*c+27*x)/27,T=O/2,N=T*T+k*k*k;if(N<0){var j=-e/3,I=j*j*j,A=u(I),C=-O/(2*A),F=C<-1?-1:C>1?1:C,q=o(F),U=f(A),B=2*U;return z=B*i(q/3)-a/3,b=B*i((q+h)/3)-a/3,_=B*i((q+2*h)/3)-a/3,[z,b,_].filter(s)}if(0===N)return g=T<0?f(-T):-f(T),z=2*g-a/3,b=-g-a/3,[z,b].filter(s);var G=u(N);return g=f(-T+G),d=f(T+G),[g-d-a/3].filter(s)},droots:function(t){if(3===t.length){var n=t[0],r=t[1],i=t[2],e=n-2*r+i;if(0!==e){var o=-u(r*r-n*i),s=-n+r,a=-(o+s)/e,f=-(-o+s)/e;return[a,f]}return r!==i&&0===e?[(2*r-i)/(2*(r-i))]:[]}if(2===t.length){var n=t[0],r=t[1];return n!==r?[n/(n-r)]:[]}},inflections:function(t){if(t.length<4)return[];var n=v.align(t,{p1:t[0],p2:t.slice(-1)[0]}),r=n[2].x*n[1].y,i=n[3].x*n[1].y,e=n[1].x*n[2].y,o=n[3].x*n[2].y,s=18*(-3*r+2*i+3*e-o),u=18*(3*r-i-3*e),a=18*(e-r);if(v.approximately(s,0)){if(!v.approximately(u,0)){var f=-a/u;if(0<=f&&f<=1)return[f]}return[]}var c=u*u-4*s*a,h=Math.sqrt(c),o=2*s;return v.approximately(o,0)?[]:[(h-u)/o,-(u+h)/o].filter(function(t){return 0<=t&&t<=1})},bboxoverlap:function(t,r){var i,e,o,s,u,a=["x","y"],f=a.length;for(i=0;i<f;i++)if(e=a[i],o=t[e].mid,s=r[e].mid,u=(t[e].size+r[e].size)/2,n(o-s)>=u)return!1;return!0},expandbox:function(t,n){n.x.min<t.x.min&&(t.x.min=n.x.min),n.y.min<t.y.min&&(t.y.min=n.y.min),n.z&&n.z.min<t.z.min&&(t.z.min=n.z.min),n.x.max>t.x.max&&(t.x.max=n.x.max),n.y.max>t.y.max&&(t.y.max=n.y.max),n.z&&n.z.max>t.z.max&&(t.z.max=n.z.max),t.x.mid=(t.x.min+t.x.max)/2,t.y.mid=(t.y.min+t.y.max)/2,t.z&&(t.z.mid=(t.z.min+t.z.max)/2),t.x.size=t.x.max-t.x.min,t.y.size=t.y.max-t.y.min,t.z&&(t.z.size=t.z.max-t.z.min)},pairiteration:function(t,n,r){var i=t.bbox(),e=n.bbox(),o=1e5,s=r||.5;if(i.x.size+i.y.size<s&&e.x.size+e.y.size<s)return[(o*(t._t1+t._t2)/2|0)/o+"/"+(o*(n._t1+n._t2)/2|0)/o];var u=t.split(.5),a=n.split(.5),f=[{left:u.left,right:a.left},{left:u.left,right:a.right},{left:u.right,right:a.right},{left:u.right,right:a.left}];f=f.filter(function(t){return v.bboxoverlap(t.left.bbox(),t.right.bbox())});var c=[];return 0===f.length?c:(f.forEach(function(t){c=c.concat(v.pairiteration(t.left,t.right,s))}),c=c.filter(function(t,n){return c.indexOf(t)===n}))},getccenter:function(t,n,r){var o,u=n.x-t.x,a=n.y-t.y,f=r.x-n.x,c=r.y-n.y,y=u*i(x)-a*e(x),p=u*e(x)+a*i(x),l=f*i(x)-c*e(x),d=f*e(x)+c*i(x),m=(t.x+n.x)/2,g=(t.y+n.y)/2,z=(n.x+r.x)/2,b=(n.y+r.y)/2,_=m+y,w=g+p,E=z+l,S=b+d,M=v.lli8(m,g,_,w,z,b,E,S),k=v.dist(M,t),O=s(t.y-M.y,t.x-M.x),T=s(n.y-M.y,n.x-M.x),N=s(r.y-M.y,r.x-M.x);return O<N?((O>T||T>N)&&(O+=h),O>N&&(o=N,N=O,O=o)):N<T&&T<O?(o=N,N=O,O=o):N+=h,M.s=O,M.e=N,M.r=k,M},numberSort:function(t,n){return t-n}};t.exports=v}()},function(t,n,r){"use strict";!function(){var n=r(2),i=function(t){this.curves=[],this._3d=!1,t&&(this.curves=t,this._3d=this.curves[0]._3d)};i.prototype={valueOf:function(){return this.toString()},toString:function(){return"["+this.curves.map(function(t){return n.pointsToString(t.points)}).join(", ")+"]"},addCurve:function(t){this.curves.push(t),this._3d=this._3d||t._3d},length:function(){return this.curves.map(function(t){return t.length()}).reduce(function(t,n){return t+n})},curve:function(t){return this.curves[t]},bbox:function t(){for(var r=this.curves,t=r[0].bbox(),i=1;i<r.length;i++)n.expandbox(t,r[i].bbox());return t},offset:function t(n){var t=[];return this.curves.forEach(function(r){t=t.concat(r.offset(n))}),new i(t)}},t.exports=i}()}]);
Raw
draw.js
function createDrawElement(w, h) {
var cvs = document.createElement("canvas");
cvs.width = w;
cvs.height = h;
var ctx = cvs.getContext("2d");
var randomColors = [];
for(var i=0,j; i<360; i++) {
j = (i*47)%360;
randomColors.push("hsl("+j+",50%,50%)");
}
var randomIndex = 0;
return {
getCanvas: function() { return cvs; },
reset: function(curve, evt) {
cvs.width = cvs.width;
ctx.strokeStyle = "black";
ctx.fillStyle = "none";
if (evt && curve) {
curve.mouse = {x: evt.offsetX, y: evt.offsetY};
}
randomIndex = 0;
},
setColor: function(c) {
ctx.strokeStyle = c;
},
noColor: function(c) {
ctx.strokeStyle = "transparent";
},
setRandomColor: function() {
randomIndex = (randomIndex+1) % randomColors.length;
var c = randomColors[randomIndex];
ctx.strokeStyle = c;
},
setRandomFill: function(a) {
randomIndex = (randomIndex+1) % randomColors.length;
a = (typeof a === "undefined") ? 1 : a;
var c = randomColors[randomIndex];
c = c.replace('hsl(','hsla(').replace(')',','+a+')');
ctx.fillStyle = c;
},
setFill: function(c) {
ctx.fillStyle = c;
},
noFill: function() {
ctx.fillStyle = "transparent";
},
drawSkeleton: function(curve, offset, nocoords) {
offset = offset || { x:0, y:0 };
var pts = curve.points;
//ctx.strokeStyle = "lightgrey";
this.drawLine(pts[0], pts[1], offset);
if(pts.length === 3) { this.drawLine(pts[1], pts[2], offset); }
else {this.drawLine(pts[2], pts[3], offset); }
//ctx.strokeStyle = "black";
if(!nocoords) this.drawPoints(pts, offset);
},
drawCurve: function(curve, offset) {
offset = offset || { x:0, y:0 };
var ox = offset.x;
var oy = offset.y;
ctx.beginPath();
var p = curve.points, i;
ctx.moveTo(p[0].x + ox, p[0].y + oy);
if(p.length === 3) {
ctx.quadraticCurveTo(
p[1].x + ox, p[1].y + oy,
p[2].x + ox, p[2].y + oy
);
}
if(p.length === 4) {
ctx.bezierCurveTo(
p[1].x + ox, p[1].y + oy,
p[2].x + ox, p[2].y + oy,
p[3].x + ox, p[3].y + oy
);
}
ctx.stroke();
ctx.closePath();
},
drawLine: function(p1, p2, offset) {
offset = offset || { x:0, y:0 };
var ox = offset.x;
var oy = offset.y;
ctx.beginPath();
ctx.moveTo(p1.x + ox,p1.y + oy);
ctx.lineTo(p2.x + ox,p2.y + oy);
ctx.stroke();
},
drawPoint: function(p, offset) {
offset = offset || { x:0, y:0 };
var ox = offset.x;
var oy = offset.y;
ctx.beginPath();
ctx.arc(p.x + ox, p.y + oy, 5, 0, 2*Math.PI);
ctx.stroke();
},
drawPoints: function(points, offset) {
offset = offset || { x:0, y:0 };
points.forEach(function(p) {
this.drawCircle(p, 3, offset);
}.bind(this));
},
drawArc: function(p, offset) {
offset = offset || { x:0, y:0 };
var ox = offset.x;
var oy = offset.y;
ctx.beginPath();
ctx.moveTo(p.x + ox, p.y + oy);
ctx.arc(p.x + ox, p.y + oy, p.r, p.s, p.e);
ctx.lineTo(p.x + ox, p.y + oy);
ctx.fill();
ctx.stroke();
},
drawCircle: function(p, r, offset) {
offset = offset || { x:0, y:0 };
var ox = offset.x;
var oy = offset.y;
ctx.beginPath();
ctx.arc(p.x + ox, p.y + oy, r, 0, 2*Math.PI);
ctx.stroke();
},
drawbbox: function(bbox, offset) {
offset = offset || { x:0, y:0 };
var ox = offset.x;
var oy = offset.y;
ctx.beginPath();
ctx.moveTo(bbox.x.min + ox, bbox.y.min + oy);
ctx.lineTo(bbox.x.min + ox, bbox.y.max + oy);
ctx.lineTo(bbox.x.max + ox, bbox.y.max + oy);
ctx.lineTo(bbox.x.max + ox, bbox.y.min + oy);
ctx.closePath();
ctx.stroke();
},
drawHull: function(hull, offset) {
ctx.beginPath();
if(hull.length === 6) {
ctx.moveTo(hull[0].x, hull[0].y);
ctx.lineTo(hull[1].x, hull[1].y);
ctx.lineTo(hull[2].x, hull[2].y);
ctx.moveTo(hull[3].x, hull[3].y);
ctx.lineTo(hull[4].x, hull[4].y);
} else {
ctx.moveTo(hull[0].x, hull[0].y);
ctx.lineTo(hull[1].x, hull[1].y);
ctx.lineTo(hull[2].x, hull[2].y);
ctx.lineTo(hull[3].x, hull[3].y);
ctx.moveTo(hull[4].x, hull[4].y);
ctx.lineTo(hull[5].x, hull[5].y);
ctx.lineTo(hull[6].x, hull[6].y);
ctx.moveTo(hull[7].x, hull[7].y);
ctx.lineTo(hull[8].x, hull[8].y);
}
ctx.stroke();
},
drawShape: function(shape, offset) {
offset = offset || { x:0, y:0 };
var order = shape.forward.points.length - 1;
ctx.beginPath();
ctx.moveTo(offset.x + shape.startcap.points[0].x, offset.y + shape.startcap.points[0].y);
ctx.lineTo(offset.x + shape.startcap.points[3].x, offset.y + shape.startcap.points[3].y);
if(order === 3) {
ctx.bezierCurveTo(
offset.x + shape.forward.points[1].x, offset.y + shape.forward.points[1].y,
offset.x + shape.forward.points[2].x, offset.y + shape.forward.points[2].y,
offset.x + shape.forward.points[3].x, offset.y + shape.forward.points[3].y
);
} else {
ctx.quadraticCurveTo(
offset.x + shape.forward.points[1].x, offset.y + shape.forward.points[1].y,
offset.x + shape.forward.points[2].x, offset.y + shape.forward.points[2].y
);
}
ctx.lineTo(offset.x + shape.endcap.points[3].x, offset.y + shape.endcap.points[3].y);
if(order === 3) {
ctx.bezierCurveTo(
offset.x + shape.back.points[1].x, offset.y + shape.back.points[1].y,
offset.x + shape.back.points[2].x, offset.y + shape.back.points[2].y,
offset.x + shape.back.points[3].x, offset.y + shape.back.points[3].y
);
} else {
ctx.quadraticCurveTo(
offset.x + shape.back.points[1].x, offset.y + shape.back.points[1].y,
offset.x + shape.back.points[2].x, offset.y + shape.back.points[2].y
);
}
ctx.closePath();
ctx.fill();
ctx.stroke();
},
drawText: function(text, offset) {
offset = offset || { x:0, y:0 };
ctx.fillText(text, offset.x, offset.y);
}
};
}
Raw
index.html
<!DOCTYPE html>
<html lang="en" style="height: 100%;">
<head>
<title>Test</title>
<script type="text/javascript" src="bezier.js"></script>
<script type="text/javascript" src="draw.js"></script>
<script type="text/javascript" src="interaction.js"></script>
</head>
<body style="position:absolute; top:0; bottom:0; right:0; left:0;">
<script type="text/javascript">
var utils = Bezier.getUtils();
var w = document.body.offsetWidth;
var h = document.body.offsetHeight;
// var normScreenParams = {s: 200, tx: 200, ty: h/2};
var distance = 100;
//var curve = new Bezier(600, 50, 655, 70, 700, 50);
//var curve = new Bezier(600, 50, 1260, 51, 1500, 50);
var curve = [{x:800, y:500}, {x: 900, y:550}, {x:1000, y:500}];
//var curve = new Bezier(800, 500, 860, 450, 1000, 500);
var pixel = {center: {x: 0, y:0}};
function isOnTheRight(l0, l1, p) {
// Is p on the right side of the line from l0 to l1 ???
return ((l1.x - l0.x)*(p.y - l0.y) - (l1.y - l0.y)*(p.x - l0.x)) < 0;
}
function isReversed(c) {
return isOnTheRight(c[0], c[2], c[1]);
}
function isSimple(c) {
//return c.simple();
c = c;
// Standard version calculating the real angle
var v1 = {x: c[0].x - c[1].x, y: c[0].y - c[1].y};
var v2 = {x: c[2].x - c[1].x, y: c[2].y - c[1].y};
var v1l = Math.sqrt(v1.x*v1.x + v1.y*v1.y);
var v2l = Math.sqrt(v2.x*v2.x + v2.y*v2.y);
var v1n = {x: v1.x/v1l, y: v1.y/v1l};
var v2n = {x: v2.x/v2l, y: v2.y/v2l};
var v1v2 = v1n.x*v2n.x + v1n.y*v2n.y; // Cos of angle between vectors (Dot product)
//var greater90 = v1v2 < 0; // > 1/2PI == 90
var greater120 = v1v2 < -0.5; // > 2/3PI == 120
// Angle on control point > 90
// Optimized version that test if the triangle is obtuse using pythagoras theorem
// https://en.wikipedia.org/wiki/Pythagorean_theorem#Converse
var l1 = {x: c[0].x - c[1].x, y: c[0].y - c[1].y};
var l2 = {x: c[2].x - c[1].x, y: c[2].y - c[1].y};
var l3 = {x: c[2].x - c[0].x, y: c[2].y - c[0].y};
var m12 = l1.x*l1.x + l1.y*l1.y;
var m22 = l2.x*l2.x + l2.y*l2.y;
var m32 = l3.x*l3.x + l3.y*l3.y;
var obtuse = m12 + m22 < m32;
// Control point is near the middle (outside of extreme quaters)
var v = {x: (c[2].x - c[0].x) / 4, y: (c[2].y - c[0].y) / 4}
var q1p1 = {x: c[0].x + v.x, y: c[0].y + v.y };
var q1p2 = {x: q1p1.x - v.y, y: q1p1.y + v.x };
var isCenteredOnRight = isOnTheRight(q1p1, q1p2, c[1]);
var q2p1 = {x: c[2].x - v.x, y: c[2].y - v.y };
var q2p2 = {x: q2p1.x - v.y, y: q2p1.y + v.x };
var isCenteredOnLeft = !isOnTheRight(q2p1, q2p2, c[1]);
return greater120 && isCenteredOnRight && isCenteredOnLeft;
//return obtuse && isCenteredOnRight && isCenteredOnLeft;
}
function split(c, t) {
// TODO Avoid bezier.js
var s = (new Bezier(c)).split(t);
return {left: s.left.points, right: s.right.points};
}
function reduce(c) {
// return c.reduce();
if (isSimple(c)) {
return [c];
} else {
//var s = c.split(0.5);
//return reduce(s.left).concat(reduce(s.right));
function findSimpleRec(c, t) {
//return isSimple(c.split(t).left ? t : findSimpleRec(c, t/2);
var s = split(c, t);
if (isSimple(s.left)) {
return t;
} else {
return findSimpleRec(c, t/2);
}
}
var current = c;
var curves = [];
while (!isSimple(current)) {
var t = findSimpleRec(current, 0.5);
var s = split(current, t);
curves.push(s.left);
current = s.right;
}
curves.push(current);
return curves;
}
}
function scale(s, d) {
//return s.scale(d);
var p0 = s[0];
var p1 = s[1];
var p2 = s[2];
var np = [];
// Tangents
var t0 = {x: p1.x - p0.x, y: p1.y - p0.y};
var mt0 = Math.sqrt(t0.x*t0.x + t0.y*t0.y);
t0 = {x: t0.x/mt0, y: t0.y/mt0};
var t1 = {x: p2.x - p1.x, y: p2.y - p1.y};
var mt1 = Math.sqrt(t1.x*t1.x + t1.y*t1.y);
t1 = {x: t1.x/mt1, y: t1.y/mt1};
// Normals
var n0 = {x: -t0.y, y: t0.x};
var n1 = {x: -t1.y, y: t1.x};
np[0] = {x: p0.x + d * n0.x, y: p0.y + d * n0.y};
np[2] = {x: p2.x + d * n1.x, y: p2.y + d * n1.y};
var od0 = {x: np[0].x + t0.x, y: np[0].y + t0.y};
var od1 = {x: np[2].x + t1.x, y: np[2].y + t1.y};
function lineIntersection(x1,y1,x2,y2,x3,y3,x4,y4) {
var nx=(x1*y2-y1*x2)*(x3-x4)-(x1-x2)*(x3*y4-y3*x4),
ny=(x1*y2-y1*x2)*(y3-y4)-(y1-y2)*(x3*y4-y3*x4),
d=(x1-x2)*(y3-y4)-(y1-y2)*(x3-x4);
if(d==0) {
return {x: (x2+x4)/2, y: (y2+y4)/2}; // Middle point
} else {
return {x: nx/d, y: ny/d};
}
}
np[1] = lineIntersection(np[0].x, np[0].y, od0.x, od0.y, np[2].x, np[2].y, od1.x, od1.y);
return np;
}
function calcAreaForPx(p10_x, p10_y, p11_x, p11_y, p12_x, p12_y,
p20_x, p20_y, p21_x, p21_y, p22_x, p22_y,
pixel_x, pixel_y,
bezierLength, curveProportions, segmentLength, segmentOffset,
reversedInternalBorder) {
// segmentLength and segmentOffset are relative to the t parameter (1 means whole curve)
// Find the t values for the cut points of the curves with the line between o and px
// Align -> Rotate to make the line the vertical axis (only calculate x coord)
// Calculate t for x=0
// Note: We don't normalize the line vector, as the scaled curve will cut at the same point
// Still, the direction of the vector is important and should point towards the curve.
// In practice is not needed because these cases are avoided.
// Note: All the curve points and the pixel use the origin point as the base. This saves calculations and parameters.
// We need 48 simple ops (taking MAD into account)
// to calculate the ts, points and normals (not including dashed)
// And 22 for the interseccion most common case.
// This is ~92 in the most common case of a simple border
// Align the points to the pixel vector (from o to the current pixel)
// Then find the t value for x = 0
// Then calculate the cut points and tangents
var ap10 = p10_x*pixel_y - p10_y*pixel_x;
var ap11 = p11_x*pixel_y - p11_y*pixel_x;
var ap12 = p12_x*pixel_y - p12_y*pixel_x;
var t1 = ap10 / (ap10 - ap11 - Math.sqrt(ap11*ap11 - ap10*ap12));
// TODO Maybe extract the parts not depending on t1 first to give time to the previous sqrt and /
var lerp11_x = p10_x + t1*(p11_x - p10_x);
var lerp12_x = p11_x + t1*(p12_x - p11_x);
var tan1_x = lerp12_x - lerp11_x;
var cP1_x = lerp11_x + t1*tan1_x;
var lerp11_y = p10_y + t1*(p11_y - p10_y);
var lerp12_y = p11_y + t1*(p12_y - p11_y);
var tan1_y = lerp12_y - lerp11_y;
var cP1_y = lerp11_y + t1*tan1_y;
/*
var cP1_ax = p10_x - 2*p11_x + p12_x;
var cP1_bx = p11_x - p10_x;
var cP1_ay = p10_y - 2*p11_y + p12_y;
var cP1_by = p11_y - p10_y;
var halftan1_x = cP1_ax*t1 + cP1_bx;
var halftan1_y = cP1_ay*t1 + cP1_by;
var cP1_x = (halftan1_x + cP1_bx)*t1 + p10_x;
var cP1_y = (halftan1_y + cP1_by)*t1 + p10_y;
var tan1_x = 2*halftan1_x;
var tan1_y = 2*halftan1_y;
*/
var ap20 = p20_x*pixel_y - p20_y*pixel_x;
var ap21 = p21_x*pixel_y - p21_y*pixel_x;
var ap22 = p22_x*pixel_y - p22_y*pixel_x;
var t2 = ap20 / (ap20 - ap21 - Math.sqrt(ap21*ap21 - ap20*ap22));
var lerp21_x = p20_x + t2*(p21_x - p20_x);
var lerp22_x = p21_x + t2*(p22_x - p21_x);
var tan2_x = lerp22_x - lerp21_x;
var cP2_x = lerp21_x + t2*tan2_x;
var lerp21_y = p20_y + t2*(p21_y - p20_y);
var lerp22_y = p21_y + t2*(p22_y - p21_y);
var tan2_y = lerp22_y - lerp21_y;
var cP2_y = lerp21_y + t2*tan2_y
/*
var cP2_ax = p20_x - 2*p21_x + p22_x;
var cP2_bx = p21_x - p20_x;
var cP2_ay = p20_y - 2*p21_y + p22_y;
var cP2_by = p21_y - p20_y;
var halftan2_x = cP2_ax*t2 + cP2_bx;
var halftan2_y = cP2_ay*t2 + cP2_by;
var cP2_x = (halftan2_x + cP2_bx)*t2 + p20_x;
var cP2_y = (halftan2_y + cP2_by)*t2 + p20_y;
var tan2_x = 2*halftan2_x;
var tan2_y = 2*halftan2_y;
*/
// Intersect curves with pixel
// TODO Displace the tangent depending on curvature to have smaller error
var area1 = intersectLineAndPixel(cP1_x, cP1_y, tan1_x, tan1_y, pixel_x, pixel_y);
var area2 = intersectLineAndPixel(cP2_x, cP2_y, tan2_x, tan2_y, pixel_x, pixel_y);
// TODO Optimize: In this situation we don't need to calculate anything related to c1
if (reversedInternalBorder) {
area1 = 0;
}
var borderArea = area2 - area1;
// Calculate the dashed area
var dashedArea = 1;
if (true) {
var tn;
if (reversedInternalBorder) {
// Special case to avoid the problems of the reversed internal border
tn = t2;
} else {
// Interpolate normals
// We don't normalize the distances or the tangents because we only care about ratio
// And the approximation is good enough
var d1 = -(tan1_x*(pixel_x - cP1_x) + tan1_y*(pixel_y - cP1_y)); // Distance from the pixel to the normal line on t1
var d2 = tan2_x*(pixel_x - cP2_x) + tan2_y*(pixel_y - cP2_y); // Distance from the pixel to the normal line on t2
var iFactor = d1 / (d1+d2);
if (iFactor < 0) { iFactor = 1; } // This is realy important, simple clamp creates many more artifacts !!!
// Note: There are still some artifacts due to the interpolation, but really small, so we stop here
// Problems seem to appear when the normals cross, but the trick above works really well
// var curve = new Bezier(600, 50, 655, 70, 700, 50);
// var distance = 600;
var inx = -(tan1_y*(1-iFactor) + tan2_y*iFactor);
var iny = tan1_x*(1-iFactor) + tan2_x*iFactor;
// Find cut point of the interpolated normal
// Interpolated normal {p1: px, p2: {x: px.x + inx, y: px.y + iny}}
var pn0 = (p20_x - pixel_x)*iny - (p20_y - pixel_y)*inx;
var pn1 = (p21_x - pixel_x)*iny - (p21_y - pixel_y)*inx;
var pn2 = (p22_x - pixel_x)*iny - (p22_y - pixel_y)*inx;
tn = pn0 / (pn0 - pn1 - Math.sqrt(pn1*pn1 - pn0*pn2));
}
if (tn > 0 && tn < 1) {
// Segmented border, with cheap AA
// IMPORTANT !! alpha can be outside [0,1], clamp if needed !!!!
// Corrention to have aprox equal length segments
// based on a flat bezier with extremes on (0,0) and (1,0) and control on (tc,0)
// curveProportions is the proportion of the sides of the triangle that touch the control point
// NOTE: tc is constant on the whole curve, we don't need to recalculate per pixel
// Alternative (worse) correction based on the idea of gamma
// var tc = (l1 / (l0 + l1)) + 0.5;
// t = Math.pow(t, tc);
var t = (2*curveProportions + (1 - 2*curveProportions)*tn)*tn;
var change = ((t+segmentOffset) / segmentLength) % 2; // Position with respect to change:[0, 2) with change at 1 and 2
var d1 = 1 - change; // Distance to 1, the change from black to white
var d2 = 2 - change; // distance to 2, the change from white to black
var pixelSizeInv = bezierLength*segmentLength; // With respect to d1 and d2, where a segment measures 1
// This is the inverse to avoid the two divisions
// NOTE: We can make pixelSizeInv smaller to get blurrier edges (divide by 2)
dashedArea = (d1 > 0) ? d1*pixelSizeInv : 1 - d2*pixelSizeInv; // Here we get the gradients for AA if distances are closer than 1px
// Of they are larger, we get values greater than 1 or lower than 0
// clamp
if (dashedArea < 0) {dashedArea = 0}
if (dashedArea > 1) {dashedArea = 1}
}
}
return borderArea * dashedArea;
}
function intersectLineAndPixel(p_x, p_y, tan_x, tan_y, pixel_x, pixel_y) {
// Most common case ~22 simple ops (taking into account MAD)
// Line defined by point p and vector tan
// Pixel center at px
// Reversed can be 1 or -1 to indicate the area we need
// Optimized calculations, see below for the detailed calculations
const sqrt2 = 1.41421356237;
const halfsqrt2 = 0.70710678119; // Also Sin and Cos of 45 degrees
// Change the origin to the pixel
var opx = p_x - pixel_x;
var opy = p_y - pixel_y;
// Rotate 45 degrees
// The halfsqrt2 has been factored out and propagated
var px = opx - opy;
var py = opx + opy;
var tx = tan_x - tan_y;
var ty = tan_x + tan_y;
// TODO Rotate and scale line when the object is transformed
// Maybe just scale point and rotate tangent ???
// Aux intermediate variables
var abslx = Math.abs(ty);
var absly = Math.abs(tx);
var abslw = Math.abs(px*ty - py*tx);
// Situations and areas depending on positions of A and B
var area;
var not_parallel_x = abslx != 0; // Not parallel to x
var not_parallel_y = absly != 0; // Not parallel to y
var not_parallel = not_parallel_x && not_parallel_y;
var aout = abslx < abslw; // A inside the square; Alternate form ((0.5*abslw)/(abslx*halfsqrt2)) > halfsqrt2
var bout = absly < abslw; // B inside the square; Alternate form ((0.5*abslw)/(absly*halfsqrt2)) > halfsqrt2
// Optimized for the most common case, both out
if (not_parallel && aout && bout) {
area = 0;
} else {
// Line AB
var halfabslw = abslw*0.5;
var abx = -abslx*halfabslw*halfsqrt2;
var aby = -halfabslw*absly*halfsqrt2;
var abw = halfabslw*halfabslw;
// Aux intermediate variables
var sqrt2abw = sqrt2*abw;
var sqrt2abx = sqrt2*abx;
var sqrt2aby = sqrt2*aby;
var wpx = sqrt2abw + abx;
var wmx = sqrt2abw - abx;
var wpy = sqrt2abw + aby;
var wmy = sqrt2abw - aby;
var xpy = sqrt2abx + sqrt2aby;
var xmy = sqrt2abx - sqrt2aby;
if (not_parallel) {
var halfsqrt2xpy = halfsqrt2/xpy; // Aux
if (aout || bout) { // Only one out
area = aout ? -(wpy*wpy)/(xmy*xpy) : halfsqrt2xpy*wpx*(sqrt2*wpy/xmy + 1);
} else { // Both inside
if (abslw != 0) {
area = Math.abs(halfsqrt2xpy*(wpx+wpy));
} else {
// If abslw == 0 A and B are on the center and the calculations are wrong
// Fortunately this case is simple, it's always half the area
area = 0.5;
}
}
} else { // Parallel
area = (not_parallel_y ? wpy*wpy : wmy*wmy) / (xpy*xpy);
}
}
// Reverse the area if needed based on the original line
// Calculates is the pixel is on the right side of the original line
if ((tan_y*opx - tan_x*opy) < 0) {
area = 1 - area;
}
return area;
/* Detailed calculations
// Change the origin to the pixel
var opx = p_x - pixel_x;
var opy = p_y - pixel_y;
// Rotate 45 degrees
var px = (opx - opy) * halfsqrt2;
var py = (opx + opy) * halfsqrt2;
var tx = (tan_x - tan_y) * halfsqrt2;
var ty = (tan_x + tan_y) * halfsqrt2;
// Intersect with axes in homogeneus coordinates
// horizontal axis: (0, 1, 0) <- from points (0,0,1);(1,0,1)
// vertical axis: (1, 0, 0) <- from points (0,0,1);(0,1,1)
var lx = -ty;
var ly = tx;
var lw = px*ty - py*tx;
// Horizontal (A) and Vertical (B) intersections
// Moved to first quadrant with absolute values
var ax = Math.abs(lw);
var ay = 0;
var aw = Math.abs(-lx);
var bx = 0;
var by = Math.abs(-lw);
var bw = Math.abs(ly);
// Situations depending on positions of A and B
var s1 = aw < 0.0001; // Horizontal line
var s2 = bw < 0.0001; // Vertical line
var s3 = (ax/aw) > halfsqrt2 && (by/bw) > halfsqrt2; // A and B are outside
var s4 = (ax/aw) < halfsqrt2 && (by/bw) < halfsqrt2; // A and B are inside
var s5 = (ax/aw) > halfsqrt2 && (by/bw) < halfsqrt2; // A ouside and B inside
var s6 = (ax/aw) < halfsqrt2 && (by/bw) > halfsqrt2; // A inside and B outside
// Create the line AB
var abx = -aw*by;
var aby = -ax*bw;
var abw = ax*by;
// Optimized line AB
var abslw = Math.abs(px*ty - py*tx);
var abx = -Math.abs(ty)*abslw;
var aby = -abslw*Math.abs(tx);
var abw = abslw*abslw;
// Intersect AB with 3 sides of the square (rotated 45 degres) to get the C points
// side 1: (-halfsqrt2, halfsqrt2, -1/2) <- from points (-halfsqrt2,0,1);(0,halfsqrt2,1)
// side 2: (halfsqrt2, halfsqrt2, -1/2) <- from points (0,halfsqrt2,1);(halfsqrt2,0,1)
// side 3: (halfsqrt2, -halfsqrt2, -1/2) <- from points (halfsqrt2,0,1);(0,-halfsqrt2,1)
var c1x = -halfsqrt2*abw - 0.5*aby;
var c1y = -halfsqrt2*abw + 0.5*abx;
var c1w = halfsqrt2*abx + halfsqrt2*aby;
var c2x = -halfsqrt2*abw - 0.5*aby;
var c2y = halfsqrt2*abw + 0.5*abx;
var c2w = halfsqrt2*abx - halfsqrt2*aby;
var c3x = halfsqrt2*abw - 0.5*aby;
var c3y = halfsqrt2*abw + 0.5*abx;
var c3w = -halfsqrt2*abx - halfsqrt2*aby;
// Calculate the lengths of the C points
// l1 and l2 with respect to (0,halfsqrt2) and l3 with respect to (halfsqrt2,0)
// Makes use of the third point in https://en.wikipedia.org/wiki/Triangle#Right_triangles
// Can divide by zero, but in that case the result won't be used later
var l1 = -(c1x/c1w)*sqrt2;
var l2 = (c2x/c2w)*sqrt2;
var l3 = -(c3y/c3w)*sqrt2;
// Areas
var t_parallel_x = (c1x/c1w)*(c1x/c1w);
var t_parallel_y = (c3y/c3w)*(c3y/c3w);
var t_x_outside = (l1*l2)/2;
var t_y_outside = ((1-l2)*l3)/2;
var t_both_inside = Math.abs(l1 + (l3 - l1)/2);
*/
}
function calcDashedParameters(c, length, offset) {
var p0 = c[0];
var p1 = c[1];
var p2 = c[2];
var l0 = Math.sqrt((p1.x - p0.x)*(p1.x - p0.x) + (p1.y - p0.y)*(p1.y - p0.y));
var l1 = Math.sqrt((p2.x - p1.x)*(p2.x - p1.x) + (p2.y - p1.y)*(p2.y - p1.y));
var l2 = Math.sqrt((p0.x - p2.x)*(p0.x - p2.x) + (p0.y - p2.y)*(p0.y - p2.y));
var bezierLength = (l0 + l1 + 2*l2) / 3; // Approximate bezier length
var curveProportions = l0 / (l0 + l1); // Curve side proportions for the t parameter correction
return {
bezierLength: bezierLength,
curveProportions: curveProportions,
segmentLength: length / bezierLength, // With respect to t
segmentOffset: offset / bezierLength, // With respect to t
nextSegmentOffset: offset + bezierLength // Total offset in pixels
}
}
var api = createDrawElement(w, h);
var cvs = api.getCanvas();
var context = cvs.getContext("2d");
document.body.appendChild(cvs);
var handler = handleInteraction(cvs, curve);
document.body.addEventListener("keydown", function(evt) {
var delta = 1;
if (!!evt.shiftKey) {
delta = 10;
}
if (!!evt.ctrlKey) {
delta = 0.1;
}
if (evt.keyCode == 37) {
distance -= delta;
}
if (evt.keyCode == 39) {
distance += delta;
}
handler.onupdate(evt);
});
function drawCircle(p, r, o, c) {
api.setColor(c);
context.lineWidth = o;
api.drawCircle(p, r);
context.lineWidth = 1;
}
handler.onupdate = function(evt) {
var borderFill = evt ? evt.keyCode == 70 : false;
api.reset();
// Change the coordinate system to "normal"
// can break text !!!!!!!
// There is a change in the fix function of interection
context.translate(0, h);
context.scale(1, -1);
function drawCurve(c1, c2, color, dashedParameters) {
// Origin
// FIXME Lines can be parallel, use homogeneous coordinates for o !
// This can be used to detect if the curve is a line on the shader
var o = utils.lli4(c1[0], c2[0], c1[2], c2[2]); // TODO Replace with custom function
// Find if the origin is between c1 and c2 using the squares of the lengths
var x12 = c1[0].x - c2[0].x;
var y12 = c1[0].y - c2[0].y;
var l12 = x12*x12 + y12*y12;
var xo2 = o.x - c2[0].x;
var yo2 = o.y - c2[0].y;
var lo2 = xo2*xo2 + yo2*yo2;
var reversedInternalBorder = l12 > lo2;
function renderTriangle(p1_x, p1_y, p2_x, p2_y, p3_x, p3_y) {
// Based on https://fgiesen.wordpress.com/2013/02/08/triangle-rasterization-in-practice/
function orient2d(ax, ay, bx, by, cx, cy) {
return (bx-ax)*(cy-ay) - (by-ay)*(cx-ax);
}
var max_x = Math.ceil(Math.max(p1_x, Math.max(p2_x, p3_x)));
var min_x = Math.floor(Math.min(p1_x, Math.min(p2_x, p3_x)));
var max_y = Math.ceil(Math.max(p1_y, Math.max(p2_y, p3_y)));
var min_y = Math.floor(Math.min(p1_y, Math.min(p2_y, p3_y)));
for(var x=min_x; x<=max_x; x++) {
for(var y=min_y; y<=max_y; y++) {
var r = color[0]; var g = color[1]; var b = color[2]; var alpha = 0;
// TODO offset the points to have space to AA the flat parts
// Determine barycentric coordinates
var w0 = orient2d(p2_x, p2_y, p3_x, p3_y, x, y);
var w1 = orient2d(p3_x, p3_y, p1_x, p1_y, x, y);
var w2 = orient2d(p1_x, p1_y, p2_x, p2_y, x, y);
// If p is on or inside all edges, render pixel.
if ((w0 >= 0 && w1 >= 0 && w2 >= 0) || (w0 <= 0 && w1 <= 0 && w2 <= 0)){
// The origin transformation saves calculations on the shader
// TODO Take this transformation out of the loop
alpha = calcAreaForPx(p10_x - o.x, p10_y - o.y, p11_x - o.x, p11_y - o.y, p12_x - o.x, p12_y - o.y,
p20_x - o.x, p20_y - o.y, p21_x - o.x, p21_y - o.y, p22_x - o.x, p22_y - o.y,
x - o.x, y - o.y,
dashedParameters.bezierLength, dashedParameters.curveProportions, dashedParameters.segmentLength, dashedParameters.segmentOffset,
reversedInternalBorder);
// alpha *= 0.3;
if (alpha < 0 || alpha > 1) { console.log(alpha);}
// Set the pixel color
var idx = (x + (h-y) * w) * 4; // Y reversed !
d[idx+0] = r; //d[idx+0]*(1-alpha) + 255*r*alpha;
d[idx+1] = g; //d[idx+1]*(1-alpha) + 255*g*alpha;
d[idx+2] = b; //d[idx+2]*(1-alpha) + 255*b*alpha;
d[idx+3] = d[idx+3]*(1-alpha) + 255*alpha;
// FIXME White fill can overlap with stroke !!!
// Probably the only solution is to draw the fill and the stroke independently.
//d[idx+0] = 255*(1-alpha); d[idx+1] = 255*(1-alpha); d[idx+2] = 255*(1-alpha); // White fill (and exterior)
}
}
}
}
// Points of the curves with respect to the origin point
var p10_x = c1[0].x;
var p10_y = c1[0].y;
var p11_x = c1[1].x;
var p11_y = c1[1].y;
var p12_x = c1[2].x;
var p12_y = c1[2].y;
var p20_x = c2[0].x;
var p20_y = c2[0].y;
var p21_x = c2[1].x;
var p21_y = c2[1].y;
var p22_x = c2[2].x;
var p22_y = c2[2].y;
if (!reversedInternalBorder) {
renderTriangle(p10_x, p10_y, p12_x, p12_y, p20_x, p20_y);
renderTriangle(p20_x, p20_y, p12_x, p12_y, p22_x, p22_y);
renderTriangle(p20_x, p20_y, p22_x, p22_y, p21_x, p21_y);
} else {
// If the triangle is reversed we adjust the painting to the origin
renderTriangle(p20_x, p20_y, o.x, o.y, p22_x, p22_y);
renderTriangle(p20_x, p20_y, p22_x, p22_y, p21_x, p21_y);
}
return o;
}
// Buffer for the pixel colors
var id = context.createImageData(w,h);
var d = id.data;
// Reverse curve
var baseCurve = curve;
if (isReversed(curve)) {
baseCurve = [curve[2], curve[1], curve[0]];
}
// Main Curve
var reduced = reduce(baseCurve);
// Offset Curve
var i = 0;
var origins = [];
var length = 10; // In pixels TODO Correct this if scaled
var dashOffset = 0;
var offsets = reduce(baseCurve).map(function(r) {
var s1 = scale(r,-distance/2);
var s2 = scale(r,distance/2);
var color = [0,0,0]; //[255*(i*0.4323 % 1), 255*(i*0.4323 % 1), 255*(i*0.4323 % 1)]
var dashedParameters = calcDashedParameters(s2, length, dashOffset);
dashOffset = dashedParameters.nextSegmentOffset;
var o = drawCurve(s1, s2, color, dashedParameters);
origins.push(o);
i += 1;
return [s1,s2];
});
context.putImageData(id, 0, 0);
// Draw main skeleton
api.setRandomColor();
api.drawSkeleton(new Bezier(baseCurve));
if (false) {
// Draw origins
origins.forEach(function(o){ drawCircle(o, 2, 5, "orange") });
// Draw offset skeletons
offsets.forEach(curves => {
var s1 = curves[0];
var s2 = curves[1];
api.setRandomColor();
api.drawSkeleton(new Bezier(s1));
api.drawSkeleton(new Bezier(s2));
});
}
};
handler.onupdate();
</script>
</body>
</html>
Raw
interaction.js
function eventFixedCoords(e) {
e = e || window.event;
var target = e.target || e.srcElement,
rect = target.getBoundingClientRect();
return {x: e.clientX - rect.left, y: rect.bottom - e.clientY};
};
function handleInteraction(cvs, curve) {
curve.mouse = false;
var lpts = curve;
var moving = false, mx = my = ox = oy = 0, cx, cy, mp = false;
var handler = { onupdate: function() {} };
cvs.addEventListener("mousedown", function(evt) {
var coords = eventFixedCoords(evt);
mx = coords.x;
my = coords.y;
lpts.forEach(function(p) {
if(Math.abs(mx-p.x)<10 && Math.abs(my-p.y)<10) {
moving = true;
mp = p;
cx = p.x;
cy = p.y;
}
});
});
cvs.addEventListener("mousemove", function(evt) {
var coords = eventFixedCoords(evt);
var found = false;
if(!lpts) return;
lpts.forEach(function(p) {
var mx = coords.x;
var my = coords.y;
if(Math.abs(mx-p.x)<10 && Math.abs(my-p.y)<10) {
found = found || true;
}
});
cvs.style.cursor = found ? "pointer" : "default";
if(!moving) {
return handler.onupdate(evt);
}
ox = coords.x - mx;
oy = coords.y - my;
mp.x = cx + ox;
mp.y = cy + oy;
//curve.update();
handler.onupdate();
});
cvs.addEventListener("mouseup", function(evt) {
if(!moving) return;
// console.log(curve.points.map(function(p) { return p.x+", "+p.y; }).join(", "));
moving = false;
mp = false;
});
cvs.addEventListener("click", function(evt) {
var coords = eventFixedCoords(evt);
var mx = coords.x;
var my = coords.y;
});
return handler;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment