Как ускорить инструмент выбора диапазона в приложении Dart WebGL

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

dart webgl picking mouse-picking ray-picking
person Everton    schedule 21.12.2013    source источник
comment
Можем ли мы увидеть, как реализована функция «findInstanceByColor»?   -  person nesderl    schedule 21.12.2013
comment
Как пиксели попали туда, где они находятся, в первую очередь, это объекты, форму и положение которых вы уже знаете, потому что вы их визуализировали? Если да, то могли бы вы использовать пересечение нарисованной формы полосы с известными фигурами, чтобы получить то, что вы хотите, или есть какая-то другая причина, по которой вам нужно выбирать по цвету?   -  person ianmjones    schedule 22.12.2013
comment
@nesderl: включен метод findInstanceByColor.   -  person Everton    schedule 23.12.2013
comment
@ianmjones: я использую цветовое кодирование. Я визуализирую каждый выбираемый объект с уникальным цветом в буфер рендеринга за пределами экрана. Чтобы узнать, какой объект отображается в пикселях (x, y), мне просто нужно прочитать цвет пикселя и использовать его для поиска объекта. Обратите внимание, что внеэкранный буфер рендеринга имеет только информацию о цвете; он не содержит информации о геометрии, поэтому я мог выполнять обработку пересечений. Думаю, я мог бы сделать геометрическое пересечение, но форма полосы 2d (расположена в ближней плоскости), а форма объекта 3d, расположенная в произвольном месте. Я не уверен в лучшем ожидании, чтобы пересечь их.   -  person Everton    schedule 23.12.2013

Ответы (1)


arrow_upward
1
arrow_downward

Прямо сейчас я вижу небольшие решения, которые могут ускорить ваш алгоритм, чтобы максимально ограничить повторение всех ваших элементов,

Первое, что вы можете сделать, это установить цвет по умолчанию. Когда вы видите этот цвет, вы знаете, что вам не нужно перебирать весь массив элементов. Это ускорит большие малонаселенные районы. Это очень легко реализовать, просто добавив 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;
}
person nesderl    schedule 23.12.2013
comment
Спасибо за отличные советы по оптимизации. Я попробую их, чтобы увидеть, насколько я ускорюсь, прежде чем прибегать к геометрическим методам. - person Everton; 23.12.2013
comment
Ваши предложения значительно улучшили результаты. Из секунд я теперь вижу ~ 400 мс под JS (Dart скомпилирован в JS) и ~ 40 мс под Dart. - person Everton; 24.12.2013
comment
Здорово! 400 мс все еще слишком медленно для любого приложения реального времени, сколько элементов, элементов на экране и пикселей вы тестируете, чтобы иметь такую ​​​​плохую производительность? - person nesderl; 24.12.2013
comment
В тесте есть следующие числа: - person Everton; 24.12.2013