Войти
ПрограммированиеФорумОбщее

поиск расстояния до ближайшего треугольника

Страницы: 1 2 3 4 Следующая »
#0
0:07, 8 дек. 2018

есть очень большой массив трианглов произвольная точка.
есть ли способ найти ближайший к точке треугольник?

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


#1
0:20, 8 дек. 2018

Mira
> закидать треугольники в OctTree - то расстояния до доундбоксов тоже ничего не
> дадут
Как это не дадут? Находишь ближайший баунд бокс с треугольниками. Это гарантирует тебе то, минимальное расстояние будет не больше, чем до самой дальней точки этого баунд бокса. Соответственно все остальные баунд боксы, лежащие дальше этого расстояния - можно на рассматривать.

#2
1:12, 8 дек. 2018

MrShoor
чекать расстояние честное до бокса, вроде бы очень кодоемкое. считать до каждого плейна

#3
1:58, 8 дек. 2018

Mira
> чекать расстояние честное до бокса, вроде бы очень кодоемкое.
В смысле?

// AABB_center=(AABB_hi+AABB_lo)/2.0f
// AABB_extent=(AABB_hi-AABB_lo)/2.0f
float distance(vec3f &point,const vec3f &AABB_center,const vec3f &AABB_extent)
{
    vec3f a=abs(point-AABB_center); // Component-wise.
    vec3f d=max(a-AABB_extent,vec3f{0.0f,0.0f,0.0f}); // Component-wise.
    return length(d);
}
#4
10:58, 8 дек. 2018

FordPerfect
И даже еще проще если сравнивать квадраты длинн

#5
11:22, 8 дек. 2018

FordPerfect
это для вписанной в бокс сферы же
хотя может оно тоже даст валидный результат

#6
11:46, 8 дек. 2018

Mira
Самый просто и производительный способ по ускорению поиска - это рассовать треугольники по сетке скажем 256x256x256 или меньше, тут без всяких деревьев, потом находишь ближайшие заполненные клетки и уже с ними считаешь. Это будет самым простым аналогом октодерева на 8 уровней.

#7
12:03, 8 дек. 2018

foxes
Дерево побыстрее будет

#8
13:03, 8 дек. 2018

Андрей5000
так тоже октри фиксированной глубины только без обхода иерархии с верхушки, но обычно ценой большего числа проверок. где то оно реально быстрее , особенно на разреженных в пространстве объектах.
а там где в одной клетке 1 объект в другой 200 - там оно проиграет, да.

#9
(Правка: 13:30) 13:20, 8 дек. 2018

Mira
> а там где в одной клетке 1 объект в другой 200
А у тебя сколько трианглов на фиксированный шаг приходиться в среднем? Насколько я понимаю это же не шум из трианглов, а какая то модель, то есть достаточно равномерно по поверхности модели треугольники распределены.
Тут даже на 100 объектов в клетке оно не сильно проиграет, линейный поиск по малому числу объектов не сильно хуже, против дерева когда эти объекты и узлы дерева разбросаны по памяти. Особенно если этих концентраций не очень много в целом также можно получить выигрыш.

#10
(Правка: 13:49) 13:45, 8 дек. 2018

foxes
ну как сказать, в дереве они разбросаны по компактному куску памяти, а при сетке по большому.

это модель персонажа и надо быстро найти расстояние до его поверхности, то бишь до ближайшего триангла. мне надо прецензионно перенести риг на другую топологию
просто приближенная интерполяция тоже катит но местми не идеально

кстати поиск с вписанной сферой не всегда верен будет =/
1111 | поиск расстояния до ближайшего треугольника

#11
(Правка: 16:43) 16:41, 8 дек. 2018

Mira
> в дереве они разбросаны по компактному куску памяти, а при сетке по большому.
Если узлы уложены в массив то да. А сетка для этого и делается не большой, чтобы тоже был компактный кусок. Ну для 3D сетки я конечно завернул, но стараются ее уложить в страницу кеша. Скажем если расширить узел дерева с 2x2x2 (32 - 64 байт) до 8x8x8 (2048 - 4096 байт), то это очень приличный буст, сразу 3 уровня от дерева.

#12
16:44, 8 дек. 2018

Mira
> это для вписанной в бокс сферы же
Что? Это именно расстояние от точки до AABB.

#13
18:17, 8 дек. 2018

Два вопроса, с которых стоило бы начать:
1. Сколько всё-таки треугольников? Хотя бы порядок.
2. С какой скоростью должен работать поиск?

Например: есть 1 миллион треугольников, есть 1000 точек, надо найти 1000 ближайших к ним треугольников и уложиться суммарно в 10 миллисекунд.

#14
18:19, 8 дек. 2018

Mira
купи мой ассет, там уже все сделанно , то что ты пытаешся сделать .
Заодно исходники посмотришь )


Страницы: 1 2 3 4 Следующая »
ПрограммированиеФорумОбщее