4 ms·

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

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

fho 3y ago
> 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.
- bruce343434 3y ago
  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.
  - fho 3y ago
    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)
araes 3y ago
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_detection_A_survey20161120-10679-yjfxsi-libre.pdf?1479694690=&response-content-disposition=inline%3B+filename%3DCollision_detection_A_survey.pdf&Expires=1705850665&Signature=L1YIvu1twCVRkadXr2OsHBjLdtn~MMC07WJC1yE~Qq5YDhrblbbSHXMdKR6LeSCdDk0pgJWuPUPQcwxQ79QZBOWnDkV1Tx46jVjYkaqGfG4eVmGUx2FWhfD3r7D6fbv0rii8~uecCdrcQYa8z0e7IaOgGn8tqJvLZDz4rXmZk9VVvzMpaQVFXbQPSTXpmCd9c84D4nuhRBIhMxPscHncfM27lhFK5lwWAG-irT-y4~SbuA4LJF6DOlDvNO4~rwyKY1BXz58XyQQ79u5pS6mWE8K6kvSwYG-Ds7WKBNon0ZMA8GCo5t6unAcAJvikw479rVCS1plwPxYV2UIgIWv1EQ__&Key-Pair-Id=APKAJLOHF5GGSLRBV4ZA 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 https://digital.csic.es/bitstream/10261/30526/1/doc1.pdf
- bruce343434 3y ago
  With "simplex based" do you mean algorithms that require a tetrahedralized mesh? Because tetrahedralization is yet another non-straightforward topic...
  - araes 3y ago
    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."
    - bruce343434 3y ago
      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.
      - beaumayns 3y ago
        For a pretty good explanation of the algorithm, check this out: https://caseymuratori.com/blog_0003 https://caseymuratori.com/blog_0003 Consider also the minkowski portal refinement algorithm: http://xenocollide.snethen.com/mpr2d.html http://xenocollide.snethen.com/mpr2d.html . Similar idea, but I find it more intuitive.
JKCalhoun 3y ago
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.
weaksauce 3y ago
real time collision detection is a good book on those fundamentals with real world considerations.

fho 3y ago

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

bruce343434 3y ago
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.
- fho 3y ago
  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)

araes 3y ago

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_detection_A_survey20161120-10679-yjfxsi-libre.pdf?1479694690=&response-content-disposition=inline%3B+filename%3DCollision_detection_A_survey.pdf&Expires=1705850665&Signature=L1YIvu1twCVRkadXr2OsHBjLdtn~MMC07WJC1yE~Qq5YDhrblbbSHXMdKR6LeSCdDk0pgJWuPUPQcwxQ79QZBOWnDkV1Tx46jVjYkaqGfG4eVmGUx2FWhfD3r7D6fbv0rii8~uecCdrcQYa8z0e7IaOgGn8tqJvLZDz4rXmZk9VVvzMpaQVFXbQPSTXpmCd9c84D4nuhRBIhMxPscHncfM27lhFK5lwWAG-irT-y4~SbuA4LJF6DOlDvNO4~rwyKY1BXz58XyQQ79u5pS6mWE8K6kvSwYG-Ds7WKBNon0ZMA8GCo5t6unAcAJvikw479rVCS1plwPxYV2UIgIWv1EQ__&Key-Pair-Id=APKAJLOHF5GGSLRBV4ZA 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 https://digital.csic.es/bitstream/10261/30526/1/doc1.pdf

bruce343434 3y ago
With "simplex based" do you mean algorithms that require a tetrahedralized mesh? Because tetrahedralization is yet another non-straightforward topic...
- araes 3y ago
  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."
  - bruce343434 3y ago
    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.
    - beaumayns 3y ago
      For a pretty good explanation of the algorithm, check this out: https://caseymuratori.com/blog_0003 https://caseymuratori.com/blog_0003 Consider also the minkowski portal refinement algorithm: http://xenocollide.snethen.com/mpr2d.html http://xenocollide.snethen.com/mpr2d.html . Similar idea, but I find it more intuitive.

JKCalhoun 3y ago

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.

weaksauce 3y ago

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