View Issue Details

IDProjectCategoryView StatusLast Update
0011403Open CASCADEOCCT:Foundation Classespublic2012-01-13 18:32
ReporteragvAssigned Toagv 
PrioritynormalSeverityfeature 
Status closedResolutionfixed 
OSAll 
Fixed in Version6.1.0 
Summary0011403: NCollection_UBTreeFiller is too slow
DescriptionThe complexity of NCollection_UBTreeFiller is O(n**2) because of the
randomization algorithm using sequence collection. This is important when the
number of objects becomes greater than 100,000, the delays are too long.
Additional information
and documentation updates
Documentation remark, added by AGV 2006-01-27 13:03:20:

New features:
1. Performance of tree filling operation increased. On PentiumIV(2.4GHz), with a
model of 1,000,000 triangles the tree is filled:
   - before: in 554sec,
   - now: in 21sec.
2. New method is added to UBFiller class: CheckTree. This method outputs the
size of the tree and the balance factor. The latter is the mean square length of
all tree branches divided by the minimal theoretical length. The greater the
factor, the less balanced is the tree.
Improvements:
1. INTERNAL: In UBFiller class Vector collection is used instead of Sequence,
with the relevant algorithm of randomization
2. INTERNAL: In UBTree class the method Add() was slightly modified to avoid
extra data copying. The additional gain of performance is ~10%.
Changes:
The previous public API of the modified classes has not been changed, but for
one point:

In UBTreeFiller constructor the parameter is added: isFullRandom, True as
default. The value True ensures the correct randomization of large tree sizes
(50,000 or more) ; with False - the randomization proceeds in a window RAND_MAX
wide (32767 values). In my test with 1,000,000 triangles I obtained:
 isFullRandom == True: filling time 21sec, balance 3.3
 isFullRandom == False: filling time 15sec, balance 9.0
Modified entities:
NCollection_UBTree
NCollection_UBTreeFiller

TagsNo tags attached.
Test case number

Attached Files

  • OCC11403-fix.tar.gz (6,586 bytes)

Activities

2006-01-27 12:47

 

OCC11403-fix.tar.gz (6,586 bytes)

Issue History

Date Modified Username Field Change
2006-01-27 14:31 bugmaster Assigned To bugmaster => agv
2006-01-27 14:31 bugmaster Status new => assigned
2006-01-27 15:05 agv CC => msv
2006-01-27 15:05 agv Status assigned => resolved
2006-02-20 16:49 aki Status resolved => tested
2006-02-20 16:51 bugmaster CC => imv
2006-02-28 11:21 bugmaster OtherBugsDependingOnThis => 11768
2006-04-06 15:55 bugmaster Status tested => closed
2006-04-06 15:55 bugmaster Resolution @0@ => fixed
2011-08-02 11:23 bugmaster Category OCCT:FDC => OCCT:Foundation Classes
2012-01-13 18:32 atp Description Updated
2012-01-13 18:32 atp Additional Information Updated