Skip to content

Instantly share code, notes, and snippets.

@jacobsandlund

jacobsandlund/index.html

Last active May 16, 2016 02:55
Show Gist options
  • Save jacobsandlund/38eeb2717a9c24486e09e565120e1b09 to your computer and use it in GitHub Desktop.
Save jacobsandlund/38eeb2717a9c24486e09e565120e1b09 to your computer and use it in GitHub Desktop.
Download ZIP
Mouse Movement (quantized)
Raw
index.html
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<title>Mouse Movement</title>
<style>
body {
margin: 0;
}
h1, p {
margin-left: 50px;
}
p {
max-width: 550px;
}
canvas {
position: absolute;
width: 100%;
height: 800px;
border: solid 1px black;
}
.running canvas {
cursor: none;
}
</style>
</head>
<body>
<h1>Mouse Movement</h1>
<p>Spacetime will store mouse data in git, in memory on the client, so it needs to be stored effeciently. This is an attempt to understand the mouse data and explore ways to reduce the amount of space it will take.</p>
<p>One way being explored is to store mouse coordinates in two k-ary trees, one each for x and y, where the leaves are tuples of changes in x/y from the previous tick. Repeated tuples of the same change values will only need to be stored once (due to git's use of SHA-1), saving memory. To increase the odds of seeing a repeated tuple, the variability in the mouse changes can be reduced by quantizing them to a few allowed values.</p>
<p><strong>Instructions:</strong> Click the canvas to start, move the mouse around, and click again to stop. The black squares are adjusted by quantizing the mouse changes, and the red squares are the original mouse positions (hint: move faster for more red). Press shift to see only one color at a time, and press space to toggle between red and black.</p>
<canvas id="canvas-bottom"></canvas>
<canvas id="canvas-top"></canvas>
<script src="./quantize.js"></script>
<script src="./ui.js"></script>
<script src="./main.js"></script>
</body>
</html>
Raw
main.js
'use strict';
var Main = {};
(function () {
// State variables:
// * adjusted{X,Y} are the x/y values after the
// change in x/y has been quantized.
var current = {
x: 0,
y: 0,
adjustedX: 0,
adjustedY: 0,
};
var last = current;
var running = false;
var animationRequestId;
var cloneState = function (state) {
return {
x: state.x,
y: state.y,
adjustedX: state.adjustedX,
adjustedY: state.adjustedY,
};
};
Main.initialize = function () {
Ui.initialize();
};
Main.toggleRunning = function (x, y) {
if (running) {
stop();
} else {
start(x, y);
}
running = !running;
};
var start = function (x, y) {
current.x = x;
current.y = y;
current.adjustedX = x;
current.adjustedY = y;
last = cloneState(current);
Ui.startRunning();
Main.run();
};
var stop = function () {
Ui.stopRunning();
window.cancelAnimationFrame(animationRequestId);
};
Main.updatePosition = function (newX, newY) {
current.x = newX;
current.y = newY;
};
Main.run = function () {
current.adjustedX = Quantize.adjustPosition(current.x, last.x, last.adjustedX);
current.adjustedY = Quantize.adjustPosition(current.y, last.y, last.adjustedY);
Ui.draw(current);
last = cloneState(current);
animationRequestId = window.requestAnimationFrame(Main.run);
};
Main.initialize();
})();
Raw
quantize.js
'use strict';
var Quantize = {};
(function () {
// Quantize takes a change in a mouse coordinate (delta x or y)
// and constrains it to a predetermined set of allowed changes.
// The central data structure is the `quantizations` array,
// with `1` at all allowed mouse deltas (absolute deltas),
// and `0` otherwise.
// To quantize the mouse movement, find the nearest index with
// a `1` value in the `quantizations` array, starting with
// the index equal to the delta.
//
// Example:
// index: 0 1 2 3 4 5
// quantizations = [1, 0, 1, 0, 0, 1]
//
// If mouse x moves by 3, then start at index 3. quantizations[3]
// is 0, so search for the nearest index with 1. In this
// case it is 2, so 2 is the quantized change.
var quantizations; // set below
Quantize.adjustPosition = function (position, lastPosition, lastAdjustedPosition) {
var positionDiff = position - lastAdjustedPosition;
var velocity = position - lastPosition;
// Setting targetDiff to velocity mirrors the gaps between
// the position and the last position as best as possible,
// but introduces drift. Setting targetDiff to positionDiff
// tries to match the position as best as possible, but can
// cause gaps to alternate between too large and too small.
var targetDiff = (2 * velocity + 3 * positionDiff) / 5;
var quantizedDiff = quantize(targetDiff);
return lastAdjustedPosition + quantizedDiff;
};
var quantize = function (targetDiff) {
var absDiff = Math.abs(targetDiff);
var sign = targetDiff < 0 ? -1 : +1;
var low = Math.floor(absDiff);
var high = Math.ceil(absDiff);
while (!quantizations[low]) {
low--;
}
while (!quantizations[high]) {
high++;
}
var lowDiff = absDiff - low;
var highDiff = high - absDiff;
if (lowDiff < highDiff) {
return sign * low;
} else {
return sign * high;
}
};
// The quantization `level` is the number of allowed
// quantizations up to the current value. It is useful for
// analyzing the variability of the mouse changes.
// TODO: do this analysis.
Quantize.levelFromDiff = function (diff) {
var absDiff = Math.abs(diff);
var level = 0;
var i;
for (i = 0; i < absDiff; i++) {
if (quantizations[i]) {
level++;
}
}
return diff < 0 ? -level : level;
};
quantizations = [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,0,1,0,1,0,1,0,1,0,0,1,0,0,1,0,0,1,0,0,0,1,0,0,0,1,0,0,0,0,1,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0];
/*
// These two arrays and next two functions are used to build
// the `quantizations` array, so they aren't essential for
// understanding the rest of the program.
var gapBetweenQuantizations = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14,15, 17, 19, 22, 25, 29, 33, 38, 44, 51, 59, 68, 78, 90];
var countsAtEachGapAmount = [18, 5, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 10];
Quantize.generateQuantizations = function () {
var quantizations = [];
var k;
for (k = 0; k < countsAtEachGapAmount.length; k++) {
var count = countsAtEachGapAmount[k];
var gap = gapBetweenQuantizations[k];
var j;
for (j = 0; j < count; j++) {
quantizations.push(1);
var i;
for (i = 1; i < gap; i++) {
quantizations.push(0);
}
}
}
quantizationStats();
return quantizations;
};
var quantizationStats = function () {
var levelRanges = [];
var numLevels = [];
var errors = [];
var sum = 0;
var numLevelsSum = 0;
var k;
for (k = 0; k < countsAtEachGapAmount.length; k++) {
var count = countsAtEachGapAmount[k];
var gap = gapBetweenQuantizations[k];
var error = gap / 2;
var errorFraction = error / (sum + error);
var errorPercent = 100 * errorFraction;
var errorRounded = Math.round(100 * errorPercent) / 100;
errors[k] = errorRounded;
sum += count * gap;
numLevelsSum += count;
levelRanges[k] = sum;
numLevels[k] = numLevelsSum;
}
var pad = function (num) {
return (' ' + num).slice(-5);
};
console.log(gapBetweenQuantizations.map(pad).join(''));
console.log(countsAtEachGapAmount.map(pad).join(''));
console.log(levelRanges.map(pad).join(''));
console.log(numLevels.map(pad).join(''));
console.log(errors.map(pad).join(''));
};
quantizations = Quantize.generateQuantizations();
*/
})();
Raw
ui.js
'use strict';
var Ui = {};
(function () {
var boxSize = 10;
var canvasTop = document.getElementById('canvas-top');
var canvasBottom = document.getElementById('canvas-bottom');
var contextTop = canvasTop.getContext('2d');
var contextBottom = canvasBottom.getContext('2d');
var spaceToggle = false;
Ui.initialize = function () {
canvasTop.width = canvasTop.offsetWidth;
canvasTop.height = canvasTop.offsetHeight;
canvasBottom.width = canvasBottom.offsetWidth;
canvasBottom.height = canvasBottom.offsetHeight;
contextBottom.fillStyle = 'red';
contextTop.fillStyle = 'black';
canvasTop.addEventListener('click', function (event) {
Main.toggleRunning(event.clientX, event.clientY);
});
canvasTop.addEventListener('mousemove', function (event) {
Main.updatePosition(event.clientX, event.clientY);
});
window.addEventListener('keydown', function (event) {
if (event.shiftKey) {
if (event.keyCode === 32) {
spaceToggle = !spaceToggle;
event.preventDefault();
}
showHideCanvases(event.shiftKey);
}
});
window.addEventListener('keyup', function (event) {
if (!event.shiftKey) {
spaceToggle = false;
showHideCanvases(event.shiftKey);
}
});
};
var showHideCanvases = function (shiftDown) {
canvasTop.style.opacity = +(shiftDown === spaceToggle);
canvasBottom.style.opacity = +!spaceToggle;
};
Ui.startRunning = function () {
document.body.className = 'running';
contextTop.clearRect(0, 0, canvasTop.width, canvasTop.height);
contextBottom.clearRect(0, 0, canvasBottom.width, canvasBottom.height);
console.log('Recording...\n\n\n\n\n\n\n');
};
Ui.stopRunning = function () {
document.body.className = '';
};
Ui.draw = function (state) {
var offsetLeft = canvasTop.offsetLeft;
var offsetTop = canvasTop.offsetTop - window.scrollY;
contextBottom.fillRect(state.x - offsetLeft, state.y - offsetTop, boxSize, boxSize);
contextTop.fillRect(state.adjustedX - offsetLeft, state.adjustedY - offsetTop, boxSize, boxSize);
};
})();
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment