View Issue Details

IDProjectCategoryView StatusLast Update
0028746CommunityOCCT:Modeling Algorithmspublic2020-01-22 10:10
Reporteraothms Assigned Tobugmaster  
PrioritynormalSeverityminor 
Status closedResolutionno change required 
PlatformWindowsOSVC++ 2015 
Summary0028746: Stack overflow on NCollection_UBTree::Select
DescriptionHi,

When performing a boolean operation with operands of ~ 15000 faces [at least on Windows with default stack size] the stack overflows due to the recursive nature of NCollection_UBTree::Select(). I can happily create a test case, but it is a fairly general problem that I think we can discuss without. What is your point of view on this, should users simply take care of allocating a stack large enough for their operations to complete, is it a possibility to rewrite NCollection_UBTree::Select() without recursion, are these kind of operations better performed on a lighter mesh-based geometry kernel? Curious to hear your thoughts.

Kind regards,
Thomas
TagsNo tags attached.
Test case number

Attached Files

  • shapes.7z (3,276,187 bytes)

Activities

msv

2017-05-18 09:50

developer   ~0066236

You are first to report stack overflow issue on UBTree::Select for decades.
Implementation of the method Select is pretty simple due to its recursive nature. Then it was decided not to make more complex implementation.
Well, as it occurred, it should be solved. But anyway we need to create non-regression test. For that, please attach all necessary data to reproduce it.

aothms

2017-05-18 18:45

reporter   ~0066296

Many thanks for your reply.

The following script will crash DRAW:

_____________________
pload ALL
mu4
restore a.brep a
restore b.brep b
fit
bcut ab1 a b
_____________________


Interestingly, using `cut` instead of `bcut` does seem to work. Is there an overview somewhere of how the DRAW commands relate to C++?

Also note that it is not simply a matter of number of faces. My first attempt was to reproduce using arbitrarily generated solids, but didn't encounter issues. Perhaps there is something in this input files that makes the tree particularly unbalanced? Just guessing.

emv

2017-05-19 08:24

developer  

shapes.7z (3,276,187 bytes)

msv

2017-05-19 09:19

developer   ~0066298

Thomas, thank you for the shapes.
a.b.brep actually is a zip-file. It has been repacked to shapes.7z.
However, I could not reproduce the problem. The algorithm completes with no error.
Please tell the following info:
- What version of OCCT do you use?
- What compiler do you use and what version? E.g., MSVC 2013.
- How did you built OCCT? Did you use pre-built binaries in package? Or built using cmake, or genproj.bat?
- Which customization you did in standard compile settings?
- Is the issue reproduced in debug build?

As for your questions, 'cut' runs old deprecated Boolean algorithm, 'bcut' uses the current actual algorithm. To get file name of the source code of the draw command, use the command 'getsourcefile'. It is all described in the Draw developer user guide (https://dev.opencascade.org/doc/overview/html/occt_dev_guides__tests.html#testmanual_3_3).

UBTree by default is unbalanced. In order to get it quasi-balanced, a special randomization procedure is used (NCollection_UBTreeFiller).

aothms

2017-05-19 15:47

reporter   ~0066330

Hi msv, many thanks for checking.

> a.b.brep actually is a zip-file. It has been repacked to shapes.7z.

Had to compress the files to comply with the max file size here on mantis. Not sure what happened with the file extension though, sorry for the confusion.

> However, I could not reproduce the problem. The algorithm completes with no error.

That is odd, I have tried DRAW from the prebuilt packages for vc10 6.9.1 7.0.0 7.1.0. All with this problem. In my own vc14 6.9.1 environment I encounter the issue in both debug and release builds.

How to proceed? I don't think on Windows there are environment settings that influence behaviour of the stack (contrary to nix). Also note that this issue has been reported by one of my users [1], so at least one other person is able to reproduce this issue.

[1] https://github.com/IfcOpenShell/IfcOpenShell/issues/213

------------------------------------------------

> - What version of OCCT do you use?

6.9.1 7.0.0 7.1.0

> - What compiler do you use and what version? E.g., MSVC 2013.

MSVC 2010 (prebuilt) and MSVC 2015

> - How did you built OCCT? Did you use pre-built binaries in package? Or built using
cmake, or genproj.bat?

pre-built binaries and CMake

> - Which customization you did in standard compile settings?

None

> - Is the issue reproduced in debug build?

Yes

------------------------------------------------

> It is all described in the Draw developer user guide

Thanks!

msv

2017-05-19 16:27

developer   ~0066335

What is OS version on your computer and on computer of your user? Is OCCT build 32 or 64 bit?

msv

2017-05-19 16:39

developer   ~0066337

I have reproduced with current OCCT version built in 32-bit mode. 64-bit build has no such issue.

msv

2017-05-19 17:02

developer   ~0066340

The best solution is to switch from NCollection_UBTree to BVH tree. The last is much more effective and contains no such issues.

msv

2017-05-19 17:03

developer   ~0066341

This issue will be postponed till available resources are present.

msv

2019-12-26 15:49

developer   ~0089779

Now Boolean operations use BVH instead of UBTree.
Our trend is to switch to BVH other OCCT algorithms.
So, this issue can be closed.

aothms

2019-12-30 12:54

reporter   ~0089823

Thanks for letting us know, much appreciated!

Issue History

Date Modified Username Field Change
2017-05-17 14:04 aothms New Issue
2017-05-17 14:04 aothms Assigned To => msv
2017-05-18 09:50 msv Note Added: 0066236
2017-05-18 09:50 msv Assigned To msv => aothms
2017-05-18 09:50 msv Status new => feedback
2017-05-18 18:40 aothms File Added: a.b.brep
2017-05-18 18:45 aothms Note Added: 0066296
2017-05-19 08:24 emv File Added: shapes.7z
2017-05-19 09:05 msv File Deleted: a.b.brep
2017-05-19 09:19 msv Note Added: 0066298
2017-05-19 15:47 aothms Note Added: 0066330
2017-05-19 16:27 msv Note Added: 0066335
2017-05-19 16:39 msv Note Added: 0066337
2017-05-19 17:02 msv Note Added: 0066340
2017-05-19 17:03 msv Note Added: 0066341
2017-05-19 17:03 msv Assigned To aothms => msv
2017-05-19 17:03 msv Status feedback => assigned
2019-12-26 15:49 msv Note Added: 0089779
2019-12-26 15:49 msv Assigned To msv => bugmaster
2019-12-26 15:49 msv Status assigned => feedback
2019-12-30 12:54 aothms Note Added: 0089823
2020-01-22 10:10 bugmaster Status feedback => closed
2020-01-22 10:10 bugmaster Resolution open => no change required