Infinite loop in PMP::corefine_and_compute_union since 4.14.2

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

Infinite loop in PMP::corefine_and_compute_union since 4.14.2

Giles Puckett
Bonjour,

I have a CAD program that uses PMP to merge meshes. I moved from 4.12 to
5.0 in order to use the default visitor to keep attributes on faces
through surface mesh unions. However, some previously working meshes now
fail with an infinite loop. The problem also appears on 4.14.2.

The infinite loop is in Corefinement::remove_unused_polylines at
face_graph_utils.h, line 1634: (in 5.0)

for(vertex_descriptor v: vertices_kept)
   {
     halfedge_descriptor h = halfedge(v, tm), start=GT::null_halfedge();

     do{
       while ( !is_border(h, tm) || is_border(opposite(h, tm), tm) )  
// This while loop never exits
         h = opposite(next(h, tm), tm);
       halfedge_descriptor in = h;
       if (start==GT::null_halfedge())
         start=in;
       else
         if (start==in)
           break;
       while ( is_border(h, tm) )
         h = opposite(next(h, tm), tm);
       set_next(in, opposite(h, tm), tm);
     }
     while(true);//this loop handles non-manifold vertices
   }

One mesh is a simple convex shape, the other is the result of a previous
union. All unions are done with exact predicates and constructions in
the standard way for consecutive bool ops. Testing for
self-intersections before and during the union reveals nothing.

Sadly, I cannot reproduce it in a simple test example program (when
writing the meshes to OFF file, precision is lost, and I get
self-intersections or an assertion about collinear points). I suspect
there may be zero-area triangles produced by the first union.

Three questions:

Have there been any changes in corefinement, PMP or surface meshes
between 4.12 and 4.14.2 that might produce this, or any known regressions?
And is there any way I can write the meshes out with sufficient accuracy
to submit a simple test case?
Lastly, is there any way I can get the functionality of the example
program (corefinement_mesh_union_with_attributes) to work in 4.12?

Thanks for any help and for reading on this far :-)

Giles.



--
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: Infinite loop in PMP::corefine_and_compute_union since 4.14.2

Sebastien Loriot (GeometryFactory)
Does one of you mesh has a boundary?

The list of PRs that could have introduced a regression is here:
https://github.com/CGAL/cgal/pulls?utf8=%E2%9C%93&q=is%3Apr+is%3Aclosed+label%3AMerged_in_4.12.2++label%3APkg%3A%3APMP+

I don't see anything suspicious. Is it deterministic?

Best,

Sebastien.



On 2/4/20 11:59 PM, Giles Puckett wrote:

> Bonjour,
>
> I have a CAD program that uses PMP to merge meshes. I moved from 4.12 to
> 5.0 in order to use the default visitor to keep attributes on faces
> through surface mesh unions. However, some previously working meshes now
> fail with an infinite loop. The problem also appears on 4.14.2.
>
> The infinite loop is in Corefinement::remove_unused_polylines at
> face_graph_utils.h, line 1634: (in 5.0)
>
> for(vertex_descriptor v: vertices_kept)
>    {
>      halfedge_descriptor h = halfedge(v, tm), start=GT::null_halfedge();
>
>      do{
>        while ( !is_border(h, tm) || is_border(opposite(h, tm), tm) ) //
> This while loop never exits
>          h = opposite(next(h, tm), tm);
>        halfedge_descriptor in = h;
>        if (start==GT::null_halfedge())
>          start=in;
>        else
>          if (start==in)
>            break;
>        while ( is_border(h, tm) )
>          h = opposite(next(h, tm), tm);
>        set_next(in, opposite(h, tm), tm);
>      }
>      while(true);//this loop handles non-manifold vertices
>    }
>
> One mesh is a simple convex shape, the other is the result of a previous
> union. All unions are done with exact predicates and constructions in
> the standard way for consecutive bool ops. Testing for
> self-intersections before and during the union reveals nothing.
>
> Sadly, I cannot reproduce it in a simple test example program (when
> writing the meshes to OFF file, precision is lost, and I get
> self-intersections or an assertion about collinear points). I suspect
> there may be zero-area triangles produced by the first union.
>
> Three questions:
>
> Have there been any changes in corefinement, PMP or surface meshes
> between 4.12 and 4.14.2 that might produce this, or any known regressions?
> And is there any way I can write the meshes out with sufficient accuracy
> to submit a simple test case?
> Lastly, is there any way I can get the functionality of the example
> program (corefinement_mesh_union_with_attributes) to work in 4.12?
>
> Thanks for any help and for reading on this far :-)
>
> Giles.
>
>
>

--
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: Infinite loop in PMP::corefine_and_compute_union since 4.14.2

Giles Puckett
Both meshes return true to does_bound_a_volume and false to
does_self_intersect. They do not throw an exception for
self-intersections. I can send the OFF files if you like, although they
don't produce the error they show the shape of the meshes..

G.

On 5/02/2020 6:23 pm, Sebastien Loriot (GeometryFactory) wrote:

> Does one of you mesh has a boundary?
>
> The list of PRs that could have introduced a regression is here:
> https://github.com/CGAL/cgal/pulls?utf8=%E2%9C%93&q=is%3Apr+is%3Aclosed+label%3AMerged_in_4.12.2++label%3APkg%3A%3APMP+ 
>
>
> I don't see anything suspicious. Is it deterministic?
>
> Best,
>
> Sebastien.
>
>
>
> On 2/4/20 11:59 PM, Giles Puckett wrote:
>> Bonjour,
>>
>> I have a CAD program that uses PMP to merge meshes. I moved from 4.12
>> to 5.0 in order to use the default visitor to keep attributes on
>> faces through surface mesh unions. However, some previously working
>> meshes now fail with an infinite loop. The problem also appears on
>> 4.14.2.
>>
>> The infinite loop is in Corefinement::remove_unused_polylines at
>> face_graph_utils.h, line 1634: (in 5.0)
>>
>> for(vertex_descriptor v: vertices_kept)
>>    {
>>      halfedge_descriptor h = halfedge(v, tm), start=GT::null_halfedge();
>>
>>      do{
>>        while ( !is_border(h, tm) || is_border(opposite(h, tm), tm) )
>> // This while loop never exits
>>          h = opposite(next(h, tm), tm);
>>        halfedge_descriptor in = h;
>>        if (start==GT::null_halfedge())
>>          start=in;
>>        else
>>          if (start==in)
>>            break;
>>        while ( is_border(h, tm) )
>>          h = opposite(next(h, tm), tm);
>>        set_next(in, opposite(h, tm), tm);
>>      }
>>      while(true);//this loop handles non-manifold vertices
>>    }
>>
>> One mesh is a simple convex shape, the other is the result of a
>> previous union. All unions are done with exact predicates and
>> constructions in the standard way for consecutive bool ops. Testing
>> for self-intersections before and during the union reveals nothing.
>>
>> Sadly, I cannot reproduce it in a simple test example program (when
>> writing the meshes to OFF file, precision is lost, and I get
>> self-intersections or an assertion about collinear points). I suspect
>> there may be zero-area triangles produced by the first union.
>>
>> Three questions:
>>
>> Have there been any changes in corefinement, PMP or surface meshes
>> between 4.12 and 4.14.2 that might produce this, or any known
>> regressions?
>> And is there any way I can write the meshes out with sufficient
>> accuracy to submit a simple test case?
>> Lastly, is there any way I can get the functionality of the example
>> program (corefinement_mesh_union_with_attributes) to work in 4.12?
>>
>> Thanks for any help and for reading on this far :-)
>>
>> Giles.
>>
>>
>>
>

--
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: Infinite loop in PMP::corefine_and_compute_union since 4.14.2

Sebastien Loriot (GeometryFactory)
If the error occurs after several operations, for debugging purpose you
can use CGAL::Simple_cartesian<CGAL::Gmpq> as kernel and I think when
writing to OFF you will write the exact rational representation.
Then I think I should be able to load them and reproduce the error.

Note that it will be much slower.

Best,

Sebastien.

PS: don't post output meshes as an attachment to the mailing list as
the file will be large (use gist.github.com or whatever online storage
service).


On 2/5/20 10:33 AM, Giles Puckett wrote:

> Both meshes return true to does_bound_a_volume and false to
> does_self_intersect. They do not throw an exception for
> self-intersections. I can send the OFF files if you like, although they
> don't produce the error they show the shape of the meshes..
>
> G.
>
> On 5/02/2020 6:23 pm, Sebastien Loriot (GeometryFactory) wrote:
>> Does one of you mesh has a boundary?
>>
>> The list of PRs that could have introduced a regression is here:
>> https://github.com/CGAL/cgal/pulls?utf8=%E2%9C%93&q=is%3Apr+is%3Aclosed+label%3AMerged_in_4.12.2++label%3APkg%3A%3APMP+ 
>>
>>
>> I don't see anything suspicious. Is it deterministic?
>>
>> Best,
>>
>> Sebastien.
>>
>>
>>
>> On 2/4/20 11:59 PM, Giles Puckett wrote:
>>> Bonjour,
>>>
>>> I have a CAD program that uses PMP to merge meshes. I moved from 4.12
>>> to 5.0 in order to use the default visitor to keep attributes on
>>> faces through surface mesh unions. However, some previously working
>>> meshes now fail with an infinite loop. The problem also appears on
>>> 4.14.2.
>>>
>>> The infinite loop is in Corefinement::remove_unused_polylines at
>>> face_graph_utils.h, line 1634: (in 5.0)
>>>
>>> for(vertex_descriptor v: vertices_kept)
>>>    {
>>>      halfedge_descriptor h = halfedge(v, tm), start=GT::null_halfedge();
>>>
>>>      do{
>>>        while ( !is_border(h, tm) || is_border(opposite(h, tm), tm) )
>>> // This while loop never exits
>>>          h = opposite(next(h, tm), tm);
>>>        halfedge_descriptor in = h;
>>>        if (start==GT::null_halfedge())
>>>          start=in;
>>>        else
>>>          if (start==in)
>>>            break;
>>>        while ( is_border(h, tm) )
>>>          h = opposite(next(h, tm), tm);
>>>        set_next(in, opposite(h, tm), tm);
>>>      }
>>>      while(true);//this loop handles non-manifold vertices
>>>    }
>>>
>>> One mesh is a simple convex shape, the other is the result of a
>>> previous union. All unions are done with exact predicates and
>>> constructions in the standard way for consecutive bool ops. Testing
>>> for self-intersections before and during the union reveals nothing.
>>>
>>> Sadly, I cannot reproduce it in a simple test example program (when
>>> writing the meshes to OFF file, precision is lost, and I get
>>> self-intersections or an assertion about collinear points). I suspect
>>> there may be zero-area triangles produced by the first union.
>>>
>>> Three questions:
>>>
>>> Have there been any changes in corefinement, PMP or surface meshes
>>> between 4.12 and 4.14.2 that might produce this, or any known
>>> regressions?
>>> And is there any way I can write the meshes out with sufficient
>>> accuracy to submit a simple test case?
>>> Lastly, is there any way I can get the functionality of the example
>>> program (corefinement_mesh_union_with_attributes) to work in 4.12?
>>>
>>> Thanks for any help and for reading on this far :-)
>>>
>>> Giles.
>>>
>>>
>>>
>>
>

--
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: Infinite loop in PMP::corefine_and_compute_union since 4.14.2

Giles Puckett
Hi,

Thanks for the suggestion. Can you post a fragment of such an OFF file
so I can see what it looks like?

It will be hard to change the kernel in the original program, because
there are a few steps between the mesh and the OFF file writing. But I
should be able to dig through the exact_points property map per vertex
and get out the exact coordinates.

What format are the coordinate values in the
Exact_predicates_exact_constructions_kernel ? (I confess I'm not very
good with C++ especially with all the heavy template usage)

G.

On 6/02/2020 6:20 pm, Sebastien Loriot (GeometryFactory) wrote:

> If the error occurs after several operations, for debugging purpose
> you can use CGAL::Simple_cartesian<CGAL::Gmpq> as kernel and I think when
> writing to OFF you will write the exact rational representation.
> Then I think I should be able to load them and reproduce the error.
>
> Note that it will be much slower.
>
> Best,
>
> Sebastien.
>
> PS: don't post output meshes as an attachment to the mailing list as
> the file will be large (use gist.github.com or whatever online storage
> service).
>
>
> On 2/5/20 10:33 AM, Giles Puckett wrote:
>> Both meshes return true to does_bound_a_volume and false to
>> does_self_intersect. They do not throw an exception for
>> self-intersections. I can send the OFF files if you like, although
>> they don't produce the error they show the shape of the meshes..
>>
>> G.
>>
>> On 5/02/2020 6:23 pm, Sebastien Loriot (GeometryFactory) wrote:
>>> Does one of you mesh has a boundary?
>>>
>>> The list of PRs that could have introduced a regression is here:
>>> https://github.com/CGAL/cgal/pulls?utf8=%E2%9C%93&q=is%3Apr+is%3Aclosed+label%3AMerged_in_4.12.2++label%3APkg%3A%3APMP+ 
>>>
>>>
>>> I don't see anything suspicious. Is it deterministic?
>>>
>>> Best,
>>>
>>> Sebastien.
>>>
>>>
>>>
>>> On 2/4/20 11:59 PM, Giles Puckett wrote:
>>>> Bonjour,
>>>>
>>>> I have a CAD program that uses PMP to merge meshes. I moved from
>>>> 4.12 to 5.0 in order to use the default visitor to keep attributes
>>>> on faces through surface mesh unions. However, some previously
>>>> working meshes now fail with an infinite loop. The problem also
>>>> appears on 4.14.2.
>>>>
>>>> The infinite loop is in Corefinement::remove_unused_polylines at
>>>> face_graph_utils.h, line 1634: (in 5.0)
>>>>
>>>> for(vertex_descriptor v: vertices_kept)
>>>>    {
>>>>      halfedge_descriptor h = halfedge(v, tm),
>>>> start=GT::null_halfedge();
>>>>
>>>>      do{
>>>>        while ( !is_border(h, tm) || is_border(opposite(h, tm), tm)
>>>> ) // This while loop never exits
>>>>          h = opposite(next(h, tm), tm);
>>>>        halfedge_descriptor in = h;
>>>>        if (start==GT::null_halfedge())
>>>>          start=in;
>>>>        else
>>>>          if (start==in)
>>>>            break;
>>>>        while ( is_border(h, tm) )
>>>>          h = opposite(next(h, tm), tm);
>>>>        set_next(in, opposite(h, tm), tm);
>>>>      }
>>>>      while(true);//this loop handles non-manifold vertices
>>>>    }
>>>>
>>>> One mesh is a simple convex shape, the other is the result of a
>>>> previous union. All unions are done with exact predicates and
>>>> constructions in the standard way for consecutive bool ops. Testing
>>>> for self-intersections before and during the union reveals nothing.
>>>>
>>>> Sadly, I cannot reproduce it in a simple test example program (when
>>>> writing the meshes to OFF file, precision is lost, and I get
>>>> self-intersections or an assertion about collinear points). I
>>>> suspect there may be zero-area triangles produced by the first union.
>>>>
>>>> Three questions:
>>>>
>>>> Have there been any changes in corefinement, PMP or surface meshes
>>>> between 4.12 and 4.14.2 that might produce this, or any known
>>>> regressions?
>>>> And is there any way I can write the meshes out with sufficient
>>>> accuracy to submit a simple test case?
>>>> Lastly, is there any way I can get the functionality of the example
>>>> program (corefinement_mesh_union_with_attributes) to work in 4.12?
>>>>
>>>> Thanks for any help and for reading on this far :-)
>>>>
>>>> Giles.
>>>>
>>>>
>>>>
>>>
>>
>

--
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: Infinite loop in PMP::corefine_and_compute_union since 4.14.2

Giles Puckett
In reply to this post by Sebastien Loriot (GeometryFactory)
Hi Sebastien,

I have reproduced the problem by writing OFF files in double precision
(previously they were only in 7-digit float).

The files are here:

https://www.dropbox.com/sh/0q1i263zkjjjv3o/AAAz27BUXGYUBqRGZDnTi_v3a?dl=0

I built on Windows 10 using Visual Studio 2019 (tool set 1.42). The
source is a modification of one of the PMP examples and it builds under
that environment.

Bon courage!

G.

On 6/02/2020 6:20 pm, Sebastien Loriot (GeometryFactory) wrote:

> If the error occurs after several operations, for debugging purpose
> you can use CGAL::Simple_cartesian<CGAL::Gmpq> as kernel and I think when
> writing to OFF you will write the exact rational representation.
> Then I think I should be able to load them and reproduce the error.
>
> Note that it will be much slower.
>
> Best,
>
> Sebastien.
>
> PS: don't post output meshes as an attachment to the mailing list as
> the file will be large (use gist.github.com or whatever online storage
> service).
>
>
> On 2/5/20 10:33 AM, Giles Puckett wrote:
>> Both meshes return true to does_bound_a_volume and false to
>> does_self_intersect. They do not throw an exception for
>> self-intersections. I can send the OFF files if you like, although
>> they don't produce the error they show the shape of the meshes..
>>
>> G.
>>
>> On 5/02/2020 6:23 pm, Sebastien Loriot (GeometryFactory) wrote:
>>> Does one of you mesh has a boundary?
>>>
>>> The list of PRs that could have introduced a regression is here:
>>> https://github.com/CGAL/cgal/pulls?utf8=%E2%9C%93&q=is%3Apr+is%3Aclosed+label%3AMerged_in_4.12.2++label%3APkg%3A%3APMP+ 
>>>
>>>
>>> I don't see anything suspicious. Is it deterministic?
>>>
>>> Best,
>>>
>>> Sebastien.
>>>
>>>
>>>
>>> On 2/4/20 11:59 PM, Giles Puckett wrote:
>>>> Bonjour,
>>>>
>>>> I have a CAD program that uses PMP to merge meshes. I moved from
>>>> 4.12 to 5.0 in order to use the default visitor to keep attributes
>>>> on faces through surface mesh unions. However, some previously
>>>> working meshes now fail with an infinite loop. The problem also
>>>> appears on 4.14.2.
>>>>
>>>> The infinite loop is in Corefinement::remove_unused_polylines at
>>>> face_graph_utils.h, line 1634: (in 5.0)
>>>>
>>>> for(vertex_descriptor v: vertices_kept)
>>>>    {
>>>>      halfedge_descriptor h = halfedge(v, tm),
>>>> start=GT::null_halfedge();
>>>>
>>>>      do{
>>>>        while ( !is_border(h, tm) || is_border(opposite(h, tm), tm)
>>>> ) // This while loop never exits
>>>>          h = opposite(next(h, tm), tm);
>>>>        halfedge_descriptor in = h;
>>>>        if (start==GT::null_halfedge())
>>>>          start=in;
>>>>        else
>>>>          if (start==in)
>>>>            break;
>>>>        while ( is_border(h, tm) )
>>>>          h = opposite(next(h, tm), tm);
>>>>        set_next(in, opposite(h, tm), tm);
>>>>      }
>>>>      while(true);//this loop handles non-manifold vertices
>>>>    }
>>>>
>>>> One mesh is a simple convex shape, the other is the result of a
>>>> previous union. All unions are done with exact predicates and
>>>> constructions in the standard way for consecutive bool ops. Testing
>>>> for self-intersections before and during the union reveals nothing.
>>>>
>>>> Sadly, I cannot reproduce it in a simple test example program (when
>>>> writing the meshes to OFF file, precision is lost, and I get
>>>> self-intersections or an assertion about collinear points). I
>>>> suspect there may be zero-area triangles produced by the first union.
>>>>
>>>> Three questions:
>>>>
>>>> Have there been any changes in corefinement, PMP or surface meshes
>>>> between 4.12 and 4.14.2 that might produce this, or any known
>>>> regressions?
>>>> And is there any way I can write the meshes out with sufficient
>>>> accuracy to submit a simple test case?
>>>> Lastly, is there any way I can get the functionality of the example
>>>> program (corefinement_mesh_union_with_attributes) to work in 4.12?
>>>>
>>>> Thanks for any help and for reading on this far :-)
>>>>
>>>> Giles.
>>>>
>>>>
>>>>
>>>
>>
>

--
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: Infinite loop in PMP::corefine_and_compute_union since 4.14.2

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

On 2/7/20 6:46 AM, Giles Puckett wrote:
> Hi,
>
> Thanks for the suggestion. Can you post a fragment of such an OFF file
> so I can see what it looks like?

There is the following undocumented function:

   template <typename P, typename NamedParameters>
   bool write_off(std::ostream& os, const Surface_mesh<P>& sm, const
NamedParameters& np)

if you pass CGAL::parameters::vertex_point_map(vpm) as np with vpm
being a map with GMPQ as FT or a custom map that forwards
`exact(epec_pt)` it should works.

The fonction CGAL::exact(CGAL::EPECK::Point_3) returns an object
of type CGAL::EPECK::Exact_kernel::Point_3.

>
> It will be hard to change the kernel in the original program, because
> there are a few steps between the mesh and the OFF file writing. But I
> should be able to dig through the exact_points property map per vertex
> and get out the exact coordinates.
>
> What format are the coordinate values in the
> Exact_predicates_exact_constructions_kernel ? (I confess I'm not very
> good with C++ especially with all the heavy template usage)

This is a filtered kernel and what is dumped is the "middle" of the
double interval surrounding the exact values. Note that those intervals
are not necessarily tight as this is also a Lazy kernel that is trying
to avoid doing exact computation until the point it is the only solution.

Best,

Sebastien.

>
> G.
>
> On 6/02/2020 6:20 pm, Sebastien Loriot (GeometryFactory) wrote:
>> If the error occurs after several operations, for debugging purpose
>> you can use CGAL::Simple_cartesian<CGAL::Gmpq> as kernel and I think when
>> writing to OFF you will write the exact rational representation.
>> Then I think I should be able to load them and reproduce the error.
>>
>> Note that it will be much slower.
>>
>> Best,
>>
>> Sebastien.
>>
>> PS: don't post output meshes as an attachment to the mailing list as
>> the file will be large (use gist.github.com or whatever online storage
>> service).
>>
>>
>> On 2/5/20 10:33 AM, Giles Puckett wrote:
>>> Both meshes return true to does_bound_a_volume and false to
>>> does_self_intersect. They do not throw an exception for
>>> self-intersections. I can send the OFF files if you like, although
>>> they don't produce the error they show the shape of the meshes..
>>>
>>> G.
>>>
>>> On 5/02/2020 6:23 pm, Sebastien Loriot (GeometryFactory) wrote:
>>>> Does one of you mesh has a boundary?
>>>>
>>>> The list of PRs that could have introduced a regression is here:
>>>> https://github.com/CGAL/cgal/pulls?utf8=%E2%9C%93&q=is%3Apr+is%3Aclosed+label%3AMerged_in_4.12.2++label%3APkg%3A%3APMP+ 
>>>>
>>>>
>>>> I don't see anything suspicious. Is it deterministic?
>>>>
>>>> Best,
>>>>
>>>> Sebastien.
>>>>
>>>>
>>>>
>>>> On 2/4/20 11:59 PM, Giles Puckett wrote:
>>>>> Bonjour,
>>>>>
>>>>> I have a CAD program that uses PMP to merge meshes. I moved from
>>>>> 4.12 to 5.0 in order to use the default visitor to keep attributes
>>>>> on faces through surface mesh unions. However, some previously
>>>>> working meshes now fail with an infinite loop. The problem also
>>>>> appears on 4.14.2.
>>>>>
>>>>> The infinite loop is in Corefinement::remove_unused_polylines at
>>>>> face_graph_utils.h, line 1634: (in 5.0)
>>>>>
>>>>> for(vertex_descriptor v: vertices_kept)
>>>>>    {
>>>>>      halfedge_descriptor h = halfedge(v, tm),
>>>>> start=GT::null_halfedge();
>>>>>
>>>>>      do{
>>>>>        while ( !is_border(h, tm) || is_border(opposite(h, tm), tm)
>>>>> ) // This while loop never exits
>>>>>          h = opposite(next(h, tm), tm);
>>>>>        halfedge_descriptor in = h;
>>>>>        if (start==GT::null_halfedge())
>>>>>          start=in;
>>>>>        else
>>>>>          if (start==in)
>>>>>            break;
>>>>>        while ( is_border(h, tm) )
>>>>>          h = opposite(next(h, tm), tm);
>>>>>        set_next(in, opposite(h, tm), tm);
>>>>>      }
>>>>>      while(true);//this loop handles non-manifold vertices
>>>>>    }
>>>>>
>>>>> One mesh is a simple convex shape, the other is the result of a
>>>>> previous union. All unions are done with exact predicates and
>>>>> constructions in the standard way for consecutive bool ops. Testing
>>>>> for self-intersections before and during the union reveals nothing.
>>>>>
>>>>> Sadly, I cannot reproduce it in a simple test example program (when
>>>>> writing the meshes to OFF file, precision is lost, and I get
>>>>> self-intersections or an assertion about collinear points). I
>>>>> suspect there may be zero-area triangles produced by the first union.
>>>>>
>>>>> Three questions:
>>>>>
>>>>> Have there been any changes in corefinement, PMP or surface meshes
>>>>> between 4.12 and 4.14.2 that might produce this, or any known
>>>>> regressions?
>>>>> And is there any way I can write the meshes out with sufficient
>>>>> accuracy to submit a simple test case?
>>>>> Lastly, is there any way I can get the functionality of the example
>>>>> program (corefinement_mesh_union_with_attributes) to work in 4.12?
>>>>>
>>>>> Thanks for any help and for reading on this far :-)
>>>>>
>>>>> Giles.
>>>>>
>>>>>
>>>>>
>>>>
>>>
>>

--
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: Infinite loop in PMP::corefine_and_compute_union since 4.14.2

Giles Puckett
Thanks. Have reproduced the infinite loop with doubles in the OFF file
(see my other email for file locations).

G.

On 10/02/2020 7:22 pm, Sebastien Loriot (GeometryFactory) wrote:

> Hey,
>
> On 2/7/20 6:46 AM, Giles Puckett wrote:
>> Hi,
>>
>> Thanks for the suggestion. Can you post a fragment of such an OFF
>> file so I can see what it looks like?
>
> There is the following undocumented function:
>
>   template <typename P, typename NamedParameters>
>   bool write_off(std::ostream& os, const Surface_mesh<P>& sm, const
> NamedParameters& np)
>
> if you pass CGAL::parameters::vertex_point_map(vpm) as np with vpm
> being a map with GMPQ as FT or a custom map that forwards
> `exact(epec_pt)` it should works.
>
> The fonction CGAL::exact(CGAL::EPECK::Point_3) returns an object
> of type CGAL::EPECK::Exact_kernel::Point_3.
>
>>
>> It will be hard to change the kernel in the original program, because
>> there are a few steps between the mesh and the OFF file writing. But
>> I should be able to dig through the exact_points property map per
>> vertex and get out the exact coordinates.
>>
>> What format are the coordinate values in the
>> Exact_predicates_exact_constructions_kernel ? (I confess I'm not very
>> good with C++ especially with all the heavy template usage)
>
> This is a filtered kernel and what is dumped is the "middle" of the
> double interval surrounding the exact values. Note that those intervals
> are not necessarily tight as this is also a Lazy kernel that is trying
> to avoid doing exact computation until the point it is the only solution.
>
> Best,
>
> Sebastien.
>
>>
>> G.
>>
>> On 6/02/2020 6:20 pm, Sebastien Loriot (GeometryFactory) wrote:
>>> If the error occurs after several operations, for debugging purpose
>>> you can use CGAL::Simple_cartesian<CGAL::Gmpq> as kernel and I think
>>> when
>>> writing to OFF you will write the exact rational representation.
>>> Then I think I should be able to load them and reproduce the error.
>>>
>>> Note that it will be much slower.
>>>
>>> Best,
>>>
>>> Sebastien.
>>>
>>> PS: don't post output meshes as an attachment to the mailing list as
>>> the file will be large (use gist.github.com or whatever online
>>> storage service).
>>>
>>>
>>> On 2/5/20 10:33 AM, Giles Puckett wrote:
>>>> Both meshes return true to does_bound_a_volume and false to
>>>> does_self_intersect. They do not throw an exception for
>>>> self-intersections. I can send the OFF files if you like, although
>>>> they don't produce the error they show the shape of the meshes..
>>>>
>>>> G.
>>>>
>>>> On 5/02/2020 6:23 pm, Sebastien Loriot (GeometryFactory) wrote:
>>>>> Does one of you mesh has a boundary?
>>>>>
>>>>> The list of PRs that could have introduced a regression is here:
>>>>> https://github.com/CGAL/cgal/pulls?utf8=%E2%9C%93&q=is%3Apr+is%3Aclosed+label%3AMerged_in_4.12.2++label%3APkg%3A%3APMP+ 
>>>>>
>>>>>
>>>>> I don't see anything suspicious. Is it deterministic?
>>>>>
>>>>> Best,
>>>>>
>>>>> Sebastien.
>>>>>
>>>>>
>>>>>
>>>>> On 2/4/20 11:59 PM, Giles Puckett wrote:
>>>>>> Bonjour,
>>>>>>
>>>>>> I have a CAD program that uses PMP to merge meshes. I moved from
>>>>>> 4.12 to 5.0 in order to use the default visitor to keep
>>>>>> attributes on faces through surface mesh unions. However, some
>>>>>> previously working meshes now fail with an infinite loop. The
>>>>>> problem also appears on 4.14.2.
>>>>>>
>>>>>> The infinite loop is in Corefinement::remove_unused_polylines at
>>>>>> face_graph_utils.h, line 1634: (in 5.0)
>>>>>>
>>>>>> for(vertex_descriptor v: vertices_kept)
>>>>>>    {
>>>>>>      halfedge_descriptor h = halfedge(v, tm),
>>>>>> start=GT::null_halfedge();
>>>>>>
>>>>>>      do{
>>>>>>        while ( !is_border(h, tm) || is_border(opposite(h, tm),
>>>>>> tm) ) // This while loop never exits
>>>>>>          h = opposite(next(h, tm), tm);
>>>>>>        halfedge_descriptor in = h;
>>>>>>        if (start==GT::null_halfedge())
>>>>>>          start=in;
>>>>>>        else
>>>>>>          if (start==in)
>>>>>>            break;
>>>>>>        while ( is_border(h, tm) )
>>>>>>          h = opposite(next(h, tm), tm);
>>>>>>        set_next(in, opposite(h, tm), tm);
>>>>>>      }
>>>>>>      while(true);//this loop handles non-manifold vertices
>>>>>>    }
>>>>>>
>>>>>> One mesh is a simple convex shape, the other is the result of a
>>>>>> previous union. All unions are done with exact predicates and
>>>>>> constructions in the standard way for consecutive bool ops.
>>>>>> Testing for self-intersections before and during the union
>>>>>> reveals nothing.
>>>>>>
>>>>>> Sadly, I cannot reproduce it in a simple test example program
>>>>>> (when writing the meshes to OFF file, precision is lost, and I
>>>>>> get self-intersections or an assertion about collinear points). I
>>>>>> suspect there may be zero-area triangles produced by the first
>>>>>> union.
>>>>>>
>>>>>> Three questions:
>>>>>>
>>>>>> Have there been any changes in corefinement, PMP or surface
>>>>>> meshes between 4.12 and 4.14.2 that might produce this, or any
>>>>>> known regressions?
>>>>>> And is there any way I can write the meshes out with sufficient
>>>>>> accuracy to submit a simple test case?
>>>>>> Lastly, is there any way I can get the functionality of the
>>>>>> example program (corefinement_mesh_union_with_attributes) to work
>>>>>> in 4.12?
>>>>>>
>>>>>> Thanks for any help and for reading on this far :-)
>>>>>>
>>>>>> Giles.
>>>>>>
>>>>>>
>>>>>>
>>>>>
>>>>
>>>
>

--
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: Infinite loop in PMP::corefine_and_compute_union since 4.14.2

Giles Puckett
Hi Sebastien,

Would you like me to raise an issue on github for this?

G.

On 10/02/2020 8:46 pm, Giles Puckett wrote:

> Thanks. Have reproduced the infinite loop with doubles in the OFF file
> (see my other email for file locations).
>
> G.
>
> On 10/02/2020 7:22 pm, Sebastien Loriot (GeometryFactory) wrote:
>> Hey,
>>
>> On 2/7/20 6:46 AM, Giles Puckett wrote:
>>> Hi,
>>>
>>> Thanks for the suggestion. Can you post a fragment of such an OFF
>>> file so I can see what it looks like?
>>
>> There is the following undocumented function:
>>
>>   template <typename P, typename NamedParameters>
>>   bool write_off(std::ostream& os, const Surface_mesh<P>& sm, const
>> NamedParameters& np)
>>
>> if you pass CGAL::parameters::vertex_point_map(vpm) as np with vpm
>> being a map with GMPQ as FT or a custom map that forwards
>> `exact(epec_pt)` it should works.
>>
>> The fonction CGAL::exact(CGAL::EPECK::Point_3) returns an object
>> of type CGAL::EPECK::Exact_kernel::Point_3.
>>
>>>
>>> It will be hard to change the kernel in the original program,
>>> because there are a few steps between the mesh and the OFF file
>>> writing. But I should be able to dig through the exact_points
>>> property map per vertex and get out the exact coordinates.
>>>
>>> What format are the coordinate values in the
>>> Exact_predicates_exact_constructions_kernel ? (I confess I'm not
>>> very good with C++ especially with all the heavy template usage)
>>
>> This is a filtered kernel and what is dumped is the "middle" of the
>> double interval surrounding the exact values. Note that those intervals
>> are not necessarily tight as this is also a Lazy kernel that is trying
>> to avoid doing exact computation until the point it is the only
>> solution.
>>
>> Best,
>>
>> Sebastien.
>>
>>>
>>> G.
>>>
>>> On 6/02/2020 6:20 pm, Sebastien Loriot (GeometryFactory) wrote:
>>>> If the error occurs after several operations, for debugging purpose
>>>> you can use CGAL::Simple_cartesian<CGAL::Gmpq> as kernel and I
>>>> think when
>>>> writing to OFF you will write the exact rational representation.
>>>> Then I think I should be able to load them and reproduce the error.
>>>>
>>>> Note that it will be much slower.
>>>>
>>>> Best,
>>>>
>>>> Sebastien.
>>>>
>>>> PS: don't post output meshes as an attachment to the mailing list as
>>>> the file will be large (use gist.github.com or whatever online
>>>> storage service).
>>>>
>>>>
>>>> On 2/5/20 10:33 AM, Giles Puckett wrote:
>>>>> Both meshes return true to does_bound_a_volume and false to
>>>>> does_self_intersect. They do not throw an exception for
>>>>> self-intersections. I can send the OFF files if you like, although
>>>>> they don't produce the error they show the shape of the meshes..
>>>>>
>>>>> G.
>>>>>
>>>>> On 5/02/2020 6:23 pm, Sebastien Loriot (GeometryFactory) wrote:
>>>>>> Does one of you mesh has a boundary?
>>>>>>
>>>>>> The list of PRs that could have introduced a regression is here:
>>>>>> https://github.com/CGAL/cgal/pulls?utf8=%E2%9C%93&q=is%3Apr+is%3Aclosed+label%3AMerged_in_4.12.2++label%3APkg%3A%3APMP+ 
>>>>>>
>>>>>>
>>>>>> I don't see anything suspicious. Is it deterministic?
>>>>>>
>>>>>> Best,
>>>>>>
>>>>>> Sebastien.
>>>>>>
>>>>>>
>>>>>>
>>>>>> On 2/4/20 11:59 PM, Giles Puckett wrote:
>>>>>>> Bonjour,
>>>>>>>
>>>>>>> I have a CAD program that uses PMP to merge meshes. I moved from
>>>>>>> 4.12 to 5.0 in order to use the default visitor to keep
>>>>>>> attributes on faces through surface mesh unions. However, some
>>>>>>> previously working meshes now fail with an infinite loop. The
>>>>>>> problem also appears on 4.14.2.
>>>>>>>
>>>>>>> The infinite loop is in Corefinement::remove_unused_polylines at
>>>>>>> face_graph_utils.h, line 1634: (in 5.0)
>>>>>>>
>>>>>>> for(vertex_descriptor v: vertices_kept)
>>>>>>>    {
>>>>>>>      halfedge_descriptor h = halfedge(v, tm),
>>>>>>> start=GT::null_halfedge();
>>>>>>>
>>>>>>>      do{
>>>>>>>        while ( !is_border(h, tm) || is_border(opposite(h, tm),
>>>>>>> tm) ) // This while loop never exits
>>>>>>>          h = opposite(next(h, tm), tm);
>>>>>>>        halfedge_descriptor in = h;
>>>>>>>        if (start==GT::null_halfedge())
>>>>>>>          start=in;
>>>>>>>        else
>>>>>>>          if (start==in)
>>>>>>>            break;
>>>>>>>        while ( is_border(h, tm) )
>>>>>>>          h = opposite(next(h, tm), tm);
>>>>>>>        set_next(in, opposite(h, tm), tm);
>>>>>>>      }
>>>>>>>      while(true);//this loop handles non-manifold vertices
>>>>>>>    }
>>>>>>>
>>>>>>> One mesh is a simple convex shape, the other is the result of a
>>>>>>> previous union. All unions are done with exact predicates and
>>>>>>> constructions in the standard way for consecutive bool ops.
>>>>>>> Testing for self-intersections before and during the union
>>>>>>> reveals nothing.
>>>>>>>
>>>>>>> Sadly, I cannot reproduce it in a simple test example program
>>>>>>> (when writing the meshes to OFF file, precision is lost, and I
>>>>>>> get self-intersections or an assertion about collinear points).
>>>>>>> I suspect there may be zero-area triangles produced by the first
>>>>>>> union.
>>>>>>>
>>>>>>> Three questions:
>>>>>>>
>>>>>>> Have there been any changes in corefinement, PMP or surface
>>>>>>> meshes between 4.12 and 4.14.2 that might produce this, or any
>>>>>>> known regressions?
>>>>>>> And is there any way I can write the meshes out with sufficient
>>>>>>> accuracy to submit a simple test case?
>>>>>>> Lastly, is there any way I can get the functionality of the
>>>>>>> example program (corefinement_mesh_union_with_attributes) to
>>>>>>> work in 4.12?
>>>>>>>
>>>>>>> Thanks for any help and for reading on this far :-)
>>>>>>>
>>>>>>> Giles.
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>
>>>>>
>>>>
>>
>

--
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: Infinite loop in PMP::corefine_and_compute_union since 4.14.2

Sebastien Loriot (GeometryFactory)
Yes please, I could reproduce the issue and it is a real bug!
As a workaround, note that if you write the output in a new mesh
it will work (the bug is only in the inplace version). I'll fix
it asap.

Thanks,

Sebastien.

On 2/12/20 12:08 PM, Giles Puckett wrote:

> Hi Sebastien,
>
> Would you like me to raise an issue on github for this?
>
> G.
>
> On 10/02/2020 8:46 pm, Giles Puckett wrote:
>> Thanks. Have reproduced the infinite loop with doubles in the OFF file
>> (see my other email for file locations).
>>
>> G.
>>
>> On 10/02/2020 7:22 pm, Sebastien Loriot (GeometryFactory) wrote:
>>> Hey,
>>>
>>> On 2/7/20 6:46 AM, Giles Puckett wrote:
>>>> Hi,
>>>>
>>>> Thanks for the suggestion. Can you post a fragment of such an OFF
>>>> file so I can see what it looks like?
>>>
>>> There is the following undocumented function:
>>>
>>>   template <typename P, typename NamedParameters>
>>>   bool write_off(std::ostream& os, const Surface_mesh<P>& sm, const
>>> NamedParameters& np)
>>>
>>> if you pass CGAL::parameters::vertex_point_map(vpm) as np with vpm
>>> being a map with GMPQ as FT or a custom map that forwards
>>> `exact(epec_pt)` it should works.
>>>
>>> The fonction CGAL::exact(CGAL::EPECK::Point_3) returns an object
>>> of type CGAL::EPECK::Exact_kernel::Point_3.
>>>
>>>>
>>>> It will be hard to change the kernel in the original program,
>>>> because there are a few steps between the mesh and the OFF file
>>>> writing. But I should be able to dig through the exact_points
>>>> property map per vertex and get out the exact coordinates.
>>>>
>>>> What format are the coordinate values in the
>>>> Exact_predicates_exact_constructions_kernel ? (I confess I'm not
>>>> very good with C++ especially with all the heavy template usage)
>>>
>>> This is a filtered kernel and what is dumped is the "middle" of the
>>> double interval surrounding the exact values. Note that those intervals
>>> are not necessarily tight as this is also a Lazy kernel that is trying
>>> to avoid doing exact computation until the point it is the only
>>> solution.
>>>
>>> Best,
>>>
>>> Sebastien.
>>>
>>>>
>>>> G.
>>>>
>>>> On 6/02/2020 6:20 pm, Sebastien Loriot (GeometryFactory) wrote:
>>>>> If the error occurs after several operations, for debugging purpose
>>>>> you can use CGAL::Simple_cartesian<CGAL::Gmpq> as kernel and I
>>>>> think when
>>>>> writing to OFF you will write the exact rational representation.
>>>>> Then I think I should be able to load them and reproduce the error.
>>>>>
>>>>> Note that it will be much slower.
>>>>>
>>>>> Best,
>>>>>
>>>>> Sebastien.
>>>>>
>>>>> PS: don't post output meshes as an attachment to the mailing list as
>>>>> the file will be large (use gist.github.com or whatever online
>>>>> storage service).
>>>>>
>>>>>
>>>>> On 2/5/20 10:33 AM, Giles Puckett wrote:
>>>>>> Both meshes return true to does_bound_a_volume and false to
>>>>>> does_self_intersect. They do not throw an exception for
>>>>>> self-intersections. I can send the OFF files if you like, although
>>>>>> they don't produce the error they show the shape of the meshes..
>>>>>>
>>>>>> G.
>>>>>>
>>>>>> On 5/02/2020 6:23 pm, Sebastien Loriot (GeometryFactory) wrote:
>>>>>>> Does one of you mesh has a boundary?
>>>>>>>
>>>>>>> The list of PRs that could have introduced a regression is here:
>>>>>>> https://github.com/CGAL/cgal/pulls?utf8=%E2%9C%93&q=is%3Apr+is%3Aclosed+label%3AMerged_in_4.12.2++label%3APkg%3A%3APMP+ 
>>>>>>>
>>>>>>>
>>>>>>> I don't see anything suspicious. Is it deterministic?
>>>>>>>
>>>>>>> Best,
>>>>>>>
>>>>>>> Sebastien.
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>> On 2/4/20 11:59 PM, Giles Puckett wrote:
>>>>>>>> Bonjour,
>>>>>>>>
>>>>>>>> I have a CAD program that uses PMP to merge meshes. I moved from
>>>>>>>> 4.12 to 5.0 in order to use the default visitor to keep
>>>>>>>> attributes on faces through surface mesh unions. However, some
>>>>>>>> previously working meshes now fail with an infinite loop. The
>>>>>>>> problem also appears on 4.14.2.
>>>>>>>>
>>>>>>>> The infinite loop is in Corefinement::remove_unused_polylines at
>>>>>>>> face_graph_utils.h, line 1634: (in 5.0)
>>>>>>>>
>>>>>>>> for(vertex_descriptor v: vertices_kept)
>>>>>>>>    {
>>>>>>>>      halfedge_descriptor h = halfedge(v, tm),
>>>>>>>> start=GT::null_halfedge();
>>>>>>>>
>>>>>>>>      do{
>>>>>>>>        while ( !is_border(h, tm) || is_border(opposite(h, tm),
>>>>>>>> tm) ) // This while loop never exits
>>>>>>>>          h = opposite(next(h, tm), tm);
>>>>>>>>        halfedge_descriptor in = h;
>>>>>>>>        if (start==GT::null_halfedge())
>>>>>>>>          start=in;
>>>>>>>>        else
>>>>>>>>          if (start==in)
>>>>>>>>            break;
>>>>>>>>        while ( is_border(h, tm) )
>>>>>>>>          h = opposite(next(h, tm), tm);
>>>>>>>>        set_next(in, opposite(h, tm), tm);
>>>>>>>>      }
>>>>>>>>      while(true);//this loop handles non-manifold vertices
>>>>>>>>    }
>>>>>>>>
>>>>>>>> One mesh is a simple convex shape, the other is the result of a
>>>>>>>> previous union. All unions are done with exact predicates and
>>>>>>>> constructions in the standard way for consecutive bool ops.
>>>>>>>> Testing for self-intersections before and during the union
>>>>>>>> reveals nothing.
>>>>>>>>
>>>>>>>> Sadly, I cannot reproduce it in a simple test example program
>>>>>>>> (when writing the meshes to OFF file, precision is lost, and I
>>>>>>>> get self-intersections or an assertion about collinear points).
>>>>>>>> I suspect there may be zero-area triangles produced by the first
>>>>>>>> union.
>>>>>>>>
>>>>>>>> Three questions:
>>>>>>>>
>>>>>>>> Have there been any changes in corefinement, PMP or surface
>>>>>>>> meshes between 4.12 and 4.14.2 that might produce this, or any
>>>>>>>> known regressions?
>>>>>>>> And is there any way I can write the meshes out with sufficient
>>>>>>>> accuracy to submit a simple test case?
>>>>>>>> Lastly, is there any way I can get the functionality of the
>>>>>>>> example program (corefinement_mesh_union_with_attributes) to
>>>>>>>> work in 4.12?
>>>>>>>>
>>>>>>>> Thanks for any help and for reading on this far :-)
>>>>>>>>
>>>>>>>> Giles.
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>
>>>>>>
>>>>>
>>>
>>

--
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: Infinite loop in PMP::corefine_and_compute_union since 4.14.2

Giles Puckett
Issue #4522 opened. Merci bien!

G.

On 12/02/2020 9:55 pm, Sebastien Loriot (GeometryFactory) wrote:

> Yes please, I could reproduce the issue and it is a real bug!
> As a workaround, note that if you write the output in a new mesh
> it will work (the bug is only in the inplace version). I'll fix
> it asap.
>
> Thanks,
>
> Sebastien.
>
> On 2/12/20 12:08 PM, Giles Puckett wrote:
>> Hi Sebastien,
>>
>> Would you like me to raise an issue on github for this?
>>
>> G.
>>
>> On 10/02/2020 8:46 pm, Giles Puckett wrote:
>>> Thanks. Have reproduced the infinite loop with doubles in the OFF
>>> file (see my other email for file locations).
>>>
>>> G.
>>>
>>> On 10/02/2020 7:22 pm, Sebastien Loriot (GeometryFactory) wrote:
>>>> Hey,
>>>>
>>>> On 2/7/20 6:46 AM, Giles Puckett wrote:
>>>>> Hi,
>>>>>
>>>>> Thanks for the suggestion. Can you post a fragment of such an OFF
>>>>> file so I can see what it looks like?
>>>>
>>>> There is the following undocumented function:
>>>>
>>>>   template <typename P, typename NamedParameters>
>>>>   bool write_off(std::ostream& os, const Surface_mesh<P>& sm, const
>>>> NamedParameters& np)
>>>>
>>>> if you pass CGAL::parameters::vertex_point_map(vpm) as np with vpm
>>>> being a map with GMPQ as FT or a custom map that forwards
>>>> `exact(epec_pt)` it should works.
>>>>
>>>> The fonction CGAL::exact(CGAL::EPECK::Point_3) returns an object
>>>> of type CGAL::EPECK::Exact_kernel::Point_3.
>>>>
>>>>>
>>>>> It will be hard to change the kernel in the original program,
>>>>> because there are a few steps between the mesh and the OFF file
>>>>> writing. But I should be able to dig through the exact_points
>>>>> property map per vertex and get out the exact coordinates.
>>>>>
>>>>> What format are the coordinate values in the
>>>>> Exact_predicates_exact_constructions_kernel ? (I confess I'm not
>>>>> very good with C++ especially with all the heavy template usage)
>>>>
>>>> This is a filtered kernel and what is dumped is the "middle" of the
>>>> double interval surrounding the exact values. Note that those
>>>> intervals
>>>> are not necessarily tight as this is also a Lazy kernel that is trying
>>>> to avoid doing exact computation until the point it is the only
>>>> solution.
>>>>
>>>> Best,
>>>>
>>>> Sebastien.
>>>>
>>>>>
>>>>> G.
>>>>>
>>>>> On 6/02/2020 6:20 pm, Sebastien Loriot (GeometryFactory) wrote:
>>>>>> If the error occurs after several operations, for debugging
>>>>>> purpose you can use CGAL::Simple_cartesian<CGAL::Gmpq> as kernel
>>>>>> and I think when
>>>>>> writing to OFF you will write the exact rational representation.
>>>>>> Then I think I should be able to load them and reproduce the error.
>>>>>>
>>>>>> Note that it will be much slower.
>>>>>>
>>>>>> Best,
>>>>>>
>>>>>> Sebastien.
>>>>>>
>>>>>> PS: don't post output meshes as an attachment to the mailing list as
>>>>>> the file will be large (use gist.github.com or whatever online
>>>>>> storage service).
>>>>>>
>>>>>>
>>>>>> On 2/5/20 10:33 AM, Giles Puckett wrote:
>>>>>>> Both meshes return true to does_bound_a_volume and false to
>>>>>>> does_self_intersect. They do not throw an exception for
>>>>>>> self-intersections. I can send the OFF files if you like,
>>>>>>> although they don't produce the error they show the shape of the
>>>>>>> meshes..
>>>>>>>
>>>>>>> G.
>>>>>>>
>>>>>>> On 5/02/2020 6:23 pm, Sebastien Loriot (GeometryFactory) wrote:
>>>>>>>> Does one of you mesh has a boundary?
>>>>>>>>
>>>>>>>> The list of PRs that could have introduced a regression is here:
>>>>>>>> https://github.com/CGAL/cgal/pulls?utf8=%E2%9C%93&q=is%3Apr+is%3Aclosed+label%3AMerged_in_4.12.2++label%3APkg%3A%3APMP+ 
>>>>>>>>
>>>>>>>>
>>>>>>>> I don't see anything suspicious. Is it deterministic?
>>>>>>>>
>>>>>>>> Best,
>>>>>>>>
>>>>>>>> Sebastien.
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>> On 2/4/20 11:59 PM, Giles Puckett wrote:
>>>>>>>>> Bonjour,
>>>>>>>>>
>>>>>>>>> I have a CAD program that uses PMP to merge meshes. I moved
>>>>>>>>> from 4.12 to 5.0 in order to use the default visitor to keep
>>>>>>>>> attributes on faces through surface mesh unions. However, some
>>>>>>>>> previously working meshes now fail with an infinite loop. The
>>>>>>>>> problem also appears on 4.14.2.
>>>>>>>>>
>>>>>>>>> The infinite loop is in Corefinement::remove_unused_polylines
>>>>>>>>> at face_graph_utils.h, line 1634: (in 5.0)
>>>>>>>>>
>>>>>>>>> for(vertex_descriptor v: vertices_kept)
>>>>>>>>>    {
>>>>>>>>>      halfedge_descriptor h = halfedge(v, tm),
>>>>>>>>> start=GT::null_halfedge();
>>>>>>>>>
>>>>>>>>>      do{
>>>>>>>>>        while ( !is_border(h, tm) || is_border(opposite(h, tm),
>>>>>>>>> tm) ) // This while loop never exits
>>>>>>>>>          h = opposite(next(h, tm), tm);
>>>>>>>>>        halfedge_descriptor in = h;
>>>>>>>>>        if (start==GT::null_halfedge())
>>>>>>>>>          start=in;
>>>>>>>>>        else
>>>>>>>>>          if (start==in)
>>>>>>>>>            break;
>>>>>>>>>        while ( is_border(h, tm) )
>>>>>>>>>          h = opposite(next(h, tm), tm);
>>>>>>>>>        set_next(in, opposite(h, tm), tm);
>>>>>>>>>      }
>>>>>>>>>      while(true);//this loop handles non-manifold vertices
>>>>>>>>>    }
>>>>>>>>>
>>>>>>>>> One mesh is a simple convex shape, the other is the result of
>>>>>>>>> a previous union. All unions are done with exact predicates
>>>>>>>>> and constructions in the standard way for consecutive bool
>>>>>>>>> ops. Testing for self-intersections before and during the
>>>>>>>>> union reveals nothing.
>>>>>>>>>
>>>>>>>>> Sadly, I cannot reproduce it in a simple test example program
>>>>>>>>> (when writing the meshes to OFF file, precision is lost, and I
>>>>>>>>> get self-intersections or an assertion about collinear
>>>>>>>>> points). I suspect there may be zero-area triangles produced
>>>>>>>>> by the first union.
>>>>>>>>>
>>>>>>>>> Three questions:
>>>>>>>>>
>>>>>>>>> Have there been any changes in corefinement, PMP or surface
>>>>>>>>> meshes between 4.12 and 4.14.2 that might produce this, or any
>>>>>>>>> known regressions?
>>>>>>>>> And is there any way I can write the meshes out with
>>>>>>>>> sufficient accuracy to submit a simple test case?
>>>>>>>>> Lastly, is there any way I can get the functionality of the
>>>>>>>>> example program (corefinement_mesh_union_with_attributes) to
>>>>>>>>> work in 4.12?
>>>>>>>>>
>>>>>>>>> Thanks for any help and for reading on this far :-)
>>>>>>>>>
>>>>>>>>> Giles.
>>>>>>>>>
>>>>>>>>>
>>>>>>>>>
>>>>>>>>
>>>>>>>
>>>>>>
>>>>
>>>
>

--
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: Infinite loop in PMP::corefine_and_compute_union since 4.14.2

Laurent Rineau (CGAL/GeometryFactory)
In reply to this post by Sebastien Loriot (GeometryFactory)
On Wednesday, February 5, 2020 9:23:31 AM CET Sebastien Loriot
(GeometryFactory) wrote:
> Does one of you mesh has a boundary?
>
> The list of PRs that could have introduced a regression is here:
> https://github.com/CGAL/cgal/pulls?utf8=%E2%9C%93&q=is%3Apr+is%3Aclosed+labe
> l%3AMerged_in_4.12.2++label%3APkg%3A%3APMP+
>
> I don't see anything suspicious. Is it deterministic?

Giles said:
> Have there been any changes in corefinement, PMP or surface meshes
> between 4.12 and 4.14.2 that might produce this

So it might be any PR introduced in 4.12.1 or later, and not only those
between CGAL-4.14.1 and 4.14.2.

--
Laurent Rineau, PhD
R&D Engineer at GeometryFactory           http://www.geometryfactory.com/
Release Manager of the CGAL Project       http://www.cgal.org/




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