Как ускорить инструмент выбора диапазона в приложении 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; 
}