Polygon Soup Not Closing to Form a Bounded Volume Due to Low Accuracy

[FuzhangHe]

Issue Details

I'm having an issue with a vector of triangles represented as a polygon soup. This polygon soup is saved in a float accuracy format and I am attempting to calculate its bounded volume. However, the polygon soup does not close as expected, and this seems to be primarily caused by the low accuracy of the points.

The triangles are saved as an .off file.resultIntersect.off

Steps to reproduce:

1. Convert the triangles into cgal polygon soup;
2. Cleaned the polygon soup using the (repair_polygon_soup);
3. Converting it to a polygon mesh (orient_polygon_soup + polygon_soup_to_polygon_mesh);
4. Do the hole filling with triangulate_refine_and_fair_hole() , by using code in the example hole_filling_example_SM.

Despite following the mentioned steps, the resulting surface mesh is not closed.

Source Code

The example hole_filling_example_SM

// Convert the triangles to cgal polygon soup
        std::vector<Custom_point> points;
        std::vector<CGAL_Polygon> polygons;

        std::map<pos3, std::size_t> index_map;
        std::size_t next_index = 0;

        for (const triangle3& t : newTris)
        {
            std::array<pos3, 3> vertices = { t.v0, t.v1, t.v2 };
            polygons.push_back({});
            for (const pos3& v : vertices)
            {
                auto it = index_map.find(v);
                if (it == index_map.end())
                {
                    // New point, add it to the points vector and the index map
                    points.push_back(v.to_custom_point());
                    index_map[v] = next_index++;
                }
                polygons.back().push_back(index_map[v]);
            }
        }
        std::cout << "Before reparation, the soup has " << points.size() << " vertices and " << polygons.size() << " faces" << std::endl;

// Now, repair and orient the polygon soup, and convert it to a mesh
        PMP::repair_polygon_soup(points, polygons, CGAL::parameters::geom_traits(Array_traits()));
        Mesh mesh;
        PMP::orient_polygon_soup(points, polygons);
        PMP::polygon_soup_to_polygon_mesh(points, polygons, mesh);

        std::cout << "Mesh has " << num_vertices(mesh) << " vertices and " << num_faces(mesh) << " faces" << std::endl;

// Hole filling
        unsigned int nb_holes = 0;
        std::vector<halfedge_descriptor> border_cycles;
        // collect one halfedge per boundary cycle
        PMP::extract_boundary_cycles(mesh, std::back_inserter(border_cycles));
        for (halfedge_descriptor h : border_cycles)
        {
            std::vector<face_descriptor>  patch_facets;
            std::vector<vertex_descriptor> patch_vertices;
            bool success = std::get<0>(PMP::triangulate_refine_and_fair_hole(mesh,
                h,
                std::back_inserter(patch_facets),
                std::back_inserter(patch_vertices)));
            std::cout << "* Number of facets in constructed patch: " << patch_facets.size() << std::endl;
            std::cout << "  Number of vertices in constructed patch: " << patch_vertices.size() << std::endl;
            std::cout << "  Is fairing successful: " << success << std::endl;
            ++nb_holes;
        }

// Check if mesh closed
        bool doesMeshClose2 = CGAL::is_closed(mesh);
        if (doesMeshClose2) {
            std::cout << "Mesh is closed" << std::endl;
        }
        else {
            std::cout << "Oh Nein!" << std::endl;
        }

Environment

• Operating system (Windows/Mac/Linux, 32/64 bits):Windows
• Compiler: Visual Studio
• Release or debug mode: debug
• Specific flags used (if any): no
• CGAL version: 5.2.1
• Boost version: 1.80.0
• Other libraries versions if used (Eigen, TBB, etc.): eigen3:x64-windows 3.4.0#2

[MaelRL]

If the issue is mostly due to float accuracy, I would suggest snapping together points with a very small distance bound and then using PMP::stitch_borders().

Hole filling can only fill a hole made of a single border, not bridge a gap between different connected components.

[FuzhangHe]

Thanks for the answer. I implied the function _PMP::stitchborders(mesh), but the mesh is still not closed.

[MaelRL]

Did you perform any snapping beforehand?

[FuzhangHe]

I'm not certain if any snapping procedure has been implemented beforehand.

Perhaps a bit more background information would be helpful. The resultant polygon soup is derived from a plan-based boolean operation, not from the CGAL corefinement boolean operation, but rather from a different algorithm. This particular algorithm conducts the boolean operation by breaking down the mesh into a polygon soup and employing homogeneous integer coordinates. The outcome of this boolean operation is a polygon soup set with float accuracy. In physical terms, this polygon soup should form a closed volume.

What I am trying to do, is to connect the polygon soup and calculate the bounded volume.

[pentacular]

The point is that the vertices may have drifted slightly apart due to floating point error.

To fix this you can have nearby vertices agree on a precise location.

If you can do this correctly, then the polygon soup should become coherent.

[FuzhangHe]

Hallo @MaelRL

The function alpha_warp_3 works, but it takes about 4 seconds to get the desired accuracy.

Also I found the snap_vertices.h, can I use it to snap the vertices? Does the "snap_all_vertices" help, can you please explain how I can use it? Especially how can I define the ToleranceMap, can I just give a value like 0.001?