Improve performance of the clipping algorithm

[JonasBreuling]

As noted in a comment in contact_patch_solver.h, the current version uses a clipping algorithm with O(n1 * n2), but it can be done in O(n1 + n2). My current application is dominated by the clipping costs, so this feature would be very important for me. Is there any chance to get this implemented? And what is the referenced algorithm with O(n1 + n2) complexity?

[jorisv]

Hello @JonasBreuling,

We are interested to improve the clipping computation time.
Do you have the name of algorithm that can achieve clipping in O(n1 + n2) ?

[jorisv]

Sorry I miss read your message. You don't know the O(n1 + n2) algorithm. I will investigate this comment.

[lmontaut]

Hey @JonasBreuling, out of curiosity, can you tell us more about your application? How big are n1 and n2 in your case?

[JonasBreuling]

As you already figured out I have no clue about a faster algorithm, but it is mentioned in the comment. The application is a simple physics engine for rigid bodies. In this specific case there are only box-box contacts. The collide functions are very fast but generating the collision patch requires most of the time.

compare1.mp4

[jorisv]

Nice demo.

We found the O(n1 + n2) algorithm in Computational Geometry in C from Joseph O'Rourke.
We will implement it in the next months.

[JonasBreuling]

That are good news, thanks for your help and the awesome library! I'll keep the issue open until the new feature is merged. Feel free to close it then.

[lmontaut]

@JonasBreuling super cool demo!! Thanks for sharing :)
Can I ask what simulator you are using for this scene?

Regarding the clipping algo, I originally wrote it for our internal simulation purposes, where we mostly generate patches with few points so the o(n1 * n2) algo was sufficient for us.
We'll switch to the o(n1 + n2) algo and will keep you posted!

[JonasBreuling]

This is a student project that I am supervising, which deals with the scaling of numerical algorithms for friction contacts for rigid body systems. So the code is in a very early stage and not ready for public yet. If you are interested in a discussion, I think it would be easier to contact me via email. I won't claime the o(n1 * n2) method is too sow, but if there are potential performance improvements by using already existing algorithms I'm happy for them.