DiscussionsIssue archiveOCCT:Modeling Algorithms

Archived issue #0025413

Line-Shape intersection algorithm became 400 times slower

CommunityOCCT:Modeling Algorithmsclosed14 public notes

Search issues

Description

The speed of the Line-Shape intersection (IntCurvesFace_ShapeIntersector) got reduced 400 times. In an application, we are intersecting many lines (parallel to Z axis) with a shape. We could do over 70000 lines per minute with OCC until 6.5.2, and since 6.5.3 (at least until the last 6.7 we have tried) we get only around 150 lines per minute.

Is it possible to get again the speed of 6.5.2?

I have seen this downgrade in speed in Linux and Windows, 32 and 64 bit, gcc and Visual Studio.

Steps to reproduce

Measure the speed of IntCurvesFace_ShapeIntersector::Perform in OCC 6.5.2, and any later release.

The sample code:

#include <BRepBndLib.hxx>
#include <OSD_Timer.hxx>
#include <IntCurvesFace_ShapeIntersector.hxx>

static Standard_Integer test(Draw_Interpretor& di, Standard_Integer narg , const char** a)
{
  if (narg != 2) return 1;
  TopoDS_Shape aShape = DBRep::Get(a[1]);

  IntCurvesFace_ShapeIntersector Inter;
  Inter.Load(aShape, Precision::Confusion());

  Bnd_Box aBndBox;
  BRepBndLib::Add(aShape, aBndBox);

  gp_Dir aDir(0., 1., 0.);
  const int N = 250;
  Standard_Real xMin = aBndBox.CornerMin().X();
  Standard_Real zMin = aBndBox.CornerMin().Z();
  Standard_Real xMax = aBndBox.CornerMax().X();
  Standard_Real zMax = aBndBox.CornerMax().Z();
  Standard_Real xStep = (xMax - xMin) / N;
  Standard_Real zStep = (zMax - zMin) / N;

  OSD_Timer aTimer;
  aTimer.Start();
  for (Standard_Real x = xMin; x <= xMax; x += xStep)
    for (Standard_Real z = zMin; z <= zMax; z += zStep)
    {
      gp_Pnt aPoint(x, 0.0, z);
      gp_Lin aLine(aPoint, aDir);
      Inter.PerformNearest(aLine, -100., 100.);
    }
  aTimer.Stop();
  aTimer.Show();
  return 0;
}

Public activity

14 archived notes

Participants are labeled by their role within this record.

01Author
I reported this to OCE. There I reported how I found the culprit to be in the introduction in 6.5.3 of bFlag code:
https://github.com/tpaviot/oce/blob/master/src/IntCurvesFace/IntCurvesFace_Intersector.cxx#L116

If bFlag is set always to true, the speed of 6.5.2 is restored. Andrei Betenev suggests that this change (and huge slowdown) was introduced related to the ticket id 023089, which I don't know.

Maybe the code can be reworked so it doesn't slowdown the intersection in ANY iges, and fixes only the calculation in the specific case of 023089?
02Author
03Commenter 3
Hello, do you have some data to test that (e.g. face and set of lines or direction to be used)? The result may depend strongly on the data used (e.g. if the surface is NURBS or elementary).
04Author
Here you can pick an iges object. It doesn't run 400 times slower, but slower enough to show the problem. I have other pieces that exhibit the 400 times slower problem but I cannot share them.

I'll possibly keep the URL up only the next hours, so please pick it soon if you can:
https://[network address removed]:49257/rbmdxo/piece-slow-intersection.7z
05Commenter 5
I have downloaded the archive, but it contains really big shape. What kind of projections you do on it? Can you extract or indicate one face which would exhibit the problem, so that this can be tested more easily?
06Author
A projection of the front view (with a 250x250 grid, so, some thousands of lines) exhibits the time problem I think. By projection, I mean intersecting lines ortogonal to the front view with the object, and taking note of the first intersection point.
07Commenter 2
Branch [archived branch] has been created by Participant.

[revision removed]


Detailed log of new commits:

Author: azv
Date: Tue Oct 28 13:57:07 2014 +0300

    0025413: Line-Shape intersection algorithm became 400 times slower
    
    Changed the procedure of creating initial samples
08Commenter 8
Branch CR25413 is ready for review.
The procedure of generating initial samples for IntCurvesFace_Intersector was changed
09Commenter 2
Branch [archived branch] has been updated forcibly by Participant.

[revision removed]
10Commenter 10
Ok
11Commenter 11
I have prepared a sample code to reproduce the problem (see "Steps To Reproduce"). The attached shape produces very bad performance (approximately 1200 times slower without the fix).
12Commenter 2
Branch [archived branch] has been updated by Participant.

[revision removed]


Detailed log of new commits:

Author: apv
Date: Fri Oct 31 15:12:22 2014 +0300

    Test-case for issue #0025413

13Commenter 13
Dear Commenter 1,

Branch CR25413 (and products from GIT master) was compiled on Linux, MacOS and Windows platforms and tested.
[revision removed]

Number of compiler warnings:
occt component:
   Linux: 18 (18 on master)
   Windows: 0 (0 on master)
products component:
   Linux: 11 (11 on master)
   Windows: 1 (1 on master)

Regressions/Differences:
Not detected

Testing cases:
bugs modalg_5(010) bug25413 - OK
http://occt-tests/CR25413-master-occt/Debian60-64/bugs/modalg_5/bug25413.html
http://occt-tests/CR25413-master-occt/Windows-32-VC10/bugs/modalg_5/bug25413.html

Testing on Linux:
Total MEMORY difference: 372473200 / 371808660
Total CPU difference: 45760.15000000018 / 48296.64000000005

Testing on Windows:
Total MEMORY difference: 276795272 / 273087684
Total CPU difference: 44756.046875 / 37050.84375
14Commenter 2
Branch [archived branch] has been deleted by Participant.

[revision removed]