pyMolDyn at EuroScipy 2016

Steps of cavity calculation:

1. Atom discretization (0:00 - 0:20):

   The given hexagonal volume and the included atoms are discretized. All points that are closer to an atom center than a user-defined cutoff radius are marked as atom cell.

2. Cavity domain segmentation (0:20 - 1:01):

   After the discretization, unmarked cells are left over. These cells form the cavity domains which are needed to calculate the actual cavities. In the current step, cavity domain cells that form a continuous volume are searched and grouped together by applying a split-and-merge algorithm.

   1. Split step (0:20 - 0:50):

      The discrete grid is traversed row-wise until a cell is found that does not match the previous visited cells. At this point, the discrete grid is split into four subvolumes. Two of these subvolumes have already been traversed and hence are homogeneous. The other two haven't been traversed yet and in turn are analysed with the same algorithm recursively. The recursion stops when all subvolumes are found to be homogeneous. As an optimization, all subvolumes that completely belong to an atom are filtered out, as they are not needed past this step.

   2. Merge step (0:51 - 1:01):

      All neighboring homogeneous subvolumes are repeatedly merged together by pairs and finally form cavity domains.

3. Cavity calculation (1:02 - 1:22):

   Each point in the given volume that is closer to a cavity domain than to an atom center is marked as cavity volume.

4. Isoline generation (1:23 - 1:43):

   A new grid is created with cells set to the amount of neighboring domain cells. On that new grid a marching squares algorithm is applied. For each grid cell which corners are above and below a given threshold (1 in that example), a line segment is generated which runs through that square. The end points of the line segment are calculated by linear interpolation along the edges. Segments are combined to pathes which form the cavity surfaces.