View Issue Details

Related ChangesetsJump to NotesJump to History
IDProjectCategoryView StatusDate SubmittedLast Update
0027590Open CASCADEOCCT:Visualizationpublic2016-06-10 13:062017-01-18 14:05
ReporterdbpAssigned Tobugmaster  
PrioritynormalSeverityfeature 
Status closedResolutionfixed 
Target Version7.1.0Fixed in Version7.1.0 
Summary0027590: Visualization, Ray Tracing - port to quad BVH trees (QBVH)
DescriptionCurrently, 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.
Steps To ReproduceN/A
Additional information
and documentation updates		Please find brief overview of new implementation in the file attached.
TagsNo tags attached.
Test case numberNot needed

Attached Files

  • QBVH_gtc_2016.pdf (2,274,141 bytes)

Relationships

related to 0028368 closedapn TKMath, BVH - Fix invalid tree height in QBVH 

Activities

git

2016-06-10 16:23

administrator   ~0054916

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%.

dbp

2016-06-14 10:14

developer   ~0054936

Dear kgv,

Please review the patch in branch CR27590.

git

2016-06-20 16:03

administrator   ~0055234

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%.

dbp

2016-06-20 16:03

developer   ~0055235

Dear kgv,

Please review the issue in branch CR27590_1.

kgv

2016-06-20 19:29

developer   ~0055265

Please test the patch.

git

2016-06-20 19:43

administrator   ~0055268

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%.

kgv

2016-06-20 19:44

developer   ~0055269

CR27590_2 is the same as CR27590_1 with corrected commit description.

mkv

2016-06-21 12:08

tester   ~0055287

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'?
...

mkv

2016-06-21 12:09

tester   ~0055288

Dear kgv,
Branch CR27590_1 has been rejected due to:
- compilation errors

git

2016-06-22 11:11

administrator   ~0055330

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%.

dbp

2016-06-22 11:13

developer   ~0055331

Dear kgv,

GCC compilation issues were resolved. Please review in branch CR27590_3.

git

2016-06-22 11:29

administrator   ~0055333

Branch CR27590_3 has been updated forcibly by dbp.

SHA-1: 0ab249a73129563c830cf139652fa303fa67eb50

kgv

2016-06-22 12:30

developer   ~0055335

Please test the patch.

mkv

2016-06-23 12:31

tester   ~0055365

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.

mkv

2016-06-23 12:31

tester   ~0055366

Dear BugMaster,
Branch CR27590_3 is TESTED.

git

2016-06-24 12:57

administrator   ~0055414

Branch CR27590_3 has been deleted by inv.

SHA-1: 0ab249a73129563c830cf139652fa303fa67eb50

git

2016-06-24 12:57

administrator   ~0055417

Branch CR27590_2 has been deleted by inv.

SHA-1: 883271cd058b3d610b5931c3293f129f5023083c

git

2016-06-24 12:57

administrator   ~0055422

Branch CR27590_1 has been deleted by inv.

SHA-1: 8ce20c1f1573dc5793b714b2a215d3c2795cb8e8

git

2016-06-24 12:58

administrator   ~0055437

Branch CR27590 has been deleted by inv.

SHA-1: 83e3e03290f989c779d9c24626c5447f3b6fa07b

dbp

2016-10-27 23:10

developer  

QBVH_gtc_2016.pdf (2,274,141 bytes)

Related Changesets

occt: master f2474958

2016-06-20 16:43:44

dbp


Committer: bugmaster Details Diff		 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%.		 Affected Issues
0027590
add - src/BVH/BVH_BinaryTree.hxx Diff File
add - src/BVH/BVH_BinaryTree.lxx Diff File
mod - src/BVH/BVH_Builder.hxx Diff File
mod - src/BVH/BVH_DistanceField.lxx Diff File
add - src/BVH/BVH_QuadTree.hxx Diff File
add - src/BVH/BVH_QuadTree.lxx Diff File
mod - src/BVH/BVH_QueueBuilder.lxx Diff File
mod - src/BVH/BVH_Tree.hxx Diff File
mod - src/BVH/BVH_Tree.lxx Diff File
mod - src/BVH/FILES Diff File
mod - src/OpenGl/OpenGl_Layer.cxx Diff File
mod - src/OpenGl/OpenGl_SceneGeometry.cxx Diff File
mod - src/OpenGl/OpenGl_SceneGeometry.hxx Diff File
mod - src/OpenGl/OpenGl_View.hxx Diff File
mod - src/OpenGl/OpenGl_View_Raytrace.cxx Diff File
mod - src/Select3D/Select3D_SensitiveSet.cxx Diff File
mod - src/SelectMgr/SelectMgr_ViewerSelector.cxx Diff File
mod - src/Shaders/RaytraceBase.fs Diff File
mod - src/Shaders/RaytraceRender.fs Diff File

Issue History

Date Modified Username Field Change
2016-06-10 13:06 dbp New Issue
2016-06-10 13:06 dbp Assigned To => dbp
2016-06-10 16:23 git Note Added: 0054916
2016-06-14 10:14 dbp Note Added: 0054936
2016-06-14 10:14 dbp Assigned To dbp => kgv
2016-06-14 10:14 dbp Status new => resolved
2016-06-14 10:14 dbp Steps to Reproduce Updated
2016-06-16 12:38 kgv Product Version Unscheduled =>
2016-06-16 12:38 kgv Target Version Unscheduled => 7.1.0
2016-06-16 12:38 kgv Summary Visualization - Port OCCT ray-tracing core to quad BVH trees (QBVH) => Visualization, RayTracing - port to quad BVH trees (QBVH)
2016-06-16 13:54 kgv Assigned To kgv => dbp
2016-06-16 13:54 kgv Status resolved => assigned
2016-06-16 20:27 kgv Summary Visualization, RayTracing - port to quad BVH trees (QBVH) => Visualization, Ray Tracing - port to quad BVH trees (QBVH)
2016-06-20 16:03 git Note Added: 0055234
2016-06-20 16:03 dbp Note Added: 0055235
2016-06-20 16:03 dbp Assigned To dbp => kgv
2016-06-20 16:03 dbp Status assigned => resolved
2016-06-20 19:29 kgv Note Added: 0055265
2016-06-20 19:29 kgv Assigned To kgv => bugmaster
2016-06-20 19:29 kgv Status resolved => reviewed
2016-06-20 19:35 mkv Assigned To bugmaster => mkv
2016-06-20 19:43 git Note Added: 0055268
2016-06-20 19:44 kgv Note Added: 0055269
2016-06-21 12:08 mkv Note Added: 0055287
2016-06-21 12:09 mkv Note Added: 0055288
2016-06-21 12:09 mkv Assigned To mkv => kgv
2016-06-21 12:09 mkv Status reviewed => assigned
2016-06-21 12:09 mkv Test case number => Not needed
2016-06-21 12:25 kgv Assigned To kgv => dbp
2016-06-22 11:11 git Note Added: 0055330
2016-06-22 11:13 dbp Note Added: 0055331
2016-06-22 11:13 dbp Assigned To dbp => kgv
2016-06-22 11:13 dbp Status assigned => resolved
2016-06-22 11:29 git Note Added: 0055333
2016-06-22 12:30 kgv Note Added: 0055335
2016-06-22 12:30 kgv Assigned To kgv => bugmaster
2016-06-22 12:30 kgv Status resolved => reviewed
2016-06-22 14:42 mkv Assigned To bugmaster => mkv
2016-06-23 12:31 mkv Note Added: 0055365
2016-06-23 12:31 mkv Note Added: 0055366
2016-06-23 12:31 mkv Assigned To mkv => bugmaster
2016-06-23 12:31 mkv Status reviewed => tested
2016-06-24 12:41 bugmaster Changeset attached => occt master f2474958
2016-06-24 12:41 bugmaster Status tested => verified
2016-06-24 12:41 bugmaster Resolution open => fixed
2016-06-24 12:57 git Note Added: 0055414
2016-06-24 12:57 git Note Added: 0055417
2016-06-24 12:57 git Note Added: 0055422
2016-06-24 12:58 git Note Added: 0055437
2016-10-27 23:10 dbp Description Updated
2016-10-27 23:10 dbp Additional Information Updated
2016-10-27 23:10 dbp File Added: QBVH_gtc_2016.pdf
2016-12-09 16:30 aiv Status verified => closed
2016-12-09 16:38 aiv Fixed in Version => 7.1.0
2017-01-18 14:05 kgv Relationship added related to 0028368