   abc
  a   
  Hi,I have implemented alot of what is the baraff papers in 3D, and have given some thought to a 2D approach. As i see there are two groups, continuous and discrete.You could get a decent system up by simply subdividing each animation step into smaller steps and using common primitive intersection methods(line against line) to find the first step that resulted in penetration. With reasonable step sizes you could get reasonable results.I have been thinking about a 2D continous method i have been thinking about testing, where you take the difference between two animation frames and build a quadrilateral from the swept area and test this against the environment. Interpolational could be used to find the exact (almost, need to make a few approximations )time of contact.;Quote:Original post by ccherngSee the thing I don't understand is that with discrete collision detection you find the time of impact within some error tolerance by maybe doing a binary-like search testing for intersection each iteration. But then once you advance to the time of impact how do you find the contact manifold? None of the polygons are going to be touching each other due to the fact that an error tolerance was used and numerical error. So then how do you generate the contact manifold robustly?What types of objects do you want to represent, i.e.:1. Convex polygons only, or2. General convex objects (including circles, ellipses, and so on), or3. Arbitrary non-convex objects?   ;Quote:Original post by ccherngconvex polygons for now. But are arbitrary polygons actually harder? Can't you decompose a polygon into convex polygons.Arbitrary polygons are harder, but you can decompose them into a set of connected convex polygons if you need to. For continuous collision detection between convex polygons in 2d with time of intersection and contact manifold, the quick answer is: separating axis theorem. Too lazy to linkify everything at the moment, but check the SAT docs at geometrictools.com; google for 'separating axis theorem', which will turn up as one of the first few hits a nice article and tutorial with interactive graphics; download oliii's tutorials and code; and look for threads in this forum in which oliii, I, and others have explained the SAT in some detail.The basic idea is to process all potential separating axes, which are the normals to the polygon edges, and track the maximum first time and the minimum last time of intersection. If the former is ever greater than the latter, there is no intersection. Otherwise, the former is the first time of intersection and you proceed to the contact manifold step. The contact features are the support features along the axis corresponding to the first time of contact. Since this axis will always be normal to a polygon edge, you already know one of the features, which is that edge. The other feature is an edge or vertex of the other polygon, which can be found fairly easily. The only case that requires non-trivial feature clipping is edge-edge, which can be done by clipping one of the edge segments to the other. This leaves you with one (vertex-edge) or two (edge-edge) contact points to feed into the physics simulator.That's a rather cursory explanation, but that plus the references I mentioned should give you a good overview of the algorithm.   ;  oliii's polycolly tutorial should have what you need, or at least some of it.   ;Quote:Original post by ccherngBut this SAT test with the assumption of only translational velocity clearly is of no use if one object is at translational rest but rotates into another object.Correct (assuming you're referring to the continuous SAT test). The way I deal with this (which I don't know to be the best way) is to roll the continuous and discrete tests into one test. That is, the test a) tells you whether the objects intersect at time 0 or at time > 0, b) returns penetration depth for the former and first time of intersection for the latter, and c) returns contact points and normal for both. This way, the situation you describe will still be caught, and the appropriate action (say, pushing the objects away from each other to resolve the collision) can be taken. Or, if you're interfacing with a physics simulator, you can feed it the necessary info to deal with the interpenetration. There are other ways to approach it as well; in general, collision detection and response can get pretty involved (even in a simplified context such as 2d with convex polygons).   