In MoloVol 1.0.0, voxels between atom type and probe core type are evaluated by searching for a neighbor probe core voxel within a probe radius.
Issue
The algorithm for the probe shell type voxels is one of the most if not the most time consuming in a calculation (in some cases the flood fill algorithm can take longer).
Improving its efficiency would significantly reduce the overall calculation time.
Proposed change
A closer look at the code of the program 3V http://3vee.molmovdb.org/ shows that they use a "reverse" algorithm:
In 3V, first the probe core voxels at the border of the probe core volume are listed.
Then a neighbor search algorithm is performed on these border probe core voxels to define all probe shell voxels within a probe radius range.
A similar algorithm could be applied with minimal changes to the current code of MoloVol since the neighbor search algorithm would be unaffected.
However, it will be necessary to add a pair of variable as attribute to each newly defined probe shell voxels to store the cavity ID and the distance to the cavity.
Indeed, with such an algorithm, a probe shell voxel could be assigned first to another cavity than it's nearest cavity and the cavity ID would need to be updated if necessary.
Alternatively, the neighbor search algorithm should be applied to each surface core voxels with gradual radius increase to always assign the nearest cavity first but always switching voxels in this manner might also have a computational cost.
Improvement
With the current MoloVol algorithm, all undefined voxels in a volume (proportional to (1/grid resolution)^3) undergo the neighbor search algorithm (proportional to (1/grid resolution)^3) that is stopped as soon as a core algorithm is found. => Number of voxel checks proportional to (1/grid resolution)^6
With an algorithm similar to 3V, a smaller number of voxels (i.e. only on a surface proportional to (1/grid resolution)^2) would undergo the neighbor search algorithm (1/grid resolution)^3) but the neighbor search algorithm would not stop until reaching the limit radius. => Number of voxel checks proportional to (1/grid resolution)^5
The theoretical improved efficiency should be checked on a small test program before going too far in a branch development.
Current status
In MoloVol 1.0.0, voxels between atom type and probe core type are evaluated by searching for a neighbor probe core voxel within a probe radius.
Issue
The algorithm for the probe shell type voxels is one of the most if not the most time consuming in a calculation (in some cases the flood fill algorithm can take longer). Improving its efficiency would significantly reduce the overall calculation time.
Proposed change
A closer look at the code of the program 3V http://3vee.molmovdb.org/ shows that they use a "reverse" algorithm: In 3V, first the probe core voxels at the border of the probe core volume are listed. Then a neighbor search algorithm is performed on these border probe core voxels to define all probe shell voxels within a probe radius range. A similar algorithm could be applied with minimal changes to the current code of MoloVol since the neighbor search algorithm would be unaffected. However, it will be necessary to add a pair of variable as attribute to each newly defined probe shell voxels to store the cavity ID and the distance to the cavity. Indeed, with such an algorithm, a probe shell voxel could be assigned first to another cavity than it's nearest cavity and the cavity ID would need to be updated if necessary. Alternatively, the neighbor search algorithm should be applied to each surface core voxels with gradual radius increase to always assign the nearest cavity first but always switching voxels in this manner might also have a computational cost.
Improvement
With the current MoloVol algorithm, all undefined voxels in a volume (proportional to (1/grid resolution)^3) undergo the neighbor search algorithm (proportional to (1/grid resolution)^3) that is stopped as soon as a core algorithm is found. => Number of voxel checks proportional to (1/grid resolution)^6 With an algorithm similar to 3V, a smaller number of voxels (i.e. only on a surface proportional to (1/grid resolution)^2) would undergo the neighbor search algorithm (1/grid resolution)^3) but the neighbor search algorithm would not stop until reaching the limit radius. => Number of voxel checks proportional to (1/grid resolution)^5
The theoretical improved efficiency should be checked on a small test program before going too far in a branch development.