4 ms·
The collision problem always makes me wonder if we miss something obvious. It's so hard to solve it mathematically/algorithmically specially when a lot of verti
by whatever1 3y ago
The collision problem always makes me wonder if we miss something obvious. It's so hard to solve it mathematically/algorithmically specially when a lot of vertices are involved, yet give the same problem to a semi awake brain and can immediately give you the right answer.
- xeonmc 3y agothe brain and eyes are massively parallel devices with stochastic ray tracing simulated for free. If you can brute-force raycasts without paying the computational burden then collision is an embarrassingly parallel problem. On the other hand, calculating collision on a computer is akin to a blind man feeling his way through a scene carefully checking against every object. The blind man has to simulate his own raytracing with his hands, unless he can perform echolocation which once again is basically lower-resolution raytracing. It does make me wonder though whether newer generation GPU focused on raytracing could finally bring hardware acceleration to collision?
- guitarlimeo 3y agoThis is a nice analogy, never thought of it that way but it makes sense!
- battesonb 3y agoWe somewhat have this with object picking. You can render objects with unique IDs to a framebuffer, so it's all in parallel. Then you just query the buffer at your mouse coordinates. Of course you lose some properties of the object and it's on a one frame delay. There's the added complexity of collision response, working in 3-dimensions, etc. But, to the point of just "eyeballing" collision, we can actually parallelize it!
- charcircuit 3y ago>and it's on a one frame delay Reading a texture from the GPU can take more than one frame.
- ReleaseCandidat 3y ago> could finally bring hardware acceleration to collision Physx has collision detection.
- hypercube33 3y agoIs it possible to use ray tracer hardware to say raytrace polygone vertices and use that for fast collision?
- raincole 3y agoNo? It's just one of the thousands of tasks that biological brains are envolved to do well.
- lebaux 3y ago[flagged]
- weregiraffe 3y agoSomeone forgot to take their pills...
- maroonblazer 3y agoAre you Eric Weinstein?
- ReleaseCandidat 3y agoThe problém with collision detection is less that is hard to do at all (it is actually quite simple), it is that it takes too long to brute-force check all of them. The samé problém as with raytracing.
- Jasper_ 3y agoThe brain solves it by noticing where two solid polygons overlap. In that sense, you could also find the collision by rasterizing both shapes and testing whether any pixels overlap, but that's going to be slower and less precise than an algorithmic version. With just an algebraic version of two polygons, your brain can't solve it as easily.
- akoboldfrying 3y agoActually, your "pixel overlap" method can be developed into a technique that is pretty efficient, provided we have (a) a quick way to partition any polygon into 2 roughly equal-size polygons and (b) a quick way to come up with a "covering disk" for any polygon (that is, a circle that contains the polygon, and doesn't extend too much further): isColliding(poly P, poly Q): if dist(P.circle.centre, Q.circle.centre) > P.circle.radius + Q.circle.radius: return false if P.circle.radius > THRESH: (P1, P2) = subdivide(P) return isColliding(P1, Q) || isColliding(P2, Q) if Q.circle.radius > THRESH: (Q1, Q2) = subdivide(Q) return isColliding(P, Q1) || isColliding(P, Q2) // Both P and Q are "small" return detectOverlapByRasterising(P, Q)
- deleted 3y ago[deleted]
- bee_rider 3y agoI don’t think we can generally eyeball if things will collide with the accuracy needed for a physics engine. For example, consider golfers, if they could just run the simulation they would get excited before getting a hole in one, not after.