Параллельные геометрические вычисления на GPU

[0...-5]

Очень нужна помощь!
Условия задачи таковы: имеется поверхность, заданная множеством треугольников. Есть алгоритм перемещения объекта вдоль этой поверхности, основанный на определении направления, при котором расстояние до поверхности максимально. Таким образом, задача поиска траектории сводится к огромному количеству вычислений точки пересечения луча и треугольника. Можно ли повысить производительность вычислений, если их перенести с CPU на GPU? Никогда не занимался подобными вещами, подскажите в какую сторону думать?
День гугленья не внес существенной ясности. Есть несколько архитектур (CUDA, OpenCL и проч), но какая из них предпочтительней в моем случае я так и не понял. Приоритетом для меня является простота интеграции в QtCreator.

[Igors]

Условия задачи таковы: имеется поверхность, заданная множеством треугольников. Есть алгоритм перемещения объекта вдоль этой поверхности, основанный на определении направления, при котором расстояние до поверхности максимально. Таким образом, задача поиска траектории сводится к огромному количеству вычислений точки пересечения луча и треугольника.

Может "один объект ползает по поверхности другого" (не пересекая его)? Не видно смысла в "расстояние до поверхности максимально" - ведь объект может удаляться от поверхности неограниченно далеко. Также уточните

- поверхность связная или может состоять из неск кусков
- объект конвексный (выпуклый) или нет
- каковы требования к непересекаемости/контакту
- какой путь нужно получить
- причем тут лучи

[0...-5]

Условия задачи таковы: имеется поверхность, заданная множеством треугольников. Есть алгоритм перемещения объекта вдоль этой поверхности, основанный на определении направления, при котором расстояние до поверхности максимально. Таким образом, задача поиска траектории сводится к огромному количеству вычислений точки пересечения луча и треугольника.

Может "один объект ползает по поверхности другого" (не пересекая его)? Не видно смысла в "расстояние до поверхности максимально" - ведь объект может удаляться от поверхности неограниченно далеко. Также уточните

- поверхность связная или может состоять из неск кусков
- объект конвексный (выпуклый) или нет
- каковы требования к непересекаемости/контакту
- какой путь нужно получить
- причем тут лучи

ммм...не знаю как это может помочь, но...
Моделируется прохождение рыбой рыбопропускного сооружения. При этом рыба ориентируется на заданное поле скоростей (структурированная сетка) и на стены сооружения, заданные поверхностями. Поверхности образуются списком треугольников. На выбор направления движения влияют скорость жидкости в данной точки и расстояние до поверхности (стенки) вдоль этого направления. Расстояние ищется перебором треугольников, образующих поверхность и проверкой их пересечения вектором направления.

[Igors]

Моделируется прохождение рыбой рыбопропускного сооружения. При этом рыба ориентируется на заданное поле скоростей (структурированная сетка) и на стены сооружения, заданные поверхностями. Поверхности образуются списком треугольников. На выбор направления движения влияют скорость жидкости в данной точки и расстояние до поверхности (стенки) вдоль этого направления. Расстояние ищется перебором треугольников, образующих поверхность и проверкой их пересечения вектором направления.

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

[0...-5]

Моделируется прохождение рыбой рыбопропускного сооружения. При этом рыба ориентируется на заданное поле скоростей (структурированная сетка) и на стены сооружения, заданные поверхностями. Поверхности образуются списком треугольников. На выбор направления движения влияют скорость жидкости в данной точки и расстояние до поверхности (стенки) вдоль этого направления. Расстояние ищется перебором треугольников, образующих поверхность и проверкой их пересечения вектором направления.

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

Сетка к геометрии не имеет никакого отношения - она импортируется из сторонних САПР (в моем случае из Flow3D). В  ее узлах определяются гидродинамика течения.
Геометрия может быть произвольной, о специфичности вряд ли можно говорить. Я понимаю, что это в чистом виде трассировка лучей, просто думал что ее как-то можно распараллелить с помощью GPU и тем самым значительно ускорить процесс.
И еще если говорить о структуризации пространства, то не уместнее ли использовать kd деревья вместо bsp?

[Igors]

Сетка к геометрии не имеет никакого отношения - она импортируется из сторонних САПР (в моем случае из Flow3D). В  ее узлах определяются гидродинамика течения.
Геометрия может быть произвольной, о специфичности вряд ли можно говорить. Я понимаю, что это в чистом виде трассировка лучей, просто думал что ее как-то можно распараллелить с помощью GPU и тем самым значительно ускорить процесс.

Время трассировки одного луча достаточно мало (порядок менее миллисекунды). Поэтому эффективность параллельных вычислений (как CPU так и GPU) зависит от того есть ли у Вас подходящие "кластеры". Например при параллельной трассировке всего 100-200 лучей КПД оказывается слишком низок.

И еще если говорить о структуризации пространства, то не уместнее ли использовать kd деревья вместо bsp?

BSP может хранить один треугольник в неск нодах. Т.е. нод содержит все пересекающие его треугольники. А kd-tree - это просто спуск по массиву (упорядоченному определенным образом), обычно для поиска ближайших точек. Не вижу как его использовать для нахождения пересечений.

Трассировка - хорошо известная, изученная задача. Лучше подобрать хороший алгоритм чем сразу рваться в "крутизну GPU" 

[0...-5]

Сетка к геометрии не имеет никакого отношения - она импортируется из сторонних САПР (в моем случае из Flow3D). В  ее узлах определяются гидродинамика течения.
Геометрия может быть произвольной, о специфичности вряд ли можно говорить. Я понимаю, что это в чистом виде трассировка лучей, просто думал что ее как-то можно распараллелить с помощью GPU и тем самым значительно ускорить процесс.

Время трассировки одного луча достаточно мало (порядок менее миллисекунды). Поэтому эффективность параллельных вычислений (как CPU так и GPU) зависит от того есть ли у Вас подходящие "кластеры". Например при параллельной трассировке всего 100-200 лучей КПД оказывается слишком низок.

И еще если говорить о структуризации пространства, то не уместнее ли использовать kd деревья вместо bsp?

BSP может хранить один треугольник в неск нодах. Т.е. нод содержит все пересекающие его треугольники. А kd-tree - это просто спуск по массиву (упорядоченному определенным образом), обычно для поиска ближайших точек. Не вижу как его использовать для нахождения пересечений.

Трассировка - хорошо известная, изученная задача. Лучше подобрать хороший алгоритм чем сразу рваться в "крутизну GPU" 

Если не трудно, можно ли ссылку на алгоритм построения bsp дерева и на алгоритм трассировки лучей с его помощью? Я в конец что-то запутался...

[Igors]

Если не трудно, можно ли ссылку на алгоритм построения bsp дерева и на алгоритм трассировки лучей с его помощью? Я в конец что-то запутался...

Где тут путаться? Если Вы уверены что нужна именно трассировка - все для Вас очень неплохо. Сам использую свою реализацию BSP, но open-source хватает - погуглите напр "binary space partitioning tree source code"

Просьба цитированием не злоупотреблять (и так понятно о чем речь)