Help Wanted [HELP NEEDED]using ConvexConvexDistanceQueries.ConvexConvex() to find intersection's vertices

I am using a custom version of ConvexConvexDistanceQueries.ConvexConvex() with ECS. I need to find the vertices of the intersecting convex shapes that belong to the intersection volume of the 2 clusters. Basically the contact between the 2 convex shapes. I need this as in index into the array of vertices. This is last thing I have to code before I release my app. I will *strongly* appreciate help.

Thank you very much,

stay safe during the pandemic.

 

Hi,

Physics doesn't offer any queries that do intersection volumes, the distance queries only tell you the closest points on a pair of shapes and the distance between them.

If you just want the vertices of the original shape that are in the intersection volume, you could do a point distance query for each vertex against the opposite shape and keep the ones that have negative distance. Note however that the intersection volume itself has vertices that are not vertices of either of the original shapes. For instance, this intersection of two boxes has no vertices at all from the original shapes:



If you need a full definition of the intersection volume, the problem is harder. The most general form of intersection query would be quite tricky, because the intersection of two ConvexColliders might be a volume that can't be represented by a ConvexCollider due to convex radius. For example, the intersection of a quad and a sphere might be a circle, and there is no way to make a circle ConvexCollider. The best you could do would be to approximate one using a regular polygon with lots of edges.

If you aren't using convex radius, or if it's small enough not to care about some inaccuracy, then you could just intersect the convex hulls. I haven't tried this before so I don't know the best way, I'm sure you can find some algorithms to do it if you search around. But the first idea that comes to my mind is to use the planes of one hull to slice the others.

for each plane in hull A
split hull B in two using the plane from A
discard the one that's outside of the plane
keep the one that's inside of the plane

Splitting a hull is probably a bit expensive. You could use a distance query to accelerate this a bit though. If the query returns a positive distance then you can early out because the intersection is empty. If it returns a negative distance, you can still test whether the faces of hull A intersect the separating plane from the distance query, and only use the intersecting faces' planes to split hull B.

Hope that's helpful, good luck

 

Hi,

Thank you greatly for helping me. This extremely useful. Thank you for your post.

I have an idea that I need help with that extends from your idea. What if we select all the vertices within a distance (distance defined by returned intersection distance) of the plane of intersection. Then we could contain the vertices that are within the intersection distance.

This would require to iterate over all n vertices but that shouldn't be concerning since GetSupportingFace() has the same time complexity.

The thing I need help with is finding the position of the intersection to define the plane to measure the distance from.

Thank you so much for your help. This is very useful to me.

 

Should I try to do something with result.SimplexVertexA(0) and result.SimplexVertexB(0)? To help define the plane. And then the normal is supplied by the results struct. I'm trying to somewhat model how things are done with GetSupportingFace. However what I am trying to accomplish is different than what GetSupportingFace is intended for so I don't directly use the function.

 

I don't completely understand what result.SimplexVertexA(0) and result.SimplexVertexB(0) represent

 

The simplex is a point, line segment, triangle, or tetrahedron in the convex hulls' CSO. Every vertex of the simplex is a vertex of hull A minus a vertex of hull B. The i'th vertex of the simplex in A-space is hullA.Vertices[SimplexVertexA(i)] - aFromB * hullB.Vertices[SimplexVertexB(i)]. For some reason ConvexConvexDistanceQueries.Result only provides three vertices of the simplex, probably just an oversight and nobody has needed it.

I think that the idea you're describing is to take all of the vertices of B that are on the negative side of the halfspace through SimplexVertexA(0) with the separating normal, and all of the vertices of A that are on the negative side of the halfspace through SimplexVertexB(0) with the separating normal. Any point on the simplex would give the same halfspace, and there is always at least point 0, so no need to use the others. The set of vertices you get by doing this doesn't have an intuitive meaning to me, but hopefully it's useful to you

 

This is definitely very useful! I'm learning a lot. I'm looking at the use of result.SimplexVertexA(0) and result.SimplexVertexB(0). I'm confused about the meaningfulness of the 0 for the simplex vertex in the use of GetSupportingFace in ConvexConvexManifold's collision processing.

//Code from ConvexConvexManifold.cs lines 459
int faceIndexA = hullA.GetSupportingFace(-normal, result.SimplexVertexA(0));

int faceIndexB = hullB.GetSupportingFace(math.mul(math.transpose(aFromB.Rotation), normal), result.SimplexVertexB(0));

Thanks a lot! You're really helping me out.

 

GetSupportingFace() just needs any vertex on the closest feature in order to find all of the faces containing that feature. So vertex 0 isn't special except that there is always at least one vertex in the simplex so it's always valid.