< 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)
 80230        : this(cellSize, DefaultHashCellBudget)
 31    {
 80232    }
 33
 82034    internal GridSpatialIndex(int cellSize, ulong cellBudget)
 35    {
 82036        _cellBudget = cellBudget;
 82037        _ordinaryGrids = new SwiftFixedSpatialHash<ushort>(InitialCapacity, (Fixed64)cellSize);
 82038        _oversizedGrids = new SwiftFixedBVH<ushort>(InitialCapacity);
 82039        _oversizedSlots = new SwiftHashSet<ushort>();
 82040        _contactEnvelopes = new SwiftFixedBVH<ushort>(InitialCapacity);
 82041        _contactEnvelopeSlots = new SwiftHashSet<ushort>();
 82042    }
 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    {
 93758        if (_ordinaryGrids.Contains(gridIndex) || _oversizedSlots.Contains(gridIndex))
 259            return false;
 60
 93561        if (FitsHashCellBudget(bounds))
 90362            _ordinaryGrids.Insert(gridIndex, bounds);
 63        else
 64        {
 3265            _oversizedGrids.Insert(gridIndex, bounds);
 3266            _oversizedSlots.Add(gridIndex);
 67        }
 68
 93569        if (contactEnvelope.HasValue)
 70        {
 92171            _contactEnvelopes.Insert(gridIndex, contactEnvelope.Value);
 92172            _contactEnvelopeSlots.Add(gridIndex);
 73        }
 74
 93575        return true;
 76    }
 77
 78    internal bool Remove(ushort gridIndex)
 79    {
 80        bool removed;
 6281        if (!_oversizedSlots.Contains(gridIndex))
 5682            removed = _ordinaryGrids.Remove(gridIndex);
 83        else
 84        {
 685            _oversizedGrids.Remove(gridIndex);
 686            _oversizedSlots.Remove(gridIndex);
 687            removed = true;
 88        }
 89
 6290        if (removed && _contactEnvelopeSlots.Remove(gridIndex))
 5991            _contactEnvelopes.Remove(gridIndex);
 92
 6293        return removed;
 94    }
 95
 96    internal void Clear()
 97    {
 79398        _ordinaryGrids.Clear();
 79399        _oversizedGrids.Clear();
 793100        _oversizedSlots.Clear();
 793101        _contactEnvelopes.Clear();
 793102        _contactEnvelopeSlots.Clear();
 793103    }
 104
 105    internal void CollectCandidates(
 106        FixedBoundVolume queryBounds,
 107        SwiftBucket<VoxelGrid> activeGrids,
 108        SwiftList<ushort> candidates)
 109    {
 1882110        candidates.Clear();
 1882111        if (activeGrids.Count == 0)
 1112            return;
 113
 1881114        if (ShouldScanActiveGrids(queryBounds, activeGrids.Count))
 115        {
 7668116            foreach (VoxelGrid grid in activeGrids)
 117            {
 2138118                var gridBounds = new FixedBoundVolume(grid.BoundsMin, grid.BoundsMax);
 2138119                if (gridBounds.Intersects(queryBounds))
 1911120                    candidates.Add(grid.GridIndex);
 121            }
 122        }
 123        else
 124        {
 185125            if (_ordinaryGrids.Count > 0)
 184126                _ordinaryGrids.Query(queryBounds, candidates);
 127
 185128            if (_oversizedGrids.Count > 0)
 17129                _oversizedGrids.Query(queryBounds, candidates);
 130        }
 131
 1881132        if (candidates.Count > 1)
 211133            candidates.SortInPlace();
 1881134    }
 135
 136    internal void CollectContactCandidates(
 137        FixedBoundVolume queryBounds,
 138        SwiftList<ushort> candidates)
 139    {
 907140        candidates.Clear();
 907141        if (_contactEnvelopes.Count > 0)
 904142            _contactEnvelopes.Query(queryBounds, candidates);
 143
 907144        if (candidates.Count > 1)
 184145            candidates.SortInPlace();
 907146    }
 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    {
 944165        if (_cellBudget == 0UL)
 1166            return false;
 167
 943168        GetCellRange(bounds, out SwiftSpatialHashCellIndex minCell, out SwiftSpatialHashCellIndex maxCell);
 943169        ulong xCount = GetCellCount(minCell.X, maxCell.X);
 943170        if (xCount > _cellBudget)
 34171            return false;
 172
 909173        ulong yCount = GetCellCount(minCell.Y, maxCell.Y);
 909174        if (yCount > _cellBudget / xCount)
 1175            return false;
 176
 908177        ulong xyCount = xCount * yCount;
 908178        ulong zCount = GetCellCount(minCell.Z, maxCell.Z);
 908179        return zCount <= _cellBudget / xyCount;
 180    }
 181
 182    internal void GetCellRange(
 183        FixedBoundVolume bounds,
 184        out SwiftSpatialHashCellIndex minCell,
 185        out SwiftSpatialHashCellIndex maxCell)
 186    {
 2836187        minCell = _ordinaryGrids.GetCellIndex(bounds.Min);
 2836188        maxCell = _ordinaryGrids.GetCellIndex(bounds.Max);
 2836189    }
 190
 191    internal bool ShouldScanActiveGrids(
 192        FixedBoundVolume queryBounds,
 193        int activeGridCount)
 194    {
 1886195        GetCellRange(queryBounds, out SwiftSpatialHashCellIndex minCell, out SwiftSpatialHashCellIndex maxCell);
 1886196        ulong count = (ulong)activeGridCount;
 1886197        ulong xCount = GetCellCount(minCell.X, maxCell.X);
 1886198        if (xCount > count)
 1250199            return true;
 200
 636201        ulong yCount = GetCellCount(minCell.Y, maxCell.Y);
 636202        if (yCount > count / xCount)
 335203            return true;
 204
 301205        ulong xyCount = xCount * yCount;
 301206        ulong zCount = GetCellCount(minCell.Z, maxCell.Z);
 301207        return zCount > count / xyCount;
 208    }
 209
 210    private static ulong GetCellCount(int minimum, int maximum) =>
 5583211        (ulong)((long)maximum - minimum + 1L);
 212}
Generated by: ReportGenerator 5.5.11.0
08/28/2026 - 03:09:44
GitHub | reportgenerator.io

Methods/Properties

.ctor(System.Int32)
.ctor(System.Int32,System.UInt64)
get_Count()
get_OrdinaryCount()
get_OversizedCount()
Insert(System.UInt16,SwiftCollections.Query.FixedBoundVolume)
Insert(System.UInt16,SwiftCollections.Query.FixedBoundVolume,System.Nullable`1<SwiftCollections.Query.FixedBoundVolume>)
Remove(System.UInt16)
Clear()
CollectCandidates(SwiftCollections.Query.FixedBoundVolume,SwiftCollections.SwiftBucket`1<GridForge.Grids.VoxelGrid>,SwiftCollections.SwiftList`1<System.UInt16>)
CollectContactCandidates(SwiftCollections.Query.FixedBoundVolume,SwiftCollections.SwiftList`1<System.UInt16>)
CollectPointCandidates(FixedMathSharp.Vector3d,SwiftCollections.SwiftList`1<System.UInt16>)
FitsHashCellBudget(SwiftCollections.Query.FixedBoundVolume)
GetCellRange(SwiftCollections.Query.FixedBoundVolume,SwiftCollections.Query.SwiftSpatialHashCellIndex&,SwiftCollections.Query.SwiftSpatialHashCellIndex&)
ShouldScanActiveGrids(SwiftCollections.Query.FixedBoundVolume,System.Int32)
GetCellCount(System.Int32,System.Int32)