MantisBT
Mantis Bug Tracker Workflow

View Issue Details Jump to Notes ] Related Changesets ] Issue History ] Print ]
IDProjectCategoryView StatusDate SubmittedLast Update
0027590Open CASCADE[OCCT] OCCT:Visualizationpublic2016-06-10 13:062017-01-18 14:05
Reporterdbp 
Assigned Tobugmaster 
PrioritynormalSeverityfeature 
StatusclosedResolutionfixed 
PlatformOSOS Version
Product Version 
Target Version[OCCT] 7.1.0Fixed in Version[OCCT] 7.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 Filespdf file icon QBVH_gtc_2016.pdf (2,274,141 bytes) 2016-10-27 23:10

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

-  Notes
(0054916)
git (administrator)
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 (developer)
2016-06-14 10:14

Dear kgv,

Please review the patch in branch CR27590.
(0055234)
git (administrator)
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 (developer)
2016-06-20 16:03

Dear kgv,

Please review the issue in branch CR27590_1.
(0055265)
kgv (developer)
2016-06-20 19:29

Please test the patch.
(0055268)
git (administrator)
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 (developer)
2016-06-20 19:44

CR27590_2 is the same as CR27590_1 with corrected commit description.
(0055287)
mkv (tester)
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 (tester)
2016-06-21 12:09

Dear kgv,
Branch CR27590_1 has been rejected due to:
- compilation errors
(0055330)
git (administrator)
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 (developer)
2016-06-22 11:13

Dear kgv,

GCC compilation issues were resolved. Please review in branch CR27590_3.
(0055333)
git (administrator)
2016-06-22 11:29

Branch CR27590_3 has been updated forcibly by dbp.

SHA-1: 0ab249a73129563c830cf139652fa303fa67eb50
(0055335)
kgv (developer)
2016-06-22 12:30

Please test the patch.
(0055365)
mkv (tester)
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 (tester)
2016-06-23 12:31

Dear BugMaster,
Branch CR27590_3 is TESTED.
(0055414)
git (administrator)
2016-06-24 12:57

Branch CR27590_3 has been deleted by inv.

SHA-1: 0ab249a73129563c830cf139652fa303fa67eb50
(0055417)
git (administrator)
2016-06-24 12:57

Branch CR27590_2 has been deleted by inv.

SHA-1: 883271cd058b3d610b5931c3293f129f5023083c
(0055422)
git (administrator)
2016-06-24 12:57

Branch CR27590_1 has been deleted by inv.

SHA-1: 8ce20c1f1573dc5793b714b2a215d3c2795cb8e8
(0055437)
git (administrator)
2016-06-24 12:58

Branch CR27590 has been deleted by inv.

SHA-1: 83e3e03290f989c779d9c24626c5447f3b6fa07b

- Related Changesets
occt: master f2474958
Timestamp: 2016-06-20 16:43:44
Author: 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%.
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 View Revisions
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 View Revisions
2016-10-27 23:10 dbp Additional Information Updated View Revisions
2016-10-27 23:10 dbp File Added: QBVH_gtc_2016.pdf
2016-12-09 16:30 user533 Status verified => closed
2016-12-09 16:38 user533 Fixed in Version => 7.1.0
2017-01-18 14:05 kgv Relationship added related to 0028368


Copyright © 2000 - 2018 MantisBT Team
Powered by Mantis Bugtracker