Toroidal Bounding

notes by Kate Goss for panda3d-ssbo

The spatial hashing algorithm allows the shaders to skip unnecessary calculations for boids outside the effective distance. However, if the space is repeating/toroidal at the boundary, the calculations will be off as boids will not see 'through' the boundary to boids on the other side.

The naive approach to resolving this is to create 'mirror boids' outside the bounding box for the purposes of calculation. However, doing this with a mirror at each boundary introduces at least 2*d*n additional calculations. The mirror boids cannot be created before spatial hashing, as the spacial hashing algorithm is dependent on a grid sized to match the field, so it would have to be awkwardly enlarged to include as many gridsquares as the radius of interaction could intersect.

The next approach would be to only generate a boundary check if the boid is in radius of an edge; otherwise, no additional behaviour is required. Within r of at least one boundary edge, a boid should check across that boundary into the one on the other side. To avoid extending the grid, I propose shifting the grid 'inside out' via moving all coords 1/2 the length of a side, modulo by the length.

here is an example grid:

┌─┬─┬─┬─┬─┬─┐
│a│b│c│d│e│f│
├─┼─┼─┼─┼─┼─┤
│g│h│i│j│k│l│
├─┼─┼─┼─┼─┼─┤
│m│n│o│p│q│r│
└─┴─┴─┴─┴─┴─┘

for example; where the radius is smaller than 1 cell, for a boid in cell l, the grid transforms to:

┌─┬─┬─┬─┬─┬─┐
│d│e│f│a│b│c│
├─┼─┼─┼─┼─┼─┤
│j│k│l│d│e│f│
├─┼─┼─┼─┼─┼─┤
│p│q│r│g│h│i│
└─┴─┴─┴─┴─┴─┘