View Issue Details

IDProjectCategoryView StatusLast Update
0026075Open CASCADEOCCT:Modeling Algorithmspublic2021-08-30 14:56
ReportermsvAssigned Tobugmaster  
PrioritynormalSeverityminor 
Status closedResolutionfixed 
Product Version6.9.0 
Target Version6.9.1Fixed in Version6.9.1 
Summary0026075: Make Extrema_GenExtCC return IsParallel flag in case of parallel curves
DescriptionThis issue came from 0026064, where distmini algorithm hangs a long time when processing two parallel curves (one is a line and another is a bspline parallel to the line).
The algorithm of non-analytical extrema Extrema_GenExtCC works in this case. It uses the results of the algorithm math_GlobOptMin on each interval of C2 continuity. And math_GlobOptMin returns several thousands of points on each interval in this case.
There are two possible solutions:

1) Make math_GlobOptMin to return only one solution on each interval with indication that minimal solution is present on any point in the input interval. In this case Extrema_GenExtCC must use this indication to marks parallel regions, and then set the flag IsParallel if all regions are marked parallel.

2) Do not alter math_GlobOptMin, but in this case Extrema_GenExtCC must process all points on the subject of the same distance if we check middle point on the segment between each two neighboring points. For that we should order the points by parameter and check middle of each segment.

It is needed to weight all pros and cons before deciding.
Steps To Reproduce#The shapes can be got from the bug 0026064

restore dist1-s1.brep s1
restore dist1-s2.brep s2
mkcurve c1 s1
mkcurve c2 s2
extrema c1 c2
TagsNo tags attached.
Test case numberbugs modalg_6 bug26075

Attached Files

  • extrema_parallel.PNG (10,899 bytes)
  • extrema_parallel_zoom.PNG (40,478 bytes)

Relationships

related to 0026064 closedbugmaster Community distmini of two edges locks up 
parent of 0029792 closedbugmaster Open CASCADE Modeling Algorithms - Add ::IsParallel method to GeomAPI_Extrema* classes 
has duplicate 0026184 closedbugmaster Open CASCADE GeomAPI_ExtremaCurveCurve hangs on parallel b-spline curves 
related to 0026269 closedbugmaster Open CASCADE Modeling Data - Analytical extrema does not take into account trimmed input data 

Activities

msv

2015-04-14 17:40

developer  

extrema_parallel.PNG (10,899 bytes)

msv

2015-04-14 17:41

developer  

extrema_parallel_zoom.PNG (40,478 bytes)

git

2015-05-22 16:50

administrator   ~0041447

Branch CR26075 has been created by aml.

SHA-1: 9bfa07c4572c815d6a41f6edcc3c8db67821a883


Detailed log of new commits:

Author: aml
Date: Fri May 22 11:42:39 2015 +0300

    0026075: Make Extrema_GenExtCC return IsParallel flag in case of parallel curves
    
    1) Added check for parallel curves.
    2) Changed unefficient o(n^2) duplicates deleting algorithm to o(n) algorithm.
    3) Deleted useless upper level duplicates deleting algorithm.

aml

2015-05-22 16:51

developer   ~0041448

Last edited: 2015-05-22 16:51

Dearm msv,
Please check current state of branch CR26075.


Testing of infinite solutions problem:
bugs modalg_6 bug26064

master : 35.56
CR26075 : 1.41
speedup : ~ 25

CR26184 "Steps to reproduce" script, case1:

master : more than 2000.0
CR26075 : 21.46
speedup : ~ 90

msv

2015-05-22 18:07

developer   ~0041456

Remarks:

src\Extrema\Extrema_GenExtCC.gxx
- The field myTol in the class Extrema_CCPointsInspector is not used.
- The formula in line 196 causes doubts:
  const Standard_Real aCellSize = Precision::PConfusion() / (2.0 * Sqrt(2.0));
- In Extrema_GenExtCC::Perform, the flag myParallel is never set to true.
- Correct comment above implementation of Extrema_GenExtCC::IsParallel.

src\Extrema\Extrema_ExtCC.cxx
- In order to unify the code, I propose to remove the lines 253, 258:
      myIsPar = myECC.IsParallel();
Instead, add the following line before the line 690:
+ myIsPar = AlgExt.IsParallel();
    NbExt = AlgExt.NbExt();

msv

2015-05-22 18:19

developer   ~0041457

Additional remark:
Please, consider also the class Extrema_ExtCC2d, which also uses GenExtCC, for utilization of IsParallel flag.

git

2015-05-25 18:24

administrator   ~0041520

Branch CR26075 has been updated by aml.

SHA-1: 06be9f1878fdc903b1aa3bdf704f3fab6ee45050


Detailed log of new commits:

Author: aml
Date: Mon May 25 13:27:01 2015 +0300

    minor corrections.

aml

2015-05-25 18:25

developer   ~0041521

Dear msv,
Please check updated CR26075 branch.

msv

2015-05-27 18:49

developer   ~0041623

Remarks:

src\Extrema\Extrema_GenExtCC.gxx
- Line 293: checking constant condition on each iteration. If number of points is less than MinNbInfSol then it is not needed to enter the loop.
- Again: correct comment above implementation of Extrema_GenExtCC::IsParallel (line 344).

src\Extrema\Extrema_ExtCC.cxx
- Line 688: replace myECC with AlgExt.

git

2015-05-28 08:54

administrator   ~0041629

Branch CR26075 has been updated forcibly by aml.

SHA-1: c947ad5df79adc0cf12ba1901ecac379efb1fe06

git

2015-05-29 14:22

administrator   ~0041725

Branch CR26075 has been updated forcibly by aml.

SHA-1: 443dc5ee1fa20a17c471e14b73f1ba9e5582f881

aml

2015-05-29 14:23

developer   ~0041726

Dear msv,
Please check updated CR26075 branch.

msv

2015-05-29 16:16

developer   ~0041746

Reviewed.

git

2015-06-01 16:52

administrator   ~0041804

Branch CR26075 has been updated by apv.

SHA-1: 64c2d74341caf192675dc720408e058bdb147030


Detailed log of new commits:

Author: apv
Date: Mon Jun 1 16:51:47 2015 +0300

    Test-case for issue 0026075

apv

2015-06-01 17:23

tester   ~0041810

Dear BugMaster,

Branch CR26075 from occt git-repository (and master from products git-repository) was compiled on Linux, MacOS and Windows platforms and tested.
SHA-1: 443dc5ee1fa20a17c471e14b73f1ba9e5582f881

Number of compiler warnings:
occt component:
   Linux: 25 (25 on master)
   Windows: 0 (0 on master)
products component:
   Linux: 37 (37 on master)
   Windows: 0 (0 on master)

Regressions/Differences:
Not detected

Testing cases:
bugs modalg_6 bug26075 - OK
http://occt-tests/CR26075-master-occt-64/Debian70-64/bugs/modalg_6/bug26075.html
http://occt-tests/CR26075-master-occt-64/Windows-64-VC10/bugs/modalg_6/bug26075.html

Testing on Linux:
Total MEMORY difference: 96093813 / 96686905 [-0.61%]
Total CPU difference: 18280.409999999938 / 18461.80000000009 [-0.98%]

Testing on Windows:
Total MEMORY difference: 57024982 / 57008678 [+0.03%]
Total CPU difference: 17448.02544559885 / 17494.154941298817 [-0.26%]

git

2015-08-14 10:59

administrator   ~0044245

Branch CR26075 has been deleted by inv.

SHA-1: 64c2d74341caf192675dc720408e058bdb147030

Related Changesets

occt: master 20a216fe

2015-06-04 11:13:58

aml


Committer: bugmaster Details Diff
0026075: Make Extrema_GenExtCC return IsParallel flag in case of parallel curves

1) Added check for parallel curves.
2) Changed unefficient o(n^2) duplicates deleting algorithm to o(n) algorithm.
3) Deleted useless upper level duplicates deleting algorithm.

Test-case for issue 0026075
Affected Issues
0026075
mod - src/Extrema/Extrema_ExtCC.cxx Diff File
mod - src/Extrema/Extrema_ExtCC2d.cxx Diff File
mod - src/Extrema/Extrema_GenExtCC.cdl Diff File
mod - src/Extrema/Extrema_GenExtCC.gxx Diff File
mod - src/math/math_GlobOptMin.cxx Diff File
add - tests/bugs/modalg_6/bug26075 Diff File

Issue History

Date Modified Username Field Change
2015-04-14 17:38 msv New Issue
2015-04-14 17:38 msv Assigned To => msv
2015-04-14 17:40 msv Relationship added related to 0026064
2015-04-14 17:40 msv File Added: extrema_parallel.PNG
2015-04-14 17:41 msv File Added: extrema_parallel_zoom.PNG
2015-04-14 17:46 msv Assigned To msv => aml
2015-04-14 17:46 msv Status new => assigned
2015-05-05 14:31 msv Relationship added has duplicate 0026184
2015-05-22 16:50 git Note Added: 0041447
2015-05-22 16:51 aml Note Added: 0041448
2015-05-22 16:51 aml Assigned To aml => msv
2015-05-22 16:51 aml Status assigned => resolved
2015-05-22 16:51 aml Note Edited: 0041448
2015-05-22 18:07 msv Note Added: 0041456
2015-05-22 18:07 msv Assigned To msv => aml
2015-05-22 18:07 msv Status resolved => assigned
2015-05-22 18:19 msv Note Added: 0041457
2015-05-25 18:24 git Note Added: 0041520
2015-05-25 18:25 aml Note Added: 0041521
2015-05-25 18:25 aml Assigned To aml => msv
2015-05-25 18:25 aml Status assigned => resolved
2015-05-26 13:55 aml Relationship added related to 0026269
2015-05-27 18:49 msv Note Added: 0041623
2015-05-27 18:49 msv Assigned To msv => aml
2015-05-27 18:49 msv Status resolved => assigned
2015-05-28 08:54 git Note Added: 0041629
2015-05-29 14:22 git Note Added: 0041725
2015-05-29 14:23 aml Note Added: 0041726
2015-05-29 14:23 aml Assigned To aml => msv
2015-05-29 14:23 aml Status assigned => resolved
2015-05-29 16:16 msv Note Added: 0041746
2015-05-29 16:16 msv Assigned To msv => bugmaster
2015-05-29 16:16 msv Status resolved => reviewed
2015-05-29 16:22 apv Assigned To bugmaster => apv
2015-06-01 16:52 git Note Added: 0041804
2015-06-01 16:52 apv Test case number => bugs modalg_6 bug26075
2015-06-01 17:23 apv Note Added: 0041810
2015-06-01 17:23 apv Assigned To apv => bugmaster
2015-06-01 17:23 apv Status reviewed => tested
2015-06-05 15:00 bugmaster Changeset attached => occt master 20a216fe
2015-06-05 15:00 bugmaster Status tested => verified
2015-06-05 15:00 bugmaster Resolution open => fixed
2015-06-08 12:32 bugmaster Target Version 7.1.0 => 7.0.0
2015-08-14 10:59 git Note Added: 0044245
2015-09-01 12:08 abv Target Version 7.0.0 => 6.9.1
2015-09-09 16:17 szy Target Version 6.9.1 => 7.0.0
2015-09-11 06:45 abv Target Version 7.0.0 => 6.9.1
2015-10-16 14:55 aiv Status verified => closed
2015-10-23 20:51 aiv Fixed in Version => 6.9.1
2021-08-30 14:56 kgv Relationship added parent of 0029792