webgl - 如何在Dart WebGL应用程序中加快频段选择工具

Question

当前的任务是将波段选择工具添加到Dart WebGL应用程序。
该工具将通过拖动鼠标在多个对象上绘制一个矩形。
因此，可以在单个用户操作中选择/选择多个对象。
我目前正在使用gl.readPixels()从屏幕外的渲染缓冲区读取颜色。
问题是，当在较大范围内选择波段时，gl.readPixels()会发出数百万个像素。
扫描如此大量的颜色浪费了宝贵的时间，仅是为了定位几个物体。

请任何人指出使用Dart + WebGL波段选择多个对象的可能更快的方法。

作为引用，我在下面显示频段选择工具的主要部分。

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

现在，我可以看到一些小的解决方案，这些解决方案可能会加快您的算法的速度，从而尽可能限制所有元素的迭代，

您可以做的第一件事是使用默认颜色。当您看到该颜色时，您就知道不需要遍历整个元素数组。
它将加速人口稀少的大片地区。
它非常容易实现，只需添加一个if。

对于更密集的区域，您可以实现某种颜色缓存。这意味着您存储遇到的颜色数组。检查像素时，首先检查缓存，然后遍历整个元素列表，如果找到该元素，则将其添加到缓存中。
它可以加快没有大元素的情况，但是如果您有很多小元素，那将是不好的，如果您选择的话，这是不太可能的...
您可以加快缓存购买速度，以按上次匹配或/和按匹配数对缓存的元素进行排序，很有可能在连续的原始像素中找到相同的元素。
这是更多的工作，但相对容易实现且时间短。

最后的优化是实现空间划分算法，以过滤您要检查的元素。
从长远来看，这将是更多的工作，但会得到更好的返回。

编辑:
我不是 Dart ，但是这是通过前两种优化以基本方式实现的样子:

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;
}