MantisBT
Mantis Bug Tracker Workflow

View Issue Details Jump to Notes ] Related Changesets ] Issue History ] Print ]
IDProjectCategoryView StatusDate SubmittedLast Update
0028639Open CASCADE[OCCT] OCCT:Modeling Algorithmspublic2017-04-07 07:342017-05-12 11:36
Reporteremv 
Assigned Tobugmaster 
PrioritynormalSeverityminor 
StatusverifiedResolutionfixed 
PlatformOSOS Version
Product Version[OCCT] 7.1.0 
Target Version[OCCT] 7.2.0*Fixed in Version 
Summary0028639: Improve performance of the IntPolyh_MaillageAffinage algorithm
DescriptionThe 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.
Steps To ReproduceNot needed.
TagsNo tags attached.
Test case numberNot needed
Attached Files

- Relationships
related to 0028599assignedemv Replacement of old Boolean operations with new ones in BRepProj_Projection algorithm 

-  Notes
(0065164)
git (administrator)
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 (developer)
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 (administrator)
2017-04-14 13:06

Branch CR28639 has been updated forcibly by emv.

SHA-1: 34e5d782d6c90ab6d875d3efbf5f0a8dff676461
(0065215)
emv (developer)
2017-04-14 13:06

The branch CR28474 has been rebased on current master.
(0065217)
git (administrator)
2017-04-14 13:16

Branch CR28639 has been updated forcibly by emv.

SHA-1: 109fb801f0c23e8aa4da85884a42d68acac73316
(0065330)
msv (developer)
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 (administrator)
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 (developer)
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 (administrator)
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 (developer)
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 (administrator)
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 (developer)
2017-04-21 12:09

Done. Please review the git branch CR28639_1.
(0065420)
msv (developer)
2017-04-21 12:12

Reviewed.
(0065428)
git (administrator)
2017-04-21 16:00

Branch CR28639_1 has been updated forcibly by mkv.

SHA-1: 0ac0ed9c7fdbaae169278ccc4e016e8e83b3b6ce
(0065476)
mkv (tester)
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 (tester)
2017-04-24 14:24

Dear BugMaster,
Branch CR28639_1 is TESTED.
(0065634)
git (administrator)
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 (administrator)
2017-05-12 11:36

Branch CR28639 has been deleted by kgv.

SHA-1: d629fd18d4a161e98cce65f620c35955864f2068
(0065960)
git (administrator)
2017-05-12 11:36

Branch CR28639_1 has been deleted by kgv.

SHA-1: 416145208d7ab4534e0de6b4544e355703e17616

- Related Changesets
occt: master 68b07699
Timestamp: 2017-04-07 04:43:44
Author: emv
Committer: bugmaster
Details ] Diff ]
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*.
mod - src/IntPolyh/IntPolyh_Edge.cxx Diff ] File ]
mod - src/IntPolyh/IntPolyh_Intersection.cxx Diff ] File ]
mod - src/IntPolyh/IntPolyh_Point.hxx Diff ] File ]
mod - src/IntPolyh/IntPolyh_Couple.hxx Diff ] File ]
mod - src/IntPolyh/IntPolyh_Triangle.cxx Diff ] File ]
add - src/IntPolyh/IntPolyh_CoupleMapHasher.hxx Diff ] File ]
mod - src/IntPolyh/IntPolyh_Intersection.hxx Diff ] File ]
mod - src/IntPolyh/IntPolyh_Intersection_1.cxx Diff ] File ]
mod - src/IntPolyh/IntPolyh_MaillageAffinage.hxx Diff ] File ]
mod - src/IntPolyh/IntPolyh_Edge.hxx Diff ] File ]
rm - src/IntPolyh/IntPolyh_ArrayOfStartPoints.hxx Diff ] File ]
mod - src/IntPolyh/IntPolyh_MaillageAffinage.cxx Diff ] File ]
mod - src/IntPolyh/IntPolyh_Point.cxx Diff ] File ]
mod - src/IntPolyh/FILES Diff ] File ]
mod - dox/dev_guides/upgrade/upgrade.md Diff ] File ]
mod - src/IntPolyh/IntPolyh_Couple.cxx Diff ] File ]
mod - src/IntPolyh/IntPolyh_Triangle.hxx Diff ] File ]

- Issue History
Date Modified Username Field Change
2017-04-07 07:34 emv New Issue
2017-04-07 07:34 emv Assigned To => msv
2017-04-07 07:34 emv Assigned To msv => emv
2017-04-07 07:34 emv Status new => assigned
2017-04-07 09:28 emv Relationship added related to 0028599
2017-04-12 10:05 git Note Added: 0065164
2017-04-12 10:09 emv Note Added: 0065165
2017-04-12 10:09 emv Assigned To emv => msv
2017-04-12 10:09 emv Status assigned => resolved
2017-04-12 10:09 emv Steps to Reproduce Updated View Revisions
2017-04-12 10:13 emv Note Edited: 0065165 View Revisions
2017-04-12 10:14 emv Note Edited: 0065165 View Revisions
2017-04-14 13:06 git Note Added: 0065214
2017-04-14 13:06 emv Note Added: 0065215
2017-04-14 13:16 git Note Added: 0065217
2017-04-19 10:27 msv Note Added: 0065330
2017-04-19 10:27 msv Assigned To msv => emv
2017-04-19 10:27 msv Status resolved => assigned
2017-04-20 15:24 git Note Added: 0065398
2017-04-20 15:29 emv Note Added: 0065399
2017-04-20 15:29 emv Assigned To emv => msv
2017-04-20 15:29 emv Status assigned => resolved
2017-04-20 15:30 git Note Added: 0065400
2017-04-21 11:57 msv Note Added: 0065416
2017-04-21 11:57 msv Assigned To msv => emv
2017-04-21 11:57 msv Status resolved => assigned
2017-04-21 12:08 git Note Added: 0065418
2017-04-21 12:09 emv Note Added: 0065419
2017-04-21 12:09 emv Assigned To emv => msv
2017-04-21 12:09 emv Status assigned => resolved
2017-04-21 12:12 msv Note Added: 0065420
2017-04-21 12:12 msv Assigned To msv => bugmaster
2017-04-21 12:12 msv Status resolved => reviewed
2017-04-21 12:34 mkv Assigned To bugmaster => mkv
2017-04-21 16:00 git Note Added: 0065428
2017-04-24 14:23 mkv Note Added: 0065476
2017-04-24 14:24 mkv Note Added: 0065477
2017-04-24 14:24 mkv Assigned To mkv => bugmaster
2017-04-24 14:24 mkv Status reviewed => tested
2017-04-24 14:24 mkv Test case number => Not needed
2017-04-28 12:24 git Note Added: 0065634
2017-04-28 13:08 bugmaster Changeset attached => occt master 68b07699
2017-04-28 13:08 bugmaster Status tested => verified
2017-04-28 13:08 bugmaster Resolution open => fixed
2017-05-12 11:36 git Note Added: 0065959
2017-05-12 11:36 git Note Added: 0065960


Copyright © 2000 - 2017 MantisBT Team
Powered by Mantis Bugtracker