SFCGAL generates incorrect 3D intersection
Created by: danielcumberbatch
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.