Add GTE (Geometric Tools Engine) or GTL (Geometric Tools Library)

[WargodHernandez]

trafficstars

I wanted to start a discussion about GTE (Geometric Tools Engine) I have been experimenting with the library over the last few days, and given the permissive license and covering similar features to some external libraries currently in use (CGAL, QHull, RANSAC_SD)

I stumbled onto the library after following comments in distancecomputationtools.cpp

The biggest issue I see to integration with CC is the lack of CMake support (and currently the library is not yet on GitHub although that is in the works)

My proposal would be to integrate GTE into CCCoreLib in place of CGAL and then expose the distance, intersection, and approximation (RANSAC) code to CloudCompare.

[dgirardeau]

Can GTE create triangular meshes? (as CGAL does currently)

[WargodHernandez]

Can GTE create triangular meshes? (as CGAL does currently)

I believe that is covered in the Delaunay3Mesh class.

There is also Delaunay2Mesh, Delaunay3, Delaunay2, and ConstrainedDelaunay2

[WargodHernandez]

For computational geometry there is the following:

[WargodHernandez]

For approximations (Some support RANSAC some do not) GTE supports the following

The following have the virtual functions required to support RANSAC

It looks simple enough to add RANSAC support to the various approximation classes that are missing support currently

[WargodHernandez]

Another large benefit in my mind is the extensive documentation provided behind each algorithm

Along with his book I haven't read it all but I have access to it through Safari books online and I do consult it fairly often once I found it.

[asmaloney]

I'm in favour of exploring this. Would it make sense to make it a requirement rather than optional like CGAL is?

Benefits:

• could replace multiple dependencies (in here + CC) with one
• could replaces multiple APIs & styles we need to deal with with a common style
• more up-to-date than current RANSAC
• could maybe move RANSAC into the main app? (and get it working on macOS)
• opportunity to use other things from there?

Drawbacks:

• I don't see anything about macOS support. Since we'd just be using the math "lib" maybe it would work(ish) since it works on Linux.
• As Chris points out, no CMake to integrate nicely.
• Without integrating it, we won't know if the results are as good/better than what we currently have :-)

I'm happy to put some time into the CMake/macOS stuff if we decide it looks promising. Someone else would have to do the integration work... we could add it as an option and then remove CGAL when we're happy with the results.

[WargodHernandez]

Going through it more, at least the mathematics library is header only with no external requirements/dependencies.

Since we will have to setup our own "fork" if we just include the contents of the Mathematics folder (excluding the MathematicsGPU subfolder) the CMake integration is pretty trivial.

As a minimum example of what using this library would look like I stripped down of the sample for Delauny3d

#include <Mathematics/ArbitraryPrecision.h>
#include <Mathematics/Delaunay3.h>

    // The choice of 12 is empirical.  All the data sets tested in this
    // sample require at most 11 elements in the UIntegerFP32 array.
    Delaunay3<float, BSNumber<UIntegerFP32<12>>> mDelaunay;
    Delaunay3<float, BSNumber<UIntegerFP32<12>>>::SearchInfo mInfo;

//init the Delauny class with a number of random vertices
mDelaunay(static_cast<int>(mVertices.size()), &mVertices[0], 0.001f); // 0.001f is epsilon

//create a path through the resulting tetrahedron from a randow starting and stopping point
//the starting point is the last iterations finishing point
int found = mDelaunay.GetContainingTetrahedron(point, mInfo);
    if (found >= 0)
    {
        mInfo.initialTetrahedron = mInfo.finalTetrahedron;

        // Make all tetra on the path solid.
        for (int i = 0; i < mInfo.numPath; ++i)
        {
            int index = mInfo.path[i];
            float red, blue;
            if (mInfo.numPath > 1)
            {
                red = i / (mInfo.numPath - 1.0f);
                blue = 1.0f - red;
            }
            else
            {
                red = 1.0f;
                blue = 0.0f;
            }
            SetTetraSolid(index, { red, 0.0f, blue, 0.5f });
        }

this results in the following output:

Lots of detail was scrubbed out of the code above, all of the graphics library, window system, input handling etc...

[dgirardeau]

Ok. Interesting (however for now we only use 2D Delaunay triangulation I believe.

I would be interested to see how this library performs on big clouds (e.g. 5 to 10M. at least). This is something the Triangle lib was doing without issues, and I believe CGAL was slightly slower).

And my other comment is that there shouldn't be any 'mandatory' dependency to CCCoreLib if it's not super straightforward / silent to compile with. Since it is used by other projects, I don't want to bring unnecessary dependencies / burden (that's also why CGAL was optional).

[WargodHernandez]

I integrated the delauny triangulation and compared it against CGAL

Pros:

• It was a really simple integration
• Gives essentially the exact same result as CGAL

Cons:

• It was painfully slow like an order of magnitude slower than CGAL :(

Because of how simple the integration was, it may make sense to offer it as a backup for when CGAL isn't available. there are other functions that may make sense still like primitive distance/intersections, RANSAC

I haven't tested RANSAC yet though, I'll get back with those results ASAP