4 ms·

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

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

by araes 3y ago

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.