Не понял вопроса. Пока критериев 2: близость по расстоянию (от точки выбросв) и направлению. Идея простейшая: если "примерно такой же" луч уже был - юзаем его, т.к. выброс и последующий шейдинг - удовольствие дорогое

Ах как быстро завершен мыслительный процесс (а он вообще начинался?). Ну да, как же мы можем "искать быстро" если заранее не построили нужных структур для поиска? А строить их всякий раз наверняка обойдется дороже перебора. Вот и все, и нефиг тут думать! Низзя!

Хотя есть одна идейка... Простая, всем известная, можно сказать "детская" 

Ну вообще-то хотелось бы от Вас что-то услышать/почерпнуть. А то с 5-го разв наконец "дошло", секунду поразмыслил и сказал что решения нет А то что сам знаю от меня никуда не убежит.

Собсно проблема в том что "кратность" поиска здесь мала, напр всего 200. Значит нужно делать "самые дешевые" структуры что помогут искать быстрее. Напрашивается "регулярная сетка". Прогоняем все найденные по расстоянию и заносим их в свои ячейки. Потом для каждого из 200 смотрим что сидит в ихней ячейке (и, возможно, соседних). Вряд ли это "так уж ускорит", но позорное пятно квадратичного перебора смоет.

Правда, реализация совсем не очевидна. Нужно быстро "спрыгивать на ячейку" (типа хеш), как это сделать для векторов напр-я (точек лежащих на сфере)?

Ну вот, сейчас опять начнется "чего-то не понял" и.т.п.

Не так. Требуется находить все данные удовлетворяющие критериям "расстояние" и "напр-е"  для каждого из 200 лучей исходящих из заданной точки. А как это делать - и есть тема обсуждения.

Сортировка по 2 и более ключам здесь смысла не имеет. Ну отсортировали, как бум искать? Кстати kd-tree сортированный result вовсе не гарантирует

Чего это? Та же регулярная (или нерегулярная) сетка имеет сложность O(N). Правда нужны хорошие "руки" чтобы здесь ее реализовать.

Кстати если так уж хотелось покритиковать постановку - это можно было легко сделать. При миллионах исходных точек скорее всего "чистый" поиск по нормали выдаст много тысяч подходящих/ближайших даже при отклонении < 1 градуса. А при углах 5-10 и подавно.

Какой "log", откуда он тут взялся? O(N * M), где N - число запросных точек, M - найденных по первому критерию близости (расстоянию). Рабочий случай N = 200, M = 100, бОльшие значения возможны.

Я уже сказал как - хеш. Получается O(M) + O(N) (занесение в хеш + поиск в нем). Правда неизвестно насколько это быстрее

"стоит или нет" означает "это для меня слишком трудно, сложно, давайте искать как обойти". В принципе это нормально, но "вторая часть" почему-то никогда не звучит

Почему два? И зачем вообще сортировать если поиску это никак не помогает?

Чего это оно "дорого"? Я же не собираюсь юзать std::unordered_map и.т.п. Есть массив (preallocated) что хранит головы списков. Перед началом поиска он зачищается (memset).  Обе ф-ции (занесение в хеш и поиск) получают на вход точку и по ее вектору напр-я вычисляют ячейку/эл-т этого массива. Занесение линкует точку к ячейке, поиск пробегается по списку. Здесь все ясно.

По сути все сводится к тому "как соскочить на ячейку" имея вектор напр-я (x, y, z). Шаблонное решение - получить инты из x, y, z и дальше банальный hash, остаток от деления. Как это усилить? Предположим на входе 2D вектор (x, y). Тогда ячейка вычисляется гораздо проще, как индексы двумерного массива. Да и точнее. Механически переносить это на 3 измерения, как обычно, плохо (опустим подробности). Вспоминаем что длины всех векторов = 1. Так не использовать ли проекцию вектора на плоскость, напр XZ ? Правда за отбрасывание одной координаты придется заплатить - нужно иметь 2 хеша (один для +y, др для -y). Ну это в общем случае, и это приемлемо. Однако проекции векторов распределены на плоскости совсем неравномерно, можно ли это учесть?

Успеваете за ходом мысли? Если нет, не торопитесь чего-то отвечать, подумайте. А я пока чайку нагною..