如何在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.

对于更密集的区域，您可以实现某种颜色缓存。这意味着你存储了一系列你遇到的颜色。检查像素时，首先检查缓存，然后查看整个元素列表，如果找到元素，则将其添加到缓存中。它应该会加速几乎没有大元素的情况，但如果你有很多小元素，那就不好了，如果你选择了。。。你可以加速你的缓存购买，根据上次点击或/和点击次数对缓存元素进行排序，很可能在连续的像素原始中找到相同的元素。它的工作量更大，但实现起来相对容易且时间短。

最后的优化是实现一个空间划分算法来过滤你想要检查的元素。这将是更多的工作，但从长远来看会有更好的回报。

编辑：我不是飞镖手，但这就是以基本方式实现前两个优化的方式：

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