< Summary

Information
Class: GridForge.Utility.GridTracer
Assembly: GridForge
File(s): File 1: /home/runner/work/GridForge/GridForge/src/GridForge/Utility/GridTracer.cs
File 2: /home/runner/work/GridForge/GridForge/src/GridForge/Utility/GridTracer.GridCoverage.cs
File 3: /home/runner/work/GridForge/GridForge/src/GridForge/Utility/GridTracer.NavigationBody.cs
File 4: /home/runner/work/GridForge/GridForge/src/GridForge/Utility/GridTracer.TraceIntervals.cs
File 5: /home/runner/work/GridForge/GridForge/src/GridForge/Utility/GridTracer.TraceLine.cs
Line coverage
100%
Covered lines: 1471
Uncovered lines: 0
Coverable lines: 1471
Total lines: 3071
Line coverage: 100%
Branch coverage
100%
Covered branches: 530
Total branches: 530
Branch coverage: 100%
Method coverage

Feature is only available for sponsors

Upgrade to PRO version

Metrics

MethodBranch coverage Crap Score Cyclomatic complexity Line coverage
File 1: .ctor(...)100%11100%
File 1: TraceLine(...)100%44100%
File 1: TraceLineInto(...)100%44100%
File 1: TraceLineInto(...)100%44100%
File 1: TraceLine(...)100%11100%
File 1: TraceLineInto(...)100%11100%
File 1: TraceLineInto(...)100%11100%
File 1: GetCoveredVoxels(...)100%44100%
File 1: GetCoveredVoxels(...)100%11100%
File 1: GetCoveredVoxels(...)100%11100%
File 1: GetCoveredVoxelsInto(...)100%44100%
File 1: GetCoveredVoxelsInto(...)100%11100%
File 1: GetCoveredVoxelsInto(...)100%11100%
File 1: GetCoveredVoxelsInto(...)100%44100%
File 1: GetCoveredVoxelsInto(...)100%11100%
File 1: GetCoveredVoxelsInto(...)100%11100%
File 1: GetCoveredScanCells(...)100%44100%
File 1: GetCoveredScanCells(...)100%11100%
File 1: GetCoveredScanCells(...)100%11100%
File 1: GetCoveredScanCellsInto(...)100%44100%
File 1: GetCoveredScanCellsInto(...)100%11100%
File 1: GetCoveredScanCellsInto(...)100%11100%
File 1: GetCoveredScanCellsInto(...)100%44100%
File 1: GetCoveredScanCellsInto(...)100%11100%
File 1: GetCoveredScanCellsInto(...)100%11100%
File 1: AddCoveredScanCellsTo(...)100%11100%
File 1: AddCoveredScanCellsTo(...)100%11100%
File 1: AddCoveredVoxelsTo(...)100%11100%
File 1: AddCoveredVoxelsTo(...)100%11100%
File 1: AddCoveredVoxelsCore(...)100%22100%
File 1: AddCoveredScanCellsCore(...)100%22100%
File 1: GetCoveredVoxelsIterator()100%22100%
File 1: <>m__Finally1()100%11100%
File 1: AddCoveredVoxelsToMapping(...)100%22100%
File 1: GetCoveredScanCellsIterator()100%22100%
File 1: <>m__Finally1()100%11100%
File 2: AddCoveredScanCellsForGrid(...)100%44100%
File 2: AddCoveredVoxelsForGrid(...)100%22100%
File 2: AddCoveredGridVoxels(...)100%44100%
File 2: AddCoveredHexGridVoxels(...)100%1212100%
File 2: AddCoveredHexScanCellsForGrid(...)100%22100%
File 2: IsHexVoxelCenterInHorizontalCoverage(...)100%66100%
File 3: TraceNavigationBodyInto(...)100%7272100%
File 3: HasClosedNavigationBodyPrismContact(...)100%66100%
File 3: GetNavigationClosure(...)100%3434100%
File 3: IsNavigationClosurePrism(...)100%44100%
File 3: SnapshotNavigationBodyCandidates(...)100%44100%
File 3: TryCreateNavigationBodyBounds(...)100%88100%
File 3: AssignNavigationBodyBounds(...)100%11100%
File 3: TryExpandNavigationBodyBounds(...)100%1212100%
File 3: HasNavigationBodyUnionCoverage(...)100%1818100%
File 3: FindNavigationBodyCandidate(...)100%44100%
File 3: FindBestMatchingNavigationBodyPrism(...)100%1010100%
File 3: IsPreferredNavigationBodyCandidate(...)100%22100%
File 3: AreSameNavigationBodyPrism(...)100%11100%
File 3: CompareNavigationBodyPrisms(...)100%1818100%
File 3: FindNavigationBodyPrismRange(...)100%1212100%
File 3: AddNavigationBodyUnionMember(...)100%11100%
File 3: AppendMissingNavigationBodyAlternativeEvidence(...)100%88100%
File 3: CountMissingNavigationBodyAlternativeEvidence(...)100%66100%
File 3: GetNavigationBodyPrismGroupEnd(...)100%44100%
File 3: IsMissingNavigationBodyAlternativeGroup(...)100%66100%
File 3: IsNavigationBodyEndpoint(...)100%66100%
File 3: CreateNavigationBodyTraceReport(...)100%11100%
File 3: FailNavigationBodyTrace(...)100%11100%
File 3: Compare(...)100%11100%
File 3: Compare(...)100%11100%
File 3: CompareNavigationBodyTraceCells(...)100%22100%
File 4: TraceIntervalsInto(...)100%3232100%
File 4: TryCollectSegmentCandidates(...)100%1010100%
File 4: SnapshotSparsePresence(...)100%44100%
File 4: TryGetPrismInterval(...)100%44100%
File 4: TryGetVerticalInterval(...)100%88100%
File 4: CreateTraceReport(...)100%11100%
File 4: FailTrace(...)100%11100%
File 4: AssignTieGroups(...)100%2222100%
File 4: HasContinuousCoverage(...)100%1818100%
File 4: SortGridIndices(...)100%11100%
File 4: SortIntervals(...)100%44100%
File 4: SiftIntervalsDown(...)100%88100%
File 4: CompareIntervals(...)100%66100%
File 4: CompareGridIdentity(...)100%11100%
File 4: .ctor(...)100%11100%
File 4: Compare(...)100%11100%
File 4: CompareConfigurationKeys(...)100%1414100%
File 4: CompareVectors(...)100%44100%
File 5: TraceLineIterator()100%22100%
File 5: <>m__Finally1()100%11100%
File 5: AddTraceLineVoxelsToMapping(...)100%22100%
File 5: AddTraceLineVoxelsTo(...)100%22100%
File 5: CreateTraceLinePlan(...)100%11100%
File 5: CalculateTraceSteps(...)100%11100%
File 5: CreateTraceEndpoint(...)100%11100%
File 5: SelectTraceCoordinate(...)100%22100%
File 5: CreatePaddedOrderedBounds(...)100%1010100%
File 5: ExpandOrderedBounds(...)100%22100%
File 5: TryGetCoveredScanCellRange(...)100%22100%
File 5: AddTraceLineVoxelsForGrid(...)100%44100%
File 5: AddTraceLineVoxelsForGrid(...)100%22100%
File 5: AddTraceLineGridVoxels(...)100%1010100%
File 5: AddHexTraceLineGridVoxels(...)100%66100%
File 5: CreateHexTraceEndpoints(...)100%11100%
File 5: CalculateHexTraceSteps(...)100%11100%
File 5: InterpolateHexTraceIndex(...)100%11100%
File 5: Interpolate(...)100%11100%
File 5: TryClipTraceSegmentToGrid(...)100%1010100%
File 5: ClipTraceSegmentAxis(...)100%1010100%
File 5: ShouldIncludeHexTraceEndIndex(...)100%44100%
File 5: InterpolateTraceSegment(...)100%11100%
File 5: InterpolateTraceAxis(...)100%66100%
File 5: AddTraceVoxelByPosition(...)100%44100%
File 5: AddTraceVoxelByIndex(...)100%44100%
File 5: ReleaseGridVoxelSets(...)100%22100%

File(s)

/home/runner/work/GridForge/GridForge/src/GridForge/Utility/GridTracer.cs

#LineLine coverage
 1//=======================================================================
 2// GridTracer.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 System.Collections.Generic;
 9using FixedMathSharp;
 10using FixedMathSharp.Geometry;
 11using GridForge.Grids;
 12using GridForge.Spatial;
 13using SwiftCollections;
 14using SwiftCollections.Pool;
 15
 16namespace GridForge.Utility;
 17
 18/// <summary>
 19/// Provides utilities for tracing lines or bounding areas in a grid, aligning them to grid voxels.
 20/// Uses fixed-point calculations to ensure deterministic and accurate grid traversal.
 21/// </summary>
 22public static partial class GridTracer
 23{
 24    private readonly struct TraceLinePlan
 25    {
 26        public readonly Vector3d TraceStart;
 27        public readonly Fixed64 Steps;
 28        public readonly Fixed64 StepX;
 29        public readonly Fixed64 StepY;
 30        public readonly Fixed64 StepZ;
 31
 32        public TraceLinePlan(
 33            Vector3d traceStart,
 34            Fixed64 steps,
 35            Fixed64 stepX,
 36            Fixed64 stepY,
 37            Fixed64 stepZ)
 38        {
 7039            TraceStart = traceStart;
 7040            Steps = steps;
 7041            StepX = stepX;
 7042            StepY = stepY;
 7043            StepZ = stepZ;
 7044        }
 45    }
 46
 47    /// <summary>
 48    /// Traces a 3D line between two points in the supplied world.
 49    /// The traced points are returned as grid voxels.
 50    /// </summary>
 51    /// <remarks>
 52    /// Uses a fractional step algorithm inspired by Bresenham’s line algorithm.
 53    /// This implementation leverages fixed-point math to maintain precision across a deterministic grid.
 54    /// </remarks>
 55    /// <param name="world">The world whose grids should be traced.</param>
 56    /// <param name="start">Starting position in world space.</param>
 57    /// <param name="end">Ending position in world space.</param>
 58    /// <param name="padding">Value applied to the start/end positions before snapping.</param>
 59    /// <param name="includeEnd">Whether to include the end voxel in the traced line.</param>
 60    /// <returns>A collection of <see cref="GridVoxelSet"/> objects representing the traced path.</returns>
 61    public static IEnumerable<GridVoxelSet> TraceLine(
 62        GridWorld world,
 63        Vector3d start,
 64        Vector3d end,
 65        Fixed64? padding = null,
 66        bool includeEnd = true)
 67    {
 4268        if (world == null || !world.IsActive)
 269            return System.Array.Empty<GridVoxelSet>();
 70
 4071        return TraceLineIterator(world, start, end, padding, includeEnd);
 72    }
 73
 74    /// <summary>
 75    /// Clears and fills caller-owned storage with voxels traced by a 3D line.
 76    /// </summary>
 77    /// <param name="world">The world whose grids should be traced.</param>
 78    /// <param name="start">Starting position in world space.</param>
 79    /// <param name="end">Ending position in world space.</param>
 80    /// <param name="results">Caller-owned storage that receives traced voxels.</param>
 81    /// <param name="padding">Value applied to the start/end positions before snapping.</param>
 82    /// <param name="includeEnd">Whether to include the end voxel in the traced line.</param>
 83    public static void TraceLineInto(
 84        GridWorld world,
 85        Vector3d start,
 86        Vector3d end,
 87        SwiftList<Voxel> results,
 88        Fixed64? padding = null,
 89        bool includeEnd = true)
 90    {
 591        SwiftThrowHelper.ThrowIfNull(results, nameof(results));
 92
 493        results.Clear();
 494        if (world == null || !world.IsActive)
 195            return;
 96
 397        SwiftHashSet<Voxel> voxelRedundancyCheck = SwiftHashSetPool<Voxel>.Shared.Rent();
 398        SwiftList<ushort> candidateGrids = SwiftListPool<ushort>.Shared.Rent();
 99
 100        try
 101        {
 3102            AddTraceLineVoxelsTo(
 3103                world,
 3104                start,
 3105                end,
 3106                padding,
 3107                includeEnd,
 3108                results,
 3109                voxelRedundancyCheck,
 3110                candidateGrids);
 111
 3112        }
 113        finally
 114        {
 3115            SwiftHashSetPool<Voxel>.Shared.Release(voxelRedundancyCheck);
 3116            SwiftListPool<ushort>.Shared.Release(candidateGrids);
 3117        }
 3118    }
 119
 120    /// <summary>
 121    /// Clears and fills caller-owned storage with voxels traced by a 3D line using caller-owned scratch collections.
 122    /// </summary>
 123    /// <param name="world">The world whose grids should be traced.</param>
 124    /// <param name="start">Starting position in world space.</param>
 125    /// <param name="end">Ending position in world space.</param>
 126    /// <param name="results">Caller-owned storage that receives traced voxels.</param>
 127    /// <param name="scratch">Reusable scratch storage for grid candidates and duplicate-voxel guards.</param>
 128    /// <param name="padding">Value applied to the start/end positions before snapping.</param>
 129    /// <param name="includeEnd">Whether to include the end voxel in the traced line.</param>
 130    public static void TraceLineInto(
 131        GridWorld world,
 132        Vector3d start,
 133        Vector3d end,
 134        SwiftList<Voxel> results,
 135        GridTraceScratch scratch,
 136        Fixed64? padding = null,
 137        bool includeEnd = true)
 138    {
 11139        SwiftThrowHelper.ThrowIfNull(results, nameof(results));
 10140        SwiftThrowHelper.ThrowIfNull(scratch, nameof(scratch));
 141
 9142        results.Clear();
 9143        if (world == null || !world.IsActive)
 2144            return;
 145
 7146        scratch.Clear();
 7147        AddTraceLineVoxelsTo(
 7148            world,
 7149            start,
 7150            end,
 7151            padding,
 7152            includeEnd,
 7153            results,
 7154            scratch.VoxelRedundancy,
 7155            scratch.CandidateGrids);
 156
 7157    }
 158
 159    /// <summary>
 160    /// Traces a 2D XZ-plane line between two points in the supplied world, snapping them to grid coordinates.
 161    /// </summary>
 162    /// <remarks>
 163    /// This method maps <see cref="Vector2d.X"/> to world X, <see cref="Vector2d.Y"/> to world Z,
 164    /// and <paramref name="layerY"/> to world Y. The default layer is world Y = 0.
 165    /// </remarks>
 166    /// <param name="world">The world whose grids should be traced.</param>
 167    /// <param name="start">Starting XZ-plane position in world space.</param>
 168    /// <param name="end">Ending XZ-plane position in world space.</param>
 169    /// <param name="padding">Value applied to the start/end positions before snapping.</param>
 170    /// <param name="includeEnd">Whether to include the end voxel in the traced line.</param>
 171    /// <param name="layerY">The world Y layer to trace. Defaults to zero.</param>
 172    /// <returns>A collection of <see cref="GridVoxelSet"/> objects representing the traced path.</returns>
 173    public static IEnumerable<GridVoxelSet> TraceLine(
 174        GridWorld world,
 175        Vector2d start,
 176        Vector2d end,
 177        Fixed64? padding = null,
 178        bool includeEnd = true,
 179        Fixed64 layerY = default)
 180    {
 4181        Vector3d start3D = GridPlane2d.ToWorld(start, layerY);
 4182        Vector3d end3D = GridPlane2d.ToWorld(end, layerY);
 183
 4184        return TraceLine(world, start3D, end3D, padding, includeEnd);
 185    }
 186
 187    /// <summary>
 188    /// Clears and fills caller-owned storage with voxels traced by a 2D XZ-plane line.
 189    /// </summary>
 190    /// <param name="world">The world whose grids should be traced.</param>
 191    /// <param name="start">Starting XZ-plane position in world space.</param>
 192    /// <param name="end">Ending XZ-plane position in world space.</param>
 193    /// <param name="results">Caller-owned storage that receives traced voxels.</param>
 194    /// <param name="padding">Value applied to the start/end positions before snapping.</param>
 195    /// <param name="includeEnd">Whether to include the end voxel in the traced line.</param>
 196    /// <param name="layerY">The world Y layer to trace. Defaults to zero.</param>
 197    public static void TraceLineInto(
 198        GridWorld world,
 199        Vector2d start,
 200        Vector2d end,
 201        SwiftList<Voxel> results,
 202        Fixed64? padding = null,
 203        bool includeEnd = true,
 204        Fixed64 layerY = default)
 205    {
 1206        Vector3d start3D = GridPlane2d.ToWorld(start, layerY);
 1207        Vector3d end3D = GridPlane2d.ToWorld(end, layerY);
 208
 1209        TraceLineInto(world, start3D, end3D, results, padding, includeEnd);
 1210    }
 211
 212    /// <summary>
 213    /// Clears and fills caller-owned storage with voxels traced by a 2D XZ-plane line using caller-owned scratch collec
 214    /// </summary>
 215    /// <param name="world">The world whose grids should be traced.</param>
 216    /// <param name="start">Starting XZ-plane position in world space.</param>
 217    /// <param name="end">Ending XZ-plane position in world space.</param>
 218    /// <param name="results">Caller-owned storage that receives traced voxels.</param>
 219    /// <param name="scratch">Reusable scratch storage for grid candidates and duplicate-voxel guards.</param>
 220    /// <param name="padding">Value applied to the start/end positions before snapping.</param>
 221    /// <param name="includeEnd">Whether to include the end voxel in the traced line.</param>
 222    /// <param name="layerY">The world Y layer to trace. Defaults to zero.</param>
 223    public static void TraceLineInto(
 224        GridWorld world,
 225        Vector2d start,
 226        Vector2d end,
 227        SwiftList<Voxel> results,
 228        GridTraceScratch scratch,
 229        Fixed64? padding = null,
 230        bool includeEnd = true,
 231        Fixed64 layerY = default)
 232    {
 1233        Vector3d start3D = GridPlane2d.ToWorld(start, layerY);
 1234        Vector3d end3D = GridPlane2d.ToWorld(end, layerY);
 235
 1236        TraceLineInto(world, start3D, end3D, results, scratch, padding, includeEnd);
 1237    }
 238
 239    /// <summary>
 240    /// Retrieves all grid voxels covered by the given bounding area in the supplied world.
 241    /// </summary>
 242    public static IEnumerable<GridVoxelSet> GetCoveredVoxels(
 243        GridWorld world,
 244        Vector3d boundsMin,
 245        Vector3d boundsMax,
 246        Fixed64? padding = null)
 247    {
 204248        if (world == null || !world.IsActive)
 2249            return System.Array.Empty<GridVoxelSet>();
 250
 202251        return GetCoveredVoxelsIterator(world, boundsMin, boundsMax, padding);
 252    }
 253
 254    /// <summary>
 255    /// Retrieves all grid voxels covered by the given XZ-plane bounding area on the supplied world Y layer.
 256    /// </summary>
 257    /// <param name="world">The world whose grids should be queried.</param>
 258    /// <param name="boundsMin">The 2D minimum corner whose X component maps to world X and Y component maps to world Z.
 259    /// <param name="boundsMax">The 2D maximum corner whose X component maps to world X and Y component maps to world Z.
 260    /// <param name="layerY">The world Y layer to cover. Defaults to zero.</param>
 261    /// <param name="padding">Value applied to the min/max bounds before snapping.</param>
 262    /// <returns>A collection of <see cref="GridVoxelSet"/> objects representing the covered voxels.</returns>
 263    public static IEnumerable<GridVoxelSet> GetCoveredVoxels(
 264        GridWorld world,
 265        Vector2d boundsMin,
 266        Vector2d boundsMax,
 267        Fixed64 layerY = default,
 268        Fixed64? padding = null)
 269    {
 5270        (Vector3d min, Vector3d max) = GridPlane2d.ToWorldBounds(boundsMin, boundsMax, layerY);
 5271        return GetCoveredVoxels(world, min, max, padding);
 272    }
 273
 274    /// <summary>
 275    /// Retrieves all grid voxels covered by the given XZ-plane area on the supplied world Y layer.
 276    /// </summary>
 277    /// <param name="world">The world whose grids should be queried.</param>
 278    /// <param name="area">The 2D area whose X component maps to world X and Y component maps to world Z.</param>
 279    /// <param name="layerY">The world Y layer to cover. Defaults to zero.</param>
 280    /// <param name="padding">Value applied to the min/max bounds before snapping.</param>
 281    /// <returns>A collection of <see cref="GridVoxelSet"/> objects representing the covered voxels.</returns>
 282    public static IEnumerable<GridVoxelSet> GetCoveredVoxels(
 283        GridWorld world,
 284        FixedBoundArea area,
 285        Fixed64 layerY = default,
 286        Fixed64? padding = null)
 287    {
 1288        return GetCoveredVoxels(world, area.Min, area.Max, layerY, padding);
 289    }
 290
 291    /// <summary>
 292    /// Clears and fills caller-owned storage with voxels covered by the supplied bounding area.
 293    /// </summary>
 294    /// <param name="world">The world whose grids should be queried.</param>
 295    /// <param name="boundsMin">The minimum corner of the bounding area.</param>
 296    /// <param name="boundsMax">The maximum corner of the bounding area.</param>
 297    /// <param name="results">Caller-owned storage that receives covered voxels.</param>
 298    /// <param name="padding">Value applied to the min/max bounds before normalization.</param>
 299    public static void GetCoveredVoxelsInto(
 300        GridWorld world,
 301        Vector3d boundsMin,
 302        Vector3d boundsMax,
 303        SwiftList<Voxel> results,
 304        Fixed64? padding = null)
 305    {
 5306        SwiftThrowHelper.ThrowIfNull(results, nameof(results));
 307
 4308        results.Clear();
 4309        if (world == null || !world.IsActive)
 1310            return;
 311
 3312        AddCoveredVoxelsTo(world, boundsMin, boundsMax, results, padding);
 3313    }
 314
 315    /// <summary>
 316    /// Clears and fills caller-owned storage with voxels covered by the supplied XZ-plane bounding area.
 317    /// </summary>
 318    /// <param name="world">The world whose grids should be queried.</param>
 319    /// <param name="boundsMin">The 2D minimum corner whose X component maps to world X and Y component maps to world Z.
 320    /// <param name="boundsMax">The 2D maximum corner whose X component maps to world X and Y component maps to world Z.
 321    /// <param name="results">Caller-owned storage that receives covered voxels.</param>
 322    /// <param name="layerY">The world Y layer to cover. Defaults to zero.</param>
 323    /// <param name="padding">Value applied to the min/max bounds before normalization.</param>
 324    public static void GetCoveredVoxelsInto(
 325        GridWorld world,
 326        Vector2d boundsMin,
 327        Vector2d boundsMax,
 328        SwiftList<Voxel> results,
 329        Fixed64 layerY = default,
 330        Fixed64? padding = null)
 331    {
 2332        (Vector3d min, Vector3d max) = GridPlane2d.ToWorldBounds(boundsMin, boundsMax, layerY);
 2333        GetCoveredVoxelsInto(world, min, max, results, padding);
 2334    }
 335
 336    /// <summary>
 337    /// Clears and fills caller-owned storage with voxels covered by the supplied XZ-plane area.
 338    /// </summary>
 339    /// <param name="world">The world whose grids should be queried.</param>
 340    /// <param name="area">The 2D area whose X component maps to world X and Y component maps to world Z.</param>
 341    /// <param name="results">Caller-owned storage that receives covered voxels.</param>
 342    /// <param name="layerY">The world Y layer to cover. Defaults to zero.</param>
 343    /// <param name="padding">Value applied to the min/max bounds before normalization.</param>
 344    public static void GetCoveredVoxelsInto(
 345        GridWorld world,
 346        FixedBoundArea area,
 347        SwiftList<Voxel> results,
 348        Fixed64 layerY = default,
 349        Fixed64? padding = null)
 350    {
 1351        GetCoveredVoxelsInto(world, area.Min, area.Max, results, layerY, padding);
 1352    }
 353
 354    /// <summary>
 355    /// Clears and fills caller-owned storage using caller-owned scratch collections.
 356    /// </summary>
 357    /// <param name="world">The world whose grids should be queried.</param>
 358    /// <param name="boundsMin">The minimum corner of the bounding area.</param>
 359    /// <param name="boundsMax">The maximum corner of the bounding area.</param>
 360    /// <param name="results">Caller-owned storage that receives covered voxels.</param>
 361    /// <param name="scratch">Reusable scratch storage for grid candidates and duplicate-voxel guards.</param>
 362    /// <param name="padding">Value applied to the min/max bounds before normalization.</param>
 363    public static void GetCoveredVoxelsInto(
 364        GridWorld world,
 365        Vector3d boundsMin,
 366        Vector3d boundsMax,
 367        SwiftList<Voxel> results,
 368        GridTraceScratch scratch,
 369        Fixed64? padding = null)
 370    {
 18371        SwiftThrowHelper.ThrowIfNull(results, nameof(results));
 17372        SwiftThrowHelper.ThrowIfNull(scratch, nameof(scratch));
 373
 16374        results.Clear();
 16375        if (world == null || !world.IsActive)
 2376            return;
 377
 14378        AddCoveredVoxelsTo(world, boundsMin, boundsMax, results, scratch, padding);
 14379    }
 380
 381    /// <summary>
 382    /// Clears and fills caller-owned storage using caller-owned scratch collections for an XZ-plane bounding area.
 383    /// </summary>
 384    /// <param name="world">The world whose grids should be queried.</param>
 385    /// <param name="boundsMin">The 2D minimum corner whose X component maps to world X and Y component maps to world Z.
 386    /// <param name="boundsMax">The 2D maximum corner whose X component maps to world X and Y component maps to world Z.
 387    /// <param name="results">Caller-owned storage that receives covered voxels.</param>
 388    /// <param name="scratch">Reusable scratch storage for grid candidates and duplicate-voxel guards.</param>
 389    /// <param name="layerY">The world Y layer to cover. Defaults to zero.</param>
 390    /// <param name="padding">Value applied to the min/max bounds before normalization.</param>
 391    public static void GetCoveredVoxelsInto(
 392        GridWorld world,
 393        Vector2d boundsMin,
 394        Vector2d boundsMax,
 395        SwiftList<Voxel> results,
 396        GridTraceScratch scratch,
 397        Fixed64 layerY = default,
 398        Fixed64? padding = null)
 399    {
 2400        (Vector3d min, Vector3d max) = GridPlane2d.ToWorldBounds(boundsMin, boundsMax, layerY);
 2401        GetCoveredVoxelsInto(world, min, max, results, scratch, padding);
 2402    }
 403
 404    /// <summary>
 405    /// Clears and fills caller-owned storage using caller-owned scratch collections for an XZ-plane area.
 406    /// </summary>
 407    /// <param name="world">The world whose grids should be queried.</param>
 408    /// <param name="area">The 2D area whose X component maps to world X and Y component maps to world Z.</param>
 409    /// <param name="results">Caller-owned storage that receives covered voxels.</param>
 410    /// <param name="scratch">Reusable scratch storage for grid candidates and duplicate-voxel guards.</param>
 411    /// <param name="layerY">The world Y layer to cover. Defaults to zero.</param>
 412    /// <param name="padding">Value applied to the min/max bounds before normalization.</param>
 413    public static void GetCoveredVoxelsInto(
 414        GridWorld world,
 415        FixedBoundArea area,
 416        SwiftList<Voxel> results,
 417        GridTraceScratch scratch,
 418        Fixed64 layerY = default,
 419        Fixed64? padding = null)
 420    {
 1421        GetCoveredVoxelsInto(world, area.Min, area.Max, results, scratch, layerY, padding);
 1422    }
 423
 424    /// <summary>
 425    /// Retrieves all scan cells within the given bounding area across relevant grids in the supplied world.
 426    /// </summary>
 427    /// <param name="world">The world whose grids should be queried.</param>
 428    /// <param name="boundsMin">The minimum corner of the bounding area.</param>
 429    /// <param name="boundsMax">The maximum corner of the bounding area.</param>
 430    /// <param name="padding">Value applied to the min/max bounds before snapping.</param>
 431    /// <returns>An enumerable of covered scan cells grouped by grid.</returns>
 432    public static IEnumerable<ScanCell> GetCoveredScanCells(
 433        GridWorld world,
 434        Vector3d boundsMin,
 435        Vector3d boundsMax,
 436        Fixed64? padding = null)
 437    {
 20438        if (world == null || !world.IsActive)
 2439            return System.Array.Empty<ScanCell>();
 440
 18441        return GetCoveredScanCellsIterator(world, boundsMin, boundsMax, padding);
 442    }
 443
 444    /// <summary>
 445    /// Retrieves all scan cells within the given XZ-plane bounding area on the supplied world Y layer.
 446    /// </summary>
 447    /// <param name="world">The world whose grids should be queried.</param>
 448    /// <param name="boundsMin">The 2D minimum corner whose X component maps to world X and Y component maps to world Z.
 449    /// <param name="boundsMax">The 2D maximum corner whose X component maps to world X and Y component maps to world Z.
 450    /// <param name="layerY">The world Y layer to cover. Defaults to zero.</param>
 451    /// <param name="padding">Value applied to the min/max bounds before snapping.</param>
 452    /// <returns>An enumerable of covered scan cells grouped by grid.</returns>
 453    public static IEnumerable<ScanCell> GetCoveredScanCells(
 454        GridWorld world,
 455        Vector2d boundsMin,
 456        Vector2d boundsMax,
 457        Fixed64 layerY = default,
 458        Fixed64? padding = null)
 459    {
 3460        (Vector3d min, Vector3d max) = GridPlane2d.ToWorldBounds(boundsMin, boundsMax, layerY);
 3461        return GetCoveredScanCells(world, min, max, padding);
 462    }
 463
 464    /// <summary>
 465    /// Retrieves all scan cells within the given XZ-plane area on the supplied world Y layer.
 466    /// </summary>
 467    /// <param name="world">The world whose grids should be queried.</param>
 468    /// <param name="area">The 2D area whose X component maps to world X and Y component maps to world Z.</param>
 469    /// <param name="layerY">The world Y layer to cover. Defaults to zero.</param>
 470    /// <param name="padding">Value applied to the min/max bounds before snapping.</param>
 471    /// <returns>An enumerable of covered scan cells grouped by grid.</returns>
 472    public static IEnumerable<ScanCell> GetCoveredScanCells(
 473        GridWorld world,
 474        FixedBoundArea area,
 475        Fixed64 layerY = default,
 476        Fixed64? padding = null)
 477    {
 1478        return GetCoveredScanCells(world, area.Min, area.Max, layerY, padding);
 479    }
 480
 481    /// <summary>
 482    /// Clears and fills caller-owned storage with scan cells covered by the supplied bounding area.
 483    /// </summary>
 484    public static void GetCoveredScanCellsInto(
 485        GridWorld world,
 486        Vector3d boundsMin,
 487        Vector3d boundsMax,
 488        SwiftList<ScanCell> results,
 489        Fixed64? padding = null)
 490    {
 6491        SwiftThrowHelper.ThrowIfNull(results, nameof(results));
 492
 5493        results.Clear();
 5494        if (world == null || !world.IsActive)
 2495            return;
 496
 3497        AddCoveredScanCellsTo(world, boundsMin, boundsMax, results, padding);
 3498    }
 499
 500    /// <summary>
 501    /// Clears and fills caller-owned storage with scan cells covered by the supplied XZ-plane bounding area.
 502    /// </summary>
 503    public static void GetCoveredScanCellsInto(
 504        GridWorld world,
 505        Vector2d boundsMin,
 506        Vector2d boundsMax,
 507        SwiftList<ScanCell> results,
 508        Fixed64 layerY = default,
 509        Fixed64? padding = null)
 510    {
 2511        (Vector3d min, Vector3d max) = GridPlane2d.ToWorldBounds(boundsMin, boundsMax, layerY);
 2512        GetCoveredScanCellsInto(world, min, max, results, padding);
 2513    }
 514
 515    /// <summary>
 516    /// Clears and fills caller-owned storage with scan cells covered by the supplied XZ-plane area.
 517    /// </summary>
 518    public static void GetCoveredScanCellsInto(
 519        GridWorld world,
 520        FixedBoundArea area,
 521        SwiftList<ScanCell> results,
 522        Fixed64 layerY = default,
 523        Fixed64? padding = null)
 524    {
 1525        GetCoveredScanCellsInto(world, area.Min, area.Max, results, layerY, padding);
 1526    }
 527
 528    /// <summary>
 529    /// Clears and fills caller-owned storage using caller-owned scratch collections.
 530    /// </summary>
 531    public static void GetCoveredScanCellsInto(
 532        GridWorld world,
 533        Vector3d boundsMin,
 534        Vector3d boundsMax,
 535        SwiftList<ScanCell> results,
 536        GridScanScratch scratch,
 537        Fixed64? padding = null)
 538    {
 14539        SwiftThrowHelper.ThrowIfNull(results, nameof(results));
 13540        SwiftThrowHelper.ThrowIfNull(scratch, nameof(scratch));
 541
 12542        results.Clear();
 12543        if (world == null || !world.IsActive)
 2544            return;
 545
 10546        AddCoveredScanCellsTo(world, boundsMin, boundsMax, results, scratch, padding);
 10547    }
 548
 549    /// <summary>
 550    /// Clears and fills caller-owned storage using caller-owned scratch collections for an XZ-plane bounding area.
 551    /// </summary>
 552    public static void GetCoveredScanCellsInto(
 553        GridWorld world,
 554        Vector2d boundsMin,
 555        Vector2d boundsMax,
 556        SwiftList<ScanCell> results,
 557        GridScanScratch scratch,
 558        Fixed64 layerY = default,
 559        Fixed64? padding = null)
 560    {
 2561        (Vector3d min, Vector3d max) = GridPlane2d.ToWorldBounds(boundsMin, boundsMax, layerY);
 2562        GetCoveredScanCellsInto(world, min, max, results, scratch, padding);
 2563    }
 564
 565    /// <summary>
 566    /// Clears and fills caller-owned storage using caller-owned scratch collections for an XZ-plane area.
 567    /// </summary>
 568    public static void GetCoveredScanCellsInto(
 569        GridWorld world,
 570        FixedBoundArea area,
 571        SwiftList<ScanCell> results,
 572        GridScanScratch scratch,
 573        Fixed64 layerY = default,
 574        Fixed64? padding = null)
 575    {
 1576        GetCoveredScanCellsInto(world, area.Min, area.Max, results, scratch, layerY, padding);
 1577    }
 578
 579    /// <summary>
 580    /// Appends covered scan cells without allocating an iterator for hot-path callers.
 581    /// </summary>
 582    internal static void AddCoveredScanCellsTo(
 583        GridWorld world,
 584        Vector3d boundsMin,
 585        Vector3d boundsMax,
 586        SwiftList<ScanCell> scanCells,
 587        Fixed64? padding = null)
 588    {
 21589        SwiftHashSet<ScanCell> voxelRedundancyCheck = SwiftHashSetPool<ScanCell>.Shared.Rent();
 21590        SwiftList<ushort> candidateGrids = SwiftListPool<ushort>.Shared.Rent();
 591
 592        try
 593        {
 21594            AddCoveredScanCellsCore(
 21595                world,
 21596                boundsMin,
 21597                boundsMax,
 21598                scanCells,
 21599                candidateGrids,
 21600                voxelRedundancyCheck,
 21601                padding);
 21602        }
 603        finally
 604        {
 21605            SwiftHashSetPool<ScanCell>.Shared.Release(voxelRedundancyCheck);
 21606            SwiftListPool<ushort>.Shared.Release(candidateGrids);
 21607        }
 21608    }
 609
 610    /// <summary>
 611    /// Appends covered scan cells using caller-owned scratch state for allocation-sensitive scans.
 612    /// </summary>
 613    internal static void AddCoveredScanCellsTo(
 614        GridWorld world,
 615        Vector3d boundsMin,
 616        Vector3d boundsMax,
 617        SwiftList<ScanCell> scanCells,
 618        GridScanScratch scratch,
 619        Fixed64? padding = null)
 620    {
 528621        scratch.Clear();
 528622        AddCoveredScanCellsCore(
 528623            world,
 528624            boundsMin,
 528625            boundsMax,
 528626            scanCells,
 528627            scratch.CandidateGrids,
 528628            scratch.ScanCellRedundancy,
 528629            padding);
 528630    }
 631
 632    /// <summary>
 633    /// Appends covered voxels without allocating an iterator for hot-path callers.
 634    /// </summary>
 635    internal static void AddCoveredVoxelsTo(
 636        GridWorld world,
 637        Vector3d boundsMin,
 638        Vector3d boundsMax,
 639        SwiftList<Voxel> voxels,
 640        Fixed64? padding = null)
 641    {
 3642        SwiftHashSet<Voxel> voxelRedundancyCheck = SwiftHashSetPool<Voxel>.Shared.Rent();
 3643        SwiftList<ushort> candidateGrids = SwiftListPool<ushort>.Shared.Rent();
 644
 645        try
 646        {
 3647            AddCoveredVoxelsCore(
 3648                world,
 3649                boundsMin,
 3650                boundsMax,
 3651                voxels,
 3652                candidateGrids,
 3653                voxelRedundancyCheck,
 3654                padding);
 3655        }
 656        finally
 657        {
 3658            SwiftHashSetPool<Voxel>.Shared.Release(voxelRedundancyCheck);
 3659            SwiftListPool<ushort>.Shared.Release(candidateGrids);
 3660        }
 3661    }
 662
 663    /// <summary>
 664    /// Appends covered voxels using caller-owned scratch state for allocation-sensitive coverage scans.
 665    /// </summary>
 666    internal static void AddCoveredVoxelsTo(
 667        GridWorld world,
 668        Vector3d boundsMin,
 669        Vector3d boundsMax,
 670        SwiftList<Voxel> voxels,
 671        GridTraceScratch scratch,
 672        Fixed64? padding = null)
 673    {
 14674        scratch.Clear();
 14675        AddCoveredVoxelsCore(
 14676            world,
 14677            boundsMin,
 14678            boundsMax,
 14679            voxels,
 14680            scratch.CandidateGrids,
 14681            scratch.VoxelRedundancy,
 14682            padding);
 14683    }
 684
 685    private static void AddCoveredVoxelsCore(
 686        GridWorld world,
 687        Vector3d boundsMin,
 688        Vector3d boundsMax,
 689        SwiftList<Voxel> voxels,
 690        SwiftList<ushort> candidateGrids,
 691        SwiftHashSet<Voxel> voxelRedundancyCheck,
 692        Fixed64? padding = null)
 693    {
 17694        (Vector3d queryMin, Vector3d queryMax) =
 17695            CreatePaddedOrderedBounds(boundsMin, boundsMax, padding);
 17696        (Vector3d candidateMin, Vector3d candidateMax) =
 17697            ExpandOrderedBounds(queryMin, queryMax, world.MaxTopologyCellEdge);
 698
 17699        _ = world.CollectGridCandidates(
 17700            candidateMin,
 17701            candidateMax,
 17702            candidateGrids,
 17703            GridWorld.MaxGrids);
 106704        foreach (ushort gridIndex in candidateGrids)
 705        {
 36706            AddCoveredGridVoxels(
 36707                world.ActiveGrids[gridIndex],
 36708                queryMin,
 36709                queryMax,
 36710                voxels,
 36711                voxelRedundancyCheck);
 712        }
 17713    }
 714
 715    private static void AddCoveredScanCellsCore(
 716        GridWorld world,
 717        Vector3d boundsMin,
 718        Vector3d boundsMax,
 719        SwiftList<ScanCell> scanCells,
 720        SwiftList<ushort> candidateGrids,
 721        SwiftHashSet<ScanCell> voxelRedundancyCheck,
 722        Fixed64? padding = null)
 723    {
 567724        (Vector3d queryMin, Vector3d queryMax) =
 567725            CreatePaddedOrderedBounds(boundsMin, boundsMax, padding);
 567726        (Vector3d candidateMin, Vector3d candidateMax) =
 567727            ExpandOrderedBounds(queryMin, queryMax, world.MaxTopologyCellEdge);
 567728        _ = world.CollectGridCandidates(
 567729            candidateMin,
 567730            candidateMax,
 567731            candidateGrids,
 567732            GridWorld.MaxGrids);
 2332733        foreach (ushort gridIndex in candidateGrids)
 734        {
 599735            AddCoveredScanCellsForGrid(
 599736                world.ActiveGrids[gridIndex],
 599737                queryMin,
 599738                queryMax,
 599739                scanCells,
 599740                voxelRedundancyCheck);
 741        }
 567742    }
 743
 744    private static IEnumerable<GridVoxelSet> GetCoveredVoxelsIterator(
 745        GridWorld world,
 746        Vector3d boundsMin,
 747        Vector3d boundsMax,
 748        Fixed64? padding)
 749    {
 202750        SwiftList<GridVoxelSet> gridVoxelSets = SwiftListPool<GridVoxelSet>.Shared.Rent();
 202751        SwiftHashSet<Voxel> voxelRedundancyCheck = SwiftHashSetPool<Voxel>.Shared.Rent();
 202752        SwiftList<ushort> candidateGrids = SwiftListPool<ushort>.Shared.Rent();
 753
 754        try
 755        {
 202756            AddCoveredVoxelsToMapping(
 202757                world,
 202758                boundsMin,
 202759                boundsMax,
 202760                padding,
 202761                gridVoxelSets,
 202762                voxelRedundancyCheck,
 202763                candidateGrids);
 764
 834765            foreach (GridVoxelSet gridVoxelSet in gridVoxelSets)
 215766                yield return gridVoxelSet;
 202767        }
 768        finally
 769        {
 202770            ReleaseGridVoxelSets(gridVoxelSets);
 202771            SwiftHashSetPool<Voxel>.Shared.Release(voxelRedundancyCheck);
 202772            SwiftListPool<ushort>.Shared.Release(candidateGrids);
 202773        }
 202774    }
 775
 776    private static void AddCoveredVoxelsToMapping(
 777        GridWorld world,
 778        Vector3d boundsMin,
 779        Vector3d boundsMax,
 780        Fixed64? padding,
 781        SwiftList<GridVoxelSet> gridVoxelSets,
 782        SwiftHashSet<Voxel> voxelRedundancyCheck,
 783        SwiftList<ushort> candidateGrids)
 784    {
 202785        (Vector3d queryMin, Vector3d queryMax) =
 202786            CreatePaddedOrderedBounds(boundsMin, boundsMax, padding);
 202787        (Vector3d candidateMin, Vector3d candidateMax) =
 202788            ExpandOrderedBounds(queryMin, queryMax, world.MaxTopologyCellEdge);
 789
 202790        _ = world.CollectGridCandidates(
 202791            candidateMin,
 202792            candidateMax,
 202793            candidateGrids,
 202794            GridWorld.MaxGrids);
 842795        foreach (ushort gridIndex in candidateGrids)
 796        {
 219797            AddCoveredVoxelsForGrid(
 219798                world.ActiveGrids[gridIndex],
 219799                queryMin,
 219800                queryMax,
 219801                gridVoxelSets,
 219802                voxelRedundancyCheck);
 803        }
 202804    }
 805
 806    private static IEnumerable<ScanCell> GetCoveredScanCellsIterator(
 807        GridWorld world,
 808        Vector3d boundsMin,
 809        Vector3d boundsMax,
 810        Fixed64? padding)
 811    {
 18812        SwiftList<ScanCell> scanCells = SwiftListPool<ScanCell>.Shared.Rent();
 18813        SwiftHashSet<ScanCell> voxelRedundancyCheck = SwiftHashSetPool<ScanCell>.Shared.Rent();
 18814        SwiftList<ushort> candidateGrids = SwiftListPool<ushort>.Shared.Rent();
 815
 816        try
 817        {
 18818            AddCoveredScanCellsCore(
 18819                world,
 18820                boundsMin,
 18821                boundsMax,
 18822                scanCells,
 18823                candidateGrids,
 18824                voxelRedundancyCheck,
 18825                padding);
 826
 202827            foreach (ScanCell scanCell in scanCells)
 83828                yield return scanCell;
 18829        }
 830        finally
 831        {
 18832            SwiftListPool<ScanCell>.Shared.Release(scanCells);
 18833            SwiftHashSetPool<ScanCell>.Shared.Release(voxelRedundancyCheck);
 18834            SwiftListPool<ushort>.Shared.Release(candidateGrids);
 18835        }
 18836    }
 837}

/home/runner/work/GridForge/GridForge/src/GridForge/Utility/GridTracer.GridCoverage.cs

#LineLine coverage
 1//=======================================================================
 2// GridTracer.GridCoverage.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 System.Runtime.CompilerServices;
 9using FixedMathSharp;
 10using GridForge.Grids;
 11using GridForge.Grids.Topology;
 12using GridForge.Spatial;
 13using SwiftCollections;
 14using SwiftCollections.Pool;
 15
 16namespace GridForge.Utility;
 17
 18/// <content>
 19/// Grid coverage utilities for resolving scan cells and voxels that intersect
 20/// a given world-space query bounds, including specialized handling for hex-prism topologies.
 21/// </content>
 22public static partial class GridTracer
 23{
 24    private static void AddCoveredScanCellsForGrid(
 25        VoxelGrid currentGrid,
 26        Vector3d queryMin,
 27        Vector3d queryMax,
 28        SwiftList<ScanCell> scanCells,
 29        SwiftHashSet<ScanCell> voxelRedundancyCheck)
 30    {
 59931        if (currentGrid.Topology.Kind == GridTopologyKind.HexPrism)
 32        {
 733            AddCoveredHexScanCellsForGrid(
 734                currentGrid,
 735                queryMin,
 736                queryMax,
 737                scanCells,
 738                voxelRedundancyCheck);
 739            return;
 40        }
 41
 59242        if (!TryGetCoveredScanCellRange(
 59243                currentGrid,
 59244                queryMin,
 59245                queryMax,
 59246                out int xMin,
 59247                out int yMin,
 59248                out int zMin,
 59249                out int xMax,
 59250                out int yMax,
 59251                out int zMax))
 52        {
 153            return;
 54        }
 55
 59156        currentGrid.AddScanCellsInRange(
 59157            xMin,
 59158            yMin,
 59159            zMin,
 59160            xMax,
 59161            yMax,
 59162            zMax,
 59163            scanCells,
 59164            voxelRedundancyCheck);
 59165    }
 66
 67    private static void AddCoveredVoxelsForGrid(
 68        VoxelGrid currentGrid,
 69        Vector3d queryMin,
 70        Vector3d queryMax,
 71        SwiftList<GridVoxelSet> gridVoxelSets,
 72        SwiftHashSet<Voxel> voxelRedundancyCheck)
 73    {
 21974        SwiftList<Voxel> voxelList = SwiftListPool<Voxel>.Shared.Rent();
 21975        AddCoveredGridVoxels(
 21976            currentGrid,
 21977            queryMin,
 21978            queryMax,
 21979            voxelList,
 21980            voxelRedundancyCheck);
 81
 21982        if (voxelList.Count > 0)
 21583            gridVoxelSets.Add(new GridVoxelSet(currentGrid, voxelList));
 84        else
 485            SwiftListPool<Voxel>.Shared.Release(voxelList);
 486    }
 87
 88    private static void AddCoveredGridVoxels(
 89        VoxelGrid currentGrid,
 90        Vector3d queryMin,
 91        Vector3d queryMax,
 92        SwiftList<Voxel> voxelList,
 93        SwiftHashSet<Voxel> voxelRedundancyCheck)
 94    {
 25595        if (currentGrid.Topology.Kind == GridTopologyKind.HexPrism)
 96        {
 997            AddCoveredHexGridVoxels(
 998                currentGrid,
 999                queryMin,
 9100                queryMax,
 9101                voxelList);
 9102            return;
 103        }
 104
 246105        if (!TopologyVoxelRangeUtility.TryGetCandidateRange(
 246106                currentGrid,
 246107                queryMin,
 246108                queryMax,
 246109                out VoxelIndex minIndex,
 246110                out VoxelIndex maxIndex))
 111        {
 1112            return;
 113        }
 114
 245115        currentGrid.AddVoxelsInIndexRange(
 245116            minIndex,
 245117            maxIndex,
 245118            voxelList,
 245119            voxelRedundancyCheck);
 245120    }
 121
 122    private static void AddCoveredHexGridVoxels(
 123        VoxelGrid currentGrid,
 124        Vector3d queryMin,
 125        Vector3d queryMax,
 126        SwiftList<Voxel> voxelList)
 127    {
 9128        if (!TopologyVoxelRangeUtility.TryGetCandidateRange(
 9129                currentGrid,
 9130                queryMin,
 9131                queryMax,
 9132                out VoxelIndex minIndex,
 9133                out VoxelIndex maxIndex))
 134        {
 1135            return;
 136        }
 137
 8138        Fixed64 horizontalExpansion =
 8139            currentGrid.Topology.Metrics.CellRadius;
 8140        Fixed64 coverageMinX = queryMin.X - horizontalExpansion;
 8141        Fixed64 coverageMaxX = queryMax.X + horizontalExpansion;
 8142        Fixed64 coverageMinZ = queryMin.Z - horizontalExpansion;
 8143        Fixed64 coverageMaxZ = queryMax.Z + horizontalExpansion;
 144
 44145        for (long x = minIndex.x; x <= maxIndex.x; x++)
 146        {
 56147            for (long y = minIndex.y; y <= maxIndex.y; y++)
 148            {
 76149                for (long z = minIndex.z; z <= maxIndex.z; z++)
 150                {
 24151                    if (currentGrid.TryGetVoxel(
 24152                            (int)x,
 24153                            (int)y,
 24154                            (int)z,
 24155                            out Voxel? voxel)
 24156                        && IsHexVoxelCenterInHorizontalCoverage(
 24157                            voxel!,
 24158                            coverageMinX,
 24159                            coverageMaxX,
 24160                            coverageMinZ,
 24161                            coverageMaxZ))
 162                    {
 13163                        voxelList.Add(voxel!);
 164                    }
 165                }
 166            }
 167        }
 8168    }
 169
 170    private static void AddCoveredHexScanCellsForGrid(
 171        VoxelGrid currentGrid,
 172        Vector3d queryMin,
 173        Vector3d queryMax,
 174        SwiftList<ScanCell> scanCells,
 175        SwiftHashSet<ScanCell> scanCellRedundancyCheck)
 176    {
 7177        if (!TopologyVoxelRangeUtility.TryGetCandidateRange(
 7178                currentGrid,
 7179                queryMin,
 7180                queryMax,
 7181                out VoxelIndex minIndex,
 7182                out VoxelIndex maxIndex))
 183        {
 1184            return;
 185        }
 186
 6187        currentGrid.AddScanCellsInRange(
 6188            minIndex.x / currentGrid.ScanCellSize,
 6189            minIndex.y / currentGrid.ScanCellSize,
 6190            minIndex.z / currentGrid.ScanCellSize,
 6191            maxIndex.x / currentGrid.ScanCellSize,
 6192            maxIndex.y / currentGrid.ScanCellSize,
 6193            maxIndex.z / currentGrid.ScanCellSize,
 6194            scanCells,
 6195            scanCellRedundancyCheck);
 6196    }
 197
 198    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 199    private static bool IsHexVoxelCenterInHorizontalCoverage(
 200        Voxel voxel,
 201        Fixed64 coverageMinX,
 202        Fixed64 coverageMaxX,
 203        Fixed64 coverageMinZ,
 204        Fixed64 coverageMaxZ)
 205    {
 22206        Vector3d position = voxel.WorldPosition;
 22207        return position.X >= coverageMinX
 22208            && position.X <= coverageMaxX
 22209            && position.Z >= coverageMinZ
 22210            && position.Z <= coverageMaxZ;
 211    }
 212}

/home/runner/work/GridForge/GridForge/src/GridForge/Utility/GridTracer.NavigationBody.cs

#LineLine coverage
 1//=======================================================================
 2// GridTracer.NavigationBody.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 System;
 9using System.Collections.Generic;
 10using FixedMathSharp;
 11using FixedMathSharp.Geometry;
 12using GridForge.Grids;
 13using GridForge.Grids.Storage;
 14using GridForge.Grids.Topology;
 15using GridForge.Spatial;
 16using SwiftCollections;
 17
 18namespace GridForge.Utility;
 19
 20/// <content>Provides bounded swept navigation-body coverage.</content>
 21public static partial class GridTracer
 22{
 23    /// <summary>Writes the canonical cells required by one direct upright-body sweep.</summary>
 24    /// <remarks>
 25    /// The start and end bodies must have closed-set contact with the declared source and target
 26    /// prisms respectively; exact endpoint tangency is admitted for that identity check.
 27    /// A prism is claimed only when its planar and vertical interiors overlap the swept body at
 28    /// one shared continuous parameter. Boundary-only coincidence and tangency are excluded.
 29    /// Grid, address, output, and combined candidate-work ceilings are independent.
 30    /// </remarks>
 31    public static GridNavigationBodyTraceReport TraceNavigationBodyInto(
 32        GridWorld world,
 33        WorldVoxelIndex source,
 34        WorldVoxelIndex target,
 35        Vector3d startFoot,
 36        Vector3d endFoot,
 37        Fixed64 horizontalRadius,
 38        Fixed64 bodyHeight,
 39        SwiftList<GridNavigationBodyTraceCell> results,
 40        GridNavigationBodyTraceScratch scratch,
 41        int gridCandidateLimit,
 42        int addressCandidateLimit,
 43        int outputLimit,
 44        long candidateWorkLimit)
 45    {
 7846        SwiftThrowHelper.ThrowIfNull(results, nameof(results));
 7847        SwiftThrowHelper.ThrowIfNull(scratch, nameof(scratch));
 7848        SwiftThrowHelper.ThrowIfNegative(gridCandidateLimit, nameof(gridCandidateLimit));
 7749        SwiftThrowHelper.ThrowIfNegative(addressCandidateLimit, nameof(addressCandidateLimit));
 7650        SwiftThrowHelper.ThrowIfNegative(outputLimit, nameof(outputLimit));
 7551        if (candidateWorkLimit < 0L)
 152            throw new ArgumentOutOfRangeException(nameof(candidateWorkLimit));
 53
 7454        results.Clear();
 7455        scratch.Clear();
 7456        if (world == null
 7457            || !world.IsActive
 7458            || horizontalRadius < Fixed64.Zero
 7459            || bodyHeight <= Fixed64.Zero)
 60        {
 461            return CreateNavigationBodyTraceReport(
 462                GridNavigationBodyTraceStatus.InvalidOrUnrepresentableGeometry,
 463                0,
 464                0,
 465                results,
 466                default);
 67        }
 68
 7069        if (!Fixed64.TryAdd(startFoot.Y, bodyHeight, out Fixed64 startTop)
 7070            || !Fixed64.TryAdd(endFoot.Y, bodyHeight, out Fixed64 endTop)
 7071            || !TryCreateNavigationBodyBounds(
 7072                startFoot,
 7073                endFoot,
 7074                startTop,
 7075                endTop,
 7076                horizontalRadius,
 7077                out Vector3d queryMin,
 7078                out Vector3d queryMax))
 79        {
 880            return CreateNavigationBodyTraceReport(
 881                GridNavigationBodyTraceStatus.ArithmeticOverflow,
 882                0,
 883                0,
 884                results,
 885                default);
 86        }
 87
 6288        world.EnterReadLock();
 89        try
 90        {
 6291            if (!world.TryGetGrid(source, out VoxelGrid? sourceGridValue)
 6292                || !world.TryGetGrid(target, out VoxelGrid? targetGridValue))
 93            {
 194                return FailNavigationBodyTrace(
 195                    results,
 196                    GridNavigationBodyTraceStatus.InvalidOrUnrepresentableGeometry,
 197                    0,
 198                    0,
 199                    default);
 100            }
 101
 61102            VoxelGrid sourceGrid = sourceGridValue!;
 61103            VoxelGrid targetGrid = targetGridValue!;
 61104            if (!GridCellGeometry.TryCreatePrism(
 61105                    sourceGrid.Configuration.TopologyKind,
 61106                    sourceGrid.Configuration.TopologyMetrics,
 61107                    sourceGrid.GetWorldPosition(source.VoxelIndex),
 61108                    source,
 61109                    out GridCellPrism sourcePrism)
 61110                || !GridCellGeometry.TryCreatePrism(
 61111                    targetGrid.Configuration.TopologyKind,
 61112                    targetGrid.Configuration.TopologyMetrics,
 61113                    targetGrid.GetWorldPosition(target.VoxelIndex),
 61114                    target,
 61115                    out GridCellPrism targetPrism))
 116            {
 2117                return FailNavigationBodyTrace(
 2118                    results,
 2119                    GridNavigationBodyTraceStatus.InvalidOrUnrepresentableGeometry,
 2120                    0,
 2121                    0,
 2122                    default);
 123            }
 124
 59125            if (!HasClosedNavigationBodyPrismContact(
 59126                    sourcePrism,
 59127                    startFoot,
 59128                    startTop,
 59129                    horizontalRadius)
 59130                || !HasClosedNavigationBodyPrismContact(
 59131                    targetPrism,
 59132                    endFoot,
 59133                    endTop,
 59134                    horizontalRadius))
 135            {
 5136                return FailNavigationBodyTrace(
 5137                    results,
 5138                    GridNavigationBodyTraceStatus.InvalidOrUnrepresentableGeometry,
 5139                    0,
 5140                    0,
 5141                    default);
 142            }
 143
 54144            Span<GridCellPrism> closurePrisms = stackalloc GridCellPrism[8];
 54145            int closureCount = GetNavigationClosure(
 54146                sourceGrid,
 54147                sourcePrism,
 54148                targetPrism,
 54149                closurePrisms);
 54150            if (closureCount == 0)
 151            {
 2152                return FailNavigationBodyTrace(
 2153                    results,
 2154                    GridNavigationBodyTraceStatus.InvalidOrUnrepresentableGeometry,
 2155                    0,
 2156                    0,
 2157                    default);
 158            }
 159
 52160            if (!TryExpandNavigationBodyBounds(
 52161                    queryMin,
 52162                    queryMax,
 52163                    world.MaxTopologyCellEdge,
 52164                    out Vector3d candidateMin,
 52165                    out Vector3d candidateMax))
 166            {
 7167                return FailNavigationBodyTrace(
 7168                    results,
 7169                    GridNavigationBodyTraceStatus.ArithmeticOverflow,
 7170                    0,
 7171                    0,
 7172                    default);
 173            }
 174
 45175            bool gridWorkLimitIsTighter = candidateWorkLimit < gridCandidateLimit;
 45176            int effectiveGridLimit = gridWorkLimitIsTighter
 45177                ? (int)candidateWorkLimit
 45178                : gridCandidateLimit;
 45179            if (!world.CollectGridCandidates(
 45180                    candidateMin,
 45181                    candidateMax,
 45182                    scratch.CandidateGrids,
 45183                    effectiveGridLimit))
 184            {
 3185                return FailNavigationBodyTrace(
 3186                    results,
 3187                    gridWorkLimitIsTighter
 3188                        ? GridNavigationBodyTraceStatus.CandidateWorkLimitExceeded
 3189                        : GridNavigationBodyTraceStatus.GridCandidateLimitExceeded,
 3190                    scratch.CandidateGrids.Count,
 3191                    0,
 3192                    default);
 193            }
 194
 42195            SortGridIndices(world, scratch.CandidateGrids);
 42196            long remainingWork = candidateWorkLimit - scratch.CandidateGrids.Count;
 42197            bool workLimitIsTighter = remainingWork < addressCandidateLimit;
 42198            int effectiveAddressLimit = workLimitIsTighter
 42199                ? (int)remainingWork
 42200                : addressCandidateLimit;
 42201            int addressCandidateCount = 0;
 208202            for (int gridOrdinal = 0; gridOrdinal < scratch.CandidateGrids.Count; gridOrdinal++)
 203            {
 65204                VoxelGrid grid = world.ActiveGrids[scratch.CandidateGrids[gridOrdinal]];
 65205                if (!TopologyVoxelRangeUtility.TryGetPrismCandidateRange(
 65206                        grid,
 65207                        queryMin,
 65208                        queryMax,
 65209                        out VoxelIndex minimum,
 65210                        out VoxelIndex maximum))
 211                {
 212                    continue;
 213                }
 214
 344215                for (int x = minimum.x; x <= maximum.x; x++)
 216                {
 478217                    for (int y = minimum.y; y <= maximum.y; y++)
 218                    {
 764219                        for (int z = minimum.z; z <= maximum.z; z++)
 220                        {
 253221                            if (addressCandidateCount >= effectiveAddressLimit)
 222                            {
 2223                                return FailNavigationBodyTrace(
 2224                                    results,
 2225                                    workLimitIsTighter
 2226                                        ? GridNavigationBodyTraceStatus.CandidateWorkLimitExceeded
 2227                                        : GridNavigationBodyTraceStatus.AddressLimitExceeded,
 2228                                    scratch.CandidateGrids.Count,
 2229                                    addressCandidateCount,
 2230                                    default);
 231                            }
 232
 251233                            addressCandidateCount++;
 251234                            VoxelIndex index = new(x, y, z);
 251235                            WorldVoxelIndex cell = new(
 251236                                world.SpawnToken,
 251237                                grid.GridIndex,
 251238                                grid.SpawnToken,
 251239                                index);
 251240                            if (!GridCellGeometry.TryCreatePrism(
 251241                                    grid.Configuration.TopologyKind,
 251242                                    grid.Configuration.TopologyMetrics,
 251243                                    grid.GetWorldPosition(index),
 251244                                    cell,
 251245                                    out GridCellPrism prism))
 246                            {
 1247                                return FailNavigationBodyTrace(
 1248                                    results,
 1249                                    GridNavigationBodyTraceStatus.InvalidOrUnrepresentableGeometry,
 1250                                    scratch.CandidateGrids.Count,
 1251                                    addressCandidateCount,
 1252                                    default);
 253                            }
 254
 250255                            bool hasPositiveOverlap =
 250256                                GridCellGeometry.HasPositiveNavigationBodyPrismOverlap(
 250257                                    prism,
 250258                                    startFoot,
 250259                                    endFoot,
 250260                                    horizontalRadius,
 250261                                    bodyHeight);
 250262                            bool isClosure = IsNavigationClosurePrism(
 250263                                prism,
 250264                                closurePrisms,
 250265                                closureCount);
 250266                            if (!hasPositiveOverlap && !isClosure)
 267                                continue;
 268
 153269                            scratch.AddressCandidates.Add(new GridNavigationBodyTraceCandidate(
 153270                                grid,
 153271                                index,
 153272                                prism,
 153273                                hasPositiveOverlap,
 153274                                isClosure));
 275                        }
 276                    }
 277                }
 278            }
 279
 39280            GridCoveredAddressRunStamp runStamp = SnapshotNavigationBodyCandidates(
 39281                world,
 39282                scratch.AddressCandidates);
 39283            scratch.AddressCandidates.SortInPlace(
 39284                default(GridNavigationBodyTraceCandidateComparer));
 39285            if (!HasNavigationBodyUnionCoverage(
 39286                    sourceGrid,
 39287                    source.VoxelIndex,
 39288                    targetGrid,
 39289                    target.VoxelIndex,
 39290                    startFoot,
 39291                    endFoot,
 39292                    horizontalRadius,
 39293                    bodyHeight,
 39294                    scratch.AddressCandidates,
 39295                    scratch.UnionMembers))
 296            {
 2297                return FailNavigationBodyTrace(
 2298                    results,
 2299                    GridNavigationBodyTraceStatus.InvalidOrUnrepresentableGeometry,
 2300                    scratch.CandidateGrids.Count,
 2301                    addressCandidateCount,
 2302                    default);
 303            }
 37304            int alternativeEvidenceCount = CountMissingNavigationBodyAlternativeEvidence(
 37305                scratch.AddressCandidates,
 37306                sourceGrid,
 37307                source.VoxelIndex,
 37308                targetGrid,
 37309                target.VoxelIndex);
 37310            if (scratch.UnionMembers.Count > outputLimit
 37311                || alternativeEvidenceCount > outputLimit - scratch.UnionMembers.Count)
 312            {
 2313                return FailNavigationBodyTrace(
 2314                    results,
 2315                    GridNavigationBodyTraceStatus.OutputLimitExceeded,
 2316                    scratch.CandidateGrids.Count,
 2317                    addressCandidateCount,
 2318                    default);
 319            }
 320
 35321            bool hasMissingPhysicalCell = false;
 300322            for (int i = 0; i < scratch.UnionMembers.Count; i++)
 323            {
 115324                GridNavigationBodyTraceCandidate candidate =
 115325                    scratch.AddressCandidates[scratch.UnionMembers[i]];
 115326                hasMissingPhysicalCell |= !candidate.IsPhysicallyPresent;
 115327                results.Add(new GridNavigationBodyTraceCell(
 115328                    new WorldVoxelIndex(
 115329                        world.SpawnToken,
 115330                        candidate.Grid.GridIndex,
 115331                        candidate.Grid.SpawnToken,
 115332                        candidate.Index),
 115333                    candidate.Grid.Configuration.ToGridKey(),
 115334                    candidate.IsPhysicallyPresent,
 115335                    candidate.GridLastChangeSequence,
 115336                    GridNavigationBodyTraceCellRole.RequiredCoverage));
 337            }
 338
 35339            if (hasMissingPhysicalCell)
 340            {
 10341                AppendMissingNavigationBodyAlternativeEvidence(
 10342                    world,
 10343                    scratch.AddressCandidates,
 10344                    results,
 10345                    sourceGrid,
 10346                    source.VoxelIndex,
 10347                    targetGrid,
 10348                    target.VoxelIndex);
 349            }
 350
 35351            results.SortInPlace(default(GridNavigationBodyTraceCellComparer));
 35352            return CreateNavigationBodyTraceReport(
 35353                hasMissingPhysicalCell
 35354                    ? GridNavigationBodyTraceStatus.IncompletePhysicalCoverage
 35355                    : GridNavigationBodyTraceStatus.Complete,
 35356                scratch.CandidateGrids.Count,
 35357                addressCandidateCount,
 35358                results,
 35359                runStamp);
 360        }
 361        finally
 362        {
 62363            world.ExitReadLock();
 62364            scratch.Clear();
 62365        }
 62366    }
 367
 368    private static bool HasClosedNavigationBodyPrismContact(
 369        in GridCellPrism prism,
 370        Vector3d foot,
 371        Fixed64 bodyTop,
 372        Fixed64 horizontalRadius)
 373    {
 113374        if (foot.Y > prism.VerticalMax || bodyTop < prism.VerticalMin)
 1375            return false;
 376
 112377        Span<Vector2d> offsets = stackalloc Vector2d[6];
 112378        Vector2d planarOrigin = new(prism.Center.X, prism.Center.Z);
 1136379        for (int i = 0; i < prism.FootprintVertexCount; i++)
 456380            offsets[i] = prism.GetFootprintVertex(i) - planarOrigin;
 381
 112382        return FixedConvex2dRelations.TryGetCircleContact(
 112383            new Vector2d(foot.X, foot.Z),
 112384            Fixed64.Zero,
 112385            horizontalRadius,
 112386            planarOrigin,
 112387            Fixed64.Zero,
 112388            offsets[..prism.FootprintVertexCount],
 112389            out _,
 112390            out _,
 112391            out _,
 112392            out _,
 112393            out _);
 394    }
 395
 396    private static int GetNavigationClosure(
 397        VoxelGrid sourceGrid,
 398        in GridCellPrism source,
 399        in GridCellPrism target,
 400        Span<GridCellPrism> closure)
 401    {
 54402        Span<VoxelIndex> offsets = stackalloc VoxelIndex[8];
 54403        VoxelIndex targetOffset = default;
 54404        bool foundTarget = AreSameNavigationBodyPrism(source, target);
 504405        for (int slot = 0; !foundTarget && slot < sourceGrid.Topology.NeighborSlotCount; slot++)
 406        {
 199407            VoxelIndex offset = sourceGrid.Topology.GetNeighborOffset(slot);
 199408            if (!Vector3d.TryAdd(
 199409                    source.Center,
 199410                    sourceGrid.Topology.GetWorldOffset((offset.x, offset.y, offset.z)),
 199411                    out Vector3d center)
 199412                || !GridCellGeometry.TryCreatePrism(
 199413                    sourceGrid.Configuration.TopologyKind,
 199414                    sourceGrid.Configuration.TopologyMetrics,
 199415                    center,
 199416                    default,
 199417                    out GridCellPrism neighbor))
 418            {
 1419                return 0;
 420            }
 198421            if (AreSameNavigationBodyPrism(neighbor, target))
 422            {
 18423                targetOffset = offset;
 18424                foundTarget = true;
 425            }
 426        }
 53427        if (!foundTarget)
 1428            return 0;
 429
 430        int closureCount;
 52431        if (targetOffset == default)
 432        {
 34433            offsets[0] = default;
 34434            closureCount = 1;
 435        }
 18436        else if (sourceGrid.Configuration.TopologyKind == GridTopologyKind.RectangularPrism)
 437        {
 16438            RectangularDirection direction = RectangularDirectionUtility.GetDirectionFromOffset(
 16439                (targetOffset.x, targetOffset.y, targetOffset.z));
 16440            closureCount = RectangularDirectionUtility.CopyNavigationClosureOffsets(direction, offsets);
 441        }
 442        else
 443        {
 2444            closureCount = HexDirectionUtility.CopyNavigationClosureOffsets(targetOffset, offsets);
 445        }
 446
 304447        for (int i = 0; i < closureCount; i++)
 448        {
 100449            VoxelIndex offset = offsets[i];
 100450            bool usesTargetPlanarCoordinates = offset.x != 0 || offset.z != 0;
 100451            Vector3d center = sourceGrid.Configuration.TopologyKind == GridTopologyKind.RectangularPrism
 100452                ? new Vector3d(
 100453                    offset.x == 0 ? source.Center.X : target.Center.X,
 100454                    offset.y == 0 ? source.Center.Y : target.Center.Y,
 100455                    offset.z == 0 ? source.Center.Z : target.Center.Z)
 100456                : new Vector3d(
 100457                    usesTargetPlanarCoordinates ? target.Center.X : source.Center.X,
 100458                    offset.y == 0 ? source.Center.Y : target.Center.Y,
 100459                    usesTargetPlanarCoordinates ? target.Center.Z : source.Center.Z);
 460
 461            // Every coordinate comes from one of the two already validated endpoint prisms.
 100462            _ = GridCellGeometry.TryCreatePrism(
 100463                sourceGrid.Configuration.TopologyKind,
 100464                sourceGrid.Configuration.TopologyMetrics,
 100465                center,
 100466                default,
 100467                out closure[i]);
 468        }
 469
 52470        return closureCount;
 471    }
 472
 473    private static bool IsNavigationClosurePrism(
 474        in GridCellPrism prism,
 475        ReadOnlySpan<GridCellPrism> closure,
 476        int count)
 477    {
 1476478        for (int i = 0; i < count; i++)
 479        {
 581480            if (AreSameNavigationBodyPrism(prism, closure[i]))
 93481                return true;
 482        }
 483
 157484        return false;
 485    }
 486
 487    private static GridCoveredAddressRunStamp SnapshotNavigationBodyCandidates(
 488        GridWorld world,
 489        SwiftList<GridNavigationBodyTraceCandidate> candidates)
 490    {
 491        GridCoveredAddressRunStamp runStamp;
 39492        lock (world.ChangeSyncRoot)
 493        {
 39494            runStamp = new GridCoveredAddressRunStamp(
 39495                world.SpawnToken,
 39496                world.Version,
 39497                world.ChangeSequence);
 366498            for (int i = 0; i < candidates.Count; i++)
 499            {
 144500                GridNavigationBodyTraceCandidate candidate = candidates[i];
 144501                bool isPresent = candidate.Grid.StorageKind == GridStorageKind.Dense
 144502                    || candidate.Grid.TryGetVoxel(candidate.Index, out _);
 144503                candidates[i] = candidate.WithPhysicalEvidence(
 144504                    isPresent,
 144505                    candidate.Grid.LastChangeSequence);
 506            }
 39507        }
 508
 39509        return runStamp;
 510    }
 511
 512    private static bool TryCreateNavigationBodyBounds(
 513        Vector3d startFoot,
 514        Vector3d endFoot,
 515        Fixed64 startTop,
 516        Fixed64 endTop,
 517        Fixed64 radius,
 518        out Vector3d minimum,
 519        out Vector3d maximum)
 520    {
 67521        minimum = default;
 67522        maximum = default;
 67523        return Fixed64.TrySubtract(FixedMath.Min(startFoot.X, endFoot.X), radius, out Fixed64 minX)
 67524            && Fixed64.TrySubtract(FixedMath.Min(startFoot.Z, endFoot.Z), radius, out Fixed64 minZ)
 67525            && Fixed64.TryAdd(FixedMath.Max(startFoot.X, endFoot.X), radius, out Fixed64 maxX)
 67526            && Fixed64.TryAdd(FixedMath.Max(startFoot.Z, endFoot.Z), radius, out Fixed64 maxZ)
 67527            && AssignNavigationBodyBounds(
 67528                minX,
 67529                FixedMath.Min(startFoot.Y, endFoot.Y),
 67530                minZ,
 67531                maxX,
 67532                FixedMath.Max(startTop, endTop),
 67533                maxZ,
 67534                out minimum,
 67535                out maximum);
 536    }
 537
 538    private static bool AssignNavigationBodyBounds(
 539        Fixed64 minX,
 540        Fixed64 minY,
 541        Fixed64 minZ,
 542        Fixed64 maxX,
 543        Fixed64 maxY,
 544        Fixed64 maxZ,
 545        out Vector3d minimum,
 546        out Vector3d maximum)
 547    {
 62548        minimum = new Vector3d(minX, minY, minZ);
 62549        maximum = new Vector3d(maxX, maxY, maxZ);
 62550        return true;
 551    }
 552
 553    private static bool TryExpandNavigationBodyBounds(
 554        Vector3d minimum,
 555        Vector3d maximum,
 556        Fixed64 expansion,
 557        out Vector3d expandedMinimum,
 558        out Vector3d expandedMaximum)
 559    {
 52560        if (!Fixed64.TrySubtract(minimum.X, expansion, out Fixed64 minX)
 52561            || !Fixed64.TrySubtract(minimum.Y, expansion, out Fixed64 minY)
 52562            || !Fixed64.TrySubtract(minimum.Z, expansion, out Fixed64 minZ)
 52563            || !Fixed64.TryAdd(maximum.X, expansion, out Fixed64 maxX)
 52564            || !Fixed64.TryAdd(maximum.Y, expansion, out Fixed64 maxY)
 52565            || !Fixed64.TryAdd(maximum.Z, expansion, out Fixed64 maxZ))
 566        {
 7567            expandedMinimum = default;
 7568            expandedMaximum = default;
 7569            return false;
 570        }
 571
 45572        expandedMinimum = new Vector3d(minX, minY, minZ);
 45573        expandedMaximum = new Vector3d(maxX, maxY, maxZ);
 45574        return true;
 575    }
 576
 577    private static bool HasNavigationBodyUnionCoverage(
 578        VoxelGrid sourceGrid,
 579        VoxelIndex source,
 580        VoxelGrid targetGrid,
 581        VoxelIndex target,
 582        Vector3d startFoot,
 583        Vector3d endFoot,
 584        Fixed64 horizontalRadius,
 585        Fixed64 bodyHeight,
 586        SwiftList<GridNavigationBodyTraceCandidate> candidates,
 587        SwiftList<int> unionMembers)
 588    {
 39589        int sourceCandidate = FindNavigationBodyCandidate(candidates, sourceGrid, source);
 39590        int targetCandidate = FindNavigationBodyCandidate(candidates, targetGrid, target);
 591        // A connected body intersects a connected set of interiors in the source topology's
 592        // exact lattice. Closing every positive-overlap neighbor therefore proves containment;
 593        // exact coincident prisms let aligned adjacent grids continue the same lattice.
 39594        AddNavigationBodyUnionMember(candidates, unionMembers, sourceCandidate);
 39595        if (targetCandidate != sourceCandidate
 39596            && AreSameNavigationBodyPrism(
 39597                candidates[sourceCandidate].Prism,
 39598                candidates[targetCandidate].Prism))
 599        {
 2600            AddNavigationBodyUnionMember(candidates, unionMembers, targetCandidate);
 601        }
 344602        for (int memberOrdinal = 0; memberOrdinal < unionMembers.Count; memberOrdinal++)
 603        {
 135604            GridCellPrism member = candidates[unionMembers[memberOrdinal]].Prism;
 7100605            for (int slot = 0; slot < sourceGrid.Topology.NeighborSlotCount; slot++)
 606            {
 3417607                VoxelIndex offset = sourceGrid.Topology.GetNeighborOffset(slot);
 608                // Candidate bounds were expanded by the world's maximum topology edge, so every
 609                // immediate neighbor of a selected member is exactly representable here.
 3417610                _ = Vector3d.TryAdd(
 3417611                    member.Center,
 3417612                    sourceGrid.Topology.GetWorldOffset((offset.x, offset.y, offset.z)),
 3417613                    out Vector3d neighborCenter);
 3417614                _ = GridCellGeometry.TryCreatePrism(
 3417615                    sourceGrid.Configuration.TopologyKind,
 3417616                    sourceGrid.Configuration.TopologyMetrics,
 3417617                    neighborCenter,
 3417618                    default,
 3417619                    out GridCellPrism neighbor);
 620
 3417621                int matchingCandidate = FindBestMatchingNavigationBodyPrism(
 3417622                    candidates,
 3417623                    neighbor,
 3417624                    sourceCandidate,
 3417625                    targetCandidate);
 3417626                bool overlapsBody = matchingCandidate >= 0
 3417627                    ? candidates[matchingCandidate].HasPositiveOverlap
 3417628                    : GridCellGeometry.HasPositiveNavigationBodyPrismOverlap(
 3417629                        neighbor,
 3417630                        startFoot,
 3417631                        endFoot,
 3417632                        horizontalRadius,
 3417633                        bodyHeight);
 3417634                if (overlapsBody && matchingCandidate < 0)
 2635                    return false;
 3415636                if (matchingCandidate >= 0
 3415637                    && !candidates[matchingCandidate].IsVisited)
 638                {
 94639                    AddNavigationBodyUnionMember(candidates, unionMembers, matchingCandidate);
 640                }
 641            }
 642        }
 643
 37644        return true;
 645    }
 646
 647    private static int FindNavigationBodyCandidate(
 648        SwiftList<GridNavigationBodyTraceCandidate> candidates,
 649        VoxelGrid grid,
 650        VoxelIndex index)
 651    {
 181652        for (int i = 0;; i++)
 653        {
 181654            GridNavigationBodyTraceCandidate candidate = candidates[i];
 181655            if (candidate.Grid == grid && candidate.Index == index)
 78656                return i;
 657        }
 658    }
 659
 660    private static int FindBestMatchingNavigationBodyPrism(
 661        SwiftList<GridNavigationBodyTraceCandidate> candidates,
 662        in GridCellPrism prism,
 663        int sourceCandidate,
 664        int targetCandidate)
 665    {
 3417666        if (AreSameNavigationBodyPrism(candidates[sourceCandidate].Prism, prism))
 94667            return sourceCandidate;
 3323668        if (AreSameNavigationBodyPrism(candidates[targetCandidate].Prism, prism))
 46669            return targetCandidate;
 670
 3277671        if (!FindNavigationBodyPrismRange(candidates, prism, out int start, out int end))
 2977672            return -1;
 673
 300674        int best = start;
 630675        for (int i = start + 1; i < end; i++)
 676        {
 15677            if (IsPreferredNavigationBodyCandidate(candidates[i], candidates[best]))
 5678                best = i;
 679        }
 680
 300681        return best;
 682    }
 683
 684    private static bool IsPreferredNavigationBodyCandidate(
 685        GridNavigationBodyTraceCandidate candidate,
 686        GridNavigationBodyTraceCandidate current)
 687    {
 15688        if (candidate.IsPhysicallyPresent != current.IsPhysicallyPresent)
 5689            return candidate.IsPhysicallyPresent;
 690
 10691        return CompareGridIdentity(candidate.Grid, current.Grid) < 0;
 692    }
 693
 694    private static bool AreSameNavigationBodyPrism(
 695        in GridCellPrism first,
 7591696        in GridCellPrism second) => CompareNavigationBodyPrisms(first, second) == 0;
 697
 698    private static int CompareNavigationBodyPrisms(
 699        in GridCellPrism first,
 700        in GridCellPrism second)
 701    {
 19780702        int comparison = (int)first.TopologyKind - (int)second.TopologyKind;
 19780703        if (comparison != 0)
 42704            return comparison;
 19738705        comparison = first.Center.X.CompareTo(second.Center.X);
 19738706        if (comparison != 0)
 11828707            return comparison;
 7910708        comparison = first.Center.Y.CompareTo(second.Center.Y);
 7910709        if (comparison != 0)
 5118710            return comparison;
 2792711        comparison = first.Center.Z.CompareTo(second.Center.Z);
 2792712        if (comparison != 0)
 1848713            return comparison;
 944714        comparison = first.VerticalMin.CompareTo(second.VerticalMin);
 944715        if (comparison != 0)
 3716            return comparison;
 941717        comparison = first.PlanarInradius.CompareTo(second.PlanarInradius);
 941718        if (comparison != 0)
 3719            return comparison;
 720
 9516721        for (int i = 0; i < first.FootprintVertexCount; i++)
 722        {
 3826723            Vector2d firstVertex = first.GetFootprintVertex(i);
 3826724            Vector2d secondVertex = second.GetFootprintVertex(i);
 3826725            comparison = firstVertex.X.CompareTo(secondVertex.X);
 3826726            if (comparison != 0)
 3727                return comparison;
 3823728            comparison = firstVertex.Y.CompareTo(secondVertex.Y);
 3823729            if (comparison != 0)
 3730                return comparison;
 731        }
 732
 932733        return 0;
 734    }
 735
 736    private static bool FindNavigationBodyPrismRange(
 737        SwiftList<GridNavigationBodyTraceCandidate> candidates,
 738        in GridCellPrism prism,
 739        out int start,
 740        out int end)
 741    {
 3277742        int low = 0;
 3277743        int high = candidates.Count;
 12234744        while (low < high)
 745        {
 8957746            int middle = low + ((high - low) >> 1);
 8957747            if (CompareNavigationBodyPrisms(candidates[middle].Prism, prism) < 0)
 3605748                low = middle + 1;
 749            else
 5352750                high = middle;
 751        }
 752
 3277753        start = low;
 3277754        if (start >= candidates.Count
 3277755            || CompareNavigationBodyPrisms(candidates[start].Prism, prism) != 0)
 756        {
 2977757            end = start;
 2977758            return false;
 759        }
 760
 300761        low = start + 1;
 300762        high = candidates.Count;
 964763        while (low < high)
 764        {
 664765            int middle = low + ((high - low) >> 1);
 664766            if (CompareNavigationBodyPrisms(candidates[middle].Prism, prism) <= 0)
 15767                low = middle + 1;
 768            else
 649769                high = middle;
 770        }
 771
 300772        end = low;
 300773        return true;
 774    }
 775
 776    private static void AddNavigationBodyUnionMember(
 777        SwiftList<GridNavigationBodyTraceCandidate> candidates,
 778        SwiftList<int> unionMembers,
 779        int candidateIndex)
 780    {
 135781        candidates[candidateIndex] = candidates[candidateIndex].WithVisited();
 135782        unionMembers.Add(candidateIndex);
 135783    }
 784
 785    private static void AppendMissingNavigationBodyAlternativeEvidence(
 786        GridWorld world,
 787        SwiftList<GridNavigationBodyTraceCandidate> candidates,
 788        SwiftList<GridNavigationBodyTraceCell> results,
 789        VoxelGrid sourceGrid,
 790        VoxelIndex source,
 791        VoxelGrid targetGrid,
 792        VoxelIndex target)
 793    {
 59794        for (int start = 0; start < candidates.Count;)
 795        {
 39796            int end = GetNavigationBodyPrismGroupEnd(candidates, start);
 39797            if (!IsMissingNavigationBodyAlternativeGroup(
 39798                    candidates,
 39799                    start,
 39800                    end,
 39801                    sourceGrid,
 39802                    source,
 39803                    targetGrid,
 39804                    target))
 805            {
 33806                start = end;
 33807                continue;
 808            }
 809
 26810            for (int candidateIndex = start; candidateIndex < end; candidateIndex++)
 811            {
 7812                GridNavigationBodyTraceCandidate candidate = candidates[candidateIndex];
 7813                if (candidate.IsVisited)
 814                    continue;
 815
 1816                candidates[candidateIndex] = candidate.WithVisited();
 1817                results.Add(new GridNavigationBodyTraceCell(
 1818                    new WorldVoxelIndex(
 1819                        world.SpawnToken,
 1820                        candidate.Grid.GridIndex,
 1821                        candidate.Grid.SpawnToken,
 1822                        candidate.Index),
 1823                    candidate.Grid.Configuration.ToGridKey(),
 1824                    isPhysicallyPresent: false,
 1825                    candidate.GridLastChangeSequence,
 1826                    GridNavigationBodyTraceCellRole.PhysicalAlternativeDependency));
 827            }
 828
 6829            start = end;
 830        }
 10831    }
 832
 833    private static int CountMissingNavigationBodyAlternativeEvidence(
 834        SwiftList<GridNavigationBodyTraceCandidate> candidates,
 835        VoxelGrid sourceGrid,
 836        VoxelIndex source,
 837        VoxelGrid targetGrid,
 838        VoxelIndex target)
 839    {
 37840        int count = 0;
 210841        for (int start = 0; start < candidates.Count;)
 842        {
 136843            int end = GetNavigationBodyPrismGroupEnd(candidates, start);
 136844            if (IsMissingNavigationBodyAlternativeGroup(
 136845                    candidates,
 136846                    start,
 136847                    end,
 136848                    sourceGrid,
 136849                    source,
 136850                    targetGrid,
 136851                    target))
 852            {
 32853                for (int candidateIndex = start; candidateIndex < end; candidateIndex++)
 9854                    count += candidates[candidateIndex].IsVisited ? 0 : 1;
 855            }
 856
 136857            start = end;
 858        }
 859
 37860        return count;
 861    }
 862
 863    private static int GetNavigationBodyPrismGroupEnd(
 864        SwiftList<GridNavigationBodyTraceCandidate> candidates,
 865        int start)
 866    {
 175867        GridCellPrism prism = candidates[start].Prism;
 175868        int end = start + 1;
 184869        while (end < candidates.Count
 184870            && CompareNavigationBodyPrisms(candidates[end].Prism, prism) == 0)
 871        {
 9872            end++;
 873        }
 874
 175875        return end;
 876    }
 877
 878    private static bool IsMissingNavigationBodyAlternativeGroup(
 879        SwiftList<GridNavigationBodyTraceCandidate> candidates,
 880        int start,
 881        int end,
 882        VoxelGrid sourceGrid,
 883        VoxelIndex source,
 884        VoxelGrid targetGrid,
 885        VoxelIndex target)
 886    {
 175887        bool hasMissingSelectedNonEndpoint = false;
 392888        for (int candidateIndex = start; candidateIndex < end; candidateIndex++)
 889        {
 179890            GridNavigationBodyTraceCandidate candidate = candidates[candidateIndex];
 179891            if (candidate.IsPhysicallyPresent)
 158892                return false;
 21893            hasMissingSelectedNonEndpoint |= candidate.IsVisited
 21894                && !IsNavigationBodyEndpoint(
 21895                    candidate,
 21896                    sourceGrid,
 21897                    source,
 21898                    targetGrid,
 21899                    target);
 900        }
 901
 17902        return hasMissingSelectedNonEndpoint;
 903    }
 904
 905    private static bool IsNavigationBodyEndpoint(
 906        GridNavigationBodyTraceCandidate candidate,
 907        VoxelGrid sourceGrid,
 908        VoxelIndex source,
 909        VoxelGrid targetGrid,
 910        VoxelIndex target) =>
 17911        (candidate.Grid == sourceGrid && candidate.Index == source)
 17912        || (candidate.Grid == targetGrid && candidate.Index == target);
 913
 914    private static GridNavigationBodyTraceReport CreateNavigationBodyTraceReport(
 915        GridNavigationBodyTraceStatus status,
 916        int gridCandidateCount,
 917        int addressCandidateCount,
 918        SwiftList<GridNavigationBodyTraceCell> results,
 919        GridCoveredAddressRunStamp runStamp) =>
 74920        new(
 74921            status,
 74922            gridCandidateCount,
 74923            addressCandidateCount,
 74924            gridCandidateCount + (long)addressCandidateCount,
 74925            results.Count,
 74926            runStamp);
 927
 928    private static GridNavigationBodyTraceReport FailNavigationBodyTrace(
 929        SwiftList<GridNavigationBodyTraceCell> results,
 930        GridNavigationBodyTraceStatus status,
 931        int gridCandidateCount,
 932        int addressCandidateCount,
 933        GridCoveredAddressRunStamp runStamp)
 934    {
 27935        results.Clear();
 27936        return CreateNavigationBodyTraceReport(
 27937            status,
 27938            gridCandidateCount,
 27939            addressCandidateCount,
 27940            results,
 27941            runStamp);
 942    }
 943
 944    private readonly struct GridNavigationBodyTraceCandidateComparer :
 945        IComparer<GridNavigationBodyTraceCandidate>
 946    {
 947        public int Compare(
 948            GridNavigationBodyTraceCandidate first,
 949            GridNavigationBodyTraceCandidate second) =>
 108950            CompareNavigationBodyPrisms(first.Prism, second.Prism);
 951    }
 952
 953    private readonly struct GridNavigationBodyTraceCellComparer :
 954        IComparer<GridNavigationBodyTraceCell>
 955    {
 956        public int Compare(
 957            GridNavigationBodyTraceCell first,
 958            GridNavigationBodyTraceCell second) =>
 144959            CompareNavigationBodyTraceCells(first, second);
 960    }
 961
 962    private static int CompareNavigationBodyTraceCells(
 963        GridNavigationBodyTraceCell first,
 964        GridNavigationBodyTraceCell second)
 965    {
 144966        int comparison = CompareConfigurationKeys(first.ConfigurationKey, second.ConfigurationKey);
 144967        return comparison != 0
 144968            ? comparison
 144969            : first.Cell.VoxelIndex.CompareTo(second.Cell.VoxelIndex);
 970    }
 971}

/home/runner/work/GridForge/GridForge/src/GridForge/Utility/GridTracer.TraceIntervals.cs

#LineLine coverage
 1//=======================================================================
 2// GridTracer.TraceIntervals.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 System;
 9using System.Collections.Generic;
 10using FixedMathSharp;
 11using GridForge.Configuration;
 12using GridForge.Grids;
 13using GridForge.Grids.Storage;
 14using GridForge.Grids.Topology;
 15using GridForge.Spatial;
 16using SwiftCollections;
 17
 18namespace GridForge.Utility;
 19
 20/// <content>
 21/// Provides exact ordered segment intervals over physical and missing grid addresses.
 22/// </content>
 23public static partial class GridTracer
 24{
 25    /// <summary>
 26    /// Traces an arbitrary world-space segment into exact, canonically ordered grid-cell intervals.
 27    /// </summary>
 28    /// <remarks>
 29    /// Results are cleared on entry and on any ceiling or representability failure. Candidate grids are
 30    /// discovered through the world spatial index. Candidate addresses are bounded around the segment,
 31    /// then exact rectangular or hexagonal prisms reject all broad-phase false positives.
 32    /// </remarks>
 33    public static GridTraceIntervalReport TraceIntervalsInto(
 34        GridWorld world,
 35        Vector3d start,
 36        Vector3d end,
 37        SwiftList<GridTraceInterval> results,
 38        GridTraceIntervalScratch scratch,
 39        int gridCandidateLimit,
 40        int addressCandidateLimit,
 41        int outputLimit,
 42        long candidateWorkLimit)
 43    {
 8244        SwiftThrowHelper.ThrowIfNull(results, nameof(results));
 8245        SwiftThrowHelper.ThrowIfNull(scratch, nameof(scratch));
 8246        SwiftThrowHelper.ThrowIfNegative(gridCandidateLimit, nameof(gridCandidateLimit));
 8147        SwiftThrowHelper.ThrowIfNegative(addressCandidateLimit, nameof(addressCandidateLimit));
 8048        SwiftThrowHelper.ThrowIfNegative(outputLimit, nameof(outputLimit));
 7949        if (candidateWorkLimit < 0L)
 150            throw new ArgumentOutOfRangeException(nameof(candidateWorkLimit));
 51
 7852        results.Clear();
 7853        scratch.Clear();
 7854        if (world == null || !world.IsActive)
 255            return CreateTraceReport(GridTraceIntervalStatus.Complete, 0, 0, results);
 56
 7657        world.EnterReadLock();
 58        try
 59        {
 7660            (Vector3d queryMin, Vector3d queryMax) = CreatePaddedOrderedBounds(start, end, padding: null);
 7661            (Vector3d candidateMin, Vector3d candidateMax) =
 7662                ExpandOrderedBounds(queryMin, queryMax, world.MaxTopologyCellEdge);
 7663            bool candidateGridLimitIsTighter = candidateWorkLimit < gridCandidateLimit;
 7664            int effectiveGridLimit = candidateGridLimitIsTighter
 7665                ? (int)candidateWorkLimit
 7666                : gridCandidateLimit;
 7667            if (!world.CollectGridCandidates(
 7668                    candidateMin,
 7669                    candidateMax,
 7670                    scratch.CandidateGrids,
 7671                    effectiveGridLimit))
 72            {
 473                return FailTrace(
 474                    results,
 475                    candidateGridLimitIsTighter
 476                        ? GridTraceIntervalStatus.CandidateWorkLimitExceeded
 477                        : GridTraceIntervalStatus.GridCandidateLimitExceeded,
 478                    scratch.CandidateGrids.Count,
 479                    0);
 80            }
 81
 7282            SortGridIndices(world, scratch.CandidateGrids);
 83
 7284            long remainingCandidateWork = candidateWorkLimit - scratch.CandidateGrids.Count;
 7285            bool candidateAddressLimitIsTighter = remainingCandidateWork < addressCandidateLimit;
 7286            int effectiveAddressLimit = candidateAddressLimitIsTighter
 7287                ? (int)remainingCandidateWork
 7288                : addressCandidateLimit;
 7289            bool hasSparseGrid = false;
 39690            for (int gridCandidateIndex = 0; gridCandidateIndex < scratch.CandidateGrids.Count; gridCandidateIndex++)
 91            {
 12992                VoxelGrid grid = world.ActiveGrids[scratch.CandidateGrids[gridCandidateIndex]];
 12993                if (!grid.IsActive
 12994                    || !TryCollectSegmentCandidates(
 12995                        grid,
 12996                        queryMin,
 12997                        queryMax,
 12998                        scratch,
 12999                        effectiveAddressLimit))
 100                {
 3101                    return FailTrace(
 3102                        results,
 3103                        candidateAddressLimitIsTighter
 3104                            ? GridTraceIntervalStatus.CandidateWorkLimitExceeded
 3105                            : GridTraceIntervalStatus.AddressCandidateLimitExceeded,
 3106                        scratch.CandidateGrids.Count,
 3107                        scratch.AddressCandidates.Count);
 108                }
 109
 126110                hasSparseGrid |= grid.StorageKind == GridStorageKind.Sparse;
 111            }
 112
 69113            if (hasSparseGrid)
 1114                SnapshotSparsePresence(world, scratch.AddressCandidates);
 115
 788116            for (int addressIndex = 0; addressIndex < scratch.AddressCandidates.Count; addressIndex++)
 117            {
 327118                GridTraceAddressCandidate candidate = scratch.AddressCandidates[addressIndex];
 327119                VoxelGrid grid = candidate.Grid;
 327120                VoxelIndex index = candidate.Index;
 327121                WorldVoxelIndex cell = new WorldVoxelIndex(
 327122                    world.SpawnToken,
 327123                    grid.GridIndex,
 327124                    grid.SpawnToken,
 327125                    index);
 327126                if (!GridCellGeometry.TryCreatePrism(
 327127                        grid.Configuration.TopologyKind,
 327128                        grid.Configuration.TopologyMetrics,
 327129                        grid.GetWorldPosition(index),
 327130                        cell,
 327131                        out GridCellPrism prism))
 132                {
 1133                    return FailTrace(
 1134                        results,
 1135                        GridTraceIntervalStatus.UnrepresentableGeometry,
 1136                        scratch.CandidateGrids.Count,
 1137                        scratch.AddressCandidates.Count);
 138                }
 139
 326140                if (!TryGetPrismInterval(start, end, prism, out Fixed64 tEnter, out Fixed64 tExit))
 141                    continue;
 142
 206143                if (results.Count >= outputLimit)
 144                {
 1145                    return FailTrace(
 1146                        results,
 1147                        GridTraceIntervalStatus.OutputLimitExceeded,
 1148                        scratch.CandidateGrids.Count,
 1149                        scratch.AddressCandidates.Count);
 150                }
 151
 205152                results.Add(new GridTraceInterval(
 205153                    cell,
 205154                    grid.Configuration.ToGridKey(),
 205155                    candidate.IsPhysicallyPresent,
 205156                    grid.LastChangeSequence,
 205157                    tEnter,
 205158                    tExit));
 159            }
 160
 67161            SortIntervals(results);
 67162            return CreateTraceReport(
 67163                GridTraceIntervalStatus.Complete,
 67164                scratch.CandidateGrids.Count,
 67165                scratch.AddressCandidates.Count,
 67166                results);
 167        }
 168        finally
 169        {
 76170            world.ExitReadLock();
 76171            scratch.Clear();
 76172        }
 76173    }
 174
 175    private static bool TryCollectSegmentCandidates(
 176        VoxelGrid grid,
 177        Vector3d queryMin,
 178        Vector3d queryMax,
 179        GridTraceIntervalScratch scratch,
 180        int addressCandidateLimit)
 181    {
 129182        if (!TopologyVoxelRangeUtility.TryGetPrismCandidateRange(
 129183                grid,
 129184                queryMin,
 129185                queryMax,
 129186                out VoxelIndex minIndex,
 129187                out VoxelIndex maxIndex))
 188        {
 1189            return true;
 190        }
 191
 128192        bool isDense = grid.StorageKind == GridStorageKind.Dense;
 630193        for (int x = minIndex.x; x <= maxIndex.x; x++)
 194        {
 810195            for (int y = minIndex.y; y <= maxIndex.y; y++)
 196            {
 1114197                for (int z = minIndex.z; z <= maxIndex.z; z++)
 198                {
 342199                    if (scratch.AddressCandidates.Count >= addressCandidateLimit)
 3200                        return false;
 201
 339202                    scratch.AddressCandidates.Add(new GridTraceAddressCandidate(
 339203                        grid,
 339204                        new VoxelIndex(x, y, z),
 339205                        isDense));
 206                }
 207            }
 208        }
 209
 125210        return true;
 211    }
 212
 213    private static void SnapshotSparsePresence(
 214        GridWorld world,
 215        SwiftList<GridTraceAddressCandidate> candidates)
 216    {
 1217        lock (world.ChangeSyncRoot)
 218        {
 8219            for (int i = 0; i < candidates.Count; i++)
 220            {
 3221                GridTraceAddressCandidate candidate = candidates[i];
 3222                if (candidate.Grid.StorageKind == GridStorageKind.Sparse)
 223                {
 3224                    candidates[i] = candidate.WithPhysicalPresence(
 3225                        candidate.Grid.TryGetVoxel(candidate.Index, out _));
 226                }
 227            }
 1228        }
 1229    }
 230
 231    internal static bool TryGetPrismInterval(
 232        Vector3d start,
 233        Vector3d end,
 234        in GridCellPrism prism,
 235        out Fixed64 tEnter,
 236        out Fixed64 tExit)
 237    {
 471238        if (!GridCellGeometry.TryGetPlanarSegmentInterval(
 471239                prism,
 471240                new Vector2d(start.X, start.Z),
 471241                new Vector2d(end.X, end.Z),
 471242                out Fixed64 planarEnter,
 471243                out Fixed64 planarExit)
 471244            || !TryGetVerticalInterval(start.Y, end.Y, prism.VerticalMin, prism.VerticalMax,
 471245                out Fixed64 verticalEnter, out Fixed64 verticalExit))
 246        {
 171247            tEnter = default;
 171248            tExit = default;
 171249            return false;
 250        }
 251
 300252        tEnter = FixedMath.Max(planarEnter, verticalEnter);
 300253        tExit = FixedMath.Min(planarExit, verticalExit);
 300254        return tEnter <= tExit;
 255    }
 256
 257    private static bool TryGetVerticalInterval(
 258        Fixed64 start,
 259        Fixed64 end,
 260        Fixed64 verticalMin,
 261        Fixed64 verticalMax,
 262        out Fixed64 tEnter,
 263        out Fixed64 tExit)
 264    {
 305265        Fixed64 delta = end - start;
 305266        if (delta == Fixed64.Zero)
 267        {
 166268            tEnter = Fixed64.Zero;
 166269            tExit = Fixed64.One;
 166270            return start >= verticalMin && start <= verticalMax;
 271        }
 272
 139273        tEnter = (verticalMin - start) / delta;
 139274        tExit = (verticalMax - start) / delta;
 139275        if (tEnter > tExit)
 3276            (tEnter, tExit) = (tExit, tEnter);
 277
 139278        tEnter = FixedMath.Clamp(tEnter, Fixed64.Zero, Fixed64.One);
 139279        tExit = FixedMath.Clamp(tExit, Fixed64.Zero, Fixed64.One);
 139280        return FixedMath.Min(start, end) <= verticalMax
 139281            && FixedMath.Max(start, end) >= verticalMin;
 282    }
 283
 284    private static GridTraceIntervalReport CreateTraceReport(
 285        GridTraceIntervalStatus status,
 286        int gridCandidateCount,
 287        int candidateCount,
 288        SwiftList<GridTraceInterval> results)
 289    {
 69290        int tieGroupCount = AssignTieGroups(results);
 69291        return new GridTraceIntervalReport(
 69292            status,
 69293            gridCandidateCount,
 69294            candidateCount,
 69295            results.Count,
 69296            tieGroupCount,
 69297            HasContinuousCoverage(results, requirePhysical: false),
 69298            HasContinuousCoverage(results, requirePhysical: true));
 299    }
 300
 301    private static GridTraceIntervalReport FailTrace(
 302        SwiftList<GridTraceInterval> results,
 303        GridTraceIntervalStatus status,
 304        int gridCandidateCount,
 305        int candidateCount)
 306    {
 9307        results.Clear();
 9308        return new GridTraceIntervalReport(status, gridCandidateCount, candidateCount, 0, 0, false, false);
 309    }
 310
 311    private static int AssignTieGroups(SwiftList<GridTraceInterval> results)
 312    {
 69313        int groupId = -1;
 69314        int order = 0;
 69315        Fixed64 groupEnter = default;
 69316        Fixed64 groupExit = default;
 546317        for (int i = 0; i < results.Count; i++)
 318        {
 204319            GridTraceInterval interval = results[i];
 204320            bool pointPeer = i > 0
 204321                && groupEnter == groupExit
 204322                && interval.TEnter == groupEnter
 204323                && interval.TExit == groupExit;
 204324            bool overlapsInterior = i > 0
 204325                && groupExit > groupEnter
 204326                && interval.TExit > interval.TEnter
 204327                && interval.TEnter < groupExit;
 204328            if (i == 0 || (!overlapsInterior && !pointPeer))
 329            {
 115330                groupId++;
 115331                order = 0;
 115332                groupEnter = interval.TEnter;
 115333                groupExit = interval.TExit;
 334            }
 89335            else if (interval.TExit > groupExit)
 1336                groupExit = interval.TExit;
 337
 204338            results[i] = interval.WithTie(groupId, order++);
 339        }
 340
 69341        return groupId + 1;
 342    }
 343
 344    private static bool HasContinuousCoverage(
 345        SwiftList<GridTraceInterval> results,
 346        bool requirePhysical)
 347    {
 138348        Fixed64 coveredThrough = Fixed64.Zero;
 138349        bool started = false;
 544350        for (int i = 0; i < results.Count; i++)
 351        {
 250352            GridTraceInterval interval = results[i];
 250353            if (requirePhysical && !interval.IsPhysicallyPresent)
 354                continue;
 249355            if (!started)
 356            {
 120357                if (interval.TEnter > Fixed64.Zero)
 2358                    return false;
 118359                started = true;
 360            }
 129361            else if (interval.TEnter > coveredThrough)
 362            {
 1363                return false;
 364            }
 365
 246366            if (interval.TExit > coveredThrough)
 206367                coveredThrough = interval.TExit;
 246368            if (coveredThrough >= Fixed64.One)
 113369                return true;
 370        }
 371
 22372        return started && coveredThrough >= Fixed64.One;
 373    }
 374
 375    private static void SortGridIndices(GridWorld world, SwiftList<ushort> values) =>
 114376        values.SortInPlace(new GridIndexComparer(world));
 377
 378    private static void SortIntervals(SwiftList<GridTraceInterval> values)
 379    {
 67380        GridTraceInterval[] items = values.InnerArray;
 67381        int count = values.Count;
 306382        for (int root = (count >> 1) - 1; root >= 0; root--)
 86383            SiftIntervalsDown(items, root, count);
 384
 422385        for (int end = count - 1; end > 0; end--)
 386        {
 144387            (items[0], items[end]) = (items[end], items[0]);
 144388            SiftIntervalsDown(items, 0, end);
 389        }
 67390    }
 391
 392    private static void SiftIntervalsDown(GridTraceInterval[] items, int root, int count)
 393    {
 220394        while (true)
 395        {
 450396            int child = (root << 1) + 1;
 450397            if (child >= count)
 218398                return;
 232399            int right = child + 1;
 232400            if (right < count && CompareIntervals(items[child], items[right]) < 0)
 84401                child = right;
 232402            if (CompareIntervals(items[root], items[child]) >= 0)
 12403                return;
 404
 220405            (items[root], items[child]) = (items[child], items[root]);
 220406            root = child;
 407        }
 408    }
 409
 410    private static int CompareIntervals(GridTraceInterval first, GridTraceInterval second)
 411    {
 385412        int comparison = first.TEnter.CompareTo(second.TEnter);
 385413        if (comparison != 0)
 243414            return comparison;
 142415        comparison = second.TExit.CompareTo(first.TExit);
 142416        if (comparison != 0)
 18417            return comparison;
 124418        comparison = CompareConfigurationKeys(first.ConfigurationKey, second.ConfigurationKey);
 124419        if (comparison != 0)
 92420            return comparison;
 32421        return first.Cell.VoxelIndex.CompareTo(second.Cell.VoxelIndex);
 422    }
 423
 424    private static int CompareGridIdentity(VoxelGrid first, VoxelGrid second)
 425    {
 112426        return CompareConfigurationKeys(
 112427            first.Configuration.ToGridKey(),
 112428            second.Configuration.ToGridKey());
 429    }
 430
 431    private readonly struct GridIndexComparer : IComparer<ushort>
 432    {
 433        private readonly GridWorld _world;
 434
 114435        internal GridIndexComparer(GridWorld world) => _world = world;
 436
 437        public int Compare(ushort first, ushort second) =>
 102438            CompareGridIdentity(_world.ActiveGrids[first], _world.ActiveGrids[second]);
 439    }
 440
 441    private static int CompareConfigurationKeys(
 442        GridConfigurationKey first,
 443        GridConfigurationKey second)
 444    {
 380445        int comparison = CompareVectors(first.BoundsMin, second.BoundsMin);
 380446        if (comparison != 0)
 63447            return comparison;
 317448        comparison = CompareVectors(first.BoundsMax, second.BoundsMax);
 317449        if (comparison != 0)
 34450            return comparison;
 283451        comparison = ((int)first.TopologyKind).CompareTo((int)second.TopologyKind);
 283452        if (comparison != 0)
 73453            return comparison;
 454
 210455        GridTopologyMetrics firstMetrics = first.TopologyMetrics;
 210456        GridTopologyMetrics secondMetrics = second.TopologyMetrics;
 210457        comparison = firstMetrics.CellRadius.CompareTo(secondMetrics.CellRadius);
 210458        if (comparison != 0)
 4459            return comparison;
 206460        comparison = firstMetrics.CellWidth.CompareTo(secondMetrics.CellWidth);
 206461        if (comparison != 0)
 7462            return comparison;
 199463        comparison = firstMetrics.LayerHeight.CompareTo(secondMetrics.LayerHeight);
 199464        if (comparison != 0)
 5465            return comparison;
 194466        comparison = firstMetrics.CellLength.CompareTo(secondMetrics.CellLength);
 194467        return comparison != 0
 194468            ? comparison
 194469            : ((int)firstMetrics.HexOrientation).CompareTo((int)secondMetrics.HexOrientation);
 470    }
 471
 472    private static int CompareVectors(Vector3d first, Vector3d second)
 473    {
 697474        int comparison = first.X.CompareTo(second.X);
 697475        if (comparison != 0)
 73476            return comparison;
 624477        comparison = first.Y.CompareTo(second.Y);
 624478        return comparison != 0 ? comparison : first.Z.CompareTo(second.Z);
 479    }
 480}

/home/runner/work/GridForge/GridForge/src/GridForge/Utility/GridTracer.TraceLine.cs

#LineLine coverage
 1//=======================================================================
 2// GridTracer.TraceLine.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 System.Collections.Generic;
 9using System.Runtime.CompilerServices;
 10using FixedMathSharp;
 11using GridForge.Grids;
 12using GridForge.Grids.Topology;
 13using GridForge.Spatial;
 14using SwiftCollections;
 15using SwiftCollections.Pool;
 16
 17namespace GridForge.Utility;
 18
 19/// <content>
 20/// Provides line-tracing functionality for identifying voxels intersected
 21/// along a segment between two points across one or more grids.
 22/// </content>
 23public static partial class GridTracer
 24{
 25    private static IEnumerable<GridVoxelSet> TraceLineIterator(
 26        GridWorld world,
 27        Vector3d start,
 28        Vector3d end,
 29        Fixed64? padding,
 30        bool includeEnd)
 31    {
 4032        SwiftList<GridVoxelSet> gridVoxelSets = SwiftListPool<GridVoxelSet>.Shared.Rent();
 4033        SwiftHashSet<Voxel> voxelRedundancyCheck = SwiftHashSetPool<Voxel>.Shared.Rent();
 4034        SwiftList<ushort> candidateGrids = SwiftListPool<ushort>.Shared.Rent();
 35
 36        try
 37        {
 4038            AddTraceLineVoxelsToMapping(
 4039                world,
 4040                start,
 4041                end,
 4042                padding,
 4043                includeEnd,
 4044                gridVoxelSets,
 4045                voxelRedundancyCheck,
 4046                candidateGrids);
 47
 18448            foreach (GridVoxelSet gridVoxelSet in gridVoxelSets)
 5249                yield return gridVoxelSet;
 4050        }
 51        finally
 52        {
 4053            ReleaseGridVoxelSets(gridVoxelSets);
 4054            SwiftHashSetPool<Voxel>.Shared.Release(voxelRedundancyCheck);
 4055            SwiftListPool<ushort>.Shared.Release(candidateGrids);
 4056        }
 4057    }
 58
 59    private static void AddTraceLineVoxelsToMapping(
 60        GridWorld world,
 61        Vector3d start,
 62        Vector3d end,
 63        Fixed64? padding,
 64        bool includeEnd,
 65        SwiftList<GridVoxelSet> gridVoxelSets,
 66        SwiftHashSet<Voxel> voxelRedundancyCheck,
 67        SwiftList<ushort> candidateGrids)
 68    {
 4069        (Vector3d queryMin, Vector3d queryMax) = CreatePaddedOrderedBounds(start, end, padding);
 4070        (Vector3d candidateMin, Vector3d candidateMax) =
 4071            ExpandOrderedBounds(queryMin, queryMax, world.MaxTopologyCellEdge);
 72
 4073        _ = world.CollectGridCandidates(
 4074            candidateMin,
 4075            candidateMax,
 4076            candidateGrids,
 4077            GridWorld.MaxGrids);
 19678        foreach (ushort gridIndex in candidateGrids)
 79        {
 5880            AddTraceLineVoxelsForGrid(
 5881                world.ActiveGrids[gridIndex],
 5882                start,
 5883                end,
 5884                padding,
 5885                includeEnd,
 5886                gridVoxelSets,
 5887                voxelRedundancyCheck);
 88        }
 4089    }
 90
 91    private static void AddTraceLineVoxelsTo(
 92        GridWorld world,
 93        Vector3d start,
 94        Vector3d end,
 95        Fixed64? padding,
 96        bool includeEnd,
 97        SwiftList<Voxel> voxels,
 98        SwiftHashSet<Voxel> voxelRedundancyCheck,
 99        SwiftList<ushort> candidateGrids)
 100    {
 10101        (Vector3d queryMin, Vector3d queryMax) = CreatePaddedOrderedBounds(start, end, padding);
 10102        (Vector3d candidateMin, Vector3d candidateMax) =
 10103            ExpandOrderedBounds(queryMin, queryMax, world.MaxTopologyCellEdge);
 104
 10105        _ = world.CollectGridCandidates(
 10106            candidateMin,
 10107            candidateMax,
 10108            candidateGrids,
 10109            GridWorld.MaxGrids);
 74110        foreach (ushort gridIndex in candidateGrids)
 111        {
 27112            AddTraceLineVoxelsForGrid(
 27113                world.ActiveGrids[gridIndex],
 27114                start,
 27115                end,
 27116                padding,
 27117                includeEnd,
 27118                voxels,
 27119                voxelRedundancyCheck);
 120        }
 10121    }
 122
 123    private static TraceLinePlan CreateTraceLinePlan(
 124        VoxelGrid grid,
 125        Vector3d start,
 126        Vector3d end,
 127        Fixed64? padding)
 128    {
 70129        (Vector3d snappedMin, Vector3d snappedMax) =
 70130            grid.NormalizeBounds(start, end, padding);
 131
 70132        Vector3d traceStart = CreateTraceEndpoint(start, end, snappedMin, snappedMax, useMinWhenIncreasing: true);
 70133        Vector3d traceEnd = CreateTraceEndpoint(start, end, snappedMin, snappedMax, useMinWhenIncreasing: false);
 134
 70135        Vector3d diff = traceEnd - traceStart;
 70136        Fixed64 steps = CalculateTraceSteps(grid, diff);
 137
 70138        return new TraceLinePlan(
 70139            traceStart,
 70140            steps,
 70141            diff.X / (steps + Fixed64.One),
 70142            diff.Y / (steps + Fixed64.One),
 70143            diff.Z / (steps + Fixed64.One));
 144    }
 145
 146    private static Fixed64 CalculateTraceSteps(VoxelGrid grid, Vector3d diff)
 147    {
 70148        Vector3d delta = Vector3d.Abs(diff);
 70149        Fixed64 stepX = delta.X / grid.Topology.Metrics.CellWidth;
 70150        Fixed64 stepY = delta.Y / grid.Topology.Metrics.LayerHeight;
 70151        Fixed64 stepZ = delta.Z / grid.Topology.Metrics.CellLength;
 70152        return FixedMath.Ceil(FixedMath.Max(FixedMath.Max(stepX, stepY), stepZ));
 153    }
 154
 155    private static Vector3d CreateTraceEndpoint(
 156        Vector3d start,
 157        Vector3d end,
 158        Vector3d snappedMin,
 159        Vector3d snappedMax,
 160        bool useMinWhenIncreasing)
 161    {
 162        // Preserve the caller's trace direction while still using snapped bounds for coverage lookup.
 158163        return new Vector3d(
 158164            SelectTraceCoordinate(start.X, end.X, snappedMin.X, snappedMax.X, useMinWhenIncreasing),
 158165            SelectTraceCoordinate(start.Y, end.Y, snappedMin.Y, snappedMax.Y, useMinWhenIncreasing),
 158166            SelectTraceCoordinate(start.Z, end.Z, snappedMin.Z, snappedMax.Z, useMinWhenIncreasing));
 167    }
 168
 169    private static Fixed64 SelectTraceCoordinate(
 170        Fixed64 start,
 171        Fixed64 end,
 172        Fixed64 snappedMin,
 173        Fixed64 snappedMax,
 174        bool useMinWhenIncreasing)
 175    {
 474176        return (start <= end) == useMinWhenIncreasing ? snappedMin : snappedMax;
 177    }
 178
 179    private static (Vector3d min, Vector3d max) CreatePaddedOrderedBounds(
 180        Vector3d min,
 181        Vector3d max,
 182        Fixed64? padding)
 183    {
 912184        Fixed64 fixedPadding = padding.HasValue && padding.Value > Fixed64.Zero
 912185            ? padding.Value
 912186            : Fixed64.Zero;
 187
 912188        min -= fixedPadding;
 912189        max += fixedPadding;
 190
 912191        (min.X, max.X) = min.X > max.X ? (max.X, min.X) : (min.X, max.X);
 912192        (min.Y, max.Y) = min.Y > max.Y ? (max.Y, min.Y) : (min.Y, max.Y);
 912193        (min.Z, max.Z) = min.Z > max.Z ? (max.Z, min.Z) : (min.Z, max.Z);
 194
 912195        return (min, max);
 196    }
 197
 198    private static (Vector3d min, Vector3d max) ExpandOrderedBounds(
 199        Vector3d min,
 200        Vector3d max,
 201        Fixed64 expansion)
 202    {
 912203        if (expansion <= Fixed64.Zero)
 6204            return (min, max);
 205
 906206        return (
 906207            new Vector3d(min.X - expansion, min.Y - expansion, min.Z - expansion),
 906208            new Vector3d(max.X + expansion, max.Y + expansion, max.Z + expansion));
 209    }
 210
 211    private static bool TryGetCoveredScanCellRange(
 212        VoxelGrid grid,
 213        Vector3d queryMin,
 214        Vector3d queryMax,
 215        out int xMin,
 216        out int yMin,
 217        out int zMin,
 218        out int xMax,
 219        out int yMax,
 220        out int zMax)
 221    {
 592222        xMin = 0;
 592223        yMin = 0;
 592224        zMin = 0;
 592225        xMax = 0;
 592226        yMax = 0;
 592227        zMax = 0;
 228
 592229        (Vector3d snappedMin, Vector3d snappedMax) = grid.NormalizeBounds(queryMin, queryMax);
 592230        if (!TopologyVoxelRangeUtility.TryClipBoundsToGrid(grid, snappedMin, snappedMax, out Vector3d clippedMin, out Ve
 1231            return false;
 232
 591233        (xMin, yMin, zMin) = grid.SnapToScanCell(clippedMin);
 591234        (xMax, yMax, zMax) = grid.SnapToScanCell(clippedMax);
 591235        return true;
 236    }
 237
 238    private static void AddTraceLineVoxelsForGrid(
 239        VoxelGrid currentGrid,
 240        Vector3d start,
 241        Vector3d end,
 242        Fixed64? padding,
 243        bool includeEnd,
 244        SwiftList<GridVoxelSet> gridVoxelSets,
 245        SwiftHashSet<Voxel> voxelRedundancyCheck)
 246    {
 58247        if (!TryClipTraceSegmentToGrid(
 58248            currentGrid,
 58249            start,
 58250            end,
 58251            padding,
 58252            out Vector3d traceStart,
 58253            out Vector3d traceEnd,
 58254            out bool segmentEndsBeforeGlobalEnd))
 255        {
 5256            return;
 257        }
 258
 53259        SwiftList<Voxel> voxelList = SwiftListPool<Voxel>.Shared.Rent();
 53260        AddTraceLineGridVoxels(
 53261            currentGrid,
 53262            traceStart,
 53263            traceEnd,
 53264            padding,
 53265            includeEnd || segmentEndsBeforeGlobalEnd,
 53266            voxelList,
 53267            voxelRedundancyCheck);
 268
 53269        if (voxelList.Count > 0)
 52270            gridVoxelSets.Add(new GridVoxelSet(currentGrid, voxelList));
 271        else
 1272            SwiftListPool<Voxel>.Shared.Release(voxelList);
 1273    }
 274
 275    private static void AddTraceLineVoxelsForGrid(
 276        VoxelGrid currentGrid,
 277        Vector3d start,
 278        Vector3d end,
 279        Fixed64? padding,
 280        bool includeEnd,
 281        SwiftList<Voxel> voxels,
 282        SwiftHashSet<Voxel> voxelRedundancyCheck)
 283    {
 27284        if (!TryClipTraceSegmentToGrid(
 27285            currentGrid,
 27286            start,
 27287            end,
 27288            padding,
 27289            out Vector3d traceStart,
 27290            out Vector3d traceEnd,
 27291            out bool segmentEndsBeforeGlobalEnd))
 292        {
 1293            return;
 294        }
 295
 26296        AddTraceLineGridVoxels(
 26297            currentGrid,
 26298            traceStart,
 26299            traceEnd,
 26300            padding,
 26301            includeEnd || segmentEndsBeforeGlobalEnd,
 26302            voxels,
 26303            voxelRedundancyCheck);
 26304    }
 305
 306    private static void AddTraceLineGridVoxels(
 307        VoxelGrid currentGrid,
 308        Vector3d start,
 309        Vector3d end,
 310        Fixed64? padding,
 311        bool includeEnd,
 312        SwiftList<Voxel> voxelList,
 313        SwiftHashSet<Voxel> voxelRedundancyCheck)
 314    {
 79315        if (currentGrid.Topology.Kind == GridTopologyKind.HexPrism)
 316        {
 9317            AddHexTraceLineGridVoxels(
 9318                currentGrid,
 9319                start,
 9320                end,
 9321                padding,
 9322                includeEnd,
 9323                voxelList,
 9324                voxelRedundancyCheck);
 9325            return;
 326        }
 327
 70328        TraceLinePlan plan = CreateTraceLinePlan(currentGrid, start, end, padding);
 329
 730330        for (Fixed64 i = Fixed64.Zero; i <= plan.Steps; i += Fixed64.One)
 331        {
 295332            Vector3d tracePos = currentGrid.FloorToGrid(
 295333                new Vector3d(
 295334                    plan.TraceStart.X + plan.StepX * i,
 295335                    plan.TraceStart.Y + plan.StepY * i,
 295336                    plan.TraceStart.Z + plan.StepZ * i));
 337
 295338            if (!currentGrid.TryGetVoxel(tracePos, out Voxel? voxel) || voxelRedundancyCheck.Add(voxel!) != true)
 339                continue;
 340
 256341            voxelList.Add(voxel!);
 342        }
 343
 70344        if (includeEnd)
 66345            AddTraceVoxelByPosition(currentGrid, end, voxelList, voxelRedundancyCheck);
 70346    }
 347
 348    private static void AddHexTraceLineGridVoxels(
 349        VoxelGrid currentGrid,
 350        Vector3d start,
 351        Vector3d end,
 352        Fixed64? padding,
 353        bool includeEnd,
 354        SwiftList<Voxel> voxelList,
 355        SwiftHashSet<Voxel> voxelRedundancyCheck)
 356    {
 9357        CreateHexTraceEndpoints(
 9358            currentGrid,
 9359            start,
 9360            end,
 9361            padding,
 9362            out VoxelIndex startIndex,
 9363            out VoxelIndex endIndex);
 364
 9365        int steps = CalculateHexTraceSteps(startIndex, endIndex);
 9366        if (steps == 0)
 367        {
 1368            AddTraceVoxelByIndex(currentGrid, startIndex, voxelList, voxelRedundancyCheck);
 1369            return;
 370        }
 371
 8372        bool includeEndIndex = ShouldIncludeHexTraceEndIndex(currentGrid, end, endIndex, includeEnd);
 8373        int finalStep = includeEndIndex ? steps : steps - 1;
 8374        Fixed64 stepCount = new Fixed64(steps);
 82375        for (int i = 0; i <= finalStep; i++)
 376        {
 33377            Fixed64 t = new Fixed64(i) / stepCount;
 33378            VoxelIndex traceIndex = InterpolateHexTraceIndex(startIndex, endIndex, t);
 33379            AddTraceVoxelByIndex(currentGrid, traceIndex, voxelList, voxelRedundancyCheck);
 380        }
 8381    }
 382
 383    private static void CreateHexTraceEndpoints(
 384        VoxelGrid grid,
 385        Vector3d start,
 386        Vector3d end,
 387        Fixed64? padding,
 388        out VoxelIndex startIndex,
 389        out VoxelIndex endIndex)
 390    {
 9391        (Vector3d snappedMin, Vector3d snappedMax) = grid.NormalizeBounds(start, end, padding);
 9392        Vector3d traceStart = grid.FloorToGrid(CreateTraceEndpoint(
 9393            start,
 9394            end,
 9395            snappedMin,
 9396            snappedMax,
 9397            useMinWhenIncreasing: true));
 9398        Vector3d traceEnd = grid.FloorToGrid(CreateTraceEndpoint(
 9399            start,
 9400            end,
 9401            snappedMin,
 9402            snappedMax,
 9403            useMinWhenIncreasing: false));
 404
 9405        grid.TryGetVoxelIndex(traceStart, out startIndex);
 9406        grid.TryGetVoxelIndex(traceEnd, out endIndex);
 9407    }
 408
 409    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 410    private static int CalculateHexTraceSteps(VoxelIndex start, VoxelIndex end)
 411    {
 9412        int qDelta = System.Math.Abs(end.x - start.x);
 9413        int rDelta = System.Math.Abs(end.z - start.z);
 9414        int sDelta = System.Math.Abs((-end.x - end.z) - (-start.x - start.z));
 9415        int planarSteps = System.Math.Max(qDelta, System.Math.Max(rDelta, sDelta));
 9416        int verticalSteps = System.Math.Abs(end.y - start.y);
 9417        return System.Math.Max(planarSteps, verticalSteps);
 418    }
 419
 420    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 421    private static VoxelIndex InterpolateHexTraceIndex(VoxelIndex start, VoxelIndex end, Fixed64 t)
 422    {
 33423        Fixed64 q = Interpolate(new Fixed64(start.x), new Fixed64(end.x), t);
 33424        Fixed64 y = Interpolate(new Fixed64(start.y), new Fixed64(end.y), t);
 33425        Fixed64 r = Interpolate(new Fixed64(start.z), new Fixed64(end.z), t);
 33426        return HexCoordinateUtility.RoundAxial(q, y, r);
 427    }
 428
 429    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 430    private static Fixed64 Interpolate(Fixed64 start, Fixed64 end, Fixed64 t) =>
 99431        start + (end - start) * t;
 432
 433    private static bool TryClipTraceSegmentToGrid(
 434        VoxelGrid grid,
 435        Vector3d start,
 436        Vector3d end,
 437        Fixed64? padding,
 438        out Vector3d clippedStart,
 439        out Vector3d clippedEnd,
 440        out bool segmentEndsBeforeGlobalEnd)
 441    {
 85442        clippedStart = default;
 85443        clippedEnd = default;
 85444        segmentEndsBeforeGlobalEnd = false;
 445
 85446        Fixed64 fixedPadding = padding.HasValue && padding.Value > Fixed64.Zero
 85447            ? padding.Value
 85448            : Fixed64.Zero;
 85449        Vector3d boundsMin = grid.BoundsMin - fixedPadding;
 85450        Vector3d boundsMax = grid.BoundsMax + fixedPadding;
 85451        Fixed64 tMin = Fixed64.Zero;
 85452        Fixed64 tMax = Fixed64.One;
 453
 85454        if (!(ClipTraceSegmentAxis(start.X, end.X, boundsMin.X, boundsMax.X, ref tMin, ref tMax)
 85455            && ClipTraceSegmentAxis(start.Y, end.Y, boundsMin.Y, boundsMax.Y, ref tMin, ref tMax)
 85456            && ClipTraceSegmentAxis(start.Z, end.Z, boundsMin.Z, boundsMax.Z, ref tMin, ref tMax)))
 457        {
 6458            return false;
 459        }
 460
 79461        clippedStart = InterpolateTraceSegment(start, end, boundsMin, boundsMax, tMin);
 79462        clippedEnd = InterpolateTraceSegment(start, end, boundsMin, boundsMax, tMax);
 79463        segmentEndsBeforeGlobalEnd = tMax < Fixed64.One;
 79464        return true;
 465    }
 466
 467    private static bool ClipTraceSegmentAxis(
 468        Fixed64 start,
 469        Fixed64 end,
 470        Fixed64 boundsMin,
 471        Fixed64 boundsMax,
 472        ref Fixed64 tMin,
 473        ref Fixed64 tMax)
 474    {
 249475        Fixed64 delta = end - start;
 249476        if (delta == Fixed64.Zero)
 167477            return start >= boundsMin && start <= boundsMax;
 478
 82479        Fixed64 axisMin = (boundsMin - start) / delta;
 82480        Fixed64 axisMax = (boundsMax - start) / delta;
 82481        if (axisMin > axisMax)
 5482            (axisMin, axisMax) = (axisMax, axisMin);
 483
 82484        if (axisMin > tMin)
 13485            tMin = axisMin;
 82486        if (axisMax < tMax)
 14487            tMax = axisMax;
 488
 82489        return tMin <= tMax;
 490    }
 491
 492    private static bool ShouldIncludeHexTraceEndIndex(
 493        VoxelGrid grid,
 494        Vector3d end,
 495        VoxelIndex endIndex,
 496        bool includeEnd)
 497    {
 8498        if (includeEnd)
 6499            return true;
 500
 2501        return !grid.TryGetVoxelIndex(end, out VoxelIndex actualEndIndex)
 2502            || actualEndIndex != endIndex;
 503    }
 504
 505    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 506    private static Vector3d InterpolateTraceSegment(
 507        Vector3d start,
 508        Vector3d end,
 509        Vector3d boundsMin,
 510        Vector3d boundsMax,
 511        Fixed64 t) =>
 158512        new(
 158513            InterpolateTraceAxis(start.X, end.X, boundsMin.X, boundsMax.X, t),
 158514            InterpolateTraceAxis(start.Y, end.Y, boundsMin.Y, boundsMax.Y, t),
 158515            InterpolateTraceAxis(start.Z, end.Z, boundsMin.Z, boundsMax.Z, t));
 516
 517    private static Fixed64 InterpolateTraceAxis(
 518        Fixed64 start,
 519        Fixed64 end,
 520        Fixed64 boundsMin,
 521        Fixed64 boundsMax,
 522        Fixed64 t)
 523    {
 474524        Fixed64 delta = end - start;
 474525        if (delta == Fixed64.Zero)
 332526            return start;
 527
 142528        if ((boundsMin - start) / delta == t)
 32529            return boundsMin;
 110530        if ((boundsMax - start) / delta == t)
 27531            return boundsMax;
 532
 83533        return start + delta * t;
 534    }
 535
 536    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 537    private static void AddTraceVoxelByPosition(
 538        VoxelGrid grid,
 539        Vector3d position,
 540        SwiftList<Voxel> voxelList,
 541        SwiftHashSet<Voxel> voxelRedundancyCheck)
 542    {
 66543        if (grid.TryGetVoxel(grid.FloorToGrid(position), out Voxel? voxel)
 66544            && voxelRedundancyCheck.Add(voxel!))
 545        {
 22546            voxelList.Add(voxel!);
 547        }
 66548    }
 549
 550    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 551    private static void AddTraceVoxelByIndex(
 552        VoxelGrid grid,
 553        VoxelIndex index,
 554        SwiftList<Voxel> voxelList,
 555        SwiftHashSet<Voxel> voxelRedundancyCheck)
 556    {
 37557        if (grid.TryGetVoxel(index, out Voxel? voxel)
 37558            && voxelRedundancyCheck.Add(voxel!))
 559        {
 33560            voxelList.Add(voxel!);
 561        }
 37562    }
 563
 564    private static void ReleaseGridVoxelSets(SwiftList<GridVoxelSet> gridVoxelSets)
 565    {
 1018566        foreach (GridVoxelSet gridVoxelSet in gridVoxelSets)
 267567            SwiftListPool<Voxel>.Shared.Release(gridVoxelSet.Voxels);
 568
 242569        SwiftListPool<GridVoxelSet>.Shared.Release(gridVoxelSets);
 242570    }
 571}
Generated by: ReportGenerator 5.5.11.0
08/28/2026 - 03:09:44
GitHub | reportgenerator.io

Methods/Properties

.ctor(FixedMathSharp.Vector3d,FixedMathSharp.Fixed64,FixedMathSharp.Fixed64,FixedMathSharp.Fixed64,FixedMathSharp.Fixed64)
TraceLine(GridForge.Grids.GridWorld,FixedMathSharp.Vector3d,FixedMathSharp.Vector3d,System.Nullable`1<FixedMathSharp.Fixed64>,System.Boolean)
TraceLineInto(GridForge.Grids.GridWorld,FixedMathSharp.Vector3d,FixedMathSharp.Vector3d,SwiftCollections.SwiftList`1<GridForge.Grids.Voxel>,System.Nullable`1<FixedMathSharp.Fixed64>,System.Boolean)
TraceLineInto(GridForge.Grids.GridWorld,FixedMathSharp.Vector3d,FixedMathSharp.Vector3d,SwiftCollections.SwiftList`1<GridForge.Grids.Voxel>,GridForge.Grids.GridTraceScratch,System.Nullable`1<FixedMathSharp.Fixed64>,System.Boolean)
TraceLine(GridForge.Grids.GridWorld,FixedMathSharp.Vector2d,FixedMathSharp.Vector2d,System.Nullable`1<FixedMathSharp.Fixed64>,System.Boolean,FixedMathSharp.Fixed64)
TraceLineInto(GridForge.Grids.GridWorld,FixedMathSharp.Vector2d,FixedMathSharp.Vector2d,SwiftCollections.SwiftList`1<GridForge.Grids.Voxel>,System.Nullable`1<FixedMathSharp.Fixed64>,System.Boolean,FixedMathSharp.Fixed64)
TraceLineInto(GridForge.Grids.GridWorld,FixedMathSharp.Vector2d,FixedMathSharp.Vector2d,SwiftCollections.SwiftList`1<GridForge.Grids.Voxel>,GridForge.Grids.GridTraceScratch,System.Nullable`1<FixedMathSharp.Fixed64>,System.Boolean,FixedMathSharp.Fixed64)
GetCoveredVoxels(GridForge.Grids.GridWorld,FixedMathSharp.Vector3d,FixedMathSharp.Vector3d,System.Nullable`1<FixedMathSharp.Fixed64>)
GetCoveredVoxels(GridForge.Grids.GridWorld,FixedMathSharp.Vector2d,FixedMathSharp.Vector2d,FixedMathSharp.Fixed64,System.Nullable`1<FixedMathSharp.Fixed64>)
GetCoveredVoxels(GridForge.Grids.GridWorld,FixedMathSharp.Geometry.FixedBoundArea,FixedMathSharp.Fixed64,System.Nullable`1<FixedMathSharp.Fixed64>)
GetCoveredVoxelsInto(GridForge.Grids.GridWorld,FixedMathSharp.Vector3d,FixedMathSharp.Vector3d,SwiftCollections.SwiftList`1<GridForge.Grids.Voxel>,System.Nullable`1<FixedMathSharp.Fixed64>)
GetCoveredVoxelsInto(GridForge.Grids.GridWorld,FixedMathSharp.Vector2d,FixedMathSharp.Vector2d,SwiftCollections.SwiftList`1<GridForge.Grids.Voxel>,FixedMathSharp.Fixed64,System.Nullable`1<FixedMathSharp.Fixed64>)
GetCoveredVoxelsInto(GridForge.Grids.GridWorld,FixedMathSharp.Geometry.FixedBoundArea,SwiftCollections.SwiftList`1<GridForge.Grids.Voxel>,FixedMathSharp.Fixed64,System.Nullable`1<FixedMathSharp.Fixed64>)
GetCoveredVoxelsInto(GridForge.Grids.GridWorld,FixedMathSharp.Vector3d,FixedMathSharp.Vector3d,SwiftCollections.SwiftList`1<GridForge.Grids.Voxel>,GridForge.Grids.GridTraceScratch,System.Nullable`1<FixedMathSharp.Fixed64>)
GetCoveredVoxelsInto(GridForge.Grids.GridWorld,FixedMathSharp.Vector2d,FixedMathSharp.Vector2d,SwiftCollections.SwiftList`1<GridForge.Grids.Voxel>,GridForge.Grids.GridTraceScratch,FixedMathSharp.Fixed64,System.Nullable`1<FixedMathSharp.Fixed64>)
GetCoveredVoxelsInto(GridForge.Grids.GridWorld,FixedMathSharp.Geometry.FixedBoundArea,SwiftCollections.SwiftList`1<GridForge.Grids.Voxel>,GridForge.Grids.GridTraceScratch,FixedMathSharp.Fixed64,System.Nullable`1<FixedMathSharp.Fixed64>)
GetCoveredScanCells(GridForge.Grids.GridWorld,FixedMathSharp.Vector3d,FixedMathSharp.Vector3d,System.Nullable`1<FixedMathSharp.Fixed64>)
GetCoveredScanCells(GridForge.Grids.GridWorld,FixedMathSharp.Vector2d,FixedMathSharp.Vector2d,FixedMathSharp.Fixed64,System.Nullable`1<FixedMathSharp.Fixed64>)
GetCoveredScanCells(GridForge.Grids.GridWorld,FixedMathSharp.Geometry.FixedBoundArea,FixedMathSharp.Fixed64,System.Nullable`1<FixedMathSharp.Fixed64>)
GetCoveredScanCellsInto(GridForge.Grids.GridWorld,FixedMathSharp.Vector3d,FixedMathSharp.Vector3d,SwiftCollections.SwiftList`1<GridForge.Grids.ScanCell>,System.Nullable`1<FixedMathSharp.Fixed64>)
GetCoveredScanCellsInto(GridForge.Grids.GridWorld,FixedMathSharp.Vector2d,FixedMathSharp.Vector2d,SwiftCollections.SwiftList`1<GridForge.Grids.ScanCell>,FixedMathSharp.Fixed64,System.Nullable`1<FixedMathSharp.Fixed64>)
GetCoveredScanCellsInto(GridForge.Grids.GridWorld,FixedMathSharp.Geometry.FixedBoundArea,SwiftCollections.SwiftList`1<GridForge.Grids.ScanCell>,FixedMathSharp.Fixed64,System.Nullable`1<FixedMathSharp.Fixed64>)
GetCoveredScanCellsInto(GridForge.Grids.GridWorld,FixedMathSharp.Vector3d,FixedMathSharp.Vector3d,SwiftCollections.SwiftList`1<GridForge.Grids.ScanCell>,GridForge.Grids.GridScanScratch,System.Nullable`1<FixedMathSharp.Fixed64>)
GetCoveredScanCellsInto(GridForge.Grids.GridWorld,FixedMathSharp.Vector2d,FixedMathSharp.Vector2d,SwiftCollections.SwiftList`1<GridForge.Grids.ScanCell>,GridForge.Grids.GridScanScratch,FixedMathSharp.Fixed64,System.Nullable`1<FixedMathSharp.Fixed64>)
GetCoveredScanCellsInto(GridForge.Grids.GridWorld,FixedMathSharp.Geometry.FixedBoundArea,SwiftCollections.SwiftList`1<GridForge.Grids.ScanCell>,GridForge.Grids.GridScanScratch,FixedMathSharp.Fixed64,System.Nullable`1<FixedMathSharp.Fixed64>)
AddCoveredScanCellsTo(GridForge.Grids.GridWorld,FixedMathSharp.Vector3d,FixedMathSharp.Vector3d,SwiftCollections.SwiftList`1<GridForge.Grids.ScanCell>,System.Nullable`1<FixedMathSharp.Fixed64>)
AddCoveredScanCellsTo(GridForge.Grids.GridWorld,FixedMathSharp.Vector3d,FixedMathSharp.Vector3d,SwiftCollections.SwiftList`1<GridForge.Grids.ScanCell>,GridForge.Grids.GridScanScratch,System.Nullable`1<FixedMathSharp.Fixed64>)
AddCoveredVoxelsTo(GridForge.Grids.GridWorld,FixedMathSharp.Vector3d,FixedMathSharp.Vector3d,SwiftCollections.SwiftList`1<GridForge.Grids.Voxel>,System.Nullable`1<FixedMathSharp.Fixed64>)
AddCoveredVoxelsTo(GridForge.Grids.GridWorld,FixedMathSharp.Vector3d,FixedMathSharp.Vector3d,SwiftCollections.SwiftList`1<GridForge.Grids.Voxel>,GridForge.Grids.GridTraceScratch,System.Nullable`1<FixedMathSharp.Fixed64>)
AddCoveredVoxelsCore(GridForge.Grids.GridWorld,FixedMathSharp.Vector3d,FixedMathSharp.Vector3d,SwiftCollections.SwiftList`1<GridForge.Grids.Voxel>,SwiftCollections.SwiftList`1<System.UInt16>,SwiftCollections.SwiftHashSet`1<GridForge.Grids.Voxel>,System.Nullable`1<FixedMathSharp.Fixed64>)
AddCoveredScanCellsCore(GridForge.Grids.GridWorld,FixedMathSharp.Vector3d,FixedMathSharp.Vector3d,SwiftCollections.SwiftList`1<GridForge.Grids.ScanCell>,SwiftCollections.SwiftList`1<System.UInt16>,SwiftCollections.SwiftHashSet`1<GridForge.Grids.ScanCell>,System.Nullable`1<FixedMathSharp.Fixed64>)
GetCoveredVoxelsIterator()
<>m__Finally1()
AddCoveredVoxelsToMapping(GridForge.Grids.GridWorld,FixedMathSharp.Vector3d,FixedMathSharp.Vector3d,System.Nullable`1<FixedMathSharp.Fixed64>,SwiftCollections.SwiftList`1<GridForge.GridVoxelSet>,SwiftCollections.SwiftHashSet`1<GridForge.Grids.Voxel>,SwiftCollections.SwiftList`1<System.UInt16>)
GetCoveredScanCellsIterator()
<>m__Finally1()
AddCoveredScanCellsForGrid(GridForge.Grids.VoxelGrid,FixedMathSharp.Vector3d,FixedMathSharp.Vector3d,SwiftCollections.SwiftList`1<GridForge.Grids.ScanCell>,SwiftCollections.SwiftHashSet`1<GridForge.Grids.ScanCell>)
AddCoveredVoxelsForGrid(GridForge.Grids.VoxelGrid,FixedMathSharp.Vector3d,FixedMathSharp.Vector3d,SwiftCollections.SwiftList`1<GridForge.GridVoxelSet>,SwiftCollections.SwiftHashSet`1<GridForge.Grids.Voxel>)
AddCoveredGridVoxels(GridForge.Grids.VoxelGrid,FixedMathSharp.Vector3d,FixedMathSharp.Vector3d,SwiftCollections.SwiftList`1<GridForge.Grids.Voxel>,SwiftCollections.SwiftHashSet`1<GridForge.Grids.Voxel>)
AddCoveredHexGridVoxels(GridForge.Grids.VoxelGrid,FixedMathSharp.Vector3d,FixedMathSharp.Vector3d,SwiftCollections.SwiftList`1<GridForge.Grids.Voxel>)
AddCoveredHexScanCellsForGrid(GridForge.Grids.VoxelGrid,FixedMathSharp.Vector3d,FixedMathSharp.Vector3d,SwiftCollections.SwiftList`1<GridForge.Grids.ScanCell>,SwiftCollections.SwiftHashSet`1<GridForge.Grids.ScanCell>)
IsHexVoxelCenterInHorizontalCoverage(GridForge.Grids.Voxel,FixedMathSharp.Fixed64,FixedMathSharp.Fixed64,FixedMathSharp.Fixed64,FixedMathSharp.Fixed64)
TraceNavigationBodyInto(GridForge.Grids.GridWorld,GridForge.Spatial.WorldVoxelIndex,GridForge.Spatial.WorldVoxelIndex,FixedMathSharp.Vector3d,FixedMathSharp.Vector3d,FixedMathSharp.Fixed64,FixedMathSharp.Fixed64,SwiftCollections.SwiftList`1<GridForge.Grids.GridNavigationBodyTraceCell>,GridForge.Grids.GridNavigationBodyTraceScratch,System.Int32,System.Int32,System.Int32,System.Int64)
HasClosedNavigationBodyPrismContact(GridForge.Grids.Topology.GridCellPrism&,FixedMathSharp.Vector3d,FixedMathSharp.Fixed64,FixedMathSharp.Fixed64)
GetNavigationClosure(GridForge.Grids.VoxelGrid,GridForge.Grids.Topology.GridCellPrism&,GridForge.Grids.Topology.GridCellPrism&,System.Span`1<GridForge.Grids.Topology.GridCellPrism>)
IsNavigationClosurePrism(GridForge.Grids.Topology.GridCellPrism&,System.ReadOnlySpan`1<GridForge.Grids.Topology.GridCellPrism>,System.Int32)
SnapshotNavigationBodyCandidates(GridForge.Grids.GridWorld,SwiftCollections.SwiftList`1<GridForge.Grids.GridNavigationBodyTraceCandidate>)
TryCreateNavigationBodyBounds(FixedMathSharp.Vector3d,FixedMathSharp.Vector3d,FixedMathSharp.Fixed64,FixedMathSharp.Fixed64,FixedMathSharp.Fixed64,FixedMathSharp.Vector3d&,FixedMathSharp.Vector3d&)
AssignNavigationBodyBounds(FixedMathSharp.Fixed64,FixedMathSharp.Fixed64,FixedMathSharp.Fixed64,FixedMathSharp.Fixed64,FixedMathSharp.Fixed64,FixedMathSharp.Fixed64,FixedMathSharp.Vector3d&,FixedMathSharp.Vector3d&)
TryExpandNavigationBodyBounds(FixedMathSharp.Vector3d,FixedMathSharp.Vector3d,FixedMathSharp.Fixed64,FixedMathSharp.Vector3d&,FixedMathSharp.Vector3d&)
HasNavigationBodyUnionCoverage(GridForge.Grids.VoxelGrid,GridForge.Spatial.VoxelIndex,GridForge.Grids.VoxelGrid,GridForge.Spatial.VoxelIndex,FixedMathSharp.Vector3d,FixedMathSharp.Vector3d,FixedMathSharp.Fixed64,FixedMathSharp.Fixed64,SwiftCollections.SwiftList`1<GridForge.Grids.GridNavigationBodyTraceCandidate>,SwiftCollections.SwiftList`1<System.Int32>)
FindNavigationBodyCandidate(SwiftCollections.SwiftList`1<GridForge.Grids.GridNavigationBodyTraceCandidate>,GridForge.Grids.VoxelGrid,GridForge.Spatial.VoxelIndex)
FindBestMatchingNavigationBodyPrism(SwiftCollections.SwiftList`1<GridForge.Grids.GridNavigationBodyTraceCandidate>,GridForge.Grids.Topology.GridCellPrism&,System.Int32,System.Int32)
IsPreferredNavigationBodyCandidate(GridForge.Grids.GridNavigationBodyTraceCandidate,GridForge.Grids.GridNavigationBodyTraceCandidate)
AreSameNavigationBodyPrism(GridForge.Grids.Topology.GridCellPrism&,GridForge.Grids.Topology.GridCellPrism&)
CompareNavigationBodyPrisms(GridForge.Grids.Topology.GridCellPrism&,GridForge.Grids.Topology.GridCellPrism&)
FindNavigationBodyPrismRange(SwiftCollections.SwiftList`1<GridForge.Grids.GridNavigationBodyTraceCandidate>,GridForge.Grids.Topology.GridCellPrism&,System.Int32&,System.Int32&)
AddNavigationBodyUnionMember(SwiftCollections.SwiftList`1<GridForge.Grids.GridNavigationBodyTraceCandidate>,SwiftCollections.SwiftList`1<System.Int32>,System.Int32)
AppendMissingNavigationBodyAlternativeEvidence(GridForge.Grids.GridWorld,SwiftCollections.SwiftList`1<GridForge.Grids.GridNavigationBodyTraceCandidate>,SwiftCollections.SwiftList`1<GridForge.Grids.GridNavigationBodyTraceCell>,GridForge.Grids.VoxelGrid,GridForge.Spatial.VoxelIndex,GridForge.Grids.VoxelGrid,GridForge.Spatial.VoxelIndex)
CountMissingNavigationBodyAlternativeEvidence(SwiftCollections.SwiftList`1<GridForge.Grids.GridNavigationBodyTraceCandidate>,GridForge.Grids.VoxelGrid,GridForge.Spatial.VoxelIndex,GridForge.Grids.VoxelGrid,GridForge.Spatial.VoxelIndex)
GetNavigationBodyPrismGroupEnd(SwiftCollections.SwiftList`1<GridForge.Grids.GridNavigationBodyTraceCandidate>,System.Int32)
IsMissingNavigationBodyAlternativeGroup(SwiftCollections.SwiftList`1<GridForge.Grids.GridNavigationBodyTraceCandidate>,System.Int32,System.Int32,GridForge.Grids.VoxelGrid,GridForge.Spatial.VoxelIndex,GridForge.Grids.VoxelGrid,GridForge.Spatial.VoxelIndex)
IsNavigationBodyEndpoint(GridForge.Grids.GridNavigationBodyTraceCandidate,GridForge.Grids.VoxelGrid,GridForge.Spatial.VoxelIndex,GridForge.Grids.VoxelGrid,GridForge.Spatial.VoxelIndex)
CreateNavigationBodyTraceReport(GridForge.Grids.GridNavigationBodyTraceStatus,System.Int32,System.Int32,SwiftCollections.SwiftList`1<GridForge.Grids.GridNavigationBodyTraceCell>,GridForge.Grids.Topology.GridCoveredAddressRunStamp)
FailNavigationBodyTrace(SwiftCollections.SwiftList`1<GridForge.Grids.GridNavigationBodyTraceCell>,GridForge.Grids.GridNavigationBodyTraceStatus,System.Int32,System.Int32,GridForge.Grids.Topology.GridCoveredAddressRunStamp)
Compare(GridForge.Grids.GridNavigationBodyTraceCandidate,GridForge.Grids.GridNavigationBodyTraceCandidate)
Compare(GridForge.Grids.GridNavigationBodyTraceCell,GridForge.Grids.GridNavigationBodyTraceCell)
CompareNavigationBodyTraceCells(GridForge.Grids.GridNavigationBodyTraceCell,GridForge.Grids.GridNavigationBodyTraceCell)
TraceIntervalsInto(GridForge.Grids.GridWorld,FixedMathSharp.Vector3d,FixedMathSharp.Vector3d,SwiftCollections.SwiftList`1<GridForge.Grids.GridTraceInterval>,GridForge.Grids.GridTraceIntervalScratch,System.Int32,System.Int32,System.Int32,System.Int64)
TryCollectSegmentCandidates(GridForge.Grids.VoxelGrid,FixedMathSharp.Vector3d,FixedMathSharp.Vector3d,GridForge.Grids.GridTraceIntervalScratch,System.Int32)
SnapshotSparsePresence(GridForge.Grids.GridWorld,SwiftCollections.SwiftList`1<GridForge.Grids.GridTraceAddressCandidate>)
TryGetPrismInterval(FixedMathSharp.Vector3d,FixedMathSharp.Vector3d,GridForge.Grids.Topology.GridCellPrism&,FixedMathSharp.Fixed64&,FixedMathSharp.Fixed64&)
TryGetVerticalInterval(FixedMathSharp.Fixed64,FixedMathSharp.Fixed64,FixedMathSharp.Fixed64,FixedMathSharp.Fixed64,FixedMathSharp.Fixed64&,FixedMathSharp.Fixed64&)
CreateTraceReport(GridForge.Grids.GridTraceIntervalStatus,System.Int32,System.Int32,SwiftCollections.SwiftList`1<GridForge.Grids.GridTraceInterval>)
FailTrace(SwiftCollections.SwiftList`1<GridForge.Grids.GridTraceInterval>,GridForge.Grids.GridTraceIntervalStatus,System.Int32,System.Int32)
AssignTieGroups(SwiftCollections.SwiftList`1<GridForge.Grids.GridTraceInterval>)
HasContinuousCoverage(SwiftCollections.SwiftList`1<GridForge.Grids.GridTraceInterval>,System.Boolean)
SortGridIndices(GridForge.Grids.GridWorld,SwiftCollections.SwiftList`1<System.UInt16>)
SortIntervals(SwiftCollections.SwiftList`1<GridForge.Grids.GridTraceInterval>)
SiftIntervalsDown(GridForge.Grids.GridTraceInterval[],System.Int32,System.Int32)
CompareIntervals(GridForge.Grids.GridTraceInterval,GridForge.Grids.GridTraceInterval)
CompareGridIdentity(GridForge.Grids.VoxelGrid,GridForge.Grids.VoxelGrid)
.ctor(GridForge.Grids.GridWorld)
Compare(System.UInt16,System.UInt16)
CompareConfigurationKeys(GridForge.Configuration.GridConfigurationKey,GridForge.Configuration.GridConfigurationKey)
CompareVectors(FixedMathSharp.Vector3d,FixedMathSharp.Vector3d)
TraceLineIterator()
<>m__Finally1()
AddTraceLineVoxelsToMapping(GridForge.Grids.GridWorld,FixedMathSharp.Vector3d,FixedMathSharp.Vector3d,System.Nullable`1<FixedMathSharp.Fixed64>,System.Boolean,SwiftCollections.SwiftList`1<GridForge.GridVoxelSet>,SwiftCollections.SwiftHashSet`1<GridForge.Grids.Voxel>,SwiftCollections.SwiftList`1<System.UInt16>)
AddTraceLineVoxelsTo(GridForge.Grids.GridWorld,FixedMathSharp.Vector3d,FixedMathSharp.Vector3d,System.Nullable`1<FixedMathSharp.Fixed64>,System.Boolean,SwiftCollections.SwiftList`1<GridForge.Grids.Voxel>,SwiftCollections.SwiftHashSet`1<GridForge.Grids.Voxel>,SwiftCollections.SwiftList`1<System.UInt16>)
CreateTraceLinePlan(GridForge.Grids.VoxelGrid,FixedMathSharp.Vector3d,FixedMathSharp.Vector3d,System.Nullable`1<FixedMathSharp.Fixed64>)
CalculateTraceSteps(GridForge.Grids.VoxelGrid,FixedMathSharp.Vector3d)
CreateTraceEndpoint(FixedMathSharp.Vector3d,FixedMathSharp.Vector3d,FixedMathSharp.Vector3d,FixedMathSharp.Vector3d,System.Boolean)
SelectTraceCoordinate(FixedMathSharp.Fixed64,FixedMathSharp.Fixed64,FixedMathSharp.Fixed64,FixedMathSharp.Fixed64,System.Boolean)
CreatePaddedOrderedBounds(FixedMathSharp.Vector3d,FixedMathSharp.Vector3d,System.Nullable`1<FixedMathSharp.Fixed64>)
ExpandOrderedBounds(FixedMathSharp.Vector3d,FixedMathSharp.Vector3d,FixedMathSharp.Fixed64)
TryGetCoveredScanCellRange(GridForge.Grids.VoxelGrid,FixedMathSharp.Vector3d,FixedMathSharp.Vector3d,System.Int32&,System.Int32&,System.Int32&,System.Int32&,System.Int32&,System.Int32&)
AddTraceLineVoxelsForGrid(GridForge.Grids.VoxelGrid,FixedMathSharp.Vector3d,FixedMathSharp.Vector3d,System.Nullable`1<FixedMathSharp.Fixed64>,System.Boolean,SwiftCollections.SwiftList`1<GridForge.GridVoxelSet>,SwiftCollections.SwiftHashSet`1<GridForge.Grids.Voxel>)
AddTraceLineVoxelsForGrid(GridForge.Grids.VoxelGrid,FixedMathSharp.Vector3d,FixedMathSharp.Vector3d,System.Nullable`1<FixedMathSharp.Fixed64>,System.Boolean,SwiftCollections.SwiftList`1<GridForge.Grids.Voxel>,SwiftCollections.SwiftHashSet`1<GridForge.Grids.Voxel>)
AddTraceLineGridVoxels(GridForge.Grids.VoxelGrid,FixedMathSharp.Vector3d,FixedMathSharp.Vector3d,System.Nullable`1<FixedMathSharp.Fixed64>,System.Boolean,SwiftCollections.SwiftList`1<GridForge.Grids.Voxel>,SwiftCollections.SwiftHashSet`1<GridForge.Grids.Voxel>)
AddHexTraceLineGridVoxels(GridForge.Grids.VoxelGrid,FixedMathSharp.Vector3d,FixedMathSharp.Vector3d,System.Nullable`1<FixedMathSharp.Fixed64>,System.Boolean,SwiftCollections.SwiftList`1<GridForge.Grids.Voxel>,SwiftCollections.SwiftHashSet`1<GridForge.Grids.Voxel>)
CreateHexTraceEndpoints(GridForge.Grids.VoxelGrid,FixedMathSharp.Vector3d,FixedMathSharp.Vector3d,System.Nullable`1<FixedMathSharp.Fixed64>,GridForge.Spatial.VoxelIndex&,GridForge.Spatial.VoxelIndex&)
CalculateHexTraceSteps(GridForge.Spatial.VoxelIndex,GridForge.Spatial.VoxelIndex)
InterpolateHexTraceIndex(GridForge.Spatial.VoxelIndex,GridForge.Spatial.VoxelIndex,FixedMathSharp.Fixed64)
Interpolate(FixedMathSharp.Fixed64,FixedMathSharp.Fixed64,FixedMathSharp.Fixed64)
TryClipTraceSegmentToGrid(GridForge.Grids.VoxelGrid,FixedMathSharp.Vector3d,FixedMathSharp.Vector3d,System.Nullable`1<FixedMathSharp.Fixed64>,FixedMathSharp.Vector3d&,FixedMathSharp.Vector3d&,System.Boolean&)
ClipTraceSegmentAxis(FixedMathSharp.Fixed64,FixedMathSharp.Fixed64,FixedMathSharp.Fixed64,FixedMathSharp.Fixed64,FixedMathSharp.Fixed64&,FixedMathSharp.Fixed64&)
ShouldIncludeHexTraceEndIndex(GridForge.Grids.VoxelGrid,FixedMathSharp.Vector3d,GridForge.Spatial.VoxelIndex,System.Boolean)
InterpolateTraceSegment(FixedMathSharp.Vector3d,FixedMathSharp.Vector3d,FixedMathSharp.Vector3d,FixedMathSharp.Vector3d,FixedMathSharp.Fixed64)
InterpolateTraceAxis(FixedMathSharp.Fixed64,FixedMathSharp.Fixed64,FixedMathSharp.Fixed64,FixedMathSharp.Fixed64,FixedMathSharp.Fixed64)
AddTraceVoxelByPosition(GridForge.Grids.VoxelGrid,FixedMathSharp.Vector3d,SwiftCollections.SwiftList`1<GridForge.Grids.Voxel>,SwiftCollections.SwiftHashSet`1<GridForge.Grids.Voxel>)
AddTraceVoxelByIndex(GridForge.Grids.VoxelGrid,GridForge.Spatial.VoxelIndex,SwiftCollections.SwiftList`1<GridForge.Grids.Voxel>,SwiftCollections.SwiftHashSet`1<GridForge.Grids.Voxel>)
ReleaseGridVoxelSets(SwiftCollections.SwiftList`1<GridForge.GridVoxelSet>)