Hacker News Reader

Comment by bruce343434 | Hacker News Reader

There really ought to be more resources for 3d collision detection, and in general 3d computational geometry. Existing resources usually suffer from one or more of the following:

- only 2d is considered

- edge cases are handwaved/not treated/rest-of-the-fucking-owl'ed

- edge cases are not even mentioned

- abstract mathematical operation is used, whose implementation (which isn't always obvious) is not given or described

- ok, hit or no hit... but then how to get the actual collision manifold? In which direction should the objects be separated and by how much?

- numerical accuracy is not regarded

- unnecessary muddying of the concepts by using OOP - just use (math) vectors and matrices please

View on HN

Write one? Just covering 2D plus some of the edge cases (and still having issues) took 20 pages of text and examples.

Reason that most 3D collision is simply handled with approximate spheres or cubes around objects, or else floating planes. IE: Feature-based Algorithms

Advanced stuff, if you want to implement it: Simplex Based Algorithms, Image-Space Occlusion Culling Algorithms, Bounding Volume Hierarchies.

Collision Detection: A Survey, S. Kockara et al, 2007 IEEE International Conference on Systems, Man and Cybernetics. https://d1wqtxts1xzle7.cloudfront.net/50445336/Collision_det...

3D Collision Detection: A Survey, P. Jimenez et al, Institute de Robotica, 2001, https://digital.csic.es/bitstream/10261/30526/1/doc1.pdf

With "simplex based" do you mean algorithms that require a tetrahedralized mesh? Because tetrahedralization is yet another non-straightforward topic...

Its basically anything related to the GJK (Gilbert-Johnson-Keerthi) algorithm mentioned elsewhere in this comment thread. Pg 2 of the first PDF linked above.

"GJK was generalized to be applied to arbitrary convex point sets, not just to polyhedra. [It] operates on the Minkowski difference between the objects. Two convex objects collide if and only if their Minkowski difference contains the origin."

So far I was only familiar with the "separating plane theorem" algorithm, and GJK by name. Do you know any good sources for where to get started when coding up a minkowski difference algorithm?

Link is Access Denied btw, but sci-hub works.

For a pretty good explanation of the algorithm, check this out: https://caseymuratori.com/blog_0003

Consider also the minkowski portal refinement algorithm: http://xenocollide.snethen.com/mpr2d.html . Similar idea, but I find it more intuitive.

> only 2d is considered

I guess that's because the concepts transfer nicely from 2d to 3d. E.g. the math for circle/circle collision is basically the same as the one for sphere/sphere collision.

Not really for more complicated meshes however, which compose planar geometries to form a solid. For 2 objects A and B you could iterate all pairs of planes that they have to see if there's any overlap, and although that works out as "elegant" math, not so elegant performance. Also, it won't yield a manifold.

No, but on some level line and plane equations are similar too. It's more about splitting bodies into convex parts to speed up the calculations.

(tbh it's been 20 years since I did that by hand ... but I would assume that the underlying math has not changed since then)

I generally port over collision code I wrote years ago. I kind of like it that way.

If I'm only doing 2D (and that is about all I have done) I don't really want/need a general collision framework. Code to detect rectangle collisions, circle-circle collisions, convex polygon collisions is fairly small and tight. Even the polygon collision code uses only simple linear algebra (dot products and such).

To your last point, because I own the code, I can guarantee no OOP ... I just use math.

real time collision detection is a good book on those fundamentals with real world considerations.

Reply on news.ycombinator.com