nobnak/EffSpaceUnity

An implementation (for Unity) of efficient spacial data structures from Stackoverflow thread

An implementation (for Unity) of efficient spatial data structures from Stackoverflow thread

Unity project of this module.

Demo

Data Structures

• Uniform Grid :
  • PointGrid (int2)
  • FPointGrid (float2)
• QuadTree: TODO

Performance

On Razer Blade stealth 13 (2020)

• Core i7-1165G7
• Unity 2020.3

Point Grid

Usage

Initialize

var verticalCellCount = 1 << 5;
var particleCount = 1000;
var screenSize = new int2(1920, 1080);
FPointGridExt.RecommendGrid(screenSize, verticalCellCount, out var cellCount, out var cellSize);
var grid = new FPointGrid(cellCount, cellSize, float2.zero);

for (var i = 0; i < particleCount; i++) {
    var pos = rand.NextFloat2(float2.zero, screenSize);
    element_ids[i] = grid.Insert(i, pos);
    particle_seeds[i] = pos;
    particle_pos[i] = pos;
    ...
}

Update

var t = Time.time;
for (var i = 0; i < particleCount; i++) {
    var element_id = element_ids[i];
    var seed = particle_seeds[i];
    var pos = particle_pos[i];
    if (element_id >= 0) grid.Remove(element_id);

    pos += dt * screenSize * new float2(
        noise.snoise(new float3(seed, t)),
        noise.snoise(new float3(-seed, t)));
    pos -= screenSize * math.floor(pos / screenSize);

    element_ids[i] = grid.Insert(i, pos);
    particle_pos[i] = pos;
}

Query

int Neareset(int i) {
    var pos = particle_pos[i];
    var element_id = element_ids[i];
    var min_dist_sq = float.MaxValue;
    var min_id = -1;
    foreach (var e in grid.Query(pos - qrange, pos + qrange)) {
        if (e == element_id) continue;

        var eq = grid.grid.elements[e];
        var pos1 = particle_pos[eq.id];
        var dist_sq = math.distancesq(pos1, pos);
        if (dist_sq < min_dist_sq) {
            min_dist_sq = dist_sq;
            min_id = e;
        }
    }
    return min_id;
}

References

1. user4842163, Efficient (and well explained) implementation of a Quadtree for 2D collision detection, Stackoveflow, 2018
2. Mark Farragher, What Is Faster In C#: An int[] or an int[,]?, 2019