Exhaustively doing all the edge-edge collision tests is working far too hard. That's why he needs SIMD.
I did the first ragdoll physics system about 20 years ago, when we had less compute available.[1] GJK, which the author mentions, is the preferred algorithm for convex hull collisions. GJK is a hill-climber. You start with two points, one on each object, and walk them towards each other along edges, picking the direction that produces the most improvement. This is O(sqrt N) on the number of vertices per object.
That's with two random starting points. If you're doing this repeatedly, as in an animation, you can start from the winning points of the previous round. If the objects are not rotating and moving very fast, the recheck is constant time. If they move a little, it takes slightly longer, of course. Many modern programs don't use the incremental form, but it's much faster.
GJK is a very fussy algorithm numerically. The optimization involves subtracting large numbers and caring about small differences. Loss of significance due to underflow can be a problem, and can cause the termination condition to not terminate, with the optimization cycling between a few near-optimal solutions. The loss of significance problems show up as objects settle into parallel-face contact, which is why this algorithm tended to loop when put inside a physics simulation where objects settled. Passed tests with randomly oriented convex hulls all day.
This was hard to fix. I had a hack solution that detected cycling, and Prof. Stephen Cameron at Oxford finally fixed the numerical math to behave.[2]
(You can get his code from his web site, there's a substantial license fee for commercial use, and he died years ago. I licensed the code back in the 1990s, but can't sublicense or release it. If someone really wants it, they'll need to find his heirs and negotiate.)
You also need "good" convex hulls. Your options are hulls with polygonal faces that won't be perfectly flat due to numerical precision limits, or hulls with triangular faces that are sometimes coplanar. Using a convex hull generator which can enforce a minimum break angle of about 1 degree, with polygonal faces, seems to work best.
Now there's OpenGJK.[3] Haven't looked at that. Hopefully they've dealt with all these problems. I was doing this back in the stone age of game physics, when nothing worked out of the box.
- Collision using simple shapes is very optimized and fast
- GJK's complexity scales linearly with the complexity of the support function, while checking pairs scales quadratically, which is a big advantage of GJK
- GJK imposes a convexity requirement, so non-convex shapes need to be decomposed somehow, this is a non-trivial problem if your shapes are dynamically generated and you need to decompose them dynamically. An absolutely nontrivial problem.
- Physics engines have a 'broadphase' where they detect collision pairs using approximate shapes much more efficiently. For a fully general algorithm, this is needed for GJK as well, because of said decomposition. This gets rid of much of the quadratic behavior of simpler algorithms.
- GJK doesn't give you penetration distance which simple algorithms do - this needs additional work, but it might be tractable since that only happens after a collision was found
- A nice thing about GJK is that it generalizes easily to continuous collision detection
- In video games, developers can 'cheat' and design their objects to be easily represented by (composites of) simple shapes - cubes, cylinders, spheres etc.
So in all, GJK imo, is a 'mini-broadphase' and not separate technique (in that it forwards the actual query to the support function).
So if OBB-OBB collision is inherently 5x faster, and SIMD gives you another 6x speedup, you need 30 collision evaluations to break even. The nature of 2D vs 3D space is that crowding in 2D is much less feasible.
There was an even better version of GJK published around 2017 which made it more numerically robust: the Signed Volume Method (https://dl.acm.org/doi/10.1145/3083724) OpenGJK is written by the same author, and is based on that paper.
Needing SIMD is hardly a problem though, especially if you only need the completely ubiquitous versions, and in using it, can avoid a good amount of fussy stuff.
Back in the day I was writing a liero clone, and came up with a neat scheme for pixel-perfect collisions (probably serendipitously, no claims it's unique). A 64bit integer can be seen as an 8x8 mask. You can pixel shift it up and down by simply bitshift left or right by 8n bits. Pixel shift left and right required more instructions; if I was to write it today I would probably store an additional rotated version instead (as that would then effectively pixel shift left and right with bit shifts).
You then have the terrain chopped up into these 8x8s too, and can then do a collision test with at most 4 of them with the 1 character/entity mask.
As a SIMD noob, one thing that wasn't obvious to me is that SIMD can also speed you up if your mem throughput is underutilized by having the CPU load more data per instruction. It isn't just about compute speedups, which is typically what it's advertised for. Using perf on Linux has been very educational for me to get an intuition for modern CPU performance.
Yeah, and in the blog post he mentions that he had to transform the data to SoA. If he had done that alone, he might already have seen a speedup from better cache utilization.
Also, I see no mention of alignment in the post. I understand x86/AVX2 likes your load/stores to be aligned, even if it technically allows unaligned access.
Unaligned loads/stores aren't super bad; if still within a cacheline, there's zero penalty, and on crossing cachelines it's alike two ops (except page crossing, which is more bad).
So, for 32B loads/stores and 64B cachelines, it's 1.5x more L1 cache ops (as half of the ops will cross a cacheline); perhaps bad if you're L1-cache-throughput-bound, but less so if you're at L2+ as the extra work sits in L1.
Well, the other way to say it is SIMD, "process more data in a vector at the same time", stops being advantageous when your "Von Neumann machine" cannot fetch enough data for the CPU in that time (the "bandwidth bottleneck" that has become a so pressing idea in the past few years...).
I feel like SIMD has been around for decades. Why has it taken this long to catch on? I feel like I have been hearing it a lot through the past few years. It feels like it’s talked about like some programming silver bullet
Intel didn't put SIMD in their chips speculatively; there was a lucrative market. HPC presumably. Maybe SIGINT.
There have always been SIMD accelerated libraries, but I assume that you're talking about more widespread hand-coded SIMD application code (either in assembly or using compiler intrinsics.) For audio DSP this caught on when SSE2 launched around 2000-2002[0]. All things being equal, the user being able to run twice as many of your plugin as your competitor's is a real commercial advantage (being super-slow compared to your competitors is also not a great look.)
Not all applications have such forces at play. For most of the intervening period computers were getting faster every generation anyway, so users were seeing performance improvements when they upgraded their hardware, with no developer effort. For me, adding features delivered more value to users than making the existing product run faster.
A few things that factored into my personal limited use of SIMD over that time frame (even though I did write some inline asm): overhead of maintaining compatibility with multiple CPU generations. i.e. AMD and Intel were not in lockstep (still aren't, see AVX512); my users' hardware was all over the shop ranging from latest and greatest to older than you would imagine; I wanted good OS backward compatibility; autovectorisation was supposed to be just around the corner (honestly it's not bad if you limit the compiler to a recent instruction set). All of this could have been addressed, but features were a higher priority.
In addition, that period was the era of "write once run everywhere." Portable code was desirable. Having inline asm was seen as dirty, using instructions that only ran on specific makes and models of CPU more so. SIMD was alien to the mainstream developer zeitgeist.
In recent years the calculus has changed: CPU clock speeds are stagnant, most if not all application processors have SIMD units. More people understand that most CPU compute is in the SIMD units. We seem to have reached a critical mass of open SIMD algorithm development in less niche domains (e.g. simdjson). But SIMD code is still not write-once-run-everywhere.
Remember the part of the article where he talks about a shocking number of people didnt have the version of AVX he wanted. This is a big issue because SIMD is writing ASM for the most part not C code so new architecture you have problems . RVV riscv SIMD has an interesting way to adapt to different CPU tiering and is a rather complete SIMD architecture but most SIMD architectures have small holes which can be mildly annoying
Simd is by far the most efficient cycles wise paradigm but its also brittle. When the shape of data is odd which is common enough you have to handle it properly which is sometimes a distraction from what people actually care about. Also GPUs exist, GPUs despite being way less power efficient are not brittle in this same way they have issues if memory is difficult but most problems work nicely on GPUs so people just do that because its easier and the tiering problem is less a big deal because GPU process instructions different than SIMD and batching and what not is left to hardware not the programmer
Exhaustively doing all the edge-edge collision tests is working far too hard. That's why he needs SIMD.
I did the first ragdoll physics system about 20 years ago, when we had less compute available.[1] GJK, which the author mentions, is the preferred algorithm for convex hull collisions. GJK is a hill-climber. You start with two points, one on each object, and walk them towards each other along edges, picking the direction that produces the most improvement. This is O(sqrt N) on the number of vertices per object.
That's with two random starting points. If you're doing this repeatedly, as in an animation, you can start from the winning points of the previous round. If the objects are not rotating and moving very fast, the recheck is constant time. If they move a little, it takes slightly longer, of course. Many modern programs don't use the incremental form, but it's much faster.
GJK is a very fussy algorithm numerically. The optimization involves subtracting large numbers and caring about small differences. Loss of significance due to underflow can be a problem, and can cause the termination condition to not terminate, with the optimization cycling between a few near-optimal solutions. The loss of significance problems show up as objects settle into parallel-face contact, which is why this algorithm tended to loop when put inside a physics simulation where objects settled. Passed tests with randomly oriented convex hulls all day.
This was hard to fix. I had a hack solution that detected cycling, and Prof. Stephen Cameron at Oxford finally fixed the numerical math to behave.[2]
(You can get his code from his web site, there's a substantial license fee for commercial use, and he died years ago. I licensed the code back in the 1990s, but can't sublicense or release it. If someone really wants it, they'll need to find his heirs and negotiate.)
You also need "good" convex hulls. Your options are hulls with polygonal faces that won't be perfectly flat due to numerical precision limits, or hulls with triangular faces that are sometimes coplanar. Using a convex hull generator which can enforce a minimum break angle of about 1 degree, with polygonal faces, seems to work best.
Now there's OpenGJK.[3] Haven't looked at that. Hopefully they've dealt with all these problems. I was doing this back in the stone age of game physics, when nothing worked out of the box.
[1] https://www.youtube.com/watch?v=5lHqEwk7YHs
[2] https://www.cs.ox.ac.uk/stephen.cameron/distances/
[3] https://github.com/MattiaMontanari/openGJK
GJK is a cool algorithm but:
- Collision using simple shapes is very optimized and fast
- GJK's complexity scales linearly with the complexity of the support function, while checking pairs scales quadratically, which is a big advantage of GJK
- GJK imposes a convexity requirement, so non-convex shapes need to be decomposed somehow, this is a non-trivial problem if your shapes are dynamically generated and you need to decompose them dynamically. An absolutely nontrivial problem.
- Physics engines have a 'broadphase' where they detect collision pairs using approximate shapes much more efficiently. For a fully general algorithm, this is needed for GJK as well, because of said decomposition. This gets rid of much of the quadratic behavior of simpler algorithms.
- GJK doesn't give you penetration distance which simple algorithms do - this needs additional work, but it might be tractable since that only happens after a collision was found
- A nice thing about GJK is that it generalizes easily to continuous collision detection
- In video games, developers can 'cheat' and design their objects to be easily represented by (composites of) simple shapes - cubes, cylinders, spheres etc.
So in all, GJK imo, is a 'mini-broadphase' and not separate technique (in that it forwards the actual query to the support function).
So if OBB-OBB collision is inherently 5x faster, and SIMD gives you another 6x speedup, you need 30 collision evaluations to break even. The nature of 2D vs 3D space is that crowding in 2D is much less feasible.
There was an even better version of GJK published around 2017 which made it more numerically robust: the Signed Volume Method (https://dl.acm.org/doi/10.1145/3083724) OpenGJK is written by the same author, and is based on that paper.
Needing SIMD is hardly a problem though, especially if you only need the completely ubiquitous versions, and in using it, can avoid a good amount of fussy stuff.
My favourite is probably Bepuphysics due to its C# nature: https://www.youtube.com/watch?v=tjtwSq3u6Dg
Unfortunately it was created before Unity could use vectorization and other C# engines were just starting out as well.
The source, a great resource for learning C# SIMD, even though its a few years old by now: https://github.com/bepu/bepuphysics2
Back in the day I was writing a liero clone, and came up with a neat scheme for pixel-perfect collisions (probably serendipitously, no claims it's unique). A 64bit integer can be seen as an 8x8 mask. You can pixel shift it up and down by simply bitshift left or right by 8n bits. Pixel shift left and right required more instructions; if I was to write it today I would probably store an additional rotated version instead (as that would then effectively pixel shift left and right with bit shifts).
You then have the terrain chopped up into these 8x8s too, and can then do a collision test with at most 4 of them with the 1 character/entity mask.
As a SIMD noob, one thing that wasn't obvious to me is that SIMD can also speed you up if your mem throughput is underutilized by having the CPU load more data per instruction. It isn't just about compute speedups, which is typically what it's advertised for. Using perf on Linux has been very educational for me to get an intuition for modern CPU performance.
The way simd speeds up "compute" is indeed mainly the reason that you operate on multiple pieces of data at once.
Yeah, and in the blog post he mentions that he had to transform the data to SoA. If he had done that alone, he might already have seen a speedup from better cache utilization.
Also, I see no mention of alignment in the post. I understand x86/AVX2 likes your load/stores to be aligned, even if it technically allows unaligned access.
Unaligned loads/stores aren't super bad; if still within a cacheline, there's zero penalty, and on crossing cachelines it's alike two ops (except page crossing, which is more bad).
So, for 32B loads/stores and 64B cachelines, it's 1.5x more L1 cache ops (as half of the ops will cross a cacheline); perhaps bad if you're L1-cache-throughput-bound, but less so if you're at L2+ as the extra work sits in L1.
If so they should just name it that
They should name it Multiple memory data, one single CPU instruction, or mmdosci for short. Easy to remember.
Well, the other way to say it is SIMD, "process more data in a vector at the same time", stops being advantageous when your "Von Neumann machine" cannot fetch enough data for the CPU in that time (the "bandwidth bottleneck" that has become a so pressing idea in the past few years...).
I feel like SIMD has been around for decades. Why has it taken this long to catch on? I feel like I have been hearing it a lot through the past few years. It feels like it’s talked about like some programming silver bullet
> Why has it taken this long to catch on?
Intel didn't put SIMD in their chips speculatively; there was a lucrative market. HPC presumably. Maybe SIGINT.
There have always been SIMD accelerated libraries, but I assume that you're talking about more widespread hand-coded SIMD application code (either in assembly or using compiler intrinsics.) For audio DSP this caught on when SSE2 launched around 2000-2002[0]. All things being equal, the user being able to run twice as many of your plugin as your competitor's is a real commercial advantage (being super-slow compared to your competitors is also not a great look.)
Not all applications have such forces at play. For most of the intervening period computers were getting faster every generation anyway, so users were seeing performance improvements when they upgraded their hardware, with no developer effort. For me, adding features delivered more value to users than making the existing product run faster.
A few things that factored into my personal limited use of SIMD over that time frame (even though I did write some inline asm): overhead of maintaining compatibility with multiple CPU generations. i.e. AMD and Intel were not in lockstep (still aren't, see AVX512); my users' hardware was all over the shop ranging from latest and greatest to older than you would imagine; I wanted good OS backward compatibility; autovectorisation was supposed to be just around the corner (honestly it's not bad if you limit the compiler to a recent instruction set). All of this could have been addressed, but features were a higher priority.
In addition, that period was the era of "write once run everywhere." Portable code was desirable. Having inline asm was seen as dirty, using instructions that only ran on specific makes and models of CPU more so. SIMD was alien to the mainstream developer zeitgeist.
In recent years the calculus has changed: CPU clock speeds are stagnant, most if not all application processors have SIMD units. More people understand that most CPU compute is in the SIMD units. We seem to have reached a critical mass of open SIMD algorithm development in less niche domains (e.g. simdjson). But SIMD code is still not write-once-run-everywhere.
[0] https://en.wikipedia.org/wiki/Streaming_SIMD_Extensions
Remember the part of the article where he talks about a shocking number of people didnt have the version of AVX he wanted. This is a big issue because SIMD is writing ASM for the most part not C code so new architecture you have problems . RVV riscv SIMD has an interesting way to adapt to different CPU tiering and is a rather complete SIMD architecture but most SIMD architectures have small holes which can be mildly annoying
Simd is by far the most efficient cycles wise paradigm but its also brittle. When the shape of data is odd which is common enough you have to handle it properly which is sometimes a distraction from what people actually care about. Also GPUs exist, GPUs despite being way less power efficient are not brittle in this same way they have issues if memory is difficult but most problems work nicely on GPUs so people just do that because its easier and the tiering problem is less a big deal because GPU process instructions different than SIMD and batching and what not is left to hardware not the programmer
https://en.wikipedia.org/wiki/Single_instruction,_multiple_d...
Looking at the Wikipedia article - I wonder if it is because SIMD and SIMT are enabled by hardware first
The average programmer isn’t falling into pits of success with auto vectorization.
And you’re using languages like Python or Lua and not using a dependency that uses it for you, forget about it.
LLMs?
Wookash Podcast just interviewed Erin Catto (the Box2D author): https://podcasts.apple.com/us/podcast/what-makes-a-good-phys... (sorry, I couldn’t find a player-agnostic feed link, even on wooka.sh, the podcast’s own website!)
Here's the video: https://www.youtube.com/watch?v=DQNqo2xtq6U
https://www.youtube.com/watch?v=6BIfqfC1i7U
useful
No support for any ARM vector instructions.. thats horrible
It looks like it supports NEON: https://github.com/erincatto/box3d/blob/781673be801569a94be7...
Old hat. Should be SVE
Do the Apple CPUs support SVE? If not then it's not worth the hassle tbh (and support on Android devices doesn't seem to be great either).
Name a few big products with SVE and not NEON, within the gaming market
This is free software.