[ODE] Convex Volume Geom (GJK)

[ode@erwincoumans.com]

Representing a collider as a convex object is faster and gives better 
results compared to representing it as a (concave) moving triangle mesh. 

There are implicit representations that work with a contact generation 
called GJK. The convex object is represented implicitly by a function that 
describes the surface. This function is called the support map function.
This is what the Bullet and Solid collision detection libraries implement. 
However for rigidbody dynamics, you need more then the 1 closest point that 
GJK gives you. That is why Bullet library adds contact point management to 
GJK which reduces and keeps points persistent (Solid doesn't have this). 

There are also explicit convex representations, that keep features (points, 
edges, planes etc), and the contact generation can use 'Lin Canny' or SAT 
(separating axis theorem). The latter is what ODE is using for box-box for 
example. Benefit is that you get all contact points at once, instead of one 
at a time. But it is less generic so you end up writing specific code for 
lots of combinations, instead of 1 convex-convex algorithm like gjk that 
covers all. 

Google for GJK or Lin Canny. 

For papers/books visit the Dtecta website at http://www.dtecta.com or 
Christer Ericsons website http://realtimecollisiondetection.net. 

As a shortcut, you can read this paper:
http://realtimecollisiondetection.net/pubs/SIGGRAPH04_Ericson_GJK_notes.pdf 

and check this GJK convex/ODE integration: 
http://www.continuousphysics.com/ftp/pub/test/physics/source/bulletode_trime 
sh_src.zip 

Erwin
www.continuousphysics.com 

jstier at cs.uvic.ca writes: 

> I am curious about Convex Hull collision detection. What
> are its advantages ? Is it faster ? Could you point me 
> to some reading material ... 
> 
> Cheers and Happy Holidays
> Jochen  
> 
> 
> Quoting Rodrigo Hernandez <kwizatz at aeongames.com>: 
> 
>> ode at erwincoumans.com wrote: 
>> 
>> >Rodrigo, 
>> >
>> >I'm interested in your solution for convex for ODE. Can you describe the 
>> >algorithms you use to compute the contact points? 
>> >
>> >Thanks,
>> >Erwin 
>> >  
>> >
>> Well, Like I said before, I have convex-plane and convex-sphere already 
>> coded, so I can descrive those.
>> First some context, 
>> 
>> Convex shapes are defined in my implementation in a somewhat redundant 
>> way, a convex shape consists of the collection
>> of planes describing a convex hull, each plane is a dVector4 containing 
>> the plane equation (X,Y,Z represents the normal of the plane and W the 
>> signed distance from the origin),
>> then there is a collection of points describing the hull, simple 
>> dVector3 variables, and finally an index buffer to assign the points to 
>> the planes in a counter-clockwise manner,
>> this buffer is an int array, arranged in the following way: first the 
>> number of points in a face (poligon), then that many indexes into the 
>> point collection, then the sequence is repeated,
>> the first group of indices matches the first plane, and so on. 
>> 
>> ODE takes pointers to all these structures, ODE does NOT allocate any of 
>> that memory, I made it this way because I think that that information is 
>> needed by a rendering engine or similar,
>> so it must be computed and allocated in the "client" application anyway, 
>> so ODE can simply reuse the data. 
>> 
>> Here us the dxConvex Class definition: 
>> 
>> struct dxConvex : public dxGeom
>> {
>>   dReal *planes; /*!< An array of planes in the form:
>>            normal X, normal Y, normal Z,Distance
>>          */
>>   dReal *points; /*!< An array of points X,Y,Z */ 
>>   unsigned int *polygons; /*! An array of indices to the points of each 
>> polygon, it should be the number of vertices followed by that amount of 
>> indices to "points" in counter clockwise order*/
>>   unsigned int planecount; /*!< Amount of planes in planes */
>>   unsigned int pointcount;/*!< Amount of points in points */
>>   dReal saabb[6];/*!< Static AABB */
>>   dxConvex(dSpaceID space,
>>        dReal *planes,
>>        unsigned int planecount,
>>        dReal *points,
>>        unsigned int pointcount,
>>        unsigned int *polygons);
>>   ~dxConvex()
>>   {
>>     //fprintf(stdout,"dxConvex Destroy\n");
>>   }
>>   void computeAABB();
>> }; 
>> 
>> And here is the Sample Data I am using for my tests, the following 
>> describes a cube, in case it is not obvious :) 
>> 
>> dReal planes[]= // planes for a cube
>>   {
>>     1.0f ,0.0f ,0.0f ,0.25f,
>>     0.0f ,1.0f ,0.0f ,0.25f,
>>     0.0f ,0.0f ,1.0f ,0.25f,
>>     0.0f ,0.0f ,-1.0f,0.25f,
>>     0.0f ,-1.0f,0.0f ,0.25f,
>>     -1.0f,0.0f ,0.0f ,0.25f
>>   };
>> const unsigned int planecount=6; 
>> 
>> dReal points[]= // points for a cube
>>   {
>>     0.25f,0.25f,0.25f,  //  point 0
>>     -0.25f,0.25f,0.25f, //  point 1 
>> 
>>     0.25f,-0.25f,0.25f, //  point 2
>>     -0.25f,-0.25f,0.25f,//  point 3 
>> 
>>     0.25f,0.25f,-0.25f, //  point 4
>>     -0.25f,0.25f,-0.25f,//  point 5 
>> 
>>     0.25f,-0.25f,-0.25f,//  point 6
>>     -0.25f,-0.25f,-0.25f,// point 7
>>   };
>> const unsigned int pointcount=8;
>> unsigned int polygons[] = //Polygons for a cube (6 squares)
>>   {
>>     4,0,2,6,4, // positive X
>>     4,1,0,4,5, // positive Y
>>     4,0,1,3,2, // positive Z
>>     4,3,1,5,7, // negative X
>>     4,2,3,7,6, // negative Y
>>     4,5,4,6,7, // negative Z
>>   }; 
>> 
>> 
>> Ok, now the algorithms, 
>> 
>> Plane-Convex is done by simply separating the points in two groups, the 
>> ones in front of the plane and the ones behind the plane, if all of them 
>> are on either side, there is no collision, if there are points on
>> both sides, there is a collision, take the ones BEHIND the plane and use 
>> them as Contact Points, the contact normal is the Plane normal for all 
>> of them, and the depth is the distance from the plane to each of the points. 
>> 
>> Sphere-Convex is a bit more complicated, but not much. you just iterate 
>> thru the planes first, checking if the sphere intersects the plane (if 
>> the distance from the center of the shere to the plane is less
>> than the radius of the sphere, it intersects) if it does, find the point 
>> on the plane closer to the center of the sphere, and check if said point 
>> is inside the polygon descrived on the plane (face), if it is,
>> the contact point is the point in the sphere surface in the direction of 
>> the point on the plane, the depth is the radius of the sphere minus the 
>> distance to the plane and the collision normal is the normal of the face.
>> IF the point is NOT inside the polygon, then we need to check for 
>> collision with a vertex or edge, so find the Voronoy region of the 
>> polygon on which the point resides and check for collision between the 
>> sphere and the closest feature that gives you (vertex or edge) if there 
>> is a collision then the collision position is the point on the sphere 
>> surface in direction (point_in_edge or vertex)-sphere_center, the depth 
>> is the radius of the sphere minus the distance to the point in the 
>> feature and the normal is the normalized vector 
>> sphere_center-(point_in_edge or vertex). 
>> 
>> I think I invented the sphere-convex collision check (I have a contiuous 
>> one as well), but it may just be a form of Lin-Canny or V-Clip, but I am 
>> not sure, I wrote all that by memory, so some details may not be 100% 
>> acurate. 
>> 
>> Cheers!
>> _______________________________________________
>> ODE mailing list
>> ODE at q12.org
>> http://q12.org/mailman/listinfo/ode 
>> 
>  
> 
>  
> 
> ----------------------------------------------------------------
> This message was sent using IMP, the Internet Messaging Program.