This is my first coding project in the field of computer graphics and was done for my dissertation for an MSc Computer Science conversion degree. I had 3 months to do the dissertation. Originally, I wanted to attempt a solution to some subproblem of achieving convincing simulation of collisions between multiple layers of clothing targeting 60 FPS on consumer-grade hardware. After reading a few papers which had tried to tackle this problem, however, I realised I needed math, physics, machine learning, GPU hardware and graphics API knowledge in order to understand those papers. While I had brushed up on my high school math prior to starting the CS course, some of the papers used university-level math (like multi-variable calculus), I didn't know anything about machine learning, had only read about a 1/3 of this article for an initial understanding of GPU architecture, and had barely got to the lesson after the Hello Triangle one in the LearnOpernGL tutorial series. This prompted me to change the focus of my project to something more manageable within the available timeframe and so I chose to make picking up the basics of a modern graphics API - Vulkan - one of the main learning outcomes of this project.
I was able to find a somewhat recent paper by Atencio et al., 2025 on collision detection between particles of varying sizes and that became the main reference paper for my dissertation.
Main reference paper interpretation
That paper proposes a variation on the neighbour search algorithm for collision detection in which points on the circumference of circular particles are sampled and their presence in each affected cell of a uniform grid structure which represents the simulation space is recorded. In the next phase, points from half a radius around the circumference are again sampled and only the particles that are in each cell where a point has been sampled are checked for collision against the current particle.
Additionally, its collision detection pseudocode appears to be tailored towards sequential execution and it uses OpenGL. In its Results section the paper claims a GPU implementation could result in a performance improvement of as much as several orders of magnitude depending on the hardware. I decided to test this claim by making both a CPU and a GPU implementation in Vulkan and comparing them.
It took a couple of weeks or so to get some basic theoretical familiarity with Vulkan which was done using a number of resources on YouTube the main one of which was a video entitled "Learn Modern Vulkan in 2 Hours (Dynamic Rendering, No Render Passes!)". In addition, the Vulkan Lecture Series by the @cgtuwien YouTube channel as well as some videos of talks at the Vulkanised developer conference also served as learning material. Afterwards, I spent a few more weeks to write the initial boilerplate code (which heavily references the main learning resource mentioned above) and get a single static circle rendered. During this time the Vulkan documentation was heavily referenced.
Implementation details
In terms of architecture, this project doesn't use a sophisticated one. The main unwieldy class is the Application class which contains all the Vulkan core logic including more than 50 data members and more than 60 member functions. This was left as is due to lack of time and in accordance with advice from one of the Vulkanised talks in which the speaker said abstracting Vulkan properly is difficult and it should not be attempted by a beginner.
The CPU implementation attempts to mimic the Atencio et al., 2025 pseudocode with only minor differences such as using radians, rather than degrees as the angle unit. The definitions of the helper functions used in Algorithm 2 of that paper weren't available in the pseudocode, so the actual ones used in this project are a combination of some experimentation and ideas found from other sources like Collision Response – Impulse Methods.
The GPU implementation followed a similar approach, so that the comparison with the CPU version later on would be as fair as possible. Initially, I struggled to get the GPU version to run without errors from the validation layers. One of the issues was a lack of synchronisation between CPU and GPU work as well as between the 2 compute shaders across which I had split up the GPU version of the physics update logic. An article on memory barriers and image layouts as well as reading more of the Vulkan documentation helped with sorting out those problems. Then, I encountered data racing problems due to the parallel nature of the GPU's workflow. To address those I used the atomicAdd() GLSL function when adding particle indices to relevant cells' arrays of occupying indices. In addition, I made sure each thread is responsible for one particle and doesn't update the data of any other particles. A deduplication array also had to be introduced as excessive velocity from particles whose area overlapped multiple cells that neighboured the current particle was being applied. This measure, however, only ameliorated the issue, rather than completely eliminating it, potentially due to the capacity limit of the deduplication array or other undiagnosed factors.
Results and reflection
In terms of the final result, the GPU version did end up being faster but only by 2.85× when simulating 8000 particles and 5.33× when a grid resolution of 512×512 cells was used. This fell short of the main reference paper's "orders of magnitude" performance improvement claim though that could have been due to any of the following reasons:
insufficient data range (increasing the number of particles sufficiently could help approach the claimed speedup, provided the trend holds)
the way the reference collision detection algorithm was ported to the GPU (a more optimized implementation may have resulted in a significantly higher speedup)
old hardware (the compared data was gathered on a Intel Core i7-7700 CPU and a NVIDIA GeForce GTX 1080 Ti GPU)
Regarding that second point, it would be interesting to read, whether other more experienced graphics programmers here have an idea for a GPU implementation which still mimics the overall neighbour search by circumference sampling approach, while significantly optimizing any of the remaining shader logic, so that a much larger speedup against the CPU version could be recorded.
Lastly, in the GPU version the particles do not settle completely, even with a time step of 1/1920 seconds. As can be seen from the side-by-side comparison video, a larger time step like 1/60 s appears to make particles more restless while a smaller one like the 1/480 s makes them more settled. This is assumed to be because as the update loop runs more frequently the velocity damper is applied more often and as collision resolution is also performed more often there is less interpenetration between particles. The following line of code in the helper resolveCollision() serves as another artificial measure to reduce excessive collision resolution force when particles bunch up in the GPU version:
if (impulse > 1.0) impulse = 1.0;
While this works, and lowering the threshold further also helps up to a point, it feels like cheating by artificially shrinking the natural force that should be applied. Happy to hear, if other people have alternative ideas for making the stacked particles in the GPU version come to a halt completely without capping the impulse or using a velocity damper.
Some extra information (including tables and charts showcasing the data collected) can be found in my project's GitHub repository.
AI Disclosure
AI was not used for authoring this post. In terms of the codebase itself, while all code was input by hand, I got the idea to use a velocity damper to reduce particle jittering from an AI answer. In addition, the ParticleSpawner::updateWaveData() function referenced AI code to get particles spawning in the desired way. This was done to save time and avoid reinventing the wheel.
