Archived issue #0030892
Modeling Algorithms - Improve Extrema_ExtPS algorithm by unifying the GRAD and TREE methods
Description
It is suggested to unify the GRAD and TREE algorithms of Extrema_ExtPS for looking for only the minimal/maximal distance between the point and surface.
Complete unification does not look possible, as in some cases all extrema solutions are required, so option such FindAllSolutions might be present.
Such unification may improve quality and performance of the Point-Surface Extrema algorithm and greatly simplify its usage.
Complete unification does not look possible, as in some cases all extrema solutions are required, so option such FindAllSolutions might be present.
Such unification may improve quality and performance of the Point-Surface Extrema algorithm and greatly simplify its usage.
Public activity
33 archived notes
Participants are labeled by their role within this record.
Branch [archived branch] has been created by Author.
[revision removed]
Detailed log of new commits:
Author: Author
Date: Mon Aug 19 08:41:04 2019 +0300
0030892: Improve Extrema_ExtPS algorithm by unifying the GRAD and TREE methods
Refactoring of the Extrema_GenExtPS class in order to improve performance and robustness of the algorithm by unifying the GRAD and TREE search methods.
[revision removed]
Detailed log of new commits:
Author: Author
Date: Mon Aug 19 08:41:04 2019 +0300
0030892: Improve Extrema_ExtPS algorithm by unifying the GRAD and TREE methods
Refactoring of the Extrema_GenExtPS class in order to improve performance and robustness of the algorithm by unifying the GRAD and TREE search methods.
Branch [archived branch] has been updated forcibly by Author.
[revision removed]
[revision removed]
Branch [archived branch] has been updated forcibly by Author.
[revision removed]
[revision removed]
Branch [archived branch] has been updated by Author.
[revision removed]
Detailed log of new commits:
Author: Author
Date: Fri Sep 13 13:55:52 2019 +0300
# Decrease the box of the sample to make BVH tree more effective.
# Use extreme MIN target in ProjLib_CompProjectedCurve.
[revision removed]
Detailed log of new commits:
Author: Author
Date: Fri Sep 13 13:55:52 2019 +0300
# Decrease the box of the sample to make BVH tree more effective.
# Use extreme MIN target in ProjLib_CompProjectedCurve.
Branch [archived branch] has been updated forcibly by Author.
[revision removed]
[revision removed]
Branch [archived branch] has been updated forcibly by Author.
[revision removed]
[revision removed]
Branch [archived branch] has been updated forcibly by Author.
[revision removed]
[revision removed]
Branch [archived branch] has been updated by Author.
[revision removed]
Detailed log of new commits:
Author: Author
Date: Thu May 21 10:05:05 2020 +0300
# fixing errors on linux and MacOS
[revision removed]
Detailed log of new commits:
Author: Author
Date: Thu May 21 10:05:05 2020 +0300
# fixing errors on linux and MacOS
Branch [archived branch] has been created by Author.
[revision removed]
Detailed log of new commits:
Author: Author
Date: Mon Aug 19 08:41:04 2019 +0300
0030892: Improve Extrema_ExtPS algorithm by unifying the GRAD and TREE methods
Refactoring of the Extrema_GenExtPS class in order to improve performance and robustness of the algorithm by unifying the GRAD and TREE search methods.
[revision removed]
Detailed log of new commits:
Author: Author
Date: Mon Aug 19 08:41:04 2019 +0300
0030892: Improve Extrema_ExtPS algorithm by unifying the GRAD and TREE methods
Refactoring of the Extrema_GenExtPS class in order to improve performance and robustness of the algorithm by unifying the GRAD and TREE search methods.
Branch [archived branch] has been updated forcibly by Author.
[revision removed]
[revision removed]
Branch [archived branch] has been updated by Author.
[revision removed]
Detailed log of new commits:
Author: Author
Date: Wed May 27 10:10:00 2020 +0300
# revert increase of a box of a max corner cell.
[revision removed]
Detailed log of new commits:
Author: Author
Date: Wed May 27 10:10:00 2020 +0300
# revert increase of a box of a max corner cell.
Branch [archived branch] has been updated by Author.
[revision removed]
Detailed log of new commits:
Author: Author
Date: Wed May 27 16:42:36 2020 +0300
# Perform localized extrema search in ComputeApproxOnPolarSurface
[revision removed]
Detailed log of new commits:
Author: Author
Date: Wed May 27 16:42:36 2020 +0300
# Perform localized extrema search in ComputeApproxOnPolarSurface
Branch [archived branch] has been updated by Author.
[revision removed]
Detailed log of new commits:
Author: Author
Date: Thu May 28 11:41:34 2020 +0300
# cosmetics
[revision removed]
Detailed log of new commits:
Author: Author
Date: Thu May 28 11:41:34 2020 +0300
# cosmetics
Branch [archived branch] has been updated forcibly by Author.
[revision removed]
[revision removed]
Branch [archived branch] has been updated by Author.
[revision removed]
Detailed log of new commits:
Author: Author
Date: Fri May 29 11:55:09 2020 +0300
# cosmetics.
[revision removed]
Detailed log of new commits:
Author: Author
Date: Fri May 29 11:55:09 2020 +0300
# cosmetics.
Branch [archived branch] has been updated forcibly by Author.
[revision removed]
[revision removed]
Branch [archived branch] has been updated forcibly by Author.
[revision removed]
[revision removed]
Branch [archived branch] has been updated forcibly by Author.
[revision removed]
[revision removed]
Branch [archived branch] has been updated forcibly by Author.
[revision removed]
[revision removed]
Branch [archived branch] has been updated by Author.
[revision removed]
Detailed log of new commits:
Author: Author
Date: Thu Aug 27 12:30:45 2020 +0300
# use std::vector in Extrema_FuncPSNorm
# Minimize the grid cell bounding box
[revision removed]
Detailed log of new commits:
Author: Author
Date: Thu Aug 27 12:30:45 2020 +0300
# use std::vector in Extrema_FuncPSNorm
# Minimize the grid cell bounding box
Branch [archived branch] has been updated forcibly by Author.
[revision removed]
[revision removed]
Branch [archived branch] has been created by Author.
[revision removed]
Detailed log of new commits:
Author: Author
Date: Mon Aug 19 08:41:04 2019 +0300
0030892: Improve Extrema_ExtPS algorithm by unifying the GRAD and TREE methods
Refactoring of the Extrema_GenExtPS class in order to improve performance and robustness of the algorithm by unifying the GRAD and TREE search methods.
[revision removed]
Detailed log of new commits:
Author: Author
Date: Mon Aug 19 08:41:04 2019 +0300
0030892: Improve Extrema_ExtPS algorithm by unifying the GRAD and TREE methods
Refactoring of the Extrema_GenExtPS class in order to improve performance and robustness of the algorithm by unifying the GRAD and TREE search methods.
Branch [archived branch] has been updated forcibly by Author.
[revision removed]
[revision removed]
Branch [archived branch] has been updated forcibly by Author.
[revision removed]
[revision removed]
Branch [archived branch] has been updated forcibly by Author.
[revision removed]
[revision removed]
I have made some experiments on current version of the fix against master and CR26166, here are results.
1. Translation of large STEP files
DRAW commands:
pload ALL
autodisplay 0
chrono s restart
stepread [locate_data_file LP1.stp] a *
chrono s stop show
The reported time is CPU time in seconds.
File | master | CR26166 | CR30892
--------|--------|---------|---------
LP1.stp | 21.6 | 32 | 21.6
LP2.stp | 74.9 | 70.2 | 63.8
LP3.stp | 910 | 711 | 867
2. Tests from branch CR26166
Test | master | CR26166 | CR30892
-------------------|--------|---------|--------
perf heal pcurves1 | 9.86 | 2.1 | 4.2
perf heal pcurves2 | 3.94 | 2.3 | 1.9
1. Translation of large STEP files
DRAW commands:
pload ALL
autodisplay 0
chrono s restart
stepread [locate_data_file LP1.stp] a *
chrono s stop show
The reported time is CPU time in seconds.
File | master | CR26166 | CR30892
--------|--------|---------|---------
LP1.stp | 21.6 | 32 | 21.6
LP2.stp | 74.9 | 70.2 | 63.8
LP3.stp | 910 | 711 | 867
2. Tests from branch CR26166
Test | master | CR26166 | CR30892
-------------------|--------|---------|--------
perf heal pcurves1 | 9.86 | 2.1 | 4.2
perf heal pcurves2 | 3.94 | 2.3 | 1.9
In addition, I have run tests in single thread, comparing master and CR30892_2.
Here are test cases where CPU regressions are noticed:
CPU bugs moddata_3 bug27534: 14.046875 / 2.9375 [+378.19%]
CPU de step_3 F2: 17.4375 / 14.328125 [+21.70%]
CPU de step_4 I1: 15.75 / 13.484375 [+16.80%]
Note: OCCT was built with VS 2019, 64 bit Release indeed; run on CPU i5-8600, 6 cores
Here are test cases where CPU regressions are noticed:
CPU bugs moddata_3 bug27534: 14.046875 / 2.9375 [+378.19%]
CPU de step_3 F2: 17.4375 / 14.328125 [+21.70%]
CPU de step_4 I1: 15.75 / 13.484375 [+16.80%]
Note: OCCT was built with VS 2019, 64 bit Release indeed; run on CPU i5-8600, 6 cores
Hello Andrey, these are the same cases revealed by jenkins tests.
The last two cases are stable ones, but I cannot reproduce the first one. It works quite fast on my configuration (VS2015, 64 bit Release):
TOTAL CPU TIME: 0.03125 sec.
The last two cases are stable ones, but I cannot reproduce the first one. It works quite fast on my configuration (VS2015, 64 bit Release):
TOTAL CPU TIME: 0.03125 sec.
I betlieve the reason of difference on test case bugs moddata_3 bug27534 is that I build with VS 2019 (vc142)
Igor,
Could you check can we have it in 7.5.0 or it requires additional testing...
Could you check can we have it in 7.5.0 or it requires additional testing...
Dear Sergey,
In my opinion this issue required additional investigations:
1. Bad performance of bugs moddata_3 bug27534, which is in test result of CR30892_2-CR30892-emv for Windows platform. Really this test is not quite correct, because for projection of curve on surface abnormally large tolerance = 0.2 is used. May be it causes some kind of numerical instability in new algorithm.
2. Possible lost of functionality: in mode GRAD and, for example flag MIN, old algorithm theoretically can produce all local minimal distances between point and surface. New algorithm cannot reproduce the same results. It can cause regressions in any customer applications.
3. If we want to improve performance, it would be interesting to test using math_PSO instead of BVH for seaching first approximation of global minimal distance (similar to extrema curve-surface)
In my opinion this issue required additional investigations:
1. Bad performance of bugs moddata_3 bug27534, which is in test result of CR30892_2-CR30892-emv for Windows platform. Really this test is not quite correct, because for projection of curve on surface abnormally large tolerance = 0.2 is used. May be it causes some kind of numerical instability in new algorithm.
2. Possible lost of functionality: in mode GRAD and, for example flag MIN, old algorithm theoretically can produce all local minimal distances between point and surface. New algorithm cannot reproduce the same results. It can cause regressions in any customer applications.
3. If we want to improve performance, it would be interesting to test using math_PSO instead of BVH for seaching first approximation of global minimal distance (similar to extrema curve-surface)
See remarks of Igor.
Branch [archived branch] has been created by Author.
[revision removed]
Detailed log of new commits:
Author: Author
Date: Fri Oct 2 08:15:31 2020 +0300
# revert changes in ProjLib_ComputeApproxOnPolarSurface just for testing.
Author: Author
Date: Fri Sep 18 13:06:08 2020 +0300
# compute all grid points in a single pass to avoid cache rebuild on BSpline surfaces.
# use iterator for array initialization with default distance values.
Author: Author
Date: Mon Aug 19 08:41:04 2019 +0300
0030892: Improve Extrema_ExtPS algorithm by unifying the GRAD and TREE methods
Refactoring of the Extrema_GenExtPS class in order to improve performance and robustness of the algorithm by unifying the GRAD and TREE search methods.
[revision removed]
Detailed log of new commits:
Author: Author
Date: Fri Oct 2 08:15:31 2020 +0300
# revert changes in ProjLib_ComputeApproxOnPolarSurface just for testing.
Author: Author
Date: Fri Sep 18 13:06:08 2020 +0300
# compute all grid points in a single pass to avoid cache rebuild on BSpline surfaces.
# use iterator for array initialization with default distance values.
Author: Author
Date: Mon Aug 19 08:41:04 2019 +0300
0030892: Improve Extrema_ExtPS algorithm by unifying the GRAD and TREE methods
Refactoring of the Extrema_GenExtPS class in order to improve performance and robustness of the algorithm by unifying the GRAD and TREE search methods.
Related records