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

21–30 of 36 posts

Re: Collision Detection (2015)

#21

Post by TeMPOraL »

aquarin wrote: post #20

I have brief look at this book and it looks nice and easy to read, however I noted the author works with floating point numbers and in some places, you can see snippets like this: // 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.

Floating point comparison is a bottomless pit. This article goes into details:

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.

Re: Collision Detection (2015)

#22

Post by Ace17 »

aquarin wrote: post #20

I have brief look at this book and it looks nice and easy to read, however I noted the author works with floating point numbers and in some places, you can see snippets like this: // 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.

> You should never compare two floating-point numbers for equality.

... 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`).

Re: Collision Detection (2015)

#24

Post by ladberg »

aquarin wrote: post #20

I have brief look at this book and it looks nice and easy to read, however I noted the author works with floating point numbers and in some places, you can see snippets like this: // 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.

You should keep reading because he covers exactly that point soon after.

Re: Collision Detection (2015)

#25

Post by taneq »

Ace17 wrote: post #22
aquarin wrote: post #20

I have brief look at this book and it looks nice and easy to read, however I noted the author works with floating point numbers and in some places, you can see snippets like this: // 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.

> You should never compare two floating-point numbers for equality. ... 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…

Like a lot of things, the “don’t compare floats for equality” is a rule you should follow unless you understand it well enough to know when you can break it.

Re: Collision Detection (2015)

#26

Post by cd_trwa »

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.

Re: Collision Detection (2015)

#28

Post by jansan »

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.

IMO it is too basic. No broad phase, no smart polygon intersections, and far from touching Bezier curves and paths. But the tutorial is well made.

Re: Collision Detection (2015)

#30

Post by z3t4 »

First sort by one axis, then take the items that are close enough and sort them by another axis, then take the ones that are close enough and do the expensive square root or intersect calculations which are much slower then sorting.
Post reply on HN