View Issue Details
| ID | Project | Category | View Status | Date Submitted | Last Update |
|---|---|---|---|---|---|
| 0025234 | Open CASCADE | OCCT:Visualization | public | 2014-09-11 13:24 | 2014-11-11 13:02 |
| Reporter | Assigned To | bugmaster | |||
| Priority | normal | Severity | minor | ||
| Status | closed | Resolution | fixed | ||
| Product Version | 6.8.0 | ||||
| Target Version | 6.8.0 | Fixed in Version | 6.8.0 | ||
| Summary | 0025234: Implementing LBVH builder | ||||
| Description | A 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). | ||||
| Tags | No tags attached. | ||||
| Test case number | Not needed | ||||
|
|
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. |
|
|
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. |
|
|
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. |
|
|
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. |
|
|
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. |
|
|
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. |
|
|
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. |
|
|
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. |
|
|
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. |
|
|
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). |
|
|
Dear kgv, please review the patch in branch CR25234_2. |
|
|
Branch CR25234_2 has been deleted by dbp. SHA-1: 60a70ac33939141f22bed83626837627e7f9a1ed |
|
|
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). |
|
|
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. |
|
|
Dear abv, please review the patch in branch CR25234_2. |
|
|
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 |
|
|
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%. |
|
|
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). |
|
|
Dear abv, please review the patch in branch CR25234_4 (was rebased on 25277). |
|
|
Reviewed along with 0025159, to be tested together (CR25159_1) |
|
|
Tested in frame of issue 0025159 |
|
|
Branch CR25234_4 has been deleted by inv. SHA-1: eaee2ac665a242febe7018f5696c0edb8e426801 |
|
|
Branch CR25234_3 has been deleted by inv. SHA-1: 82f4e50860f1608427577347cf124a5b3991eef5 |
|
|
Branch CR25234_2 has been deleted by inv. SHA-1: e22799fd46a6edc63ade1201a6822d77d4aca018 |
|
|
Branch CR25234_1 has been deleted by inv. SHA-1: 8b903ade94e8b033b31d055d9910aa459735dda9 |
|
|
Branch CR25234 has been deleted by inv. SHA-1: 1073f24432168554705d2d45a7397a5d77ac7deb |
|
occt: master 0ef61b50 2014-09-24 15:32:40
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). |
Affected Issues 0025234 |
|
| 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 | ||
| Date Modified | Username | Field | Change |
|---|---|---|---|
| 2014-09-11 13:24 |
|
New Issue | |
| 2014-09-11 13:24 |
|
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 |
|
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 |
|
Note Added: 0031702 | |
| 2014-09-15 14:39 |
|
Assigned To | duv => kgv |
| 2014-09-15 14:39 |
|
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 |
|
Assigned To | kgv => abv |
| 2014-09-15 15:31 |
|
Status | resolved => assigned |
| 2014-09-15 15:31 |
|
Note Added: 0031708 | |
| 2014-09-15 15:31 |
|
Status | assigned => resolved |
| 2014-09-23 14:30 |
|
Relationship added | child of 0024623 |
| 2014-09-23 16:52 |
|
Relationship added | related to 0025227 |
| 2014-09-23 16:54 |
|
Note Added: 0032027 | |
| 2014-09-23 16:54 |
|
Assigned To | abv => duv |
| 2014-09-23 16:54 |
|
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 |
|
Note Added: 0032107 | |
| 2014-09-24 19:35 |
|
Assigned To | duv => abv |
| 2014-09-24 19:35 |
|
Status | assigned => resolved |
| 2014-09-24 19:40 |
|
Additional Information Updated | |
| 2014-10-01 20:11 |
|
Note Added: 0032542 | |
| 2014-10-01 20:11 |
|
Assigned To | abv => bugmaster |
| 2014-10-01 20:11 |
|
Status | resolved => reviewed |
| 2014-10-01 20:12 |
|
Relationship added | related to 0025159 |
| 2014-10-02 16:13 |
|
Assigned To | bugmaster => apv |
| 2014-10-07 16:37 |
|
Test case number | => Not needed |
| 2014-10-07 16:38 |
|
Note Added: 0032781 | |
| 2014-10-07 16:38 |
|
Assigned To | apv => bugmaster |
| 2014-10-07 16:38 |
|
Status | reviewed => tested |
| 2014-10-07 16:38 |
|
Note Edited: 0032781 | |
| 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 |
|
Fixed in Version | => 6.8.0 |
| 2014-11-11 13:02 |
|
Status | verified => closed |
