Template:Lloyd Optimizer: Difference between revisions
From XMS Wiki
Jump to navigationJump to search
m (Protected "Template:Lloyd Optimizer" ([Edit=Allow only administrators] (indefinite) [Move=Allow only administrators] (indefinite))) |
No edit summary |
||
| (7 intermediate revisions by 2 users not shown) | |||
| Line 7: | Line 7: | ||
From [https://doc.cgal.org/latest/Mesh_2/index.html#secMesh_2_optimization CGAL]: | From [https://doc.cgal.org/latest/Mesh_2/index.html#secMesh_2_optimization CGAL]: | ||
<blockquote> | <blockquote> | ||
This optimization process alternates relocating vertices to the center of mass of their Voronoi cells, and updating the Delaunay connectivity of the triangulation. The center of mass is computed with respect to a sizing function that was designed to preserve the local density of points in the | This optimization process alternates relocating vertices to the center of mass of their Voronoi cells, and updating the Delaunay connectivity of the triangulation. The center of mass is computed with respect to a sizing function that was designed to preserve the local density of points in the grid... | ||
</blockquote> | </blockquote> | ||
====Input Parameters==== | ====Input Parameters==== | ||
* ''Input grid'' – A UGrid containing triangles to optimize. | * ''Input grid'' – A UGrid containing triangles to optimize. | ||
* '' | * ''Number of iterations to perform'' – The maximum number of iterations to perform before stopping. Can be set to 0 for no limit. | ||
* '' | * ''Maximum duration, in seconds'' – The maximum amount of time to optimize for, in seconds. Set to "0" for no limit. <!--This should be a number followed by a letter indicating the scale, e.g. "10m" for 10 minutes. Supported scales are "d" (days), "h" (hours), "m" (minutes) and "s" (seconds). These can be combined by separating them with a space, e.g. "1d 6h 30m" for one day, six hours and thirty minutes. If left blank, there will be no time limit.--> | ||
* '' | * ''Minimum movement ratio'' – Fraction of the length of a vertex's shortest incident edge by which it must move during an iteration. If an iteration would move the vertex by less than this amount, then movement of the vertex will be skipped during this iteration. Other vertices may still move during the iteration, and the skipped vertex may be moved during a later iteration if the vertex gets a larger proposed move. This can be useful to prevent the optimizer from spending time moving vertices by tiny amounts. It should be a value between 0 and 1. A value of 0 will disable this condition. | ||
* ''Freeze ratio'' – Similar to ''Move ratio'', except that the optimization will stop rather than skip the move. | * ''Freeze ratio'' – Similar to ''Move ratio'', except that the optimization will stop rather than skip the move. | ||
====Additional Notes==== | ====Additional Notes==== | ||
The optimizer will not move points on boundary polygons | The optimizer will not move points on boundary polygons or the boundaries of holes. | ||
During development, points were observed moving across boundaries in some cases. This issue can no longer be reproduced, which prevents understanding the underlying cause and verifying that it is truly resolved. To be on the safe side, the tool will delete any points that migrate across boundaries during optimization. | During development, points were observed moving across boundaries in some cases. This issue can no longer be reproduced, which prevents understanding the underlying cause and verifying that it is truly resolved. To be on the safe side, the tool will delete any points that migrate across boundaries during optimization. | ||
While this tool operates on any 2D UGrid, it requires that the grid be fully triangulated. To accomodate this, the tool will generate a triangulated grid based on the input grid and optimize the triangulated grid instead. This may result in swapped interior edges and non-triangular cells being broken down into triangular ones. Boundaries and holes will still be preserved. | While this tool operates on any 2D UGrid, it requires that the grid be fully triangulated. To accomodate this, the tool will generate a triangulated grid based on the input grid and optimize the triangulated grid instead. This may result in swapped interior edges and non-triangular cells being broken down into triangular ones. Boundaries and holes will still be preserved. | ||
The optimizer requires that either the ''Timeout'' option, number of ''Iterations'' option, or both be set to a nonzero value to ensure it converges. If the chosen values prove too low, it is possible to resume the optimization where it left off to save time. To resume optimization, run the tool again and use the previous output grid as the new input grid. | |||
====Output Parameters==== | ====Output Parameters==== | ||
* '' | * ''Smoothed grid'' – Name of the output grid. | ||
====Current Location in Toolbox==== | ====Current Location in Toolbox==== | ||
Unstructured Grids/Lloyd | Unstructured Grids/Lloyd Optimizer | ||
{{-}} | {{-}} | ||
<noinclude>[[Category: | <noinclude>[[Category:Toolbox UGrid]]</noinclude> | ||
Latest revision as of 15:36, 24 October 2023
Lloyd Optimizer
The Lloyd Optimizer tool optimizes the angles in a triangular grid to make them close to 60 degrees. It can run for a given time, number of iterations, or until a point no longer moves far. It can also require that all points move far enough.
From CGAL:
This optimization process alternates relocating vertices to the center of mass of their Voronoi cells, and updating the Delaunay connectivity of the triangulation. The center of mass is computed with respect to a sizing function that was designed to preserve the local density of points in the grid...
Input Parameters
- Input grid – A UGrid containing triangles to optimize.
- Number of iterations to perform – The maximum number of iterations to perform before stopping. Can be set to 0 for no limit.
- Maximum duration, in seconds – The maximum amount of time to optimize for, in seconds. Set to "0" for no limit.
- Minimum movement ratio – Fraction of the length of a vertex's shortest incident edge by which it must move during an iteration. If an iteration would move the vertex by less than this amount, then movement of the vertex will be skipped during this iteration. Other vertices may still move during the iteration, and the skipped vertex may be moved during a later iteration if the vertex gets a larger proposed move. This can be useful to prevent the optimizer from spending time moving vertices by tiny amounts. It should be a value between 0 and 1. A value of 0 will disable this condition.
- Freeze ratio – Similar to Move ratio, except that the optimization will stop rather than skip the move.
Additional Notes
The optimizer will not move points on boundary polygons or the boundaries of holes.
During development, points were observed moving across boundaries in some cases. This issue can no longer be reproduced, which prevents understanding the underlying cause and verifying that it is truly resolved. To be on the safe side, the tool will delete any points that migrate across boundaries during optimization.
While this tool operates on any 2D UGrid, it requires that the grid be fully triangulated. To accomodate this, the tool will generate a triangulated grid based on the input grid and optimize the triangulated grid instead. This may result in swapped interior edges and non-triangular cells being broken down into triangular ones. Boundaries and holes will still be preserved.
The optimizer requires that either the Timeout option, number of Iterations option, or both be set to a nonzero value to ensure it converges. If the chosen values prove too low, it is possible to resume the optimization where it left off to save time. To resume optimization, run the tool again and use the previous output grid as the new input grid.
Output Parameters
- Smoothed grid – Name of the output grid.
Current Location in Toolbox
Unstructured Grids/Lloyd Optimizer
