Collision Detection (2015)(jeffreythompson.org) |
Collision Detection (2015)(jeffreythompson.org) |
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.
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.
If you don't mind me asking, what are the other two top books?
> a whole section on how to write cache aware algorithms
"Efficient Memory Programming" by David Loshin is worth a look.
An intro is nice, but this is like writing about sorting and only showing bubble sort.
1. Off-axis rectangles, which are common for things like fighting games
2. Efficient convex polygon to convex polygon collision (GJK being the most popular algorithm), which is sort of the “most general” 2d collision detection problem.
// are the two points in the same location? if (x1 == x2 && y1 == y2) { return true; }
You should never compare two floating-point numbers for equality. Use interval and < > to determine if two numbers are close.
... when their values come from an arithmetic computation.
Here's a counter example: Quake's collision code makes extensive use of `if(trace.fraction == 1.0f)`, which basically means "could the whole move be done without colliding?". This makes sense, because `fraction` is explicitly initialized to `1.0f`, and gets potentially overwritten with lower values in case the ray intersects colliders.
This could also make sense when dealing with clamped values, e.g:
``` const float ratio = clamp(some_computation, 0.0f, 1.0f); if (ratio == 0.0) { // ... } ```
In both cases, the zero or one being compared to isn't a result of an arithmetic computation ; it comes from an assignment with a known constant (e.g inside `clamp`).
https://randomascii.wordpress.com/2012/02/25/comparing-float...
In particular, in many cases, you want to consider alternatives to comparing against a fixed epsilon: the relative epsilon approach, and the ULP (Units in the Last Place) method, which tests for how many other floats/doubles are representable between two values you're comparing. The benefit of these two methods is that they scale with the compared numbers.
Is it a premature optimization these days?
N-squared for single-digit N worked just fine, too.
π ~= 3,314?
Unte im finyish du kaxa okwa bik, 4 600 mm bi wit dek xante im. Na desh kuwang, unte im 2 300 mm gova bik, unte 14 000 mm fo imim du gang im. - 1 Da Bosmang Da Bik Imalowda 7:23