• Products
  • Solutions
  • Made with Unity
  • Learning
  • Support & Services
  • Community
  • Asset Store
  • Get Unity

UNITY ACCOUNT

You need a Unity Account to shop in the Online and Asset Stores, participate in the Unity Community and manage your license portfolio. Login Create account
  • Blog
  • Forums
  • Answers
  • Evangelists
  • User Groups
  • Beta Program
  • Advisory Panel

Navigation

  • Home
  • Products
  • Solutions
  • Made with Unity
  • Learning
  • Support & Services
  • Community
    • Blog
    • Forums
    • Answers
    • Evangelists
    • User Groups
    • Beta Program
    • Advisory Panel

Unity account

You need a Unity Account to shop in the Online and Asset Stores, participate in the Unity Community and manage your license portfolio. Login Create account

Language

  • Chinese
  • Spanish
  • Japanese
  • Korean
  • Portuguese
  • Ask a question
  • Spaces
    • Default
    • Help Room
    • META
    • Moderators
    • Topics
    • Questions
    • Users
    • Badges
  • Home /
  • Help Room /
avatar image
0
Question by shelljump · Mar 04, 2021 at 10:00 AM · collision detectionalgorithm

GJK+EPA infinite loop

I am implementing custom physics in my game and having a go at gjk+epa for collision detection and response. The GJK part seems to work correctly (in 2D for now), but I am running into an infinite loop on my epa code and I do not understand why.

My algorithm looks like this:

     public static Vector2 GJK(List<Vector2> a, List<Vector2> b)
     {
         //GJK
         List<Vector2> s = new List<Vector2>();
         Vector2 dir = Vector2.left;
         s.Add(support(a, dir) - support(b, -dir));
         dir = -s[0];
 
         while (s.Count < 3) //3 because we are in 2D, so an enclosing simplex is a triangle
         {
             //add the vertex furthest along in the search direction onto the simplex
             Vector2 p = support(a, dir) - support(b, -dir);
             //if that vertex is not on the other side of the origin, report no collision
             if (Vector2.Dot(p, dir) < 0) return Vector2.zero;
             s.Add(p);
             //keep only the piece of the simplex that the origin is closest to
             do_simplex(ref s, ref dir);
         }
 
         //EPA
         int     min_i = 0;
         float   min_d = float.PositiveInfinity;
         Vector2 min_n = Vector2.zero;
 
         while (min_d == float.PositiveInfinity)
         {
             //get closest edge to origin
             for (int i = 0; i < s.Count; ++i)
             {
                 Vector2 e = s[(i+1) % s.Count] - s[i];
                 Vector2 n = new Vector2(e.y, -e.x).normalized;
                 float e_d = Vector2.Dot(n, s[i]);
                 if (e_d < 0) { n *= -1; e_d *= -1;}
 
                 if (e_d < min_d)
                 {
                     min_d = e_d;
                     min_n = n;
                     min_i = (i + 1) % s.Count;
                 }
             }
 
             //search for verticies in direction normal to the min edge
             Vector2 p = support(a, min_n) - support(b, -min_n);
             float p_d = Vector2.Dot(p, min_n);
 
             //if the polytope has been expanded, we have more faces to search
             if (Mathf.Abs(p_d - min_d) > 0.001f)
             {
                 min_d = float.PositiveInfinity;
                 //inserting the vertex in the correct order should take care of
                 //the polygon automatically in 2D. (why is this still convex?)
                 s.Insert(min_i, p);
             }
         }
 
         return min_n * (min_d + 0.001f);
     }

The problem is that if I run it on almost any vertex list, e.g. a = b = {(-0.2, 0.6), (0.8, 0.6), (0.8, 1.6), (-0.2, 1.6)}, I get stuck in the second while loop forever, as points are cyclically added into the polytope.

I feel like there is just something I fundamentally don't understand about the algorithm and all of the readings about it online are extremely terse, so I'm hoping someone here who has implemented it before can see the error.

Comment
Add comment · Show 1
10 |3000 characters needed characters left characters exceeded
▼
  • Viewable by all users
  • Viewable by moderators
  • Viewable by moderators and the original poster
  • Advanced visibility
Viewable by all users
avatar image shelljump · Mar 04, 2021 at 10:12 AM 0
Share

I can include the do_simplex() and support() routines if needed, but keep in $$anonymous$$d that the GJK part correctly detects if a collision occurred-- it returns Vector2.zero if no overlap happens and produces a list of 3 points if one does happen.

0 Replies

· Add your reply
  • Sort: 

Your answer

Hint: You can notify a user about this post by typing @username

Up to 2 attachments (including images) can be used with a maximum of 524.3 kB each and 1.0 MB total.

Follow this Question

Answers Answers and Comments

158 People are following this question.

avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image

Related Questions

Using OnTriggerEnter outside of MonoBehaviour 0 Answers

Unity Collider2D is causing the game object to disappear upon collision? 1 Answer

Determine collision points/area 0 Answers

Collisions without colliders 0 Answers

move pooled object on collision/trigger but keep pooling it 1 Answer


Enterprise
Social Q&A

Social
Subscribe on YouTube social-youtube Follow on LinkedIn social-linkedin Follow on Twitter social-twitter Follow on Facebook social-facebook Follow on Instagram social-instagram

Footer

  • Purchase
    • Products
    • Subscription
    • Asset Store
    • Unity Gear
    • Resellers
  • Education
    • Students
    • Educators
    • Certification
    • Learn
    • Center of Excellence
  • Download
    • Unity
    • Beta Program
  • Unity Labs
    • Labs
    • Publications
  • Resources
    • Learn platform
    • Community
    • Documentation
    • Unity QA
    • FAQ
    • Services Status
    • Connect
  • About Unity
    • About Us
    • Blog
    • Events
    • Careers
    • Contact
    • Press
    • Partners
    • Affiliates
    • Security
Copyright © 2020 Unity Technologies
  • Legal
  • Privacy Policy
  • Cookies
  • Do Not Sell My Personal Information
  • Cookies Settings
"Unity", Unity logos, and other Unity trademarks are trademarks or registered trademarks of Unity Technologies or its affiliates in the U.S. and elsewhere (more info here). Other names or brands are trademarks of their respective owners.
  • Anonymous
  • Sign in
  • Create
  • Ask a question
  • Spaces
  • Default
  • Help Room
  • META
  • Moderators
  • Explore
  • Topics
  • Questions
  • Users
  • Badges