Нужен совет по 3D физическому моделированию - многогранники

[Azzi]

Делаю моделирование роста зерен на основе геометрической модели. Каждое зерно - гексагональная призма, но можно искать решение и для общего вида выпуклого многогранника. Задается исходное распределение зерен в пространстве. Каждый шаг зерна подрастают в размере и проверяются на пересечение друг с другом. Если есть контакт, то нужно максимально грамотно их развести, с расчетом компонент вращения и трансляции как если бы было упругое соударение + трение вязкой среды. Не хочется изобретать велосипед, т.к. думаю, что алгоритм столкновения двух многогранников уже где-то есть. Все пишу в VC++ Win32. Если у кого есть ссылки на литературу или код подобного физического моделирования, либо по геометрическим моделям роста зерен поделитесь, пожалуйста.

[yocto]

Моя любимая книга на сей счёт:

"Mathematics for 3D Game Programming & Computer Graphics"
by Eric Lengyel (ISBN 1-58450-037-9)

Там есть практически всё, что нужно, начиная с азов линейной алгебры, в том числе и про polygon collisions.
В последнее время я очень много писал для движка WireFusion (www.demicron.com) и нахожу его очень удобным для моделирования, так как многое там уже решено. Если с C++ знаком, значит и на Java тоже будет не сложно. Удобство - работает во всех броузерах, хотя можно строить и standalone apps. Понимает vrml модели и из всех движков, что я исследовал, является самым шустрым.
Если нужна помощь - спрашивай.

[Azzi]

Спасибо, посмотрю книгу. В разработке 3D игр много подобного, но они часто грешат множеством допущений, которые неприемлемы в физ. моделировании. Может, есть хорошая библиотека типа Rigid Body Dynamics Simulators ?
На Java пересаживаться не буду, т.к. написал уже много на C++, в том числе графическое отображение зерен (OpenGL) и collision detection, теперь чешу репу как эти столкновения обрабатывать. К тому же скорость вычислений важна (для, скажем, 1,000,000 зерен), а C++ пошустрее будет.

[yocto]

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

Конечно, если готовый код есть, то выбрасыват жалко. Тем более, эта книга полезна будет. Математический аппарат там рассматривается абсолютно серьёзный, мне эта книга очень помогла освежить всё, что мне было нужно.

[Angry]

А нельзя ли по подробней о задаче? Может стоит использовать более простые fakes? Например, заанимировать рост зерен отдельно? Или же размер и положение зерен пусть считает одна функция.

Упрощенный пример - растут два шара рядом - расстояние мужду ними автоматически 2R. И нафиг тут не нужны collision detection. Или я чего-то не понимаю?

[yocto]

Упрощенный пример - растут два шара рядом - расстояние мужду ними автоматически 2R. И нафиг тут не нужны collision detection. Или я чего-то не понимаю?

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

Хотя апроксимация сферой действительно часто применяется, но только для того, чтобы избежать интенсивных вычислений для геометрий, которые гарантированно не пересекаются.
Строго говоря, даже сама задача нахождения bounding volume для произвольного набора вертексов уже сама по себе нетривиальна и жрёт ресурсы изрядно.

[Angry]

Упрощенный пример - растут два шара рядом - расстояние мужду ними автоматически 2R. И нафиг тут не нужны collision detection. Или я чего-то не понимаю?

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

Хотя апроксимация сферой действительно часто применяется, но только для того, чтобы избежать интенсивных вычислений для геометрий, которые гарантированно не пересекаются.
Строго говоря, даже сама задача нахождения bounding volume для произвольного набора вертексов уже сама по себе нетривиальна и жрёт ресурсы изрядно.

Для realtime графики используют для определения столкновений: прямоугольный пар-пипид, сферу, конус, цилиндр... все Остальное слишком сложно (долго).

Я думаю, автор топика неправильно поставил задачу. Collision Detection используется, когда неизвестно заранее направление движения объектов.
У него не тот слуай

[yocto]

Я думаю, автор топика неправильно поставил задачу. Collision Detection используется, когда неизвестно заранее направление движения объектов.
У него не тот слуай

Да, наверное. Но у него частный случай, он же сам сказал - гексагональная призма.
Можно даже свою оптимизацию создать, именно для этой призмы.
Наверное, пересечение отрезка и плоскости даже подойдёт. А для быстрости - апроксимировать цилиндром, если, конечно, призма правильная.

[Димма]

Делаю моделирование роста зерен на основе геометрической модели. Каждое зерно - гексагональная призма, но можно искать решение и для общего вида выпуклого многогранника. Задается исходное распределение зерен в пространстве. Каждый шаг зерна подрастают в размере и проверяются на пересечение друг с другом. Если есть контакт, то нужно максимально грамотно их развести, с расчетом компонент вращения и трансляции как если бы было упругое соударение + трение вязкой среды. Не хочется изобретать велосипед, т.к. думаю, что алгоритм столкновения двух многогранников уже где-то есть. Все пишу в VC++ Win32. Если у кого есть ссылки на литературу или код подобного физического моделирования, либо по геометрическим моделям роста зерен поделитесь, пожалуйста.

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

Можно считать расстояние до плоскостей многогранников по вектору скорости вершин, как только оно меньше определенного threshold'а - прикладывать упругую силу к вершине многогранника (с подсчетом моментов и прочей rigid body dynamics). По сути - прилепить по упругому шару на каждую вершину и считать пересечения этих шаров с гранями.

[Azzi]

Я видел в одной из моделей представление многогранника набором шаров. Но у меня правильная гексагональная призма - простая симметричная фигура, 12 вершин, 18 ребер и 8 граней, и не вижу смысла в аппроксимации шарами.
Почему collision detection не нужно? Я не понимаю. А как еще находить точки касания? У меня это реализуется применением фильтра bounding spheres на поиск потенциальных соседей, а потом проверкой пересечения каждого ребра одного полигона с каждой гранью другого с запоминанием координат пересечения.
Попробую рассказать поподробнее. Моделируется рост кристаллов конструкционной керамики из расплава. В каждый момент времени кристаллы неподвижны в пространстве и только растут в размерах, если окружение позволяет. Они не могут свободно двигаться, т.к. находятся в окружении мелких кристаллов и нерасплавившегося порошка (не учитываются в модели) и вязкой жидкости-расплава. В случае контакта двух таких кристаллов, они перемещаются в направлении наименьшего сопротивления, чтобы иметь возможность расти дальше.
Вероятно, можно сделать какие-то допущения, чтобы упростить модель свободно движущихся в пространстве многогранников.

[Angry]

Я видел в одной из моделей представление многогранника набором шаров. Но у меня правильная гексагональная призма - простая симметричная фигура, 12 вершин, 18 ребер и 8 граней, и не вижу смысла в аппроксимации шарами.
Почему collision detection не нужно? Я не понимаю. А как еще находить точки касания? У меня это реализуется применением фильтра bounding spheres на поиск потенциальных соседей, а потом проверкой пересечения каждого ребра одного полигона с каждой гранью другого с запоминанием координат пересечения.
Попробую рассказать поподробнее. Моделируется рост кристаллов конструкционной керамики из расплава. В каждый момент времени кристаллы неподвижны в пространстве и только растут в размерах, если окружение позволяет. Они не могут свободно двигаться, т.к. находятся в окружении мелких кристаллов и нерасплавившегося порошка (не учитываются в модели) и вязкой жидкости-расплава. В случае контакта двух таких кристаллов, они перемещаются в направлении наименьшего сопротивления, чтобы иметь возможность расти дальше.
Вероятно, можно сделать какие-то допущения, чтобы упростить модель свободно движущихся в пространстве многогранников.

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

[Azzi]

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

А я так и делаю. Каждый кристалл - отдельный объект с коодинатами центра, размерами и положением в пространстве, и со своей функцией прорисовки. Хранить местоположения вершин тоже не занимает много места, и пересчитать легко при изменении каких-то параметров. Каждый кадр рисуется заново, исходя из текущих параметров объектов, вызывая метод прорисовки у каждого кристалла по очереди. Визуализацию можно и отключить, или прорисовывать, скажем, каждый 100-й шаг.

[Димма]

Я видел в одной из моделей представление многогранника набором шаров. Но у меня правильная гексагональная призма - простая симметричная фигура, 12 вершин, 18 ребер и 8 граней, и не вижу смысла в аппроксимации шарами.

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

[Azzi]

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

One grain at a time. Рассматриваем только по два кристалла за раз - "наш" кристалл и по очереди те, что с ним в контакте. Ансамбли - это слишком сложно.

[Azzi]

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