How to speed up band selection tool in a Dart WebGL application

Question

The task at hand is to add a band selection tool to a Dart WebGL application. The tool will be used to draw a rectangle over multiple objects by dragging the mouse. Thus multiple objects can be selected/picked in a single user action. I'm currently using gl.readPixels() to read colors from an off-screen renderbuffer. Problem is, when a large area is band-selected, gl.readPixels() issues millions of pixels. Scanning such a big amount of colors wastes precious seconds just to locate few objects.

Please anyone point possibly faster methods for band-selecting multiple objects with Dart+WebGL.

For reference, I show below the current main portion of the band selection tool.

Uint8List _color = new Uint8List(4);

void bandSelection(int x, y, width, height, PickerShader picker, RenderingContext gl, bool shift) {

  if (picker == null) {
    err("bandSelection: picker not available");
    return;
  }

  int size = 4 * width * height;
  if (size > _color.length) {
    _color = new Uint8List(size);
  }

  gl.bindFramebuffer(RenderingContext.FRAMEBUFFER, picker.framebuffer);
  gl.readPixels(x, y, width, height, RenderingContext.RGBA, RenderingContext.UNSIGNED_BYTE, _color);

  if (!shift) {
    // shift is released
    _selection.clear();
  }

  for (int i = 0; i < size; i += 4) {

    if (_selection.length >= picker.numberOfInstances) {
      // selected all available objects, no need to keep searching
      break;
    }

    PickerInstance pi = picker.findInstanceByColor(_color[i], _color[i+1], _color[i+2]);
    if (pi == null) {
      continue;
    }

    _selection.add(pi);
  }

  debug("bandSelection: $_selection");  
}

// findInstanceByColor is method from PickerShader
PickerInstance findInstanceByColor(int r, g, b) {
  return colorHit(_instanceList, r, g, b);
}

PickerInstance colorHit(Iterable<Instance> list, int r,g,b) {

  bool match(Instance i) {
    Float32List f = i.pickColor;
    return (255.0*f[0] - r.toDouble()).abs() < 1.0 &&
        (255.0*f[1] - g.toDouble()).abs() < 1.0 &&
        (255.0*f[2] - b.toDouble()).abs() < 1.0;
  }

  Instance pi;

  try {
    pi = list.firstWhere(match);
  } catch (e) {
    return null;
  }

  return pi as PickerInstance;
}

Answer 1

Right now I can see small solutions that might speed up your algorithm to limit as much as possible iterating over all of your elements,

The first thing you can do is have a default colour. When you see that colour, you know you don't need to iterate all over your array of elements. It will accelerate large poorly populated areas. It's very easy to implement, just adding a if.

For more dense areas you can implement some kind of colour caching. That means you store an array of colour you encountered. When you check a pixel, you first check the cache and then go over the entire list of elements, and if you find the element, add it to the cache. It should accelerate cases with few big elements but will be bad if you have lots of small elements, which is very unlikely if you have picking... You can accelerate your cache buy sorting your cached elements by last hit or/and by number of hits, it's very likely to find the same element in a continuous raw of pixels. It's more work but stays relatively easy and short to implement.

Last optimisation would be to implement a space partitioning algorithm to filter the elements you want to check. That would be more work but will pay better of on the long run.

edit : I'm not a dart guy but this is how it would look like to implement in a basic way the first two optimisations:

var cache = new Map<UInt32, PickerInstance>();

for (int i = 0; i < size; i += 4) {
  UInt32 colour = _color[i] << 24 | _color[i+1] << 16 | _color[i+2] << 8 | 0; // I guess we can just skip transparency.

  if (_selection.length >= picker.numberOfInstances) {
    // selected all available objects, no need to keep searching
    break;
  }

  // black is a good default colour.
  if(colour == 0) {
    // if the pixel is black we didn't hit any element :(
    continue;
  }

  // check the cache
  if(cache[colour] != null) {
    _selection.add(cache[colour]);    
    continue;
  }

  // valid colour and cache miss, we can't avoid iterating the list.
  PickerInstance pi = picker.findInstanceByColor(_color[i], _color[i+1], _color[i+2]);
  if (pi == null) {
    continue;
  }

  _selection.add(pi);
  // update cache
  cache[colour] = pi;
}