< Summary

Information
Class: GridForge.Grids.GridSpatialIndex
Assembly: GridForge
File(s): /home/runner/work/GridForge/GridForge/src/GridForge/Grids/Managers/GridSpatialIndex.cs
Line coverage
100%
Covered lines: 94
Uncovered lines: 0
Coverable lines: 94
Total lines: 212
Line coverage: 100%
Branch coverage
100%
Covered branches: 48
Total branches: 48
Branch coverage: 100%
Method coverage

Feature is only available for sponsors

Upgrade to PRO version

Metrics

MethodBranch coverage Crap Score Cyclomatic complexity Line coverage
.ctor(...)100%11100%
.ctor(...)100%11100%
get_Count()100%11100%
get_OrdinaryCount()100%11100%
get_OversizedCount()100%11100%
Insert(...)100%11100%
Insert(...)100%88100%
Remove(...)100%66100%
Clear()100%11100%
CollectCandidates(...)100%1414100%
CollectContactCandidates(...)100%44100%
CollectPointCandidates(...)100%66100%
FitsHashCellBudget(...)100%66100%
GetCellRange(...)100%11100%
ShouldScanActiveGrids(...)100%44100%
GetCellCount(...)100%11100%

File(s)

/home/runner/work/GridForge/GridForge/src/GridForge/Grids/Managers/GridSpatialIndex.cs

#LineLine coverage
 1//=======================================================================
 2// GridSpatialIndex.cs
 3//=======================================================================
 4// MIT License, Copyright (c) 2024-present David Oravsky (mrdav30)
 5// See LICENSE file in the project root for full license information.
 6//=======================================================================
 7
 8using FixedMathSharp;
 9using SwiftCollections;
 10using SwiftCollections.Query;
 11
 12namespace GridForge.Grids;
 13
 14/// <summary>
 15/// Owns deterministic top-level grid spatial classification and lookup.
 16/// </summary>
 17internal sealed class GridSpatialIndex
 18{
 19    private const int InitialCapacity = 16;
 20    internal const ulong DefaultHashCellBudget = 64UL;
 21
 22    private readonly ulong _cellBudget;
 23    private readonly SwiftFixedSpatialHash<ushort> _ordinaryGrids;
 24    private readonly SwiftFixedBVH<ushort> _oversizedGrids;
 25    private readonly SwiftHashSet<ushort> _oversizedSlots;
 26    private readonly SwiftFixedBVH<ushort> _contactEnvelopes;
 27    private readonly SwiftHashSet<ushort> _contactEnvelopeSlots;
 28
 29    internal GridSpatialIndex(int cellSize)
 108730        : this(cellSize, DefaultHashCellBudget)
 31    {
 108732    }
 33
 110534    internal GridSpatialIndex(int cellSize, ulong cellBudget)
 35    {
 110536        _cellBudget = cellBudget;
 110537        _ordinaryGrids = new SwiftFixedSpatialHash<ushort>(InitialCapacity, (Fixed64)cellSize);
 110538        _oversizedGrids = new SwiftFixedBVH<ushort>(InitialCapacity);
 110539        _oversizedSlots = new SwiftHashSet<ushort>();
 110540        _contactEnvelopes = new SwiftFixedBVH<ushort>(InitialCapacity);
 110541        _contactEnvelopeSlots = new SwiftHashSet<ushort>();
 110542    }
 43
 544    internal int Count => OrdinaryCount + OversizedCount;
 45
 1046    internal int OrdinaryCount => _ordinaryGrids.Count;
 47
 1048    internal int OversizedCount => _oversizedGrids.Count;
 49
 50    internal bool Insert(ushort gridIndex, FixedBoundVolume bounds) =>
 1851        Insert(gridIndex, bounds, bounds);
 52
 53    internal bool Insert(
 54        ushort gridIndex,
 55        FixedBoundVolume bounds,
 56        FixedBoundVolume? contactEnvelope)
 57    {
 124458        if (_ordinaryGrids.Contains(gridIndex) || _oversizedSlots.Contains(gridIndex))
 259            return false;
 60
 124261        if (FitsHashCellBudget(bounds))
 121062            _ordinaryGrids.Insert(gridIndex, bounds);
 63        else
 64        {
 3265            _oversizedGrids.Insert(gridIndex, bounds);
 3266            _oversizedSlots.Add(gridIndex);
 67        }
 68
 124269        if (contactEnvelope.HasValue)
 70        {
 122271            _contactEnvelopes.Insert(gridIndex, contactEnvelope.Value);
 122272            _contactEnvelopeSlots.Add(gridIndex);
 73        }
 74
 124275        return true;
 76    }
 77
 78    internal bool Remove(ushort gridIndex)
 79    {
 80        bool removed;
 6881        if (!_oversizedSlots.Contains(gridIndex))
 6282            removed = _ordinaryGrids.Remove(gridIndex);
 83        else
 84        {
 685            _oversizedGrids.Remove(gridIndex);
 686            _oversizedSlots.Remove(gridIndex);
 687            removed = true;
 88        }
 89
 6890        if (removed && _contactEnvelopeSlots.Remove(gridIndex))
 6591            _contactEnvelopes.Remove(gridIndex);
 92
 6893        return removed;
 94    }
 95
 96    internal void Clear()
 97    {
 107898        _ordinaryGrids.Clear();
 107899        _oversizedGrids.Clear();
 1078100        _oversizedSlots.Clear();
 1078101        _contactEnvelopes.Clear();
 1078102        _contactEnvelopeSlots.Clear();
 1078103    }
 104
 105    internal void CollectCandidates(
 106        FixedBoundVolume queryBounds,
 107        SwiftSlotMap<VoxelGrid> activeGrids,
 108        SwiftList<ushort> candidates)
 109    {
 2457110        candidates.Clear();
 2457111        if (activeGrids.Count == 0)
 1112            return;
 113
 2456114        if (ShouldScanActiveGrids(queryBounds, activeGrids.Count))
 115        {
 10130116            foreach (VoxelGrid grid in activeGrids)
 117            {
 2813118                var gridBounds = new FixedBoundVolume(grid.BoundsMin, grid.BoundsMax);
 2813119                if (gridBounds.Intersects(queryBounds))
 2506120                    candidates.Add(grid.GridIndex);
 121            }
 122        }
 123        else
 124        {
 204125            if (_ordinaryGrids.Count > 0)
 203126                _ordinaryGrids.Query(queryBounds, candidates);
 127
 204128            if (_oversizedGrids.Count > 0)
 17129                _oversizedGrids.Query(queryBounds, candidates);
 130        }
 131
 2456132        if (candidates.Count > 1)
 280133            candidates.SortInPlace();
 2456134    }
 135
 136    internal void CollectContactCandidates(
 137        FixedBoundVolume queryBounds,
 138        SwiftList<ushort> candidates)
 139    {
 1208140        candidates.Clear();
 1208141        if (_contactEnvelopes.Count > 0)
 1205142            _contactEnvelopes.Query(queryBounds, candidates);
 143
 1208144        if (candidates.Count > 1)
 202145            candidates.SortInPlace();
 1208146    }
 147
 148    internal void CollectPointCandidates(
 149        Vector3d point,
 150        SwiftList<ushort> candidates)
 151    {
 154152        candidates.Clear();
 154153        if (_ordinaryGrids.Count > 0)
 151154            _ordinaryGrids.CollectPointCandidates(point, candidates);
 155
 154156        if (_oversizedGrids.Count > 0)
 4157            _oversizedGrids.Query(new FixedBoundVolume(point, point), candidates);
 158
 154159        if (candidates.Count > 1)
 16160            candidates.SortInPlace();
 154161    }
 162
 163    internal bool FitsHashCellBudget(FixedBoundVolume bounds)
 164    {
 1251165        if (_cellBudget == 0UL)
 1166            return false;
 167
 1250168        GetCellRange(bounds, out SwiftSpatialHashCellIndex minCell, out SwiftSpatialHashCellIndex maxCell);
 1250169        ulong xCount = GetCellCount(minCell.X, maxCell.X);
 1250170        if (xCount > _cellBudget)
 34171            return false;
 172
 1216173        ulong yCount = GetCellCount(minCell.Y, maxCell.Y);
 1216174        if (yCount > _cellBudget / xCount)
 1175            return false;
 176
 1215177        ulong xyCount = xCount * yCount;
 1215178        ulong zCount = GetCellCount(minCell.Z, maxCell.Z);
 1215179        return zCount <= _cellBudget / xyCount;
 180    }
 181
 182    internal void GetCellRange(
 183        FixedBoundVolume bounds,
 184        out SwiftSpatialHashCellIndex minCell,
 185        out SwiftSpatialHashCellIndex maxCell)
 186    {
 3719187        minCell = _ordinaryGrids.GetCellIndex(bounds.Min);
 3719188        maxCell = _ordinaryGrids.GetCellIndex(bounds.Max);
 3719189    }
 190
 191    internal bool ShouldScanActiveGrids(
 192        FixedBoundVolume queryBounds,
 193        int activeGridCount)
 194    {
 2462195        GetCellRange(queryBounds, out SwiftSpatialHashCellIndex minCell, out SwiftSpatialHashCellIndex maxCell);
 2462196        ulong count = (ulong)activeGridCount;
 2462197        ulong xCount = GetCellCount(minCell.X, maxCell.X);
 2462198        if (xCount > count)
 1663199            return true;
 200
 799201        ulong yCount = GetCellCount(minCell.Y, maxCell.Y);
 799202        if (yCount > count / xCount)
 457203            return true;
 204
 342205        ulong xyCount = xCount * yCount;
 342206        ulong zCount = GetCellCount(minCell.Z, maxCell.Z);
 342207        return zCount > count / xyCount;
 208    }
 209
 210    private static ulong GetCellCount(int minimum, int maximum) =>
 7284211        (ulong)((long)maximum - minimum + 1L);
 212}