Internal:Adaptive CDT3D - Smoothing: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
|||
| (7 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
= Current Approach = | |||
The current (as of 2019) approach of the '''adaptive''' code is vertex based smoothing. Similar code to the one we use in | |||
boundary recovery. | |||
= Original Approach = | |||
Original CDT3D approach was a element based global smoothing | |||
= NASA/refine = | = NASA/refine = | ||
== Pseudocode == | == Pseudocode == | ||
'' We solve the nonsmooth optimization problem | '' We solve the nonsmooth optimization problem... | ||
Using this information, we can predict the points at which the active set A will change by | ...Using this information, we can predict the points at which the active set A will change by | ||
computing the intersection of each linear approximation with the pro jection of the current | computing the intersection of each linear approximation with the pro jection of the current | ||
active function in the search direction. | active function in the search direction. The distance to the nearest intersection point from the current location gives the initial step length, a. | ||
The distance to the nearest intersection point from the current location gives the initial step length, a. | '' | ||
'' The initial step is accepted if the actual improvement exceeds 90 percent of the estimated improvement or the subsequent step results in a smaller function improvement. Otherwise is halved recursively until a step is accepted or falls below some minimum step length tolerance.'' | |||
The initial step is accepted if the actual | |||
improvement exceeds 90 percent of the estimated improvement or the subsequent step results | |||
in a smaller function improvement. Otherwise is halved recursively until a step is accepted | |||
or falls below some minimum step length tolerance.'' | |||
1. Evaluate the degree of the node and collect adajcent cells | 1. Evaluate the degree of the node and collect adajcent cells | ||
| Line 17: | Line 19: | ||
4. If number of active elements >= 4 exit | 4. If number of active elements >= 4 exit | ||
4.1 else if number of active elements ==1 set dir=grad[worst] | 4.1 else if number of active elements ==1 set dir=grad[worst] | ||
4.2 else use Charalambous and Conn approach <ref> An Efficient Method to Solve the Minmax Problem Directly, C. Charalambous and A. R. Conn, https://epubs.siam.org/doi/abs/10.1137/0715011,http://www.cs.odu.edu/crtc/internal/Christos/Charalambous_An_Efficient_Method_To_Solve_The_Minmax_problem_directly.pdf </ref> to find best dir | 4.2 else use Charalambous and Conn approach <ref> An Efficient Method to Solve the Minmax Problem Directly, C. Charalambous and A. R. Conn, [https://epubs.siam.org/doi/abs/10.1137/0715011],[http://www.cs.odu.edu/crtc/internal/Christos/Charalambous_An_Efficient_Method_To_Solve_The_Minmax_problem_directly.pdf] </ref> to find best dir | ||
5. set m0 = dot(dir,grad[worst]) | 5. set m0 = dot(dir,grad[worst]) | ||
6. find stepsize alpha: | 6. find stepsize alpha: | ||
| Line 26: | Line 28: | ||
///to approximate all of the quality functions as lines, | ///to approximate all of the quality functions as lines, | ||
//so we will have to do a line search to find our ultimate | //so we will have to do a line search to find our ultimate | ||
//step size. <ref> Tetrahedral Mesh Improvement Using Swapping and Smoothing, Lori A. Freitag and Carl Ollivier-Gooch, https://onlinelibrary.wiley.com/doi/abs/10.1002/%28SICI%291097-0207%2819971115%2940%3A21%3C3979%3A%3AAID-NME251%3E3.0.CO%3B2-9, http://www.cs.odu.edu/crtc/internal/Christos/Freitag_et_al-1997-International_Journal_for_Numerical_Methods_in_Engineering.pdf </ref> | //step size. <ref> Tetrahedral Mesh Improvement Using Swapping and Smoothing, Lori A. Freitag and Carl Ollivier-Gooch, [https://onlinelibrary.wiley.com/doi/abs/10.1002/%28SICI%291097-0207%2819971115%2940%3A21%3C3979%3A%3AAID-NME251%3E3.0.CO%3B2-9], [http://www.cs.odu.edu/crtc/internal/Christos/Freitag_et_al-1997-International_Journal_for_Numerical_Methods_in_Engineering.pdf] </ref> | ||
7. compute the approximation of when this funnction will become the objective / | 7. compute the approximation of when this funnction will become the objective / | ||
8. for each non active incident : alpha = (quals[worst] - quals[i]) / (m1 - m0); min(min_alpha,alpha) | 8. for each non active incident : alpha = (quals[worst] - quals[i]) / (m1 - m0); min(min_alpha,alpha) | ||
| Line 36: | Line 38: | ||
''' Code ''' : https://github.com/nasa/refine/blob/master/src/ref_smooth.c#L1258 | ''' Code ''' : https://github.com/nasa/refine/blob/master/src/ref_smooth.c#L1258 | ||
= 27th IMR = | |||
'' We evaluate the vertex quality function with a greedy algorithm on a discretized domain. No derivatives are necessary which allows easy replacement of the quality metric '' | |||
See page 6 figures and page 7 algorithm 2 <ref> Discrete Mesh Optimization on GPU, Daniel Zint and Roberto Grosso [https://project.inria.fr/imr27/files/2018/09/1003.pdf] </ref> | |||
= References = | |||
Latest revision as of 14:32, 4 September 2019
Current Approach
The current (as of 2019) approach of the adaptive code is vertex based smoothing. Similar code to the one we use in boundary recovery.
Original Approach
Original CDT3D approach was a element based global smoothing
NASA/refine
Pseudocode
We solve the nonsmooth optimization problem... ...Using this information, we can predict the points at which the active set A will change by computing the intersection of each linear approximation with the pro jection of the current active function in the search direction. The distance to the nearest intersection point from the current location gives the initial step length, a. The initial step is accepted if the actual improvement exceeds 90 percent of the estimated improvement or the subsequent step results in a smaller function improvement. Otherwise is halved recursively until a step is accepted or falls below some minimum step length tolerance.
1. Evaluate the degree of the node and collect adajcent cells 2. For each attached cell evaluate quality and gradient of quality as well as min quality of set. 3. activate tets that (quals[i]-quals[worst]) < 1e-12 4. If number of active elements >= 4 exit 4.1 else if number of active elements ==1 set dir=grad[worst] 4.2 else use Charalambous and Conn approach [1] to find best dir 5. set m0 = dot(dir,grad[worst]) 6. find stepsize alpha: //for our initial step size, we use the distance //to the next intersection with another quality funtion. //this is the point at which the other quality function ///becomes the worst. we use a single-term taylor expansion ///to approximate all of the quality functions as lines, //so we will have to do a line search to find our ultimate //step size. [2] 7. compute the approximation of when this funnction will become the objective / 8. for each non active incident : alpha = (quals[worst] - quals[i]) / (m1 - m0); min(min_alpha,alpha) 9. if min_alpha didn’t change min_alpha = (1.0 - quals[0]) / ref_math_dot(dir, &(grads[3 * 0])) 10. for (i = 1; i < degree; i++) min_alpha = MIN(min_alpha, (1.0 - quals[i]) / ref_math_dot(dir, &(grads[3 * i]))); 11. line serach as descriped above : 11.1 find smallest dot product between dir and grad of active elements (m0 in refine) 11.2 Do at most 8 loops of linear walk to optimize quality of cavity
Code : https://github.com/nasa/refine/blob/master/src/ref_smooth.c#L1258
27th IMR
We evaluate the vertex quality function with a greedy algorithm on a discretized domain. No derivatives are necessary which allows easy replacement of the quality metric
See page 6 figures and page 7 algorithm 2 [3]