GJK vs Raycasting
Author
I give up! Gino GJK doesn't work for me.
It gives me a bumpy collision behavior, and until now I can't deal with rounding errors. Using FreeSolid 2.0 was a disaster.
I don't understand it well and that tricky set of precalculated bits goes so far for my programming skills.
So, thinking on GJK principle, I've got the idea that it would better implement some kind of ray casting algorithm for find collision contact points and interpenetration.
That algorithm may improve heuristics, A*, or gradient hill climbing for find nearest features-points.
Also it may combine GJK support mapping with ray casting.
And, think about objects that move too fast: traditional collision algorithm dismiss their collision allowing them to pass through. Isn't Raycasting the God solution for this?
However, I have a doubt. Does anybody have successful results with GJK or FreeSolid?
Thanks.
GJK is great, and is simple to understand, but the main problem it has, in my opinion, is that when you implement it, you're bound to encounter lots of floating point presision problems, doing a robust implementation is hard, specially if your math is rusty.
I recently bought Gino's book and I am implementing the EPA algorithm into FreeSOLID, but right now, as it is, FreeSOLID is only good to determine if 2 objects collide, getting Depth Penetration involves calls to dtProceed() before calling dtTest().
What results are you looking for? FreeSOLID is good enought for Collision Detection as is if you only need to know if objects collide, if you need depth penetration, you need to set Smart collision detection and call dtProceed() before calling dtTest, you need to do your own collision response though.
I recently bought Gino's book and I am implementing the EPA algorithm into FreeSOLID, but right now, as it is, FreeSOLID is only good to determine if 2 objects collide, getting Depth Penetration involves calls to dtProceed() before calling dtTest().
What results are you looking for? FreeSOLID is good enought for Collision Detection as is if you only need to know if objects collide, if you need depth penetration, you need to set Smart collision detection and call dtProceed() before calling dtTest, you need to do your own collision response though.
Author
Thanks for tell your experience Kwizatz.
However, I think that FreeSolid doesn't find contact points very well when you forces it to work with single float precision. That's what I was trying.
Also, I've implemented my own GJK algorithm with my own support mapping. But it becomes worst.
And add the problem when the objects moves too fast. It didn't resolve interpenetration very well.
So, FreeSolid is good enough for Physic collisions? I don't think so.
But just think on ray tracing. How sweet it would be if it resolves collisions when objects moves too fast, and how easy would be finding collision contacts.
However, I think that FreeSolid doesn't find contact points very well when you forces it to work with single float precision. That's what I was trying.
Also, I've implemented my own GJK algorithm with my own support mapping. But it becomes worst.
And add the problem when the objects moves too fast. It didn't resolve interpenetration very well.
So, FreeSolid is good enough for Physic collisions? I don't think so.
But just think on ray tracing. How sweet it would be if it resolves collisions when objects moves too fast, and how easy would be finding collision contacts.
Well, if the objects are moving too fast, they may be tunneling thru each other, for example, a sphere crosses a wall because it's initial position as well as it's last position do not present a collision with the wall, but each of them are on either side of the wall:
There are several ways to get arround this problem, one is to subdivide the motion vector, so you check for collisions at the middle of it, and then the middle of the middle, etc recursivelly to a maximim number of recursions you set untill you find a collision or the number of maximum recursions is met.
Another option is to create a bounding volume for the moving objects trajectory, for example, the bounding box of the sphere at the initial position plus the bounding box of the sphere at the final position and check if this bounding box collides with the Wall's bounding box, if it does, you know the sphere collides at some point with the wall, and you need to find when that happens.
There is another option using GJK, what you do is that you get support mappings for the moving object at the inital and final position, and use those instead of the static ones, sorry I cant explain much about this method right now, currently I am trying to get EPA correctly implemented. [sad]
There are several ways to get arround this problem, one is to subdivide the motion vector, so you check for collisions at the middle of it, and then the middle of the middle, etc recursivelly to a maximim number of recursions you set untill you find a collision or the number of maximum recursions is met.
Another option is to create a bounding volume for the moving objects trajectory, for example, the bounding box of the sphere at the initial position plus the bounding box of the sphere at the final position and check if this bounding box collides with the Wall's bounding box, if it does, you know the sphere collides at some point with the wall, and you need to find when that happens.
There is another option using GJK, what you do is that you get support mappings for the moving object at the inital and final position, and use those instead of the static ones, sorry I cant explain much about this method right now, currently I am trying to get EPA correctly implemented. [sad]
Quote:Original post by Kwizatz
Well, if the objects are moving too fast, they may be tunneling thru each other, for example, a sphere crosses a wall because it's initial position as well as it's last position do not present a collision with the wall, but each of them are on either side of the wall:
There are several ways to get arround this problem, one is to subdivide the motion vector, so you check for collisions at the middle of it, and then the middle of the middle, etc recursivelly to a maximim number of recursions you set untill you find a collision or the number of maximum recursions is met.
Another option is to create a bounding volume for the moving objects trajectory, for example, the bounding box of the sphere at the initial position plus the bounding box of the sphere at the final position and check if this bounding box collides with the Wall's bounding box, if it does, you know the sphere collides at some point with the wall, and you need to find when that happens.
There is another option using GJK, what you do is that you get support mappings for the moving object at the inital and final position, and use those instead of the static ones, sorry I cant explain much about this method right now, currently I am trying to get EPA correctly implemented. [sad]
From what I heard, the proper way to implement this actually to consider time as an extra dimension, and then, knowing the object's movement during one frame, you can perform an intersection test in 4 dimensions, and that gives you the point of intersection, comprising the time where the collision took place.
Doing something like this, you can accurately detect collisions, no matter the velocity of the objects. The problem, however, is that this becomes very hard to do for more complex shapes, such as oriented bounding boxes.
If I may suggest another approach that will partially resolve the problem of objects getting through things. You could only subdivide the object's trajectory if the object's initial and final bounding volumes do not intersect one another (if the object moves fast enough so that there is actually a "leap" between its initial and final positions). This wouldn't always work correctly for small obstacles, but it would keep things from going through walls without using too much CPU power.
The CSO has another interesting property: the intersection, if any, between the relative velocity vector and the CSO of two objects in their initial positions gives you the time of intersection, as well as information about the contact normal and features.
To do this you need to be able to intersect a ray with a convex object that is only known through its support mapping. The technique is described in a paper by van den Bergen, and can also be used for general raytracing against convex objects. This technique extends GJK to support swept intersections, and solves the aforementioned tunnelling problems. I believe that the newest version of SOLID does include, or will include, this feature.
Like many others I've been slowly chipping away at my own GJK implementation. Although I'm confident that I'll get it eventually, for someone at my level (which I'd describe as intermediate) it's not a trivial undertaking. From my experience with the algorithm, the 'devil is in the details', as they say. However, I suspect that it will only become more popular due to its generality and support of static and swept intersection between most types of convex objects, including combinations that have no other straightforward solution (that I know of at least).
To do this you need to be able to intersect a ray with a convex object that is only known through its support mapping. The technique is described in a paper by van den Bergen, and can also be used for general raytracing against convex objects. This technique extends GJK to support swept intersections, and solves the aforementioned tunnelling problems. I believe that the newest version of SOLID does include, or will include, this feature.
Like many others I've been slowly chipping away at my own GJK implementation. Although I'm confident that I'll get it eventually, for someone at my level (which I'd describe as intermediate) it's not a trivial undertaking. From my experience with the algorithm, the 'devil is in the details', as they say. However, I suspect that it will only become more popular due to its generality and support of static and swept intersection between most types of convex objects, including combinations that have no other straightforward solution (that I know of at least).
Author
Thanks!
Yeah! colliding a ray against a convex is a simple operation. I'll read van den Bergen paper for that.
But there is a question. How many sample rays will be enough for find collisions? How I should direct them for that goal?
It's CPU expensive? Probably.
Focus on GJK, at this time I didn't know if any physics engine uses it for collisions. Where is it? It GJK useful?
On physics engines, there around are separating axes methods, like ODE, and Voronoi clipping collisions in others. But I didn't have notice about GJK. Which engine implements it?
Yeah! colliding a ray against a convex is a simple operation. I'll read van den Bergen paper for that.
But there is a question. How many sample rays will be enough for find collisions? How I should direct them for that goal?
It's CPU expensive? Probably.
Focus on GJK, at this time I didn't know if any physics engine uses it for collisions. Where is it? It GJK useful?
On physics engines, there around are separating axes methods, like ODE, and Voronoi clipping collisions in others. But I didn't have notice about GJK. Which engine implements it?
Quote:Original post by leoptimus
I give up! Gino GJK doesn't work for me.
It gives me a bumpy collision behavior, and until now I can't deal with rounding errors. Using FreeSolid 2.0 was a disaster.
I don't understand it well and that tricky set of precalculated bits goes so far for my programming skills.
So, thinking on GJK principle, I've got the idea that it would better implement some kind of ray casting algorithm for find collision contact points and interpenetration.
That algorithm may improve heuristics, A*, or gradient hill climbing for find nearest features-points.
Also it may combine GJK support mapping with ray casting.
And, think about objects that move too fast: traditional collision algorithm dismiss their collision allowing them to pass through. Isn't Raycasting the God solution for this?
However, I have a doubt. Does anybody have successful results with GJK or FreeSolid?
Thanks.
This is the same conclusion I got a while back. In my opinion all these new books and papers about collision are nothing but a scam. All they do is a reimplementation of existing algorithms like http://web.comlab.ox.ac.uk/oucl/work/stephen.cameron/distances/ or some variance of Gilbert, Johnson and Keerthi they distance algorithm.
They all say their method is better than the other but when you come to see it not different at all and in fact most of then are mediocre at best.
I had tested Icollide and Solid in the pass and I can confirm that neither of them is reliable or as fast as they claim they are.
I do not know how physics engine are doing this but I am convinced they are doing something none of the others of theses books know. Take a look at collision in engine like Havok, Novodex and Meqon, it is almost perfect.
I do not know about you guys but I gave up and since I cannot afford a commercial library I settled for the Newton engine.
The engine can be used as a standalone collision library and it has a very clean interface, it is fast and very robust, and it keeps improving fairly frequently. Take a look at this video
http://www.newtondynamics.com/downloads/ContinueColl.mpg
Quote:Original post by leoptimus
Focus on GJK, at this time I didn't know any physics engine that uses it for collisions. Where is it? It GJK useful?
On physics engines, there around are separating axes methods, like ODE, and Voronoi clipping collisions in others. But I didn't have notice about GJK. Which engine implements it?
Well, ODE users have shown interest in using GJK for it in the past, some claim that they managed to implement it, but as far as I know, no one has made their implementation public, either they don't want to (ODE BSD license allows this), or they don't feel its good enought to see the public light.
SOLID 3.5 cannot be used with ODE because of License conflicts (ODE is LGPL or BSD depending on which one the user wants to avide to, and SOLID 3.5 is GPL, so if ODE uses SOLID 3.5, it must become GPL).
FreeSOLID is LGPL and there is no licensing problem using it with ODE, however, because the EPA (Expanding Polytope Algorithm) for penetration depth is not implemented in it, it is useless for ODE, as ODE requires the penetration depth as a normal vector + a Scalar lenght [sad], this is why I want to get EPA into FreeSOLID.
Edit: Currently ODE uses its own collision detection for primitives such as boxes, spheres, planes and others (I have no idea whats the approach there), it uses OPCODE for triangle meshes, but that is not entirelly stable.
Author
Thanks Jovani, you are right. Focus on existing engines, do you know if I can use Newton for a comercial game at Free?
Whatever, I still interested on raycasting: it sounds weird, but I hope that if there is an engine that have achieved it, it will the best, or better around.
Also thanks to Kwizatz for give your opinion. Do you have a running demo of your GJK implementation? Please share it with us.
Whatever, I still interested on raycasting: it sounds weird, but I hope that if there is an engine that have achieved it, it will the best, or better around.
Also thanks to Kwizatz for give your opinion. Do you have a running demo of your GJK implementation? Please share it with us.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
