Collinear facets returned from Boolean union of solids

[mknigh23]

I have written a small utility to perform a Boolean operation on a single base object by the union one or more other objects. The code works exactly as designed and is not part of the issue (a simplified version is provided below).

When I interrogate the output of the union - a.off + b.off = c.off - I have a collinear facets on lines (see c.off)...

line 848: 3 279 281 284 = { 29917.4 35925.9 8.744, 29917.4 35926.9 8.744, 29917.4 35926.9 8.744 };

line 849: 3 279 284 218 = { 29917.4 35925.9 8.744, 29917.4 35926.9 8.744, 29917.4 35925.8 8.744 };

line 867: 3 280 284 281 = { 29917.4 35926.9 11.335, 29917.4 35926.9 8.744, 29917.4 35926.9 8.744 };

All collinear/zero-area facets should be resolved by the Boolean operation and should not appear in the resulting solid.

OFF_files.zip

bool readOff(const fs::path& path, Nef_3& nef)
{
    std::ifstream ifs(path);

    if (ifs.is_open())
    {
        CGAL::OFF_to_nef_3(ifs, nef, true);

        return nef.is_valid();
    }

    return false;
}

int main(int argc, char* argv[])
{
    Nef_3 A;

    if (readOff("a.off", A))
    {
        Nef_3 B;

        if (readOff("b.off", B))
        {
            A += B;

            if (A.is_valid())
            {
                std::ofstream ofs("c.off");

                if (A.is_simple())
                {
                    Polyhedron poly;

                    A.convert_to_polyhedron(poly);
                    ofs << poly;
                }
                else
                {
                    ofs << A;
                }

                ofs.close();
                return 0;
            }
        }
    }

    return -1;
}

Environment

• Operating system: Windows 64-bits
• Compiler: Visual Studio 2019
• Release or debug mode: Both
• Specific flags used (if any): n/a
• CGAL version: 5.2.2
• Boost version: 1.76.0
• Other libraries versions if used (Eigen, TBB, etc.): n/a

[sloriot]

The Boolean operation is performed using a number type with arbitrary precision. When you write the OFF file you are first doing a rounding to double and that's from here that the creation of degenerate faces is happening.

As a post-processing step you can use the function CGAL::Polygon_mesh_processing::remove_degenerate_faces() from CGAL/Polygon_mesh_processing/repair_degeneracies.h.

Let me also point out a faster of Boolean operations (restricted to triangle meshes only) in the Polygon Mesh Processing package: See here

[mknigh23]

Hi Sebastien, Firstly, let me apologise for the delayed response. As soon as you mentioned the precision, I realised the error - I had also seen a shift in some vertices when zoomed in - and resolved the issue by setting the output precision, rather than relying on the writer to use the normal default of 6 decimal places (which it didn't).

I then tested the CGAL::Polygon_mesh_processing equivalent that you referred me to. Although it was noticeably quicker, it does not produce a closed mesh, so I had to complete my current dev task before I was able to provide you with feedback; hence the delay.

When I run bool ok = CGAL::Polygon_mesh_processing::corefine_and_compute_union(A, B, C); on the attached files, an invalid facet is formed between the outer edges of two holes (highlighted in blue in the image below, with handles on the vertices and on line 568 of c.off in the attached files; 3 289 253 129), rather than between the closer vertices. Because there are no facets to join either end to the perpendicular facets within the holes, the object is unclosed and cannot be used to provide a volume.

FYI: To test for closure, I dissolve the adjoining half-edges for each planar surface, leaving a list of unique edges that should form individual polygons for each face, holes included, if closed.

Finally, I have seen numerous posts regarding holes in polygons and cannot believe CGAL does not support 3D polygons with holes. Most 'end-users' do not have the technical background to interpret or visualise their building floorplans, walls and ceilings (I'm using the context for the attached images), from a bunch of triangles. It is entirely feasible that more programmers than just myself would like to produce a simplified solid with holes directly from a polygon mesh, polyhedron or NEF polyhedra. These cannot be output using file formats that do not understand polygon topology (i.e. OFF), but there are many formats that do (i.e. ESRI multi-patch shapefile, GeoJSON...).

Note: please disregard if something does exist to provide the simplified format... I am new to CGAL and open to correction.

Triangulated mesh :-(

Simplified solid with holes :-)

OFF_files.zip

[sloriot]

Looking at a.off, I noticed that the model is not closed. Actually you have some non-conformal boundaries like here: After fixing it I could compute the union successfully and the output is closed. union.zip