Programming
Game development
Algorithms
Mathematics
Concurrent computing
1 June

Жизнь на частицах 3D

ПривеТ! Решил поделиться с читателями своими небольшими экспериментами с системами частиц в трехмерном пространстве. За основу взял публикацию на Хабре об экспериментах с частицами в 2D пространстве.



Начнем со ссылки на статью которая меня и подтолкнула к действию. Но есть еще одна причина, с недавнего времени все больше перехожу в своих экспериментах на Ubuntu, многое радует начиная со свободной установки ОС и далее по списку плюсов. Минусы есть, у меня это борьба с драйверами при нестандартной установке ОС вроде двух видеокарт и нескольких мониторов.


За основу взял с++, добавил поддержку CUDA как вычислительной платформы, частиц много и центральный процессор явно не справится с такой нагрузкой в реальном времени и графический движок Ogre3D к ним в компанию. Кашу заварили, буду приправлять повествование Gif анимацией и цитатами из статьи о 2D варианте симуляции.


"Сначала я пошёл по стопам игры «жизнь»: у каждой частицы есть счётчик “перенаселения”, который равен сумме обратных квадратов расстояний до других частиц. Если этот счётчик меньше определённого предела, то есть соседей мало, то частица притягивается к другим частицам, а если соседей много — отталкивается. Если частицы пересекаются, то они отталкиваются в любом случае, чтобы не проходить сквозь друг друга.


Случайно раскидываем частицы по полю и смотрим, что выйдет."



Расширенный вариант видео
Теперь немного о логике происходящего в программе. Создается массив частиц с определёнными параметрами. Часть параметров отвечают за физические свойства: радиус, масса, скорость и тд., часть за создание связей между частицами, такими как: тип частиц, кол-во связей частицы с другими частицами и прочее. В среднем использовал в симуляции от 700 до 3000 частиц, так как хотелось считать в реальном времени, большее значение приводило к торможению картинки в следствии роста объема вычислений. Затем все это добро передаётся в память видеокарты, где уже GPU в режиме сильного распараллеливания обрабатывает три основных подпрограммы: симуляция движения частиц, обработка столкновений частиц(соударений) и образование-разрушение связей между частицами.


"Меняем правила игры. Больше не будем считать соседей. Пусть частицы будут просто притягиваться или отталкиваться в зависимости от их типов. Если все частицы одного типа, то тут всего 2 варианта: они либо все отталкиваются, либо все притягиваются."


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



"Не будем сильно менять правила. Вместо этого добавим новую фичу. Теперь частицы на небольшом расстоянии будут образовывать связи. Если частицы связаны, то они постоянно притягиваются друг к другу. Это притяжение не ослабевает с расстоянием. Но, если расстояние выше определённого порога, то связь рвётся."


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



Расширенный вариант видео


или в виде картинки



Далее начался процесс проб и ошибок. Во первых программирование на GPU требует дополнительной внимательности в части так называемого "races on read-modify-write of shared data", что означает что могут быть проблемы когда несколько потоков одновременно пытаются изменить переменную. Возникают нестабильности вроде таких:



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



расширенная версия видео


Как говорится если не куб, то пусть будет шар:



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


__device__ static int Links[3][3] =      {{1,0,1},{1,0,0},{1,1,0}};
__device__ static int LinksField[3][3] = {{0,0,0},{0,0,1},{0,0,0}};
__device__ static int LinkTypeSize[3] =  {3,8,2};
__device__ static int LinkTypePP[3][3] = {{0,1,1},{8,1,6},{0,1,1}};

Привел кусочек кода как есть, это матрицы взаимодействия трех типов частиц друг с другом.
-первая строчка это принцип образования связей: 1 есть возможность установить связь с другой частицей, 0 соответственно нет.
-вторая строчка- это закон притяжения отталкивания частиц. По сути в этом варианте все отталкиваются друг от друга, кроме притяжения второго типа частиц к третьему. Можно конечно зеркалить матрицу, но в данном случае так.
-третья строчка количество общих связей частиц по типам.
-четвёртая это количество связей частицы с каждым типом частиц.Первый тип например сам с собой не может образовать связь.


Получаем частицы в сильном броунском движении:



расширенная версия видео


Пришлось вводить потерю энергии при столкновениях.



расширенная версия видео


Стало слишком все статично, уменьшаем силы взаимодействия частиц.



расширенная версия видео


Если посмотреть видео видно как происходит постройка каркаса. Потом он остаётся все равно статичным.


Меняем правила в части коэфф матриц.



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



Еще одно видео, демострирует что будет, если в динамике менять длину связей между частицами, со второй минуты видео это особо выраженно.



Но надо попробовать повторить вариант 2D автора, чьи цитаты в теле статьи. Есть вариант такой "жизни":



или такой



Что можно добавить? Во первых Исходники программы. Во вторых на хабре есть несколько статей с описанием клеточных автоматов или пободных систем(в теории клеточный автомат является эквивалентом машины Тьюринга) с вынесенным заголовком включающим слово "жизнь", поэтому и решил тоже использовать его, вроде как традиция. Хотя это скорее просто каледоскоп, простые правила порождают сложное поведение, как частицы и система зеркал в детской игрушке.


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



Надеюсь кому-то понравится и он шагнёт из 3D дальше, как автор шагнул из 2D. Главное для себя повторил уроки по CUDA и Ogre3D под Ubuntu.



И еще будут идеи пишите, может что интересное придумаем :)


+49
7.3k 70
Comments 21
Top of the day