MantisBT
Mantis Bug Tracker Workflow

View Issue Details Jump to Notes ] Related Changesets ] Issue History ] Print ]
IDProjectCategoryView StatusDate SubmittedLast Update
0025234Open CASCADE[OCCT] OCCT:Visualizationpublic2014-09-11 13:242014-11-11 13:02
Reporterduv 
Assigned Tobugmaster 
PrioritynormalSeverityminor 
StatusclosedResolutionfixed 
PlatformOSOS Version
Product Version[OCCT] 6.8.0 
Target Version[OCCT] 6.8.0Fixed in Version[OCCT] 6.8.0 
Summary0025234: Implementing LBVH builder
DescriptionA fast LBVH builder is necessary for new selection algorithm and other tasks.
Additional information
and documentation updates
Linear BVH reduces the problem of BVH building to spatial sort along Morton curve (or Z curve). Sorting itself is implemeted by using radix-sort algorithm with O(N) complexity. Heavy stages of the algorithm were parallelized with Intel TBB. In sum, new builder processes more than 4M triangles per second (on quad core Intel i5-3450).
TagsNo tags attached.
Test case numberNot needed
Attached Files

- Relationships
related to 0025227closedbugmaster Visualization - optimize BVH binned builder 
related to 0025159closedbugmaster Collections and common types in BVH package are named in non-conformant manner 
child of 0024623closedbugmaster Visualization - improve selection mechanism 

-  Notes
(0031613)
git (administrator)
2014-09-11 14:26

Branch CR25234 has been created by dbp.

SHA-1: b933217e09321d98eea2165a5c78bea009a42c27


Detailed log of new commits:

Author: dbp
Date: Thu Sep 11 14:26:04 2014 +0400

    Initial.
(0031643)
git (administrator)
2014-09-12 10:23

Branch CR25234 has been updated by dbp.

SHA-1: 45a424fcec9f782defe8acba05275a43031beb5c


Detailed log of new commits:

Author: dbp
Date: Fri Sep 12 10:19:10 2014 +0400

    Update.

(0031656)
git (administrator)
2014-09-12 12:30

Branch CR25234 has been updated by duv.

SHA-1: 693a3980015bc5f9af5422c17b95ec8f150ceed0


Detailed log of new commits:

Author: duv
Date: Fri Sep 12 12:29:51 2014 +0400

    Linear builder fixed.

(0031676)
git (administrator)
2014-09-12 16:15

Branch CR25234 has been updated by dbp.

SHA-1: 1375185180e37e84fd69a1810bc99b47c7bb5392


Detailed log of new commits:

Author: dbp
Date: Fri Sep 12 16:15:16 2014 +0400

    Fix critical bug.

(0031681)
git (administrator)
2014-09-12 18:42

Branch CR25234 has been updated by dbp.

SHA-1: 1073f24432168554705d2d45a7397a5d77ac7deb


Detailed log of new commits:

Author: dbp
Date: Fri Sep 12 18:42:16 2014 +0400

    Optimize LBVH.

(0031687)
git (administrator)
2014-09-12 19:31

Branch CR25234_1 has been created by dbp.

SHA-1: 9e73c0c35af1643facc2f32bf05d877fc68b62ba


Detailed log of new commits:

Author: dbp
Date: Fri Sep 12 19:30:47 2014 +0400

    Optimize LBVH.

Author: dbp
Date: Fri Sep 12 18:42:16 2014 +0400

    Optimize LBVH.

Author: dbp
Date: Fri Sep 12 16:15:16 2014 +0400

    Fix critical bug.

Author: duv
Date: Fri Sep 12 12:29:51 2014 +0400

    Linear builder fixed.

Author: dbp
Date: Fri Sep 12 10:19:10 2014 +0400

    Update.

Author: dbp
Date: Thu Sep 11 14:26:04 2014 +0400

    Initial.
(0031694)
git (administrator)
2014-09-15 11:26

Branch CR25234_1 has been updated by dbp.

SHA-1: 1327482a2c60e5d0aa06fc6f9ac7a7e6728c15be


Detailed log of new commits:

Author: dbp
Date: Mon Sep 15 11:25:57 2014 +0400

    Optimize LBVH builder.

(0031695)
git (administrator)
2014-09-15 12:20

Branch CR25234_1 has been updated by dbp.

SHA-1: 27cf5bc66a169b6eb039d8f5b982d85e6e4247b9


Detailed log of new commits:

Author: dbp
Date: Mon Sep 15 12:19:53 2014 +0400

    Optimize radix sort function.

(0031699)
git (administrator)
2014-09-15 13:28

Branch CR25234_1 has been updated by dbp.

SHA-1: 8b903ade94e8b033b31d055d9910aa459735dda9


Detailed log of new commits:

Author: dbp
Date: Mon Sep 15 13:28:26 2014 +0400

    Cosmetics.

(0031701)
git (administrator)
2014-09-15 14:38

Branch CR25234_2 has been created by dbp.

SHA-1: 60a70ac33939141f22bed83626837627e7f9a1ed


Detailed log of new commits:

Author: dbp
Date: Mon Sep 15 14:35:44 2014 +0400

    0025234: Implementing LBVH builder
    Performs fast BVH construction using LBVH building approach. Algorithm uses spatial Morton codes to reduce the BVH construction problem to a sorting problem (radix sort -- O(N) complexity). This Linear Bounding Volume Hierarchy (LBVH) builder produces BVH trees of lower quality compared to SAH-based BVH builders but it is over an order of magnitude faster (up to 3M triangles per second).
(0031702)
dbp (developer)
2014-09-15 14:39

Dear kgv,

please review the patch in branch CR25234_2.
(0031704)
git (administrator)
2014-09-15 15:20

Branch CR25234_2 has been deleted by dbp.

SHA-1: 60a70ac33939141f22bed83626837627e7f9a1ed
(0031705)
git (administrator)
2014-09-15 15:20

Branch CR25234_2 has been created by dbp.

SHA-1: 1789d9ca8e01032cfc9ee4df938e86161b4ab2b4


Detailed log of new commits:

Author: dbp
Date: Mon Sep 15 15:19:33 2014 +0400

    0025234: Implementing LBVH builder
    Performs fast BVH construction using LBVH building approach. Algorithm uses spatial Morton codes to reduce the BVH construction problem to a sorting problem (radix sort -- O(N) complexity). This Linear Bounding Volume Hierarchy (LBVH) builder produces BVH trees of lower quality compared to SAH-based BVH builders but it is over an order of magnitude faster (up to 3M triangles per second).
(0031706)
git (administrator)
2014-09-15 15:29

Branch CR25234_2 has been updated by dbp.

SHA-1: e22799fd46a6edc63ade1201a6822d77d4aca018


Detailed log of new commits:

Author: dbp
Date: Mon Sep 15 15:29:09 2014 +0400

    Add compile-time checking.

(0031708)
dbp (developer)
2014-09-15 15:31

Dear abv,

please review the patch in branch CR25234_2.
(0032027)
abv (manager)
2014-09-23 16:54

I have no remarks on the changes made, however it seems to be not reasonable to test the fix since it is based on patch for 0025227 which is not yet ready. Please rebase this branch on new version of fix for 0025227
(0032105)
git (administrator)
2014-09-24 19:29

Branch CR25234_3 has been created by dbp.

SHA-1: 82f4e50860f1608427577347cf124a5b3991eef5


Detailed log of new commits:

Author: dbp
Date: Wed Sep 24 19:29:17 2014 +0400

    Parallelizing LBVH builder.

Author: dbp
Date: Mon Sep 15 15:29:09 2014 +0400

    Add compile-time checking.

Author: dbp
Date: Mon Sep 15 15:19:33 2014 +0400

    0025234: Implementing LBVH builder
    Performs fast BVH construction using LBVH building approach. Algorithm uses spatial Morton codes to reduce the BVH construction problem to a sorting problem (radix sort -- O(N) complexity). This Linear Bounding Volume Hierarchy (LBVH) builder produces BVH trees of lower quality compared to SAH-based BVH builders but it is over an order of magnitude faster (up to 3M triangles per second).

Author: dbp
Date: Thu Sep 11 13:37:48 2014 +0400

    Cosmetics.

Author: dbp
Date: Wed Sep 10 12:37:14 2014 +0400

    0025227: Visualization - optimize BVH binned builder
    BVH binned builder is used for different rendering aspects, such as view frustum culling, ray-tracing, and (in future) for selection. It is desirable to improve builder performance. This simple patch decreases BVH building time for 30-35%.
(0032106)
git (administrator)
2014-09-24 19:33

Branch CR25234_4 has been created by dbp.

SHA-1: eaee2ac665a242febe7018f5696c0edb8e426801


Detailed log of new commits:

Author: dbp
Date: Wed Sep 24 19:32:40 2014 +0400

    0025234: Implementing LBVH builder
    
    Performs fast BVH construction using LBVH building approach. Algorithm uses spatial Morton codes to reduce the BVH construction problem to a sorting problem (radix sort -- O(N) complexity). This Linear Bounding Volume Hierarchy (LBVH) builder produces BVH trees of lower quality compared to SAH-based BVH builders but it is over an order of magnitude faster (up to 4M triangles per second).
(0032107)
dbp (developer)
2014-09-24 19:35

Dear abv,

please review the patch in branch CR25234_4 (was rebased on 25277).
(0032542)
abv (manager)
2014-10-01 20:11

Reviewed along with 0025159, to be tested together (CR25159_1)
(0032781)
apv (tester)
2014-10-07 16:38
edited on: 2014-10-07 16:38

Tested in frame of issue 0025159

(0033474)
git (administrator)
2014-10-21 16:44

Branch CR25234_4 has been deleted by inv.

SHA-1: eaee2ac665a242febe7018f5696c0edb8e426801
(0033475)
git (administrator)
2014-10-21 16:44

Branch CR25234_3 has been deleted by inv.

SHA-1: 82f4e50860f1608427577347cf124a5b3991eef5
(0033480)
git (administrator)
2014-10-21 16:45

Branch CR25234_2 has been deleted by inv.

SHA-1: e22799fd46a6edc63ade1201a6822d77d4aca018
(0033481)
git (administrator)
2014-10-21 16:45

Branch CR25234_1 has been deleted by inv.

SHA-1: 8b903ade94e8b033b31d055d9910aa459735dda9
(0033482)
git (administrator)
2014-10-21 16:45

Branch CR25234 has been deleted by inv.

SHA-1: 1073f24432168554705d2d45a7397a5d77ac7deb

- Related Changesets
occt: master 0ef61b50
Timestamp: 2014-09-24 15:32:40
Author: dbp
Committer: bugmaster
Details ] Diff ]
0025234: Implementing LBVH builder

Performs fast BVH construction using LBVH building approach. Algorithm uses spatial Morton codes to reduce the BVH construction problem to a sorting problem (radix sort -- O(N) complexity). This Linear Bounding Volume Hierarchy (LBVH) builder produces BVH trees of lower quality compared to SAH-based BVH builders but it is over an order of magnitude faster (up to 4M triangles per second).
mod - src/BVH/BVH.cxx Diff ] File ]
mod - src/BVH/BVH_BinnedBuilder.hxx Diff ] File ]
mod - src/BVH/BVH_BinnedBuilder.lxx Diff ] File ]
mod - src/BVH/BVH_Builder.hxx Diff ] File ]
mod - src/BVH/BVH_Builder.lxx Diff ] File ]
add - src/BVH/BVH_LinearBuilder.hxx Diff ] File ]
add - src/BVH/BVH_LinearBuilder.lxx Diff ] File ]
add - src/BVH/BVH_QueueBuilder.hxx Diff ] File ]
add - src/BVH/BVH_QueueBuilder.lxx Diff ] File ]
mod - src/BVH/BVH_SweepPlaneBuilder.hxx Diff ] File ]
mod - src/BVH/BVH_SweepPlaneBuilder.lxx Diff ] File ]
mod - src/BVH/BVH_Tree.hxx Diff ] File ]
mod - src/BVH/BVH_Tree.lxx Diff ] File ]
mod - src/BVH/BVH_Triangulation.lxx Diff ] File ]
mod - src/BVH/BVH_Types.hxx Diff ] File ]
mod - src/BVH/BVH_Types.lxx Diff ] File ]
mod - src/BVH/FILES Diff ] File ]

- Issue History
Date Modified Username Field Change
2014-09-11 13:24 duv New Issue
2014-09-11 13:24 duv Assigned To => duv
2014-09-11 14:26 git Note Added: 0031613
2014-09-12 10:23 git Note Added: 0031643
2014-09-12 12:30 git Note Added: 0031656
2014-09-12 16:15 git Note Added: 0031676
2014-09-12 18:42 git Note Added: 0031681
2014-09-12 19:31 git Note Added: 0031687
2014-09-15 11:21 duv Status new => assigned
2014-09-15 11:26 git Note Added: 0031694
2014-09-15 12:20 git Note Added: 0031695
2014-09-15 13:28 git Note Added: 0031699
2014-09-15 14:38 git Note Added: 0031701
2014-09-15 14:39 dbp Note Added: 0031702
2014-09-15 14:39 dbp Assigned To duv => kgv
2014-09-15 14:39 dbp Status assigned => resolved
2014-09-15 15:20 git Note Added: 0031704
2014-09-15 15:20 git Note Added: 0031705
2014-09-15 15:29 git Note Added: 0031706
2014-09-15 15:31 dbp Note Added: 0031707
2014-09-15 15:31 dbp Assigned To kgv => abv
2014-09-15 15:31 dbp Status resolved => assigned
2014-09-15 15:31 dbp Note Deleted: 0031707
2014-09-15 15:31 dbp Note Added: 0031708
2014-09-15 15:31 dbp Status assigned => resolved
2014-09-23 14:30 abv Relationship added child of 0024623
2014-09-23 16:52 abv Relationship added related to 0025227
2014-09-23 16:54 abv Note Added: 0032027
2014-09-23 16:54 abv Assigned To abv => duv
2014-09-23 16:54 abv Status resolved => assigned
2014-09-24 19:29 git Note Added: 0032105
2014-09-24 19:33 git Note Added: 0032106
2014-09-24 19:35 dbp Note Added: 0032107
2014-09-24 19:35 dbp Assigned To duv => abv
2014-09-24 19:35 dbp Status assigned => resolved
2014-09-24 19:40 dbp Additional Information Updated View Revisions
2014-10-01 20:11 abv Note Added: 0032542
2014-10-01 20:11 abv Assigned To abv => bugmaster
2014-10-01 20:11 abv Status resolved => reviewed
2014-10-01 20:12 abv Relationship added related to 0025159
2014-10-02 16:13 apv Assigned To bugmaster => apv
2014-10-07 16:37 apv Test case number => Not needed
2014-10-07 16:38 apv Note Added: 0032781
2014-10-07 16:38 apv Assigned To apv => bugmaster
2014-10-07 16:38 apv Status reviewed => tested
2014-10-07 16:38 apv Note Edited: 0032781 View Revisions
2014-10-13 17:52 bugmaster Changeset attached => occt master 0ef61b50
2014-10-13 17:52 bugmaster Status tested => verified
2014-10-13 17:52 bugmaster Resolution open => fixed
2014-10-21 16:44 git Note Added: 0033474
2014-10-21 16:44 git Note Added: 0033475
2014-10-21 16:45 git Note Added: 0033480
2014-10-21 16:45 git Note Added: 0033481
2014-10-21 16:45 git Note Added: 0033482
2014-11-11 12:43 aiv Fixed in Version => 6.8.0
2014-11-11 13:02 aiv Status verified => closed


Copyright © 2000 - 2019 MantisBT Team
Powered by Mantis Bugtracker