View Issue Details
| ID | Project | Category | View Status | Date Submitted | Last Update |
|---|---|---|---|---|---|
| 0007349 | Open CASCADE | OCCT:Foundation Classes | public | 2004-12-03 09:22 | 2012-01-16 18:21 |
| Reporter | Assigned To | ||||
| Priority | normal | Severity | feature | ||
| Status | closed | Resolution | fixed | ||
| OS | All | ||||
| Fixed in Version | 5.2.2 | ||||
| Summary | 0007349: New algorithm for binary tree of bounding boxes | ||||
| Description | OCCT has a lack in algorithm that makes possible to significantly increase performance of operations where the filtering of geometric objects by bounding boxes is used. Usually such filtering is performed sequentially on all bounding boxes, which can be very slow on large amount of boxes. I.e., the time of computation is a function of N, where N is a number of objects. When it is needed to compare each object with all others from a set of N objects, the time is dramatically increased to a function of N^2. The algorithm of binary tree of bounding boxes allows to reduce the computation time to a function of log(N) when making one filtering, and to N*log(N) when comparing all objects with each other. It is proposed to get the algorithm from the Express Mesh, the following classes located in Products workbench: QMTools_UBTree.hxx QMTools_EBTree.hxx QMTools_UBTreeFiller.hxx And to move them into the package NCollection, renaming the files and classes names. The classes are written as C++ templates, and can be used on a wide range of geometric substances, such as points, segments, curves, shapes, mesh elements. | ||||
| Additional information and documentation updates | Documentation remark, added by MSV 2004-12-15 09:42:19: New features: The new algorithm of binary tree of bounding boxes (NCollection_UBTree) implemented in the form of C++ template makes possible to significantly increase performance of operations where the filtering of geometric objects by bounding boxes is used. It allows to reduce the computation time to a function of N*log(N) when comparing all objects with each other in the set of N objects, as opposed to a direct method that takes N*N operations. Modified entities: New files in the package NCollection: NCollection_UBTree.hxx NCollection_EBTree.hxx NCollection_UBTreeFiller.hxx | ||||
| Tags | No tags attached. | ||||
| Test case number | |||||
| Date Modified | Username | Field | Change |
|---|---|---|---|
| 2004-12-03 12:26 | bugmaster | Assigned To | bugmaster => msv |
| 2004-12-03 12:26 | bugmaster | Status | new => assigned |
| 2004-12-06 11:16 | bugmaster | Status | assigned => verified |
| 2004-12-24 08:58 | bugmaster | Status | verified => closed |
| 2004-12-24 08:58 | bugmaster | Resolution | @0@ => fixed |
| 2011-08-02 11:23 | bugmaster | Category | OCCT:FDC => OCCT:Foundation Classes |
| 2012-01-16 18:21 |
|
Description Updated | |
| 2012-01-16 18:21 |
|
Additional Information Updated |
