Valid Solid shells cannot be converted to CGAL polyhedra

[DRC1Spatial]

Many valid Solids contain "pinched" or self-touching shells where the existing algorithm to convert a TriangulatedSurface to a CGAL polyhedron produces a non-manifold point. Since CGAL's combinatorial maps cannot represent non-manifold points, this causes construction to fail.

These problem geometries can easily be produced as algorithm results; the corefinement code will solve this by duplicating the pinch vertices so as to hide the pinch from the combinatorial map. Once recomposed, these Geometries cannot be decomposed again without triggering the problem.

Here are three test cases which demonstrate the problem. The problem geometry is the same in all tests; in the third test it is produced from inputs to difference3D, but the same geometry can be produced directly from WKT, as demonstrated in the first two tests.

BOOST_AUTO_TEST_SUITE( SFCGAL_algorithm_GL3D_514_toPolyhedron_3 )

// Most direct GL3D-514 test: invoke toPolyhedron_3 directly on a problem geometry.
BOOST_AUTO_TEST_CASE( GL3D514test_toPolyhedron_3 /*, *boost::unit_test::disabled() */ )
{
    std::cout << "GL3D514test_toPolyhedron_3" << std::endl;
    std::auto_ptr<SFCGAL::Geometry> tin = SFCGAL::io::readWkt("TIN(((0.00000 2.00000 0.00000,-1.00000 2.00000 1.00000,1.00000 2.00000 1.00000,0.00000 2.00000 0.00000)),"
                                                              "((1.00000 2.00000 1.00000,1.00000 2.00000 -1.00000,0.00000 2.00000 0.00000,1.00000 2.00000 1.00000)),"
                                                              "((-1.00000 2.00000 1.00000,0.00000 1.00000 1.00000,1.00000 2.00000 1.00000,-1.00000 2.00000 1.00000)),"
                                                              "((0.00000 2.00000 0.00000,-1.00000 2.00000 -1.00000,-1.00000 2.00000 1.00000,0.00000 2.00000 0.00000)),"
                                                              "((1.00000 2.00000 -1.00000,-1.00000 2.00000 -1.00000,0.00000 2.00000 0.00000,1.00000 2.00000 -1.00000)),"
                                                              "((1.00000 2.00000 1.00000,1.00000 1.00000 0.00000,1.00000 2.00000 -1.00000,1.00000 2.00000 1.00000)),"
                                                              "((0.00000 1.00000 1.00000,1.00000 0.00000 1.00000,1.00000 2.00000 1.00000,0.00000 1.00000 1.00000)),"
                                                              "((-1.00000 2.00000 1.00000,-0.20000 0.80000 1.00000,0.00000 1.00000 1.00000,-1.00000 2.00000 1.00000)),"
                                                              "((-1.00000 2.00000 -1.00000,-1.00000 1.00000 0.00000,-1.00000 2.00000 1.00000,-1.00000 2.00000 -1.00000)),"
                                                              "((1.00000 2.00000 -1.00000,0.00000 1.00000 -1.00000,-1.00000 2.00000 -1.00000,1.00000 2.00000 -1.00000)),"
                                                              "((1.00000 1.00000 0.00000,1.00000 0.80000 -0.20000,1.00000 2.00000 -1.00000,1.00000 1.00000 0.00000)),"
                                                              "((1.00000 2.00000 1.00000,1.00000 0.00000 1.00000,1.00000 1.00000 0.00000,1.00000 2.00000 1.00000)),"
                                                              "((0.00000 1.00000 1.00000,1.00000 1.00000 0.00000,1.00000 0.00000 1.00000,0.00000 1.00000 1.00000)),"
                                                              "((-0.20000 0.80000 1.00000,-1.00000 0.80000 0.20000,0.00000 1.00000 1.00000,-0.20000 0.80000 1.00000)),"
                                                              "((-1.00000 2.00000 1.00000,-1.00000 0.00000 1.00000,-0.20000 0.80000 1.00000,-1.00000 2.00000 1.00000)),"
                                                              "((-1.00000 1.00000 0.00000,-1.00000 0.80000 0.20000,-1.00000 2.00000 1.00000,-1.00000 1.00000 0.00000)),"
                                                              "((-1.00000 2.00000 -1.00000,-1.00000 0.00000 -1.00000,-1.00000 1.00000 0.00000,-1.00000 2.00000 -1.00000)),"
                                                              "((0.00000 1.00000 -1.00000,-1.00000 0.00000 -1.00000,-1.00000 2.00000 -1.00000,0.00000 1.00000 -1.00000)),"
                                                              "((1.00000 2.00000 -1.00000,0.20000 0.80000 -1.00000,0.00000 1.00000 -1.00000,1.00000 2.00000 -1.00000)),"
                                                              "((1.00000 0.80000 -0.20000,1.00000 0.00000 -1.00000,1.00000 2.00000 -1.00000,1.00000 0.80000 -0.20000)),"
                                                              "((1.00000 1.00000 0.00000,0.00000 1.00000 -1.00000,1.00000 0.80000 -0.20000,1.00000 1.00000 0.00000)),"
                                                              "((0.00000 1.00000 1.00000,0.00000 2.00000 0.00000,1.00000 1.00000 0.00000,0.00000 1.00000 1.00000)),"
                                                              "((-1.00000 0.80000 0.20000,-1.00000 1.00000 0.00000,0.00000 1.00000 1.00000,-1.00000 0.80000 0.20000)),"
                                                              "((-0.20000 0.80000 1.00000,-1.00000 0.00000 1.00000,-1.00000 0.80000 0.20000,-0.20000 0.80000 1.00000)),"
                                                              "((-1.00000 2.00000 1.00000,-1.00000 0.80000 0.20000,-1.00000 0.00000 1.00000,-1.00000 2.00000 1.00000)),"
                                                              "((-1.00000 0.00000 -1.00000,0.00000 1.00000 -1.00000,-1.00000 1.00000 0.00000,-1.00000 0.00000 -1.00000)),"
                                                              "((0.20000 0.80000 -1.00000,1.00000 0.80000 -0.20000,0.00000 1.00000 -1.00000,0.20000 0.80000 -1.00000)),"
                                                              "((1.00000 2.00000 -1.00000,1.00000 0.00000 -1.00000,0.20000 0.80000 -1.00000,1.00000 2.00000 -1.00000)),"
                                                              "((1.00000 0.80000 -0.20000,0.20000 0.80000 -1.00000,1.00000 0.00000 -1.00000,1.00000 0.80000 -0.20000)),"
                                                              "((1.00000 1.00000 0.00000,0.00000 2.00000 0.00000,0.00000 1.00000 -1.00000,1.00000 1.00000 0.00000)),"
                                                              "((0.00000 1.00000 1.00000,-1.00000 1.00000 0.00000,0.00000 2.00000 0.00000,0.00000 1.00000 1.00000)),"
                                                              "((0.00000 1.00000 -1.00000,0.00000 2.00000 0.00000,-1.00000 1.00000 0.00000,0.00000 1.00000 -1.00000)))");
    std::cout << "Conversion 1" << std::endl;
    std::auto_ptr< CGAL::Polyhedron_3<SFCGAL::Kernel> > tin_cgal_1 = tin->as<SFCGAL::TriangulatedSurface>().toPolyhedron_3<SFCGAL::Kernel, CGAL::Polyhedron_3<SFCGAL::Kernel> >();
    std::cout << "Conversion 2" << std::endl;
    std::auto_ptr< SFCGAL::detail::MarkedPolyhedron > tin_cgal_2 = tin->as<SFCGAL::TriangulatedSurface>().toPolyhedron_3<SFCGAL::Kernel, SFCGAL::detail::MarkedPolyhedron >();
    std::cout << "GL3D514test_toPolyhedron_3 succeeded" << std::endl;
}

BOOST_AUTO_TEST_SUITE_END()


BOOST_AUTO_TEST_SUITE( SFCGAL_algorithm_GL3D_514_decompose )

// Test that starts with the same shape as a Solid, and winds up making the same call as GL3D514test_toPolyhedron_3
BOOST_AUTO_TEST_CASE( GL3D514test_decompose /*, *boost::unit_test::disabled() */ )
{
    std::cout << "GL3D514test_decompose" << std::endl;

    std::auto_ptr<SFCGAL::Geometry> g0 = SFCGAL::io::readWkt("SOLID(("
                                                             "((0.00000 2.00000 0.00000,-1.00000 2.00000 1.00000,1.00000 2.00000 1.00000,0.00000 2.00000 0.00000)),"
                                                             "((1.00000 2.00000 1.00000,1.00000 2.00000 -1.00000,0.00000 2.00000 0.00000,1.00000 2.00000 1.00000)),"
                                                             "((-1.00000 2.00000 1.00000,0.00000 1.00000 1.00000,1.00000 2.00000 1.00000,-1.00000 2.00000 1.00000)),"
                                                             "((0.00000 2.00000 0.00000,-1.00000 2.00000 -1.00000,-1.00000 2.00000 1.00000,0.00000 2.00000 0.00000)),"
                                                             "((1.00000 2.00000 -1.00000,-1.00000 2.00000 -1.00000,0.00000 2.00000 0.00000,1.00000 2.00000 -1.00000)),"
                                                             "((1.00000 2.00000 1.00000,1.00000 1.00000 0.00000,1.00000 2.00000 -1.00000,1.00000 2.00000 1.00000)),"
                                                             "((0.00000 1.00000 1.00000,1.00000 0.00000 1.00000,1.00000 2.00000 1.00000,0.00000 1.00000 1.00000)),"
                                                             "((-1.00000 2.00000 1.00000,-0.20000 0.80000 1.00000,0.00000 1.00000 1.00000,-1.00000 2.00000 1.00000)),"
                                                             "((-1.00000 2.00000 -1.00000,-1.00000 1.00000 0.00000,-1.00000 2.00000 1.00000,-1.00000 2.00000 -1.00000)),"
                                                             "((1.00000 2.00000 -1.00000,0.00000 1.00000 -1.00000,-1.00000 2.00000 -1.00000,1.00000 2.00000 -1.00000)),"
                                                             "((1.00000 1.00000 0.00000,1.00000 0.80000 -0.20000,1.00000 2.00000 -1.00000,1.00000 1.00000 0.00000)),"
                                                             "((1.00000 2.00000 1.00000,1.00000 0.00000 1.00000,1.00000 1.00000 0.00000,1.00000 2.00000 1.00000)),"
                                                             "((0.00000 1.00000 1.00000,1.00000 1.00000 0.00000,1.00000 0.00000 1.00000,0.00000 1.00000 1.00000)),"
                                                             "((-0.20000 0.80000 1.00000,-1.00000 0.80000 0.20000,0.00000 1.00000 1.00000,-0.20000 0.80000 1.00000)),"
                                                             "((-1.00000 2.00000 1.00000,-1.00000 0.00000 1.00000,-0.20000 0.80000 1.00000,-1.00000 2.00000 1.00000)),"
                                                             "((-1.00000 1.00000 0.00000,-1.00000 0.80000 0.20000,-1.00000 2.00000 1.00000,-1.00000 1.00000 0.00000)),"
                                                             "((-1.00000 2.00000 -1.00000,-1.00000 0.00000 -1.00000,-1.00000 1.00000 0.00000,-1.00000 2.00000 -1.00000)),"
                                                             "((0.00000 1.00000 -1.00000,-1.00000 0.00000 -1.00000,-1.00000 2.00000 -1.00000,0.00000 1.00000 -1.00000)),"
                                                             "((1.00000 2.00000 -1.00000,0.20000 0.80000 -1.00000,0.00000 1.00000 -1.00000,1.00000 2.00000 -1.00000)),"
                                                             "((1.00000 0.80000 -0.20000,1.00000 0.00000 -1.00000,1.00000 2.00000 -1.00000,1.00000 0.80000 -0.20000)),"
                                                             "((1.00000 1.00000 0.00000,0.00000 1.00000 -1.00000,1.00000 0.80000 -0.20000,1.00000 1.00000 0.00000)),"
                                                             "((0.00000 1.00000 1.00000,0.00000 2.00000 0.00000,1.00000 1.00000 0.00000,0.00000 1.00000 1.00000)),"
                                                             "((-1.00000 0.80000 0.20000,-1.00000 1.00000 0.00000,0.00000 1.00000 1.00000,-1.00000 0.80000 0.20000)),"
                                                             "((-0.20000 0.80000 1.00000,-1.00000 0.00000 1.00000,-1.00000 0.80000 0.20000,-0.20000 0.80000 1.00000)),"
                                                             "((-1.00000 2.00000 1.00000,-1.00000 0.80000 0.20000,-1.00000 0.00000 1.00000,-1.00000 2.00000 1.00000)),"
                                                             "((-1.00000 0.00000 -1.00000,0.00000 1.00000 -1.00000,-1.00000 1.00000 0.00000,-1.00000 0.00000 -1.00000)),"
                                                             "((0.20000 0.80000 -1.00000,1.00000 0.80000 -0.20000,0.00000 1.00000 -1.00000,0.20000 0.80000 -1.00000)),"
                                                             "((1.00000 2.00000 -1.00000,1.00000 0.00000 -1.00000,0.20000 0.80000 -1.00000,1.00000 2.00000 -1.00000)),"
                                                             "((1.00000 0.80000 -0.20000,0.20000 0.80000 -1.00000,1.00000 0.00000 -1.00000,1.00000 0.80000 -0.20000)),"
                                                             "((1.00000 1.00000 0.00000,0.00000 2.00000 0.00000,0.00000 1.00000 -1.00000,1.00000 1.00000 0.00000)),"
                                                             "((0.00000 1.00000 1.00000,-1.00000 1.00000 0.00000,0.00000 2.00000 0.00000,0.00000 1.00000 1.00000)),"
                                                             "((0.00000 1.00000 -1.00000,0.00000 2.00000 0.00000,-1.00000 1.00000 0.00000,0.00000 1.00000 -1.00000))))");

    // The Solid is correctly considered valid.
    // That can be verified by uncommenting these lines.
    //std::cout << "Checking validity" << std::endl;
    //SFCGAL::SFCGAL_ASSERT_GEOMETRY_VALIDITY( *g0 );

    std::cout << "decomposing g0" << std::endl;
    SFCGAL::detail::GeometrySet<3> gs0( *g0 );
}

BOOST_AUTO_TEST_SUITE_END()


BOOST_AUTO_TEST_SUITE( SFCGAL_algorithm_GL3D_514_full )

// Full test case that demonstrates how the situation can arise.
// The difference algorithm produces correct output which includes the problem geometry.
// (Note that the above may require a fix to corefinement_operations.h for a separate issue, that might not be in the public code yet.)
// Then an attempt will be made to decompose it in GeometrySet.filterCovered, which will make a decompose call as above.
// By inspecting intermediate geometries in this test, you can see how CGAL represents the problem geometry when returning it from an algorithm;
// the problem vertex is duplicated to hide the non-manifold point from the underlying combinatorial map.
// Below the test an example of the CGAL output is given.
BOOST_AUTO_TEST_CASE( GL3D514test_full /*, *boost::unit_test::disabled() */ )
{
    std::cout << "GL3D514test_full" << std::endl;

    std::auto_ptr<SFCGAL::Geometry> g1 = SFCGAL::io::readWkt("SOLID Z(("
                                                             "(( 1.00000  2.00000  1.00000, 1.00000 -1.00000  1.00000, 1.00000 -1.00000 -1.00000, 1.00000  2.00000 -1.00000, 1.00000  2.00000  1.00000)),"
                                                             "(( 1.00000  2.00000  1.00000, 1.00000  2.00000 -1.00000,-1.00000  2.00000 -1.00000,-1.00000  2.00000  1.00000, 1.00000  2.00000  1.00000)),"
                                                             "((-1.00000  2.00000 -1.00000,-1.00000 -1.00000 -1.00000,-1.00000 -1.00000  1.00000,-1.00000  2.00000  1.00000,-1.00000  2.00000 -1.00000)),"
                                                             "(( 1.00000 -1.00000  1.00000,-1.00000 -1.00000  1.00000,-1.00000 -1.00000 -1.00000, 1.00000 -1.00000 -1.00000, 1.00000 -1.00000  1.00000)),"
                                                             "(( 1.00000  2.00000 -1.00000, 1.00000 -1.00000 -1.00000,-1.00000 -1.00000 -1.00000,-1.00000  2.00000 -1.00000, 1.00000  2.00000 -1.00000)),"
                                                             "(( 1.00000  2.00000  1.00000,-1.00000  2.00000  1.00000,-1.00000 -1.00000  1.00000, 1.00000 -1.00000  1.00000, 1.00000  2.00000  1.00000))"
                                                             "))");
    std::auto_ptr<SFCGAL::Geometry> g2 = SFCGAL::io::readWkt("SOLID Z(("
                                                             "((0.00000 2.00000 0.00000,2.00000 0.00000 0.00000,0.00000 0.00000 -2.00000,0.00000 2.00000 0.00000)),"
                                                             "((0.00000 2.00000 0.00000,0.00000 0.00000 2.00000,2.00000 0.00000 0.00000,0.00000 2.00000 0.00000)),"
                                                             "((0.00000 2.00000 0.00000,-2.00000 0.00000 0.00000,0.00000 0.00000 2.00000,0.00000 2.00000 0.00000)),"
                                                             "((0.00000 2.00000 0.00000,0.00000 0.00000 -2.00000,-2.00000 0.00000 0.00000,0.00000 2.00000 0.00000)),"
                                                             "((0.00000 -2.00000 0.00000,0.00000 0.00000 -2.00000,2.00000 0.00000 0.00000,0.00000 -2.00000 0.00000)),"
                                                             "((0.00000 -2.00000 0.00000,2.00000 0.00000 0.00000,0.00000 0.00000 2.00000,0.00000 -2.00000 0.00000)),"
                                                             "((0.00000 -2.00000 0.00000,0.00000 0.00000 2.00000,-2.00000 0.00000 0.00000,0.00000 -2.00000 0.00000)),"
                                                             "((0.00000 -2.00000 0.00000,-2.00000 0.00000 0.00000,0.00000 0.00000 -2.00000,0.00000 -2.00000 0.00000))"
                                                             "))");

    std::auto_ptr<SFCGAL::Geometry> diff1 = SFCGAL::algorithm::difference3D( *g1, *g2, SFCGAL::algorithm::NoValidityCheck() );
    std::auto_ptr<SFCGAL::Geometry> diff2 = SFCGAL::algorithm::difference3D( *g2, *g1, SFCGAL::algorithm::NoValidityCheck() );

    BOOST_CHECK( SFCGAL::algorithm::isValid(*diff1) );
    BOOST_CHECK( SFCGAL::algorithm::isValid(*diff2) );
    BOOST_CHECK( diff1->is<SFCGAL::MultiSolid>() );
    BOOST_CHECK( diff2->is<SFCGAL::MultiSolid>() );
    BOOST_CHECK( diff1->as<SFCGAL::MultiSolid>().numGeometries() == 5 );
    BOOST_CHECK( diff2->as<SFCGAL::MultiSolid>().numGeometries() == 5 );
}
/*
    This shows how CGAL represents the shape (taken from some formatted log output).
    Note the duplicate of the vertex at (0,2,0).

	<line>... Import_volume_as_polyhedron operator()... </line>
	<line>... Adding vertex: -1, 0, -1... </line>
	<line>... Adding vertex: 0, 1, -1... </line>
	<line>... Adding vertex: -1, 2, -1... </line>
	<line>... Adding vertex: -1, 1, 0... </line>
	<line>... Adding vertex: 1, 2, -1... </line>
	<line>... Adding vertex: 0, 2, 0... </line>
	<line>... Adding vertex: 0.2, 0.8, -1... </line>
	<line>... Adding vertex: 0, 2, 0... </line>
	<line>... Adding vertex: -1, 2, 1... </line>
	<line>... Adding vertex: 0, 1, 1... </line>
	<line>... Adding vertex: 1, 1, 0... </line>
	<line>... Adding vertex: 1, 0.8, -0.2... </line>
	<line>... Adding vertex: 1, 0, -1... </line>
	<line>... Adding vertex: 1, 2, 1... </line>
	<line>... Adding vertex: -1, 0.8, 0.2... </line>
	<line>... Adding vertex: -1, 0, 1... </line>
	<line>... Adding vertex: -0.2, 0.8, 1... </line>
	<line>... Adding vertex: 1, 0, 1... </line>
	<line>... Adding facet: 0, 2, 1... </line>
	<line>... Adding facet: 1, 3, 0... </line>
	<line>... Adding facet: 2, 4, 1... </line>
	<line>... Adding facet: 0, 3, 2... </line>
	<line>... Adding facet: 1, 5, 3... </line>
	<line>... Adding facet: 4, 6, 1... </line>
	<line>... Adding facet: 2, 7, 4... </line>
	<line>... Adding facet: 3, 8, 2... </line>
	<line>... Adding facet: 5, 9, 3... </line>
	<line>... Adding facet: 1, 10, 5... </line>
	<line>... Adding facet: 6, 11, 1... </line>
	<line>... Adding facet: 4, 12, 6... </line>
	<line>... Adding facet: 7, 13, 4... </line>
	<line>... Adding facet: 2, 8, 7... </line>
	<line>... Adding facet: 3, 14, 8... </line>
	<line>... Adding facet: 9, 14, 3... </line>
	<line>... Adding facet: 5, 10, 9... </line>
	<line>... Adding facet: 1, 11, 10... </line>
	<line>... Adding facet: 6, 12, 11... </line>
	<line>... Adding facet: 4, 11, 12... </line>
	<line>... Adding facet: 13, 10, 4... </line>
	<line>... Adding facet: 7, 8, 13... </line>
	<line>... Adding facet: 14, 15, 8... </line>
	<line>... Adding facet: 9, 16, 14... </line>
	<line>... Adding facet: 10, 17, 9... </line>
	<line>... Adding facet: 11, 4, 10... </line>
	<line>... Adding facet: 13, 17, 10... </line>
	<line>... Adding facet: 8, 9, 13... </line>
	<line>... Adding facet: 15, 16, 8... </line>
	<line>... Adding facet: 14, 16, 15... </line>
	<line>... Adding facet: 9, 8, 16... </line>
	<line>... Adding facet: 17, 13, 9... </line>
	<line>... Import_volume_as_polyhedron operator(): done... </line>
*/

BOOST_AUTO_TEST_SUITE_END()

[DRC1Spatial]

Here's an example of another shape which can be an algorithm output (you could generate this one with a couple of simple unions or differences) which exhibits the same problem.

Note that in this case, unlike the first, the shape is detected as "invalid" because the self-intersection is along a line rather than a point and so is detected by algorithm::selfIntersects3D.

SOLID((((0.00 0.00 1.00,1.00 -1.00 2.00,1.00 1.00 2.00,0.00 0.00 1.00)),((0.00 0.00 -1.00,1.00 1.00 -2.00,1.00 -1.00 -2.00,0.00 0.00 -1.00)),((0.00 0.00 1.00,0.00 0.00 -1.00,1.00 -1.00 -2.00,0.00 0.00 1.00)),((1.00 -1.00 2.00,0.00 0.00 1.00,1.00 -1.00 -2.00,1.00 -1.00 2.00)),((0.00 0.00 1.00,1.00 1.00 2.00,1.00 1.00 -2.00,0.00 0.00 1.00)),((0.00 0.00 -1.00,0.00 0.00 1.00,1.00 1.00 -2.00,0.00 0.00 -1.00)),((1.00 1.00 2.00,2.00 -2.00 2.00,2.00 2.00 2.00,1.00 1.00 2.00)),((1.00 1.00 2.00,1.00 -1.00 2.00,2.00 -2.00 2.00,1.00 1.00 2.00)),((-1.00 -1.00 2.00,-2.00 2.00 2.00,-2.00 -2.00 2.00,-1.00 -1.00 2.00)),((-1.00 -1.00 2.00,-1.00 1.00 2.00,-2.00 2.00 2.00,-1.00 -1.00 2.00)),((1.00 -1.00 2.00,-1.00 -1.00 2.00,-2.00 -2.00 2.00,1.00 -1.00 2.00)),((2.00 -2.00 2.00,1.00 -1.00 2.00,-2.00 -2.00 2.00,2.00 -2.00 2.00)),((1.00 1.00 2.00,2.00 2.00 2.00,-2.00 2.00 2.00,1.00 1.00 2.00)),((-1.00 1.00 2.00,1.00 1.00 2.00,-2.00 2.00 2.00,-1.00 1.00 2.00)),((1.00 1.00 -2.00,-1.00 1.00 2.00,-1.00 1.00 -2.00,1.00 1.00 -2.00)),((1.00 1.00 -2.00,1.00 1.00 2.00,-1.00 1.00 2.00,1.00 1.00 -2.00)),((1.00 -1.00 2.00,1.00 -1.00 -2.00,-1.00 -1.00 -2.00,1.00 -1.00 2.00)),((-1.00 -1.00 2.00,1.00 -1.00 2.00,-1.00 -1.00 -2.00,-1.00 -1.00 2.00)),((-1.00 -1.00 -2.00,1.00 -1.00 -2.00,-2.00 -2.00 -2.00,-1.00 -1.00 -2.00)),((1.00 -1.00 -2.00,2.00 2.00 -2.00,2.00 -2.00 -2.00,1.00 -1.00 -2.00)),((1.00 -1.00 -2.00,1.00 1.00 -2.00,2.00 2.00 -2.00,1.00 -1.00 -2.00)),((-2.00 2.00 -2.00,2.00 2.00 -2.00,1.00 1.00 -2.00,-2.00 2.00 -2.00)),((-2.00 2.00 -2.00,-1.00 1.00 -2.00,-2.00 -2.00 -2.00,-2.00 2.00 -2.00)),((-2.00 2.00 -2.00,1.00 1.00 -2.00,-1.00 1.00 -2.00,-2.00 2.00 -2.00)),((-1.00 1.00 -2.00,-1.00 -1.00 -2.00,-2.00 -2.00 -2.00,-1.00 1.00 -2.00)),((-2.00 -2.00 -2.00,1.00 -1.00 -2.00,2.00 -2.00 -2.00,-2.00 -2.00 -2.00)),((2.00 -2.00 -2.00,-2.00 -2.00 2.00,-2.00 -2.00 -2.00,2.00 -2.00 -2.00)),((2.00 -2.00 -2.00,2.00 -2.00 2.00,-2.00 -2.00 2.00,2.00 -2.00 -2.00)),((2.00 2.00 2.00,2.00 2.00 -2.00,-2.00 2.00 -2.00,2.00 2.00 2.00)),((-2.00 2.00 2.00,2.00 2.00 2.00,-2.00 2.00 -2.00,-2.00 2.00 2.00)),((2.00 -2.00 2.00,2.00 -2.00 -2.00,2.00 2.00 -2.00,2.00 -2.00 2.00)),((2.00 2.00 2.00,2.00 -2.00 2.00,2.00 2.00 -2.00,2.00 2.00 2.00)),((-2.00 -2.00 -2.00,-2.00 2.00 2.00,-2.00 2.00 -2.00,-2.00 -2.00 -2.00)),((-2.00 -2.00 -2.00,-2.00 -2.00 2.00,-2.00 2.00 2.00,-2.00 -2.00 -2.00)),((0.00 0.00 -1.00,-1.00 -1.00 -2.00,-1.00 1.00 -2.00,0.00 0.00 -1.00)),((0.00 0.00 1.00,-1.00 1.00 2.00,-1.00 -1.00 2.00,0.00 0.00 1.00)),((-1.00 -1.00 -2.00,0.00 0.00 1.00,-1.00 -1.00 2.00,-1.00 -1.00 -2.00)),((-1.00 -1.00 -2.00,0.00 0.00 -1.00,0.00 0.00 1.00,-1.00 -1.00 -2.00)),((0.00 0.00 1.00,-1.00 1.00 -2.00,-1.00 1.00 2.00,0.00 0.00 1.00)),((0.00 0.00 1.00,0.00 0.00 -1.00,-1.00 1.00 -2.00,0.00 0.00 1.00))))

I'm currently testing an algorithm which is able to resolve the original problem for both these shapes.

However, it now appears that algorithm::selfIntersects3D is also a problem area. It is unable to detect self-intersections formed by two triangle fan shapes sharing a central vertex, as in the original example. Also, arguably, it should not be used in the validity algorithm for surfaces, because correct functioning of the boolean algorithms can produce Solids with shells that self-intersect at a point or a line, even though their interiors do not overlap. Surface validity should possibly depend on detecting self-penetrations rather than self-intersections.

[mhugo]

@DRC1Spatial Hi, thanks for your detailed report. I honestly need some time to digest it, visualise your examples and understand what is the problem.

[DRC1Spatial]

No problem – drop me a line if you need any help and I’ll do my best to assist. Just FYI, here are some renderings of the involved shapes. This is the first problem shape, which has two opposed triangle fans sharing a central vertex (it’s the vertex above and right of centre):    It is produced as part of a MultiSolid resulting from difference3D on these input shapes (but fixes to corefinement_operations.h that I have here may be required to get the correct resulting MultiSolid from this operation, otherwise an error may result):  This is the more complex shape that I submitted, which exhibits a similar problem along an edge (the shared edge in the centre is the problem):    Cheers, Dave C From: Hugo Mercier <notifications@github.com> Sent: 26 May 2020 07:28 To: Oslandia/SFCGAL <SFCGAL@noreply.github.com> Cc: Dave Chambers <dave.chambers@1spatial.com>; Mention <mention@noreply.github.com> Subject: Re: [Oslandia/SFCGAL] Valid Solid shells cannot be converted to CGAL polyhedra (#225) @DRC1Spatial<https://eur03.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgithub.com%2FDRC1Spatial&data=02%7C01%7Cdave.chambers%401spatial.com%7Cc843660c4aff4d4820c308d8013de666%7C27170d82c2e7473fbdbf488cf747b269%7C0%7C0%7C637260712696977613&sdata=o7%2FlZ2VLVvz03232IEId1QS8ndPRxdNCA08d2KexmPM%3D&reserved=0> Hi, thanks for your detailed report. I honestly need some time to digest it, visualise your examples and understand what is the problem. — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub<https://eur03.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgithub.com%2FOslandia%2FSFCGAL%2Fissues%2F225%23issuecomment-633831942&data=02%7C01%7Cdave.chambers%401spatial.com%7Cc843660c4aff4d4820c308d8013de666%7C27170d82c2e7473fbdbf488cf747b269%7C0%7C0%7C637260712696977613&sdata=ehZpinqHqpWY56iF%2BQc98rplul3ELn9BRJUfxqsDOBk%3D&reserved=0>, or unsubscribe<https://eur03.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgithub.com%2Fnotifications%2Funsubscribe-auth%2FAMUAL3DZQMXJMKY7432L3PDRTNON5ANCNFSM4NG77IUQ&data=02%7C01%7Cdave.chambers%401spatial.com%7Cc843660c4aff4d4820c308d8013de666%7C27170d82c2e7473fbdbf488cf747b269%7C0%7C0%7C637260712696987609&sdata=6wjmmK2FsgA9RSNof2PfvGt20f6QoQly7OMVvdN3dsA%3D&reserved=0>. [https://www.1spatial.com/signatures/1SpatialLogo_Small.jpg]<http://www.1spatial.com> [https://www.1spatial.com/emails/youtube.png]<http://www.youtube.com/user/1SpatialGroup> [https://www.1spatial.com/emails/facebook.png] <https://www.facebook.com/1Spatial> [https://www.1spatial.com/emails/linkedIn.png] <http://www.linkedin.com/company/1spatial> [https://www.1spatial.com/emails/twitter.png] <http://www.twitter.com/1spatial>

…

________________________________ The information in this e-mail is confidential and may be legally privileged. It is intended solely for the addressee. Access to this email by anyone else is unauthorised. Any views or opinions expressed in this e-mail may be solely those of the author and are not necessarily those of 1Spatial Plc. This email has been scanned for viruses and message content. 1Spatial Group Limited is a company registered in England and Wales No.4785688. Registered Office: Tennyson House, Cambridge Business Park, Cambridge CB4 0WZ

[mhugo]

@DRC1Spatial Thanks, however the attached images do not seem to be visible.

Edit: received your images by email, pasted them into your last comment

[sloriot]

If you have a non-manifold vertex in your input, Boolean operations for example will not be possible. So even if non-manifold can be represented in a Polyhedron, you won't be able to do something with it. You wrote Many valid Solids contain "pinched" or self-touching shells but who says that they are valid? The norm or a function?

[DRC1Spatial]

You wrote Many valid Solids contain "pinched" or self-touching shells but who says that they are valid? The norm or a function?

algorithm::isValid. If you run it on the given Solid, you'll see what I mean. This in fact turns out to be a bug in selfIntersects3D - it won't detect opposing triangle fans that share a central vertex, because it allows point touches between non-neighbours. If not for that bug, it would probably detect the given shape as invalid.

However, this is unfortunately a problem, because you can get such shapes as algorithm results. The third test case demonstrates this. When represented as CGAL polyhedra (as returned by the P_minus_Q operation), the shared vertex is duplicated so that a non-manifold point does not occur in the topology - the triangle fan on one side references one copy of the vertex, and the triangle fan on the other side references the other copy of the vertex (you can see this in the logging output from Import_volume_as_polyhedron that I have included). But as soon as the GeometrySet containing that polyhedron is recomposed, the information about the duplicated vertex is lost, and the next attempt to decompose the shape will result in an error.

[DRC1Spatial]

I did not initially think that algorithm::isValid was wrong, because this Solid can be produced by boolean operations, has a closed shell that does not self-penetrate, and no discontinuities in its interior.

[vmora]

but who says that they are valid? The norm or a function?

The SFS doesn't say much about volumes.

[DRC1Spatial]

The SFS doesn't say much about volumes.

Yes, to my knowledge, they have not yet published a version that extends to 3D, so there is no appropriate standard.

But I think it's fair to say that if a shape can be produced by boolean operations from simple primitives, SFCGAL will need to support it.

[sloriot]

A polyhedron expects the surface it represents to be manifold but you can produce some non-manifold surfaces using Boolean operations and you would need a Nef_polyhedron for representing such surfaces. Note that in the real world no solid exists with a boundary surface being manifold. The best short term solution I see is to fix the is valid function and to update the wrapper around the CGAL function to also return false when a non-manifold vertex is produced (non-manifold edges are already making the function returning false).

[DRC1Spatial]

Note that in the real world no solid exists with a boundary surface being [non-]manifold.

Quite a lot of GIS data represents non-physical things - e.g. electoral districts.

A Solid might refer to a volume of space enclosed by a non-physical boundary, rather than an actual solid object, and could therefore have a non-manifold boundary, could it not?

[sloriot]

I'm just saying that it is not possible to have this feature with the current data structure and I'm proposing a workaround. If you want the "general case", then you have to use Nef polyhedra and pay the overhead price.

[DRC1Spatial]

you can produce some non-manifold surfaces using Boolean operations and you would need a Nef_polyhedron for representing such surfaces.

This is not correct in all cases - you can see from my original example that a normal CGAL polyhedron can describe such surfaces, by careful use of duplicated vertices.

What I don't know is whether CGAL can do this in the general case.

I'm just saying that it is not possible to have this feature with the current data structure

Yes, that's true - that's the bug that I was trying to alert you to.

Even if there is a workaround by denying that such surfaces can be valid Solid shells, the library perhaps needs to deal more gracefully with what happens when they occur as a result of boolean operations.

[sloriot]

The way the function in CGAL is supposed to work is to return false if the output is not manifold. There is an exception that I allowed that was the case of a non-manifold vertex because a halfedge data structure can represent it, but it does not make it a valid polyhedral surface (calling is_valid_polygon_mesh() will actually return false).

[DRC1Spatial]

A question that I'm interested in knowing the answer to is this:

As shown in the example, there are at least some cases involving non-manifold vertices and/or edges which the halfedge structure can represent by duplicating vertices without losing any important information. So, when you take two valid polyhedra and do a P_minus_Q operation to get the difference, and the resulting shape happens to have non-manifold points, the underlying algorithm can sometimes give a result back that can then be assembled into a closed surface. My original test case demonstrates this.

But can it do this in all cases? Or, is there a family of valid input polyhedra and boolean operations on those polyhedra such that non-manifold points in the result cannot be "hidden" by duplicating vertices (or possibly where they could, but the algorithm cannot reliably discover how to do it)?

Another way to ask the same question is this. If you take a closed TriangulatedSurface that self-touches as in the examples, decompose the enclosed volume into tetrahedrons, then union the set of resulting tetrahedrons together, will this always succeed and return a halfedge structure from which the original TriangulatedSurface can be recovered?