How to do a hierarchical voxel traversal algorithm for ray tracing : Theory and practice

Sammanfattning

To create a hierarchical voxel traversal algorithm can be confusing and hard. There also seems to be problems with other solutions which also seemingly haven’t been discussed in the literature before. This work presents three different ways to design a hierarchical voxel traversal algorithm: H4T, HP4T and HP8T. H4T was inspired from a method called HERO and it was modified with an ID so that a property that gets the name 4-connectivity in the work is fulfilled. HP4T and HP8T uses but they are modified so that they use the position of the planes that are used in these methods for the new position. The results show that H4T algorithm that agrees with the reference data 100% of the time, the other two algorithms that don’t have 100% correctness never showed in the worst-case bigger margin of error than 2.5%. The conclusion is that there are different ways to design a hierarchical voxel traversal algorithm and if one is careful about designing the algorithm it is possible to avoid the problems with depth in the depth buffer and the surface normal problems in the normal buffer presented in the work. More work must be done to prove that an algorithm is showing correct behaviour for surface normals in the applications where those are needed, to test these algorithms on a graphics processor and a more detailed and intricate analysis needs to be done on the algorithms.