logo

part3d


Important Note!

part3d is no longer being supported, as it has been superceded by an arbitrary-dimensional version called Part-ND. Please see that page for the most recent version of the code. Part-ND will still perform all of the computations seen on this page.

Introduction

part3d is a stand-alone particle system program written in ANSI C mostly for my own amusement. It utilizes an octree system for heirarchical space subdivision and can simulate a variety of forces and boundary conditions. There is an input file that is fairly self-explanatory, but there are no guides to help the user choose appropriate parameters for the various constants. Trial and error was how I made it this far. The strand constants are especially difficult to choose. Anyways, on with the page.

Files

You can download the code here: part3d_v1.1.tar.gz. This is version 1.1, which corrects version 0.9's bug that created incorrect particle force results, and some bugs in 1.0, too. In addition to bug fixes, there are a few more enhancements.

Features

So far, part3d has the following features:

Future versions of part3d may address the following needs:

Examples

But, despite all that, the program is capable of making some silly little animations, which you can click upon to view:

20,000 particles in a galaxy-forming gravitation simulation; animation is a 564 KB aGIF
32,000 particles in a galaxy-forming gravitation simulation; animations are 2.5 MB and 9.4 MB MPEGs
100,000 particles falling from initially loosely-placed positions; animations are 256 KB aGIF and 960 KB MPEG
A gravitationally-clumped group of 1000 particles being hit by a single particle with a high density (10 times) and at a very high velocity (10 times escape velocity), extremely high damping case
Same as above, high damping
58 particles in a simulation of a computational strand; animations are 48 KB aGIF and 250 KB MPEG
64 strand simulation in a strange initial formation; animations are 100 KB aGIF and 533 KB MPEG
A 1000-particle moon impacting a 10000-particle planet; animations are 230 KB and 750 KB MPEG-1

Programming notes

It isn't very difficult to write a computer code to perform these calculations. The only real complexity is in creating a method to quickly calculate the forces on one particle from all of the other particles. Here is the simple method:

First, create a data structure for your particles. Feel free to include any rendering parameters you like, because they won't affect the simulation. Include a three-vector for position and velocity: x[3], u[3], and floats for mass and radius. Note that the code is easier to write if you give all of your particles the same radius.

Second, you need to write a routine to march through your particles and find the forces or accelerations on each one. Remember, the acceleration is just the force divided by the particle's mass, so one is as good as the other. This subroutine is where you include forces due to particle gravity ( F = G * m1 * m2 / d^2), universal gravity (F = mg), particle contact (F = -k * penetration), and others.

Once you determine the accelerations on all of the particles, multiply them by the duration of the time step, and add them to the velocities. Update the positions in a similar manner.

Keep in mind that the naive approach of calculating forces (nested iteration through the complete particle lists) produces a method that is of order N-squared, or a doubling of the number of particles makes the code run four times slower. A good method to use to get around this poor scaling is called octree space subdivision. I won't go into the details on this page, but you should be able to find many resources on the web describing the technique. The essence of it is that you clump particles together as one virtual mass when computing the effect of that clump of particles on a particle or clump of particles far away. part3d uses a method that does this.

Revision history

part3d_v1.1.tar.gz minor bug fixes
part3d_v1.0.tar.gz correct force calculation, many bug fixes, better output handling, other enhancements
part3d_v0.9.tar.gz merged spaghetti and gravitation codes, GPL'd

References

J.E. Barnes and P. Hut, A heirarchical O(N log N) force calculations algorithm, Nature 324, 446 (1986)


Mark Stock, PhD Candidate, University of Michigan, Ann Arbor
Page last modified 2005-02-09