Skip to content
This repository has been archived by the owner on Mar 25, 2024. It is now read-only.

SFCGAL generates incorrect 3D intersection #200

Open
danielcumberbatch opened this issue Nov 15, 2019 · 5 comments
Open

SFCGAL generates incorrect 3D intersection #200

danielcumberbatch opened this issue Nov 15, 2019 · 5 comments

Comments

@danielcumberbatch
Copy link

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
Copy link
Author

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.

danielcumberbatch added a commit to 1SpatialGroupLtd/SFCGAL that referenced this issue Nov 15, 2019
@danielcumberbatch
Issue Oslandia#200: Added unit tests to reproduce issue Oslandia#200.
d37bb0a 
* Two tests have been added, both involving the intersection
  of two 3D solids that should result in a MultiSolid with
  two constituent parts, but instead result in an invalid Solid
  with two disjoint parts.
danielcumberbatch added a commit to 1SpatialGroupLtd/SFCGAL that referenced this issue Nov 15, 2019
@danielcumberbatch
Issue Oslandia#200: Define static data member to avoid failing build …
c0fc33f 
…on RHEL 7.
danielcumberbatch added a commit to 1SpatialGroupLtd/SFCGAL that referenced this issue Nov 15, 2019
@danielcumberbatch
Issue Oslandia#200: Separate convex volumetric components of 3D solid…
d5f162d 
…-solid intersection and store as separate primitives.
danielcumberbatch added a commit to 1SpatialGroupLtd/SFCGAL that referenced this issue Nov 15, 2019
@danielcumberbatch
Issue Oslandia#200: Pass geometry to covers() or covers3D() in _filte…
0716a81 
…r_covered() depending on its coordinate dimension.
danielcumberbatch added a commit to 1SpatialGroupLtd/SFCGAL that referenced this issue Nov 17, 2019
@danielcumberbatch
Issue Oslandia#200: Added unit tests to reproduce issue.
2fa58b7
danielcumberbatch added a commit to 1SpatialGroupLtd/SFCGAL that referenced this issue Nov 17, 2019
@danielcumberbatch
Issue Oslandia#200: Pass geometry to covers or covers3D in GeometrySe…
bb39797 
…t::_filter_covered() depending on its coordinate dimension.
danielcumberbatch added a commit to 1SpatialGroupLtd/SFCGAL that referenced this issue Nov 17, 2019
@danielcumberbatch
Issue Oslandia#200: Separate convex volumetric components of 3D solid…
bcc9200 
…-solid intersection and store as separate primitives.
danielcumberbatch added a commit to 1SpatialGroupLtd/SFCGAL that referenced this issue Nov 18, 2019
@danielcumberbatch
Issue Oslandia#200: Added unit tests to reproduce issue.
13f1ed4
danielcumberbatch added a commit to 1SpatialGroupLtd/SFCGAL that referenced this issue Nov 18, 2019
@danielcumberbatch
Issue Oslandia#200: Pass geometry to covers or covers3D in GeometrySe…
c0ec200 
…t::_filter_covered() depending on its coordinate dimension.
danielcumberbatch added a commit to 1SpatialGroupLtd/SFCGAL that referenced this issue Nov 18, 2019
@danielcumberbatch
Issue Oslandia#200: Separate convex volumetric components of 3D solid…
879005f 
…-solid intersection and store as separate primitives.
danielcumberbatch added a commit to 1SpatialGroupLtd/SFCGAL that referenced this issue Nov 18, 2019
@danielcumberbatch
Issue Oslandia#200: Fixed benchmark test to read WKT triangle.
cf4d628 
* Experienced exception in ekt reader owing to fact that
  specified triangle is defined with 5 vertices (one duplicate),
  rather than 4.
@danielcumberbatch danielcumberbatch mentioned this issue Nov 18, 2019
Closed
@danielcu888
Copy link
Contributor

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
Copy link
Contributor

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
Copy link
Contributor

danielcu888 commented Apr 21, 2020 •
edited
Loading

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 added a commit to danielcu888/SFCGAL that referenced this issue Apr 21, 2020
@danielcu888
Issue Oslandia#200: Added test to reproduce issue.
d518c06
danielcu888 added a commit to danielcu888/SFCGAL that referenced this issue Apr 21, 2020
@danielcu888
Issue Oslandia#200: Process individual darts using Volume_import_modi…
7d7e29e 
…fier when building intersection polyhedra.

* When recovering the vertices pertaining to each Polyhedra
  component of the desired intersection volume, we now
  process each 3-cell deemed relevant to the intersection result
  individually rather than collectively, since they may pertain
  to disjoint volumes. These volumes are now combined downstream
  as separate primitives, preserving the disjoint nature of the
  components of the result if they are indeed disjoint. This
  scenario is that particularly relevant to Issue Oslandia#200 where the
  intersection result consists of two disjoint volumes, yielding
  a MultiSolid intersection result.
danielcu888 added a commit to danielcu888/SFCGAL that referenced this issue Apr 21, 2020
@danielcu888
Issue Oslandia#200: Fixed WKT of Triangle in Bench test yielding io e…
052c04b 
…rror.
danielcu888 added a commit to danielcu888/SFCGAL that referenced this issue Apr 21, 2020
@danielcu888
Issue Oslandia#200: Moved new unit test to regression test suite; Add…
a8509ae 
…ed verification of result.
@danielcu888 danielcu888 mentioned this issue Apr 21, 2020
Closed
@danielcu888
Copy link
Contributor

Added PR #220 containing a fix for this issue.

@danielcu888 danielcu888 mentioned this issue Apr 22, 2020
Open
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
2 participants
@danielcu888 @danielcumberbatch