Teaching myself C so I can build a particle simulation

Source: Teaching myself C so I can build a particle simulation, Michael Richardson, 11:52, uploaded 2024-05-01, playlist index 169.

Michael Richardson starts with a small embarrassment familiar to anyone who has built a beautiful prototype before asking it to do more work. A video by Pezza shows a polished two-dimensional simulation of colliding particles. Richardson tries to make a three-dimensional version in Python with help from ChatGPT. Python reaches a few hundred particles, whilst Pezza’s example handles around 100,000. Several optimisations and algorithms fail to close the gap, so Richardson rebuilds the project in C and uses the process to get a better feel for computer simulation.

From Euler to Verlet integration

The first model treats movement as a sequence of small updates. The program calculates a particle’s displacement over a fixed time interval, adds it to the current position, updates the velocity, and repeats. Richardson calls this the Euler approach. It is simple and fast, yet the small errors accumulate as the simulation continues.

He returns to Newton’s kinematic equation, which relates an object’s current position to its initial position, velocity, acceleration, jerk, and further terms. A little calculus produces another equation in which velocity disappears. The program keeps the current position, the previous position, and the acceleration, along with an error term that Richardson presents as an improvement over Euler’s quadratic error. This is Verlet integration, the method around which the rest of the project is built.

The C translation uses a class-like structure for each Verlet object. Richardson stores the three values from the equation and adds a radius for collision checks and rendering. The update method follows the formula closely, although he jokes about writing the code in an obscure style. A first run lets the particles move from frame to frame and keeps them inside a spherical boundary through a distance check.

The first result exposes a missing part of the model. The particles can pass through one another because the simulation has movement without collision detection. For two spheres, the fix is direct: calculate the distance between their centres, compare it with the sum of their radii, and push the spheres apart when they overlap. Richardson adds an attractive force triggered by a keyboard press, which gives the small system something to do beyond falling into the walls.

The cost of treating every particle as a neighbour

The simple collision method works for a handful of particles because it compares every particle with every other particle. Its cost rises quickly as the population grows. Richardson also finds a separate rendering problem. The program draws every sphere as an independent object, so each frame sends model data from the CPU to the GPU and makes a separate draw call for each particle.

He first tests collision methods he finds online, including a KD-tree implementation. The results bring no meaningful improvement, so he drops that route. The useful change comes from the simulation’s coordinate system. Richardson overlays a grid on the scene and assigns each particle to a cell. Each cell checks its own particles and the particles in neighbouring cells, which removes comparisons with objects that are too far away to collide. A particle alone in a corner has little work to do. A dense cluster still receives close attention. This change doubles the population to about 2,000 particles.

The rendering bottleneck needs a different kind of change. With 100 particles, the program sends 100 packets of model data to the GPU and makes 100 draw calls every frame. Richardson stops the simulation so that the distinction becomes visible: the scene runs faster when the particles stay still because the repeated CPU-to-GPU communication has ended.

Instanced rendering moves the repeated work into a single draw. The program packs all particle positions into one array, sends it to the GPU once per frame, and sends one copy of the model data. The GPU uses that model to render each instance at its position. Richardson reports more than 8,000 simultaneous particles after this change.

The grid also makes a third optimisation possible. Since cells can compare their particles and neighbours with limited dependence on distant cells, the work can be divided among worker threads. Richardson imagines a five-millisecond collision pass divided among five threads and hopes to approach one millisecond. The finished version reaches around 11,000 particles at 60 frames per second before another bottleneck takes over. He leaves the remaining bugs and optimisations for a later video. Performance work has moved the bottleneck to another part of the system.

Colour as a reading of motion

Once the base simulation runs, Richardson uses the particle data to change what the viewer can see. In the fragment shader, the small GPU program that determines a pixel’s colour, he defines a light blue and a dark red. A value derived from each particle’s velocity is clamped between zero and one, then used to interpolate between the colours. Slow particles remain close to blue. Fast particles move towards red.

The effect turns velocity into a visible property of the field. The simulation already contains the value, yet the shader gives it a place in the image without adding another object or a separate measurement display.

Distance constraints and accidental geometry

Richardson returns to the Python version to prototype links between particles. The smaller population makes experiments easier, and the link count remains low enough that C’s performance advantage matters less. A link keeps two particle centres at a fixed distance, using the same distance calculation that resolved sphere collisions.

The constraint works on the first attempt. Rendering it in three dimensions proves harder because the link needs the right orientation and rotation. Richardson finds a linear algebra book in a thrift store and uses its treatment of change of basis to solve the problem. The finished example contains a small surprise. He asks four particles to remain equidistant from one another, and the system settles into a tetrahedral arrangement without receiving that shape as an explicit instruction. The geometry emerges from the constraints.

The same approach produces larger structures. An icosphere starts with a twelve-vertex base model. Richardson divides each face into four smaller triangles, projects the new vertices onto a sphere, and repeats the process to increase the resolution. Linking the particles alone makes the structure collapse, so he uses the ideal gas law to calculate the centre of the particle group and apply outward pressure. The result stays inflated.

A trampoline follows from the same ingredients. Particles form a grid, links connect neighbouring points, and fixed corners hold the surface in place. Richardson ends with several less defined creations built from the same constraint system.

Limits of the demonstration

The video records an implementation path with informal benchmarks. Richardson gives the particle counts and frame rate reached at each stage, whilst leaving hardware, compiler settings, scene dimensions, timestep, and exact comparison conditions unspecified. The figures show what his project achieves in the recorded setup. They do not establish a general ranking of Python, C, grid collision detection, instanced rendering, or worker threads.

The transcript also comes from YouTube’s caption tracks, which contain small recognition errors around terms such as Euler, instanced rendering, and icospheres. The equations and code are presented in the video itself, whilst the description supplies the implementation repositories and references. The note follows the source’s explanation and keeps its informal claims within the evidence available here.

Richardson says that he began the project more than a year before making the video and had left it unfinished. The conclusion therefore returns to the pleasure of the unfinished system. Verlet integration can support much more than this one demonstration, and entire games have been built around related physics. The project remains open because every successful optimisation exposes another place where the model, renderer, or data flow could be changed.

Further reading / references

• Pezza’s video, the two-dimensional particle simulation that prompted Richardson’s project.
• Verlet Algorithm, linked in the video’s description.
• Verlet Integration, another source linked in the description.
• Icospheres, the description’s reference for the recursively subdivided sphere model.
• C implementation and Python implementation, the repositories Richardson provides for curious viewers.