Octree
An octree is a tree data structure in which each internal node has exactly eight children (see the wikipedia article for more general information).
In MoloVol, an octree data structure is used to improve the efficiency of the analysis algorithms. The analyzed space is divided into a three dimensional grid of cubic voxels. Eight voxels are then assigned to a parent voxel, so that the parent voxel has twice the side length of its children. Depending on the "optimisation depth", a parameter set by the user, the parent voxels may become children of a larger voxel as well, and so on.
In order to increase the accuracy of a calculation, it is necessary to increase the spatial resolution of the voxel grid, which is done through a parameter in the UI. An increased resolution leads to an increase in Voxels that need to be evaluated which will influence the calculation speed. In the absence of an octree in 3D a doubled resolution leads to an eight-fold increase in voxels, as every voxel is now represented by eight smaller voxels. However, only voxels close to an interface, for instance the outside of a spherical atom, will contribute towards a more accurate description. The splitting of a voxel that was far outside the radius of the atom will not change the volume or surface results.
The octree data structure can massively improve calculation efficiency, by making sure that only those voxels are split that are close to an interface. This is achieved, by always assessing the voxel on the highest possible octree level. If the voxel can be analyzed completely on a higher level, then its children never need to be assessed.
At first a number of top level voxels are created, so that the entire analysis space is covered. The size of the voxels is determined by input parameters. As the voxels are being analyzed they may be either be assigned a type, or be split into eight subvoxels. Each of the subvoxels is then analyzed analogously to the parent voxel.
Since the voxel class does not contain pointers to their children in order to keep memory cost down, a separate grid of voxels for each octree level is stored in memory. The children are accessed through the Space class. A consequence of this is that regardless of whether or not lower level voxels are needed, they are always created.
Dividing the space in such an octree of voxels considerably reduces the number of voxels to be analyzed, even when using a very small grid step for high resolution analysis.
Through the GUI, the user can choose the octree level manually which will lead to a largest voxel size equal to grid_step_size * 2^octree_level. The bottom level voxel grid is independant of the octree depth.
To illustrate the optimisation, the figure below shows the equivalent in 2D with a quadtree of pixels instead of an octree of voxels. There are 6 atoms with a radius of 1.5 Å, the grid step size is 0.1 Å and the quadtree level is 5.
In this simple case, the algorithm would check the largest pixel level to determine whether the pixel is completely inside any atom, completely outside of all atoms, or partly inside and outside. In the last case, the pixel would be divided in four pixels of half length and continue until pixels of length 0.1 Å are analyzed.
If the quadtree level was set to 0 (i.e. no quadtree), there would be 12288 pixels to analyze (96*128).
With the level 5 quadtree presented, there are a total of 1712 pixels analyzed which is 7 times more efficient than for level 0.
Detailed pixel numbers:
- 12 at level 5
- 44 at level 4
- 116 at level 3
- 228 at level 2
- 432 at level 1
- 880 at level 0
The increase in efficiency is expected to be higher in 3D with an octree than in 2D with a quadtree since each additional octree level would lead to up to 8 times fewer voxels to analyze (as opposed to the 4 times fewer pixels with a quadtree).
Interestingly, in the example above, a level 4 quadtree would have led to 4 more pixels at level 4 but no pixel at level 5 which means a total of 1704 pixels to analyze. Technically, the level 4 quadtree would have been more efficient than the level 5 illustrated above.
The difference between level 4 and 5 is negligible but this shows that for a given structure and set of parameters, there is an optimal quadtree level (same for octree level in 3D). This means that it is contraproductive to use an extremely large octree level in MoloVol.
Considering the typical size of atoms and potential voids present in molecules, the optimal octree level with a given grid step size would lead to a largest voxel side length of 2-6 Å (e.g. with a grid step size of 0.1 Å, the optimal octree level would likely be 5 or 6 depending on the structure). Accordingly, the default octree level takes this into account and the default parameters should provide results with a good resolution in a decent calculation time.