View Issue Details

Related ChangesetsJump to NotesJump to History
IDProjectCategoryView StatusDate SubmittedLast Update
0025929Open CASCADEOCCT:Modeling Algorithmspublic2015-03-13 14:102017-12-14 16:35
ReporternbvAssigned Tobugmaster  
PrioritynormalSeverityfeature 
Status closedResolutionfixed 
Product Version6.8.0 
Target Version7.0.0Fixed in Version7.0.0 
Summary0025929: Make Approx_ComputeLine algorithm adaptive
DescriptionNow 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 [+1.90666457620117940000 -4.81467964191310390000 +26.49925714205659200000] [+4.71250587855327650000 +0.19477910881389290000] [+3.06831691674069560000 -0.16473900943604278000]
 271 [+1.75037341065040230000 -4.86289890083316930000 +26.50114473837706400000] [+4.71854514205396840000 +0.18183839211542752000] [+3.07434778007345330000 -0.14921541759025503000]
 272 [+1.59419943342437280000 -4.91113704279707970000 +26.50202012992274100000] [+4.72458085326343990000 +0.16914435696997976000] [+3.08037351817593890000 -0.13345356306381939000]
 273 [+1.43808406952954870000 -4.95949041229089540000 +26.50187058910960800000] [+4.73061656447291230000 +0.15676613968902675000] [+3.08639718766187570000 -0.11736976847892722000]
 274 [+1.28211045162126580000 -5.00804768146907620000 +26.50067590984266300000] [+4.73665084416149720000 +0.14481860564032534000] [+3.09241664263891150000 -0.10085865624392509000]
 275 [+1.12630877682254500000 -5.05697368972781640000 +26.49840485141154300000] [+4.74268512385008290000 +0.13346905505613194000] [+3.09843221917128720000 -0.08374979795370673900]
 276 [+0.97072096248810058000 -5.10653496951993800000 +26.49500569814527400000] [+4.74872182192545540000 +0.12298571744066056000] [+3.10444457538708110000 -0.06576873645070424600]
 277 [+0.81558335206028842000 -5.15713415452643800000 +26.49039354522489700000] [+4.75475852000082710000 +0.11383774784232781000] [+3.11044831269595700000 -0.04646582436343127400]
                                       ...
 579 [+13.96512641202997100000 -52.53774058421905100000 +16.54539992388721700000] [+4.95142919414421190000 +50.00000000000000000000] [+2.98153983701058810000 +49.99989200028419800000]
----------- 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 +0.97072096248810058000 -5.10653496951993800000 +26.49500569814527400000
# parameter 1 = 0.80708806952489476
#ext_1
Draw[]> length ext_1
#The length ext_1 is 3.769612263912171e-005

A good value must be less than 1.e-7.
See approx.png file attached.


---- PROBLEM # 2
In addition, see message http://tracker.dev.opencascade.org/view.php?id=25709#c39511.

---- PROBLEM # 3
Test case bugs modalg_6 bug26310_4
Additional information
and documentation updates		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)
TagsNo tags attached.
Test case numberNot needed

Attached Files

  • approx.PNG (40,213 bytes)

Relationships

related to 0026847 closedbugmaster Open CASCADE Bad result of bfuseblend algorithm 
related to 0026848 closedbugmaster Open CASCADE Result of BO depends on arguments order 
parent of 0026472 closedbugmaster Open CASCADE C0 continuity of projection curve 
parent of 0026927 closedbugmaster Open CASCADE Make Intersection algorithm more adaptive 
related to 0026310 closedbugmaster Community Very slow boolean cut operations on cylinders 
related to 0026675 closedbugmaster Open CASCADE Eliminate normalization of coordinates in ApproxInt package 

Activities

nbv

2015-03-13 14:10

developer  

approx.PNG (40,213 bytes)

nbv

2015-03-17 12:04

developer   ~0038418

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).

git

2015-06-05 14:59

administrator   ~0041980

Branch CR25929 has been created by aml.

SHA-1: 097e5e1ff9a0763ddcbdc850fb633522ddee2f44


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.

git

2015-06-10 12:17

administrator   ~0042076

Branch CR25929_DeBoor has been created by aml.

SHA-1: 097e5e1ff9a0763ddcbdc850fb633522ddee2f44


No new revisions were added by this update.

git

2015-06-10 12:17

administrator   ~0042077

Branch CR25929 has been deleted by aml.

SHA-1: 097e5e1ff9a0763ddcbdc850fb633522ddee2f44

git

2015-06-10 13:09

administrator   ~0042079

Branch CR25929_ifv has been created by ifv.

SHA-1: 5437f51f6888d8ed15cb421ea55c77bc171040b3


Detailed log of new commits:

Author: ifv
Date: Wed Jun 10 13:07:45 2015 +0300

    Adaptive partition of WLine is implemented

git

2015-07-09 10:53

administrator   ~0042855

Branch CR25929_ifv has been updated forcibly by ifv.

SHA-1: 631efb0007bfb2d497db729c9abaa7c5da87582b

aml

2015-07-16 10:25

developer   ~0043100

Last edited: 2015-07-16 10:25

 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.

git

2015-07-20 14:59

administrator   ~0043190

Branch CR25929 has been created by aml.

SHA-1: 17ac5835230c7e722683aae4496ba8d833d7bef2


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

git

2015-07-21 11:43

administrator   ~0043213

Branch CR25929 has been updated forcibly by aml.

SHA-1: 1fec174975b16a528bc1e9ffad83ebccf7eb5aaf

git

2015-07-31 13:32

administrator   ~0043746

Branch CR25929 has been updated forcibly by aml.

SHA-1: fd75bbf2be7c9da57b4a81465de1f6ad4ab1e5c1

git

2015-07-31 15:03

administrator   ~0043755

Branch CR25929 has been updated forcibly by aml.

SHA-1: 23fc5798b9915a2506ff16e4592a97b840fd2fd2

git

2015-08-06 14:59

administrator   ~0043885

Branch CR25929 has been updated forcibly by aml.

SHA-1: cf652484fe019bbd505c54a8e37f92794c800386

git

2015-08-07 09:49

administrator   ~0043898

Branch CR25929 has been updated forcibly by aml.

SHA-1: 3dea494947370343a257201bae1d7bf2fc47e664

git

2015-08-31 14:17

administrator   ~0044881

Branch CR25929 has been updated forcibly by aml.

SHA-1: 82b64fd28f9671161d52ece17725cb7534d97b69

git

2015-09-29 14:23

administrator   ~0046256

Branch CR25929 has been updated forcibly by aml.

SHA-1: 9cfb1e6489b695a97e79ba0a7e3d672b8de54104

git

2015-10-23 13:54

administrator   ~0047375

Branch CR25929 has been updated forcibly by aml.

SHA-1: 4a274a99fb85d7517f2e1a9dbd00ff00cdb2d280

git

2015-10-27 10:28

administrator   ~0047461

Branch CR25929 has been updated forcibly by aml.

SHA-1: d2f65859916c4ad228cc9e054c9a46beb6e4bea8

git

2015-10-29 13:11

administrator   ~0047592

Branch CR25929 has been updated forcibly by aml.

SHA-1: 456af05d828b9effe888ad84984611eadbd53946

git

2015-10-30 10:25

administrator   ~0047637

Branch CR25929 has been updated forcibly by aml.

SHA-1: ea3cd8e5a1a21cdc02fc99a5a7c09a013a529007

git

2015-10-30 12:11

administrator   ~0047645

Branch CR25929 has been updated forcibly by aml.

SHA-1: c9782c9f5c5c029965d4143e4efbd050387f9f9b

git

2015-10-30 13:08

administrator   ~0047647

Branch CR25929_2 has been created by aml.

SHA-1: b711480779bb12bb81b9a42f6631745f50340751


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.

git

2015-11-02 07:17

administrator   ~0047690

Branch CR25929_2 has been updated forcibly by aml.

SHA-1: eb50b8218d17d464e521074008383b72292d3e30

aml

2015-11-02 07:18

developer   ~0047691

Last edited: 2015-11-02 14:07

 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.

abv

2015-11-03 19:50

manager   ~0047777

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.

aml

2015-11-05 07:23

developer   ~0047779

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.

msv

2015-11-05 16:54

developer   ~0047845

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.

git

2015-11-06 13:22

administrator   ~0047874

Branch CR25929_3 has been created by aml.

SHA-1: 219f81353a12f9d92f2b93251348b4dc1093c3a4


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.

aml

2015-11-06 13:30

developer   ~0047875

Dear msv,

Please check CR25929_3 (rebased on current master + remarks elimination) from occt repository and CR25929 from products repository.

msv

2015-11-06 16:53

developer   ~0047894

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.

msv

2015-11-06 16:58

developer   ~0047896

This patch must not be integrated till all regressions are gone. So, new bugs 0026847 and 0026847 should be fixed in the same patch.

git

2015-11-06 18:35

administrator   ~0047900

Branch CR25929_3 has been updated forcibly by aml.

SHA-1: b22b62aa13e715abd3056a036cf090dc5a5107f0

git

2015-11-09 15:24

administrator   ~0047954

Branch CR25929_3 has been updated by aml.

SHA-1: 5ea6eb9222535c54d021361636971db65ad74b1b


Detailed log of new commits:

Author: aml
Date: Mon Nov 9 15:23:28 2015 +0300

    Filtering algorithm improved.

git

2015-11-11 08:48

administrator   ~0048030

Branch CR25929_3 has been updated by aml.

SHA-1: 0581602de98f44cb211a57b2fb2c6176135c5f3f


Detailed log of new commits:

Author: aml
Date: Wed Nov 11 08:47:25 2015 +0300

    Good behaviour restored.

aml

2015-11-12 09:50

developer   ~0048084

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?

git

2015-11-13 14:03

administrator   ~0048156

Branch CR25929_4 has been created by aml.

SHA-1: f2f3d5c49228a23eaee0dc0ec06f196bbe96a7d2


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.

git

2015-11-17 09:29

administrator   ~0048260

Branch CR25929_4 has been updated by aml.

SHA-1: 7f155a5af40e9953777231a1fa7bc322a619a843


Detailed log of new commits:

Author: aml
Date: Mon Nov 16 12:57:38 2015 +0300

    Filtration improved.

nbv

2015-11-18 17:25

developer   ~0048359

Last edited: 2015-11-18 17:28

 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.

aml

2015-11-25 14:26

developer   ~0048565

Dear nbv,

This fix cannot solve bad tolerance problem (Approximator level), it lie more deeper. Please look at the 0026927 bug for more details.

nbv

2015-11-30 13:02

developer   ~0048654

Dear Bugmaster,

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.

apv

2015-11-30 13:21

tester   ~0048656

Tested together with #26431

git

2016-04-17 14:14

administrator   ~0053083

Branch CR25929 has been deleted by kgv.

SHA-1: c9782c9f5c5c029965d4143e4efbd050387f9f9b

git

2016-04-17 14:14

administrator   ~0053084

Branch CR25929_2 has been deleted by kgv.

SHA-1: eb50b8218d17d464e521074008383b72292d3e30

git

2016-04-17 14:14

administrator   ~0053085

Branch CR25929_3 has been deleted by kgv.

SHA-1: 0581602de98f44cb211a57b2fb2c6176135c5f3f

git

2016-04-17 14:14

administrator   ~0053086

Branch CR25929_4 has been deleted by kgv.

SHA-1: 7f155a5af40e9953777231a1fa7bc322a619a843

git

2016-04-17 14:14

administrator   ~0053087

Branch CR25929_DeBoor has been deleted by kgv.

SHA-1: 097e5e1ff9a0763ddcbdc850fb633522ddee2f44

git

2016-04-17 14:14

administrator   ~0053088

Branch CR25929_ifv has been deleted by kgv.

SHA-1: 631efb0007bfb2d497db729c9abaa7c5da87582b

Related Changesets

occt: master f44aa197

2015-11-10 06:57:03

aml


Committer: bugmaster Details Diff		 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.

Filtering algorithm improved.		 Affected Issues
0025929
mod - src/ApproxInt/ApproxInt_Approx.gxx Diff File
add - src/ApproxInt/ApproxInt_KnotTools.cxx Diff File
add - src/ApproxInt/ApproxInt_KnotTools.hxx Diff File
mod - src/ApproxInt/FILES Diff File
mod - src/BRepApprox/BRepApprox_Approx.hxx Diff File
mod - src/GeomInt/GeomInt_WLApprox.hxx Diff File

Issue History

Date Modified Username Field Change
2015-03-13 14:10 nbv New Issue
2015-03-13 14:10 nbv Assigned To => msv
2015-03-13 14:10 nbv File Added: approx.PNG
2015-03-17 10:48 msv Product Version => 6.8.0
2015-03-17 10:48 msv Target Version 6.9.0 => Unscheduled
2015-03-17 10:48 msv Summary Move approximation of intersection lines task from Approx_ComputeLine to Approx_BSplComputeLine algorithm => Switch approximation of intersection lines from Approx_ComputeLine to Approx_BSplComputeLine
2015-03-17 10:48 msv Description Updated
2015-03-17 11:20 msv Assigned To msv => aml
2015-03-17 11:20 msv Status new => assigned
2015-03-17 12:04 nbv Note Added: 0038418
2015-03-17 12:06 nbv Steps to Reproduce Updated
2015-04-09 16:52 nbv Steps to Reproduce Updated
2015-06-05 14:59 git Note Added: 0041980
2015-06-10 12:17 git Note Added: 0042076
2015-06-10 12:17 git Note Added: 0042077
2015-06-10 13:09 git Note Added: 0042079
2015-07-09 10:53 git Note Added: 0042855
2015-07-15 16:16 msv Target Version Unscheduled => 7.1.0
2015-07-16 10:22 aml Summary Switch approximation of intersection lines from Approx_ComputeLine to Approx_BSplComputeLine => Make Approx_ComputeLine algorithm adaptive
2015-07-16 10:22 aml Description Updated
2015-07-16 10:25 aml Note Added: 0043100
2015-07-16 10:25 aml Note Edited: 0043100
2015-07-16 10:39 nbv Relationship added related to 0026310
2015-07-16 11:10 nbv Steps to Reproduce Updated
2015-07-20 14:59 git Note Added: 0043190
2015-07-21 11:43 git Note Added: 0043213
2015-07-23 12:15 aml Relationship added parent of 0026472
2015-07-31 13:32 git Note Added: 0043746
2015-07-31 15:03 git Note Added: 0043755
2015-08-06 14:59 git Note Added: 0043885
2015-08-07 09:49 git Note Added: 0043898
2015-08-31 14:17 git Note Added: 0044881
2015-09-29 14:23 git Note Added: 0046256
2015-10-22 17:12 nbv Relationship added related to 0026675
2015-10-23 13:54 git Note Added: 0047375
2015-10-27 10:28 git Note Added: 0047461
2015-10-28 12:57 msv Target Version 7.1.0 => 7.0.0
2015-10-29 13:11 git Note Added: 0047592
2015-10-30 10:25 git Note Added: 0047637
2015-10-30 12:11 git Note Added: 0047645
2015-10-30 13:08 git Note Added: 0047647
2015-11-02 07:17 git Note Added: 0047690
2015-11-02 07:18 aml Note Added: 0047691
2015-11-02 07:18 aml Assigned To aml => msv
2015-11-02 07:18 aml Status assigned => resolved
2015-11-02 14:07 aml Note Edited: 0047691
2015-11-03 19:50 abv Note Added: 0047777
2015-11-05 07:23 aml Note Added: 0047779
2015-11-05 16:54 msv Note Added: 0047845
2015-11-05 16:54 msv Assigned To msv => aml
2015-11-05 16:54 msv Status resolved => assigned
2015-11-06 13:20 aml Relationship added related to 0026847
2015-11-06 13:20 aml Relationship added related to 0026848
2015-11-06 13:22 git Note Added: 0047874
2015-11-06 13:30 aml Note Added: 0047875
2015-11-06 13:30 aml Assigned To aml => msv
2015-11-06 13:30 aml Status assigned => resolved
2015-11-06 16:53 msv Note Added: 0047894
2015-11-06 16:53 msv Assigned To msv => aml
2015-11-06 16:53 msv Status resolved => assigned
2015-11-06 16:58 msv Note Added: 0047896
2015-11-06 18:35 git Note Added: 0047900
2015-11-09 15:24 git Note Added: 0047954
2015-11-11 08:48 git Note Added: 0048030
2015-11-12 09:50 aml Note Added: 0048084
2015-11-12 09:50 aml Assigned To aml => nbv
2015-11-12 09:50 aml Status assigned => feedback
2015-11-13 14:03 git Note Added: 0048156
2015-11-17 09:29 git Note Added: 0048260
2015-11-18 17:25 nbv Note Added: 0048359
2015-11-18 17:26 nbv Assigned To nbv => aml
2015-11-18 17:28 nbv Note Edited: 0048359
2015-11-25 14:19 aml Relationship added parent of 0026927
2015-11-25 14:26 aml Note Added: 0048565
2015-11-25 14:30 aml Additional Information Updated
2015-11-25 14:32 aml Additional Information Updated
2015-11-25 14:44 nbv Assigned To aml => nbv
2015-11-30 13:02 nbv Note Added: 0048654
2015-11-30 13:02 nbv Assigned To nbv => bugmaster
2015-11-30 13:17 bugmaster Assigned To bugmaster => apv
2015-11-30 13:21 apv Test case number => Not needed
2015-11-30 13:21 apv Note Added: 0048656
2015-11-30 13:21 apv Assigned To apv => bugmaster
2015-11-30 13:21 apv Status feedback => tested
2015-12-04 20:05 bugmaster Changeset attached => occt master f44aa197
2015-12-04 20:05 bugmaster Status tested => verified
2015-12-04 20:05 bugmaster Resolution open => fixed
2016-04-17 14:14 git Note Added: 0053083
2016-04-17 14:14 git Note Added: 0053084
2016-04-17 14:14 git Note Added: 0053085
2016-04-17 14:14 git Note Added: 0053086
2016-04-17 14:14 git Note Added: 0053087
2016-04-17 14:14 git Note Added: 0053088
2016-04-20 15:42 aiv Fixed in Version => 7.0.0
2016-04-20 15:50 aiv Status verified => closed