First off, I would recommend not using highly tessellated shapes in your physics simulation. Generally it's a best practice to have very low face counts, and use different geometries for physics than compared to rendering. This way we have high poly rendering, but physics is happy with the larger faces (which are not visible to the player). There are mesh-simplification tools that can take a high-poly mesh and simplify it to be more fit for physics simulation.
If this isn't an option then I would just hard-code special cases for highly tessellated shapes. Circles would just have a different code path than cubes. But maybe there isn't a good way to do special cases, if so then here is the approach I would take:
When you gather a collision event (with shape A and shape B) from a curved surface, or tessellated surface, I would take the contact plane from the physics engines. This will be a very good frame of reference. Project the vertices of each shape from 3D to 2D in the contact plane, but only project points to the contact frame of reference if they are within PROJECT_TOLERANCE distance, which is a tunable parameter.
Now we have a 2D area from shape A and another from shape B, only on the contact plane. These areas will approximate how much overlap a real-life physical contact would have. I would take these two area values and mix them together with this formula:
float Mix( float a, float b )
{
return sqrt( a * b );
}
The purpose of the Mix function is to make sure that if either A or B contribute a super tiny area -- which could happen if a sharp edge of say a cube hits a flat plane -- the overall mix result used to calculate stickyness is very small. However if A and B are roughly equal, the mix result will be close to A and B.
To compute the convex hull in 2D there is a very fast routine within Box2D (here it is) that you can copy. If you have physics shapes that are implicitly defined (like a sphere represented by a point and radius, or a capsule with 2 points and radius), then a dedicated "projected area" function can probably be created. In other words, computing the 2D area of a projected sphere is simple enough to be solved directly, without projecting a bunch of triangles.
This kind of algorithm is generally more of an art than a science since we are dealing with idealized rigid bodies, but want them to behave more intuitively like real-life objects. Naturally many kinds of corners can be cut. This is just my take on the problem.
Edit: Thought of another way to approximate the contact area. In Game Programming Gems 6 Erin Catto has a good article on clipping 3D meshes to a clipping plane, and then calculating the resulting volume. In our case the contact plane can be expanded into two separate planes, where we offset the contact plane by + and - PROJECT_TOLERANCE. Take shape A and clip it against the positive plane, take shape B and clip it against the positive plane. Take the two resulting volumes, mix them together, and use that as the input value to stickyness. Personally I would still prefer the 2D projection since it's a little simpler, and can handle implicit shapes easily.
