SFCGAL generates incorrect 3D intersection

danielcumberbatch commented 5 years ago

SFCGAL appears to generate only single part results from the intersection of two input volumes.

The following test demonstrates this:

BOOST_AUTO_TEST_CASE(incorrect_intersection)
{
   std::auto_ptr<SFCGAL::Geometry> poly1 = SFCGAL::io::readWkt("POLYGON((0 0,1 0,1 1,0 1,0 0))");
   std::auto_ptr<SFCGAL::Geometry> solid1 = SFCGAL::algorithm::extrude(*poly1, 0.0, 0.0, 1.0);

   std::auto_ptr<SFCGAL::Geometry> poly2 = SFCGAL::io::readWkt("POLYGON((-1 0.2,1.8 0.2,1.8 0.4,-0.8 0.4,-0.8 0.6,1.8 0.6,1.8 0.8,-1 0.8,-1 0.2))");
   std::auto_ptr<SFCGAL::Geometry> solid2 = SFCGAL::algorithm::extrude(*poly2, 0.0, 0.0, 1.0);

   std::auto_ptr<SFCGAL::Geometry> inx = SFCGAL::algorithm::intersection3D(*solid1, *solid2);
   std::cout << inx->asText(5) << std::endl;

   std::cout << "Valid: " << SFCGAL::algorithm::isValid(*inx) << std::endl;
}

giving the result:

SOLID((((0.00000 0.40000 0.30769,0.40000 0.40000 0.00000,0.00000 0.40000 0.00000,0.00000 0.40000 0.30769)),((0.00000 0.40000 0.00000,0.00000 0.33846 0.00000,0.00000 0.40000 0.30769,0.00000 0.40000 0.00000)),((0.40000 0.40000 0.00000,0.31429 0.31429 0.00000,0.00000 0.40000 0.00000,0.40000 0.40000 0.00000)),((0.00000 0.40000 0.30769,1.00000 0.40000 0.69231,0.40000 0.40000 0.00000,0.00000 0.40000 0.30769)),((0.00000 0.33846 0.00000,0.00000 0.20000 0.20000,0.00000 0.40000 0.30769,0.00000 0.33846 0.00000)),((0.00000 0.40000 0.00000,0.31429 0.31429 0.00000,0.00000 0.33846 0.00000,0.00000 0.40000 0.00000)),((0.40000 0.40000 0.00000,1.00000 0.26154 0.00000,0.31429 0.31429 0.00000,0.40000 0.40000 0.00000)),((1.00000 0.40000 0.69231,1.00000 0.40000 0.60000,0.40000 0.40000 0.00000,1.00000 0.40000 0.69231)),((0.00000 0.40000 0.30769,0.60000 0.40000 1.00000,1.00000 0.40000 0.69231,0.00000 0.40000 0.30769)),((0.00000 0.20000 0.20000,0.00000 0.40000 0.40000,0.00000 0.40000 0.30769,0.00000 0.20000 0.20000)),((0.00000 0.33846 0.00000,0.00000 0.20000 0.00000,0.00000 0.20000 0.20000,0.00000 0.33846 0.00000)),((0.31429 0.31429 0.00000,0.20000 0.20000 0.00000,0.00000 0.33846 0.00000,0.31429 0.31429 0.00000)),((1.00000 0.26154 0.00000,1.00000 0.20000 0.00000,0.31429 0.31429 0.00000,1.00000 0.26154 0.00000)),((0.40000 0.40000 0.00000,1.00000 0.40000 0.00000,1.00000 0.26154 0.00000,0.40000 0.40000 0.00000)),((1.00000 0.40000 0.60000,1.00000 0.40000 0.00000,0.40000 0.40000 0.00000,1.00000 0.40000 0.60000)),((1.00000 0.40000 0.69231,1.00000 0.20000 0.80000,1.00000 0.40000 0.60000,1.00000 0.40000 0.69231)),((0.60000 0.40000 1.00000,1.00000 0.40000 1.00000,1.00000 0.40000 0.69231,0.60000 0.40000 1.00000)),((0.00000 0.40000 0.30769,0.00000 0.40000 0.40000,0.60000 0.40000 1.00000,0.00000 0.40000 0.30769)),((0.00000 0.20000 0.20000,0.00000 0.20000 0.64286,0.00000 0.40000 0.40000,0.00000 0.20000 0.20000)),((0.00000 0.20000 0.00000,0.20000 0.20000 0.00000,0.00000 0.20000 0.20000,0.00000 0.20000 0.00000)),((0.00000 0.33846 0.00000,0.20000 0.20000 0.00000,0.00000 0.20000 0.00000,0.00000 0.33846 0.00000)),((0.31429 0.31429 0.00000,1.00000 0.20000 0.00000,0.20000 0.20000 0.00000,0.31429 0.31429 0.00000)),((1.00000 0.26154 0.00000,1.00000 0.20000 0.28571,1.00000 0.20000 0.00000,1.00000 0.26154 0.00000)),((1.00000 0.40000 0.00000,1.00000 0.20000 0.28571,1.00000 0.26154 0.00000,1.00000 0.40000 0.00000)),((1.00000 0.40000 0.60000,1.00000 0.20000 0.28571,1.00000 0.40000 0.00000,1.00000 0.40000 0.60000)),((1.00000 0.20000 0.80000,1.00000 0.20000 0.28571,1.00000 0.40000 0.60000,1.00000 0.20000 0.80000)),((1.00000 0.40000 0.69231,1.00000 0.40000 1.00000,1.00000 0.20000 0.80000,1.00000 0.40000 0.69231)),((0.60000 0.40000 1.00000,0.71667 0.28333 1.00000,1.00000 0.40000 1.00000,0.60000 0.40000 1.00000)),((0.00000 0.40000 0.40000,0.00000 0.40000 1.00000,0.60000 0.40000 1.00000,0.00000 0.40000 0.40000)),((0.00000 0.20000 0.64286,0.00000 0.40000 1.00000,0.00000 0.40000 0.40000,0.00000 0.20000 0.64286)),((0.00000 0.20000 0.20000,0.20000 0.20000 0.00000,0.00000 0.20000 0.64286,0.00000 0.20000 0.20000)),((1.00000 0.20000 0.00000,1.00000 0.20000 0.28571,0.20000 0.20000 0.00000,1.00000 0.20000 0.00000)),((1.00000 0.20000 0.80000,0.80000 0.20000 1.00000,1.00000 0.20000 0.28571,1.00000 0.20000 0.80000)),((1.00000 0.40000 1.00000,1.00000 0.26154 1.00000,1.00000 0.20000 0.80000,1.00000 0.40000 1.00000)),((0.71667 0.28333 1.00000,1.00000 0.26154 1.00000,1.00000 0.40000 1.00000,0.71667 0.28333 1.00000)),((0.60000 0.40000 1.00000,0.00000 0.33846 1.00000,0.71667 0.28333 1.00000,0.60000 0.40000 1.00000)),((0.00000 0.40000 1.00000,0.00000 0.33846 1.00000,0.60000 0.40000 1.00000,0.00000 0.40000 1.00000)),((0.00000 0.20000 0.64286,0.00000 0.33846 1.00000,0.00000 0.40000 1.00000,0.00000 0.20000 0.64286)),((0.20000 0.20000 0.00000,1.00000 0.20000 0.28571,0.00000 0.20000 0.64286,0.20000 0.20000 0.00000)),((0.80000 0.20000 1.00000,0.00000 0.20000 0.64286,1.00000 0.20000 0.28571,0.80000 0.20000 1.00000)),((1.00000 0.20000 0.80000,1.00000 0.20000 1.00000,0.80000 0.20000 1.00000,1.00000 0.20000 0.80000)),((1.00000 0.26154 1.00000,1.00000 0.20000 1.00000,1.00000 0.20000 0.80000,1.00000 0.26154 1.00000)),((0.71667 0.28333 1.00000,0.80000 0.20000 1.00000,1.00000 0.26154 1.00000,0.71667 0.28333 1.00000)),((0.00000 0.33846 1.00000,0.00000 0.20000 1.00000,0.71667 0.28333 1.00000,0.00000 0.33846 1.00000)),((0.00000 0.20000 0.64286,0.00000 0.20000 1.00000,0.00000 0.33846 1.00000,0.00000 0.20000 0.64286)),((0.80000 0.20000 1.00000,0.00000 0.20000 1.00000,0.00000 0.20000 0.64286,0.80000 0.20000 1.00000)),((1.00000 0.20000 1.00000,1.00000 0.26154 1.00000,0.80000 0.20000 1.00000,1.00000 0.20000 1.00000)),((0.71667 0.28333 1.00000,0.00000 0.20000 1.00000,0.80000 0.20000 1.00000,0.71667 0.28333 1.00000)),((0.00000 0.80000 0.35714,0.80000 0.80000 0.00000,0.00000 0.80000 0.00000,0.00000 0.80000 0.35714)),((0.00000 0.80000 0.00000,0.00000 0.66154 0.00000,0.00000 0.80000 0.35714,0.00000 0.80000 0.00000)),((0.80000 0.80000 0.00000,0.71667 0.71667 0.00000,0.00000 0.80000 0.00000,0.80000 0.80000 0.00000)),((0.00000 0.80000 0.35714,1.00000 0.80000 0.71429,0.80000 0.80000 0.00000,0.00000 0.80000 0.35714)),((0.00000 0.66154 0.00000,0.00000 0.60000 0.00000,0.00000 0.80000 0.35714,0.00000 0.66154 0.00000)),((0.00000 0.80000 0.00000,0.71667 0.71667 0.00000,0.00000 0.66154 0.00000,0.00000 0.80000 0.00000)),((0.80000 0.80000 0.00000,1.00000 0.73846 0.00000,0.71667 0.71667 0.00000,0.80000 0.80000 0.00000)),((1.00000 0.80000 0.71429,1.00000 0.80000 0.20000,0.80000 0.80000 0.00000,1.00000 0.80000 0.71429)),((0.00000 0.80000 0.35714,0.20000 0.80000 1.00000,1.00000 0.80000 0.71429,0.00000 0.80000 0.35714)),((0.00000 0.60000 0.00000,0.00000 0.60000 0.60000,0.00000 0.80000 0.35714,0.00000 0.60000 0.00000)),((0.00000 0.66154 0.00000,0.60000 0.60000 0.00000,0.00000 0.60000 0.00000,0.00000 0.66154 0.00000)),((0.71667 0.71667 0.00000,0.60000 0.60000 0.00000,0.00000 0.66154 0.00000,0.71667 0.71667 0.00000)),((1.00000 0.73846 0.00000,1.00000 0.60000 0.00000,0.71667 0.71667 0.00000,1.00000 0.73846 0.00000)),((0.80000 0.80000 0.00000,1.00000 0.80000 0.00000,1.00000 0.73846 0.00000,0.80000 0.80000 0.00000)),((1.00000 0.80000 0.20000,1.00000 0.80000 0.00000,0.80000 0.80000 0.00000,1.00000 0.80000 0.20000)),((1.00000 0.80000 0.71429,1.00000 0.60000 0.40000,1.00000 0.80000 0.20000,1.00000 0.80000 0.71429)),((0.20000 0.80000 1.00000,1.00000 0.80000 1.00000,1.00000 0.80000 0.71429,0.20000 0.80000 1.00000)),((0.00000 0.80000 0.35714,0.00000 0.80000 0.80000,0.20000 0.80000 1.00000,0.00000 0.80000 0.35714)),((0.00000 0.60000 0.60000,0.00000 0.80000 0.80000,0.00000 0.80000 0.35714,0.00000 0.60000 0.60000)),((0.00000 0.60000 0.00000,0.60000 0.60000 0.00000,0.00000 0.60000 0.60000,0.00000 0.60000 0.00000)),((0.71667 0.71667 0.00000,1.00000 0.60000 0.00000,0.60000 0.60000 0.00000,0.71667 0.71667 0.00000)),((1.00000 0.73846 0.00000,1.00000 0.80000 0.20000,1.00000 0.60000 0.00000,1.00000 0.73846 0.00000)),((1.00000 0.80000 0.00000,1.00000 0.80000 0.20000,1.00000 0.73846 0.00000,1.00000 0.80000 0.00000)),((1.00000 0.60000 0.40000,1.00000 0.60000 0.30769,1.00000 0.80000 0.20000,1.00000 0.60000 0.40000)),((1.00000 0.80000 0.71429,1.00000 0.60000 1.00000,1.00000 0.60000 0.40000,1.00000 0.80000 0.71429)),((1.00000 0.80000 1.00000,1.00000 0.73846 1.00000,1.00000 0.80000 0.71429,1.00000 0.80000 1.00000)),((0.20000 0.80000 1.00000,0.31429 0.68571 1.00000,1.00000 0.80000 1.00000,0.20000 0.80000 1.00000)),((0.00000 0.80000 0.80000,0.00000 0.80000 1.00000,0.20000 0.80000 1.00000,0.00000 0.80000 0.80000)),((0.00000 0.60000 0.60000,0.00000 0.60000 0.69231,0.00000 0.80000 0.80000,0.00000 0.60000 0.60000)),((0.60000 0.60000 0.00000,0.00000 0.60000 0.69231,0.00000 0.60000 0.60000,0.60000 0.60000 0.00000)),((1.00000 0.60000 0.00000,1.00000 0.60000 0.30769,0.60000 0.60000 0.00000,1.00000 0.60000 0.00000)),((1.00000 0.80000 0.20000,1.00000 0.60000 0.30769,1.00000 0.60000 0.00000,1.00000 0.80000 0.20000)),((1.00000 0.60000 0.40000,0.40000 0.60000 1.00000,1.00000 0.60000 0.30769,1.00000 0.60000 0.40000)),((1.00000 0.60000 1.00000,0.40000 0.60000 1.00000,1.00000 0.60000 0.40000,1.00000 0.60000 1.00000)),((1.00000 0.80000 0.71429,1.00000 0.73846 1.00000,1.00000 0.60000 1.00000,1.00000 0.80000 0.71429)),((1.00000 0.80000 1.00000,0.31429 0.68571 1.00000,1.00000 0.73846 1.00000,1.00000 0.80000 1.00000)),((0.20000 0.80000 1.00000,0.00000 0.66154 1.00000,0.31429 0.68571 1.00000,0.20000 0.80000 1.00000)),((0.00000 0.80000 1.00000,0.00000 0.66154 1.00000,0.20000 0.80000 1.00000,0.00000 0.80000 1.00000)),((0.00000 0.80000 0.80000,0.00000 0.66154 1.00000,0.00000 0.80000 1.00000,0.00000 0.80000 0.80000)),((0.00000 0.60000 0.69231,0.00000 0.66154 1.00000,0.00000 0.80000 0.80000,0.00000 0.60000 0.69231)),((0.60000 0.60000 0.00000,1.00000 0.60000 0.30769,0.00000 0.60000 0.69231,0.60000 0.60000 0.00000)),((0.40000 0.60000 1.00000,0.00000 0.60000 0.69231,1.00000 0.60000 0.30769,0.40000 0.60000 1.00000)),((1.00000 0.60000 1.00000,1.00000 0.73846 1.00000,0.40000 0.60000 1.00000,1.00000 0.60000 1.00000)),((0.31429 0.68571 1.00000,0.40000 0.60000 1.00000,1.00000 0.73846 1.00000,0.31429 0.68571 1.00000)),((0.00000 0.66154 1.00000,0.00000 0.60000 1.00000,0.31429 0.68571 1.00000,0.00000 0.66154 1.00000)),((0.00000 0.60000 0.69231,0.00000 0.60000 1.00000,0.00000 0.66154 1.00000,0.00000 0.60000 0.69231)),((0.40000 0.60000 1.00000,0.00000 0.60000 1.00000,0.00000 0.60000 0.69231,0.40000 0.60000 1.00000)),((0.31429 0.68571 1.00000,0.00000 0.60000 1.00000,0.40000 0.60000 1.00000,0.31429 0.68571 1.00000)))) with the above SOLID being classified as invalid.

The result should be a MULTISOLID consisting of two valid SOLID parts, instead of the above result which is a single invalid SOLID with two disjoint components.

This bug comes about from the SFCGAL's use of CGAL's polyhedra_corefinement class, which, in this case, generates a single object consisting of two disjoint closed polyhedra. SFCGAL then wraps and returns these as a single component SOLID, whereas it should separate out the disjoint components and return them as SOLID parts of a single MULTISOLID.

danielcumberbatch commented 5 years ago

A fix has been engineered for this bug (and will be submitted shortly) consisting of:

Decomposing the intersection polyhedron from Polyhedron_corefinement into separate parts before adding them to the geometry set returned from SFCGAL::algorithm::intersection3D.
Adapting the SFCGAL client to accept multiple part results and returning them as a MULTISOLID.

danielcu888 commented 4 years ago

We're getting two 3-cells being passed into the Volume_import_modifier. The modifier then is iterating over all 3-cells passed into it and collecting primitives associated with them in order to construct the faces of a single intersection polyhedron, leading to a Solid with disjoint parts. Looks like we need to process each 3-cell in the Volume_import_modifier individually and then the downstream call to filterCovered will remove any duplicate primitives and faces in the result.

danielcu888 commented 4 years ago

The result is a GC with incomplete faces. This indicates that the resulting solids are Polyhedra that consist of contributions from more than a single 3-cell.

Clearly when the points from ALL 3-cells in the list passed to the Volume_import_modifier that index into the combinatorial map entry of one of those list entries we get the current bug with too many contributions.

Hence the list of 3-cells passed to the Volume_import_modifier needs better filtering before being used to construct the output polyhedra.

danielcu888 commented 4 years ago

Actually I was wrong, in the previous attempt I had only considered the first output Polyhedron. When considering both, the correct MultiSolid is created.

This raises a disturbing quality of the combinatorial map. When retrieving points in the Volume_import_modifier for one of the two intersection volumes from both of the intersection 3-cells it should not retrieve any points that pertain to the other completely disjoint volume. This appears not to be the case as I was able to partially reconstruct edges and vertices for both disjoint volumes when building only one of them using the Volume_import_modifier.

However, when combining the two contributions, the inevitable overlapping geometry is filtered out downstream by filterCovered, and we arrive at the correct result. PR to follow shortly.

Also to mention that I used the very convenient constructor for the Volume_import_modifier that takes a single dart, rather than a range of them in order to build each output volume.

danielcu888 commented 4 years ago

Added PR https://github.com/Oslandia/SFCGAL/pull/220 containing a fix for this issue.

Oslandia / SFCGAL

SFCGAL generates incorrect 3D intersection #200