pramithas dhakal Ответов: 3

о том, как вычислить треугольники-кандидаты из сетки

Я пытаюсь вычислить расстояние между точкой и треугольниками в треугольной сетке для обработки столкновений для программного обеспечения CFD.Я уже закодировал для расчета минимального расстояния между определенным треугольником и точкой.Теперь задача состоит в том, чтобы найти треугольники-кандидаты(треугольники, с помощью которых я вычисляю расстояние от заданной точки для возможного столкновения).Что я могу сделать, чтобы найти треугольники-кандидаты?Есть ли для этого алгоритм? что делают программы CFD в этих случаях?Действительно ли они находят треугольники-кандидаты или они находят расстояния точки от всех треугольников в сетке?
пожалуйста помочь..

Stefan_Lang

Точка сама по себе не сталкивается, если она не движется. Вам не нужно находить расстояние до точки, вам нужно найти пересечение траектории, по которой она движется вместе с треугольниками.

pramithas dhakal

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

The_Inventor

Как только у вас есть данные в массиве, будет относительно просто проверить один массив точек против массива треугольников.

Stefan_Lang

Мой ответ был не совсем точен: если ваша цель-проверить, лежит ли точка внутри объекта _solid_, который описывается его внешней поверхностью, то технически вам не нужно знать о траектории точки. Если вы просто хотите знать, столкнется ли движущаяся точка с поверхностью (или движущаяся поверхность столкнется с точкой), то вам это нужно.

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

Смотрите мое решение ниже для получения более подробной информации.

3 Ответов

Рейтинг:
12

Stefan_Lang

Во-первых, вы должны проверить каждый треугольник. Вы можете ускорить эту проверку, построив октодерево, которое разбивает ваше 3D-пространство на управляемые ячейки сетки. (видеть http://en.wikipedia.org/wiki/Octree[^] или google для получения учебных пособий и кода, как его использовать)

Для каждой ячейки окт-дерева можно заранее вычислить, какой треугольник пересекает его, а какой нет. Затем, когда вы хотите проверить точку, просто проверьте, в какой ячейке октодерева она находится, а затем продолжите проверять, какие треугольники, как вы знаете, пересекают ту же самую ячейку: если вы хорошо построили свое октодерево, может быть только 3-5 треугольников, которые вам действительно нужно проверить.

Если вы хотите проверить, находится ли точка внутри твердого тела или снаружи, вам нужно определить линию, проходящую через эту точку. Если точка движется, вы можете использовать текущее направление движения для определения направления линии; это даст дополнительную информацию. В противном случае направление не имеет значения, но вычисления будут проще, если вы используете одну из осей, например (1,0,0).

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

Подсчитайте количество точек пересечения, которые лежат на одной стороне вашей начальной точки вдоль линии. Если это число нечетное, то ваша точка находится внутри твердого тела. Если оно ровное, то оно снаружи.

pramithas dhakal

спасибо за идею восьмеричного дерева набора..Я работаю над этим сейчас...

pramithas dhakal

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

Stefan_Lang

Я сам никогда не реализовывал октодерево, я только планирую подобную структуру, и у меня есть прошлый опыт ее использования. Так что отнеситесь к нижеследующему с недоверием и используйте свое собственное суждение:

Для нахождения соседних частиц, в зависимости от вашего определения соседних, есть два способа и их (dis-)преимущества:

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

2. Определите геометрические измерения диапазона окрестностей (обычно сферы или Куба, центрированного на вашей начальной частице), а затем определите все Кубы, соприкасающиеся с этим диапазоном
- нужно проверить все кубики, чтобы узнать, какие из них касаются диапазона
+ тривиальный код, особенно если вы используете куб для определения диапазона окрестностей
+ возможно, вы сможете найти реализации octree, которые уже содержат такую функцию

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

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

pramithas dhakal

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

Stefan_Lang

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

Я предлагаю вам поискать в google "пересекающийся кубический треугольник", чтобы найти подходящий алгоритм - поскольку я сам никогда не нуждался в таком алгоритме, я не могу дать совет в этой области.

Рейтинг:
1

Member 14901987

I had an almost similar scenario where I wanted to optimize a list of triangles coming from a Tria mesh to check if they were intersecting a cell in my grid. Typically the brute force way of doing it would be to check all triangles in the mesh against all cells in the grid resulting in O(n^2) time complexity if there were n triangles and n cells. Although I'm still looking for solutions, I'm convinced its going to be hidden amongst the different solutions available for "culling" primitives to check during collision detection in Game engines. You might want to look into topics related to Broad phase/range collision detection, Quadtree/Octree, Cell hashing and other related techniques.

Patrice T

Задайте свой собственный вопрос, чтобы получить помощь: https://www.codeproject.com/Questions/ask.aspx[^]
и удалите это

Рейтинг:
0

The_Inventor

Предположим, что x,y,z-это три точки, образующие треугольник, и центр вашей частицы. Если ваша частица имеет объем, то вы добавляете радиус к центру, находите коробку максимумов и смотрите, есть ли там ваш треугольник.