Archived issue #0025929
Make Approx_ComputeLine algorithm adaptive
Description
Now Approx_ComputeLine make bezier curve on 30 points regardless of their curvature and distribution. After this algorithm sew them into one bspline curve.
It is necessary to improve this algorithm to choose points of bezier curve more wisely, to get more simple output bspline curve.
It is necessary to improve this algorithm to choose points of bezier curve more wisely, to get more simple output bspline curve.
Steps to reproduce
---- PROBLEM # 1
One of examples, when approximation algorithm fails is "bugs modalg_5 bug24915" test case (after the fix, this script should be updated to IMPROVE).
The fragment of the WLine:
----------- D u m p I n t P a t c h _ W L i n e --------------
Num [X Y Z] [U1 V1] [U2 V2]
...
270 [[phone removed]40000 -4.81467964191310390000 [phone removed]00000] [[phone removed]50000 [phone removed]90000] [[phone removed]60000 -0.16473900943604278000]
271 [[phone removed]30000 -4.86289890083316930000 [phone removed]00000] [[phone removed]40000 [phone removed]52000] [[phone removed]30000 -0.14921541759025503000]
272 [[phone removed]80000 -4.91113704279707970000 [phone removed]00000] [[phone removed]90000 [phone removed]76000] [[phone removed]90000 -0.13345356306381939000]
273 [[phone removed]70000 -4.95949041229089540000 [phone removed]00000] [[phone removed]30000 [phone removed]75000] [[phone removed]70000 -0.11736976847892722000]
274 [[phone removed]80000 -5.00804768146907620000 [phone removed]00000] [[phone removed]20000 [phone removed]34000] [[phone removed]50000 -0.10085865624392509000]
275 [[phone removed]00000 -5.05697368972781640000 [phone removed]00000] [[phone removed]90000 [phone removed]94000] [[phone removed]20000 -0.08374979795370673900]
276 [[phone removed]58000 -5.10653496951993800000 [phone removed]00000] [[phone removed]40000 [phone removed]56000] [[phone removed]10000 -0.06576873645070424600]
277 [[phone removed]42000 -5.15713415452643800000 [phone removed]00000] [[phone removed]10000 [phone removed]81000] [[phone removed]00000 -0.04646582436343127400]
...
579 [[phone removed]00000 -52.53774058421905100000 [phone removed]00000] [[phone removed]90000 [phone removed]00000] [[phone removed]10000 [phone removed]00000]
----------- IntPatch_Point :
P( 25.9518819125, 7.8014976062, -0.4356946734) UV1( 3.1415926536, 2.3588491912) UV2( 1.4975014128, -2.3565588358) (Para: 1.0000000000)
----> IntSurf_PntOn2S : 1 Pnt (25.9518819124648,7.80149760621922,-0.435694673408663)
----------- IntPatch_Point :
P( 13.9651264120, -52.5377405842, 16.5453999239) UV1( 4.9514291941, 50.0000000000) UV2( 2.9815398370, 49.9998920003) (Para: 579.0000000000)
However, it is approximated WORSE (only 3D-curve is approximated, 2D-curves are excluded):
#Take point # 276 from WLine
Draw[]> proj c_1 [phone removed]58000 -5.10653496951993800000 [phone removed]00000
# parameter 1 = 0.80708806952489476
#ext_1
Draw[]> length ext_1
#The length ext_1 is 3.[revision removed]-005
A good value must be less than 1.e-7.
See Attachment 1 (PNG) file attached.
---- PROBLEM # 2
In addition, see message [archived tracker link removed]
---- PROBLEM # 3
Test case bugs modalg_6 bug26310_4
One of examples, when approximation algorithm fails is "bugs modalg_5 bug24915" test case (after the fix, this script should be updated to IMPROVE).
The fragment of the WLine:
----------- D u m p I n t P a t c h _ W L i n e --------------
Num [X Y Z] [U1 V1] [U2 V2]
...
270 [[phone removed]40000 -4.81467964191310390000 [phone removed]00000] [[phone removed]50000 [phone removed]90000] [[phone removed]60000 -0.16473900943604278000]
271 [[phone removed]30000 -4.86289890083316930000 [phone removed]00000] [[phone removed]40000 [phone removed]52000] [[phone removed]30000 -0.14921541759025503000]
272 [[phone removed]80000 -4.91113704279707970000 [phone removed]00000] [[phone removed]90000 [phone removed]76000] [[phone removed]90000 -0.13345356306381939000]
273 [[phone removed]70000 -4.95949041229089540000 [phone removed]00000] [[phone removed]30000 [phone removed]75000] [[phone removed]70000 -0.11736976847892722000]
274 [[phone removed]80000 -5.00804768146907620000 [phone removed]00000] [[phone removed]20000 [phone removed]34000] [[phone removed]50000 -0.10085865624392509000]
275 [[phone removed]00000 -5.05697368972781640000 [phone removed]00000] [[phone removed]90000 [phone removed]94000] [[phone removed]20000 -0.08374979795370673900]
276 [[phone removed]58000 -5.10653496951993800000 [phone removed]00000] [[phone removed]40000 [phone removed]56000] [[phone removed]10000 -0.06576873645070424600]
277 [[phone removed]42000 -5.15713415452643800000 [phone removed]00000] [[phone removed]10000 [phone removed]81000] [[phone removed]00000 -0.04646582436343127400]
...
579 [[phone removed]00000 -52.53774058421905100000 [phone removed]00000] [[phone removed]90000 [phone removed]00000] [[phone removed]10000 [phone removed]00000]
----------- IntPatch_Point :
P( 25.9518819125, 7.8014976062, -0.4356946734) UV1( 3.1415926536, 2.3588491912) UV2( 1.4975014128, -2.3565588358) (Para: 1.0000000000)
----> IntSurf_PntOn2S : 1 Pnt (25.9518819124648,7.80149760621922,-0.435694673408663)
----------- IntPatch_Point :
P( 13.9651264120, -52.5377405842, 16.5453999239) UV1( 4.9514291941, 50.0000000000) UV2( 2.9815398370, 49.9998920003) (Para: 579.0000000000)
However, it is approximated WORSE (only 3D-curve is approximated, 2D-curves are excluded):
#Take point # 276 from WLine
Draw[]> proj c_1 [phone removed]58000 -5.10653496951993800000 [phone removed]00000
# parameter 1 = 0.80708806952489476
#ext_1
Draw[]> length ext_1
#The length ext_1 is 3.[revision removed]-005
A good value must be less than 1.e-7.
See Attachment 1 (PNG) file attached.
---- PROBLEM # 2
In addition, see message [archived tracker link removed]
---- PROBLEM # 3
Test case bugs modalg_6 bug26310_4
Additional information
Implementation based on
A Heuristic Knot Placement Algorithm for B-Spline Curve Approximation
Weishi Lia, Shuhong Xub, Gang Zhaoc & Li Ping Gohd (http://www.tandfonline.com/doi/abs/10.1080/16864360.2004.10738319?journalCode=tcad20#.VlWcKL_bDRY)
A Heuristic Knot Placement Algorithm for B-Spline Curve Approximation
Weishi Lia, Shuhong Xub, Gang Zhaoc & Li Ping Gohd (http://www.tandfonline.com/doi/abs/10.1080/16864360.2004.10738319?journalCode=tcad20#.VlWcKL_bDRY)
Public activity
46 archived notes
Participants are labeled by their role within this record.
Dear colleagues!
Maybe, problem described in "Steps To Reproduce" cannot be solved in this bug. However, this fix should give necessary tools for solving it (e.g. entering special vertices in Approximation interface).
Maybe, problem described in "Steps To Reproduce" cannot be solved in this bug. However, this fix should give necessary tools for solving it (e.g. entering special vertices in Approximation interface).
Branch [archived branch] has been created by Participant.
[revision removed]
Detailed log of new commits:
Author: aml
Date: Thu Jun 4 13:00:50 2015 +0300
Initial version of de Boor algo.
Author: aml
Date: Thu Jun 4 08:12:19 2015 +0300
0025929: Switch approximation of intersection lines from Approx_ComputeLine to Approx_BSplComputeLine
Refactoring.
[revision removed]
Detailed log of new commits:
Author: aml
Date: Thu Jun 4 13:00:50 2015 +0300
Initial version of de Boor algo.
Author: aml
Date: Thu Jun 4 08:12:19 2015 +0300
0025929: Switch approximation of intersection lines from Approx_ComputeLine to Approx_BSplComputeLine
Refactoring.
Branch [archived branch] has been created by Participant.
[revision removed]
No new revisions were added by this update.
[revision removed]
No new revisions were added by this update.
Branch [archived branch] has been deleted by Participant.
[revision removed]
[revision removed]
Branch [archived branch] has been created by Participant.
[revision removed]
Detailed log of new commits:
Author: ifv
Date: Wed Jun 10 13:07:45 2015 +0300
Adaptive partition of WLine is implemented
[revision removed]
Detailed log of new commits:
Author: ifv
Date: Wed Jun 10 13:07:45 2015 +0300
Adaptive partition of WLine is implemented
Branch [archived branch] has been updated forcibly by Participant.
[revision removed]
[revision removed]
After investigation we observed, that BsplineComputeLine have too bad performance and there is no way improve it. So, it was decided to improve Approx_ComputeLine algorithm.
Branch [archived branch] has been created by Participant.
[revision removed]
Detailed log of new commits:
Author: aml
Date: Mon Jul 13 07:09:07 2015 +0300
Modifications.
Author: ifv
Date: Tue Jul 7 15:17:13 2015 +0300
New method BuildKnots1 for building knots for N-dimension curve
Author: ifv
Date: Wed Jun 10 13:07:45 2015 +0300
Adaptive partition of WLine is implemented
[revision removed]
Detailed log of new commits:
Author: aml
Date: Mon Jul 13 07:09:07 2015 +0300
Modifications.
Author: ifv
Date: Tue Jul 7 15:17:13 2015 +0300
New method BuildKnots1 for building knots for N-dimension curve
Author: ifv
Date: Wed Jun 10 13:07:45 2015 +0300
Adaptive partition of WLine is implemented
Branch [archived branch] has been updated forcibly by Participant.
[revision removed]
[revision removed]
Branch [archived branch] has been updated forcibly by Participant.
[revision removed]
[revision removed]
Branch [archived branch] has been updated forcibly by Participant.
[revision removed]
[revision removed]
Branch [archived branch] has been updated forcibly by Participant.
[revision removed]
[revision removed]
Branch [archived branch] has been updated forcibly by Participant.
[revision removed]
[revision removed]
Branch [archived branch] has been updated forcibly by Participant.
[revision removed]
[revision removed]
Branch [archived branch] has been updated forcibly by Participant.
[revision removed]
[revision removed]
Branch [archived branch] has been updated forcibly by Participant.
[revision removed]
[revision removed]
Branch [archived branch] has been updated forcibly by Participant.
[revision removed]
[revision removed]
Branch [archived branch] has been updated forcibly by Participant.
[revision removed]
[revision removed]
Branch [archived branch] has been updated forcibly by Participant.
[revision removed]
[revision removed]
Branch [archived branch] has been updated forcibly by Participant.
[revision removed]
[revision removed]
Branch [archived branch] has been created by Participant.
[revision removed]
Detailed log of new commits:
Author: aml
Date: Fri Oct 30 12:07:45 2015 +0300
0025929: Make Approx_ComputeLine algorithm adaptive
Adaptive partition algorithm of WLine is implemented and used in ApproxInt_Approx.gxx file.
Refactoring of ApproxInt_Approx class.
Test cases are updated to the new behaviour.
[revision removed]
Detailed log of new commits:
Author: aml
Date: Fri Oct 30 12:07:45 2015 +0300
0025929: Make Approx_ComputeLine algorithm adaptive
Adaptive partition algorithm of WLine is implemented and used in ApproxInt_Approx.gxx file.
Refactoring of ApproxInt_Approx class.
Test cases are updated to the new behaviour.
Branch [archived branch] has been updated forcibly by Participant.
[revision removed]
[revision removed]
Dear msv,
Please check current state of branch CR25929_2 and CR25929 from products repository. Please note that it contains same commits as CR25929 branch but squished into one.
Please check current state of branch CR25929_2 and CR25929 from products repository. Please note that it contains same commits as CR25929 branch but squished into one.
Alexander, please explain the changes made in ShapeFix_ComposeShell.cxx -- they are not described neither in commit message nor in Mantis. In general, I believe that regular introducing of specific hacks and tolerances (like 5e-7 in this case) is poor practice which should be avoided as much as possible.
Andrey, all changes which are out of ApproxInt_Approx and ApproxInt_KnotTools are related to fixing of cases became bad after fix.
This particular case caused by situation when our general tolerances protection failed. We obtained a pair of points with distance more than 1.0e-9, so duplicate handling with tolerance 1.0-9 not deleted one of points. As a result too small edges created, which fail checkshape check.
Formal meaning of this piece of code is to avoid creation of edges fully covered by their vertex tolerances.
This particular case caused by situation when our general tolerances protection failed. We obtained a pair of points with distance more than 1.0e-9, so duplicate handling with tolerance 1.0-9 not deleted one of points. As a result too small edges created, which fail checkshape check.
Formal meaning of this piece of code is to avoid creation of edges fully covered by their vertex tolerances.
src\ApproxInt\ApproxInt_KnotTools.hxx
1) Make the following line the comment of doxygen style:
120: // Perform knots filtration.
src\IntTools\IntTools_FaceFace.cxx
2) This change is dangerous because it is just fitting of the code for one case. It is better to make test case bad (and create a new bug if it makes sense).
src\ShapeFix\ShapeFix_ComposeShell.cxx
3) The choice of tolerance must be justified. I propose to use 2D tolerance computed as resolution of Confusion() from the 3D curve.
1) Make the following line the comment of doxygen style:
120: // Perform knots filtration.
src\IntTools\IntTools_FaceFace.cxx
2) This change is dangerous because it is just fitting of the code for one case. It is better to make test case bad (and create a new bug if it makes sense).
src\ShapeFix\ShapeFix_ComposeShell.cxx
3) The choice of tolerance must be justified. I propose to use 2D tolerance computed as resolution of Confusion() from the 3D curve.
Branch [archived branch] has been created by Participant.
[revision removed]
Detailed log of new commits:
Author: aml
Date: Fri Oct 30 12:07:45 2015 +0300
0025929: Make Approx_ComputeLine algorithm adaptive
Adaptive partition algorithm of WLine is implemented and used in ApproxInt_Approx.gxx file.
Refactoring of ApproxInt_Approx class.
Test cases are updated to the new behaviour.
[revision removed]
Detailed log of new commits:
Author: aml
Date: Fri Oct 30 12:07:45 2015 +0300
0025929: Make Approx_ComputeLine algorithm adaptive
Adaptive partition algorithm of WLine is implemented and used in ApproxInt_Approx.gxx file.
Refactoring of ApproxInt_Approx class.
Test cases are updated to the new behaviour.
Dear msv,
Please check CR25929_3 (rebased on current master + remarks elimination) from occt repository and CR25929 from products repository.
Please check CR25929_3 (rebased on current master + remarks elimination) from occt repository and CR25929 from products repository.
src\IntTools\IntTools_FaceFace.cxx
1) No sense to checkout this file now, revert it please.
src\ShapeFix\ShapeFix_ComposeShell.cxx
2) The line 1385:
aReduceCoeff = anAdaptor.Resolution(aTol3d);
We should protect against bad resolution. For that, do not allow aReduceCoeff to be exceeding (l-f)/2.
1) No sense to checkout this file now, revert it please.
src\ShapeFix\ShapeFix_ComposeShell.cxx
2) The line 1385:
aReduceCoeff = anAdaptor.Resolution(aTol3d);
We should protect against bad resolution. For that, do not allow aReduceCoeff to be exceeding (l-f)/2.
Branch [archived branch] has been updated forcibly by Participant.
[revision removed]
[revision removed]
Branch [archived branch] has been updated by Participant.
[revision removed]
Detailed log of new commits:
Author: aml
Date: Mon Nov 9 15:23:28 2015 +0300
Filtering algorithm improved.
[revision removed]
Detailed log of new commits:
Author: aml
Date: Mon Nov 9 15:23:28 2015 +0300
Filtering algorithm improved.
Branch [archived branch] has been updated by Participant.
[revision removed]
Detailed log of new commits:
Author: aml
Date: Wed Nov 11 08:47:25 2015 +0300
Good behaviour restored.
[revision removed]
Detailed log of new commits:
Author: aml
Date: Wed Nov 11 08:47:25 2015 +0300
Good behaviour restored.
Dear nbv,
I've analyzed results on merged branch CR26431_NBVunion. Maximal tolerance obtained on bend part of intersection curves. It is seems that additional points needed. Could you please investigate cylinder / cylinder intersection algorithm to check this?
I've analyzed results on merged branch CR26431_NBVunion. Maximal tolerance obtained on bend part of intersection curves. It is seems that additional points needed. Could you please investigate cylinder / cylinder intersection algorithm to check this?
Branch [archived branch] has been created by Participant.
[revision removed]
Detailed log of new commits:
Author: aml
Date: Mon Nov 9 15:23:28 2015 +0300
Good behaviour restored.
Filtering algorithm improved.
Author: aml
Date: Fri Oct 30 12:07:45 2015 +0300
0025929: Make Approx_ComputeLine algorithm adaptive
Adaptive partition algorithm of WLine is implemented and used in ApproxInt_Approx.gxx file.
Refactoring of ApproxInt_Approx class.
Test cases are updated to the new behaviour.
[revision removed]
Detailed log of new commits:
Author: aml
Date: Mon Nov 9 15:23:28 2015 +0300
Good behaviour restored.
Filtering algorithm improved.
Author: aml
Date: Fri Oct 30 12:07:45 2015 +0300
0025929: Make Approx_ComputeLine algorithm adaptive
Adaptive partition algorithm of WLine is implemented and used in ApproxInt_Approx.gxx file.
Refactoring of ApproxInt_Approx class.
Test cases are updated to the new behaviour.
Branch [archived branch] has been updated by Participant.
[revision removed]
Detailed log of new commits:
Author: aml
Date: Mon Nov 16 12:57:38 2015 +0300
Filtration improved.
[revision removed]
Detailed log of new commits:
Author: aml
Date: Mon Nov 16 12:57:38 2015 +0300
Filtration improved.
Dear Alexander,
I have tried to increase quantity of points in region with high curvature 100 times more. As result, TolReached is decreased from 6.e-4 to 1.2e-5.
This is BAD solution (in spite of some improvement). I think, we should find another solution (out of frame of this bug). Let discuss verbally.
I have tried to increase quantity of points in region with high curvature 100 times more. As result, TolReached is decreased from 6.e-4 to 1.2e-5.
This is BAD solution (in spite of some improvement). I think, we should find another solution (out of frame of this bug). Let discuss verbally.
Dear nbv,
This fix cannot solve bad tolerance problem (Approximator level), it lie more deeper. Please look at the #0026927 bug for more details.
This fix cannot solve bad tolerance problem (Approximator level), it lie more deeper. Please look at the #0026927 bug for more details.
Dear Commenter 1,
Fix for this issue has been added in CR26431RI branch. Now, summary fix has "tested" status (see bug #26431).
New test case for this issue is not required. However, the problem described in this issue has NOT been fixed. It has been submitted to the issue #0026927.
Consequently, we should close this issue.
Fix for this issue has been added in CR26431RI branch. Now, summary fix has "tested" status (see bug #26431).
New test case for this issue is not required. However, the problem described in this issue has NOT been fixed. It has been submitted to the issue #0026927.
Consequently, we should close this issue.
Tested together with #26431
Branch [archived branch] has been deleted by Participant.
[revision removed]
[revision removed]
Branch [archived branch] has been deleted by Participant.
[revision removed]
[revision removed]
Branch [archived branch] has been deleted by Participant.
[revision removed]
[revision removed]
Branch [archived branch] has been deleted by Participant.
[revision removed]
[revision removed]
Branch [archived branch] has been deleted by Participant.
[revision removed]
[revision removed]
Branch [archived branch] has been deleted by Participant.
[revision removed]
[revision removed]
Related records
- #0026847 · related to · closedBad result of bfuseblend algorithm
- #0026848 · related to · closedResult of BO depends on arguments order
- #0026472 · parent of · closedC0 continuity of projection curve
- #0026927 · parent of · closedMake Intersection algorithm more adaptive
- #0026310 · related to · closedVery slow boolean cut operations on cylinders
- #0026675 · related to · closedEliminate normalization of coordinates in ApproxInt package