Triangulation: Add static filter for 5D and 6D orientation predicate

[afabri]

Summary of Changes

This PR adds a static filter for the orientation test of 5D and 6D points. It is ~20% faster than just interval arithmetic.

• [ ] Add for 4D
• [ ] Add in sphere predicate

Release Management

• Affected package(s): Triangulation
• License and copyright ownership: unchanged

[mglisse]

So far it is slower than just interval arithmetic

I tried quickly running the benchmark (on a file generated with the new generator). With master, I get 11s. Branch with -DCGAL_NO_STATIC_FILTER_5 (so presumably just the clear/mark change): 10.3s Branch (with static filter): 8.5s

That doesn't look slower to me :confused:

• The TDS change is exactly what I had in mind
• orientationC5.h doesn't seem to be used (ah! it was probably used as input to FPG, then it makes sense to keep it somewhere indeed, with a comment to avoid confusing people like me :wink:)
• we could write the static filter directly with the internal interface instead of defining an adapter (I used the adapter approach for 2d and 3d because I wanted to reuse the static filters from Kernel_23 without modifying them), but if you prefer with the intermediate adapter, that's fine with me.

[afabri]

@sloriot can you please create the 4D version, plus the in-sphere tests with the filter generator.

[afabri]

Hi @mglisse I just added the 4D version. The user we know only constructs a convex hull, and all points are on the hull, so the triangulation class does the job, and I have no need for a faster insphere test. It might make sense to add a convex hull function that does not insert if the locate type is not outside convex hull, but not in this PR.

[sloriot]

Successfully tested in CGAL-6.1-Ic-189

[afabri]

In 6D with 100K points the runtime is 207 vs 94 seconds.

[github-actions[bot]]

This pull-request was previously marked with the label Tested, but has been modified with new commits. That label has been removed.

[sloriot]

Successfully tested in CGAL-6.1-Ic-208