theory of BoxPairTester

[lmtss]

Your code amazes me, I would like to ask something about box-box in narrowphase.
Why the number of candidates can be implicitly guaranteed to be 8 or less?
When clipping edges to faces, is it possible to ensure that the number of generated candidates is less than or equal to 4？

[RossNordby]

The number of contact candidates that a single edge can contribute is 2 because the clipped features are guaranteed to be convex. Given perfect numerical precision, getting more than 2 would require concavity- tracing the opposing face's edges would need to go outside the edge, then inside the edge, then outside again.

So, the number of edge-related candidates generated is no larger than min(edgeCountA * 2, edgeCountB * 2).

There can also be candidates when an edge is fully contained within the opposing face. We only generate one per contained edge in this case- there's no point in creating a contact for the start and the end of the edge, because the end of the edge is the start of the next edge.

So the number of possible contained edge contacts is max(edgeCountA, edgeCountB).

So, the maximum number of candidates from either source is just max(max(edgeCountA, edgeCountB), min(edgeCountA * 2, edgeCountB * 2)). In the case of box-box, edgeCountA and edgeCountB are both 4, so this evaluates to 8.

In practice, numerical error could result in spurious contacts being added, but this tends to be pretty rare and the implementation just shrugs and stops adding contacts once the candidate set is full.

When clipping edges to faces, is it possible to ensure that the number of generated candidates is less than or equal to 4？

For a full face-face test, you'd have to choose some candidates to not generate ahead of time. There may exist some rules that would get you results similar to the contact reduction postpass, but it would probably be complicated.

[lmtss]

In practice, numerical error could result in spurious contacts being added, but this tends to be pretty rare and the implementation just shrugs and stops adding contacts once the candidate set is full.

I see that your code does not explicitly constrain the number, that is, the number of candidates may exceed 8.

int byteCount = Unsafe.SizeOf<ManifoldCandidate>() * 8;
var buffer = stackalloc byte[byteCount];
ref var candidates = ref Unsafe.As<byte, ManifoldCandidate>(ref *buffer);

According to my understanding, the number of candidates generated by CreateEdgeContacts is less than or equal to 8, and the number of candidates generated by AddBoxAVertices is less than or equal to 4, so the total number of candidates is less than or equal to 12.
Am I misunderstanding? Is the total number of candidates still less than 8 (CreateEdgeContacts and AddBoxAVertices )?

[RossNordby]

AddBoxAVertices checks the number of vertices before adding:

bepuphysics2/BepuPhysics/CollisionDetection/CollisionTasks/BoxPairTester.cs

Lines 129 to 131 in 2c84959

	var belowBufferCapacity = Vector.LessThan(candidateCount, new Vector<int>(8));
	var contactExists = Vector.BitwiseAnd(allowContacts, Vector.BitwiseAnd(contained, belowBufferCapacity));
	ManifoldCandidateHelper.AddCandidate(ref candidates, ref candidateCount, candidate, contactExists, pairCount);

That condition wouldn't be hit if you had perfect numerical precision, but it's there just in case.

[lmtss]

Oh my gosh, I didn't even see this line of code! I have watched it several times!
Thank you!