## [Algorithms] Something wrong with this SAT method for finding contact points?

 [Algorithms] Something wrong with this SAT method for finding contact points? From: Manolache Adrian - 2010-02-11 14:07:56 Attachments: Message as HTML ```Hi! I was wondering if there is a better way for finding the contact points in 2D when using SAT. Here's what i currently use: Find the two objects positions pos1New and pos2New that represent the positions when the two objects are just touching and are about to collide if moved further. Find the minimum translation vector, let it be vectMTD. Take polygon1 in position pos1New and find the minimum of projecting it's vertices onto vectMTD. Also store the points that cause this minimum projection measure int list L1. Build a separating plane using vectMTD and one of these points detected. Now build a second list(L2) of points that lie on this plane but correspond to polygon2 in position pos2New. If one of the lists has 1 point an the other two then we have vertex-edge case, if both have one point then we have vertex-vertex case. If both lists have two points than we have edge-edge case. We calculate a new plane along the edge of the polygons using a normal perpendicular to vectMTD and located in the origin. Next the for points are sorted based on their distance to the plane. The second and third point define the line of collision. Are there any flaws with this approach? ```

 [Algorithms] Something wrong with this SAT method for finding contact points? From: Manolache Adrian - 2010-02-11 14:07:56 Attachments: Message as HTML ```Hi! I was wondering if there is a better way for finding the contact points in 2D when using SAT. Here's what i currently use: Find the two objects positions pos1New and pos2New that represent the positions when the two objects are just touching and are about to collide if moved further. Find the minimum translation vector, let it be vectMTD. Take polygon1 in position pos1New and find the minimum of projecting it's vertices onto vectMTD. Also store the points that cause this minimum projection measure int list L1. Build a separating plane using vectMTD and one of these points detected. Now build a second list(L2) of points that lie on this plane but correspond to polygon2 in position pos2New. If one of the lists has 1 point an the other two then we have vertex-edge case, if both have one point then we have vertex-vertex case. If both lists have two points than we have edge-edge case. We calculate a new plane along the edge of the polygons using a normal perpendicular to vectMTD and located in the origin. Next the for points are sorted based on their distance to the plane. The second and third point define the line of collision. Are there any flaws with this approach? ```
 Re: [Algorithms] Something wrong with this SAT method for finding contact points? From: - 2010-02-11 14:46:40 ```-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA256 > Hi! I was wondering if there is a better way for finding the contact > points in 2D when using SAT. Here's what i currently use: > > Find the two objects positions pos1New and pos2New that represent > the positions when the two objects are just touching and are about > to collide if moved further. Find the minimum translation vector, > let it be vectMTD. > > Take polygon1 in position pos1New and find the minimum of projecting > it's vertices onto vectMTD. Also store the points that cause this > minimum projection measure int list L1. > Build a separating plane using vectMTD and one of these points > detected. Now build a second list(L2) of points that lie on this > plane but correspond to polygon2 in position pos2New. > > If one of the lists has 1 point an the other two then we have > vertex-edge case, if both have one point then we have vertex-vertex case. > If both lists have two points than we have edge-edge case. We > calculate a new plane along the edge of the polygons using a normal > perpendicular to vectMTD and located in the origin. Next the for > points are sorted based on their distance to the plane. The second > and third point define the line of collision. Hi Adrian, In 2d there is only edge/vertex and vertex/edge cases. Once you have determined which case you have, you take the edge from one object and then build another edge from the vertex of the other using some metric to choose the other vertex (like vertex which produces most edge overlap, for example) and then simply project the vertices of one edge onto the other edge (clamping to edge extents) and visa versa, giving you two contact points for each object, penetration distances and a single normal (the normal from MTD). Thats what we did anyway :) Cheers, Paul. ********************************************************************** This email and any files transmitted with it are confidential and intended solely for the use of the individual or entity to whom they are addressed. If you have received this email in error please notify postmaster@... This footnote also confirms that this email message has been checked for all known viruses. Sony Computer Entertainment Europe Limited Registered Office: 10 Great Marlborough Street, London W1F 7LP, United Kingdom Registered in England: 3277793 ********************************************************************** P Please consider the environment before printing this e-mail -----BEGIN PGP SIGNATURE----- Version: PGP Universal 2.9.1 (Build 287) Charset: US-ASCII wsBVAwUBS3QSBHajGqjtoMHxAQgK/AgAjF9cOwqaP93BadjnQDfsyj2K/7Z4XjQ/ w96MEdcMopygc1mouIAUcDUsoTvhLABXBysQFLE7aNyoUEM1yFip9LS1oetqrB6q ATjfdUFz6OpuX1+qhWYqV2SiTu6GcX1akO1svQXuKxHKklZhaA1zHn0We0L0rQ8e DhIRMnaOFDpa0uxO9p3Zge67HKUINwqxEG6LbixjummZn6Qm5/7yx5QNpnKAlE90 fegXEBqLKAonEcmiDYvSWbIQHIfiZNnACqv++eSFRg1yzxMw9W6+MoWxk5ImPkPe /E2sK0JMPhVQmJQSYVJ+6QrM1mzCSH4lRldtv5tVud3RctaU6RTzeQ== =UVEJ -----END PGP SIGNATURE----- ```