parcoords constraint cleanup

- more precise mapping of constraints to data - which enables decreased filterEpsilon - only make the constraint mask texture once per render - and update it on subsequent renders, so we're not leaking THAT - let its height be independent of canvasHeight, and set at 2K - speed up mask generation by only unsetting, not unsetting and resetting - always overshoot ordinal values for clarity - when picking ordinal values, map closer to what your already showed instead of often jumping to cover an extra value
plotly · alexcjohnson · Mar 21, 2018 · Feb 5, 2018 · Mar 3, 2018 · Mar 6, 2018
commit 367e294422765da13a2efe1d10bc3c60fac89d4e
diff --git a/src/traces/parcoords/axisbrush.js b/src/traces/parcoords/axisbrush.js
@@ -45,43 +45,56 @@ function addFilterBarDefs(defs) {
         .attr('stroke-width', c.bar.strokeWidth);
 }
 
-// these two could be unified at a slight loss of readability
-function ordinalScaleSnapLo(a, v) {
-    var i, prevDiff, prevValue, diff, j;
-    for(i = 0, prevDiff = Infinity, prevValue = a[0]; i < a.length; i++) {
-        if(a[i] < v) j = i;
-        diff = Math.abs(a[i] - v);
-        if(diff > prevDiff) {
-            return {value: prevValue, adjacent: j};
-        }
-        prevDiff = diff;
-        prevValue = a[i];
+var snapRatio = c.bar.snapRatio;
+function snapOvershoot(v, vAdjacent) { return v * (1 - snapRatio) + vAdjacent * snapRatio; }
+
+var snapClose = c.bar.snapClose;
+function closeToCovering(v, vAdjacent) { return v * (1 - snapClose) + vAdjacent * snapClose; }
+
+// snap for the low end of a range on an ordinal scale
+// on an ordinal scale, always show some overshoot from the exact value,
+// so it's clear we're covering it
+// find the interval we're in, and snap to 1/4 the distance to the next
+// these two could be unified at a slight loss of readability / perf
+function ordinalScaleSnapLo(a, v, existingRanges) {
+    if(overlappingExisting(v, existingRanges)) return v;
+
+    var aPrev = a[0];
+    var aPrevPrev = aPrev;
+    for(var i = 1; i < a.length; i++) {
+        var aNext = a[i];
+
+        // very close to the previous - snap down to it
+        if(v < closeToCovering(aPrev, aNext)) return snapOvershoot(aPrev, aPrevPrev);
+        if(v < aNext || i === a.length - 1) return snapOvershoot(aNext, aPrev);
+
+        aPrevPrev = aPrev;
+        aPrev = aNext;
     }
-    return {value: a[a.length - 1], adjacent: j};
 }
 
-function ordinalScaleSnapHi(a, v) {
-    var i, prevDiff, prevValue, diff, j;
-    for(i = a.length - 1, prevDiff = Infinity, prevValue = a[a.length - 1]; i >= 0; i--) {
-        if(a[i] > v) j = i;
-        diff = Math.abs(a[i] - v);
-        if(diff > prevDiff) {
-            return {value: prevValue, adjacent: j};
-        }
-        prevDiff = diff;
-        prevValue = a[i];
+function ordinalScaleSnapHi(a, v, existingRanges) {
+    if(overlappingExisting(v, existingRanges)) return v;
+
+    var aPrev = a[a.length - 1];
+    var aPrevPrev = aPrev;
+    for(var i = a.length - 2; i >= 0; i--) {
+        var aNext = a[i];
+
+        // very close to the previous - snap down to it
+        if(v > closeToCovering(aPrev, aNext)) return snapOvershoot(aPrev, aPrevPrev);
+        if(v > aNext || i === a.length - 1) return snapOvershoot(aNext, aPrev);
+
+        aPrevPrev = aPrev;
+        aPrev = aNext;
     }
-    return {value: a[0], adjacent: j};
 }
 
-function snapOvershoot(a, i, value) {
-    // Take the distance to the adjacent ordinal value (if any) and extend the magenta bar to some ratio of it,
-    // so that singular value selections still show up with non-zero length (therefore visible and interactive) bars,
-    // yet the extension is short enough that a gap remains between adjacent selections, irrespective of how many
-    // ordinal values there are, and whether their cadence is regular or not. A dense clustering (screen distance of a
-    // few pixels or less) is still bound to result in undecipherable highlighting due to the limits of the screen
-    // resolution. Further doc is at the respective constants.
-    return (i === undefined ? c.bar.snapDefaultRatio : Math.abs(value - a[i]) * c.bar.snapRatio);
+function overlappingExisting(v, existingRanges) {
+    for(var i = 0; i < existingRanges.length; i++) {
+        if(v >= existingRanges[i][0] && v <= existingRanges[i][1]) return true;
+    }
+    return false;
 }
 
 function barHorizontalSetup(selection) {
@@ -282,9 +295,10 @@ function attachDragBehavior(selection) {
                 if(s.grabbingBar) { // moving the bar
                     s.newExtent = [y - s.grabPoint, y + s.barLength - s.grabPoint].map(d.unitScaleInOrder.invert);
                 } else { // south/north drag or new bar creation
-                    s.newExtent = d.unitScaleInOrder(s.startExtent) < y
-                        ? [s.startExtent, d.unitScaleInOrder.invert(y)]
-                        : [d.unitScaleInOrder.invert(y), s.startExtent];
+                    var endExtent = d.unitScaleInOrder.invert(y);
+                    s.newExtent = s.startExtent < endExtent ?
+                        [s.startExtent, endExtent] :
+                        [endExtent, s.startExtent];
                 }
 
                 // take care of the parcoords axis height constraint: bar can't breach it
@@ -338,18 +352,14 @@ function attachDragBehavior(selection) {
                 };
                 if(d.ordinal) {
                     var a = d.ordinalScale.range();
-                    var snapLo = ordinalScaleSnapLo(a, s.newExtent[0]);
-                    var snapHi = ordinalScaleSnapHi(a, s.newExtent[1]);
-                    var i0 = snapLo.adjacent;
-                    var i1 = snapHi.adjacent;
-                    s.newExtent[0] = snapLo.value;
-                    s.newExtent[1] = snapHi.value;
-                    if(s.newExtent[0] === s.newExtent[1]) {
-                        // if one single ordinal is selected, give it a finite bar length
-                        s.newExtent[0] = Math.max(0, s.newExtent[0] - snapOvershoot(a, i0, snapLo.value));
-                        s.newExtent[1] = Math.min(1, s.newExtent[1] + snapOvershoot(a, i1, snapHi.value));
+                    s.newExtent = [
+                        ordinalScaleSnapLo(a, s.newExtent[0], s.stayingIntervals),
+                        ordinalScaleSnapHi(a, s.newExtent[1], s.stayingIntervals)
+                    ];
+                    s.extent = s.stayingIntervals.concat(s.newExtent[1] > s.newExtent[0] ? [s.newExtent] : []);
+                    if(!s.extent.length) {
+                        brushClear(brush);
                     }
-                    s.extent = s.stayingIntervals.concat([s.newExtent]);
                     s.brushCallback(d);
                     renderHighlight(this.parentElement, mergeIntervals); // merging in
10000
tervals post the snap tween
                 } else {

diff --git a/src/traces/parcoords/constants.js b/src/traces/parcoords/constants.js
@@ -26,7 +26,7 @@ module.exports = {
         fillOpacity: 1, // Filter bar fill opacity
         snapDuration: 150, // tween duration in ms for brush snap for ordinal axes
         snapRatio: 0.25, // ratio of bar extension relative to the distance between two adjacent ordinal values
-        snapDefaultRatio: 0.05, // bar extension relative to the entire axis length, for when there's no adjacent value
+        snapClose: 0.01, // fraction of inter-value distance to snap to the closer one, even if you're not over it
         strokeColor: 'white', // Color of the filter bar side lines
         strokeOpacity: 1, // Filter bar side stroke opacity
         strokeWidth: 1, // Filter bar side stroke width in pixels

diff --git a/src/traces/parcoords/lines.js b/src/traces/parcoords/lines.js
@@ -9,13 +9,22 @@
 'use strict';
 
 var glslify = require('glslify');
-var c = require('./constants');
 var vertexShaderSource = glslify('./shaders/vertex.glsl');
 var contextShaderSource = glslify('./shaders/context_vertex.glsl');
 var pickVertexShaderSource = glslify('./shaders/pick_vertex.glsl');
 var fragmentShaderSource = glslify('./shaders/fragment.glsl');
 
-var depthLimitEpsilon = 1e-6; // don't change; otherwise near/far plane lines are lost
+var Lib = require('../../lib');
+
+// don't change; otherwise near/far plane lines are lost
+var depthLimitEpsilon = 1e-6;
+// just enough buffer for an extra bit at single-precision floating point
+// which on [0, 1] is 6e-8 (1/2^24)
+var filterEpsilon = 1e-7;
+
+// precision of multiselect is the full range divided into this many parts
+var maskHeight = 2048;
+
 
 var gpuDimensionCount = 64;
 var sectionVertexCount = 2;
@@ -206,6 +215,8 @@ module.exports = function(canvasGL, d) {
 
     var regl = d.regl;
 
+    var mask, maskTexture;
+
     var paletteTexture = regl.texture({
         shape: [256, 1],
         format: 'rgba',
@@ -295,6 +306,7 @@ module.exports = function(canvasGL, d) {
             hiD: regl.prop('hiD'),
             palette: paletteTexture,
             mask: regl.prop('maskTexture'),
+            maskHeight: regl.prop('maskHeight'),
             colorClamp: regl.prop('colorClamp')
         },
         offset: regl.prop('offset'),
@@ -310,30 +322,22 @@ module.exports = function(canvasGL, d) {
 
     var previousAxisOrder = [];
 
-    function makeItem(i, ii, x, y, panelSizeX, canvasPanelSizeY, crossfilterDimensionIndex, I, leftmost, rightmost) {
+    function makeItem(i, ii, x, y, panelSizeX, canvasPanelSizeY, crossfilterDimensionIndex, I, leftmost, rightmost, constraints) {
         var loHi, abcd, d, index;
         var leftRight = [i, ii];
-        var filterEpsilon = c.verticalPadding / canvasPanelSizeY;
 
         var dims = [0, 1].map(function() {return [0, 1, 2, 3].map(function() {return new Float32Array(16);});});
-        var lims = [0, 1].map(function() {return [0, 1, 2, 3].map(function() {return new Float32Array(16);});});
 
         for(loHi = 0; loHi < 2; loHi++) {
             index = leftRight[loHi];
             for(abcd = 0; abcd < 4; abcd++) {
                 for(d = 0; d < 16; d++) {
-                    var dimP = d + 16 * abcd;
                     dims[loHi][abcd][d] = d + 16 * abcd === index ? 1 : 0;
-                    if(!context) {
-                        lims[loHi][abcd][d] = (valid(d, 16 * abcd, panelCount) ? initialDims[dimP === 0 ? 0 : 1 + ((dimP - 1) % (initialDims.length - 1))].brush.filter.getBounds()[loHi] : loHi) + (2 * loHi - 1) * filterEpsilon;
-                    }
                 }
             }
         }
 
-        var mask, maskTexture;
-
-        var vm = {
+        var vm = Lib.extendFlat({
             key: crossfilterDimensionIndex,
             resolution: [canvasWidth, canvasHeight],
             viewBoxPosition: [x + overdrag, y],
@@ -361,55 +365,86 @@ module.exports = function(canvasGL, d) {
             viewportY: model.pad.b + model.layoutHeight * domain.y[0],
             viewportWidth: canvasWidth,
             viewportHeight: canvasHeight
-        };
+        }, constraints);
 
-        if(!context) {
-            mask = Array.apply(null, new Array(canvasHeight * channelCount)).map(function() {
-                return 255;
-            });
-            for(var dimIndex = 0; dimIndex < dimensionCount; dimIndex++) {
-                var bitIndex = dimIndex % bitsPerByte;
-                var byteIndex = (dimIndex - bitIndex) / bitsPerByte;
-                var bitMask = Math.pow(2, bitIndex);
-                var dim = initialDims[dimIndex];
-                var ranges = dim.brush.filter.get();
-                if(ranges.length < 2) continue; // bail if the bounding box based filter is sufficient
-                var pi, pixelRange;
-                var boundingBox = dim.brush.filter.getBounds();
-                pixelRange = boundingBox.map(dim.unitScaleInOrder);
-                for(pi = Math.max(0, Math.floor(pixelRange[0])); pi <= Math.min(canvasHeight - 1, Math.ceil(pixelRange[1])); pi++) {
-                    mask[pi * channelCount + byteIndex] &= ~bitMask; // clear bits
-                }
-                for(var r = 0; r < ranges.length; r++) {
-                    pixelRange = ranges[r].map(dim.unitScaleInOrder);
-                    for(pi = Math.max(0, Math.floor(pixelRange[0])); pi <= Math.min(canvasHeight - 1, Math.ceil(pixelRange[1])); pi++) {
-                        mask[pi * channelCount + byteIndex] |= bitMask;
+        return vm;
+    }
+
+    function makeConstraints() {
+        var loHi, abcd, d;
+
+        var lims = [0, 1].map(function() {return [0, 1, 2, 3].map(function() {return new Float32Array(16);});});
+
+        for(loHi = 0; loHi < 2; loHi++) {
+            for(abcd = 0; abcd < 4; abcd++) {
+                for(d = 0; d < 16; d++) {
+                    var dimP = d + 16 * abcd;
+                    var lim;
+                    if(valid(d, 16 * abcd, panelCount)) {
+                        var dimi = initialDims[dimP === 0 ? 0 : 1 + ((dimP - 1) % (initialDims.length - 1))];
+                        lim = dimi.brush.filter.getBounds()[loHi];
                     }
+                    else lim = loHi;
+                    lims[loHi][abcd][d] = lim + (2 * loHi - 1) * filterEpsilon;
                 }
             }
+        }
 
-            maskTexture = regl.texture({
-                shape: [channelCount, canvasHeight], // 8 units x 8 bits = 64 bits, just sufficient for the almost 64 dimensions we support
-                format: 'alpha',
-                type: 'uint8',
-                mag: 'nearest',
-                min: 'nearest',
-                data: mask
-            });
+        var maskExpansion = maskHeight / canvasHeight;

-            vm.maskTexture = maskTexture;
+        function expandedPixelRange(dim, bounds) {
+            var originalPixelRange = bounds.map(dim.unitScaleInOrder);
+            return [
+                Math.max(0, Math.floor(originalPixelRange[0] * maskExpansion)),
+                Math.min(maskHeight - 1, Math.ceil(originalPixelRange[1] * maskExpansion))
+            ];
+        }
 
-            vm.loA = lims[0][0];
-            vm.loB = lims[0][1];
-            vm.loC = lims[0][2];
-            vm.loD = lims[0][3];
-            vm.hiA = lims[1][0];
-            vm.hiB = lims[1][1];
-            vm.hiC = lims[1][2];
-            vm.hiD = lims[1][3];
+        mask = Array.apply(null, new Array(maskHeight * channelCount)).map(function() {
+            return 255;
+        });
+        for(var dimIndex = 0; dimIndex < dimensionCount; dimIndex++) {
+            var bitIndex = dimIndex % bitsPerByte;
+            var byteIndex = (dimIndex - bitIndex) / bitsPerByte;
+            var bitMask = Math.pow(2, bitIndex);
+            var dim = initialDims[dimIndex];
+            var ranges = dim.brush.filter.get().sort(function(a, b) {return a[0] - b[0]; });
+            if(ranges.length < 2) continue; // bail if the bounding box based filter is sufficient
+
+            var prevEnd = expandedPixelRange(dim, ranges[0])[1];
+            for(var ri = 1; ri < ranges.length; ri++) {
+                var nextRange = expandedPixelRange(dim, ranges[ri]);
+                for(var pi = prevEnd + 1; pi < nextRange[0]; pi++) {
+                    mask[pi * channelCount + byteIndex] &= ~bitMask;
+                }
+                prevEnd = Math.max(prevEnd, nextRange[1]);
+            }
         }
 
-        return vm;
+        var textureData = {
+            // 8 units x 8 bits = 64 bits, just sufficient for the almost 64 dimensions we support
+            shape: [channelCount, maskHeight],
+            format: 'alpha',
+            type: 'uint8',
+            mag: 'nearest',
+            min: 'nearest',
+            data: mask
+        };
+        if(maskTexture) maskTexture(textureData);
+        else maskTexture = regl.texture(textureData);
+
+        return {
+            maskTexture: maskTexture,
+            maskHeight: maskHeight,
+            loA: lims[0][0],
+            loB: lims[0][1],
+            loC: lims[0][2],
+            loD: lims[0][3],
+            hiA: lims[1][0],
+            hiB: lims[1][1],
+            hiC: lims[1][2],
+            hiD: lims[1][3]
+        };
     }
 
     function renderGLParcoords(panels, setChanged, clearOnly) {
@@ -433,6 +468,7 @@ module.exports = function(canvasGL, d) {
             // clear canvas here, as the panel iteration below will not enter the loop body
             clear(regl, 0, 0, canvasWidth, canvasHeight);
         }
+        var constraints = context ? {} : makeConstraints();
 
         for(I = 0; I < panelCount; I++) {
             var panel = panels[I];
@@ -447,7 +483,7 @@ module.exports = function(canvasGL, d) {
             var xTo = x + panelSizeX;
             if(setChanged || !previousAxisOrder[i] || previousAxisOrder[i][0] !== x || previousAxisOrder[i][1] !== xTo) {
                 previousAxisOrder[i] = [x, xTo];
-                var item = makeItem(i, ii, x, y, panelSizeX, panelSizeY, dim1.crossfilterDimensionIndex, I, leftmost, rightmost);
+                var item = makeItem(i, ii, x, y, panelSizeX, panelSizeY, dim1.crossfilterDimensionIndex, I, leftmost, rightmost, constraints);
                 renderState.clearOnly = clearOnly;
                 renderBlock(regl, glAes, renderState, setChanged ? lines.blockLineCount : sampleCount, sampleCount, item);
             }

diff --git a/src/traces/parcoords/parcoords.js b/src/traces/parcoords/parcoords.js
@@ -182,7 +182,8 @@ function viewModel(state, callbacks, model) {
 
     var unitPad = c.verticalPadding / (height * canvasPixelRatio);
     var unitPadScale = (1 - 2 * unitPad);
-    var paddedUnitScale = function(d) {return unitPad + unitPadScale * d;};
+    function paddedUnitScale(d) { return unitPad + unitPadScale * d; }
+    function invertPaddedUnitScale(d) { return (d - unitPad) / unitPadScale; }
     var uScaleInOrder = unitScaleInOrder(height, c.verticalPadding);
 
     var viewModel = {
@@ -202,7 +203,7 @@ function viewModel(state, callbacks, model) {
         var uScale = unitScale(height, c.verticalPadding);
         var specifiedConstraint = dimension.constraintrange;
         var filterRangeSpecified = specifiedConstraint && specifiedConstraint.length > 0;
-        var filterRange = filterRangeSpecified ? specifiedConstraint.map(function(d) {return d.map(domainToUnit);}) : [[0, 1]];
+        var filterRange = filterRangeSpecified ? specifiedConstraint.map(function(d) {return d.map(domainToUnit).map(paddedUnitScale);}) : [[0, 1]];
         var brushMove = function() {
             var p = viewModel;
             p.focusLayer && p.focusLayer.render(p.panels, true);
@@ -257,7 +258,7 @@ function viewModel(state, callbacks, model) {
                         var invScale = domainToUnit.invert;
 
                         // update gd.data as if a Plotly.restyle were fired
-                        var newRanges = f.map(function(r) {return r.map(invScale);});
+                        var newRanges = f.map(function(r) {return r.map(invertPaddedUnitScale).map(invScale);});
                         callbacks.filterChanged(p.key, dimension._index, newRanges);
                     }
                 }