DiscussionsIssue archiveOCCT:Modeling Algorithms

Archived issue #0025929

Make Approx_ComputeLine algorithm adaptive

Open CASCADEOCCT:Modeling Algorithmsclosed46 public notes

Search issues

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.

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

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)

Public activity

46 archived notes

Participants are labeled by their role within this record.

01Commenter 1
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).
02Commenter 2
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.
03Commenter 2
Branch [archived branch] has been created by Participant.

[revision removed]


No new revisions were added by this update.
04Commenter 2
Branch [archived branch] has been deleted by Participant.

[revision removed]
05Commenter 2
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
06Commenter 2
Branch [archived branch] has been updated forcibly by Participant.

[revision removed]
07Commenter 7
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.

08Commenter 2
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
09Commenter 2
Branch [archived branch] has been updated forcibly by Participant.

[revision removed]
10Commenter 2
Branch [archived branch] has been updated forcibly by Participant.

[revision removed]
11Commenter 2
Branch [archived branch] has been updated forcibly by Participant.

[revision removed]
12Commenter 2
Branch [archived branch] has been updated forcibly by Participant.

[revision removed]
13Commenter 2
Branch [archived branch] has been updated forcibly by Participant.

[revision removed]
14Commenter 2
Branch [archived branch] has been updated forcibly by Participant.

[revision removed]
15Commenter 2
Branch [archived branch] has been updated forcibly by Participant.

[revision removed]
16Commenter 2
Branch [archived branch] has been updated forcibly by Participant.

[revision removed]
17Commenter 2
Branch [archived branch] has been updated forcibly by Participant.

[revision removed]
18Commenter 2
Branch [archived branch] has been updated forcibly by Participant.

[revision removed]
19Commenter 2
Branch [archived branch] has been updated forcibly by Participant.

[revision removed]
20Commenter 2
Branch [archived branch] has been updated forcibly by Participant.

[revision removed]
21Commenter 2
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.
22Commenter 2
Branch [archived branch] has been updated forcibly by Participant.

[revision removed]
23Commenter 23
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.

24Commenter 24
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.
25Commenter 25
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.
26Commenter 26
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.
27Commenter 2
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.
28Commenter 28
Dear msv,

Please check CR25929_3 (rebased on current master + remarks elimination) from occt repository and CR25929 from products repository.
29Commenter 29
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.
30Commenter 30
This patch must not be integrated till all regressions are gone. So, new bugs #0026847 and #0026847 should be fixed in the same patch.
31Commenter 2
Branch [archived branch] has been updated forcibly by Participant.

[revision removed]
32Commenter 2
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.

33Commenter 2
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.

34Commenter 34
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?
35Commenter 2
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.
36Commenter 2
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.

37Commenter 37
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.

38Commenter 38
Dear nbv,

This fix cannot solve bad tolerance problem (Approximator level), it lie more deeper. Please look at the #0026927 bug for more details.
39Commenter 39
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.
40Commenter 40
Tested together with #26431
41Commenter 2
Branch [archived branch] has been deleted by Participant.

[revision removed]
42Commenter 2
Branch [archived branch] has been deleted by Participant.

[revision removed]
43Commenter 2
Branch [archived branch] has been deleted by Participant.

[revision removed]
44Commenter 2
Branch [archived branch] has been deleted by Participant.

[revision removed]
45Commenter 2
Branch [archived branch] has been deleted by Participant.

[revision removed]
46Commenter 2
Branch [archived branch] has been deleted by Participant.

[revision removed]

Related records