[ODE] Convex Volume Geom (GJK)

[jstier@cs.uvic.ca]

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.