Bubbles Demo
Introduction
This project was started somewhen in 2009.
Unlike most C++ code I’ve wrote during the recent years, this one was developed mostly for fun. So no design goals, just something fun to create, and possibly to showcase while interviewing for a new job.
I’ve used some parts of the code, namely VsTabs, UnitTest and RGBA image viewer, in the real projects I did for money, and I think they proved to be useful.
You'll find the source code, build instructions, and source code overview in the separate article "Bubbles Demo: Technical Details".
The Bubble Model
When I was a kid studying (among other useless things I was interested in) crystallography, I read about the bubble model for the 2D crystal structure.
First you mix soap & water. Then you create many bubbles in the water, 1-2mm each, all bubbles being the same size. You’ll need e.g. to borrow an electric air compressor from your aquarium fishes, to achieve uniform air flow. Wait for bubbles to come to the water surface. Don’t create too many bubbles: the single layer of the bubbles should only occupy half of the water surface. Then watch the bubbles group together and form the hexagon lattice, solely due to the surface tension forces acting between them. Meditate on that picture. Then use something like 2 plastic cards to simulate the forces applied to the crystal, and watch how the structure behaves when stressed: the lattice is not being deformed, instead the crystallographic defects appear, and travel across the structure.
When I’ve got nothing more interesting to do, planning to learn Direct3D 9 API by coding something funny, I’ve recalled that soap bubbles. Actually, the Windows Vista’s built in screensaver remind me about it.
Unfortunately, I’ve got no idea what exactly was the book I’ve read that. I do remember the experiment description, and a few grayscale photos of the water surface with bubbles. However the idea looked reasonably simple, the simulation result seemed to be reasonably beautiful, and Wikipedia knew more than enough about the Lennard-Jones potential to implement that in C++ code.
Simulation
To make the experiment interesting, we’ll need a lot of bubbles.
For this task, I’ve defined “a lot” as “at least 1-2k of them, the more the better”.
Theoretically every bubble interacts with every other bubble. For every calculated frame, if the water surface contains 2k bubbles, it gives 4M interactions. It was clear some serious optimization tricks were required for the model to work in the realtime.
The idea behind spatial cache container is simple. First I split the infinite XY plane into the uniform square cells. For my 2D case, I use the ATL’s CPoint class (which is basically a 2D vector of integers) to hold the cell coordinate.
Then I use the hashmap that maps integer cell coordinates to the set of elements contained within the cell. This way the space is almost unlimited (if you just thought about integer limitations and thus 1.8·1019 total cells count, just use 64-bit integers for your task), while empty cells consume no RAM at all.
The elements itself are stored in the linked list, grouped by the contained cell. You might switch to array instead of the list: this gets you much more cache friendliness for the price of massive MoveMemory operations each time an element being created or destroyed, or when an element crosses its cell’s boundaries.
Remember however, that unlike crappy open source lists, the good list allocates elements in large chunks, thus effectively localizing the elements even when they are constantly created and destroyed during the application’s lifetime. Given that several MB cache sizes of the modern CPUs, I think my choice is rational.
And by the way, I tried to switch from CAtlList to the std::list. The overall framerate, that was about 18 FPS with good containers, is now only 15 FPS. I’d like to stress it: the STL collections are bad. In some cases, you can get +20% overall application performance by switching to the functionally equivalent ATL template collection. Besides, it’s possible (and not that hard) to use ATL template collection classes, and still write exception-safe C++ code.
I didn’t try to use hash_map instead of the CAtlMap. I believe I’d get even more dramatic results if I did.
First of all I limited the interaction distance. By using something what I’d like to name “the spatial cache” (see the “CBubbleContainer.hpp” for the template container implementing the approach), I’ve divided the plane into the set of cells, so I was able to dramatically limit the set of the bubbles in need for the interaction processing. For example, imagine you’ve got 5000 bubbles. Without the spatial cache, each bubble interacts with 4999 other bubbles. When using the cache, if there’re 20 bubbles in the average cell, then average bubble only interacts with 179 other bubbles: 19 in its own cell, and 160 more in the 8 adjacent cells.
Then, for simplicity I supposed the bubble’s mass is zero. This is very close to true for soap bubbles.
And I’ve kept in mind the Newton’s 3-rd law, so the force that bubble A acting on bubble B is the same as bubble B acting on bubble A.
These measures resulted in the reasonable 18 frames (=simulation steps) per seconds for 5000 bubbles, on my old Core 2 duo 6300. BTW, when I build the same source code as the 32-bit binary, the figure is only 14 FPS, that’s why I strongly encourage everyone to install 64-bit operating systems, and port the software to the 64 bit.
You’re welcome doing your own experiments yourself.
The force of interaction is calculated by the CSoapBubblesSim::BubbleSim::GetForce method. The 2D vector values for all bubbles are summed up for every bubble. Keep in mind this function is called many times for each bubble for each frame, so you better only use simple math there or the simulation will slow down because of the CPU load.
The force is converted to the bubble’s movement in the CSoapBubblesSim::BubbleSim::ConvertForceToMovement method. To bring a bit of stability to the model, the maximum movement length is limited for any given frame.
No user-controllable deformation is currently implemented.
I think if you’re doing science professionally not recreationally, you might be able to dramatically improve the underlying model in order to make it behave much closer to the real-life crystals. I suspect the price will be the CPU and RAM usage, though :-)
Simulation Results
Here's a typical screenshot (click to see the larger image with some notes added in Photoshop). And by the way, you can inject bubbles with left mouse button, clear bubbles with right mouse button, zoom with mouse wheel, and scroll the view by moving the mouse with the middle button pressed. There’s also some rudimentary UI to manage the bubble’s coloring, which opens when you press the tab key.
On the screenshot, the color hue represents the count of the adjacent bubbles. This count is 6 for red bubbles. The color value (=lightness) represents the bubble’s momentary energy.
Further Optimizations
Parallel the simulation to use many CPU cores: I expect on my code 2 duo the resulting frame rate will improve at least by 75%, saying nothing about the newer i7 CPUs. One way to do that – split the 2 ‘for’s in the CSoapBubblesSim::ProcessInteractions function between different threads. You should also redesign the CollectCellBubbles, ProcessInteractionsAcrossBuffers and ProcessInteractionsWithinBuffer functions, so they only write to local data storage, and then flush the changes at once to the main bubble store. This way you’ll only need to lock the bubble store for very small amount of time, thus decreasing time the threads spend waiting for a critical section.
Split the bubbles array info the 2 arrays: one containing all the information needed while the simulation step (i.e. position and force), another containing stuff like colors & average energy, that only needed once for each bubble. This will improve cache friendliness a lot.
Disclaimers
It’s impossible to create a good product without requirements written carefully. While in this case not only I didn’t create any project documentation, but this “project” seems to have no goals other then entertaining me, the only developer.
The project is not finished. It’s not even an alpha version. It works on my PC. There might be both minor and major glitches, or it might even not work at all, on your PC.
Not each part of code is tested equally. For example, the Direct3D windows class is extremely hardware and OS-dependent by its nature, while I only tested it on my 2 PCs and on my netbook.