Polygon_mesh_processing::corefine_and_compute_difference

classic Classic list List threaded Threaded
14 messages Options
Reply | Threaded
Open this post in threaded view
|

Polygon_mesh_processing::corefine_and_compute_difference

Sean Hardesty
I have a collection of meshes that overlap slightly, so I am going through a loop removing overlapping pieces. It works for a while, but eventually I run into trouble. I am calling PMP::corefine_and_compute_difference (CGAL 4.11) on a pair of meshes that satisfy

!CGAL::Polygon_mesh_processing::does_self_intersect
CGAL::Polygon_mesh_processing::does_bound_a_volume

and I get the following:

terminate called after throwing an instance of 'CGAL::Assertion_exception'
  what():  CGAL ERROR: assertion violation!
Expr: hedge!=start
File: /usr/local/include/CGAL/Polygon_mesh_processing/internal/Corefinement/Visitor.h
Line: 663
Aborted (core dumped)


They are fairly small, so I wrote them to .off format and attached them to this message. I am aware from your documentation pages that there can be problems with sequential boolean operations, so I am using the kernel with exact predicates and exact constructions. Maybe the precision in the .off format is inadequate to diagnose the problem. I would be grateful for any help that can be provided.

    Sincerely,
    Sean Hardesty

mesh1.off (38K) Download Attachment
mesh2.off (34K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Polygon_mesh_processing::corefine_and_compute_difference

Sebastien Loriot (GeometryFactory)
When I open you files in the CGAL polyhedron demo, it is telling me that
your meshes are polygon soups (meaning you have non-manifold edges).
If I duplicate those edges to make it a self-intersecting surface
I have the following set of intersecting faces.

Sebastien.

On 12/05/2017 05:22 PM, Sean Hardesty wrote:

> I have a collection of meshes that overlap slightly, so I am going
> through a loop removing overlapping pieces. It works for a while, but
> eventually I run into trouble. I am calling
> PMP::corefine_and_compute_difference(CGAL 4.11) on a pair of meshes that
> satisfy
>
> !CGAL::Polygon_mesh_processing::does_self_intersect
> CGAL::Polygon_mesh_processing::does_bound_a_volume
>
> and I get the following:
>
> terminate called after throwing an instance of 'CGAL::Assertion_exception'
>    what(): CGAL ERROR: assertion violation!
> Expr: hedge!=start
> File:
> /usr/local/include/CGAL/Polygon_mesh_processing/internal/Corefinement/Visitor.h
> Line: 663
> Aborted (core dumped)
>
> They are fairly small, so I wrote them to .off format and attached them
> to this message. I am aware from your documentation pages that there can
> be problems with sequential boolean operations, so I am using the kernel
> with exact predicates and exact constructions. Maybe the precision in
> the .off format is inadequate to diagnose the problem. I would be
> grateful for any help that can be provided.
>
>      Sincerely,
>      Sean Hardesty
--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://sympa.inria.fr/sympa/info/cgal-discuss



Screenshot from 2017-12-06 09-23-00.png (446K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Polygon_mesh_processing::corefine_and_compute_difference

Sean Hardesty
I was able to compile the polyhedron demo and duplicate the results you described. However, I don't understand how I would test for this in my own program. I generated the .off files I sent from CGAL::Surface_mesh - how do I check whether such an object is a polygon soup (as is done in the demo)?

All of the following look okay:

mesh.is_valid() = 1
CGAL::Polygon_mesh_processing::does_bound_a_volume(mesh) = 1
CGAL::Polygon_mesh_processing::does_self_intersect(mesh) = 0
CGAL::Polygon_mesh_processing::is_outward_oriented(mesh) = 1
CGAL::is_closed(mesh) = 1

I wanted to try something from the polygon soup example, like this

CGAL::Polygon_mesh_processing::is_polygon_soup_a_polygon_mesh

but I haven't been able to figure out how to call that on a CGAL::Surface_mesh object.

    Thanks,
    Sean Hardesty

On Wed, Dec 6, 2017 at 2:24 AM, Sebastien Loriot (GeometryFactory) <[hidden email]> wrote:
When I open you files in the CGAL polyhedron demo, it is telling me that
your meshes are polygon soups (meaning you have non-manifold edges).
If I duplicate those edges to make it a self-intersecting surface
I have the following set of intersecting faces.

Sebastien.

On 12/05/2017 05:22 PM, Sean Hardesty wrote:
I have a collection of meshes that overlap slightly, so I am going through a loop removing overlapping pieces. It works for a while, but eventually I run into trouble. I am calling PMP::corefine_and_compute_difference(CGAL 4.11) on a pair of meshes that satisfy

!CGAL::Polygon_mesh_processing::does_self_intersect
CGAL::Polygon_mesh_processing::does_bound_a_volume

and I get the following:

terminate called after throwing an instance of 'CGAL::Assertion_exception'
   what(): CGAL ERROR: assertion violation!
Expr: hedge!=start
File: /usr/local/include/CGAL/Polygon_mesh_processing/internal/Corefinement/Visitor.h
Line: 663
Aborted (core dumped)

They are fairly small, so I wrote them to .off format and attached them to this message. I am aware from your documentation pages that there can be problems with sequential boolean operations, so I am using the kernel with exact predicates and exact constructions. Maybe the precision in the .off format is inadequate to diagnose the problem. I would be grateful for any help that can be provided.

     Sincerely,
     Sean Hardesty

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://sympa.inria.fr/sympa/info/cgal-discuss



Reply | Threaded
Open this post in threaded view
|

Re: Polygon_mesh_processing::corefine_and_compute_difference

Sebastien Loriot (GeometryFactory)
If you have been able to build a Polyhedron or a Surface_mesh it means
that it is not a polygon soup.

I guess you do something different than just loading the two files
posted. If you have a minimal example showing the pb it would help
to tell you exactly what the pb is.

Sebastien.

On 12/13/2017 03:33 PM, Sean Hardesty wrote:

> I was able to compile the polyhedron demo and duplicate the results you
> described. However, I don't understand how I would test for this in my
> own program. I generated the .off files I sent from CGAL::Surface_mesh -
> how do I check whether such an object is a polygon soup (as is done in
> the demo)?
>
> All of the following look okay:
>
> mesh.is_valid() = 1
> CGAL::Polygon_mesh_processing::does_bound_a_volume(mesh) = 1
> CGAL::Polygon_mesh_processing::does_self_intersect(mesh) = 0
> CGAL::Polygon_mesh_processing::is_outward_oriented(mesh) = 1
> CGAL::is_closed(mesh) = 1
>
> I wanted to try something from the polygon soup example, like this
>
> CGAL::Polygon_mesh_processing::is_polygon_soup_a_polygon_mesh
>
> but I haven't been able to figure out how to call that on a
> CGAL::Surface_mesh object.
>
>      Thanks,
>      Sean Hardesty
>
> On Wed, Dec 6, 2017 at 2:24 AM, Sebastien Loriot (GeometryFactory)
> <[hidden email] <mailto:[hidden email]>> wrote:
>
>     When I open you files in the CGAL polyhedron demo, it is telling me that
>     your meshes are polygon soups (meaning you have non-manifold edges).
>     If I duplicate those edges to make it a self-intersecting surface
>     I have the following set of intersecting faces.
>
>     Sebastien.
>
>     On 12/05/2017 05:22 PM, Sean Hardesty wrote:
>
>         I have a collection of meshes that overlap slightly, so I am
>         going through a loop removing overlapping pieces. It works for a
>         while, but eventually I run into trouble. I am calling
>         PMP::corefine_and_compute_difference(CGAL 4.11) on a pair of
>         meshes that satisfy
>
>         !CGAL::Polygon_mesh_processing::does_self_intersect
>         CGAL::Polygon_mesh_processing::does_bound_a_volume
>
>         and I get the following:
>
>         terminate called after throwing an instance of
>         'CGAL::Assertion_exception'
>             what(): CGAL ERROR: assertion violation!
>         Expr: hedge!=start
>         File:
>         /usr/local/include/CGAL/Polygon_mesh_processing/internal/Corefinement/Visitor.h
>         Line: 663
>         Aborted (core dumped)
>
>         They are fairly small, so I wrote them to .off format and
>         attached them to this message. I am aware from your
>         documentation pages that there can be problems with sequential
>         boolean operations, so I am using the kernel with exact
>         predicates and exact constructions. Maybe the precision in the
>         .off format is inadequate to diagnose the problem. I would be
>         grateful for any help that can be provided.
>
>               Sincerely,
>               Sean Hardesty
>
>
>     --
>     You are currently subscribed to cgal-discuss.
>     To unsubscribe or access the archives, go to
>     https://sympa.inria.fr/sympa/info/cgal-discuss
>     <https://sympa.inria.fr/sympa/info/cgal-discuss>
>
>
>

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://sympa.inria.fr/sympa/info/cgal-discuss


Reply | Threaded
Open this post in threaded view
|

Re: Polygon_mesh_processing::corefine_and_compute_difference

biswajitcse
Hi Sebastien,
Thanks a lot for your help.
Have a good day,

On Wed, Dec 13, 2017 at 9:07 PM, Sebastien Loriot (GeometryFactory) <[hidden email]> wrote:
If you have been able to build a Polyhedron or a Surface_mesh it means
that it is not a polygon soup.

I guess you do something different than just loading the two files
posted. If you have a minimal example showing the pb it would help
to tell you exactly what the pb is.

Sebastien.

On 12/13/2017 03:33 PM, Sean Hardesty wrote:
I was able to compile the polyhedron demo and duplicate the results you described. However, I don't understand how I would test for this in my own program. I generated the .off files I sent from CGAL::Surface_mesh - how do I check whether such an object is a polygon soup (as is done in the demo)?

All of the following look okay:

mesh.is_valid() = 1
CGAL::Polygon_mesh_processing::does_bound_a_volume(mesh) = 1
CGAL::Polygon_mesh_processing::does_self_intersect(mesh) = 0
CGAL::Polygon_mesh_processing::is_outward_oriented(mesh) = 1
CGAL::is_closed(mesh) = 1

I wanted to try something from the polygon soup example, like this

CGAL::Polygon_mesh_processing::is_polygon_soup_a_polygon_mesh

but I haven't been able to figure out how to call that on a CGAL::Surface_mesh object.

     Thanks,
     Sean Hardesty

On Wed, Dec 6, 2017 at 2:24 AM, Sebastien Loriot (GeometryFactory) <[hidden email] <mailto:[hidden email]>> wrote:

    When I open you files in the CGAL polyhedron demo, it is telling me that
    your meshes are polygon soups (meaning you have non-manifold edges).
    If I duplicate those edges to make it a self-intersecting surface
    I have the following set of intersecting faces.

    Sebastien.

    On 12/05/2017 05:22 PM, Sean Hardesty wrote:

        I have a collection of meshes that overlap slightly, so I am
        going through a loop removing overlapping pieces. It works for a
        while, but eventually I run into trouble. I am calling
        PMP::corefine_and_compute_difference(CGAL 4.11) on a pair of
        meshes that satisfy

        !CGAL::Polygon_mesh_processing::does_self_intersect
        CGAL::Polygon_mesh_processing::does_bound_a_volume

        and I get the following:

        terminate called after throwing an instance of
        'CGAL::Assertion_exception'
            what(): CGAL ERROR: assertion violation!
        Expr: hedge!=start
        File:
        /usr/local/include/CGAL/Polygon_mesh_processing/internal/Corefinement/Visitor.h
        Line: 663
        Aborted (core dumped)

        They are fairly small, so I wrote them to .off format and
        attached them to this message. I am aware from your
        documentation pages that there can be problems with sequential
        boolean operations, so I am using the kernel with exact
        predicates and exact constructions. Maybe the precision in the
        .off format is inadequate to diagnose the problem. I would be
        grateful for any help that can be provided.

              Sincerely,
              Sean Hardesty


    --     You are currently subscribed to cgal-discuss.
    To unsubscribe or access the archives, go to
    https://sympa.inria.fr/sympa/info/cgal-discuss
    <https://sympa.inria.fr/sympa/info/cgal-discuss>




--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://sympa.inria.fr/sympa/info/cgal-discuss





--
thanks and regards 
mobile:9163016823
Reply | Threaded
Open this post in threaded view
|

Re: Polygon_mesh_processing::corefine_and_compute_difference

Sean Hardesty
In reply to this post by Sebastien Loriot (GeometryFactory)
Thank you for your help! I am well aware of the difficulty of tracking these things down via e-mail...

I am using a source build of CGAL 4.11 because my Ubuntu distribution comes with 4.7. My program looks like this:

#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
#include <CGAL/Surface_mesh.h>

#include <CGAL/Polygon_mesh_processing/corefinement.h>

typedef CGAL::Exact_predicates_exact_constructions_kernel K;
typedef CGAL::Surface_mesh<K::Point_3> Mesh;

Skip some irrelevant code...

    // create cgal meshes

    std::vector<Mesh> mesh(ne);
    for(uint64_t ie=0;ie<ne;ie++) {
        foo.create_cgal_mesh(mesh[ie]);
    }

If I write them to .off files here, the Polyhedron demo does not say that any of them are polygon soups.

    // remove intersecting pieces


    for(uint64_t ie=0;ie<ne;ie++) {
        for(uint64_t je=ie+1;je<ne;je++) {
           
            bool result =
                CGAL::Polygon_mesh_processing::corefine_and_compute_difference(mesh[je], mesh[ie], mesh[je]);

            if (!result) {
                std::cout << "CGAL call returned false!" << std::endl;
                exit(1);
            }
        }
    }


If I write to a .off file each time through the inner loop and load the results into the polyhedron demo, I see that at some point, several of them become polygon soups (this seems to be the case independent of the precision with which I write the .off files). However, the loop continues well past the point where this first occurs. There is a particular pair of meshes (the ones I sent previously) where the call to corefine_and_compute_difference either results in the assertion error I mentioned in my first message, or runs for an implausibly long time (I think the difference between these two behaviors may have been caused by an update to my system libraries).

Suspecting that the real problem occurred earlier, I went back to find the first place where the results of corefine_and_compute_difference became a polygon soup. My meshes have some (approximate) symmetry, so I end up with two cases that are nearly identical, but one creates the first polygon soup and the other does not. The output for these two cases I have attached to this message. The demo lets me orient the polygon soup (mesh4.off) as a surface mesh and says it's not directly orientable, resulting in duplicated vertices and self-intersections. When I try to run self-intersection test, the demo segfaults.

    Sincerely,
    Sean






On Wed, Dec 13, 2017 at 9:37 AM, Sebastien Loriot (GeometryFactory) <[hidden email]> wrote:
If you have been able to build a Polyhedron or a Surface_mesh it means
that it is not a polygon soup.

I guess you do something different than just loading the two files
posted. If you have a minimal example showing the pb it would help
to tell you exactly what the pb is.

Sebastien.

On 12/13/2017 03:33 PM, Sean Hardesty wrote:
I was able to compile the polyhedron demo and duplicate the results you described. However, I don't understand how I would test for this in my own program. I generated the .off files I sent from CGAL::Surface_mesh - how do I check whether such an object is a polygon soup (as is done in the demo)?

All of the following look okay:

mesh.is_valid() = 1
CGAL::Polygon_mesh_processing::does_bound_a_volume(mesh) = 1
CGAL::Polygon_mesh_processing::does_self_intersect(mesh) = 0
CGAL::Polygon_mesh_processing::is_outward_oriented(mesh) = 1
CGAL::is_closed(mesh) = 1

I wanted to try something from the polygon soup example, like this

CGAL::Polygon_mesh_processing::is_polygon_soup_a_polygon_mesh

but I haven't been able to figure out how to call that on a CGAL::Surface_mesh object.

     Thanks,
     Sean Hardesty

On Wed, Dec 6, 2017 at 2:24 AM, Sebastien Loriot (GeometryFactory) <[hidden email] <mailto:[hidden email]>> wrote:

    When I open you files in the CGAL polyhedron demo, it is telling me that
    your meshes are polygon soups (meaning you have non-manifold edges).
    If I duplicate those edges to make it a self-intersecting surface
    I have the following set of intersecting faces.

    Sebastien.

    On 12/05/2017 05:22 PM, Sean Hardesty wrote:

        I have a collection of meshes that overlap slightly, so I am
        going through a loop removing overlapping pieces. It works for a
        while, but eventually I run into trouble. I am calling
        PMP::corefine_and_compute_difference(CGAL 4.11) on a pair of
        meshes that satisfy

        !CGAL::Polygon_mesh_processing::does_self_intersect
        CGAL::Polygon_mesh_processing::does_bound_a_volume

        and I get the following:

        terminate called after throwing an instance of
        'CGAL::Assertion_exception'
            what(): CGAL ERROR: assertion violation!
        Expr: hedge!=start
        File:
        /usr/local/include/CGAL/Polygon_mesh_processing/internal/Corefinement/Visitor.h
        Line: 663
        Aborted (core dumped)

        They are fairly small, so I wrote them to .off format and
        attached them to this message. I am aware from your
        documentation pages that there can be problems with sequential
        boolean operations, so I am using the kernel with exact
        predicates and exact constructions. Maybe the precision in the
        .off format is inadequate to diagnose the problem. I would be
        grateful for any help that can be provided.

              Sincerely,
              Sean Hardesty


    --     You are currently subscribed to cgal-discuss.
    To unsubscribe or access the archives, go to
    https://sympa.inria.fr/sympa/info/cgal-discuss
    <https://sympa.inria.fr/sympa/info/cgal-discuss>




--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://sympa.inria.fr/sympa/info/cgal-discuss




mesh3.off (11K) Download Attachment
mesh4.off (11K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Polygon_mesh_processing::corefine_and_compute_difference

Sebastien Loriot (GeometryFactory)
OK let's try the following:

after
bool result =
CGAL::Polygon_mesh_processing::corefine_and_compute_difference(mesh[je],
mesh[ie], mesh[je]);

Add:
{
std::ofstream otmp("/tmp/out.off");
otmp << std::setprecision(17) << mesh[je];
otmp.close();
std::ifstream itmp("/tmp/out.off");
std::vector<Point_3> pts;
std::vector< CGAL::cpp11::array<int, 3> > polygons;
CGAL::read_OFF(itmp, pts,  polygons);
if
(!CGAL::Polygon_mesh_processing::is_polygon_soup_a_polygon_mesh(polygons))
{
   std::cout << "BOOM!\n";
   exit(1);
}
}

Then send me with precision 17 mesh[je] and mesh[ie] before the call to
the function.

Sebastien.

PS: I haven't try to compile it so it's up to typos...


On 12/14/2017 04:09 AM, Sean Hardesty wrote:

> Thank you for your help! I am well aware of the difficulty of tracking
> these things down via e-mail...
>
> I am using a source build of CGAL 4.11 because my Ubuntu distribution
> comes with 4.7. My program looks like this:
>
> #include <CGAL/Exact_predicates_exact_constructions_kernel.h>
> #include <CGAL/Surface_mesh.h>
>
> #include <CGAL/Polygon_mesh_processing/corefinement.h>
>
> typedef CGAL::Exact_predicates_exact_constructions_kernel K;
> typedef CGAL::Surface_mesh<K::Point_3> Mesh;
>
> Skip some irrelevant code...
>
>      // create cgal meshes
>
>      std::vector<Mesh> mesh(ne);
>      for(uint64_t ie=0;ie<ne;ie++) {
>          foo.create_cgal_mesh(mesh[ie]);
>      }
>
> If I write them to .off files here, the Polyhedron demo does not say
> that any of them are polygon soups.
>
>      // remove intersecting pieces
>
>      for(uint64_t ie=0;ie<ne;ie++) {
>          for(uint64_t je=ie+1;je<ne;je++) {
>
>              bool result =
>                  
> CGAL::Polygon_mesh_processing::corefine_and_compute_difference(mesh[je],
> mesh[ie], mesh[je]);
>
>              if (!result) {
>                  std::cout << "CGAL call returned false!" << std::endl;
>                  exit(1);
>              }
>          }
>      }
>
> If I write to a .off file each time through the inner loop and load the
> results into the polyhedron demo, I see that at some point, several of
> them become polygon soups (this seems to be the case independent of the
> precision with which I write the .off files). However, the loop
> continues well past the point where this first occurs. There is a
> particular pair of meshes (the ones I sent previously) where the call to
> corefine_and_compute_difference either results in the assertion error I
> mentioned in my first message, or runs for an implausibly long time (I
> think the difference between these two behaviors may have been caused by
> an update to my system libraries).
>
> Suspecting that the real problem occurred earlier, I went back to find
> the first place where the results of corefine_and_compute_difference
> became a polygon soup. My meshes have some (approximate) symmetry, so I
> end up with two cases that are nearly identical, but one creates the
> first polygon soup and the other does not. The output for these two
> cases I have attached to this message. The demo lets me orient the
> polygon soup (mesh4.off) as a surface mesh and says it's not directly
> orientable, resulting in duplicated vertices and self-intersections.
> When I try to run self-intersection test, the demo segfaults.
>
>      Sincerely,
>      Sean
>
>
>
>
>
>
> On Wed, Dec 13, 2017 at 9:37 AM, Sebastien Loriot (GeometryFactory)
> <[hidden email] <mailto:[hidden email]>> wrote:
>
>     If you have been able to build a Polyhedron or a Surface_mesh it means
>     that it is not a polygon soup.
>
>     I guess you do something different than just loading the two files
>     posted. If you have a minimal example showing the pb it would help
>     to tell you exactly what the pb is.
>
>     Sebastien.
>
>     On 12/13/2017 03:33 PM, Sean Hardesty wrote:
>
>         I was able to compile the polyhedron demo and duplicate the
>         results you described. However, I don't understand how I would
>         test for this in my own program. I generated the .off files I
>         sent from CGAL::Surface_mesh - how do I check whether such an
>         object is a polygon soup (as is done in the demo)?
>
>         All of the following look okay:
>
>         mesh.is_valid() = 1
>         CGAL::Polygon_mesh_processing::does_bound_a_volume(mesh) = 1
>         CGAL::Polygon_mesh_processing::does_self_intersect(mesh) = 0
>         CGAL::Polygon_mesh_processing::is_outward_oriented(mesh) = 1
>         CGAL::is_closed(mesh) = 1
>
>         I wanted to try something from the polygon soup example, like this
>
>         CGAL::Polygon_mesh_processing::is_polygon_soup_a_polygon_mesh
>
>         but I haven't been able to figure out how to call that on a
>         CGAL::Surface_mesh object.
>
>               Thanks,
>               Sean Hardesty
>
>         On Wed, Dec 6, 2017 at 2:24 AM, Sebastien Loriot
>         (GeometryFactory) <[hidden email]
>         <mailto:[hidden email]> <mailto:[hidden email]
>         <mailto:[hidden email]>>> wrote:
>
>              When I open you files in the CGAL polyhedron demo, it is
>         telling me that
>              your meshes are polygon soups (meaning you have
>         non-manifold edges).
>              If I duplicate those edges to make it a self-intersecting
>         surface
>              I have the following set of intersecting faces.
>
>              Sebastien.
>
>              On 12/05/2017 05:22 PM, Sean Hardesty wrote:
>
>                  I have a collection of meshes that overlap slightly, so
>         I am
>                  going through a loop removing overlapping pieces. It
>         works for a
>                  while, but eventually I run into trouble. I am calling
>                  PMP::corefine_and_compute_difference(CGAL 4.11) on a
>         pair of
>                  meshes that satisfy
>
>                  !CGAL::Polygon_mesh_processing::does_self_intersect
>                  CGAL::Polygon_mesh_processing::does_bound_a_volume
>
>                  and I get the following:
>
>                  terminate called after throwing an instance of
>                  'CGAL::Assertion_exception'
>                      what(): CGAL ERROR: assertion violation!
>                  Expr: hedge!=start
>                  File:
>                
>         /usr/local/include/CGAL/Polygon_mesh_processing/internal/Corefinement/Visitor.h
>                  Line: 663
>                  Aborted (core dumped)
>
>                  They are fairly small, so I wrote them to .off format and
>                  attached them to this message. I am aware from your
>                  documentation pages that there can be problems with
>         sequential
>                  boolean operations, so I am using the kernel with exact
>                  predicates and exact constructions. Maybe the precision
>         in the
>                  .off format is inadequate to diagnose the problem. I
>         would be
>                  grateful for any help that can be provided.
>
>                        Sincerely,
>                        Sean Hardesty
>
>
>              --     You are currently subscribed to cgal-discuss.
>              To unsubscribe or access the archives, go to
>         https://sympa.inria.fr/sympa/info/cgal-discuss
>         <https://sympa.inria.fr/sympa/info/cgal-discuss>
>              <https://sympa.inria.fr/sympa/info/cgal-discuss
>         <https://sympa.inria.fr/sympa/info/cgal-discuss>>
>
>
>
>
>     --
>     You are currently subscribed to cgal-discuss.
>     To unsubscribe or access the archives, go to
>     https://sympa.inria.fr/sympa/info/cgal-discuss
>     <https://sympa.inria.fr/sympa/info/cgal-discuss>
>
>
>

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://sympa.inria.fr/sympa/info/cgal-discuss


Reply | Threaded
Open this post in threaded view
|

Re: Polygon_mesh_processing::corefine_and_compute_difference

biswajitcse
Good tips......and......trick.................

On Thu, Dec 14, 2017 at 1:27 PM, Sebastien Loriot (GeometryFactory) <[hidden email]> wrote:
OK let's try the following:

after
bool result = CGAL::Polygon_mesh_processing::corefine_and_compute_difference(mesh[je], mesh[ie], mesh[je]);

Add:
{
std::ofstream otmp("/tmp/out.off");
otmp << std::setprecision(17) << mesh[je];
otmp.close();
std::ifstream itmp("/tmp/out.off");
std::vector<Point_3> pts;
std::vector< CGAL::cpp11::array<int, 3> > polygons;
CGAL::read_OFF(itmp, pts,  polygons);
if (!CGAL::Polygon_mesh_processing::is_polygon_soup_a_polygon_mesh(polygons))
{
  std::cout << "BOOM!\n";
  exit(1);
}
}

Then send me with precision 17 mesh[je] and mesh[ie] before the call to the function.

Sebastien.

PS: I haven't try to compile it so it's up to typos...



On 12/14/2017 04:09 AM, Sean Hardesty wrote:
Thank you for your help! I am well aware of the difficulty of tracking these things down via e-mail...

I am using a source build of CGAL 4.11 because my Ubuntu distribution comes with 4.7. My program looks like this:

#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
#include <CGAL/Surface_mesh.h>

#include <CGAL/Polygon_mesh_processing/corefinement.h>

typedef CGAL::Exact_predicates_exact_constructions_kernel K;
typedef CGAL::Surface_mesh<K::Point_3> Mesh;

Skip some irrelevant code...

     // create cgal meshes

     std::vector<Mesh> mesh(ne);
     for(uint64_t ie=0;ie<ne;ie++) {
         foo.create_cgal_mesh(mesh[ie]);
     }

If I write them to .off files here, the Polyhedron demo does not say that any of them are polygon soups.

     // remove intersecting pieces

     for(uint64_t ie=0;ie<ne;ie++) {
         for(uint64_t je=ie+1;je<ne;je++) {

             bool result =
                 CGAL::Polygon_mesh_processing::corefine_and_compute_difference(mesh[je], mesh[ie], mesh[je]);

             if (!result) {
                 std::cout << "CGAL call returned false!" << std::endl;
                 exit(1);
             }
         }
     }

If I write to a .off file each time through the inner loop and load the results into the polyhedron demo, I see that at some point, several of them become polygon soups (this seems to be the case independent of the precision with which I write the .off files). However, the loop continues well past the point where this first occurs. There is a particular pair of meshes (the ones I sent previously) where the call to corefine_and_compute_difference either results in the assertion error I mentioned in my first message, or runs for an implausibly long time (I think the difference between these two behaviors may have been caused by an update to my system libraries).

Suspecting that the real problem occurred earlier, I went back to find the first place where the results of corefine_and_compute_difference became a polygon soup. My meshes have some (approximate) symmetry, so I end up with two cases that are nearly identical, but one creates the first polygon soup and the other does not. The output for these two cases I have attached to this message. The demo lets me orient the polygon soup (mesh4.off) as a surface mesh and says it's not directly orientable, resulting in duplicated vertices and self-intersections. When I try to run self-intersection test, the demo segfaults.

     Sincerely,
     Sean






On Wed, Dec 13, 2017 at 9:37 AM, Sebastien Loriot (GeometryFactory) <[hidden email] <mailto:[hidden email]>> wrote:

    If you have been able to build a Polyhedron or a Surface_mesh it means
    that it is not a polygon soup.

    I guess you do something different than just loading the two files
    posted. If you have a minimal example showing the pb it would help
    to tell you exactly what the pb is.

    Sebastien.

    On 12/13/2017 03:33 PM, Sean Hardesty wrote:

        I was able to compile the polyhedron demo and duplicate the
        results you described. However, I don't understand how I would
        test for this in my own program. I generated the .off files I
        sent from CGAL::Surface_mesh - how do I check whether such an
        object is a polygon soup (as is done in the demo)?

        All of the following look okay:

        mesh.is_valid() = 1
        CGAL::Polygon_mesh_processing::does_bound_a_volume(mesh) = 1
        CGAL::Polygon_mesh_processing::does_self_intersect(mesh) = 0
        CGAL::Polygon_mesh_processing::is_outward_oriented(mesh) = 1
        CGAL::is_closed(mesh) = 1

        I wanted to try something from the polygon soup example, like this

        CGAL::Polygon_mesh_processing::is_polygon_soup_a_polygon_mesh

        but I haven't been able to figure out how to call that on a
        CGAL::Surface_mesh object.

              Thanks,
              Sean Hardesty

        On Wed, Dec 6, 2017 at 2:24 AM, Sebastien Loriot
        (GeometryFactory) <[hidden email]
        <mailto:[hidden email]> <mailto:[hidden email]

        <mailto:[hidden email]>>> wrote:

             When I open you files in the CGAL polyhedron demo, it is
        telling me that
             your meshes are polygon soups (meaning you have
        non-manifold edges).
             If I duplicate those edges to make it a self-intersecting
        surface
             I have the following set of intersecting faces.

             Sebastien.

             On 12/05/2017 05:22 PM, Sean Hardesty wrote:

                 I have a collection of meshes that overlap slightly, so
        I am
                 going through a loop removing overlapping pieces. It
        works for a
                 while, but eventually I run into trouble. I am calling
                 PMP::corefine_and_compute_difference(CGAL 4.11) on a
        pair of
                 meshes that satisfy

                 !CGAL::Polygon_mesh_processing::does_self_intersect
                 CGAL::Polygon_mesh_processing::does_bound_a_volume

                 and I get the following:

                 terminate called after throwing an instance of
                 'CGAL::Assertion_exception'
                     what(): CGAL ERROR: assertion violation!
                 Expr: hedge!=start
                 File:
                        /usr/local/include/CGAL/Polygon_mesh_processing/internal/Corefinement/Visitor.h
                 Line: 663
                 Aborted (core dumped)

                 They are fairly small, so I wrote them to .off format and
                 attached them to this message. I am aware from your
                 documentation pages that there can be problems with
        sequential
                 boolean operations, so I am using the kernel with exact
                 predicates and exact constructions. Maybe the precision
        in the
                 .off format is inadequate to diagnose the problem. I
        would be
                 grateful for any help that can be provided.

                       Sincerely,
                       Sean Hardesty


             --     You are currently subscribed to cgal-discuss.
             To unsubscribe or access the archives, go to
        https://sympa.inria.fr/sympa/info/cgal-discuss
        <https://sympa.inria.fr/sympa/info/cgal-discuss>
             <https://sympa.inria.fr/sympa/info/cgal-discuss
        <https://sympa.inria.fr/sympa/info/cgal-discuss>>




    --     You are currently subscribed to cgal-discuss.
    To unsubscribe or access the archives, go to
    https://sympa.inria.fr/sympa/info/cgal-discuss
    <https://sympa.inria.fr/sympa/info/cgal-discuss>




--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://sympa.inria.fr/sympa/info/cgal-discuss





--
thanks and regards 
mobile:9163016823
Reply | Threaded
Open this post in threaded view
|

Re: Polygon_mesh_processing::corefine_and_compute_difference

Sebastien Loriot (GeometryFactory)
In reply to this post by Sebastien Loriot (GeometryFactory)
Thanks Sean for sending the files.
You are actually hitting a known issue that I'll officially fix soon.

In the meantime here is what is going on and how to fix it:

The boolean operation is creating a non-manifold vertex (2 mesh parts
connected by a vertex in your case). I'm pretty sure from your data
that you'd like to discard the small part.

In order to do that, you can call the following function that will
duplicate all non-manifold vertices:

std::size_t nb_dv=duplicate_non_manifold_vertices(mesh[je],
get(CGAL::vertex_point, mesh_je));

Then you should end-up with 2 connected components
you can filter with the following:

if (nb_dv!=0)
   PMP::keep_largest_connected_components(mesh[je], 1);

Sorry for the inconvenience.

Sebastien.

template <class TriangleMesh, class Vpm>
std::size_t duplicate_non_manifold_vertices(TriangleMesh& tm, Vpm vpm)
{
   typedef boost::graph_traits<TriangleMesh> GT;
   typedef typename GT::vertex_descriptor vertex_descriptor;
   typedef typename GT::halfedge_descriptor halfedge_descriptor;

   boost::unordered_set<vertex_descriptor> vertices_handled;
   boost::unordered_set<halfedge_descriptor> halfedges_handled;

   std::size_t nb_new_vertices=0;

   std::vector<halfedge_descriptor> non_manifold_cones;
   BOOST_FOREACH(halfedge_descriptor h, halfedges(tm))
   {
     if (halfedges_handled.insert(h).second)
     {
       vertex_descriptor vd = target(h, tm);
       if ( !vertices_handled.insert(vd).second )
       {
         non_manifold_cones.push_back(h);
       }
       else
         set_halfedge(vd, h, tm);
       halfedge_descriptor start=opposite(next(h, tm), tm);
       h=start;
       do{
         halfedges_handled.insert(h);
         h=opposite(next(h, tm), tm);
       }while(h!=start);
     }
   }

   if (!non_manifold_cones.empty())  {
     BOOST_FOREACH(halfedge_descriptor h, non_manifold_cones)
     {
       halfedge_descriptor start = h;
       vertex_descriptor new_vd = add_vertex(tm);
       ++nb_new_vertices;
       put(vpm, new_vd, get(vpm, target(h, tm)));
       set_halfedge(new_vd, h, tm);
       do{
         set_target(h, new_vd, tm);
         h=opposite(next(h, tm), tm);
       } while(h!=start);
     }
   }

   return nb_new_vertices;
}



On 12/14/2017 08:57 AM, Sebastien Loriot (GeometryFactory) wrote:

> OK let's try the following:
>
> after
> bool result =
> CGAL::Polygon_mesh_processing::corefine_and_compute_difference(mesh[je],
> mesh[ie], mesh[je]);
>
> Add:
> {
> std::ofstream otmp("/tmp/out.off");
> otmp << std::setprecision(17) << mesh[je];
> otmp.close();
> std::ifstream itmp("/tmp/out.off");
> std::vector<Point_3> pts;
> std::vector< CGAL::cpp11::array<int, 3> > polygons;
> CGAL::read_OFF(itmp, pts,  polygons);
> if
> (!CGAL::Polygon_mesh_processing::is_polygon_soup_a_polygon_mesh(polygons))
> {
>    std::cout << "BOOM!\n";
>    exit(1);
> }
> }
>
> Then send me with precision 17 mesh[je] and mesh[ie] before the call to
> the function.
>
> Sebastien.
>
> PS: I haven't try to compile it so it's up to typos...
>
>
> On 12/14/2017 04:09 AM, Sean Hardesty wrote:
>> Thank you for your help! I am well aware of the difficulty of tracking
>> these things down via e-mail...
>>
>> I am using a source build of CGAL 4.11 because my Ubuntu distribution
>> comes with 4.7. My program looks like this:
>>
>> #include <CGAL/Exact_predicates_exact_constructions_kernel.h>
>> #include <CGAL/Surface_mesh.h>
>>
>> #include <CGAL/Polygon_mesh_processing/corefinement.h>
>>
>> typedef CGAL::Exact_predicates_exact_constructions_kernel K;
>> typedef CGAL::Surface_mesh<K::Point_3> Mesh;
>>
>> Skip some irrelevant code...
>>
>>      // create cgal meshes
>>
>>      std::vector<Mesh> mesh(ne);
>>      for(uint64_t ie=0;ie<ne;ie++) {
>>          foo.create_cgal_mesh(mesh[ie]);
>>      }
>>
>> If I write them to .off files here, the Polyhedron demo does not say
>> that any of them are polygon soups.
>>
>>      // remove intersecting pieces
>>
>>      for(uint64_t ie=0;ie<ne;ie++) {
>>          for(uint64_t je=ie+1;je<ne;je++) {
>>
>>              bool result =
>> CGAL::Polygon_mesh_processing::corefine_and_compute_difference(mesh[je],
>> mesh[ie], mesh[je]);
>>
>>              if (!result) {
>>                  std::cout << "CGAL call returned false!" << std::endl;
>>                  exit(1);
>>              }
>>          }
>>      }
>>
>> If I write to a .off file each time through the inner loop and load
>> the results into the polyhedron demo, I see that at some point,
>> several of them become polygon soups (this seems to be the case
>> independent of the precision with which I write the .off files).
>> However, the loop continues well past the point where this first
>> occurs. There is a particular pair of meshes (the ones I sent
>> previously) where the call to corefine_and_compute_difference either
>> results in the assertion error I mentioned in my first message, or
>> runs for an implausibly long time (I think the difference between
>> these two behaviors may have been caused by an update to my system
>> libraries).
>>
>> Suspecting that the real problem occurred earlier, I went back to find
>> the first place where the results of corefine_and_compute_difference
>> became a polygon soup. My meshes have some (approximate) symmetry, so
>> I end up with two cases that are nearly identical, but one creates the
>> first polygon soup and the other does not. The output for these two
>> cases I have attached to this message. The demo lets me orient the
>> polygon soup (mesh4.off) as a surface mesh and says it's not directly
>> orientable, resulting in duplicated vertices and self-intersections.
>> When I try to run self-intersection test, the demo segfaults.
>>
>>      Sincerely,
>>      Sean
>>
>>
>>
>>
>>
>>
>> On Wed, Dec 13, 2017 at 9:37 AM, Sebastien Loriot (GeometryFactory)
>> <[hidden email] <mailto:[hidden email]>> wrote:
>>
>>     If you have been able to build a Polyhedron or a Surface_mesh it
>> means
>>     that it is not a polygon soup.
>>
>>     I guess you do something different than just loading the two files
>>     posted. If you have a minimal example showing the pb it would help
>>     to tell you exactly what the pb is.
>>
>>     Sebastien.
>>
>>     On 12/13/2017 03:33 PM, Sean Hardesty wrote:
>>
>>         I was able to compile the polyhedron demo and duplicate the
>>         results you described. However, I don't understand how I would
>>         test for this in my own program. I generated the .off files I
>>         sent from CGAL::Surface_mesh - how do I check whether such an
>>         object is a polygon soup (as is done in the demo)?
>>
>>         All of the following look okay:
>>
>>         mesh.is_valid() = 1
>>         CGAL::Polygon_mesh_processing::does_bound_a_volume(mesh) = 1
>>         CGAL::Polygon_mesh_processing::does_self_intersect(mesh) = 0
>>         CGAL::Polygon_mesh_processing::is_outward_oriented(mesh) = 1
>>         CGAL::is_closed(mesh) = 1
>>
>>         I wanted to try something from the polygon soup example, like
>> this
>>
>>         CGAL::Polygon_mesh_processing::is_polygon_soup_a_polygon_mesh
>>
>>         but I haven't been able to figure out how to call that on a
>>         CGAL::Surface_mesh object.
>>
>>               Thanks,
>>               Sean Hardesty
>>
>>         On Wed, Dec 6, 2017 at 2:24 AM, Sebastien Loriot
>>         (GeometryFactory) <[hidden email]
>>         <mailto:[hidden email]> <mailto:[hidden email]
>>         <mailto:[hidden email]>>> wrote:
>>
>>              When I open you files in the CGAL polyhedron demo, it is
>>         telling me that
>>              your meshes are polygon soups (meaning you have
>>         non-manifold edges).
>>              If I duplicate those edges to make it a self-intersecting
>>         surface
>>              I have the following set of intersecting faces.
>>
>>              Sebastien.
>>
>>              On 12/05/2017 05:22 PM, Sean Hardesty wrote:
>>
>>                  I have a collection of meshes that overlap slightly, so
>>         I am
>>                  going through a loop removing overlapping pieces. It
>>         works for a
>>                  while, but eventually I run into trouble. I am calling
>>                  PMP::corefine_and_compute_difference(CGAL 4.11) on a
>>         pair of
>>                  meshes that satisfy
>>
>>                  !CGAL::Polygon_mesh_processing::does_self_intersect
>>                  CGAL::Polygon_mesh_processing::does_bound_a_volume
>>
>>                  and I get the following:
>>
>>                  terminate called after throwing an instance of
>>                  'CGAL::Assertion_exception'
>>                      what(): CGAL ERROR: assertion violation!
>>                  Expr: hedge!=start
>>                  File:
>>        
>> /usr/local/include/CGAL/Polygon_mesh_processing/internal/Corefinement/Visitor.h
>>
>>                  Line: 663
>>                  Aborted (core dumped)
>>
>>                  They are fairly small, so I wrote them to .off format
>> and
>>                  attached them to this message. I am aware from your
>>                  documentation pages that there can be problems with
>>         sequential
>>                  boolean operations, so I am using the kernel with exact
>>                  predicates and exact constructions. Maybe the precision
>>         in the
>>                  .off format is inadequate to diagnose the problem. I
>>         would be
>>                  grateful for any help that can be provided.
>>
>>                        Sincerely,
>>                        Sean Hardesty
>>
>>
>>              --     You are currently subscribed to cgal-discuss.
>>              To unsubscribe or access the archives, go to
>>         https://sympa.inria.fr/sympa/info/cgal-discuss
>>         <https://sympa.inria.fr/sympa/info/cgal-discuss>
>>              <https://sympa.inria.fr/sympa/info/cgal-discuss
>>         <https://sympa.inria.fr/sympa/info/cgal-discuss>>
>>
>>
>>
>>
>>     --     You are currently subscribed to cgal-discuss.
>>     To unsubscribe or access the archives, go to
>>     https://sympa.inria.fr/sympa/info/cgal-discuss
>>     <https://sympa.inria.fr/sympa/info/cgal-discuss>
>>
>>
>>

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://sympa.inria.fr/sympa/info/cgal-discuss


Reply | Threaded
Open this post in threaded view
|

Re: Polygon_mesh_processing::corefine_and_compute_difference

Sean Hardesty
Thank you, Sebastien! It works beautifully.

On Fri, Dec 15, 2017 at 2:02 AM, Sebastien Loriot (GeometryFactory) <[hidden email]> wrote:
Thanks Sean for sending the files.
You are actually hitting a known issue that I'll officially fix soon.

In the meantime here is what is going on and how to fix it:

The boolean operation is creating a non-manifold vertex (2 mesh parts connected by a vertex in your case). I'm pretty sure from your data
that you'd like to discard the small part.

In order to do that, you can call the following function that will
duplicate all non-manifold vertices:

std::size_t nb_dv=duplicate_non_manifold_vertices(mesh[je], get(CGAL::vertex_point, mesh_je));

Then you should end-up with 2 connected components
you can filter with the following:

if (nb_dv!=0)
  PMP::keep_largest_connected_components(mesh[je], 1);

Sorry for the inconvenience.

Sebastien.

template <class TriangleMesh, class Vpm>
std::size_t duplicate_non_manifold_vertices(TriangleMesh& tm, Vpm vpm)
{
  typedef boost::graph_traits<TriangleMesh> GT;
  typedef typename GT::vertex_descriptor vertex_descriptor;
  typedef typename GT::halfedge_descriptor halfedge_descriptor;

  boost::unordered_set<vertex_descriptor> vertices_handled;
  boost::unordered_set<halfedge_descriptor> halfedges_handled;

  std::size_t nb_new_vertices=0;

  std::vector<halfedge_descriptor> non_manifold_cones;
  BOOST_FOREACH(halfedge_descriptor h, halfedges(tm))
  {
    if (halfedges_handled.insert(h).second)
    {
      vertex_descriptor vd = target(h, tm);
      if ( !vertices_handled.insert(vd).second )
      {
        non_manifold_cones.push_back(h);
      }
      else
        set_halfedge(vd, h, tm);
      halfedge_descriptor start=opposite(next(h, tm), tm);
      h=start;
      do{
        halfedges_handled.insert(h);
        h=opposite(next(h, tm), tm);
      }while(h!=start);
    }
  }

  if (!non_manifold_cones.empty())  {
    BOOST_FOREACH(halfedge_descriptor h, non_manifold_cones)
    {
      halfedge_descriptor start = h;
      vertex_descriptor new_vd = add_vertex(tm);
      ++nb_new_vertices;
      put(vpm, new_vd, get(vpm, target(h, tm)));
      set_halfedge(new_vd, h, tm);
      do{
        set_target(h, new_vd, tm);
        h=opposite(next(h, tm), tm);
      } while(h!=start);
    }
  }

  return nb_new_vertices;

}



On 12/14/2017 08:57 AM, Sebastien Loriot (GeometryFactory) wrote:
OK let's try the following:

after
bool result = CGAL::Polygon_mesh_processing::corefine_and_compute_difference(mesh[je], mesh[ie], mesh[je]);

Add:
{
std::ofstream otmp("/tmp/out.off");
otmp << std::setprecision(17) << mesh[je];
otmp.close();
std::ifstream itmp("/tmp/out.off");
std::vector<Point_3> pts;
std::vector< CGAL::cpp11::array<int, 3> > polygons;
CGAL::read_OFF(itmp, pts,  polygons);
if (!CGAL::Polygon_mesh_processing::is_polygon_soup_a_polygon_mesh(polygons))
{
   std::cout << "BOOM!\n";
   exit(1);
}
}

Then send me with precision 17 mesh[je] and mesh[ie] before the call to the function.

Sebastien.

PS: I haven't try to compile it so it's up to typos...


On 12/14/2017 04:09 AM, Sean Hardesty wrote:
Thank you for your help! I am well aware of the difficulty of tracking these things down via e-mail...

I am using a source build of CGAL 4.11 because my Ubuntu distribution comes with 4.7. My program looks like this:

#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
#include <CGAL/Surface_mesh.h>

#include <CGAL/Polygon_mesh_processing/corefinement.h>

typedef CGAL::Exact_predicates_exact_constructions_kernel K;
typedef CGAL::Surface_mesh<K::Point_3> Mesh;

Skip some irrelevant code...

     // create cgal meshes

     std::vector<Mesh> mesh(ne);
     for(uint64_t ie=0;ie<ne;ie++) {
         foo.create_cgal_mesh(mesh[ie]);
     }

If I write them to .off files here, the Polyhedron demo does not say that any of them are polygon soups.

     // remove intersecting pieces

     for(uint64_t ie=0;ie<ne;ie++) {
         for(uint64_t je=ie+1;je<ne;je++) {

             bool result =
CGAL::Polygon_mesh_processing::corefine_and_compute_difference(mesh[je], mesh[ie], mesh[je]);

             if (!result) {
                 std::cout << "CGAL call returned false!" << std::endl;
                 exit(1);
             }
         }
     }

If I write to a .off file each time through the inner loop and load the results into the polyhedron demo, I see that at some point, several of them become polygon soups (this seems to be the case independent of the precision with which I write the .off files). However, the loop continues well past the point where this first occurs. There is a particular pair of meshes (the ones I sent previously) where the call to corefine_and_compute_difference either results in the assertion error I mentioned in my first message, or runs for an implausibly long time (I think the difference between these two behaviors may have been caused by an update to my system libraries).

Suspecting that the real problem occurred earlier, I went back to find the first place where the results of corefine_and_compute_difference became a polygon soup. My meshes have some (approximate) symmetry, so I end up with two cases that are nearly identical, but one creates the first polygon soup and the other does not. The output for these two cases I have attached to this message. The demo lets me orient the polygon soup (mesh4.off) as a surface mesh and says it's not directly orientable, resulting in duplicated vertices and self-intersections. When I try to run self-intersection test, the demo segfaults.

     Sincerely,
     Sean






On Wed, Dec 13, 2017 at 9:37 AM, Sebastien Loriot (GeometryFactory) <[hidden email] <mailto:[hidden email]>> wrote:

    If you have been able to build a Polyhedron or a Surface_mesh it means
    that it is not a polygon soup.

    I guess you do something different than just loading the two files
    posted. If you have a minimal example showing the pb it would help
    to tell you exactly what the pb is.

    Sebastien.

    On 12/13/2017 03:33 PM, Sean Hardesty wrote:

        I was able to compile the polyhedron demo and duplicate the
        results you described. However, I don't understand how I would
        test for this in my own program. I generated the .off files I
        sent from CGAL::Surface_mesh - how do I check whether such an
        object is a polygon soup (as is done in the demo)?

        All of the following look okay:

        mesh.is_valid() = 1
        CGAL::Polygon_mesh_processing::does_bound_a_volume(mesh) = 1
        CGAL::Polygon_mesh_processing::does_self_intersect(mesh) = 0
        CGAL::Polygon_mesh_processing::is_outward_oriented(mesh) = 1
        CGAL::is_closed(mesh) = 1

        I wanted to try something from the polygon soup example, like this

        CGAL::Polygon_mesh_processing::is_polygon_soup_a_polygon_mesh

        but I haven't been able to figure out how to call that on a
        CGAL::Surface_mesh object.

              Thanks,
              Sean Hardesty

        On Wed, Dec 6, 2017 at 2:24 AM, Sebastien Loriot
        (GeometryFactory) <[hidden email]
        <mailto:[hidden email]> <mailto:[hidden email]
        <mailto:[hidden email]>>> wrote:

             When I open you files in the CGAL polyhedron demo, it is
        telling me that
             your meshes are polygon soups (meaning you have
        non-manifold edges).
             If I duplicate those edges to make it a self-intersecting
        surface
             I have the following set of intersecting faces.

             Sebastien.

             On 12/05/2017 05:22 PM, Sean Hardesty wrote:

                 I have a collection of meshes that overlap slightly, so
        I am
                 going through a loop removing overlapping pieces. It
        works for a
                 while, but eventually I run into trouble. I am calling
                 PMP::corefine_and_compute_difference(CGAL 4.11) on a
        pair of
                 meshes that satisfy

                 !CGAL::Polygon_mesh_processing::does_self_intersect
                 CGAL::Polygon_mesh_processing::does_bound_a_volume

                 and I get the following:

                 terminate called after throwing an instance of
                 'CGAL::Assertion_exception'
                     what(): CGAL ERROR: assertion violation!
                 Expr: hedge!=start
                 File:
        /usr/local/include/CGAL/Polygon_mesh_processing/internal/Corefinement/Visitor.h
                 Line: 663
                 Aborted (core dumped)

                 They are fairly small, so I wrote them to .off format and
                 attached them to this message. I am aware from your
                 documentation pages that there can be problems with
        sequential
                 boolean operations, so I am using the kernel with exact
                 predicates and exact constructions. Maybe the precision
        in the
                 .off format is inadequate to diagnose the problem. I
        would be
                 grateful for any help that can be provided.

                       Sincerely,
                       Sean Hardesty


             --     You are currently subscribed to cgal-discuss.
             To unsubscribe or access the archives, go to
        https://sympa.inria.fr/sympa/info/cgal-discuss
        <https://sympa.inria.fr/sympa/info/cgal-discuss>
             <https://sympa.inria.fr/sympa/info/cgal-discuss
        <https://sympa.inria.fr/sympa/info/cgal-discuss>>




    --     You are currently subscribed to cgal-discuss.
    To unsubscribe or access the archives, go to
    https://sympa.inria.fr/sympa/info/cgal-discuss
    <https://sympa.inria.fr/sympa/info/cgal-discuss>




--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://sympa.inria.fr/sympa/info/cgal-discuss



Reply | Threaded
Open this post in threaded view
|

Re: Polygon_mesh_processing::corefine_and_compute_difference

biswajitcse
Thank you, Sebastien! you are awesome.........

On Fri, Dec 22, 2017 at 9:11 AM, Sean Hardesty <[hidden email]> wrote:
Thank you, Sebastien! It works beautifully.

On Fri, Dec 15, 2017 at 2:02 AM, Sebastien Loriot (GeometryFactory) <[hidden email]> wrote:
Thanks Sean for sending the files.
You are actually hitting a known issue that I'll officially fix soon.

In the meantime here is what is going on and how to fix it:

The boolean operation is creating a non-manifold vertex (2 mesh parts connected by a vertex in your case). I'm pretty sure from your data
that you'd like to discard the small part.

In order to do that, you can call the following function that will
duplicate all non-manifold vertices:

std::size_t nb_dv=duplicate_non_manifold_vertices(mesh[je], get(CGAL::vertex_point, mesh_je));

Then you should end-up with 2 connected components
you can filter with the following:

if (nb_dv!=0)
  PMP::keep_largest_connected_components(mesh[je], 1);

Sorry for the inconvenience.

Sebastien.

template <class TriangleMesh, class Vpm>
std::size_t duplicate_non_manifold_vertices(TriangleMesh& tm, Vpm vpm)
{
  typedef boost::graph_traits<TriangleMesh> GT;
  typedef typename GT::vertex_descriptor vertex_descriptor;
  typedef typename GT::halfedge_descriptor halfedge_descriptor;

  boost::unordered_set<vertex_descriptor> vertices_handled;
  boost::unordered_set<halfedge_descriptor> halfedges_handled;

  std::size_t nb_new_vertices=0;

  std::vector<halfedge_descriptor> non_manifold_cones;
  BOOST_FOREACH(halfedge_descriptor h, halfedges(tm))
  {
    if (halfedges_handled.insert(h).second)
    {
      vertex_descriptor vd = target(h, tm);
      if ( !vertices_handled.insert(vd).second )
      {
        non_manifold_cones.push_back(h);
      }
      else
        set_halfedge(vd, h, tm);
      halfedge_descriptor start=opposite(next(h, tm), tm);
      h=start;
      do{
        halfedges_handled.insert(h);
        h=opposite(next(h, tm), tm);
      }while(h!=start);
    }
  }

  if (!non_manifold_cones.empty())  {
    BOOST_FOREACH(halfedge_descriptor h, non_manifold_cones)
    {
      halfedge_descriptor start = h;
      vertex_descriptor new_vd = add_vertex(tm);
      ++nb_new_vertices;
      put(vpm, new_vd, get(vpm, target(h, tm)));
      set_halfedge(new_vd, h, tm);
      do{
        set_target(h, new_vd, tm);
        h=opposite(next(h, tm), tm);
      } while(h!=start);
    }
  }

  return nb_new_vertices;

}



On 12/14/2017 08:57 AM, Sebastien Loriot (GeometryFactory) wrote:
OK let's try the following:

after
bool result = CGAL::Polygon_mesh_processing::corefine_and_compute_difference(mesh[je], mesh[ie], mesh[je]);

Add:
{
std::ofstream otmp("/tmp/out.off");
otmp << std::setprecision(17) << mesh[je];
otmp.close();
std::ifstream itmp("/tmp/out.off");
std::vector<Point_3> pts;
std::vector< CGAL::cpp11::array<int, 3> > polygons;
CGAL::read_OFF(itmp, pts,  polygons);
if (!CGAL::Polygon_mesh_processing::is_polygon_soup_a_polygon_mesh(polygons))
{
   std::cout << "BOOM!\n";
   exit(1);
}
}

Then send me with precision 17 mesh[je] and mesh[ie] before the call to the function.

Sebastien.

PS: I haven't try to compile it so it's up to typos...


On 12/14/2017 04:09 AM, Sean Hardesty wrote:
Thank you for your help! I am well aware of the difficulty of tracking these things down via e-mail...

I am using a source build of CGAL 4.11 because my Ubuntu distribution comes with 4.7. My program looks like this:

#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
#include <CGAL/Surface_mesh.h>

#include <CGAL/Polygon_mesh_processing/corefinement.h>

typedef CGAL::Exact_predicates_exact_constructions_kernel K;
typedef CGAL::Surface_mesh<K::Point_3> Mesh;

Skip some irrelevant code...

     // create cgal meshes

     std::vector<Mesh> mesh(ne);
     for(uint64_t ie=0;ie<ne;ie++) {
         foo.create_cgal_mesh(mesh[ie]);
     }

If I write them to .off files here, the Polyhedron demo does not say that any of them are polygon soups.

     // remove intersecting pieces

     for(uint64_t ie=0;ie<ne;ie++) {
         for(uint64_t je=ie+1;je<ne;je++) {

             bool result =
CGAL::Polygon_mesh_processing::corefine_and_compute_difference(mesh[je], mesh[ie], mesh[je]);

             if (!result) {
                 std::cout << "CGAL call returned false!" << std::endl;
                 exit(1);
             }
         }
     }

If I write to a .off file each time through the inner loop and load the results into the polyhedron demo, I see that at some point, several of them become polygon soups (this seems to be the case independent of the precision with which I write the .off files). However, the loop continues well past the point where this first occurs. There is a particular pair of meshes (the ones I sent previously) where the call to corefine_and_compute_difference either results in the assertion error I mentioned in my first message, or runs for an implausibly long time (I think the difference between these two behaviors may have been caused by an update to my system libraries).

Suspecting that the real problem occurred earlier, I went back to find the first place where the results of corefine_and_compute_difference became a polygon soup. My meshes have some (approximate) symmetry, so I end up with two cases that are nearly identical, but one creates the first polygon soup and the other does not. The output for these two cases I have attached to this message. The demo lets me orient the polygon soup (mesh4.off) as a surface mesh and says it's not directly orientable, resulting in duplicated vertices and self-intersections. When I try to run self-intersection test, the demo segfaults.

     Sincerely,
     Sean






On Wed, Dec 13, 2017 at 9:37 AM, Sebastien Loriot (GeometryFactory) <[hidden email] <mailto:[hidden email]>> wrote:

    If you have been able to build a Polyhedron or a Surface_mesh it means
    that it is not a polygon soup.

    I guess you do something different than just loading the two files
    posted. If you have a minimal example showing the pb it would help
    to tell you exactly what the pb is.

    Sebastien.

    On 12/13/2017 03:33 PM, Sean Hardesty wrote:

        I was able to compile the polyhedron demo and duplicate the
        results you described. However, I don't understand how I would
        test for this in my own program. I generated the .off files I
        sent from CGAL::Surface_mesh - how do I check whether such an
        object is a polygon soup (as is done in the demo)?

        All of the following look okay:

        mesh.is_valid() = 1
        CGAL::Polygon_mesh_processing::does_bound_a_volume(mesh) = 1
        CGAL::Polygon_mesh_processing::does_self_intersect(mesh) = 0
        CGAL::Polygon_mesh_processing::is_outward_oriented(mesh) = 1
        CGAL::is_closed(mesh) = 1

        I wanted to try something from the polygon soup example, like this

        CGAL::Polygon_mesh_processing::is_polygon_soup_a_polygon_mesh

        but I haven't been able to figure out how to call that on a
        CGAL::Surface_mesh object.

              Thanks,
              Sean Hardesty

        On Wed, Dec 6, 2017 at 2:24 AM, Sebastien Loriot
        (GeometryFactory) <[hidden email]
        <mailto:[hidden email]> <mailto:[hidden email]
        <mailto:[hidden email]>>> wrote:

             When I open you files in the CGAL polyhedron demo, it is
        telling me that
             your meshes are polygon soups (meaning you have
        non-manifold edges).
             If I duplicate those edges to make it a self-intersecting
        surface
             I have the following set of intersecting faces.

             Sebastien.

             On 12/05/2017 05:22 PM, Sean Hardesty wrote:

                 I have a collection of meshes that overlap slightly, so
        I am
                 going through a loop removing overlapping pieces. It
        works for a
                 while, but eventually I run into trouble. I am calling
                 PMP::corefine_and_compute_difference(CGAL 4.11) on a
        pair of
                 meshes that satisfy

                 !CGAL::Polygon_mesh_processing::does_self_intersect
                 CGAL::Polygon_mesh_processing::does_bound_a_volume

                 and I get the following:

                 terminate called after throwing an instance of
                 'CGAL::Assertion_exception'
                     what(): CGAL ERROR: assertion violation!
                 Expr: hedge!=start
                 File:
        /usr/local/include/CGAL/Polygon_mesh_processing/internal/Corefinement/Visitor.h
                 Line: 663
                 Aborted (core dumped)

                 They are fairly small, so I wrote them to .off format and
                 attached them to this message. I am aware from your
                 documentation pages that there can be problems with
        sequential
                 boolean operations, so I am using the kernel with exact
                 predicates and exact constructions. Maybe the precision
        in the
                 .off format is inadequate to diagnose the problem. I
        would be
                 grateful for any help that can be provided.

                       Sincerely,
                       Sean Hardesty


             --     You are currently subscribed to cgal-discuss.
             To unsubscribe or access the archives, go to
        https://sympa.inria.fr/sympa/info/cgal-discuss
        <https://sympa.inria.fr/sympa/info/cgal-discuss>
             <https://sympa.inria.fr/sympa/info/cgal-discuss
        <https://sympa.inria.fr/sympa/info/cgal-discuss>>




    --     You are currently subscribed to cgal-discuss.
    To unsubscribe or access the archives, go to
    https://sympa.inria.fr/sympa/info/cgal-discuss
    <https://sympa.inria.fr/sympa/info/cgal-discuss>




--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://sympa.inria.fr/sympa/info/cgal-discuss






--
thanks and regards 
mobile:9163016823
Reply | Threaded
Open this post in threaded view
|

Re: Polygon_mesh_processing::corefine_and_compute_difference

Sean Hardesty
In reply to this post by Sebastien Loriot (GeometryFactory)
Sebastien,

Back in December, you sent a function duplicate_non_manifold_vertices to be used prior to calling keep_largest_connected_components. It has mostly worked fine, but I have just recently stumbled across a case where it fails quickly and consistently: CGAL 4.11 segfaults (same thing with 4.11.1, 4.12) in the call to CGAL::Polygon_mesh_processing::corefine_and_compute_difference. I have attached .off files that were written immediately prior to the call where it segfaults. They aren't polygon soups, but they do have problems - looks like triangles are hanging off the corners, and weren't removed by prior calls to duplicate_non_manifold_vertices and keep_largest_connected_components. Do you have any suggestions about how to fix it?

    Thanks,
    Sean Hardesty



On Fri, Dec 15, 2017 at 2:02 AM, Sebastien Loriot (GeometryFactory) <[hidden email]> wrote:
Thanks Sean for sending the files.
You are actually hitting a known issue that I'll officially fix soon.

In the meantime here is what is going on and how to fix it:

The boolean operation is creating a non-manifold vertex (2 mesh parts connected by a vertex in your case). I'm pretty sure from your data
that you'd like to discard the small part.

In order to do that, you can call the following function that will
duplicate all non-manifold vertices:

std::size_t nb_dv=duplicate_non_manifold_vertices(mesh[je], get(CGAL::vertex_point, mesh_je));

Then you should end-up with 2 connected components
you can filter with the following:

if (nb_dv!=0)
  PMP::keep_largest_connected_components(mesh[je], 1);

Sorry for the inconvenience.

Sebastien.

template <class TriangleMesh, class Vpm>
std::size_t duplicate_non_manifold_vertices(TriangleMesh& tm, Vpm vpm)
{
  typedef boost::graph_traits<TriangleMesh> GT;
  typedef typename GT::vertex_descriptor vertex_descriptor;
  typedef typename GT::halfedge_descriptor halfedge_descriptor;

  boost::unordered_set<vertex_descriptor> vertices_handled;
  boost::unordered_set<halfedge_descriptor> halfedges_handled;

  std::size_t nb_new_vertices=0;

  std::vector<halfedge_descriptor> non_manifold_cones;
  BOOST_FOREACH(halfedge_descriptor h, halfedges(tm))
  {
    if (halfedges_handled.insert(h).second)
    {
      vertex_descriptor vd = target(h, tm);
      if ( !vertices_handled.insert(vd).second )
      {
        non_manifold_cones.push_back(h);
      }
      else
        set_halfedge(vd, h, tm);
      halfedge_descriptor start=opposite(next(h, tm), tm);
      h=start;
      do{
        halfedges_handled.insert(h);
        h=opposite(next(h, tm), tm);
      }while(h!=start);
    }
  }

  if (!non_manifold_cones.empty())  {
    BOOST_FOREACH(halfedge_descriptor h, non_manifold_cones)
    {
      halfedge_descriptor start = h;
      vertex_descriptor new_vd = add_vertex(tm);
      ++nb_new_vertices;
      put(vpm, new_vd, get(vpm, target(h, tm)));
      set_halfedge(new_vd, h, tm);
      do{
        set_target(h, new_vd, tm);
        h=opposite(next(h, tm), tm);
      } while(h!=start);
    }
  }

  return nb_new_vertices;

}



On 12/14/2017 08:57 AM, Sebastien Loriot (GeometryFactory) wrote:
OK let's try the following:

after
bool result = CGAL::Polygon_mesh_processing::corefine_and_compute_difference(mesh[je], mesh[ie], mesh[je]);

Add:
{
std::ofstream otmp("/tmp/out.off");
otmp << std::setprecision(17) << mesh[je];
otmp.close();
std::ifstream itmp("/tmp/out.off");
std::vector<Point_3> pts;
std::vector< CGAL::cpp11::array<int, 3> > polygons;
CGAL::read_OFF(itmp, pts,  polygons);
if (!CGAL::Polygon_mesh_processing::is_polygon_soup_a_polygon_mesh(polygons))
{
   std::cout << "BOOM!\n";
   exit(1);
}
}

Then send me with precision 17 mesh[je] and mesh[ie] before the call to the function.

Sebastien.

PS: I haven't try to compile it so it's up to typos...


On 12/14/2017 04:09 AM, Sean Hardesty wrote:
Thank you for your help! I am well aware of the difficulty of tracking these things down via e-mail...

I am using a source build of CGAL 4.11 because my Ubuntu distribution comes with 4.7. My program looks like this:

#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
#include <CGAL/Surface_mesh.h>

#include <CGAL/Polygon_mesh_processing/corefinement.h>

typedef CGAL::Exact_predicates_exact_constructions_kernel K;
typedef CGAL::Surface_mesh<K::Point_3> Mesh;

Skip some irrelevant code...

     // create cgal meshes

     std::vector<Mesh> mesh(ne);
     for(uint64_t ie=0;ie<ne;ie++) {
         foo.create_cgal_mesh(mesh[ie]);
     }

If I write them to .off files here, the Polyhedron demo does not say that any of them are polygon soups.

     // remove intersecting pieces

     for(uint64_t ie=0;ie<ne;ie++) {
         for(uint64_t je=ie+1;je<ne;je++) {

             bool result =
CGAL::Polygon_mesh_processing::corefine_and_compute_difference(mesh[je], mesh[ie], mesh[je]);

             if (!result) {
                 std::cout << "CGAL call returned false!" << std::endl;
                 exit(1);
             }
         }
     }

If I write to a .off file each time through the inner loop and load the results into the polyhedron demo, I see that at some point, several of them become polygon soups (this seems to be the case independent of the precision with which I write the .off files). However, the loop continues well past the point where this first occurs. There is a particular pair of meshes (the ones I sent previously) where the call to corefine_and_compute_difference either results in the assertion error I mentioned in my first message, or runs for an implausibly long time (I think the difference between these two behaviors may have been caused by an update to my system libraries).

Suspecting that the real problem occurred earlier, I went back to find the first place where the results of corefine_and_compute_difference became a polygon soup. My meshes have some (approximate) symmetry, so I end up with two cases that are nearly identical, but one creates the first polygon soup and the other does not. The output for these two cases I have attached to this message. The demo lets me orient the polygon soup (mesh4.off) as a surface mesh and says it's not directly orientable, resulting in duplicated vertices and self-intersections. When I try to run self-intersection test, the demo segfaults.

     Sincerely,
     Sean






On Wed, Dec 13, 2017 at 9:37 AM, Sebastien Loriot (GeometryFactory) <[hidden email] <mailto:[hidden email]>> wrote:

    If you have been able to build a Polyhedron or a Surface_mesh it means
    that it is not a polygon soup.

    I guess you do something different than just loading the two files
    posted. If you have a minimal example showing the pb it would help
    to tell you exactly what the pb is.

    Sebastien.

    On 12/13/2017 03:33 PM, Sean Hardesty wrote:

        I was able to compile the polyhedron demo and duplicate the
        results you described. However, I don't understand how I would
        test for this in my own program. I generated the .off files I
        sent from CGAL::Surface_mesh - how do I check whether such an
        object is a polygon soup (as is done in the demo)?

        All of the following look okay:

        mesh.is_valid() = 1
        CGAL::Polygon_mesh_processing::does_bound_a_volume(mesh) = 1
        CGAL::Polygon_mesh_processing::does_self_intersect(mesh) = 0
        CGAL::Polygon_mesh_processing::is_outward_oriented(mesh) = 1
        CGAL::is_closed(mesh) = 1

        I wanted to try something from the polygon soup example, like this

        CGAL::Polygon_mesh_processing::is_polygon_soup_a_polygon_mesh

        but I haven't been able to figure out how to call that on a
        CGAL::Surface_mesh object.

              Thanks,
              Sean Hardesty

        On Wed, Dec 6, 2017 at 2:24 AM, Sebastien Loriot
        (GeometryFactory) <[hidden email]
        <mailto:[hidden email]> <mailto:[hidden email]
        <mailto:[hidden email]>>> wrote:

             When I open you files in the CGAL polyhedron demo, it is
        telling me that
             your meshes are polygon soups (meaning you have
        non-manifold edges).
             If I duplicate those edges to make it a self-intersecting
        surface
             I have the following set of intersecting faces.

             Sebastien.

             On 12/05/2017 05:22 PM, Sean Hardesty wrote:

                 I have a collection of meshes that overlap slightly, so
        I am
                 going through a loop removing overlapping pieces. It
        works for a
                 while, but eventually I run into trouble. I am calling
                 PMP::corefine_and_compute_difference(CGAL 4.11) on a
        pair of
                 meshes that satisfy

                 !CGAL::Polygon_mesh_processing::does_self_intersect
                 CGAL::Polygon_mesh_processing::does_bound_a_volume

                 and I get the following:

                 terminate called after throwing an instance of
                 'CGAL::Assertion_exception'
                     what(): CGAL ERROR: assertion violation!
                 Expr: hedge!=start
                 File:
        /usr/local/include/CGAL/Polygon_mesh_processing/internal/Corefinement/Visitor.h
                 Line: 663
                 Aborted (core dumped)

                 They are fairly small, so I wrote them to .off format and
                 attached them to this message. I am aware from your
                 documentation pages that there can be problems with
        sequential
                 boolean operations, so I am using the kernel with exact
                 predicates and exact constructions. Maybe the precision
        in the
                 .off format is inadequate to diagnose the problem. I
        would be
                 grateful for any help that can be provided.

                       Sincerely,
                       Sean Hardesty


             --     You are currently subscribed to cgal-discuss.
             To unsubscribe or access the archives, go to
        https://sympa.inria.fr/sympa/info/cgal-discuss
        <https://sympa.inria.fr/sympa/info/cgal-discuss>
             <https://sympa.inria.fr/sympa/info/cgal-discuss
        <https://sympa.inria.fr/sympa/info/cgal-discuss>>




    --     You are currently subscribed to cgal-discuss.
    To unsubscribe or access the archives, go to
    https://sympa.inria.fr/sympa/info/cgal-discuss
    <https://sympa.inria.fr/sympa/info/cgal-discuss>




--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://sympa.inria.fr/sympa/info/cgal-discuss




mesh_j.off (35K) Download Attachment
mesh_i.off (35K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Polygon_mesh_processing::corefine_and_compute_difference

Konstantinos Katrioplas

Dear Sean,

PMP's corefine_and_compute_difference probably fails because there are self intersections in both meshes in the attached files. Maybe you could try removing them first using the functionality that is offered by PMP's repair.h file. You would need to include the header,

 #include <CGAL/Polygon_mesh_processing/repair.h>

and then add to your code something like that:

  PMP::remove_self_intersections(mesh_i);
  PMP::remove_self_intersections(mesh_j);
  PMP::corefine_and_compute_difference(mesh_i, mesh_j, mesh_out);

However, since repair.h is under development, please try this with version 4.12.

Regards,
Konstantinos


On 05/20/2018 09:29 PM, Sean Hardesty wrote:
Sebastien,

Back in December, you sent a function duplicate_non_manifold_vertices to be used prior to calling keep_largest_connected_components. It has mostly worked fine, but I have just recently stumbled across a case where it fails quickly and consistently: CGAL 4.11 segfaults (same thing with 4.11.1, 4.12) in the call to CGAL::Polygon_mesh_processing::corefine_and_compute_difference. I have attached .off files that were written immediately prior to the call where it segfaults. They aren't polygon soups, but they do have problems - looks like triangles are hanging off the corners, and weren't removed by prior calls to duplicate_non_manifold_vertices and keep_largest_connected_components. Do you have any suggestions about how to fix it?

    Thanks,
    Sean Hardesty



On Fri, Dec 15, 2017 at 2:02 AM, Sebastien Loriot (GeometryFactory) <[hidden email]> wrote:
Thanks Sean for sending the files.
You are actually hitting a known issue that I'll officially fix soon.

In the meantime here is what is going on and how to fix it:

The boolean operation is creating a non-manifold vertex (2 mesh parts connected by a vertex in your case). I'm pretty sure from your data
that you'd like to discard the small part.

In order to do that, you can call the following function that will
duplicate all non-manifold vertices:

std::size_t nb_dv=duplicate_non_manifold_vertices(mesh[je], get(CGAL::vertex_point, mesh_je));

Then you should end-up with 2 connected components
you can filter with the following:

if (nb_dv!=0)
  PMP::keep_largest_connected_components(mesh[je], 1);

Sorry for the inconvenience.

Sebastien.

template <class TriangleMesh, class Vpm>
std::size_t duplicate_non_manifold_vertices(TriangleMesh& tm, Vpm vpm)
{
  typedef boost::graph_traits<TriangleMesh> GT;
  typedef typename GT::vertex_descriptor vertex_descriptor;
  typedef typename GT::halfedge_descriptor halfedge_descriptor;

  boost::unordered_set<vertex_descriptor> vertices_handled;
  boost::unordered_set<halfedge_descriptor> halfedges_handled;

  std::size_t nb_new_vertices=0;

  std::vector<halfedge_descriptor> non_manifold_cones;
  BOOST_FOREACH(halfedge_descriptor h, halfedges(tm))
  {
    if (halfedges_handled.insert(h).second)
    {
      vertex_descriptor vd = target(h, tm);
      if ( !vertices_handled.insert(vd).second )
      {
        non_manifold_cones.push_back(h);
      }
      else
        set_halfedge(vd, h, tm);
      halfedge_descriptor start=opposite(next(h, tm), tm);
      h=start;
      do{
        halfedges_handled.insert(h);
        h=opposite(next(h, tm), tm);
      }while(h!=start);
    }
  }

  if (!non_manifold_cones.empty())  {
    BOOST_FOREACH(halfedge_descriptor h, non_manifold_cones)
    {
      halfedge_descriptor start = h;
      vertex_descriptor new_vd = add_vertex(tm);
      ++nb_new_vertices;
      put(vpm, new_vd, get(vpm, target(h, tm)));
      set_halfedge(new_vd, h, tm);
      do{
        set_target(h, new_vd, tm);
        h=opposite(next(h, tm), tm);
      } while(h!=start);
    }
  }

  return nb_new_vertices;

}



On 12/14/2017 08:57 AM, Sebastien Loriot (GeometryFactory) wrote:
OK let's try the following:

after
bool result = CGAL::Polygon_mesh_processing::corefine_and_compute_difference(mesh[je], mesh[ie], mesh[je]);

Add:
{
std::ofstream otmp("/tmp/out.off");
otmp << std::setprecision(17) << mesh[je];
otmp.close();
std::ifstream itmp("/tmp/out.off");
std::vector<Point_3> pts;
std::vector< CGAL::cpp11::array<int, 3> > polygons;
CGAL::read_OFF(itmp, pts,  polygons);
if (!CGAL::Polygon_mesh_processing::is_polygon_soup_a_polygon_mesh(polygons))
{
   std::cout << "BOOM!\n";
   exit(1);
}
}

Then send me with precision 17 mesh[je] and mesh[ie] before the call to the function.

Sebastien.

PS: I haven't try to compile it so it's up to typos...


On 12/14/2017 04:09 AM, Sean Hardesty wrote:
Thank you for your help! I am well aware of the difficulty of tracking these things down via e-mail...

I am using a source build of CGAL 4.11 because my Ubuntu distribution comes with 4.7. My program looks like this:

#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
#include <CGAL/Surface_mesh.h>

#include <CGAL/Polygon_mesh_processing/corefinement.h>

typedef CGAL::Exact_predicates_exact_constructions_kernel K;
typedef CGAL::Surface_mesh<K::Point_3> Mesh;

Skip some irrelevant code...

     // create cgal meshes

     std::vector<Mesh> mesh(ne);
     for(uint64_t ie=0;ie<ne;ie++) {
         foo.create_cgal_mesh(mesh[ie]);
     }

If I write them to .off files here, the Polyhedron demo does not say that any of them are polygon soups.

     // remove intersecting pieces

     for(uint64_t ie=0;ie<ne;ie++) {
         for(uint64_t je=ie+1;je<ne;je++) {

             bool result =
CGAL::Polygon_mesh_processing::corefine_and_compute_difference(mesh[je], mesh[ie], mesh[je]);

             if (!result) {
                 std::cout << "CGAL call returned false!" << std::endl;
                 exit(1);
             }
         }
     }

If I write to a .off file each time through the inner loop and load the results into the polyhedron demo, I see that at some point, several of them become polygon soups (this seems to be the case independent of the precision with which I write the .off files). However, the loop continues well past the point where this first occurs. There is a particular pair of meshes (the ones I sent previously) where the call to corefine_and_compute_difference either results in the assertion error I mentioned in my first message, or runs for an implausibly long time (I think the difference between these two behaviors may have been caused by an update to my system libraries).

Suspecting that the real problem occurred earlier, I went back to find the first place where the results of corefine_and_compute_difference became a polygon soup. My meshes have some (approximate) symmetry, so I end up with two cases that are nearly identical, but one creates the first polygon soup and the other does not. The output for these two cases I have attached to this message. The demo lets me orient the polygon soup (mesh4.off) as a surface mesh and says it's not directly orientable, resulting in duplicated vertices and self-intersections. When I try to run self-intersection test, the demo segfaults.

     Sincerely,
     Sean






On Wed, Dec 13, 2017 at 9:37 AM, Sebastien Loriot (GeometryFactory) <[hidden email] <mailto:[hidden email]>> wrote:

    If you have been able to build a Polyhedron or a Surface_mesh it means
    that it is not a polygon soup.

    I guess you do something different than just loading the two files
    posted. If you have a minimal example showing the pb it would help
    to tell you exactly what the pb is.

    Sebastien.

    On 12/13/2017 03:33 PM, Sean Hardesty wrote:

        I was able to compile the polyhedron demo and duplicate the
        results you described. However, I don't understand how I would
        test for this in my own program. I generated the .off files I
        sent from CGAL::Surface_mesh - how do I check whether such an
        object is a polygon soup (as is done in the demo)?

        All of the following look okay:

        mesh.is_valid() = 1
        CGAL::Polygon_mesh_processing::does_bound_a_volume(mesh) = 1
        CGAL::Polygon_mesh_processing::does_self_intersect(mesh) = 0
        CGAL::Polygon_mesh_processing::is_outward_oriented(mesh) = 1
        CGAL::is_closed(mesh) = 1

        I wanted to try something from the polygon soup example, like this

        CGAL::Polygon_mesh_processing::is_polygon_soup_a_polygon_mesh

        but I haven't been able to figure out how to call that on a
        CGAL::Surface_mesh object.

              Thanks,
              Sean Hardesty

        On Wed, Dec 6, 2017 at 2:24 AM, Sebastien Loriot
        (GeometryFactory) <[hidden email]
        <mailto:[hidden email]> <mailto:[hidden email]
        <mailto:[hidden email]>>> wrote:

             When I open you files in the CGAL polyhedron demo, it is
        telling me that
             your meshes are polygon soups (meaning you have
        non-manifold edges).
             If I duplicate those edges to make it a self-intersecting
        surface
             I have the following set of intersecting faces.

             Sebastien.

             On 12/05/2017 05:22 PM, Sean Hardesty wrote:

                 I have a collection of meshes that overlap slightly, so
        I am
                 going through a loop removing overlapping pieces. It
        works for a
                 while, but eventually I run into trouble. I am calling
                 PMP::corefine_and_compute_difference(CGAL 4.11) on a
        pair of
                 meshes that satisfy

                 !CGAL::Polygon_mesh_processing::does_self_intersect
                 CGAL::Polygon_mesh_processing::does_bound_a_volume

                 and I get the following:

                 terminate called after throwing an instance of
                 'CGAL::Assertion_exception'
                     what(): CGAL ERROR: assertion violation!
                 Expr: hedge!=start
                 File:
        /usr/local/include/CGAL/Polygon_mesh_processing/internal/Corefinement/Visitor.h
                 Line: 663
                 Aborted (core dumped)

                 They are fairly small, so I wrote them to .off format and
                 attached them to this message. I am aware from your
                 documentation pages that there can be problems with
        sequential
                 boolean operations, so I am using the kernel with exact
                 predicates and exact constructions. Maybe the precision
        in the
                 .off format is inadequate to diagnose the problem. I
        would be
                 grateful for any help that can be provided.

                       Sincerely,
                       Sean Hardesty


             --     You are currently subscribed to cgal-discuss.
             To unsubscribe or access the archives, go to
        https://sympa.inria.fr/sympa/info/cgal-discuss
        <https://sympa.inria.fr/sympa/info/cgal-discuss>
             <https://sympa.inria.fr/sympa/info/cgal-discuss
        <https://sympa.inria.fr/sympa/info/cgal-discuss>>




    --     You are currently subscribed to cgal-discuss.
    To unsubscribe or access the archives, go to
    https://sympa.inria.fr/sympa/info/cgal-discuss
    <https://sympa.inria.fr/sympa/info/cgal-discuss>




--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://sympa.inria.fr/sympa/info/cgal-discuss




Reply | Threaded
Open this post in threaded view
|

Re: Polygon_mesh_processing::corefine_and_compute_difference

Sean Hardesty
Thank you, Konstantinos! Your suggestion solved my problem.

On Wed, May 23, 2018 at 2:37 AM, Konstantinos Katrioplas <[hidden email]> wrote:

Dear Sean,

PMP's corefine_and_compute_difference probably fails because there are self intersections in both meshes in the attached files. Maybe you could try removing them first using the functionality that is offered by PMP's repair.h file. You would need to include the header,

 #include <CGAL/Polygon_mesh_processing/repair.h>

and then add to your code something like that:

  PMP::remove_self_intersections(mesh_i);
  PMP::remove_self_intersections(mesh_j);
  PMP::corefine_and_compute_difference(mesh_i, mesh_j, mesh_out);

However, since repair.h is under development, please try this with version 4.12.

Regards,
Konstantinos


On 05/20/2018 09:29 PM, Sean Hardesty wrote:
Sebastien,

Back in December, you sent a function duplicate_non_manifold_vertices to be used prior to calling keep_largest_connected_components. It has mostly worked fine, but I have just recently stumbled across a case where it fails quickly and consistently: CGAL 4.11 segfaults (same thing with 4.11.1, 4.12) in the call to CGAL::Polygon_mesh_processing::corefine_and_compute_difference. I have attached .off files that were written immediately prior to the call where it segfaults. They aren't polygon soups, but they do have problems - looks like triangles are hanging off the corners, and weren't removed by prior calls to duplicate_non_manifold_vertices and keep_largest_connected_components. Do you have any suggestions about how to fix it?

    Thanks,
    Sean Hardesty



On Fri, Dec 15, 2017 at 2:02 AM, Sebastien Loriot (GeometryFactory) <[hidden email]> wrote:
Thanks Sean for sending the files.
You are actually hitting a known issue that I'll officially fix soon.

In the meantime here is what is going on and how to fix it:

The boolean operation is creating a non-manifold vertex (2 mesh parts connected by a vertex in your case). I'm pretty sure from your data
that you'd like to discard the small part.

In order to do that, you can call the following function that will
duplicate all non-manifold vertices:

std::size_t nb_dv=duplicate_non_manifold_vertices(mesh[je], get(CGAL::vertex_point, mesh_je));

Then you should end-up with 2 connected components
you can filter with the following:

if (nb_dv!=0)
  PMP::keep_largest_connected_components(mesh[je], 1);

Sorry for the inconvenience.

Sebastien.

template <class TriangleMesh, class Vpm>
std::size_t duplicate_non_manifold_vertices(TriangleMesh& tm, Vpm vpm)
{
  typedef boost::graph_traits<TriangleMesh> GT;
  typedef typename GT::vertex_descriptor vertex_descriptor;
  typedef typename GT::halfedge_descriptor halfedge_descriptor;

  boost::unordered_set<vertex_descriptor> vertices_handled;
  boost::unordered_set<halfedge_descriptor> halfedges_handled;

  std::size_t nb_new_vertices=0;

  std::vector<halfedge_descriptor> non_manifold_cones;
  BOOST_FOREACH(halfedge_descriptor h, halfedges(tm))
  {
    if (halfedges_handled.insert(h).second)
    {
      vertex_descriptor vd = target(h, tm);
      if ( !vertices_handled.insert(vd).second )
      {
        non_manifold_cones.push_back(h);
      }
      else
        set_halfedge(vd, h, tm);
      halfedge_descriptor start=opposite(next(h, tm), tm);
      h=start;
      do{
        halfedges_handled.insert(h);
        h=opposite(next(h, tm), tm);
      }while(h!=start);
    }
  }

  if (!non_manifold_cones.empty())  {
    BOOST_FOREACH(halfedge_descriptor h, non_manifold_cones)
    {
      halfedge_descriptor start = h;
      vertex_descriptor new_vd = add_vertex(tm);
      ++nb_new_vertices;
      put(vpm, new_vd, get(vpm, target(h, tm)));
      set_halfedge(new_vd, h, tm);
      do{
        set_target(h, new_vd, tm);
        h=opposite(next(h, tm), tm);
      } while(h!=start);
    }
  }

  return nb_new_vertices;

}



On 12/14/2017 08:57 AM, Sebastien Loriot (GeometryFactory) wrote:
OK let's try the following:

after
bool result = CGAL::Polygon_mesh_processing::corefine_and_compute_difference(mesh[je], mesh[ie], mesh[je]);

Add:
{
std::ofstream otmp("/tmp/out.off");
otmp << std::setprecision(17) << mesh[je];
otmp.close();
std::ifstream itmp("/tmp/out.off");
std::vector<Point_3> pts;
std::vector< CGAL::cpp11::array<int, 3> > polygons;
CGAL::read_OFF(itmp, pts,  polygons);
if (!CGAL::Polygon_mesh_processing::is_polygon_soup_a_polygon_mesh(polygons))
{
   std::cout << "BOOM!\n";
   exit(1);
}
}

Then send me with precision 17 mesh[je] and mesh[ie] before the call to the function.

Sebastien.

PS: I haven't try to compile it so it's up to typos...


On 12/14/2017 04:09 AM, Sean Hardesty wrote:
Thank you for your help! I am well aware of the difficulty of tracking these things down via e-mail...

I am using a source build of CGAL 4.11 because my Ubuntu distribution comes with 4.7. My program looks like this:

#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
#include <CGAL/Surface_mesh.h>

#include <CGAL/Polygon_mesh_processing/corefinement.h>

typedef CGAL::Exact_predicates_exact_constructions_kernel K;
typedef CGAL::Surface_mesh<K::Point_3> Mesh;

Skip some irrelevant code...

     // create cgal meshes

     std::vector<Mesh> mesh(ne);
     for(uint64_t ie=0;ie<ne;ie++) {
         foo.create_cgal_mesh(mesh[ie]);
     }

If I write them to .off files here, the Polyhedron demo does not say that any of them are polygon soups.

     // remove intersecting pieces

     for(uint64_t ie=0;ie<ne;ie++) {
         for(uint64_t je=ie+1;je<ne;je++) {

             bool result =
CGAL::Polygon_mesh_processing::corefine_and_compute_difference(mesh[je], mesh[ie], mesh[je]);

             if (!result) {
                 std::cout << "CGAL call returned false!" << std::endl;
                 exit(1);
             }
         }
     }

If I write to a .off file each time through the inner loop and load the results into the polyhedron demo, I see that at some point, several of them become polygon soups (this seems to be the case independent of the precision with which I write the .off files). However, the loop continues well past the point where this first occurs. There is a particular pair of meshes (the ones I sent previously) where the call to corefine_and_compute_difference either results in the assertion error I mentioned in my first message, or runs for an implausibly long time (I think the difference between these two behaviors may have been caused by an update to my system libraries).

Suspecting that the real problem occurred earlier, I went back to find the first place where the results of corefine_and_compute_difference became a polygon soup. My meshes have some (approximate) symmetry, so I end up with two cases that are nearly identical, but one creates the first polygon soup and the other does not. The output for these two cases I have attached to this message. The demo lets me orient the polygon soup (mesh4.off) as a surface mesh and says it's not directly orientable, resulting in duplicated vertices and self-intersections. When I try to run self-intersection test, the demo segfaults.

     Sincerely,
     Sean






On Wed, Dec 13, 2017 at 9:37 AM, Sebastien Loriot (GeometryFactory) <[hidden email] <mailto:[hidden email]>> wrote:

    If you have been able to build a Polyhedron or a Surface_mesh it means
    that it is not a polygon soup.

    I guess you do something different than just loading the two files
    posted. If you have a minimal example showing the pb it would help
    to tell you exactly what the pb is.

    Sebastien.

    On 12/13/2017 03:33 PM, Sean Hardesty wrote:

        I was able to compile the polyhedron demo and duplicate the
        results you described. However, I don't understand how I would
        test for this in my own program. I generated the .off files I
        sent from CGAL::Surface_mesh - how do I check whether such an
        object is a polygon soup (as is done in the demo)?

        All of the following look okay:

        mesh.is_valid() = 1
        CGAL::Polygon_mesh_processing::does_bound_a_volume(mesh) = 1
        CGAL::Polygon_mesh_processing::does_self_intersect(mesh) = 0
        CGAL::Polygon_mesh_processing::is_outward_oriented(mesh) = 1
        CGAL::is_closed(mesh) = 1

        I wanted to try something from the polygon soup example, like this

        CGAL::Polygon_mesh_processing::is_polygon_soup_a_polygon_mesh

        but I haven't been able to figure out how to call that on a
        CGAL::Surface_mesh object.

              Thanks,
              Sean Hardesty

        On Wed, Dec 6, 2017 at 2:24 AM, Sebastien Loriot
        (GeometryFactory) <[hidden email]
        <mailto:[hidden email]> <mailto:[hidden email]
        <mailto:[hidden email]>>> wrote:

             When I open you files in the CGAL polyhedron demo, it is
        telling me that
             your meshes are polygon soups (meaning you have
        non-manifold edges).
             If I duplicate those edges to make it a self-intersecting
        surface
             I have the following set of intersecting faces.

             Sebastien.

             On 12/05/2017 05:22 PM, Sean Hardesty wrote:

                 I have a collection of meshes that overlap slightly, so
        I am
                 going through a loop removing overlapping pieces. It
        works for a
                 while, but eventually I run into trouble. I am calling
                 PMP::corefine_and_compute_difference(CGAL 4.11) on a
        pair of
                 meshes that satisfy

                 !CGAL::Polygon_mesh_processing::does_self_intersect
                 CGAL::Polygon_mesh_processing::does_bound_a_volume

                 and I get the following:

                 terminate called after throwing an instance of
                 'CGAL::Assertion_exception'
                     what(): CGAL ERROR: assertion violation!
                 Expr: hedge!=start
                 File:
        /usr/local/include/CGAL/Polygon_mesh_processing/internal/Corefinement/Visitor.h
                 Line: 663
                 Aborted (core dumped)

                 They are fairly small, so I wrote them to .off format and
                 attached them to this message. I am aware from your
                 documentation pages that there can be problems with
        sequential
                 boolean operations, so I am using the kernel with exact
                 predicates and exact constructions. Maybe the precision
        in the
                 .off format is inadequate to diagnose the problem. I
        would be
                 grateful for any help that can be provided.

                       Sincerely,
                       Sean Hardesty


             --     You are currently subscribed to cgal-discuss.
             To unsubscribe or access the archives, go to
        https://sympa.inria.fr/sympa/info/cgal-discuss
        <https://sympa.inria.fr/sympa/info/cgal-discuss>
             <https://sympa.inria.fr/sympa/info/cgal-discuss
        <https://sympa.inria.fr/sympa/info/cgal-discuss>>




    --     You are currently subscribed to cgal-discuss.
    To unsubscribe or access the archives, go to
    https://sympa.inria.fr/sympa/info/cgal-discuss
    <https://sympa.inria.fr/sympa/info/cgal-discuss>




--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://sympa.inria.fr/sympa/info/cgal-discuss