MantisBT - Open CASCADE
View Issue Details
0027590Open CASCADE[OCCT] OCCT:Visualizationpublic2016-06-10 13:062017-01-18 14:05
dbp 
bugmaster 
normalfeature 
closedfixed 
 
[OCCT] 7.1.0[OCCT] 7.1.0 
Not needed
0027590: Visualization, Ray Tracing - port to quad BVH trees (QBVH)
Currently, OCCT ray-tracing core (like many other render engines) uses binary BVH trees to accelerate ray-triangle intersection tests. However, binary trees have some drawbacks:

1/ Big height of the tree for complex scenes resulting in large stack size needed for BVH traversal. As we can see, stack size is one of the most critical points affecting performance of GLSL-based ray-tracing.

2/ Significant divergence of thread execution paths caused by many iterations over tree structure. At the same time, we are interested in maximum coherence of threads in order to keep GPU busy.

3/ Significant memory consumption of binary BVH. We need to store ~2N nodes for N primitives.

In view these considerations, it is reasonable to evaluate (and possibly to migrate) the quad BVH (QBVH) accelerating structure. This type of BVH is produced by flattening standard binary BVH (by leaving out intermediate levels). As a result, each BVH node contains up to 4 child nodes. In this way, we achieve a smaller memory consumption and favor thread coherency. However, the main challange here is to keep stack size equal to tree height. In conventional QBVH, we need stack of size 3H (where H is tree height) to store all potentially hit nodes. To overcome this limitation it is proposed to reserve few bits in node index in order to store additional information.
N/A
Please find brief overview of new implementation in the file attached.
No tags attached.
related to 0028368closed apn TKMath, BVH - Fix invalid tree height in QBVH 
pdf QBVH_gtc_2016.pdf (2,274,141) 2016-10-27 23:10
https://tracker.dev.opencascade.org/
Issue History
2016-06-10 13:06dbpNew Issue
2016-06-10 13:06dbpAssigned To => dbp
2016-06-10 16:23gitNote Added: 0054916
2016-06-14 10:14dbpNote Added: 0054936
2016-06-14 10:14dbpAssigned Todbp => kgv
2016-06-14 10:14dbpStatusnew => resolved
2016-06-14 10:14dbpSteps to Reproduce Updatedbug_revision_view_page.php?rev_id=13911#r13911
2016-06-16 12:38kgvProduct VersionUnscheduled =>
2016-06-16 12:38kgvTarget VersionUnscheduled => 7.1.0
2016-06-16 12:38kgvSummaryVisualization - Port OCCT ray-tracing core to quad BVH trees (QBVH) => Visualization, RayTracing - port to quad BVH trees (QBVH)
2016-06-16 13:54kgvAssigned Tokgv => dbp
2016-06-16 13:54kgvStatusresolved => assigned
2016-06-16 20:27kgvSummaryVisualization, RayTracing - port to quad BVH trees (QBVH) => Visualization, Ray Tracing - port to quad BVH trees (QBVH)
2016-06-20 16:03gitNote Added: 0055234
2016-06-20 16:03dbpNote Added: 0055235
2016-06-20 16:03dbpAssigned Todbp => kgv
2016-06-20 16:03dbpStatusassigned => resolved
2016-06-20 19:29kgvNote Added: 0055265
2016-06-20 19:29kgvAssigned Tokgv => bugmaster
2016-06-20 19:29kgvStatusresolved => reviewed
2016-06-20 19:35mkvAssigned Tobugmaster => mkv
2016-06-20 19:43gitNote Added: 0055268
2016-06-20 19:44kgvNote Added: 0055269
2016-06-21 12:08mkvNote Added: 0055287
2016-06-21 12:09mkvNote Added: 0055288
2016-06-21 12:09mkvAssigned Tomkv => kgv
2016-06-21 12:09mkvStatusreviewed => assigned
2016-06-21 12:09mkvTest case number => Not needed
2016-06-21 12:25kgvAssigned Tokgv => dbp
2016-06-22 11:11gitNote Added: 0055330
2016-06-22 11:13dbpNote Added: 0055331
2016-06-22 11:13dbpAssigned Todbp => kgv
2016-06-22 11:13dbpStatusassigned => resolved
2016-06-22 11:29gitNote Added: 0055333
2016-06-22 12:30kgvNote Added: 0055335
2016-06-22 12:30kgvAssigned Tokgv => bugmaster
2016-06-22 12:30kgvStatusresolved => reviewed
2016-06-22 14:42mkvAssigned Tobugmaster => mkv
2016-06-23 12:31mkvNote Added: 0055365
2016-06-23 12:31mkvNote Added: 0055366
2016-06-23 12:31mkvAssigned Tomkv => bugmaster
2016-06-23 12:31mkvStatusreviewed => tested
2016-06-24 12:41bugmasterChangeset attached => occt master f2474958
2016-06-24 12:41bugmasterStatustested => verified
2016-06-24 12:41bugmasterResolutionopen => fixed
2016-06-24 12:57gitNote Added: 0055414
2016-06-24 12:57gitNote Added: 0055417
2016-06-24 12:57gitNote Added: 0055422
2016-06-24 12:58gitNote Added: 0055437
2016-10-27 23:10dbpDescription Updatedbug_revision_view_page.php?rev_id=15105#r15105
2016-10-27 23:10dbpAdditional Information Updatedbug_revision_view_page.php?rev_id=15107#r15107
2016-10-27 23:10dbpFile Added: QBVH_gtc_2016.pdf
2016-12-09 16:30aivStatusverified => closed
2016-12-09 16:38aivFixed in Version => 7.1.0
2017-01-18 14:05kgvRelationship addedrelated to 0028368

Notes
(0054916)
git   
2016-06-10 16:23   
Branch CR27590 has been created by dbp.

SHA-1: 83e3e03290f989c779d9c24626c5447f3b6fa07b


Detailed log of new commits:

Author: dbp
Date: Fri Jun 10 16:23:35 2016 +0300

    0027590: Visualization - Port OCCT ray-tracing core to quad BVH trees (QBVH)
    
    In frames of this issue binary BVH tree produced by building algorithms was collapsed into 4-ary BVH (QBVH). The BVH traversal code in GLSL was modified to process such trees correctly. This allows to implore thread coherence, decrease BVH memory consumption (~2 times), and use traversal stack of the half size. As a result, ray tracing scalability is improved, as well as rendering performance. For various setups, speedup is 12-18%.
(0054936)
dbp   
2016-06-14 10:14   
Dear kgv,

Please review the patch in branch CR27590.
(0055234)
git   
2016-06-20 16:03   
Branch CR27590_1 has been created by dbp.

SHA-1: 8ce20c1f1573dc5793b714b2a215d3c2795cb8e8


Detailed log of new commits:

Author: dbp
Date: Mon Jun 20 16:02:59 2016 +0300

    0027590: Visualization - Port OCCT ray-tracing core to quad BVH trees (QBVH)
    
    In frames of this issue binary BVH tree produced by building algorithms was collapsed into 4-ary BVH (QBVH). The BVH traversal code in GLSL was modified to process such trees correctly. This allows to implore thread coherence, decrease BVH memory consumption (~2 times), and use traversal stack of the half size. As a result, ray tracing scalability is improved, as well as rendering performance. For various setups, speedup is 12-18%.
(0055235)
dbp   
2016-06-20 16:03   
Dear kgv,

Please review the issue in branch CR27590_1.
(0055265)
kgv   
2016-06-20 19:29   
Please test the patch.
(0055268)
git   
2016-06-20 19:43   
Branch CR27590_2 has been created by kgv.

SHA-1: 883271cd058b3d610b5931c3293f129f5023083c


Detailed log of new commits:

Author: dbp
Date: Mon Jun 20 19:43:44 2016 +0300

    0027590: Visualization, Ray Tracing - port to quad BVH trees (QBVH)
    
    In frames of this issue binary BVH tree produced by building algorithms was collapsed into 4-ary BVH (QBVH).
    The BVH traversal code in GLSL was modified to process such trees correctly.
    This allows to implore thread coherence, decrease BVH memory consumption (~2 times), and use traversal stack of the half size.
    As a result, ray tracing scalability is improved, as well as rendering performance. For various setups, speedup is 12-18%.
(0055269)
kgv   
2016-06-20 19:44   
CR27590_2 is the same as CR27590_1 with corrected commit description.
(0055287)
mkv   
2016-06-21 12:08   
Dear BugMaster,
Branch CR27590_1 from occt git-repository (and master from products git-repository) was compiled on Linux, MacOS and Windows platforms and tested on Release mode.
SHA-1: 8ce20c1f1573dc5793b714b2a215d3c2795cb8e8

There are following compilation errors:
Linux:
http://jenkins-test-07.nnov.opencascade.com:8080/view/CR27590-1-master/job/CR27590-1-master-OCCT-Debian70-64-opt-compile/1/parsed_console/ [^]
/dn54/builds/CR27590-1-master/Debian70-64-opt/OCCT/src/BVH/BVH_QuadTree.hxx:28:16: error: class 'BVH_Tree<T, N, BVH_QuadTree>' does not have any field named 'BVH_TreeBase'
....
/dn54/builds/CR27590-1-master/Debian70-64-opt/OCCT/src/BVH/BVH_QuadTree.lxx:23:37: error: 'myNodeInfoBuffer' was not declared in this scope
....
/dn54/builds/CR27590-1-master/Debian70-64-opt/OCCT/src/BVH/BVH_BinaryTree.hxx:58:26: error: 'BVH_VecNt' does not name a type
....
/dn54/builds/CR27590-1-master/Debian70-64-opt/OCCT/src/BVH/BVH_BinaryTree.hxx:58:37: error: ISO C++ forbids declaration of 'theMinPoint' with no type [-fpermissive]
/dn54/builds/CR27590-1-master/Debian70-64-opt/OCCT/src/BVH/BVH_BinaryTree.hxx:59:26: error: 'BVH_VecNt' does not name a type
....
/dn54/builds/CR27590-1-master/Debian70-64-opt/OCCT/src/BVH/BVH_BinaryTree.hxx:59:37: error: ISO C++ forbids declaration of 'theMaxPoint' with no type [-fpermissive]
/dn54/builds/CR27590-1-master/Debian70-64-opt/OCCT/src/BVH/BVH_BinaryTree.hxx:64:27: error: 'BVH_VecNt' does not name a type
....

MacOS:
http://jenkins-test-07.nnov.opencascade.com:8080/view/CR27590-1-master/job/CR27590-1-master-OCCT-MacOS-opt-compile/1/parsed_console/ [^]
/Users/mnt/builds/CR27590-1-master/MacOS-opt/OCCT/src/BVH/BVH_QuadTree.hxx:28:16: error: member initializer 'BVH_TreeBase' does not name a non-static data member or base class
...
/Users/mnt/builds/CR27590-1-master/MacOS-opt/OCCT/src/BVH/BVH_QuadTree.lxx:23:37: error: use of undeclared identifier 'myNodeInfoBuffer'
...
/Users/mnt/builds/CR27590-1-master/MacOS-opt/OCCT/src/BVH/BVH_BinaryTree.hxx:58:26: error: no template named 'BVH_VecNt'; did you mean 'BVH_Set'?
....
/Users/mnt/builds/CR27590-1-master/MacOS-opt/OCCT/src/BVH/BVH_BinaryTree.hxx:58:26: error: use of class template 'BVH_Set' requires template arguments
...
/Users/mnt/builds/CR27590-1-master/MacOS-opt/OCCT/src/BVH/BVH_BinaryTree.hxx:59:26: error: no template named 'BVH_VecNt'; did you mean 'BVH_Set'?
...
(0055288)
mkv   
2016-06-21 12:09   
Dear kgv,
Branch CR27590_1 has been rejected due to:
- compilation errors
(0055330)
git   
2016-06-22 11:11   
Branch CR27590_3 has been created by dbp.

SHA-1: f54591dd5c3ded2beae30bcb05933f1caec4985e


Detailed log of new commits:

Author: dbp
Date: Mon Jun 20 19:43:44 2016 +0300

    0027590: Visualization, Ray Tracing - port to quad BVH trees (QBVH)
    
    In frames of this issue binary BVH tree produced by building algorithms was collapsed into 4-ary BVH (QBVH).
    The BVH traversal code in GLSL was modified to process such trees correctly.
    This allows to implore thread coherence, decrease BVH memory consumption (~2 times), and use traversal stack of the half size.
    As a result, ray tracing scalability is improved, as well as rendering performance. For various setups, speedup is 12-18%.
(0055331)
dbp   
2016-06-22 11:13   
Dear kgv,

GCC compilation issues were resolved. Please review in branch CR27590_3.
(0055333)
git   
2016-06-22 11:29   
Branch CR27590_3 has been updated forcibly by dbp.

SHA-1: 0ab249a73129563c830cf139652fa303fa67eb50
(0055335)
kgv   
2016-06-22 12:30   
Please test the patch.
(0055365)
mkv   
2016-06-23 12:31   
Dear BugMaster,
Branch CR27590_3 from occt git-repository (and master from products git-repository) was compiled on Linux, MacOS and Windows platforms and tested on Release mode.
SHA-1: 0ab249a73129563c830cf139652fa303fa67eb50

Number of compiler warnings:

occt component :
Linux: 0 (0 on master)
Windows: 0 (0 on master)
MacOS : 0 (0 on master)

products component :
Linux: 68 (68 on master)
Windows: 0 (0 on master)
MacOS : 1119

Regressions/Differences/Improvements:
No regressions/differences

Testing cases:
Not needed

Testing on Linux:
occt component :
Total MEMORY difference: 88422955 / 89151715 [-0.82%]
Total CPU difference: 19351.06999999997 / 19458.07999999997 [-0.55%]
products component :
Total MEMORY difference: 27441028 / 27412842 [+0.10%]
Total CPU difference: 5151.249999999985 / 5165.429999999985 [-0.27%]

Testing on Windows:
occt component :
Total MEMORY difference: 55921286 / 55909495 [+0.02%]
Total CPU difference: 18490.767329798724 / 18565.835010998944 [-0.40%]
products component :
Total MEMORY difference: 18651419 / 18614185 [+0.20%]
Total CPU difference: 5043.27832849995 / 4998.802443399952 [+0.89%]

There are no differences in images found by testdiff.
(0055366)
mkv   
2016-06-23 12:31   
Dear BugMaster,
Branch CR27590_3 is TESTED.
(0055414)
git   
2016-06-24 12:57   
Branch CR27590_3 has been deleted by inv.

SHA-1: 0ab249a73129563c830cf139652fa303fa67eb50
(0055417)
git   
2016-06-24 12:57   
Branch CR27590_2 has been deleted by inv.

SHA-1: 883271cd058b3d610b5931c3293f129f5023083c
(0055422)
git   
2016-06-24 12:57   
Branch CR27590_1 has been deleted by inv.

SHA-1: 8ce20c1f1573dc5793b714b2a215d3c2795cb8e8
(0055437)
git   
2016-06-24 12:58   
Branch CR27590 has been deleted by inv.

SHA-1: 83e3e03290f989c779d9c24626c5447f3b6fa07b