search

opencax / GSoC

Google Summer of Code Projects
30 stars 14 forks source link

Add minGap function #82

Closed pca006132 closed 3 months ago

pca006132 commented 5 months ago

Outline

Implement minGap function to check mechanism tolerances. (https://github.com/elalish/manifold/issues/186)

Details

A convenient function would be to measure the minimum gap between two Manifolds (good for checking that mechanisms have the proper tolerances). The signature would be: float Manifold.MinGap(const Manifold& other, float searchLength) const

It would always return a value between zero and searchLength. It would perform an intersection and if that was non-empty, it returns zero (overlapping). If not, it will collide the triangles of each mesh with the triangles of the other, expanded into boxes 2*searchLength wide, then for those collisions, calculate triangle-to-triangle distances. The minimum is returned.

Expected Outcome

Implementation of the minGap function.

Future Possibilities

An algorithm without needing for a searchLength. Perhaps it is possible by doing nearest neighbor search (to determine a good searchLength for the point) + range query (to get all potential nearest triangles).

Project Properties

Skills

Difficulty

Size

Additional Information

mleleszi commented 4 months ago

Hey @elalish @pca006132,

This seems like an interesting problem, I'd love to work on this! I've spent a bit of time going through the wiki and the codebase, got the build and tests working. I've put together a little POC based on the algorithm proposed in the project description to check if I'm understanding things correctly. (I'm just exploring things, disregard the code quality/organization)

https://github.com/elalish/manifold/compare/master...mleleszi:manifold:mingap-poc

Am I going in the right direction? Let me know what you think. I'd love to contribute even before GSoC starts!

elalish commented 4 months ago

Thank you, this looks like a great start! I'm glad to see the tests too. I would recommend adding some test cases where the min gap occurs in the middle of two edges (twist one of your cubes), and another in the middle of a triangle, to ensure you have a correct algorithm. Then the next part will be speeding it up using our Collider for the broad phase.

mleleszi commented 4 months ago

Thank you, I'll try these! How much of this should I ideally get done before GSoC? Get as much implemented and merged as I can, and If there isn't enough work left from this for GSoC then write a proposal for a different project idea? Or how should I got about it

elalish commented 4 months ago

I'm very flexible; my impression of GSoC is that it's trying to encourage people to fall in love with open source and continue contributing. Certainly that's the best outcome for us. I will be happy to give you more project ideas or guide any you come up with to keep you as busy as you like. I'm sure we can make it work, so let's cross that bridge when we come to it.

mleleszi commented 4 months ago

Got it, thank you!

mleleszi commented 3 months ago

Added the test cases you recommended and it made me realize that the triangle to triangle distance calculation is a bit more tricky than I initially thought, I didn't cover a lot of cases. I've researched algorithms for it and opened a draft PR where I documented it. We can continue the discussion there and it can serve as the plan/preparation for GSoC if I don't get to the implementation till then. I'll also look into your other recommendation as to how we could use the Collider to speed things up.

Moult commented 3 months ago

Sorry just jumping in here not knowing any context but FYI Nvidia's Omniverse Physx has a whole bunch of algorithms available including triangle-triangle distance: https://github.com/NVIDIA-Omniverse/PhysX/blob/a2af52eb6a2532bd2bc583ef8ead9c81c9222af1/physx/source/geomutils/src/distance/GuDistanceTriangleTriangle.cpp

It's licensed under BSD. We use it in IfcOpenShell for collision stuff too. It sounds similar to what this project is describing: we have a BVH tree of every triangle mesh, collide BVHs and then use tri-tri distance to determine "clearance".

mleleszi commented 3 months ago

Thank you @Moult, I'll take a look!

Moult commented 3 months ago

If it helps, here is the IfcOpenShell implementation of a many-many clearance clash: https://github.com/IfcOpenShell/IfcOpenShell/blob/796760a064007bb63b9b330a9f7e2853c6ef9ff1/src/ifcgeom_schema_agnostic/IfcGeomTree.h#L1224

It uses two BVHes, one based on the OBBs of each mesh object and another based on the triangles of individual meshes which is very fast compared to looping through all triangles, and multithreading. Then the actual distance check is here: https://github.com/IfcOpenShell/IfcOpenShell/blob/796760a064007bb63b9b330a9f7e2853c6ef9ff1/src/ifcgeom_schema_agnostic/IfcGeomTree.h#L791 with the modified tri-tri code (for OpenCASCADE) here: https://github.com/IfcOpenShell/IfcOpenShell/blob/796760a064007bb63b9b330a9f7e2853c6ef9ff1/src/ifcgeom_schema_agnostic/clash_utils.cpp#L192

Note that there are a number of probably bad coding practices in there since I'm a beginner to C++. We're slowly cleaning it up in https://github.com/IfcOpenShell/IfcOpenShell/tree/feature-clash3

mleleszi commented 3 months ago

Thank you, these will definitely help!

elalish commented 3 months ago

Thanks @Moult, though we actually already have our own parallel BHV tree (Coliider) that we use in our library. Still, the tri-to-tri stuff will likely be useful!

elalish commented 3 months ago

Done, thanks to @mleleszi in https://github.com/elalish/manifold/pull/765!