Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Collision Detection (2015)

jeffreythompson.org

Post reply on HN
Print view View original

31–36 of 36 posts

Re: Collision Detection (2015)

#31

Post by schemescape »

cd_trwa wrote: post #26
schemescape wrote: post #17

In my experience, collision detection is the easy piece (partly due to the prevalence of resources like this one); collision resolution is where you start having to make compromises (and there aren’t always clean solutions).

CD is an unsolved problem. CD is actually where you make the bigger compromises. Even we had analytical solutions to every collision scenario (we are nowhere near that) still we have "floating point issue". Everything that touches FP is corrupted and it gets much worse for CD. Issues with the collision response partly the after effects.

Good points. I suspect when you need a high degree of accuracy with nontrivial shapes you’re probably right (my 2D games required neither of these :)

Re: Collision Detection (2015)

#32

Post by megameter »

cd_trwa wrote: post #26
schemescape wrote: post #17

In my experience, collision detection is the easy piece (partly due to the prevalence of resources like this one); collision resolution is where you start having to make compromises (and there aren’t always clean solutions).

CD is an unsolved problem. CD is actually where you make the bigger compromises. Even we had analytical solutions to every collision scenario (we are nowhere near that) still we have "floating point issue". Everything that touches FP is corrupted and it gets much worse for CD. Issues with the collision response partly the after effects.

I think the main difference is that it's not hard to get approximate detection methods working with some high school geometry(and for games with simple physical behavior, you can usually stop at those) but finding any kind of approximate solution to collision response is not something students are ordinarily given any theoretical background in until undergraduate education, and then mostly indirectly through calculus, not crossing into the general CS classes where it would directly connect.

If you study physics specifically and are plugged into the theory driving iterative solvers, or perhaps you study math and spot the connection between constraint problems generally and the specific case of collision, you can find your way to answers about engineering satisfying non-realistic behaviors, but that's describing a subset of game programmers. Many still stumble through a sea of hacks and reliance on libraries because the conceptual knowledge hasn't been directed at them.

Re: Collision Detection (2015)

#33

Post by d13 »

vvanders wrote: post #5
djmips wrote: post #2

Very nice! A very good resource on collision detection is the book by Christer Ericson (2005). However it is more geared towards c++ realtime games. https://realtimecollisiondetection.net/ I appreciate this nice site too.

That book is in my top 3 technical books of all time. It's basically data structures for 2D/3D space. It's also the only algorithms book I've found that actually has a whole section on how to write cache aware algorithms, pure gold.

Seconded. Absolute genius

Re: Collision Detection (2015)

#34

Post by eska »

I found the OOP chapter to be very questionable and against industry practice. Even for simple software you don't want to clobber rendering and collision detection together into the same object. The algorithms also naturally become O(n^2) and it's not possible to fix that without major rewrites, undoing the OOP. OOP is notoriously bad for CD. I'd suggest a simple data oriented design approach here, e.g. pushing collisions into a new container instead of setting flags in some object that the rendering code then uses.

Re: Collision Detection (2015)

#35

Post by mlvljr »

tapirl wrote: post #14
Animats wrote: post #9

It's a very basic intro. Polygon/polygon is brute force, O(N^2). There's no coarse filtering so that only nearby objects are checked. There's nothing that points out that concave objects are much harder to check efficiently than convex ones. Plus it's 2D only. An intro is nice, but this is like writing about sorting and only showing bubble sort.

It looks it intends not to touch broad phase things.

Pun?

Re: Collision Detection (2015)

#36

Post by jeffthompson »

Thanks all for the love and suggestions! I made this site more than five years ago and am so happy it helps folks daily. This is a project that can always be expanded and what's there is never enough. Super helpful to hear from y'all on some low-hanging next steps. Happy to hear more suggestions on what next steps and/or can't-be-left-out topics. (With the eye towards beginners and folks without a ton of math background – the goal isn't to be a drop-in for Box2D or Unity or whatever but to outline the fundamentals and get folks started.)
Post reply on HN