Added functions to get distances to primatives and meshes

[weymouth]

Created new file distances.jl which computes the absolute_distance and the signed_distance to triangle meshes, HyperSpheres and HyperRects. These functions have been exported.

The sphere and rect signed functions are straightforward, and there is a fallback for absolute_distance to equal abs(signed_distance).

Dealing with triangles and triangle meshes is less straightforward. The absolute distance to a triangle is a well defined (if complex) function, but the signed distance isn't. I've used the signed distance to the plane aligned with the triangle. The signed distance to a mesh of triangles is then the signed distance to the convex union of those planes. This is simple, but obviously has drawbacks.

Alternatively, the absolute distance to a mesh of triangles is robust, and could be supplimented with a global operation (like the winding number) to determine a sign.

I've added a 27 tests to runtests which illustrate some of these issues.

[sjkelly]

For reference I have a few more of these functions here: https://github.com/sjkelly/Descartes.jl/blob/master/src/frep.jl

[weymouth]

For reference I have a few more of these functions here: https://github.com/sjkelly/Descartes.jl/blob/master/src/frep.jl

That's great. Do you think it makes sense to merge some of them?

[sjkelly]

Yes, feel free copy whatever is useful from Descartes, assuming people are on board with adding these distance functions.

[SimonDanisch]

Thank you :) Yeah I don't see why not ;)

[weymouth]

So the three primitives I haven't covered yet are Particle (trivial) Cylinder and Pyramid.

It looks like Cylinder is defined with a general line segment and a radius (this is different than Descartes, so I can't copy the code over). I can generalize the Rect corner distance function to cover these.

A Pyramid is just a union of planes, so it'll be caught with a fallback of meshing anything meshable.

[sjkelly]

I'm on the fence about distances for AbstractMesh. There are techniques to speed this up, and what is in here is of bad search complexity for anything decently large. Moreso if you want to do uniform sampling of the mesh. To do it fast, we would need some other dependencies, that would introduce a circular dependents. I'm a little out of the loop on invalidations and how they would affect the design decision here as well.

[weymouth]

By uniform sampling, do you mean filling an entire array with the SDF of a mesh? Because that is my use case.

In fact, I only need this to be accurate fairly close to the mesh, so my plan was to loop through all the mesh faces and fill the array points in the face's bounding box. So this would scale with the number of faces times number of array points per face.

For the general case, I agree that you need some kind of tree method, but this requires some data-structures be set up within GeometryBasics. You could also apply a tree to the array, such as a multi-grid search.

[sjkelly]

Nice! This would be useful to a few other packages, as-is so I am for it. I realize too you could integrate with Adaptive Distance Fields and address a good chunk of performance issues. Also Interpolations.jl would help in many cases.

[weymouth]

Hold the phone. Looking at AdaptiveDistanceFields (which looks cool) EnhancedGJK already has a function ReferenceDistance.signed_distance to a mesh of simplexes, which means I don't need to implement it again here.

[weymouth]

But EnhancedGJK only works with GeometryTypes!!?!

[SimonDanisch]

But EnhancedGJK only works with GeometryTypes!!?!

It's usually not too hard to upgrade to GeometryBasics, since most APIs have stayed fairly similar!

[weymouth]

What is the process/etiquette for this? I've raised an issue on EnhancedGJK but not heard back. https://github.com/JuliaRobotics/EnhancedGJK.jl/issues/39

[SimonDanisch]

Good question... I think those may not be maintained anymore... We can ask, if they want to move the package to JuliaGeometry, so it can be maintained by more people!

[sjkelly]

FWIW the GT->GB transition is a pretty big ask. A huge amount of their stack is in GeometryTypes, with EnhancedGJK being pretty key foundation. One approach would be to use import rather than using and support both APIs in EnhancedGJK. I did this in Meshing.jl because many of my users were still on GeometryTypes. https://github.com/JuliaGeometry/Meshing.jl/blob/master/src/geometrybasics_api.jl https://github.com/JuliaGeometry/Meshing.jl/blob/master/src/geometrytypes_api.jl