|
<!DOCTYPE html> |
|
<meta charset="utf-8"> |
|
<title>FFT-based transition on timelines</title> |
|
<meta content="Experimenting a FFT-based transitioning system between timelines in d3.js" name="description"> |
|
<style> |
|
|
|
body { |
|
position: relative; |
|
margin: auto; |
|
} |
|
|
|
#under-construction { |
|
display: none; |
|
position: absolute; |
|
top: 200px; |
|
left: 300px; |
|
font-size: 40px; |
|
} |
|
|
|
.path { |
|
fill: none; |
|
stroke: steelblue; |
|
stroke-width: 2px; |
|
} |
|
|
|
.progresses path, |
|
.progresses line { |
|
fill: none; |
|
stroke: black; |
|
shape-rendering: crispEdges; |
|
} |
|
.progresses text, text.small { |
|
font-family: sans-serif; |
|
font-size: 11px; |
|
fill: black; |
|
} |
|
|
|
.progresses .indicator { |
|
fill: none; |
|
stroke-width: 1; |
|
stroke: black; |
|
} |
|
</style> |
|
<body onload="initData()"> |
|
<svg></svg> |
|
<div id="under-construction"> |
|
UNDER CONSTRUCTION |
|
</div> |
|
<script src="//d3js.org/d3.v4.min.js"></script> |
|
<script> |
|
var WITH_TRANSITION = true; |
|
var WITHOUT_TRANSITION = false; |
|
var duration = 3000; |
|
|
|
var radix2 = 7, |
|
pathDataCount = Math.pow(2,radix2), // FFT only on data of length 2-radix |
|
currentPathData = [], |
|
newPathData = [], |
|
ease = d3.easeLinear, |
|
tweenCPs = [0.3, 0.7]; // timing of simplified paths; in ]0,1[ |
|
|
|
//begin: fft-based conf. |
|
var mainComponentCount = 2*radix2+1, // simplification strength |
|
currentFftComponents = [], |
|
currentFftMainComponents = [], |
|
currentFftSimplifiedPathData = [], |
|
newFftComponents = [], |
|
newFftMainComponents = [], |
|
newFftSimplifiedPathData = []; |
|
//end: fft-based conf. |
|
|
|
//begin: moving average conf. |
|
var windowSize = (radix2%2===0)? radix2+1 : radix2, |
|
halfWindowSize = Math.floor(windowSize/2), |
|
currentMovingAvgSimplifiedPathData = [], |
|
newMovingAvgSimplifiedPathData = []; |
|
//end: moving average conf. |
|
|
|
//begin: layout conf. |
|
var margin = {top: 20, right: 20, bottom: 20, left: 20}, |
|
svgWidth = 960, |
|
svgHeight = 500, |
|
width = svgWidth - margin.left - margin.right, |
|
height = svgHeight - margin.top - margin.bottom; |
|
//end: layout conf. |
|
|
|
var x = d3.scaleLinear() |
|
.domain([0, pathDataCount-1]) |
|
.range([0, width]); |
|
var y = d3.scaleLinear() |
|
.domain([0, 1]) |
|
.range([10, height/3-10]); |
|
|
|
var xProgress = d3.scaleLinear() |
|
.domain([0, 1]) |
|
.range([0, width]); |
|
|
|
var line = d3.line() |
|
.x(function(d,i){ return x(i); }) |
|
.y(function(d){ return y(d); }) |
|
.curve(d3.curveBasis); |
|
|
|
|
|
//begin: init layout and define reusable d3 selections |
|
d3.select("svg") |
|
.attr("width", svgWidth) |
|
.attr("height", svgHeight); |
|
var drawingArea = d3.select("svg").append("g") |
|
.attr("class", "drawing-area") |
|
.attr("transform", "translate(" + [margin.left, margin.top] + ")"); |
|
|
|
var basicPath = drawingArea |
|
.append("g") |
|
.classed("transition-container", true) |
|
.append("path") |
|
.classed("path", true); |
|
var fftPath = drawingArea |
|
.append("g") |
|
.classed("transition-container", true) |
|
.attr("transform", "translate("+[0,height/3]+")") |
|
.append("path") |
|
.classed("path", true); |
|
var movingAvgPath = drawingArea |
|
.append("g") |
|
.classed("transition-container", true) |
|
.attr("transform", "translate("+[0,2*height/3]+")") |
|
.append("path") |
|
.classed("path", true); |
|
|
|
var delta = 5; |
|
var progresses = drawingArea.append("g") |
|
.classed("progresses", true) |
|
.attr("transform", "translate("+[0,height/3]+")"); |
|
|
|
progresses.append("path") |
|
.attr("d", "M"+[0,delta]+"h"+width); |
|
progresses.append("path") |
|
.attr("d", "M"+[0,-delta]+"h"+width); |
|
progresses.selectAll(".tick") |
|
.data([0,tweenCPs[0],tweenCPs[1],1]) |
|
.enter() |
|
.append("path") |
|
.attr("d", function(d,i) { |
|
var x=xProgress(d); |
|
if (i%3===0) { |
|
return "M"+[x,-delta-4]+"v8M"+[x,delta-4]+"v8"; |
|
} else { |
|
return "M"+[x,delta-4]+"v8"; |
|
} |
|
}); |
|
|
|
progresses.append("text") |
|
.attr("transform", "translate("+[xProgress(0),-delta-7]+")") |
|
.attr("text-anchor", "begin") |
|
.text("initial path"); |
|
progresses.append("text") |
|
.attr("transform", "translate("+[xProgress(tweenCPs[0]),delta+15]+")") |
|
.attr("text-anchor", "middle") |
|
.text("simplified initial path"); |
|
progresses.append("text") |
|
.attr("transform", "translate("+[xProgress(tweenCPs[1]),delta+15]+")") |
|
.attr("text-anchor", "middle") |
|
.text("simplified final path"); |
|
progresses.append("text") |
|
.attr("transform", "translate("+[xProgress(1),-delta-7]+")") |
|
.attr("text-anchor", "end") |
|
.text("final path"); |
|
|
|
var basicProgressIndicator = progresses.append("circle") |
|
.classed("indicator", true) |
|
.attr("r", 3) |
|
.attr("cy", -5) |
|
.attr("cx", xProgress(0)); |
|
var modelBasedProgressIndicator = progresses.append("circle") |
|
.classed("indicator", true) |
|
.attr("r", 3) |
|
.attr("cy", 5) |
|
.attr("cx", xProgress(0)); |
|
|
|
drawingArea.append("text") |
|
.text("D3's path transition"); |
|
drawingArea.append("text") |
|
.classed("small", true) |
|
.attr("transform", "translate("+[130,0]+")") |
|
.text("("+pathDataCount+" points per path)"); |
|
drawingArea.append("text") |
|
.attr("transform", "translate("+[0,2*height/3]+")") |
|
.text("Path transition using simplified versions of paths for easier human comprehension (fft-based model, "+mainComponentCount+" components retained)"); |
|
drawingArea.append("text") |
|
.attr("transform", "translate("+[0,height]+")") |
|
.text("Path transition using simplified versions of paths for easier human comprehension (moving average model, "+windowSize+" points)"); |
|
//end: build layout and define reusable d3 selections |
|
|
|
function initData() { |
|
computeNewPathData(); |
|
computeNewFftComponents(); |
|
computeNewFftMainComponents(); |
|
computeNewFftSimplifiedPathData(); |
|
computeNewMovingAvgSimplifiedPathData(); |
|
|
|
drawPaths(); |
|
} |
|
|
|
//begin: main loop |
|
d3.interval(function(elapsed) { |
|
prepareLoop(); |
|
computeNewPathData(); |
|
computeNewFftComponents(); |
|
computeNewFftMainComponents(); |
|
computeNewFftSimplifiedPathData(); |
|
computeNewMovingAvgSimplifiedPathData(); |
|
|
|
redrawPaths(WITH_TRANSITION); |
|
animateTweenIndicators() |
|
}, duration+1000); |
|
//end: main loop |
|
|
|
function computeNewPathData() { |
|
var pathData = []; |
|
var i; |
|
|
|
for (i=0; i<pathDataCount; i++) { |
|
pathData.push(Math.random()); |
|
} |
|
newPathData = pathData; |
|
} |
|
|
|
//computeNewFftComponents: computes FFT's components of the newPathData |
|
function computeNewFftComponents() { |
|
var complexPathData = newPathData.map(function(d,i) { |
|
return new Complex(i, d); |
|
}) |
|
newFftComponents = cfft(complexPathData); |
|
} |
|
|
|
//computeNewFftMainComponents: retains only main FFT's components |
|
function computeNewFftMainComponents() { |
|
var fftMainComponents = [], |
|
apks, |
|
mainIndices; |
|
|
|
apks = newFftComponents.map(function(c,i){ return {f: i, apk: apk(c)}; }); |
|
apks.sort(function(apk0, apk1){ return apk1.apk-apk0.apk; }); |
|
mainIndices = apks.slice(0,mainComponentCount).map(function(apk){ return apk.f; }); |
|
|
|
newFftComponents.forEach(function(c,i){ |
|
if (mainIndices.includes(i)) { |
|
fftMainComponents.push(new Complex(c.re, c.im)); |
|
} else { |
|
fftMainComponents.push(new Complex(0, 0)); |
|
} |
|
}) |
|
newFftMainComponents = fftMainComponents; |
|
} |
|
|
|
//computeNewFftSimplifiedPathData: compute path data from retained FFT's components |
|
function computeNewFftSimplifiedPathData() { |
|
var fftSimplifiedPathData = icfft(newFftMainComponents); |
|
|
|
newFftSimplifiedPathData = fftSimplifiedPathData.map(function(d){ return d.im; }); |
|
} |
|
|
|
function apk(c) { return Math.pow(c.re,2)+Math.pow(c.im,2); }; |
|
|
|
function computeNewMovingAvgSimplifiedPathData() { |
|
var movingAvgSimplifiedPathData = [], |
|
cumul = 0, |
|
j; |
|
|
|
newPathData.map(function(d,i) { |
|
cumul += d; |
|
if (i===windowSize-1) { |
|
for(j=0; j<halfWindowSize; j++) { |
|
movingAvgSimplifiedPathData.push(cumul/windowSize); |
|
} |
|
movingAvgSimplifiedPathData.push(cumul/windowSize); |
|
} |
|
if (i>=windowSize) { |
|
cumul -= newPathData[i-windowSize]; |
|
movingAvgSimplifiedPathData.push(cumul/windowSize); |
|
} |
|
}) |
|
for(j=0; j<halfWindowSize; j++) { |
|
movingAvgSimplifiedPathData.push(cumul/windowSize); |
|
} |
|
newMovingAvgSimplifiedPathData = movingAvgSimplifiedPathData; |
|
} |
|
|
|
function drawPaths(withTransition) { |
|
basicPath.transition() |
|
.attr("d", line(newPathData)); |
|
fftPath.transition() |
|
.attr("d", line(newPathData)); |
|
movingAvgPath.transition() |
|
.attr("d", line(newPathData)); |
|
} |
|
|
|
function redrawPaths(withTransition) { |
|
basicPath.transition() |
|
.duration(withTransition? duration : 0) |
|
.attr("d", line(newPathData)); |
|
fftPath.transition() |
|
.duration(withTransition? duration : 0) |
|
.ease(ease) |
|
.attrTween("d", fftTween()); |
|
movingAvgPath.transition() |
|
.duration(withTransition? duration : 0) |
|
.ease(ease) |
|
.attrTween("d", movingAvgTween()); |
|
} |
|
|
|
//call modelBasedTween with FFT-based interim patData |
|
function fftTween() { |
|
return modelBasedTween(currentFftSimplifiedPathData, newFftSimplifiedPathData); |
|
} |
|
|
|
//call modelBasedTween with movingAvg-based interim patData |
|
function movingAvgTween() { |
|
return modelBasedTween(currentMovingAvgSimplifiedPathData, newMovingAvgSimplifiedPathData); |
|
} |
|
|
|
//modelBasedTween: separate transition in 3 stages: |
|
// stage 1: simplification: from (erratic) initial path to simplified version |
|
// stage 2: simple morphing: transition from simplified initial path to simplified final path |
|
// stage 3: complexification: from simplified final path to (erratic) final path |
|
function modelBasedTween(currentSimplifiedPathData, newSimplifiedPathData) { |
|
return function() { |
|
var stage1Interpolators = [], |
|
stage2Interpolators = [], |
|
stage3Interpolators = [], |
|
current, currentSimplified, newSimplified; |
|
|
|
newPathData.forEach(function(d,i) { |
|
current = currentPathData[i]; |
|
currentSimplified = currentSimplifiedPathData[i]; |
|
newSimplified = newSimplifiedPathData[i]; |
|
stage1Interpolators.push(d3.interpolate(current,currentSimplified)); |
|
stage2Interpolators.push(d3.interpolate(currentSimplified,newSimplified)); |
|
stage3Interpolators.push(d3.interpolate(newSimplified,d)); |
|
}); |
|
|
|
return function(t) { |
|
var t1, |
|
stageInterpolators, |
|
interimFftComponents, |
|
interimComplexData, |
|
pathData; |
|
|
|
if (t<1) { |
|
if (t<tweenCPs[0]) { |
|
t1 = d3.easeCubicInOut(t/tweenCPs[0]); |
|
stageInterpolators = stage1Interpolators; |
|
} else if (t<tweenCPs[1]) { |
|
t1 = d3.easeCubicInOut((t-tweenCPs[0])/(tweenCPs[1]-tweenCPs[0])); |
|
stageInterpolators = stage2Interpolators; |
|
} else { |
|
t1 = d3.easeCubicInOut((t-tweenCPs[1])/(1-tweenCPs[1])); |
|
stageInterpolators = stage3Interpolators; |
|
} |
|
pathData = stageInterpolators.map(function(i) { return i(t1); }) |
|
} else { |
|
pathData = newPathData; |
|
} |
|
|
|
return line(pathData); |
|
}; |
|
}; |
|
} |
|
|
|
function animateTweenIndicators() { |
|
basicProgressIndicator |
|
.attr("cx", 0) |
|
.transition() |
|
.duration(duration) |
|
.attr("cx", xProgress(1)); |
|
modelBasedProgressIndicator |
|
.attr("cx", 0) |
|
.transition() |
|
.duration(duration) |
|
.ease(function(t) { |
|
var t1; |
|
|
|
if (t<tweenCPs[0]) { |
|
t1 = d3.easeCubicInOut(t/tweenCPs[0]); |
|
t1 = t1*tweenCPs[0]; |
|
} else if (t<tweenCPs[1]) { |
|
t1 = d3.easeCubicInOut((t-tweenCPs[0])/(tweenCPs[1]-tweenCPs[0])); |
|
t1 = t1*(tweenCPs[1]-tweenCPs[0])+tweenCPs[0]; |
|
} else { |
|
t1 = d3.easeCubicInOut((t-tweenCPs[1])/(1-tweenCPs[1])); |
|
t1 = t1*(1-tweenCPs[1])+tweenCPs[1]; |
|
} |
|
return t1; |
|
}) |
|
.attr("cx", xProgress(1)); |
|
} |
|
|
|
function prepareLoop() { |
|
currentPathData = newPathData; |
|
currentFftComponents = newFftComponents; |
|
currentFftMainComponents = newFftMainComponents; |
|
currentFftSimplifiedPathData = newFftSimplifiedPathData; |
|
currentMovingAvgSimplifiedPathData = newMovingAvgSimplifiedPathData; |
|
} |
|
|
|
/******************************************************************/ |
|
/* complex fast fourier transform and inverse from */ |
|
/* https://rosettacode.org/wiki/Fast_Fourier_transform#JavaScript */ |
|
/******************************************************************/ |
|
function icfft(amplitudes) |
|
{ |
|
var N = amplitudes.length; |
|
var iN = 1 / N; |
|
|
|
//conjugate if imaginary part is not 0 |
|
for(var i = 0 ; i < N; ++i) |
|
if(amplitudes[i] instanceof Complex) |
|
amplitudes[i].im = -amplitudes[i].im; |
|
|
|
//apply fourier transform |
|
amplitudes = cfft(amplitudes) |
|
|
|
for(var i = 0 ; i < N; ++i) |
|
{ |
|
//conjugate again |
|
amplitudes[i].im = -amplitudes[i].im; |
|
//scale |
|
amplitudes[i].re *= iN; |
|
amplitudes[i].im *= iN; |
|
} |
|
return amplitudes; |
|
} |
|
|
|
function cfft(amplitudes) |
|
{ |
|
var N = amplitudes.length; |
|
if( N <= 1 ) |
|
return amplitudes; |
|
|
|
var hN = N / 2; |
|
var even = []; |
|
var odd = []; |
|
even.length = hN; |
|
odd.length = hN; |
|
for(var i = 0; i < hN; ++i) |
|
{ |
|
even[i] = amplitudes[i*2]; |
|
odd[i] = amplitudes[i*2+1]; |
|
} |
|
even = cfft(even); |
|
odd = cfft(odd); |
|
|
|
var a = -2*Math.PI; |
|
for(var k = 0; k < hN; ++k) |
|
{ |
|
if(!(even[k] instanceof Complex)) |
|
even[k] = new Complex(even[k], 0); |
|
if(!(odd[k] instanceof Complex)) |
|
odd[k] = new Complex(odd[k], 0); |
|
var p = k/N; |
|
var t = new Complex(0, a * p); |
|
t.cexp(t).mul(odd[k], t); |
|
amplitudes[k] = even[k].add(t, odd[k]); |
|
amplitudes[k + hN] = even[k].sub(t, even[k]); |
|
} |
|
return amplitudes; |
|
} |
|
|
|
/* |
|
basic complex number arithmetic from |
|
http://rosettacode.org/wiki/Fast_Fourier_transform#Scala |
|
*/ |
|
function Complex(re, im) |
|
{ |
|
this.re = re; |
|
this.im = im || 0.0; |
|
} |
|
Complex.prototype.add = function(other, dst) |
|
{ |
|
dst.re = this.re + other.re; |
|
dst.im = this.im + other.im; |
|
return dst; |
|
} |
|
Complex.prototype.sub = function(other, dst) |
|
{ |
|
dst.re = this.re - other.re; |
|
dst.im = this.im - other.im; |
|
return dst; |
|
} |
|
Complex.prototype.mul = function(other, dst) |
|
{ |
|
//cache re in case dst === this |
|
var r = this.re * other.re - this.im * other.im; |
|
dst.im = this.re * other.im + this.im * other.re; |
|
dst.re = r; |
|
return dst; |
|
} |
|
Complex.prototype.cexp = function(dst) |
|
{ |
|
var er = Math.exp(this.re); |
|
dst.re = er * Math.cos(this.im); |
|
dst.im = er * Math.sin(this.im); |
|
return dst; |
|
} |
|
Complex.prototype.log = function() |
|
{ |
|
/* |
|
although 'It's just a matter of separating out the real and imaginary parts of jw.' is not a helpful quote |
|
the actual formula I found here and the rest was just fiddling / testing and comparing with correct results. |
|
http://cboard.cprogramming.com/c-programming/89116-how-implement-complex-exponential-functions-c.html#post637921 |
|
*/ |
|
if( !this.re ) |
|
console.log(this.im.toString()+'j'); |
|
else if( this.im < 0 ) |
|
console.log(this.re.toString()+this.im.toString()+'j'); |
|
else |
|
console.log(this.re.toString()+'+'+this.im.toString()+'j'); |
|
} |
|
</script> |