[ODE] Convex Volume Geom (GJK)

[Rodrigo Hernandez]

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!