| | | 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 | | |
| | | 8 | | using FixedMathSharp; |
| | | 9 | | using SwiftCollections; |
| | | 10 | | using SwiftCollections.Query; |
| | | 11 | | |
| | | 12 | | namespace GridForge.Grids; |
| | | 13 | | |
| | | 14 | | /// <summary> |
| | | 15 | | /// Owns deterministic top-level grid spatial classification and lookup. |
| | | 16 | | /// </summary> |
| | | 17 | | internal 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 | | |
| | | 27 | | internal GridSpatialIndex(int cellSize) |
| | 550 | 28 | | : this(cellSize, DefaultHashCellBudget) |
| | | 29 | | { |
| | 550 | 30 | | } |
| | | 31 | | |
| | 568 | 32 | | internal GridSpatialIndex(int cellSize, ulong cellBudget) |
| | | 33 | | { |
| | 568 | 34 | | _cellBudget = cellBudget; |
| | 568 | 35 | | _ordinaryGrids = new SwiftFixedSpatialHash<ushort>(InitialCapacity, (Fixed64)cellSize); |
| | 568 | 36 | | _oversizedGrids = new SwiftFixedBVH<ushort>(InitialCapacity); |
| | 568 | 37 | | _oversizedSlots = new SwiftHashSet<ushort>(); |
| | 568 | 38 | | } |
| | | 39 | | |
| | 5 | 40 | | internal int Count => OrdinaryCount + OversizedCount; |
| | | 41 | | |
| | 10 | 42 | | internal int OrdinaryCount => _ordinaryGrids.Count; |
| | | 43 | | |
| | 10 | 44 | | internal int OversizedCount => _oversizedGrids.Count; |
| | | 45 | | |
| | | 46 | | internal bool Insert(ushort gridIndex, FixedBoundVolume bounds) |
| | | 47 | | { |
| | 572 | 48 | | if (_ordinaryGrids.Contains(gridIndex) || _oversizedSlots.Contains(gridIndex)) |
| | 2 | 49 | | return false; |
| | | 50 | | |
| | 570 | 51 | | if (FitsHashCellBudget(bounds)) |
| | 545 | 52 | | return _ordinaryGrids.Insert(gridIndex, bounds); |
| | | 53 | | |
| | 25 | 54 | | _oversizedGrids.Insert(gridIndex, bounds); |
| | 25 | 55 | | _oversizedSlots.Add(gridIndex); |
| | 25 | 56 | | return true; |
| | | 57 | | } |
| | | 58 | | |
| | | 59 | | internal bool Remove(ushort gridIndex) |
| | | 60 | | { |
| | 45 | 61 | | if (!_oversizedSlots.Contains(gridIndex)) |
| | 39 | 62 | | return _ordinaryGrids.Remove(gridIndex); |
| | | 63 | | |
| | 6 | 64 | | _oversizedGrids.Remove(gridIndex); |
| | 6 | 65 | | _oversizedSlots.Remove(gridIndex); |
| | 6 | 66 | | return true; |
| | | 67 | | } |
| | | 68 | | |
| | | 69 | | internal void Clear() |
| | | 70 | | { |
| | 543 | 71 | | _ordinaryGrids.Clear(); |
| | 543 | 72 | | _oversizedGrids.Clear(); |
| | 543 | 73 | | _oversizedSlots.Clear(); |
| | 543 | 74 | | } |
| | | 75 | | |
| | | 76 | | internal void CollectCandidates( |
| | | 77 | | FixedBoundVolume queryBounds, |
| | | 78 | | SwiftBucket<VoxelGrid> activeGrids, |
| | | 79 | | SwiftList<ushort> candidates) |
| | | 80 | | { |
| | 1432 | 81 | | candidates.Clear(); |
| | 1432 | 82 | | if (activeGrids.Count == 0) |
| | 7 | 83 | | return; |
| | | 84 | | |
| | 1425 | 85 | | if (ShouldScanActiveGrids(queryBounds, activeGrids.Count)) |
| | | 86 | | { |
| | 5892 | 87 | | foreach (VoxelGrid grid in activeGrids) |
| | | 88 | | { |
| | 1610 | 89 | | var gridBounds = new FixedBoundVolume(grid.BoundsMin, grid.BoundsMax); |
| | 1610 | 90 | | if (gridBounds.Intersects(queryBounds)) |
| | 1471 | 91 | | candidates.Add(grid.GridIndex); |
| | | 92 | | } |
| | | 93 | | } |
| | | 94 | | else |
| | | 95 | | { |
| | 89 | 96 | | if (_ordinaryGrids.Count > 0) |
| | 88 | 97 | | _ordinaryGrids.Query(queryBounds, candidates); |
| | | 98 | | |
| | 89 | 99 | | if (_oversizedGrids.Count > 0) |
| | 17 | 100 | | _oversizedGrids.Query(queryBounds, candidates); |
| | | 101 | | } |
| | | 102 | | |
| | 1425 | 103 | | if (candidates.Count > 1) |
| | 129 | 104 | | candidates.SortInPlace(); |
| | 1425 | 105 | | } |
| | | 106 | | |
| | | 107 | | internal void CollectPointCandidates( |
| | | 108 | | Vector3d point, |
| | | 109 | | SwiftList<ushort> candidates) |
| | | 110 | | { |
| | 153 | 111 | | candidates.Clear(); |
| | 153 | 112 | | if (_ordinaryGrids.Count > 0) |
| | 151 | 113 | | _ordinaryGrids.CollectPointCandidates(point, candidates); |
| | | 114 | | |
| | 153 | 115 | | if (_oversizedGrids.Count > 0) |
| | 4 | 116 | | _oversizedGrids.Query(new FixedBoundVolume(point, point), candidates); |
| | | 117 | | |
| | 153 | 118 | | if (candidates.Count > 1) |
| | 16 | 119 | | candidates.SortInPlace(); |
| | 153 | 120 | | } |
| | | 121 | | |
| | | 122 | | internal bool FitsHashCellBudget(FixedBoundVolume bounds) |
| | | 123 | | { |
| | 579 | 124 | | if (_cellBudget == 0UL) |
| | 1 | 125 | | return false; |
| | | 126 | | |
| | 578 | 127 | | GetCellRange(bounds, out SwiftSpatialHashCellIndex minCell, out SwiftSpatialHashCellIndex maxCell); |
| | 578 | 128 | | ulong xCount = GetCellCount(minCell.X, maxCell.X); |
| | 578 | 129 | | if (xCount > _cellBudget) |
| | 27 | 130 | | return false; |
| | | 131 | | |
| | 551 | 132 | | ulong yCount = GetCellCount(minCell.Y, maxCell.Y); |
| | 551 | 133 | | if (yCount > _cellBudget / xCount) |
| | 1 | 134 | | return false; |
| | | 135 | | |
| | 550 | 136 | | ulong xyCount = xCount * yCount; |
| | 550 | 137 | | ulong zCount = GetCellCount(minCell.Z, maxCell.Z); |
| | 550 | 138 | | return zCount <= _cellBudget / xyCount; |
| | | 139 | | } |
| | | 140 | | |
| | | 141 | | internal void GetCellRange( |
| | | 142 | | FixedBoundVolume bounds, |
| | | 143 | | out SwiftSpatialHashCellIndex minCell, |
| | | 144 | | out SwiftSpatialHashCellIndex maxCell) |
| | | 145 | | { |
| | 2015 | 146 | | minCell = _ordinaryGrids.GetCellIndex(bounds.Min); |
| | 2015 | 147 | | maxCell = _ordinaryGrids.GetCellIndex(bounds.Max); |
| | 2015 | 148 | | } |
| | | 149 | | |
| | | 150 | | internal bool ShouldScanActiveGrids( |
| | | 151 | | FixedBoundVolume queryBounds, |
| | | 152 | | int activeGridCount) |
| | | 153 | | { |
| | 1430 | 154 | | GetCellRange(queryBounds, out SwiftSpatialHashCellIndex minCell, out SwiftSpatialHashCellIndex maxCell); |
| | 1430 | 155 | | ulong count = (ulong)activeGridCount; |
| | 1430 | 156 | | ulong xCount = GetCellCount(minCell.X, maxCell.X); |
| | 1430 | 157 | | if (xCount > count) |
| | 1037 | 158 | | return true; |
| | | 159 | | |
| | 393 | 160 | | ulong yCount = GetCellCount(minCell.Y, maxCell.Y); |
| | 393 | 161 | | if (yCount > count / xCount) |
| | 231 | 162 | | return true; |
| | | 163 | | |
| | 162 | 164 | | ulong xyCount = xCount * yCount; |
| | 162 | 165 | | ulong zCount = GetCellCount(minCell.Z, maxCell.Z); |
| | 162 | 166 | | return zCount > count / xyCount; |
| | | 167 | | } |
| | | 168 | | |
| | | 169 | | private static ulong GetCellCount(int minimum, int maximum) => |
| | 3664 | 170 | | (ulong)((long)maximum - minimum + 1L); |
| | | 171 | | } |