CGAL Inexact Volume calculation

user_15519994 0
Viewed 76

My Problem

I would like to calculate the exact volume for an intersection with polygonmeshes. Unfortunately the result is wrong!?!?!. I think it has something to do with me choosing the wrong options. I have an STEP/OFF file (both work). I move a smaller Cylinder into a bigger Cylinder. Then I calculate the Intersection. I do not use a pointmap. If I calculate the Volume of the first three intersections, CGAL tells me their volume is zero, but it is not.

Why the Result is wrong

I know this, because:

  1. I described this Problem analytically and solved the integral with matlab => Volume is not 0
  2. I solved the Problem Using FreeCAD => Volume is the same as in Matlab
  3. I solved the Volume in CGAL Result do not match 1 and 2.

I wrote the Results of many all the intersection into files, and the files concerning the problem are not empty. With a mesh viewer like (gmsh or meshlab) I can confirm heigth width and length. So the volume should not be 0, because it is intersecting so the volume cannot be 0.

What I have done

I have read this:

  1. The Exact Computation Paradigm
  2. Robustness and Precision Issues in Geometric Computation
  3. FAQ: I am using double (or float or ...) as my number type and get assertion failures or incorrect output. Is this a bug in CGAL?

I did not understand how these three apply to my situation.

I am using the Exact_predicates_exact_constructions_kernel, I defined CGAL_DONT_USE_LAZY_KERNEL. I have used the other Kernels and not defined CGAL_DONT_USE_LAZY_KERNEL, the result does not change. I do not use the the same output and input variable for intersection like in the Polygon_mesh_processing/corefinement_consecutive_bool_op.cpp, so i do not use a point map as a result.

If needed I will supply the entire example, but I think, I did something wrong and the includes and way how I calculate the volume should suffice.

// originalExampleFrom corefinement_parallel_union_meshes.cpp;
#include <CGAL/Exact_predicates_exact_constructions_kernel_with_sqrt.h>
//#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Polygon_mesh_processing/transform.h>
#include <CGAL/Polygon_mesh_processing/intersection.h>
#include <CGAL/Named_function_parameters.h>
#include <CGAL/boost/graph/named_params_helper.h>
#include <CGAL/Surface_mesh.h>
#include <CGAL/aff_transformation_tags.h>
#include <CGAL/Polygon_mesh_processing/triangulate_faces.h>
#include <CGAL/Polygon_mesh_processing/corefinement.h>
#include <CGAL/Polygon_mesh_processing/repair.h>
#include <CGAL/Polygon_mesh_processing/IO/polygon_mesh_io.h>
#include <CGAL/Aff_transformation_3.h>
#include <iostream>
#include <fstream> // for write to file
#include <cassert>
#include <typeinfo>
//#define CGAL_DONT_USE_LAZY_KERNEL

/*
 The corefinement operation (which is also internally used in the three Boolean operations) will correctly change the topology of the input surface mesh
 if the point type used in the point property maps of the input meshes is from a CGAL Kernel with exact predicates.
 If that kernel does not have exact constructions, the embedding of the output surface mesh might have self-intersections.
 In case of consecutive operations, it is thus recommended to use a point property map with points from a kernel
 with exact predicates and exact constructions (such as CGAL::Exact_predicates_exact_constructions_kernel).
 In practice, this means that with exact predicates and inexact constructions, edges will be split at each intersection with a triangle but the position of the intersection point might create self-intersections due to the limited precision of floating point numbers.
 */
typedef CGAL::Exact_predicates_exact_constructions_kernel Kernel; //read text abouve about kernel
typedef Kernel::Point_3 Point_3;
typedef CGAL::Surface_mesh<Kernel::Point_3> Mesh;
#define CGAL_DONT_USE_LAZY_KERNEL
namespace PMP = CGAL::Polygon_mesh_processing;

bool simulateDrillingRadial(Mesh cutter, Mesh rotor, Mesh &out, double step) { //Kernel::Point_3 *volume
    bool validIntersection = false;
    CGAL::Aff_transformation_3<Kernel> trans(CGAL::Translation(),
            Kernel::Vector_3(0, step, Z_INIT)); // step * 2
    PMP::transform(trans, cutter);
    assert(!CGAL::Polygon_mesh_processing::does_self_intersect(rotor));
    assert(!CGAL::Polygon_mesh_processing::does_self_intersect(cutter));
    assert(CGAL::Polygon_mesh_processing::does_bound_a_volume(cutter));
    assert(CGAL::Polygon_mesh_processing::does_bound_a_volume(rotor));
    validIntersection = CGAL::exact(
            PMP::corefine_and_compute_intersection(cutter, rotor, out));
#ifndef NDEBUG
    CGAL::IO::write_polygon_mesh("union" + std::to_string(step) + ".off", out,
            CGAL::parameters::stream_precision(17));
    assert(validIntersection);
    std::cout << "Cutter Volume: " << PMP::volume(cutter) << std::endl;
    std::cout << "Rotor  Volume: " << PMP::volume(rotor) << std::endl;
    std::cout << "Out    Volume: " << CGAL::exact(PMP::volume(out)) << std::endl;
    std::cout << "Numb. of Step: " << step << std::endl;
    std::cout << "Bohrtiefe    : " << Y_INIT - DRMAX * 1.0 / ND * step
            << std::endl;
#endif
    return validIntersection;
}

The Rest of the CODE:

bool simulateDrillingRadial(Mesh cutter, Mesh rotor, Mesh &out, double step) { //Kernel::Point_3 *volume
    bool validIntersection = false;
    CGAL::Aff_transformation_3<Kernel> trans(CGAL::Translation(),
            Kernel::Vector_3(0, step, Z_INIT)); // step * 2
    PMP::transform(trans, cutter);
    assert(!CGAL::Polygon_mesh_processing::does_self_intersect(rotor));
    assert(!CGAL::Polygon_mesh_processing::does_self_intersect(cutter));
    assert(CGAL::Polygon_mesh_processing::does_bound_a_volume(cutter));
    assert(CGAL::Polygon_mesh_processing::does_bound_a_volume(rotor));
    validIntersection = CGAL::exact(
            PMP::corefine_and_compute_intersection(cutter, rotor, out));
#ifndef NDEBUG
    CGAL::IO::write_polygon_mesh("union" + std::to_string(step) + ".step", out,
            CGAL::parameters::stream_precision(17));
    assert(validIntersection);
    std::cout << "Cutter Volume: " << PMP::volume(cutter) << std::endl;
    std::cout << "Rotor  Volume: " << PMP::volume(rotor) << std::endl;
    std::cout << "Out    Volume: " << CGAL::exact(PMP::volume(out)) << std::endl;
    std::cout << "Bohrtiefe    : " << step << std::endl;
#endif

    return validIntersection;
}
int main(int argc, char **argv) {
    bool validRead = false;
    bool validIntersection = false;

    Mesh cutter, rotor; //out; // , out;
    Mesh out[ND];
    Kernel::Point_3 centers[ND];
    //Kernel::FT volume[ND];
    //GetGeomTraits<TriangleMesh, CGAL_NP_CLASS>::type::FT volume[ND];
    double steps[40] = { 40.0000, 39.9981, 39.9926, 39.9833, 39.9703, 39.9535,
            39.9330, 39.9086, 39.8804, 39.8482, 39.8121, 39.7719, 39.7276,
            39.6791, 39.6262, 39.5689, 39.5070, 39.4404, 39.3689, 39.2922,
            39.2103, 39.1227, 39.0293, 38.9297, 38.8235, 38.7102, 38.5893,
            38.4601, 38.3219, 38.1736, 38.0140, 37.8415, 37.6542, 37.4490,
            37.2221, 36.9671, 36.6740, 36.3232, 35.8661, 35.0000 };
    const std::string cutterFile = CGAL::data_file_path("Cutter.off");
    const std::string rotorFile = CGAL::data_file_path("Rotor.off");
    validRead = (!PMP::IO::read_polygon_mesh(cutterFile, cutter)
            || !PMP::IO::read_polygon_mesh(rotorFile, rotor));
    assert(!validRead);
    PMP::triangulate_faces(cutter);
    PMP::triangulate_faces(rotor);
    PMP::transform(rotAroundX(M_PI / 2), cutter);
    for (int i = 0; i < ND; i++) {
        //simulateDrillingRadial(Mesh & cutter, Mesh & rotor, Mesh & out, unsigned int step)
        simulateDrillingRadial(cutter, rotor, out[i], steps[i] + 10);
    }
    writeToCSV("tmp.csv", ND, out, steps);
    return 0;
}
cgal c c++
1 Answers

Change the output format of your mesh from *.off to *.stl, then open the intersection mesh in a software like Autodesk Netfabb which can detect and repair errors in the meshes being loaded. I think there’s a high chance the functions you’re using generate meshes with bugs. Possible bugs include holes, duplicate triangles, and self-intersections. Strictly speaking, such meshes do not unambiguously define a solid body and they have no volume.

If you confirm that’s the problem, there’re two ways to fix.

  1. Replace or fix the intersection algorithm making it produce watertight meshes with no self-intersections or duplicate triangles. Maybe the Nef Polyhedra from the same library will help.

  2. Replace volume computation algorithm making it tolerant to the bugs you have in your intersection meshes.

I realize the answer is rather vague. The reason for that — the problem is very hard to solve well. Very smart people published research papers over several decades. Some companies even selling commercial libraries just for reliable Boolean operations on 3D meshes.

user_1269950
Related