суббота, 6 августа 2016 г.

идея для быстрого и экономного акселлератора пересечений луча с обьектами сцены grid. обновлено - пересечение

данный алгоритм писался с учетом особенностей GLSL и программирования GPU-рендера - простота и быстродействие выбраных технологий
  1. по формуле из SunFlow расчитать количества ячеек в grid на основе ограничивающего бокса сцены и количества обьектов
  2. пройтись по сцене и вместо добавления обьектов увеличивать счетчик необходимых ячеек
  3. выделить память под массив
  4. расчитать коэфициент ближайшего большего десятка по количеству обьектов
  5. хранить одну запись в формате float.
    элемент массива = индекс обьекта*коэфициент + номер ячейки
  6. пройтись по сцене и сохранить в массив данные
  7. отсортировать сортировкой Шелла массив по номеру ячейки. она на 2-3 месте от quicksort и лучше там, что проста в воплощении и нерекурсивна
  8. доступ к элементам в ячейке - быстрый поиск в массиве по номеру ячейки
пересечение. проход ячейки grid.
  1. выбираются все обьекты у которых mailbox!=rayID, складываются в массив сортированых ид обьектов. если такой ид уже есть(бинарный поиск мне поможет), то не вставлять. если нет - смотреть и сдвигать элементы массива
  2. полученный массив обьектов сортируется по дальности центров BBox относительно ray.org (сортировка шелла, sqrt не вызываю)
    vec3 delta = vec3(bbx.bbmax-bbx.bbmin)*0.5-r.org;
    float dist = dot(delta,delta);
  3. отсортированный массив проходится и устанавливается обьектам mailbox=rayID