   Convex geometry collision detection problems
  Hi there...I'm developping a rigid body simulator and the objects are moving correctilly, the air drag force is correctly applied and so on...The my problem is within collision detection :( uugghh!!...I'm using the separanting planes method to do it...and the problem is the slowdowns I get when the bodies collide...I'll give a brief description about how I'm doing the CD :Firstly I do an Axis Aligned Bounding Box (AABB) penetration test with tolerance in order to proceed to the hardcore computations(this 'with tolerance' means I'm using a 'collision tolerance' value here. It means that if the lower distance between the two bodies be lower than the collision tolerance, the objects are colliding.I'm not sure if this is the best method but through some analisys, I found that the Havok's Reactor(a pro dynamics simulator) uses this method.So, since I scale one of the bodies by 'collision tolerance' times, I must also scale its bounding box by the same value in all axis)...if it tests true, I go to the separating planes method. I take the body B and scale it by 'collision tolerance' times and then I try to find any seperating plane between A and B.First I test if there's any plane on the bodyB's triangles, then if there's any plane on the bodyA's triangles and finally if there's any plane on the bodies edges(if you know the separating planes method you know about what I'm talking)...If any separating plane be found, the lower distance between A and B is greater than collision tolerance or better, body A is not penetrating the scaled body B. If doesn't exist any separating plane, the bodies are within tolerance and we must solve the collision cuz it exists.To solve the collision, I need the contact points. Since the bodies are not in contact, each one has its own contact points. To find the contact points, I need to test if any vertex of A is within the "Voronoi Regions"(I hope you know it :)) of the body B and viceversa. the Voronoi region of a face is the face extruded by 'collision tolerance', of a vertex is a sphere with a radius of 'collision tolerance' and of an edge is a cylinder with a radius of 'collision tolerance'.I just test if any vertex is within any of these volumes.If yes, it is added to the contact points list. I do the the same with the body B's vertices. It is not all! we have the edges now!! just compute if they form a valid separating plane and if yes compute their lower distance.If lower than collision tolerance, they can be colliding. Project them in the same plane and compute the intersection point of these two segments...and so on...(I'm not specifying too much cuz it is a lot of crazy things!!!the text is already big!!).Then its just catch the points that has the lower distance between then use them to compute and apply impulses....UUUUuuuFFffFFfsss....Thats it...this is the part where I get a lot of slowdowns (but its working correctly:) and since I compute collisions by the distance, I need substeps or the bodies will easyly penetrate...and substeps make it a lot lower!!!And you're asking: "What does this crazy man really want?!?" ... :) I want to know if my method is a correct and famous one...I wanna know what is the best and most used method cuz I need speed here...I'll use it as a base to realyze one dream: develop my racing game :) :) :)Thanks a lot man...you're always helping me a lot and sorry for the LONG text :)Cya   
Quote:I want to know if my method is a correct and famous one...I wanna know what is the best and most used method cuz I need speed here...I don't have an answer to this question, but I'm working on the same sorts of things so I'll at least join in the discussion.Unless I'm mistaken, the separating planes approach is more or less equivalent to the separating axis method (with the plane normals corresponding to the potential separating axes). As you're obviously aware, this doesn't scale very well for arbitrary polyhedra due to the cross-product axes; the overall number of axes to test can quickly get into the hundreds or thousands for polyhedra of any complexity. As you also noted, this really only comes into play when the result is positive - determining non-intersection can generally be done quite quickly.Now, I'm not sure I'm clear on how the tolerances are being used. I gather you are using a discrete rather than continuous test, is that correct? The part that confuses my a little is where in prefacing the discussion of finding the contact points, you say 'since the bodies are not in contact'. It seems that even given the buffer, unless you were sure of a maximum bound on object displacement per frame, there would be no guarantee that the objects themselves (minus the buffer) would not be interpenetrating after an update.So I think there's something I'm misunderstanding here, which will probably limit the usefulness of any further input I might offer. The clipping of features to Voronoi regions seems somewhat impractical, but since I'm still not sure how the buffer is being used, I may just be missing the necessity of this method. I will say that I've worked on this problem without the buffer aspect, and in that context there are several shortcuts and optimizations for performing the separating axis test, and for determining the contact features. I'd be happy to discuss these further if they would be at all relevant to your application. More than that though, I'd be interested in better understanding the buffer and its purpose.Finally, it seems that even the best implementation of the SAT may not give  you the performance you're looking for for arbitrary polyhedra. I'm sure you've already considered this, but might a simpler bounding volume or set of bounding volumes suffice? If not, it might be worth looking into other algorithms besides the separating plane/axis method.   ;  thanks for reading and answering jyk...I want to ask you one thing: do you have msn?!? if yes, could you add me please?!? (xissburg@hotmail.com)The tolerances I'm talking about is the lower distance between the two objects to consider them in contact. Think about two spheres where we can easily compute their distances. If the distance between them be lower than the collision tolerance they are considered in contact. As I already said, Havok's Reactor uses this method. If you set a high collision tolerance value, the objects will collide even when they are far one from the aonther. Did you understand?There's another method I tried out but it didnot worked :( ...in this one, you check if the objects are penetrating using SAT. If yes, back in time and recheck if they are penetrating yet and so on even they be within tolerance(the same way I described above)...you'll need many integrations to do it and it can be too hardcore :P ...As I said above, the my collision detection is simply: if the lower distance between the two bodies be lower than collision tolerance, they are colliding, but in the truth, they are not!!It is hard to explain man!! but lets continue ;);Not on msn unfortunately, but meanwhile I'll be happy to continue the discussion here :)Not being in the industry myself, I don't know what coldet algorithms are used in pro applications. IMO, robust and reliable collision detection is one of the most difficult things to implement successfully, and my guess is that those who figure it out aren't particularly inclined to reveal how they did it. (Note that Id was kind enough to include both their physics and math code in the Doom 3 SDK, but the CD code is conspicuously absent!)Back to the tolerances. I read the document 'HavokPrimer.pdf', which I assume is where you got the info about the tolerances. However, I think the current version of Havok uses continuous methods, and that the discrete test + buffer approach is perhaps no longer in use.So I do think I understand your original post now, in light of reading the Havok doc. It seems the idea is to always try to catch intersections after the buffer regions have begun to intersect, but before the actual objects have begun to intersect; I'm assuming this is why you can assume the actual objects are not interpenetrating when it comes time to compute the contact points. The particular requirement of catching intersection in the 'window' after the buffer regions have intersected but before the objects have intersected seems like it would be difficult to maintain in a general simulation. If this is how the first version of Havok did it, it obviously must be a viable method, but my guess is that it's been superseded by other approaches. The iterative 'backtracking' method you mentioned in your last post has probably also fallen out of favor, I would guess, due its inefficiency and the fact that it doesn't really solve the inherent problems of discrete methods, but only moves them to a different scale.So this brings us to continuous collision detection, which I imagine will soon be standard in games if it isn't already. The SAT test that you mentioned (which again is closely related to the separating plane test) can be extended to incorporate constant linear velocity, and to return the first time of intersection along with a collision normal and contact manifold. Again though, if you absolutely require complex arbitrary convex geometry, it may not be a suitable solution due to the scaling problem. An alternative is GJK, which might be a viable option for your simulation.This is just IMO, but although implementing these algorithms (SAT, GJK, etc.) from a purely functional perspective is certainly challenging, I don't think that's 'the hard part', so to speak. If one aspires to create production-quality software, it must be the case, more or less, that your collision detection algorithm will never fail under any circumstance that will be encountered in practice. In my experience so far, meeting this requirement is where the true challenge of collision detection programming lies.I'll certainly be interested to hear any further thoughts you or anyone else might have on the subject. As an independent developer who won't be licensing Havok anytime soon, I see robust collision detection as perhaps the biggest obstacle to creating the kinds of simulations I want to create. So I'm always interested in discussing the topic and hearing about other people's experiences working on this problem.   ;  Oh yeah man...develop a good collision detection system is really a hard task...I get hurt a lot when trying it out ;)Many times I catch my notebook and try to think about what would be a good method but...if even professionals get some trouble when developping it, I have no chances within :( ...I'm not so experienced within math and physics since I just finished the college last year and I'm not studying at any high school. So I don't know many methods I'm just trying to know them right now. I want to find a good method to detect collisions between two convex polyhedra, nothing else... but its being a hard task to find any.I don't have anymore words to say about cuz what I know was already said!! :P Sorry but I'll not be able to continue the discussion this way...ehehh...Thats all and thanks for the help   ;  Hi xissburg!Basically, Convex collision detection involves two problems:1) Find separating axis and determine if the two convex are colliding.2) Get contact points, contact normal and penetration depth.For the 1st problem, you can use Separating Axis Theorem as jyk said.But it is quite expensive for convex with many faces. So is recomended to use a GJK algorith. Take a look to FreeSolid, get it at sourceforge.net.For the 2nd problem, you must develop an algorithm that finds the contact feature of each convex (Wich face?,Wich edge?) those must be aligned with the separating axis. For this, I think, only the Lin-Canny V-Clip algorithm can do.  I've got the V-Clip, but it is in Java. I want to translate this code for C++, but I don't have time right now. Please download it from:http:/usuarios.lycos.es/tripticon/vclip.zipTake a look, and if you can translate this to C++, would be kind of you share it with us. So go ahead, and surely I'll reward you giving my Trimesh-Trimesh collision method.(Really works) ;  Hello leoptimus...Sorry but I have no idea about what is GJK, V-Clip and Lin-Canny !!!And have another thing to talk about...My wish is not develop a rigid body simulator(I'm doing it just to learn :P), my wish is develop a racing game. I'm not sure if I should use the same methods used in a rigid body simulator to do it. Should I?!? Aren't them too expensive for a game?!?   ;  Aha, let's see... your goal is to develop a racing game right? Why don't you've tried a ready-to-use physics library? Start with Newton. Take a trip on their page : http://newtondynamics.com/downloads.htmlIt has good demos, including a racing car demo! The good new is Newton is free for comercial use Another good library is Tokamap, free for comercial use too.The drawback for those libraries is that they aren't open source, limiting your games to run on Windows only.If you need to write games for Mac or Consoles, I suggest you using Open Dynamics Engine ( ODE: http://www.ode.org/ It's open source and Free) , but it needs more work.   ;Quote:Original post by leoptimusThe drawback for those libraries is that they aren't open source, limiting your games to run on Windows only.If you need to write games for Mac or Consoles, I suggest you using Open Dynamics Engine ( ODE: http://www.ode.org/ It's open source and Free) , but it needs more work.For the record Newton works on Mac and Linux, I used on the Mac and in Linux.;  I hate "ready-to-use physics libraries"....I want to develop my own...I don't want to 'just' develop a racing game, I want to learn how to develop a racing game.If I use a library like this I'll not learn anything else...and I don't like to use them cuz they are developped for the ones who doesn't have the capacity of learn how to do these things...I have the capacity to, I just need some help or articles about cuz I can't learn these things alone!!