Войти
ПрограммированиеФорумГрафика

Бинарный поиск ближайшей точки в 3D [кривые, заполняющие пространство и пр]

#0
14:52, 19 мая 2017

И так, шальные мысли опять затуманили мой разум ))) В поисках решения Real Time TRUE Global illumination я наткнулся на необходимость сверх быстрого поиска ближайшей точки в 3D, хотя бы бинарным поиском.
Дано:
1. Массив точек в 3D, у каждой есть координаты X,Y и Z. Точки не лежат в упор рядом друг с другом образуя сплошной куб, точки разбросаны рандомно.
2. Есть точка - мишень, у которой так же есть TARGET(X,Y,Z).

Найти в массиве из п.1 ближайшую точку к точке мишени (TARGET) за время, не превышающее log(N) (ну и + n времени на случай, если есть много ближайших точек на одинаковом расстояние)

Собственно что я сам об этом думаю, есть так называемые кривые, заполняющие пространство (ну это из королевства фракталов), например кривая Пеано или кривая Мортона, причём о последней наверное многие слышали, точнее слышали наверное о Мортон кодах при построение окто деревьев, но наверное не знали, откуда ноги растут :-)
Ну так вот, эти кривые как раз и создавались, что бы описать позицию точки в n-мерном пространстве для быстрого поиска, но конечно же не всё так просто. Все эти кривые не дают 100% гарантии, что ты найдёшь именно ближайшую точку, что для рендера конечно же не подходит. Ну так вот, есть ли у вас какие то идеи, как построить дерево, отсортировать массив или сделать что - угодно другое с базовым массивом точек, что бы можно было бинарным поиском найти ближайшую точку в хотя бы в 3D ?
P.S.: тем, кто предложит октодерево - сразу скажу, что исходный массив огромен, опустим 100 000 000 000 и тратить память на дерево не получиться :-)


#1
16:25, 19 мая 2017

-=MASTER=-
RB-tree :)

#2
9:32, 20 мая 2017

Mira
> RB-tree :)
в общем, быстрый поиск ближайшей точки - это част задачи, с помощью которой можно лишь обыграть ray marching или тот же surfels marching в point-based approximate color bleeding, в идеале конечно нежно не это.
В идеале нужен быстрый поиск ray - triangle intersection-а, то есть поиск ближайшего к стартовой точке луча треугольника из огромного массива, который этот луч пересёк. Вот если этот поиск провернуть на скорости log(N) + n, тога ты будешь круче всех и сделаешь true real time path tracing без шума.

#3
11:31, 20 мая 2017

Может просто отсортировать точки по осям (используя допуск отклонения)?
Да, массивы каждой строчки будут неравномерные, однако, вряд ли, это будет большой проблемой (дело техники, т.с.).

#4
11:38, 20 мая 2017

ExeLord
> Может просто отсортировать точки по осям (используя допуск отклонения)?
что ты имеешь ввиду? Сделать три массива, 1-й отсортирован по X, 2-й - по Y, 3-й по Z ?
Ну и как ты будешь искать ближайшую точку в таком случае?

#5
17:35, 20 мая 2017

Октодерево?

#6
21:13, 20 мая 2017

-=MASTER=-
Да нет же! Назовём это Axes Aligned Vertex Sort.
1) Сортируем массив по ОХ. Заодно находим Xmin, Xmax.
2) Разбиваем промежуток на N частей. И в данном случае (Xmax-Xmin)/N - это и будет допуск строчки.
Заводим массив из { startID; count } длиной N (думаю, понятно зачем).
Пробегаем по отсортированному массиву точек и для каждого промежутка находим начало и конец (выпадание точки).
3) Каждый из промежутков сортируем по ОY;
4) Повторяем разбивку, но уже по ОY для каждого промежутка ОХ.
5) Сортируем по OZ;

Выходит, при поиске, мы достаточно легко можем вычислить, в какой из промежутков попадает цель.
В этом и близлежащих (на всякий случай) промежутках ищем по Z бинарным поиском ближайшую точку.
А проверка близлежащих промежутков (как по х так и по у) может дать лучшие результаты по другим координатам (которые кроме z)

(типа z далеко, а есть другая ближе но смешенная по y (в другом промежутке). Но надо смотреть по размерам допуска.
В любом случае, по OY берутся только два промежутка, иначе по y слишком далеко будет и это не будет иметь смысла)

и выбрать из них лучший вариант.

Panzerschrek[CN]
> Октодерево?
>P.S.: тем, кто предложит октодерево - сразу скажу, что исходный массив огромен, допустим 100 000 000 000 и тратить память на дерево не получиться :-)
Вас же предупреждали :-)
#7
9:16, 21 мая 2017

ExeLord, не, это ерунда, объясню почему:
1. Фактический, то, что ты делаешь в п.1 и 2. - это просто построение пирамидального дерево для оси Х. Это можно вообще не делать, можно бинарным поиском искать сразу
2. Главная фишка в том, что это тебе ничего не даст, т.к. ну нашёл ты ближайший ящик (с N элементами) по оси Х, ну и что? Этот ближайший ящик может содержать очень далёкие значения по Y или по Z, по этому, наиближайшим вариантом будет не самый ближайший ящик, а возможно соседний...  Хотя хз, возможно я тебя не правильно понял и ты имеешь ввиду, что в каждом ящике хранятся min/max элементы по X,Y и Z ? Но как же ты эти ящики отсортируешь?
В общем, ты сам ещё раз подумай над своей идей и увидишь, что там косяк, хотя опять же, возможно я ошибаюсь, тогда объясни в чём?

Вообще, я долго думал над этой темой, на самом деле все эти классические подходы тут не годятся, тут нужно нечто вроде 3D intervaltree или 3D NCList (https://academic.oup.com/bioinformatics/article-abstract/23/11/13… algorithm-for)

#8
18:11, 22 мая 2017

-=MASTER=-
> Это можно вообще не делать, можно бинарным поиском искать сразу
Как? Если координаты 3, а не 1. Или сортировать по удалению от ЦК (все равно фигня же будет)?
> возможно я тебя не правильно понял и ты имеешь ввиду
Эти ящики, как бы ячейки сетки по ху (понятное дело, сортированны соответственно). В каждой ячейке точки отсортированы по z (по последней координате, пожалуй, нет смысла разбивать).

А про 2-ой пункт я написал. Примем допущение, что в каждом ящике есть хотя бы одна точка. Тогда ближайший вариант, может оказаться максимум в соседнем ящике. Ведь проигрыш по ОХ должен быть меньше, чем выигрыш по ОY или OZ. Т.е. проигрыш по других координатам говорит нам о том, насколько далеко мы можем смотреть в другие ящики. Ещё стоит проверять по min/max (1-ый и последний элементы диапазона) к какому лучше ящику переходить.
Если же пустых ящиков очень много (довольно маловероятный случай, с учетом огроменного кол-ва точек), тогда это ваще пичалька (если пробегать нужно больше чем 10-100 соседних ящиков)! Лучше тогда переразбить на меньшее кол-во ящиков, или вообще разбить это облако на несколько более плотных облаков и там уже сортировать.

П.С. в любом случае, нужно проверять. На глаз, так просто, сложно предугадать...

Прости! Но рисовать (для объяснений) и проверять лень и некогда. Так что, если это туфта или непонятно... то, значит, туфта! :)

#9
20:57, 22 мая 2017

ExeLord
> или вообще разбить это облако на несколько более плотных облаков и там уже
> сортировать.
ну в общем то это Sparse Voxels Oct Tree с mipmap-ами так сказать...
Ладно, я понял, буду дальше думать, есть у меня пара идеек :-)

ПрограммированиеФорумГрафика

Тема в архиве.