Yeah I assumed this when I noticed even the Retina laptops with the i7s weren't doing as well. I have an Nvidia GTX 560 Ti which must be doing most of the work.
It looks like there's some sort of gravity involved. So then how do you get around the O(n^2) problem of comparing the contribution of each particle to every other particle? Did they implement an quadtree of some sort, or is it something else?
I'm wondering what optimization you can to that do with a quadtree. The only way I can see is if you sacrifice accuracy on distant particles by quantizing and counting. You could use geometric hashing to do the same thing.
Anyway, I don't think this demo is exhibiting inter-particle attraction, but I'm not positive.
It looks like it's using a fluid solver. So, it's not that every particle is interacting with every other particle, but that there's a flow vector being established at each point on the screen and that's being added to each particle's position.
Disclaimer: I haven't actually analyzed the source.
Galaxies would require coupling of the particles, interactions through gravity... this would kill the efficiency of the solver. N-Particle simulations are always O(N^2) (or more).
It's not cutting off. It's replacing many long-range effects with a single one weighted more (and done it carefully so that the floating-point error is literally smaller than you could tell).
There's even better methods that take O(n) time, like the fast multipole expansion ones.
Btw this goes into numerical analysis, and O(-) is important but so is error convergence. I imagine these big-O figures are for a constant error, but I figure the asymptotic may change behavior as the other parameter changes.
One could also use FFTs and the particle-mesh method or a TreePM method. Basically, the particle masses are deposited on a fine mesh. Poisson's equation gets solved using FFTs and then the particle accelerations are computed by interpolating on the gradient of the potential field.
You could potentially do better than N^2 (ish) by approximating. Quantize the world into a grid, add up mass at each grid point. Then each particle is affected by this weighted grid, which is made up of a relatively small number of pseudo-particles.
Of course, you'd still need to fall back to N^2 for the nearest particles, or the accuracy would be unusably bad. But it's a much smaller N.
I moved the mouse very slightly at the edge, which caused all the particles to eventually settle in two separate spinning groups. Then I started making fast circles around one of the groups, and once the group started following the pattern, added a slowly moving center of rotation towards the other undisturbed group. This caused it to slowly move towards the stationary one, until they collided, each ripping from the other, until they merged.
The frame rate is incredible given the number of particles. JavaScript interpreters really have come a long way.
The frame rate for JS particle simulation beats the frame rate you get when you tell a browser to append content, which is usually native C/C++ optimized to death.
To the author: great work. It looked very much alive on my screen when I first loaded the page.
WebGL (or OpenGL ES) is not written in JS (obviously). JS calls into it, but the heavy lifting is being done by a native library. Calling this a "particle generator in javascript" is somewhat disingenuous.
WebGL is just a JavaScript API specification that exposes an OpenGL-like interface to scripts running within a webpage. The calls that your JavaScript makes to WebGL functions are translated behind the scenes to actual OpenGL calls (although, it doesn't have to be opengl, i think IE uses directx under the hood). Both opengl and directx are API interfaces that allow you to talk to graphics hardware.
Graphics hardware is incredibly fast and programmable (via shaders), and now that WebGL is part of the standard, Javascript programs can actually use the hardware's capabilities. What we see in a lot of this demos is not the javascript interpreter being fast. Although chrome's V8 actually is fast (compared to other js implementations at least), most of the work is being done by the video card.
Firefox and Safari JS compilers are actually fast too. Even faster than V8 in some cases.
For example, I was surprised to find out recently that Firefox 25 is smoother and faster nowadays than Chrome on Mac Os X when running my interactive geometry genereator that is based on javascript/canvas (http://GeoKone.NET).
The Javascript uses the WebGL library to compile and upload a piece of native code called a shader to the graphics card. The graphics card is then instructed to run the shader, which produces the image buffer, the image buffer is rendered directly to the screen.
Does anyone have the theoretical description of what is happening? I'm curious about the fractal patterns being generated and the increasing in entropy and the that results in a catastrophic failure of the stable system. Is this some kind of chaotic system or is just an force field being applied on the particules.
half a million particles are rendered to a texture, which is then blurred, and the gradients are used to update the velocity of the particles in a feedback loop. There's no direct interaction between individual particles. There are two words to describe the haphazard in the behavior. Use Google or Wikipedia to learn about "dissipative systems" and "stigmergy".
The much beloved Plasma Pong for older versions of Windows can still be found on the 'net. It did something similar, and I spent quite some time playing in its sandbox.
Took me a long time to notice that my cursor movements were injecting disturbances into the fluid. What physical laws govern these points, and how is the cursor perturbing them?
I agree. Does anyone know of a website that is just people posting really cool, short code snippets? Things like "Here is a checkers AI in 50 lines of Python" or "Here is a Neural Network in 30 lines of Perl".
90 comments
[ 3.0 ms ] story [ 157 ms ] threadIt's pretty slow on my computer. Would ASM.js work better?
It uses OpenGL ES it seems, doesn't work in IE 11.
Edit: It would be interesting to know if this would perform better using WebGL and running it in IE 11, anyone has any thoughts on that?
&
22 FPS on Firefox..
It's gorgeous... reminds me of the good old "visualization" days of Winamp and MusicMatch
Anyway, I don't think this demo is exhibiting inter-particle attraction, but I'm not positive.
http://en.wikipedia.org/wiki/Barnes%E2%80%93Hut_simulation
Disclaimer: I haven't actually analyzed the source.
Also, a way to reset the simulation without reloading the page would be nice.
There's even better methods that take O(n) time, like the fast multipole expansion ones.
Of course, you'd still need to fall back to N^2 for the nearest particles, or the accuracy would be unusably bad. But it's a much smaller N.
To the author: great work. It looked very much alive on my screen when I first loaded the page.
EDIT: I assume the "native-code" part is something like webgl?
Graphics hardware is incredibly fast and programmable (via shaders), and now that WebGL is part of the standard, Javascript programs can actually use the hardware's capabilities. What we see in a lot of this demos is not the javascript interpreter being fast. Although chrome's V8 actually is fast (compared to other js implementations at least), most of the work is being done by the video card.
For example, I was surprised to find out recently that Firefox 25 is smoother and faster nowadays than Chrome on Mac Os X when running my interactive geometry genereator that is based on javascript/canvas (http://GeoKone.NET).
Three.js also has some pretty nice to follow particles samples:
http://threejs.org/examples/#webgl_particles_random
http://threejs.org/examples/#webgl_particles_sprites
http://threejs.org/examples/#webgl_buffergeometry_particles
Using Version 31.0.1650.57 m Google Chrome is up to date
It complains about the lack of an OpenGL extension, but it looks fine.
https://www.shadertoy.com/
It'd be nice if the color gradually changed.
I've had a look here: http://creativejs.com/2013/11/coupled-turing-pattern-and-219...
but there's no details on the specifics