Improve perf of picking with large pickingRadius (visgl#1222)

Pessimistress · web-flow · commit d08a72b997b2 · 2017-12-08T19:03:11.000-08:00
diff --git a/src/core/lib/pick-layers.js b/src/core/lib/pick-layers.js
@@ -339,7 +339,7 @@ function callLayerPickingCallbacks(infos, mode) {
  * Pick at a specified pixel with a tolerance radius
  * Returns the closest object to the pixel in shape `{pickedColor, pickedLayer, pickedObjectIndex}`
  */
-function getClosestFromPickingBuffer(gl, {
+export function getClosestFromPickingBuffer(gl, {
   pickedColors,
   layers,
   deviceX,
@@ -348,42 +348,53 @@ function getClosestFromPickingBuffer(gl, {
   deviceRect
 }) {
   assert(pickedColors);
-  let closestResultToCenter = NO_PICKED_OBJECT;
 
   // Traverse all pixels in picking results and find the one closest to the supplied
   // [deviceX, deviceY]
+  const {x, y, width, height} = deviceRect;
   let minSquareDistanceToCenter = deviceRadius * deviceRadius;
+  let closestPixelIndex = -1;
   let i = 0;
 
-  for (let row = 0; row < deviceRect.height; row++) {
-    for (let col = 0; col < deviceRect.width; col++) {
-      // Decode picked layer from color
-      const pickedLayerIndex = pickedColors[i + 3] - 1;
-
-      if (pickedLayerIndex >= 0) {
-        const dx = col + deviceRect.x - deviceX;
-        const dy = row + deviceRect.y - deviceY;
-        const d2 = dx * dx + dy * dy;
-
-        if (d2 <= minSquareDistanceToCenter) {
-          minSquareDistanceToCenter = d2;
-
-          // Decode picked object index from color
-          const pickedColor = pickedColors.slice(i, i + 4);
-          const pickedLayer = layers[pickedLayerIndex];
-          if (pickedLayer) {
-            const pickedObjectIndex = pickedLayer.decodePickingColor(pickedColor);
-            closestResultToCenter = {pickedColor, pickedLayer, pickedObjectIndex};
-          } else {
-            log.error(0, 'Picked non-existent layer. Is picking buffer corrupt?');
+  for (let row = 0; row < height; row++) {
+    const dy = row + y - deviceY;
+    const dy2 = dy * dy;
+
+    if (dy2 > minSquareDistanceToCenter) {
+      // skip this row
+      i += 4 * width;
+    } else {
+      for (let col = 0; col < width; col++) {
+        // Decode picked layer from color
+        const pickedLayerIndex = pickedColors[i + 3] - 1;
+
+        if (pickedLayerIndex >= 0) {
+          const dx = col + x - deviceX;
+          const d2 = dx * dx + dy2;
+
+          if (d2 <= minSquareDistanceToCenter) {
+            minSquareDistanceToCenter = d2;
+            closestPixelIndex = i;
           }
         }
+        i += 4;
       }
-      i += 4;
     }
   }
 
-  return closestResultToCenter;
+  if (closestPixelIndex >= 0) {
+    // Decode picked object index from color
+    const pickedLayerIndex = pickedColors[closestPixelIndex + 3] - 1;
+    const pickedColor = pickedColors.slice(closestPixelIndex, closestPixelIndex + 4);
+    const pickedLayer = layers[pickedLayerIndex];
+    if (pickedLayer) {
+      const pickedObjectIndex = pickedLayer.decodePickingColor(pickedColor);
+      return {pickedColor, pickedLayer, pickedObjectIndex};
+    }
+    log.error(0, 'Picked non-existent layer. Is picking buffer corrupt?');
+  }
+
+  return NO_PICKED_OBJECT;
 }
 /* eslint-enable max-depth, max-statements */
 
diff --git a/test/bench/index.js b/test/bench/index.js
@@ -25,10 +25,12 @@ import coreLayersBench from './core-layers.bench';
 import layerBench from './layer.bench';
 import viewportBench from './viewport.bench';
 import colorBench from './color.bench';
+import pickLayersBench from './pick-layers.bench';
 
 const suite = new Bench();
 
 // add tests
+pickLayersBench(suite);
 coreLayersBench(suite);
 layerBench(suite);
 viewportBench(suite);
diff --git a/test/bench/pick-layers.bench.js b/test/bench/pick-layers.bench.js
@@ -0,0 +1,76 @@
+import {Layer} from 'deck.gl/core';
+import {getClosestFromPickingBuffer} from 'deck.gl/core/lib/pick-layers';
+
+const SAMPLE_LAYERS = [new Layer()];
+const OBJECT_COLOR = [0, 10, 20, 1];
+const NULL_COLOR = [0, 0, 0, 0];
+
+const TEST_CASES = [
+  {
+    title: 'Solid',
+    data: generateSampleData({
+      pickingRadius: 10,
+      getColor: () => OBJECT_COLOR
+    })
+  },
+  {
+    // radius 5 circle centered in 20x20 rect.
+    title: 'Circle',
+    data: generateSampleData({
+      pickingRadius: 10,
+      getColor: (x, y) => (10 - x) * (10 - x) + (10 - y) * (10 - y) < 25 ? OBJECT_COLOR : NULL_COLOR
+    })
+  },
+  {
+    // half of rect on top left
+    title: 'Triangle',
+    data: generateSampleData({
+      pickingRadius: 10,
+      getColor: (x, y) => x + y <= 10 ? OBJECT_COLOR : NULL_COLOR
+    })
+  },
+  {
+    title: 'Solid - Big',
+    data: generateSampleData({
+      pickingRadius: 50,
+      getColor: () => OBJECT_COLOR
+    })
+  }
+];
+
+export default function pickLayersBench(bench) {
+
+  bench = bench.group('getClosestFromPickingBuffer');
+
+  TEST_CASES.forEach(testCase => {
+    bench = bench.add(testCase.title, () => getClosestFromPickingBuffer(null, testCase.data));
+  });
+
+  return bench;
+}
+
+function generateSampleData({pickingRadius, getColor}) {
+  const width = pickingRadius * 2;
+  const height = pickingRadius * 2;
+  const pixels = new Uint8Array(width * height * 4);
+
+  let i = 0;
+  for (let row = 0; row < height; row++) {
+    for (let col = 0; col < width; col++) {
+      const color = getColor(col, row);
+      pixels[i++] = color[0];
+      pixels[i++] = color[1];
+      pixels[i++] = color[2];
+      pixels[i++] = color[3];
+    }
+  }
+
+  return {
+    pickedColors: pixels,
+    layers: SAMPLE_LAYERS,
+    deviceX: pickingRadius,
+    deviceY: pickingRadius,
+    deviceRadius: pickingRadius,
+    deviceRect: {x: 0, y: 0, width, height}
+  };
+}
