Replace GTS with CDT

[mjcarroll]

This removes the dependency on GTS.

• It removes the Mesh boolean operations functions, which were part of the building editor in Gazebo-classic but are unused in modern gazebo.
• It replaces the GTS delaunay triangulation with the header-only CDT library.

[iche033]

gts dep removal in the gz-common6-release repo when this lands: https://github.com/gazebo-release/gz-common6-release/pull/4

[iche033]

I tested this with the polylines.sdf world and I think some of the triangles may be oriented incorrectly, i.e. normals are in the opposite direction:

left: GTS vs right: CDT

[scpeters]

I tested this with the polylines.sdf world and I think some of the triangles may be oriented incorrectly, i.e. normals are in the opposite direction:

I added a printout to the DelaunayTriangulation test to show the vertices for the triangles:

patch

~~~ diff --git a/graphics/src/DelaunayTriangulation_TEST.cc b/graphics/src/DelaunayTriangulation_TEST.cc index df919d3..c441257 100644 --- a/graphics/src/DelaunayTriangulation_TEST.cc +++ b/graphics/src/DelaunayTriangulation_TEST.cc @@ -69,6 +69,32 @@ TEST_F(DelaunayTriangulation, DelaunayTriangulation) // same as number of vertices in the path EXPECT_EQ(subMesh.VertexCount(), 8u); + std::cerr << subMesh.Max() << '\n'; + std::cerr << subMesh.Min() << '\n'; + // Print vertices + std::cerr << "vertices: \n"; + for (int v = 0; v < subMesh.VertexCount(); ++v) + { + std::cerr << subMesh.Vertex(v) << '\n'; + } + // Print normals + std::cerr << "normals: \n"; + for (int v = 0; v < subMesh.NormalCount(); ++v) + { + std::cerr << subMesh.Normal(v) << '\n'; + } + // there should be 8 triangles. EXPECT_EQ(subMesh.IndexCount() / 3u, 8u); + // Print triangles + std::cerr << "triangles: \n"; + for (int i = 0; i < subMesh.IndexCount() / 3u; ++i) + { + int i1 = subMesh.Index(i*3 + 0); + int i2 = subMesh.Index(i*3 + 1); + int i3 = subMesh.Index(i*3 + 2); + std::cerr << '[' << subMesh.Vertex(i1) << "]\n" + << '[' << subMesh.Vertex(i2) << "]\n" + << '[' << subMesh.Vertex(i3) << "]\n\n"; + } } ~~~

output with GTS

~~~ [ RUN ] GTSMeshUtils.DelaunayTriangulation 1 1 0 0 0 0 vertices: 0.75 0.75 0 1 0 0 1 1 0 0.75 0.25 0 0.25 0.75 0 0 1 0 0.25 0.25 0 0 0 0 normals: triangles: [0.75 0.75 0] [1 1 0] [1 0 0] [0.75 0.25 0] [0.75 0.75 0] [1 0 0] [0.25 0.75 0] [0.25 0.25 0] [0 1 0] [0.75 0.25 0] [1 0 0] [0.25 0.25 0] [1 0 0] [0 0 0] [0.25 0.25 0] [0.25 0.25 0] [0 0 0] [0 1 0] [0.75 0.75 0] [0.25 0.75 0] [1 1 0] [0.25 0.75 0] [0 1 0] [1 1 0] [ OK ] GTSMeshUtils.DelaunayTriangulation (1 ms) ~~~

output with CDT

~~~ [ RUN ] DelaunayTriangulation.DelaunayTriangulation 1 1 0 0 0 0 vertices: 0 0 0 1 0 0 1 1 0 0 1 0 0.25 0.25 0 0.25 0.75 0 0.75 0.75 0 0.75 0.25 0 normals: triangles: [0.75 0.75 0] [1 1 0] [0 1 0] [0.25 0.75 0] [0.75 0.75 0] [0 1 0] [0.25 0.25 0] [0 1 0] [0 0 0] [0.75 0.25 0] [0.25 0.25 0] [1 0 0] [0.25 0.75 0] [0 1 0] [0.25 0.25 0] [0.75 0.25 0] [1 0 0] [0.75 0.75 0] [1 0 0] [1 1 0] [0.75 0.75 0] [1 0 0] [0.25 0.25 0] [0 0 0] [ OK ] DelaunayTriangulation.DelaunayTriangulation (1 ms) ~~~

[iche033]

I tested this with the polylines.sdf world and I think some of the triangles may be oriented incorrectly, i.e. normals are in the opposite direction:

I added a printout to the DelaunayTriangulation test to show the vertices for the triangles:

patch

output with GTS

output with CDT

Thanks, I created a fix for this in #623. It also addresses other feedback in this PR.

[codecov[bot]]

Codecov Report

Attention: Patch coverage is 60.56884% with 610 lines in your changes missing coverage. Please review.

Project coverage is 79.32%. Comparing base (316ea33) to head (b852307). Report is 6 commits behind head on main.

Files	Patch %	Lines
graphics/src/CDT/Triangulation.hpp	63.66%	274 Missing :warning:
graphics/src/CDT/KDTree.h	28.49%	128 Missing :warning:
graphics/src/CDT/portable_nth_element.hpp	53.71%	56 Missing :warning:
graphics/src/CDT/Triangulation.h	46.73%	49 Missing :warning:
graphics/src/CDT/CDTUtils.hpp	61.20%	45 Missing :warning:
graphics/src/CDT/predicates.h	76.68%	45 Missing :warning:
graphics/src/DelaunayTriangulation.cc	82.14%	5 Missing :warning:
graphics/src/CDT/CDTUtils.h	91.30%	4 Missing :warning:
graphics/src/CDT/LocatorKDTree.h	76.47%	4 Missing :warning:

Additional details and impacted files

```diff @@ Coverage Diff @@ ## main #617 +/- ## ========================================== - Coverage 80.54% 79.32% -1.22% ========================================== Files 80 87 +7 Lines 13588 14877 +1289 ========================================== + Hits 10944 11801 +857 - Misses 2644 3076 +432 ```

:umbrella: View full report in Codecov by Sentry.
:loudspeaker: Have feedback on the report? Share it here.

[scpeters]

I think we could ignore graphics/src/CDT in codecov.yml

[iche033]

I think we could ignore graphics/src/CDT in codecov.yml

I updated the ignore files in 7ddc32a

[iche033]

removed gts dep from package.xml in a159b79