Could someone enlighten me as to how convex collision works?
by Josh Albrecht · in Torque Game Engine · 06/30/2003 (7:07 pm) · 16 replies
I would like to use the built in collision functions in torque within the map2dif exporter. I've created ConvexFeature instances for two brushes, and initialized them correctly.
However, when I call ConvexFeature::collide, the collisionList.count is never incremented, essentially meaning that there are no collisions. However, I know that the two shapes should collide because I set them up that way in the .map file.
The .map file is simply two tetrahedrons, one with a point sticking into the other, obviously colliding.
Now, as ConvexFeature::collide progresses, I notice that it stops in the same place every time. It loops through all vertices, and calls testVertex for each. In testvertex, the execution stops right here:
ConvexFeature::collide also calls testEdge, which does something very similair:
I do not understand what these distances represent, or how the function works. I also have no idea what sqrDistanceEdges does.
If anyone understands this, I'd greatly appreciate some hints. Thanks! :)
However, when I call ConvexFeature::collide, the collisionList.count is never incremented, essentially meaning that there are no collisions. However, I know that the two shapes should collide because I set them up that way in the .map file.
The .map file is simply two tetrahedrons, one with a point sticking into the other, obviously colliding.
Now, as ConvexFeature::collide progresses, I notice that it stops in the same place every time. It loops through all vertices, and calls testVertex for each. In testvertex, the execution stops right here:
// Point near the plane?
F32 distance = mDot(face->normal,v - p0);
if (distance > tol || distance < -tol)
//code never continues
continue;ConvexFeature::collide also calls testEdge, which does something very similair:
// Get the distance and closest points
Point3F i1,i2;
F32 distance = sqrDistanceEdges(s1, e1, s2, e2, &i1, &i2);
if (distance > tolSquared)
//code never continues
continue;I do not understand what these distances represent, or how the function works. I also have no idea what sqrDistanceEdges does.
If anyone understands this, I'd greatly appreciate some hints. Thanks! :)
#2
http://www.garagegames.com/mg/forums/result.thread.php?qt=11865
Though that focues more on the actual collide routine than the queuing. Sorry that I cant help any more than that. :(
(that thread answered my original question, so I havent bothered looking any deeper)
08/08/2003 (4:51 pm)
Another related thread that you might want to check out is:http://www.garagegames.com/mg/forums/result.thread.php?qt=11865
Though that focues more on the actual collide routine than the queuing. Sorry that I cant help any more than that. :(
(that thread answered my original question, so I havent bothered looking any deeper)
#3
Well, from what I'm seeing vehicles use GJK-type collision checks and that is an algorithm which checks for minimum distances between convex hulls, correct?
It appears those minimum distances need to be less than 0.1 meters (units) using the default vehicle datablock (collisionTol) in order to queue a vehicle collision, is this correct?
If so, then I'm still unclear on why with integration even set to 1 (checking convex positions once per 32ms tick) and I can clearly see two convex polyhedrons with about 700 triangles (180 - see below) intersecting for many ticks, the engine is stll not noticing the collision in the proper places and the onCollision script code isn't called on these guys sometimes (albeit infrequent). Can the detail of my convex be confusing things here?
Another thing I've noticed is that once one convex is fully encapsulated within another, then collisions won't take place until the faces are actually touching again... i'm assuming that has to do with the distances between the convex being calculated as larger than the minimum required, but I would think if one was within another the convex check should return zero distance.
Any more hints from anyone would be appreciated as I want to move away from collisions and onto something fun! hehehe
08/08/2003 (6:02 pm)
Thanks Josh, I hadn't found that thread in my search on collisions.Well, from what I'm seeing vehicles use GJK-type collision checks and that is an algorithm which checks for minimum distances between convex hulls, correct?
It appears those minimum distances need to be less than 0.1 meters (units) using the default vehicle datablock (collisionTol) in order to queue a vehicle collision, is this correct?
If so, then I'm still unclear on why with integration even set to 1 (checking convex positions once per 32ms tick) and I can clearly see two convex polyhedrons with about 700 triangles (180 - see below) intersecting for many ticks, the engine is stll not noticing the collision in the proper places and the onCollision script code isn't called on these guys sometimes (albeit infrequent). Can the detail of my convex be confusing things here?
Another thing I've noticed is that once one convex is fully encapsulated within another, then collisions won't take place until the faces are actually touching again... i'm assuming that has to do with the distances between the convex being calculated as larger than the minimum required, but I would think if one was within another the convex check should return zero distance.
Any more hints from anyone would be appreciated as I want to move away from collisions and onto something fun! hehehe
#4
You should have something like 20 polys in your convex. Not 700. More polys = ALOT slower. I have no idea how the engine would react with collision meshes that complicated, but I know that it wont function properly.
08/08/2003 (6:22 pm)
Uh, 700 polys in a convex!? Oh my!You should have something like 20 polys in your convex. Not 700. More polys = ALOT slower. I have no idea how the engine would react with collision meshes that complicated, but I know that it wont function properly.
#5
PS- I just checked my max model and I'm using 180 triangles for the col-1 mesh not 700, hehe, i exaggerate sometimes, but maybe its still too many.
PPS - Vehicles only use Col-1, not the other 8 possible collision meshes, right?
PPPS - Final Postscript? Ok, I just changed a few things and I just witnessed my missing collision happen with two vehicle hulls, one with 20 poly's and one with 80. So... what is wrong here? I don't even want vehicle impulses calculated on collisions, I just want to notify script and it seems that the mConvex.getClosestState and getCollisionInfo functions in updateCollision should be handling this just fine.
PPPPS- Oops, I had another thought. Do these vehicle collision functions use the LOS collision mesh anywhere? I don't have one on my vehicles.
08/08/2003 (6:26 pm)
Ok, I'll reduce it and see if things work any better. It seemed fast enough for now but I haven't done any real speed testing. I would LIKE to think that a convex with maybe 300 polys is possible with this engine because I might like to have high detail levels which properly include/reject sunlight beams like Melv's and other neato features. (ok, so maybe the answer to that one is to use more detailed LOS-convex's but less detailed collision meshes...) I have spherical convex's, so more triangles seemed more realistic.PS- I just checked my max model and I'm using 180 triangles for the col-1 mesh not 700, hehe, i exaggerate sometimes, but maybe its still too many.
PPS - Vehicles only use Col-1, not the other 8 possible collision meshes, right?
PPPS - Final Postscript? Ok, I just changed a few things and I just witnessed my missing collision happen with two vehicle hulls, one with 20 poly's and one with 80. So... what is wrong here? I don't even want vehicle impulses calculated on collisions, I just want to notify script and it seems that the mConvex.getClosestState and getCollisionInfo functions in updateCollision should be handling this just fine.
PPPPS- Oops, I had another thought. Do these vehicle collision functions use the LOS collision mesh anywhere? I don't have one on my vehicles.
#6
In that first code snippet it is determining how far point 'p0' is from the plane 'face'. Note that it is only allowing a collision if the point is within plus or minus 'tol' of the face. So it not going to detect collision if the colliding point is already more that 'tol' within all faces of the other collision mesh.
08/08/2003 (7:55 pm)
@JoshIn that first code snippet it is determining how far point 'p0' is from the plane 'face'. Note that it is only allowing a collision if the point is within plus or minus 'tol' of the face. So it not going to detect collision if the colliding point is already more that 'tol' within all faces of the other collision mesh.
#7
08/08/2003 (9:13 pm)
I'm finding that when this problem occurs for me, findClosestState is returning a state with a distance of 0, but then I get nothing added to the collision list when getCollisionInfo does its thing by checking feature collisions. It sounds similar to Josh's problem. I would understand if the bounding boxes are touching but features are not touching yet, but that is not the case either. Hmmm, it seems the code should be returning a collision whenever any vertex is within the other's convex, but maybe thats too slow compared to this gjk method. I'm confused.
#8
@kevin: But it would detect a collision because an edge would be going through a face in that case, right?
08/08/2003 (9:17 pm)
@Jim: Read the docs maybe, because I dont know very much about the vehicle collision stuff.@kevin: But it would detect a collision because an edge would be going through a face in that case, right?
#9
Another note for vehicles. It appears that in updateCollisions, the findClosestState call uses the gjkCollisionState::distance(blah blah blah) virtual method, but then Convex::getCollisionInfo is being called and it appears that the gjkCollisionState::getCollisionInfo method is never called. Shouldn't it be? *sigh*
08/08/2003 (10:39 pm)
@Josh: (since we're doing the @ thing) I haven't found a good document about the collisions, but I think I'm having the same problem you are, so if you figure anything out, please post it here.Another note for vehicles. It appears that in updateCollisions, the findClosestState call uses the gjkCollisionState::distance(blah blah blah) virtual method, but then Convex::getCollisionInfo is being called and it appears that the gjkCollisionState::getCollisionInfo method is never called. Shouldn't it be? *sigh*
#10
08/08/2003 (11:32 pm)
Are you sure that your, uh, collision hulls are actually convex?
#11
08/09/2003 (12:48 am)
Uhm, pretty sure, i'll double check it again for the convex that was 80 polys. The one that was 20 polys was fershur as it was an unaltered sphere, but the other one was tweaked a little from a sphere, so I'll make sure it still is. I was careful about this when I originally created them though, so I figure they are.
#12
That second piece of code looks like it is determining the closest distance between two line segments. I'd guess that it returns in i1 and i2 the points on each line segment that are closest to the other line segment.
08/09/2003 (8:28 am)
That first check is just checking points to planes, not line segments to planes. So unless any point is within tol of the plane it won't register a collision. Wouldn't matter if any particular line segment intersected the plane if both its endpoints were greater than tol from the plane.That second piece of code looks like it is determining the closest distance between two line segments. I'd guess that it returns in i1 and i2 the points on each line segment that are closest to the other line segment.
#13
From what I'm gathering here, it looks like gjk is only used to check collision state distances (for their OOBBs?) in findClosestState, but then it is not really used when the code calls getCollision Info. The code appears to use Convex feature comparisons for distance which won't always return a collision if the wires of one mesh are not close enough to the wires of the other intersecting mesh. Does this sound correct?
I'm starting to think that my best solution would be to have objects with multiple bounding boxes contained within one. Does torque support this? I assume it must ... I'll try to figure out how headshots worked in T2.
08/09/2003 (12:12 pm)
So it appears the code is checking for vertices that are within 0.1 meters (vehicle default) from another object face, or edges which are within 0.1 meters from other object edges, but not really checking for any sort of intersection between the convex hulls other than that? That would explain my difficulties. Isn't there a quick way to check if the convex objects are actually intersecting eachother anywhere? Would it be too time consuming to do something like loop through all convex vertices and see if they are inVolume for the objects in the workingCollisionSet? The current code appears to do that only for the collision points to determine collision normals and it mentions in there that even that is a bit slow. I know with BSP type objects it should be very quick to find if any points lie within a 'wall'... maybe I should be using interiors instead of shapes...From what I'm gathering here, it looks like gjk is only used to check collision state distances (for their OOBBs?) in findClosestState, but then it is not really used when the code calls getCollision Info. The code appears to use Convex feature comparisons for distance which won't always return a collision if the wires of one mesh are not close enough to the wires of the other intersecting mesh. Does this sound correct?
I'm starting to think that my best solution would be to have objects with multiple bounding boxes contained within one. Does torque support this? I assume it must ... I'll try to figure out how headshots worked in T2.
#14
It seems to be running fast enough with my tested vehicles which have collision meshes with 80 and 20 triangles each (2 types of objects), and they are now colliding with integration rate set to one and large velocities without any ray testing. The code is opting out of filling the whole collision list as soon as it finds a single vertex within another convex and just queues a single collision for notifyCollision. I have already had to remove some of the collision impulse functionality that Tim added which bounce vehicles apart but I don't need any more collision information other than just to know if two convex's are intersecting at all.
(in my sim i am not implementing elastic collisions, just notifying script that a collision happened)
It seems like this solution is working for me, so I'm on to the next part! I hope... If someone knows of a quicker way to find intersection between convex's, please let me know.
08/10/2003 (4:07 pm)
Well, I wound up rewriting a few of the collision functions for my spacevehicle class (and added an intersect function to the Convex class) Now, rather than checking for features within a tolerance, i'm loading up the features and then comparing the convex vertices using inVolume against the other convex objects in the working list.It seems to be running fast enough with my tested vehicles which have collision meshes with 80 and 20 triangles each (2 types of objects), and they are now colliding with integration rate set to one and large velocities without any ray testing. The code is opting out of filling the whole collision list as soon as it finds a single vertex within another convex and just queues a single collision for notifyCollision. I have already had to remove some of the collision impulse functionality that Tim added which bounce vehicles apart but I don't need any more collision information other than just to know if two convex's are intersecting at all.
(in my sim i am not implementing elastic collisions, just notifying script that a collision happened)
It seems like this solution is working for me, so I'm on to the next part! I hope... If someone knows of a quicker way to find intersection between convex's, please let me know.
#15
08/13/2003 (10:09 am)
Jim: Would love to see this as a resource. Having the ability to support more complex collision shapes seems goodness.
#16
PS - Thanks for YOUR space resource Wendell, it helped alot to get me started with using torque for my space environment. I especially liked the odbc database of stars, though I am not using it in my game.
08/13/2003 (12:27 pm)
I'll see what I can do. It won't appeal to everyone, because the code isn't currently supporting the multiple-collision points required for proper elastic collision handling (bouncing off objects), just reporting a single collision vertex back for any intersecting shapes. However, it has helped me alot for my project and it allows my space vehicles to collide properly even at fairly high velocities. It is still possible that an object could pass completely through another object within one tick if the velocity gets too high, but its working well for me. I'm still thinking there must be a quicker way to detect intersection between two convex shapes than checking each vertex, but I haven't found it yet. If I find it, I may reimplement the functions so that they will report a full collision list back like the original vehicle updateCollision functions do.PS - Thanks for YOUR space resource Wendell, it helped alot to get me started with using torque for my space environment. I especially liked the odbc database of stars, though I am not using it in my game.
Torque 3D Owner Jim Rowley
Would someone care to enlighten the dimmer of us ( no offense Josh :D ) as to how this convex collision stuff works? I'm trying to research collisions in some of my reading materials, but I thought someone might be able to give a good quick overview as I haven't yet found one on these forums.
I'm having some problems where my vehicles are passing through eachother and when I try to debug the collision functions, I'm seeing that it appears at times the collisions are never noticed for actual colliding shapes (when I turn boundingbox on it appears that the poly's should be noticing eachother...) I have overloaded some of the impulse functionality from the original cool code Tim has in HEAD, but my changes are just queueing collisions more often and I'm still running into problems when I have integration rates set low (like 1). I'm confused on why the system shouldn't still notice these vehicle collisions properly when the objects are not appearing to be moving very quickly even at times when it misses. Does the system get overloaded on collisions if too many are happening at once? And why do collisions get set up to time out? Anybody want to help?