CGAL users discussion list

["Sebastien Loriot (GeometryFactory)" <>]

CGAL provides a few functions that can help cleaning your mesh:

- polygon soup orientation
- self-intersection detection
- hole filling
- border stitching
- ...

They are all documented in the Polygon Mesh Processing package:
http://doc.cgal.org/latest/Polygon_mesh_processing/index.html

There is a non-documented alternative to Nef polyhedron called
corefinement that is shipped with CGAL.
In a few words your input must not be self-intersecting where
the input polyhedra intersects, and the intersection between the
surface must be a set of close curves (boundary might be used
to close the curves).

I join an example to see how it is working.

A non-official documentation:
https://cgal.geometryfactory.com/~sloriot/corefinement_doc/classCGAL_1_1Polyhedron__corefinement.html

Sebastien.



On 11/20/2015 12:18 AM, SirM2X wrote:
> Taus,
> Thank you very much for the detailed response. Especially, thanks for the
> link to builder example. It will surely come in handy.
> Regarding the Boolean operations, I wouldn't even think of implementing them
> myself (toooo complicated).
> So, if I understand everything correctly, CGAL won't be able to help me: the
> meshes that I deal with are obtained using point cloud data and look
> terrible (you can bet that they will have self-intersections, degeneracies,
> and so on). Also, I'm sure many of the meshes that I use are not closed
> (imagine a really bad 3D reconstruction of a ball and a box on a desk). I
> can preprocess my meshes to remove degeneracies and self-intersections, but
> I cannot guarantee that the mesh will be closed. So I'm assuming CGAL won't
> work?
>
> If the answer is no, then I may have to jettison the idea of using Boolean
> operations for what I want to do.
>
> Marius,
> Thank you for the additional information.
>
>
> Taus Møller wrote
> > I have been struggling (and still is) with this exact problem for
> > quite some time. There are quite a few issues and challenges in
> > relation to this, and the documentation is largely useless on the
> > issues related to use with C#. I have done boolean operations
> > successfully but continually struggle with making it robust.
> > .
> > .
> > .
> > First, my advice would be to actually make you own boolean operations.
> > At least if you need it for anything more than proof of concept. The
> > performance of boolean operations in CGAL is horrendous. I have tried
> > inquiring about method to speed them up, but it seem that is just the
> > way it is. As an example doing a simple union between two meshes of
> > around 400 triangles takes around 8 seconds, which is frankly
> > ridiculous. My understanding is that this performance is the price you
> > pay for having exact math in the calculation. This advantage is
> > however mostly lost due to the fact you pulling the meshes out of
> > CGAL. This is additionally compounded by the need to converted to and
> > from Nef polyhedra. We are primarily using CGAL because implementing
> > Booleans is hard(!) and we currently have the resources to do it.
> > Additionally, CGAL provides a lot of additional functionality that is
> > very convenient. Also, to be fair, it is my experience that appart
> > from booleans CGAL is actually very quick.
> >
> > .
> > .
> > .
> >
> > To convert to Polyhedron_3 i found the best way was to implement
> > Modifier_base as outlined here:
> > http://doc.cgal.org/4.7/Polyhedron/Polyhedron_2polyhedron_prog_incr_builder_8cpp-example.html.
> > This way you can provide you mesh as vertex list and triangle indices
> > and get a Polyhedron_3 from it.
> >
> >
> > In relation to robustness, before you convert to nef you have to be
> > absolutely sure that you Polyhedron mesh is valid, closed and not self
> > intersecting. If there is any kind of issue with the mesh, CGAL fails
> > in a very unhelpful way. I am currently struggling to ensure mesh
> > integrity on Polyhedron_3 meshes. CGAL does provide some useful
> > functionality for this, but still leaves a lot to be desired.
> >
> > Hope it helps
>
>
>
>
>
> --
> View this message in context: 
> http://cgal-discuss.949826.n4.nabble.com/Boolean-operations-on-triangular-meshes-tp4661345p4661366.html
> Sent from the cgal-discuss mailing list archive at Nabble.com.

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Polyhedron_3.h>
#include <CGAL/IO/Polyhedron_iostream.h>
#include <CGAL/corefinement_operations.h>
#include <CGAL/iterator.h>

#include <fstream>
#include <iostream>

typedef CGAL::Exact_predicates_inexact_constructions_kernel Kernel;
typedef CGAL::Polyhedron_3<Kernel> Polyhedron;
typedef CGAL::Polyhedron_corefinement<Polyhedron> Corefinement;
typedef std::vector<Kernel::Point_3> Polyline;



int main(int argc,char** argv)
{
  if (argc!=3){
    std::cerr << "Usage: " << argv[0] << "file1.off file2.off" << std::endl;
    return 1;
  }

  //read input polyhedra
  Polyhedron A,B;
  std::ifstream input;
  
  input.open(argv[1]);
  if (!input) {std::cerr << "Error cannot read " << argv[1] << std::endl; return 1;}
  input >> A;
  input.close();

  input.open(argv[2]);
  if (!input) {std::cerr << "Error cannot read " << argv[2] << std::endl; return 1;}
  input >> B;
  input.close();
  
  //check validity of polyhedra
  if (!A.is_pure_triangle() || !B.is_pure_triangle()){
    std::cerr << "Inputs polyhedra must be triangulated." << std::endl;
    return 1;
  }

  if (!A.size_of_vertices() || !B.size_of_vertices()){
    std::cerr << "Inputs polyhedra must not be empty." << std::endl;
    return 1;
  }

  if (!A.is_valid() || !B.is_valid()){
    std::cerr << "Inputs polyhedra must be valid." << std::endl;
    return 1;
  }
  
  //define the vector to contain result.
  std::vector<std::pair <Polyhedron*,int> > result;
  result.reserve(2);
  
  //Define the functor performing corefinement and boolean operations
  Corefinement coref;
  CGAL::Emptyset_iterator polyline_output;  //if you are interested by the intersection polyline,
  //                                          declare std::list<Polyline> polylines;  and use 
  //                                          std::back_inserter(polylines) instead of polyline_output
  
  //run the corefinement. The sum of tags indicates we are interested in the union and the intersection of
  // the input polyhedra.
  coref(A,B,polyline_output,std::back_inserter(result),Corefinement::Join_tag | Corefinement::Intersection_tag);
  
  std::ofstream output;
  
  int union_index = result[0].second==Corefinement::Join_tag?0:1;
  int intersection_index = (union_index+1)%2;
  
  //write result into off files.
  output.open("union.off");
  output << *( result[union_index].first );
  output.close();

  output.open("intersection.off");
  output << *( result[intersection_index].first );
  output.close();
  
  //delete result polyhedra when no longer needed
  delete result[0].first;
  delete result[1].first;

  return 0;
}