lloyd optimization mesh 2 assertion failure

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

lloyd optimization mesh 2 assertion failure

chrism
Hi,

I've been successfully meshing a 2D domain with the CDT as per 

I've been using an outer domain constraint, and have now started to add interior constraints (lines that represent rivers that should be not crossed by triangles).

This works as expected.

However, when I enable lloyd optimization I have the following error:

Running 1 Lloyd iterations...
CGAL error: assertion violation!
Expression : do_intersect(line, m_cdt.segment(face->blinding_constraint()))
File       : /usr/local/include/CGAL/Constrained_voronoi_diagram_2.h
Line       : 392
Explanation:
Refer to the bug-reporting instructions at http://www.cgal.org/bug_report.html
libc++abi.dylib: terminating with uncaught exception of type CGAL::Assertion_exception: CGAL ERROR: assertion violation!
Expr: do_intersect(line, m_cdt.segment(face->blinding_constraint()))
File: /usr/local/include/CGAL/Constrained_voronoi_diagram_2.h
Line: 392

When I use the same domain *without* the interior constraints, the lloyd optimization works as expected.

I've been unable to figure out what is going wrong based on this error message and would appreciate any insight

Cheers
Chris
Reply | Threaded
Open this post in threaded view
|

Re: lloyd optimization mesh 2 assertion failure

Jane Tournois
Hi Chris,

thanks for your report.

First, I have one question : did you insert the interior constraints
before running the mesher (I mean the refinement step), or after?

Can you please send some code and data to help me reproduce the issue?
The use case you mention has been tested already, so I would need your data.

Best regards,

Jane.



Le 23/02/2018 à 00:25, Chris Marsh a écrit :

> Hi,
>
> I've been successfully meshing a 2D domain with the CDT as per
> https://doc.cgal.org/latest/Mesh_2/index.html
>
> I've been using an outer domain constraint, and have now started to
> add interior constraints (lines that represent rivers that should be
> not crossed by triangles).
>
> This works as expected.
>
> However, when I enable lloyd optimization I have the following error:
>
> Running 1 Lloyd iterations...
> CGAL error: assertion violation!
> Expression : do_intersect(line,
> m_cdt.segment(face->blinding_constraint()))
> File       : /usr/local/include/CGAL/Constrained_voronoi_diagram_2.h
> Line       : 392
> Explanation:
> Refer to the bug-reporting instructions at
> http://www.cgal.org/bug_report.html
> libc++abi.dylib: terminating with uncaught exception of type
> CGAL::Assertion_exception: CGAL ERROR: assertion violation!
> Expr: do_intersect(line, m_cdt.segment(face->blinding_constraint()))
> File: /usr/local/include/CGAL/Constrained_voronoi_diagram_2.h
> Line: 392
>
> When I use the same domain *without* the interior constraints, the
> lloyd optimization works as expected.
>
> I've been unable to figure out what is going wrong based on this error
> message and would appreciate any insight
>
> Cheers
> Chris

--
Jane Tournois, PhD
R&D Engineer at GeometryFactory
http://www.geometryfactory.com/


--
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: lloyd optimization mesh 2 assertion failure

chrism
Ok this is odd. I made some changes this morning  (nothing related to my
constraint code) and recompiled, problem is gone. I can run the domain with
lloyd optimization without issue. However, the resulting "optimized" mesh is
of poor quality. Many small, thin (non-Delauany) triangles are present along
the constraint (circled in red). I've attached an image to show what I mean
where I ran max of 100 lloyd iterations. Is this expected behaviour? All the
other meshes I run lloyd iterations on produce high quality  meshes.

<http://cgal-discuss.949826.n4.nabble.com/file/t375307/File_001.png>



--
Sent from: http://cgal-discuss.949826.n4.nabble.com/

--
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: lloyd optimization mesh 2 assertion failure

Jane Tournois
I see the bad triangles, but I don't understand where the constraints
are, on your figure. Can you please highlight them?


Le 24/02/2018 à 01:00, chrism a écrit :

> Ok this is odd. I made some changes this morning  (nothing related to my
> constraint code) and recompiled, problem is gone. I can run the domain with
> lloyd optimization without issue. However, the resulting "optimized" mesh is
> of poor quality. Many small, thin (non-Delauany) triangles are present along
> the constraint (circled in red). I've attached an image to show what I mean
> where I ran max of 100 lloyd iterations. Is this expected behaviour? All the
> other meshes I run lloyd iterations on produce high quality  meshes.
>
> <http://cgal-discuss.949826.n4.nabble.com/file/t375307/File_001.png>
>
>
>
> --
> Sent from: http://cgal-discuss.949826.n4.nabble.com/
>

--
Jane Tournois, PhD
R&D Engineer at GeometryFactory
http://www.geometryfactory.com/


--
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: lloyd optimization mesh 2 assertion failure

chrism
Ah, sorry. Please find the comparison as presented above with the constraint
shown in red.

<http://cgal-discuss.949826.n4.nabble.com/file/t375307/lloyd.png>

As I cannot attach a large image, it may be difficult to see exactly? If so,
I have paraview compatible VTU files as well as the triangulation and
constraint in ESRI shape files (shp) to load into a GIS, such as qGIS.



--
Sent from: http://cgal-discuss.949826.n4.nabble.com/

--
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: lloyd optimization mesh 2 assertion failure

Jane Tournois

Hi Chris,

I understand what you mean.
Actually, your input mesh is pretty coarse close to constraints, so the Lloyd optimization cannot do much about it.

You can have a look at this paper for more details on our algorithm :
www.global-sci.org/nmtma/volumes/v3n2/pdf/32-212.pdf

The triangles that are called "blind" (meaning that their circumcenter is on the other side of a constrained edge) can hardly have a good shape without refining the associated constrained edge.
See for example Figure 5, where such triangles are colored.

If you want better shaped triangles close to constrained edges, they should be refined using the Delaunay_mesh_size_criteria_2 [1].

Also note that the Lloyd smoothing algorithm is enriched with a sizing field that locally preserves the mesh density through iterations. So, the vertices that are close to constraints should remain close to constraints. It avoids creating needle-shaped triangles next to constraints.

Best regards,

Jane.


[1] https://doc.cgal.org/latest/Mesh_2/classCGAL_1_1Delaunay__mesh__size__criteria__2.html


Le 26/02/2018 à 18:06, chrism a écrit :
Ah, sorry. Please find the comparison as presented above with the constraint
shown in red.

<http://cgal-discuss.949826.n4.nabble.com/file/t375307/lloyd.png> 

As I cannot attach a large image, it may be difficult to see exactly? If so,
I have paraview compatible VTU files as well as the triangulation and
constraint in ESRI shape files (shp) to load into a GIS, such as qGIS.



--
Sent from: http://cgal-discuss.949826.n4.nabble.com/


-- 
Jane Tournois, PhD
R&D Engineer at GeometryFactory
http://www.geometryfactory.com/
Reply | Threaded
Open this post in threaded view
|

Re: lloyd optimization mesh 2 assertion failure

Christophe Riedinger
In reply to this post by chrism
Le 23 févr. 2018 00:26, "Chris Marsh" <[hidden email]> a écrit :
Hi,

I've been successfully meshing a 2D domain with the CDT as per 

I've been using an outer domain constraint, and have now started to add interior constraints (lines that represent rivers that should be not crossed by triangles).

This works as expected.

However, when I enable lloyd optimization I have the following error:

Running 1 Lloyd iterations...
CGAL error: assertion violation!
Expression : do_intersect(line, m_cdt.segment(face->blinding_constraint()))
File       : /usr/local/include/CGAL/Constrained_voronoi_diagram_2.h
Line       : 392
Explanation:
Refer to the bug-reporting instructions at http://www.cgal.org/bug_report.html
libc++abi.dylib: terminating with uncaught exception of type CGAL::Assertion_exception: CGAL ERROR: assertion violation!
Expr: do_intersect(line, m_cdt.segment(face->blinding_constraint()))
File: /usr/local/include/CGAL/Constrained_voronoi_diagram_2.h
Line: 392

When I use the same domain *without* the interior constraints, the lloyd optimization works as expected.

I've been unable to figure out what is going wrong based on this error message and would appreciate any insight

Cheers
Chris
Reply | Threaded
Open this post in threaded view
|

Re: lloyd optimization mesh 2 assertion failure

chrism
I will read the paper, but I think this makes sense. I will just use fewer/no
iterations then! I'll let you know if I run into that strange error again.

Thanks very much
Cheers
Chris



--
Sent from: http://cgal-discuss.949826.n4.nabble.com/

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