Программирование игр, создание игрового движка, OpenGL, DirectX, физика, форум
GameDev.ru / Программирование / Форум / поиск расстояния до ближайшего треугольника

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

Страницы: 1 2 3 4 Следующая »
MiraПостоялецwww8 дек. 20180:07#0
есть очень большой массив трианглов произвольная точка.
есть ли способ найти ближайший к точке треугольник?

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

MrShoorУчастникwww8 дек. 20180:20#1
Mira
> закидать треугольники в OctTree - то расстояния до доундбоксов тоже ничего не
> дадут
Как это не дадут? Находишь ближайший баунд бокс с треугольниками. Это гарантирует тебе то, минимальное расстояние будет не больше, чем до самой дальней точки этого баунд бокса. Соответственно все остальные баунд боксы, лежащие дальше этого расстояния - можно на рассматривать.
MiraПостоялецwww8 дек. 20181:12#2
MrShoor
чекать расстояние честное до бокса, вроде бы очень кодоемкое. считать до каждого плейна
FordPerfectПостоялецwww8 дек. 20181:58#3
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);
}
Андрей5000Постоялецwww8 дек. 201810:58#4
FordPerfect
И даже еще проще если сравнивать квадраты длинн
MiraПостоялецwww8 дек. 201811:22#5
FordPerfect
это для вписанной в бокс сферы же
хотя может оно тоже даст валидный результат
foxesПостоялецwww8 дек. 201811:46#6
Mira
Самый просто и производительный способ по ускорению поиска - это рассовать треугольники по сетке скажем 256x256x256 или меньше, тут без всяких деревьев, потом находишь ближайшие заполненные клетки и уже с ними считаешь. Это будет самым простым аналогом октодерева на 8 уровней.
Андрей5000Постоялецwww8 дек. 201812:03#7
foxes
Дерево побыстрее будет
MiraПостоялецwww8 дек. 201813:03#8
Андрей5000
так тоже октри фиксированной глубины только без обхода иерархии с верхушки, но обычно ценой большего числа проверок. где то оно реально быстрее , особенно на разреженных в пространстве объектах.
а там где в одной клетке 1 объект в другой 200 - там оно проиграет, да.
foxesПостоялецwww8 дек. 201813:20#9
Mira
> а там где в одной клетке 1 объект в другой 200
А у тебя сколько трианглов на фиксированный шаг приходиться в среднем? Насколько я понимаю это же не шум из трианглов, а какая то модель, то есть достаточно равномерно по поверхности модели треугольники распределены.
Тут даже на 100 объектов в клетке оно не сильно проиграет, линейный поиск по малому числу объектов не сильно хуже, против дерева когда эти объекты и узлы дерева разбросаны по памяти. Особенно если этих концентраций не очень много в целом также можно получить выигрыш.

Правка: 8 дек. 2018 13:30

MiraПостоялецwww8 дек. 201813:45#10
foxes
ну как сказать, в дереве они разбросаны по компактному куску памяти, а при сетке по большому.

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

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

Правка: 8 дек. 2018 13:49

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

Правка: 8 дек. 2018 16:43

FordPerfectПостоялецwww8 дек. 201816:44#12
Mira
> это для вписанной в бокс сферы же
Что? Это именно расстояние от точки до AABB.
alexzzzzПостоялецwww8 дек. 201818:17#13
Два вопроса, с которых стоило бы начать:
1. Сколько всё-таки треугольников? Хотя бы порядок.
2. С какой скоростью должен работать поиск?

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

Polyflow3dПостоялецwww8 дек. 201818:19#14
Mira
купи мой ассет, там уже все сделанно , то что ты пытаешся сделать .
Заодно исходники посмотришь )

Страницы: 1 2 3 4 Следующая »

/ Форум / Программирование игр / Общее

2001—2018 © GameDev.ru — Разработка игр