part3d

Important Note!

Introduction

Files

Features

• Automatic and adaptive octree space subdivision allowing O(NlogN) long-range force computations
• N-body gravitational forces (Barnes and Hut opening criterion) with delta-smoothing (Krasny's delta parameter)
• Hard-sphere contact forces, with contact-axis and contact-plane damping
• Constant-vector gravitation force
• Strand-connectivity forces, compression/tension and bending
• Hard or open boundaries
• 2-d or 3-d density field construction
• Raw and Radiance output for particle locations
• png, gif, pgm output for particle locations and density field
• Time-saving check that runs many more contact time steps than gravitational time steps

Future versions of part3d may address the following needs:

• Arbitrary number of dimensions
• Better controls on stability (currently uses a 1st order Euler forward integrator)
• Adaptive time step
• Rotations in N-space caused by contact friction
• Setting for molecular (r^-6 or r^-12) forces
• Spring-like attraction forces
• Electrodynamic forces
• Periodic boundaries
• Read and write a raw binary file

Examples

	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

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

References