Template:Relax UGrid Points

Relax UGrid Points

The Relax UGrid Points' tool adjusts point locations attempting to improve the quality of connected triangle cells. Usually the overall quality of the grid will improve but not in all cases. Some examples are of the tool are shown below.

Input parameters

• UGrid – Select the grid in the project that will have its points relaxed.
• Relaxation method – Select the desired relaxation method.
  • "Area" – This method calculates the new location of a particular point by finding the centroid and area of all surrounding triangles and then computing a new location that is the weighted average of the triangle centroids. The weights are determined by the triangle area divided by the total area of all triangles connected to the point.
  • "Angle" – This method attempts to make all the angles connected to a point equal. The new location is calculated such that the difference between connected angles is minimized.
  • "Spring" – This method uses a size function (desired edge length) and spring force equation to move a point to the location that best satisfies the size function.
  • "Lloyd" – This method is similar to area relax but seeks to move the particular point to the centroid of the voronoi polygon. It is recommended to use the “Optimize triangulation” when using the Lloyd relaxation option.

    See Wikipedia Lloyd’s algorithm - Lloyd's algorithm

    Implemented with guidelines from “Efficient mesh optimization schemes base on Optimal Delaunay Triangulations” Chen, Holst 2011)

• Number of iterations – The number of iterations to perform with the relaxation method
• Convergence distance – Early termination of the tool will occur if the maximum distance any point moves during an iteration is less than the convergence distance.
• Locked points dataset – A dataset where any nonzero value indicates that the point/node is locked and will not have its location adjusted by the tool.
• Spring relax size dataset – A dataset indicating the desired edge size at each point/node in the grid. This dataset must be specified if the relaxation method is “Spring”.
• Optimize triangulation – Before each smoothing step the triangles are checked to ensure they meet the Delaunay criteria. Any triangles that are not Delaunay compliant will be adjusted to satisfy the Delaunay criteria.

Output parameters

• Relaxed output grid name – Name of the output grid produced by the tool.

Outline of the tool algorithm

A basic outline of the algorithm is as follows:

1. Build a list of all triangles in the input grid
2. If optimizing the triangulation
   • Ensure triangles satisfy Delaunay criterion
3. Compute the initial quality of all triangles
4. Ensure that all boundary points are locked (they may not move)
5. For each iteration
   1. Compute the new location of all points using the specified method
   2. Check if the new locations will create any invalid triangles
      • If invalid triangles are created then calculate new locations that are half the distance to the previous new locations and check again for invalid triangles
   3. Check for convergence if the maximum distance moved by any point is less than the convergence distance
   4. If convergence is not met and optimizing triangulation, optimize the triangles
6. Compute final triangle quality
7. Create the output grid

Discussion

Which smoothing option should I use? The answer to this question almost always depends on the particular application. The following are guidelines to help answer that question.

• Area relaxation and Lloyd relaxation produce similar results. Lloyd relaxation will typically move the points further from their original locations than area. This may be desirable in some application.
• Angle relaxation often gives better results than area relaxation when there is considerable area difference between triangles connected at a given point.
• Spring relaxation makes the most sense to use when the grid/mesh has been developed using a size function for the domain. Additionally, the boundaries used to generate the grid/mesh should be consistent with the size function.

Examples

Example 1

This example shows a grid with a uniform boundary spacing (5.0) with distribution of points on the interior.

• In this example, all of the relaxation methods perform well. The overall final cell/element quality is extremely high and the grids would be satisfactory for numerical analysis.

Example 1 Figure 1

Area relax results with 5 iterations

Quality	Min	Median	Mean	Std. Dev.
Initial Rr	0.286	0.903	0.843	0.161
Final Rr	0.853	0.991	0.982	0.023

Example 1 Figure 2

Angle relax results with 5 iterations

Quality	Min	Median	Mean	Std. Dev.
Initial Rr	0.286	0.903	0.843	0.161
Final Rr	0.853	0.989	0.983	0.023

Example 1 Figure 3

Spring relax results with 5 iterations and constant size function of 5.0

Quality	Min	Median	Mean	Std. Dev.
Initial Rr	0.286	0.903	0.843	0.161
Final Rr	0.853	0.988	0.981	0.025

Example 1 Figure 4

Lloyd relax results with 5 iterations

Quality	Min	Median	Mean	Std. Dev.
Initial Rr	0.286	0.903	0.843	0.161
Final Rr	0.855	0.989	0.980	0.025

Example 1 Figure 5

Example 2

This example shows a grid with a uniform boundary spacing (5.0) with dense distribution of points near the center of the grid.

Example 2 Figure 1

Area relax results with 5 iterations

Quality	Min	Median	Mean	Std. Dev.
Initial Rr	0.392	0.853	0.812	0.155
Final Rr	0.538	0.904	0.872	0.110

Example 2 Figure 2

Angle relax results with 5 iterations

Quality	Min	Median	Mean	Std. Dev.
Initial Rr	0.392	0.853	0.812	0.155
Final Rr	0.376	0.928	0.889	0.117

Example 2 Figure 3

Spring relax results with 5 iterations.

• Size function computed from the initial point spacing.
• Notice that the minimum quality metric decreased; the cell with the worst quality has become even worse.

Quality	Min	Median	Mean	Std. Dev.
Initial Rr	0.392	0.853	0.812	0.155
Final Rr	0.358	0.935	0.881	0.136

Example 2 Figure 4

Lloyd relax results with 5 iterations

Quality	Min	Median	Mean	Std. Dev.
Initial Rr	0.392	0.853	0.812	0.155
Final Rr	0.394	0.872	0.831	0.144

Example 2 Figure 5

Lloyd relax results with 5 iterations and optimize triangulation turned on.

Quality	Min	Median	Mean	Std. Dev.
Initial Rr	0.392	0.853	0.812	0.155
Final Rr	0.582	0.939	0.915	0.082

Example 2 Figure 6

Example 3

This example shows a grid with a non-uniform boundary spacing. Note the longer boundary edge of the cell within the red box in the image below.

Example 3 Figure 1

Area relax results with 5 iterations.

• The overall quality of the grid improves slightly. However, notice that the minimum quality metric has decreased; the cell with the worst quality has become even worse.

Quality	Min	Median	Mean	Std. Dev.
Initial Rr	0.371	0.921	0.899	0.093
Final Rr	0.267	0.928	0.902	0.102

Example 3 Figure 2

Angle relax results with 5 iterations

• Similar to area relax. The overall quality of the grid improves slightly. However, notice that the minimum quality metric has decreased; the cell with the worst quality has become even worse.

Quality	Min	Median	Mean	Std. Dev.
Initial Rr	0.371	0.921	0.899	0.093
Final Rr	0.264	0.924	0.901	0.103

Example 3 Figure 3

Spring relax results with 5 iterations and a size function computed from the initial point spacing

• This is difficult problem for the spring relax to solve because of the constrained boundary. Ideally, the boundary would be consistent with an overall size function that would be applied during the meshing process.

Quality	Min	Median	Mean	Std. Dev.
Initial Rr	0.371	0.921	0.899	0.093
Final Rr	0.092	0.923	0.897	0.115

Example 3 Figure 4

Lloyd relax results with 5 iterations and optimize triangulation turned on.

• Similar to area relax. The overall quality of the grid improves slightly. However, notice that the minimum quality metric has decreased; the cell with the worst quality has become even worse.

Quality	Min	Median	Mean	Std. Dev.
Initial Rr	0.371	0.921	0.899	0.093
Final Rr	0.239	0.947	0.920	0.101

Example 3 Figure 5

Example 4

This example shows a grid with fairly uniform boundary spacing and an internal feature that will be preserved using the locked nodes feature. The locked nodes are shown with dark red symbols.

Example 4 Figure 1

Area relax results with 5 iterations.

Quality	Min	Median	Mean	Std. Dev.
Initial Rr	0.122	0.792	0.736	0.201
Final Rr	0.544	0.899	0.878	0.093

Example 4 Figure 2

Angle relax results with 5 iterations

Quality	Min	Median	Mean	Std. Dev.
Initial Rr	0.122	0.792	0.736	0.201
Final Rr	0.522	0.913	0.889	0.087

Example 4 Figure 3

Spring relax results with 5 iterations and a size function computed from the initial point spacing

Quality	Min	Median	Mean	Std. Dev.
Initial Rr	0.122	0.792	0.736	0.201
Final Rr	0.500	0.909	0.883	0.096

Example 4 Figure 4

Lloyd relax results with 5 iterations and optimize triangulation turned on.

Quality	Min	Median	Mean	Std. Dev.
Initial Rr	0.122	0.792	0.736	0.201
Final Rr	0.590	0.927	0.898	0.091

Example 4 Figure 5