importance light sampling. tungsten

взято из Tungsten. со слов Handling multiple lights

идея для быстрого и экономного акселлератора пересечений луча с обьектами сцены 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