[HN Gopher] Sort, sweep, and prune: Collision detection algorith...
___________________________________________________________________
Sort, sweep, and prune: Collision detection algorithms (2023)
Author : wonger_
Score : 204 points
Date : 2024-08-14 02:19 UTC (20 hours ago)
(HTM) web link (leanrada.com)
(TXT) w3m dump (leanrada.com)
| marginalia_nu wrote:
| I enjoyed the use of illustration. Seems like an appropriate
| usage.
|
| Sometimes I feel like these articles with interactive
| illustrations are more like an excuse to put together a bunch of
| cool demos, like there's a lot of fluff with not much substance
| (a bit like a TED talk), but this one didn't let the
| illustrations take over.
| JKCalhoun wrote:
| > This naive algorithm runs in O(n2) time in Big O terms.
|
| Is this true? The naive algorithm's outer loop (i) counts n - 1,
| while the inner loop (j) begins at i + 1 (so counts progressively
| less than n - 1).
|
| Not a CS major, is this roughly equivalent (for large values of
| n) to O(n2) or is it, as it appears, something less?
| friendzis wrote:
| Big O is just complexity classes, describing how number of
| abstract computations _scale_ (that 's the key word) with input
| size (input list length). Generally speaking, if you could
| analytically express number of computations as a function of
| input size, Big O takes the largest term and drops all factors.
|
| It does not necessarily describe performance of the algorithm.
| `20n2^+5n` and `2n^2 + 9001n` are both O(n^2)
| chipdart wrote:
| > It does not necessarily describe performance of the
| algorithm.
|
| Not necessarily true. It does indeed describe performance of
| the algorithm. It just compares scenarios with coarser
| granularity. You can tell from the very start that a O(1)
| algorithm is expected to outperform a O(N2) alternative.
| ohwellhere wrote:
| My algorithms class taught to think of it not as
| "describing performance" in an absolute sense, but as
| "describing how performance changes as the size of the
| input data increases".
|
| It is not necessarily true that an O(1) algorithm will
| outperform an O(n^2) alternative on a particular set of
| data. But it is true that an O(1) algorithm will outperform
| an O(n^2) alternative as the size of the input data
| increases.
| chipdart wrote:
| > (...) but as "describing how performance changes as the
| size of the input data increases".
|
| Yes, that's the definition of asymptotic computational
| complexity. That's the whole point of these comparisons.
| It's pointless to compare algorithms when input size is
| in the single digit scale.
| Kubuxu wrote:
| You could have an O(N^2) algorithm outperform an O(N) on
| the scale of 10,000 (or whatever scale you want to
| imagine). The big-O notation compares only asymptotic
| behaviour, and sometimes the lower power factors are
| overwhelming.
| tialaramex wrote:
| This sometimes doesn't work out in practice because the
| scaling involved runs into a limitation your big-O model
| didn't account for. Typical examples are: The size of the
| machine registers, physical RAM, addressable storage, or
| transmission speeds.
|
| If your O(1) algorithm takes an hour for any input, and
| the competition is O(n) it may seem like there must be
| cases where you're better, and then you realise n is the
| size in bytes of some data in RAM, and your competitors
| can do 4GB per second. You won't be competitive until
| we're talking about 15TB of data and then you remember
| you only have 64GB of RAM.
|
| Big-O complexities are not useless, but they're a poor
| summary alone, about as useful as knowing the mean price
| of items at supermarkets. I guess this supermarket is
| cheaper? Or it offers more small items? Or it has no
| high-end items? Or something?
| yeevs wrote:
| it's the summation of numbers from 1 to n which is n(n+1)/2.
| This reduces to quadratic complexity because big O notation
| ignores all coefficients and terms that scale slower
| cinntaile wrote:
| I don't know if this will make more sense to you but Big O is
| like limit calculations from calculus.
| spacecadet_ wrote:
| You're right that it's not exactly n^2. For the i-th element we
| perform (n - i - 1) comparisons (indexing from 0). This adds up
| to a total of (n - 1) * n / 2 comparisons. (see
| https://en.wikipedia.org/wiki/Triangular_number)
|
| In the end it doesn't make a difference for big-O analysis
| because it's used to describe the behavior when n approaches
| infinity, where the quadratic factor takes over.
| qwery wrote:
| The "optimisation" of starting the inner loop at `j = i + 1` is
| done to avoid testing every pair of objects _twice_.
|
| [Ed: I should add that it also prevents testing an object
| against itself.]
|
| The algorithm is O(n^2) because every pair will be checked
| _once_.
| veryrealsid wrote:
| Zhe Jin Tian
| sixthDot wrote:
| The title was curious to me because I expected more a post about
| the `intersects` function, e.g the pip algorithm... turns out
| it's more about the complexity involved by the number of objects
| to test, which in the end is also interesting.
| veryrealsid wrote:
| Wo Ronald Hansen
| sixthDot wrote:
| E Don Lancaster
| wood_spirit wrote:
| A tangent, but HNers interested in an article on collision
| detection might know: are there any similar articles that show
| how to compute the intersection of two capsules (as in the space
| that that a sphere moving in a straight line in a time step
| occupies) in 3D? My own hobby 3D game got stuck on that hurdle
| and I couldn't find any examples anywhere :(
| xeonmc wrote:
| Isn't it just a matter of checking if two lines' perigee fall
| within radius sum, and if so check if the respective segments'
| closest points to the perigee are within radius sum?
| pornel wrote:
| You make one of them have thickness of both, so that the
| collision detection becomes line vs capsule collision.
|
| Another trick is to rotate both so that one of the move
| directions is axis-aligned, and then the problem looks more
| like AABB.
| qwery wrote:
| Capsule-capsule overlap can be detected by treating the
| capsules as line segments with radius/thickness. But I think
| you need something more complicated than capsule-capsule
| intersection to truly solve the problem (continuous collision
| detection between dynamic objects).
|
| The Rapier project and its documentation[0] might be of
| interest to you. Rapier has a more sophisticated CCD
| implementation than most (popular in gamedev) physics engines.
|
| > Rapier implements nonlinear CCD, meaning that it takes into
| account both the angular and translational motion of the rigid-
| body.
|
| [0]
| https://rapier.rs/docs/user_guides/rust/rigid_bodies#continu...
| GistNoesis wrote:
| For fine collision between capsules, you consider the capsules
| as 3d segments with thickness. And two of those collide if the
| distance between segments < sum of half-thicknesses.
|
| You can check this site with nice animations which explain how
| to compute the distance between segments :
| https://zalo.github.io/blog/closest-point-between-segments/
|
| One more generic way to compute the distance between shapes is
| to view it as a minimization problem. You take a point A inside
| object 1 and a point B inside object 2, and you minimize the
| squared distance between the points : ||A-B||^2 while
| constraining point A to object 1 and point B to object 2.
|
| In the case of capsules, this is a "convex" optimization
| problem : So one way of solving for the points, is to take a
| minimization (newton) step and then project back each point to
| its respective convex object (projection is well defined and
| unique because of the convex property) (It usually need less
| than 10 iterations).
|
| In geometry, we often decompose object into convex unions. One
| example is sphere-trees, where you cover your object with
| spheres.
|
| This allow you to use fast coarse collision algorithm for
| spheres to find collision candidates of your capsules : You
| cover your capsules with spheres (a little bigger than the
| thickness) so that the capsule is inside the union of the
| spheres.
| bee_rider wrote:
| Since the balls probably don't move much per frame, should the
| list be considered "nearly sorted?"
| Sharlin wrote:
| Yes, the author gets to that in the second part.
| jonnycat wrote:
| One interesting note on this approach is that the author suggests
| using a "fast" sorting algorithm like mergesort/quicksort as the
| sorting algorithm for best performance. But in practice, you may
| get better performance from a "worse" sorting algorithm:
| insertion sort.
|
| The reason is that objects in collision detection systems tend to
| move relatively small steps between frames, meaning you can keep
| lists from the previous frame that are already mostly sorted. For
| sorting these mostly sorted lists, insertion sort tends towards
| O(n) while Quicksort tends towards O(n^2)!
| deathanatos wrote:
| The author covers this pretty much exactly as you describe it.
| From Part 2 of TFA,
|
| > _Let's look at the sort step, which is the bottleneck of the
| algorithm according to the analysis._
|
| > _You can see that most of the time, the sort does nothing at
| all! The list is almost always already sorted from the previous
| frame._
|
| > _Even when it becomes unsorted, it usually just takes a
| couple of swaps to be sorted again._
|
| > _Here's insertion sort in action:_
| tialaramex wrote:
| If you use a modern sort, it'll just go "Oh that's sorted,
| we're done". Pattern Defeating Quicksort will do that and so
| would Glidesort, Driftsort, IPNsort and so on. Most of these
| algorithms will also correctly shortcut trivial "almost
| sorted" cases like 123457689 (only longer, if you really only
| have nine elements you want a custom sort for that, there
| will be a correct algorithm and it's probably written down
| somewhere already)
|
| Rust's _old_ sorts, both of them, get this right. There 's a
| fair chance the current version of your C++ stdlib even gets
| this right in its unstable sort. In 1965 it's understandable
| that you reach for an insertion sort for this case, in 2024
| it's embarrassing if your language doesn't provide a built-in
| sort where this just works.
| nextaccountic wrote:
| > Rust's old sorts, both of them, get this right.
|
| And the newer sort in the stdlib does too, right?
|
| Link https://www.reddit.com/r/rust/comments/1dl079x/the_rus
| t_stdl...
| tialaramex wrote:
| Yes, the stdlib provided sort and sort_unstable in Rust
| 1.81 and later are
|
| https://github.com/Voultapher/sort-research-
| rs/blob/main/wri... and
| https://github.com/Voultapher/sort-research-
| rs/blob/main/wri...
| GistNoesis wrote:
| There is an alternative to sorting every step : Build your
| indexing structure a little looser, so that you catch the
| candidates collisions when object have moved less than epsilon.
|
| For example that can be done by increasing the radius of the
| spheres by epsilon. As long as the spheres have not moved by
| epsilon, you don't need to recompute the index.
|
| To avoid latency peaks when you do need to recompute the index,
| you can start building a lagging index by sorting 10% each
| frame (aka amortizing the computation cost). After 10 frames
| you have an index that is valid as long as the position is
| within epsilon of the position 10 frames ago.
| rendaw wrote:
| I hadn't seen this before, but isn't it similar to using
| something like a quad-tree to reduce the number of potential
| colliders?
| deliveryboyman wrote:
| Yes, although you're more likely to see something like a k-d
| tree in offline rendering than in real-time rendering.
| justbookmark wrote:
| https://github.com/southkorea/southkorea-maps/issues/11
| syntaxing wrote:
| Super interesting, my first thought before I read the article was
| why not a bloom filter but didn't expect it to be "physical"
| collision
| bambax wrote:
| Excellent article. Sorting the list is a really simple and neat
| idea, without the need for clustering or a special data
| structure.
| denvaar wrote:
| Got distracted (in a good way) by this website. It's fun and
| inspiring.
| FrustratedMonky wrote:
| Very Nice animated examples
| layer8 wrote:
| The animations don't show on iOS Safari.
| fuzzythinker wrote:
| Part 2: https://leanrada.com/notes/sweep-and-prune-2/
|
| Check out his other goodies https://leanrada.com/
| RaftPeople wrote:
| > _I won't cover other approaches, such as space partitioning or
| spatial tree subdivision_
|
| I'm curious about this comment, anyone know if the algorithm in
| the article is generally faster than space partitioning/spatial
| tree subdivision?
|
| A long time ago I used a spatial tree type of approach which
| seemed naively to be a pretty good approach, but I never
| investigated or compared algorithms other people were using (this
| was 80's, pre-internet).
| kevingadd wrote:
| The complexity involved in maintaining space partitioning, tree
| subdivision etc can end up being a big hassle, especially if
| you have huge numbers of moving objects.
|
| It's much easier to write, debug and optimize something that
| manages a single list of entities, or a grid of i.e. 256x256
| 'cells' that each contain a list of entities, than it is to set
| up a complex partitioning scheme that maintains all your tree
| invariants every time an object moves.
|
| In the days of i.e. DOOM or Quake the performance of these
| underlying systems was much more important than it is now, so
| it (IMO) made more sense for the authors of those engines to
| cook up really complex partitioning systems. But these days
| CPUs are really good at blasting through sorted arrays of
| items, and less good at chasing linked lists/trees
| (comparatively) than they used to be, due to pipelining. Your
| CPU time isn't going to be spent on managing those entity lists
| but will instead be spent on things like AI, rendering, etc.
| bob1029 wrote:
| I've always enjoyed this document regarding continuous collision
| detection:
|
| https://github.com/bepu/bepuphysics2/blob/master/Documentati...
|
| The library itself is amazing in terms of performance. It is a
| bit challenging to integrate with though due to the amount of
| optimization involved.
___________________________________________________________________
(page generated 2024-08-14 23:00 UTC)