MantisBT - Open CASCADE
View Issue Details
0028639Open CASCADE[OCCT] OCCT:Modeling Algorithmspublic2017-04-07 07:342017-11-24 11:22
emv 
bugmaster 
normalminor 
closedfixed 
[OCCT] 7.1.0 
[OCCT] 7.2.0[OCCT] 7.2.0 
Not needed
0028639: Improve performance of the IntPolyh_MaillageAffinage algorithm
The implementation of some methods of the IntPolyh_MaillageAffinage class is inefficient and sometimes most of the time is spent on the creation of the triangles instead of their intersection. It is necessary to revise these methods and make them more efficient. It will allow improving the performance of the algorithm.
Not needed.
No tags attached.
related to 0028599closed apn Open CASCADE Replacement of old Boolean operations with new ones in BRepProj_Projection algorithm 
Issue History
2017-04-07 07:34emvNew Issue
2017-04-07 07:34emvAssigned To => msv
2017-04-07 07:34emvAssigned Tomsv => emv
2017-04-07 07:34emvStatusnew => assigned
2017-04-07 09:28emvRelationship addedrelated to 0028599
2017-04-12 10:05gitNote Added: 0065164
2017-04-12 10:09emvNote Added: 0065165
2017-04-12 10:09emvAssigned Toemv => msv
2017-04-12 10:09emvStatusassigned => resolved
2017-04-12 10:09emvSteps to Reproduce Updatedbug_revision_view_page.php?rev_id=16396#r16396
2017-04-12 10:13emvNote Edited: 0065165bug_revision_view_page.php?bugnote_id=65165#r16398
2017-04-12 10:14emvNote Edited: 0065165bug_revision_view_page.php?bugnote_id=65165#r16399
2017-04-14 13:06gitNote Added: 0065214
2017-04-14 13:06emvNote Added: 0065215
2017-04-14 13:16gitNote Added: 0065217
2017-04-19 10:27msvNote Added: 0065330
2017-04-19 10:27msvAssigned Tomsv => emv
2017-04-19 10:27msvStatusresolved => assigned
2017-04-20 15:24gitNote Added: 0065398
2017-04-20 15:29emvNote Added: 0065399
2017-04-20 15:29emvAssigned Toemv => msv
2017-04-20 15:29emvStatusassigned => resolved
2017-04-20 15:30gitNote Added: 0065400
2017-04-21 11:57msvNote Added: 0065416
2017-04-21 11:57msvAssigned Tomsv => emv
2017-04-21 11:57msvStatusresolved => assigned
2017-04-21 12:08gitNote Added: 0065418
2017-04-21 12:09emvNote Added: 0065419
2017-04-21 12:09emvAssigned Toemv => msv
2017-04-21 12:09emvStatusassigned => resolved
2017-04-21 12:12msvNote Added: 0065420
2017-04-21 12:12msvAssigned Tomsv => bugmaster
2017-04-21 12:12msvStatusresolved => reviewed
2017-04-21 12:34mkvAssigned Tobugmaster => mkv
2017-04-21 16:00gitNote Added: 0065428
2017-04-24 14:23mkvNote Added: 0065476
2017-04-24 14:24mkvNote Added: 0065477
2017-04-24 14:24mkvAssigned Tomkv => bugmaster
2017-04-24 14:24mkvStatusreviewed => tested
2017-04-24 14:24mkvTest case number => Not needed
2017-04-28 12:24gitNote Added: 0065634
2017-04-28 13:08bugmasterChangeset attached => occt master 68b07699
2017-04-28 13:08bugmasterStatustested => verified
2017-04-28 13:08bugmasterResolutionopen => fixed
2017-05-12 11:36gitNote Added: 0065959
2017-05-12 11:36gitNote Added: 0065960
2017-09-29 16:19aivFixed in Version => 7.2.0
2017-09-29 16:25aivStatusverified => closed
2017-11-24 11:22msvRelationship addedrelated to 0025731

Notes
(0065164)
git   
2017-04-12 10:05   
Branch CR28639 has been created by emv.

SHA-1: 2440a6e876c7a9e6d18f1574ba50caf8bb354bb6


Detailed log of new commits:

Author: emv
Date: Fri Apr 7 07:43:44 2017 +0300

    0028639: Improve performance of the IntPolyh_MaillageAffinage algorithm
    
    The following improvements have been made:
    1. Linking edges to triangles while creating the edges.
    2. Replacing the array of couples of intersecting triangles with the list to avoid unnecessary allocations of memory.
    3. Using the algorithm of unbalanced binary tree when looking for pairs of interfering triangles.
    4. Building bounding boxes for the triangles only once and then reusing it.
    5. Making the simple methods of the IntPolyh_Point, IntPolyh_Edge, IntPolyh_Triangle, IntPolyh_Couple classes inline.
(0065165)
emv   
2017-04-12 10:09   
(edited on: 2017-04-12 10:14)
Dear Mikhail, could you please review the branch CR28639?

Local testing of that branch has shown the following improvements comparing to the master:
CPU boolean bcut_complex G2: 2.5 / 5.328125 [-53.08%]
CPU boolean bcut_complex N9: 0.671875 / 3.40625 [-80.28%]
CPU boolean bfuse_complex F1: 1.625 / 2.953125 [-44.97%]
CPU boolean bfuse_complex F2: 3.46875 / 6.09375 [-43.08%]
CPU boolean bfuse_complex F8: 1.9375 / 2.90625 [-33.33%]
CPU boolean bopcommon_complex D8: 8 / 16.703125 [-52.10%]
CPU boolean bopcommon_complex D9: 8.03125 / 16.6875 [-51.87%]
CPU boolean bopcommon_complex E5: 0.28125 / 1.546875 [-81.82%]
CPU boolean bopcommon_complex E6: 0.28125 / 1.5 [-81.25%]
CPU boolean bopcut_complex E1: 7.484375 / 16.328125 [-54.16%]
CPU boolean bopcut_complex E2: 7.625 / 16.125 [-52.71%]
CPU boolean bopcut_complex E7: 0.265625 / 1.5625 [-83.00%]
CPU boolean bopcut_complex E8: 0.28125 / 1.5 [-81.25%]
CPU boolean bopcut_complex P8: 5.46875 / 10.109375 [-45.90%]
CPU boolean bopfuse_complex C9: 7.546875 / 16.203125 [-53.42%]
CPU boolean bopfuse_complex D1: 7.71875 / 16.359375 [-52.82%]
CPU boolean bopfuse_complex D6: 0.265625 / 1.5 [-82.29%]
CPU boolean bopfuse_complex D7: 0.3125 / 1.5 [-79.17%]
CPU boolean bopfuse_complex J7: 1.46875 / 3.40625 [-56.88%]
CPU boolean bopfuse_simple ZP6: 2 / 5.015625 [-60.12%]
CPU boolean bsection R9: 1.84375 / 3.5625 [-48.25%]
CPU boolean gdml_private ZG4: 1.34375 / 36.921875 [-96.36%]
CPU boolean gdml_public A9: 4.078125 / 9.171875 [-55.54%]
CPU bugs modalg_1 buc60462_1: 1.875 / 3.59375 [-47.83%]
CPU bugs modalg_1 bug18186: 1.484375 / 2.28125 [-34.93%]
CPU bugs modalg_1 bug19071: 0.515625 / 1.109375 [-53.52%]
CPU bugs modalg_2 bug335: 0.453125 / 1.75 [-74.11%]
CPU bugs modalg_3 bug600: 4.59375 / 112.953125 [-95.93%]
CPU bugs modalg_4 bug697_2: 2.828125 / 4.15625 [-31.95%]
CPU bugs modalg_4 bug697_4: 2.96875 / 4.34375 [-31.65%]
CPU bugs modalg_4 bug697_7: 2.96875 / 4.296875 [-30.91%]
CPU bugs modalg_4 bug697_8: 2.96875 / 4.328125 [-31.41%]
CPU bugs modalg_5 bug25456: 2.6875 / 11.453125 [-76.53%]
CPU bugs modalg_6 bug22609: 1.1875 / 2.078125 [-42.86%]
CPU bugs modalg_6 bug26450: 3.765625 / 6.421875 [-41.36%]
CPU bugs modalg_6 bug26535: 2.1875 / 3 [-27.08%]
CPU bugs modalg_6 bug26621: 29.640625 / 42.59375 [-30.41%]
CPU bugs modalg_6 bug26848: 4.859375 / 113 [-95.70%]
CPU bugs modalg_6 bug26938_1: 4.03125 / 6.09375 [-33.85%]
CPU bugs modalg_6 bug26938_4: 3.3125 / 4.703125 [-29.57%]
CPU bugs modalg_6 bug27615: 29.859375 / 36.640625 [-18.51%]
CPU bugs modalg_6 bug27746_1: 5.890625 / 9.953125 [-40.82%]
CPU bugs moddata_1 bug152_1: 0.4375 / 10.40625 [-95.80%]
CPU bugs moddata_1 bug152_2: 0.453125 / 9.09375 [-95.02%]
CPU bugs moddata_2 bug228: 8.03125 / 16.640625 [-51.74%]
CPU bugs moddata_3 bug599: 4.765625 / 112.515625 [-95.76%]
CPU chamfer dist_angle_complex C1: 1.09375 / 3.03125 [-63.92%]
CPU chamfer dist_angle_sequence C1: 1.625 / 2.734375 [-40.57%]
CPU chamfer dist_dist_complex C1: 0.875 / 2.578125 [-66.06%]
CPU chamfer dist_dist_sequence C1: 1.609375 / 2.8125 [-42.78%]
CPU chamfer equal_dist_complex C1: 1.140625 / 3.0625 [-62.76%]
CPU chamfer equal_dist_sequence C1: 1.3125 / 2.71875 [-51.72%]
CPU perf modalg bug19793_2: 19.546875 / 55.59375 [-64.84%]
CPU prj base C7: 0.359375 / 2.5625 [-85.98%]
CPU prj base C8: 0.9375 / 6.03125 [-84.46%]
CPU prj base D1: 0.46875 / 3.1875 [-85.29%]
CPU prj base D2: 0.609375 / 4.09375 [-85.11%]
CPU prj base D4: 0.171875 / 0.828125 [-79.25%]
CPU prj base D5: 0.21875 / 1.09375 [-80.00%]
CPU prj base D8: 1.125 / 7.703125 [-85.40%]
CPU prj base D9: 0.3125 / 2.203125 [-85.82%]
CPU prj base E2: 0.125 / 0.78125 [-84.00%]
CPU prj base E3: 0.453125 / 2.4375 [-81.41%]
CPU prj base E4: 0.1875 / 1.4375 [-86.96%]
CPU prj base E5: 0.28125 / 1.4375 [-80.43%]
CPU prj base E6: 0.453125 / 2.5625 [-82.32%]
CPU prj base E7: 0.359375 / 2.171875 [-83.45%]
CPU prj base F5: 0.25 / 1.328125 [-81.18%]
CPU prj base F7: 0.25 / 1.25 [-80.00%]
CPU prj base G1: 0.1875 / 0.84375 [-77.78%]
CPU prj base G2: 0.09375 / 0.65625 [-85.71%]
CPU prj base G3: 0.28125 / 1.59375 [-82.35%]
CPU prj base G4: 0.34375 / 1.890625 [-81.82%]
CPU prj base G5: 0.515625 / 2.984375 [-82.72%]
CPU prj base G6: 0.484375 / 3.515625 [-86.22%]
CPU prj base G8: 0.1875 / 1.171875 [-84.00%]
CPU prj base G9: 0.140625 / 0.890625 [-84.21%]
CPU prj base H1: 0.25 / 1.21875 [-79.49%]
CPU prj base H2: 0.34375 / 2.046875 [-83.21%]
CPU prj base H4: 0.40625 / 2.40625 [-83.12%]
CPU prj base H5: 0.96875 / 7.078125 [-86.31%]
CPU prj base H6: 0.625 / 4.953125 [-87.38%]
CPU prj base H7: 0.625 / 4.703125 [-86.71%]
CPU prj base H8: 0.34375 / 2.203125 [-84.40%]
CPU prj base H9: 0.375 / 2.578125 [-85.45%]
CPU prj base I1: 0.359375 / 2.28125 [-84.25%]
CPU prj base I2: 0.3125 / 2.21875 [-85.92%]
CPU prj base I3: 1.421875 / 10.546875 [-86.52%]
CPU prj base I4: 0.46875 / 3.5 [-86.61%]


The list shows only the most noticeable improvements.

(0065214)
git   
2017-04-14 13:06   
Branch CR28639 has been updated forcibly by emv.

SHA-1: 34e5d782d6c90ab6d875d3efbf5f0a8dff676461
(0065215)
emv   
2017-04-14 13:06   
The branch CR28474 has been rebased on current master.
(0065217)
git   
2017-04-14 13:16   
Branch CR28639 has been updated forcibly by emv.

SHA-1: 109fb801f0c23e8aa4da85884a42d68acac73316
(0065330)
msv   
2017-04-19 10:27   
Remarks:

src\IntPolyh\FILES
- keep alphabit sorting of list of files.

src\IntPolyh\IntPolyh_Edge.hxx
src\IntPolyh\IntPolyh_Point.hxx
src\IntPolyh\IntPolyh_Couple.hxx
src\IntPolyh\IntPolyh_Triangle.hxx
- As you are changing 90% of the source code rename fields according to coding rules.

src\IntPolyh\IntPolyh_Couple.hxx
- 53: it returns integer, so it is not TRUE.
- 58: "the angle of between", "of" is extra.

src\IntPolyh\IntPolyh_CoupleMapHasher.hxx
- DEFINE_STANDARD_ALLOC is not needed.

src\IntPolyh\IntPolyh_Triangle.hxx
- get rid of "if" statements in GetEdgeNumber, SetEdge, GetEdgeOrientation, SetEdgeOrientation, GetNextTriangle2, LinkEdges2Triangle, SetEdgeAndOrientation by replacing fields p1,p2,p3,e1,e2,e3,oe1,oe2,oe3 with C arrays p[3], e[3], oe[3].
- compact boolean flags using bit fields.

src\IntPolyh\IntPolyh_Triangle.cxx
- The method IntPolyh_Triangle::BoundingBox is to be optimized:
  - use cached isDegenerated flag;
  - avoid enlarge and setting gap on repeated calls.

src\IntPolyh\IntPolyh_MaillageAffinage.cxx
- 178: make it private.
- In the method TriangleCompare now it became useless to check the number of contacts by NbTTC. So, the lines 3200-3202, 3231-3232 are to be removed.

src\IntPolyh\IntPolyh_MaillageAffinage.hxx
- Remove declaration of not implemented method GetArrayOfSP.
- Remove unused field TStartPoints.
- Remove unused class IntPolyh_ArrayOfStartPoints.hxx
- Remove unused methods:
 TriangleComparePSP
 StartPointsCalcul.
 NextStartingPointsResearch
 StartingPointsResearch
(0065398)
git   
2017-04-20 15:24   
Branch CR28639 has been updated by emv.

SHA-1: d629fd18d4a161e98cce65f620c35955864f2068


Detailed log of new commits:

Author: emv
Date: Thu Apr 20 11:41:41 2017 +0300

    Correction of the *IntPolyh_Triangle* class.
    
    Upgrade guide has been updated with the removed methods.

Author: emv
Date: Wed Apr 19 16:36:01 2017 +0300

    Correction of the *IntPolyh_Point* class.

Author: emv
Date: Wed Apr 19 16:21:45 2017 +0300

    Correction of the *IntPolyh_Edge* class.

Author: emv
Date: Wed Apr 19 16:00:20 2017 +0300

    Correction of the clas *IntPolyh_Couple*.

Author: emv
Date: Wed Apr 19 14:58:28 2017 +0300

    // Corrections according to remarks;
    
    * The method *IntPolyh_Triangle::SetEdgeandOrientation* has been removed as unused;
    * The following methods of the *IntPolyh_MaillageAffinage* have been removed as unused:
     - *LinkEdges2Triangles*;
     - *TriangleEdgeContact2*;
     - *StartingPointsResearch2*;
     - *NextStartingPointsResearch2*;
     - *TriangleComparePSP*;
     - *StartPointsCalcul*.

(0065399)
emv   
2017-04-20 15:29   
Dear Mikhail, please review the updated branch. Do not pay too much attention to commit messages, they will be updated in the final branch with single commit.
(0065400)
git   
2017-04-20 15:30   
Branch CR28639_1 has been created by emv.

SHA-1: beb827d193b281b494b648717985d20db0c38c21


Detailed log of new commits:

Author: emv
Date: Fri Apr 7 07:43:44 2017 +0300

    0028639: Improve performance of the IntPolyh_MaillageAffinage algorithm
    
    The following improvements have been made:
    1. Linking edges to triangles while creating the edges.
    2. Replacing the array of couples of intersecting triangles with the list to avoid unnecessary allocations of memory.
    3. Using the algorithm of unbalanced binary tree when looking for pairs of interfering triangles.
    4. Building bounding boxes for the triangles only once and then reusing it.
    5. Making the simple methods of the IntPolyh_Point, IntPolyh_Edge, IntPolyh_Triangle, IntPolyh_Couple classes inline.
    6. The following methods of the *IntPolyh_Triangle* class have been removed as unused:
      - *CheckCommonEdge*
      - *SetEdgeandOrientation*
      - *MultipleMiddleRefinement2*.
    7. The method *IntPolyh_Triangle::TriangleDeflection* has been replaced with the *IntPolyh_Triangle::ComputeDeflection*.
    8. The following methods of the *IntPolyh_MaillageAffinage* class have been removed as unused:
      - *LinkEdges2Triangles*;
      - *TriangleEdgeContact2*;
      - *StartingPointsResearch2*;
      - *NextStartingPointsResearch2*;
      - *TriangleComparePSP*;
      - *StartPointsCalcul*.
(0065416)
msv   
2017-04-21 11:57   
Remarks:

src\IntPolyh\IntPolyh_Couple.hxx
src\IntPolyh\IntPolyh_Point.hxx
- Using of bit field is unjustified for only one variable.

src\IntPolyh\IntPolyh_Triangle.cxx
- in the method IntPolyh_Triangle::Dump, pass int argument to printf instead of bool.
(0065418)
git   
2017-04-21 12:08   
Branch CR28639_1 has been updated by emv.

SHA-1: d8dd328be4993a1edcb81c62c3349ed9d719fcf9


Detailed log of new commits:

Author: emv
Date: Fri Apr 21 12:08:17 2017 +0300

    // Corrections according to remarks.

(0065419)
emv   
2017-04-21 12:09   
Done. Please review the git branch CR28639_1.
(0065420)
msv   
2017-04-21 12:12   
Reviewed.
(0065428)
git   
2017-04-21 16:00   
Branch CR28639_1 has been updated forcibly by mkv.

SHA-1: 0ac0ed9c7fdbaae169278ccc4e016e8e83b3b6ce
(0065476)
mkv   
2017-04-24 14:23   
Dear BugMaster,
Branch CR28639_1 from occt git-repository (and master from products git-repository) was compiled on Linux, MacOS and Windows platforms and tested on Release mode.
SHA-1: 0ac0ed9c7fdbaae169278ccc4e016e8e83b3b6ce

Number of compiler warnings:

occt component :
Linux: 0 (0 on master)
Windows: 0 (0 on master)
MacOS : 0 (0 on master)

products component :
Linux: 64 (64 on master)
Windows: 0 (0 on master)
MacOS : 1195

Regressions/Differences/Improvements:
No regressions/differences

Testing cases:
Not needed

Testing on Linux:
occt component :
Total MEMORY difference: 91790382 / 91810384 [-0.02%]
Total CPU difference: 18996.680000000324 / 19561.10000000033 [-2.89%]
products component :
Total MEMORY difference: 31249691 / 31264414 [-0.05%]
Total CPU difference: 5414.379999999983 / 5400.509999999974 [+0.26%]
Testing on Windows:
occt component :
Total MEMORY difference: 58037467 / 58034445 [+0.01%]
Total CPU difference: 17316.891004998637 / 18122.277367698553 [-4.44%]
products component :
Total MEMORY difference: 22650125 / 22611847 [+0.17%]
Total CPU difference: 5318.339291699976 / 5410.192680499973 [-1.70%]

There are no differences in images found by testdiff.
(0065477)
mkv   
2017-04-24 14:24   
Dear BugMaster,
Branch CR28639_1 is TESTED.
(0065634)
git   
2017-04-28 12:24   
Branch CR28639_1 has been updated by emv.

SHA-1: 416145208d7ab4534e0de6b4544e355703e17616


Detailed log of new commits:

Author: emv
Date: Fri Apr 28 12:23:04 2017 +0300

    // Elimination of the warning.

(0065959)
git   
2017-05-12 11:36   
Branch CR28639 has been deleted by kgv.

SHA-1: d629fd18d4a161e98cce65f620c35955864f2068
(0065960)
git   
2017-05-12 11:36   
Branch CR28639_1 has been deleted by kgv.

SHA-1: 416145208d7ab4534e0de6b4544e355703e17616