< Summary

Line coverage
100%
Covered lines: 1892
Uncovered lines: 0
Coverable lines: 1892
Total lines: 3914
Line coverage: 100%
Branch coverage
100%
Covered branches: 874
Total branches: 874
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%11100%
File 3: TraceNavigationBodyInto(...)100%8888100%
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%2020100%
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: TracePlanarNavigationBodyInto(...)100%9292100%
File 5: ArePlanarCoverageNeighborsOrCoincident(...)100%44100%
File 5: TryGetPlanarProofPrism(...)100%22100%
File 5: MatchesPlanarEndpoint(...)100%1414100%
File 5: TryCreatePlanarBodyBounds(...)100%1010100%
File 5: TryExpandPlanarCandidateBounds(...)100%1212100%
File 5: TryCreatePlanarProofPrism(...)100%11100%
File 5: HasClosedPlanarBodyContact(...)100%22100%
File 5: HasStrictPlanarBodyOverlap(...)100%22100%
File 5: GetPlanarNavigationClosure(...)100%1818100%
File 5: ClosePlanarBodyUnion(...)100%3030100%
File 5: TryAddPlanarUnionMember(...)100%22100%
File 6: TryGetPlanarCandidateRange(...)100%1010100%
File 6: FindPlanarCoordinateBound(...)100%1414100%
File 7: TryTraceRectangularSlabsInto(...)100%3030100%
File 7: TryQualifyRectangularSlabs(...)100%2626100%
File 7: IsRepresentableSlabExtreme(...)100%44100%
File 7: RectangularSlabSeparatesEndpoints(...)100%1212100%
File 8: TraceIntervalsInto(...)100%11100%
File 8: ValidateTraceArguments(...)100%11100%
File 8: TraceIntervalsCore(...)100%2424100%
File 8: AppendTraceIntervals(...)100%1010100%
File 8: TryCollectSegmentCandidates(...)100%1212100%
File 8: TryAdmitTraceRange(...)100%22100%
File 8: TryCollectRectangularSegmentCandidates(...)100%1414100%
File 8: CollectRectangularSegmentSlab(...)100%66100%
File 8: FindRectangularZBound(...)100%88100%
File 8: SnapshotSparsePresence(...)100%44100%
File 8: TryGetPrismInterval(...)100%44100%
File 8: TryGetVerticalInterval(...)100%88100%
File 8: CreateTraceReport(...)100%11100%
File 8: FailTrace(...)100%11100%
File 8: AssignTieGroups(...)100%2222100%
File 8: HasContinuousCoverage(...)100%1818100%
File 8: SortGridIndices(...)100%11100%
File 8: SortIntervals(...)100%66100%
File 8: SiftIntervalsDown(...)100%1414100%
File 8: CompareIntervals(...)100%66100%
File 8: CompareGridIdentity(...)100%11100%
File 8: .ctor(...)100%11100%
File 8: Compare(...)100%11100%
File 8: CompareConfigurationKeys(...)100%1414100%
File 8: CompareVectors(...)100%44100%
File 9: TraceLineIterator()100%22100%
File 9: <>m__Finally1()100%11100%
File 9: AddTraceLineVoxelsToMapping(...)100%22100%
File 9: AddTraceLineVoxelsTo(...)100%22100%
File 9: CreateTraceLinePlan(...)100%11100%
File 9: CalculateTraceSteps(...)100%11100%
File 9: CreateTraceEndpoint(...)100%11100%
File 9: SelectTraceCoordinate(...)100%22100%
File 9: CreatePaddedOrderedBounds(...)100%1010100%
File 9: ExpandOrderedBounds(...)100%22100%
File 9: TryGetCoveredScanCellRange(...)100%22100%
File 9: AddTraceLineVoxelsForGrid(...)100%44100%
File 9: AddTraceLineVoxelsForGrid(...)100%22100%
File 9: AddTraceLineGridVoxels(...)100%1010100%
File 9: AddHexTraceLineGridVoxels(...)100%66100%
File 9: CreateHexTraceEndpoints(...)100%11100%
File 9: CalculateHexTraceSteps(...)100%11100%
File 9: InterpolateHexTraceIndex(...)100%11100%
File 9: Interpolate(...)100%11100%
File 9: TryClipTraceSegmentToGrid(...)100%1010100%
File 9: ClipTraceSegmentAxis(...)100%1010100%
File 9: ShouldIncludeHexTraceEndIndex(...)100%44100%
File 9: InterpolateTraceSegment(...)100%11100%
File 9: InterpolateTraceAxis(...)100%66100%
File 9: AddTraceVoxelByPosition(...)100%44100%
File 9: AddTraceVoxelByIndex(...)100%44100%
File 9: 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    /// Consume each pooled voxel list inside the enumeration or copy its contents
 55    /// to caller-owned storage. Retained results should use <c>TraceLineInto</c>.
 56    /// </remarks>
 57    /// <param name="world">The world whose grids should be traced.</param>
 58    /// <param name="start">Starting position in world space.</param>
 59    /// <param name="end">Ending position in world space.</param>
 60    /// <param name="padding">Value applied to the start/end positions before snapping.</param>
 61    /// <param name="includeEnd">Whether to include the end voxel in the traced line.</param>
 62    /// <returns>Grouped results whose voxel lists are lent until enumeration completes or is disposed.</returns>
 63    public static IEnumerable<GridVoxelSet> TraceLine(
 64        GridWorld world,
 65        Vector3d start,
 66        Vector3d end,
 67        Fixed64? padding = null,
 68        bool includeEnd = true)
 69    {
 4270        if (world == null || !world.IsActive)
 271            return System.Array.Empty<GridVoxelSet>();
 72
 4073        return TraceLineIterator(world, start, end, padding, includeEnd);
 74    }
 75
 76    /// <summary>
 77    /// Clears and fills caller-owned storage with voxels traced by a 3D line.
 78    /// </summary>
 79    /// <param name="world">The world whose grids should be traced.</param>
 80    /// <param name="start">Starting position in world space.</param>
 81    /// <param name="end">Ending position in world space.</param>
 82    /// <param name="results">Caller-owned storage that receives traced voxels.</param>
 83    /// <param name="padding">Value applied to the start/end positions before snapping.</param>
 84    /// <param name="includeEnd">Whether to include the end voxel in the traced line.</param>
 85    public static void TraceLineInto(
 86        GridWorld world,
 87        Vector3d start,
 88        Vector3d end,
 89        SwiftList<Voxel> results,
 90        Fixed64? padding = null,
 91        bool includeEnd = true)
 92    {
 593        ChronicleGuard.ThrowIfNull(results, nameof(results));
 94
 495        results.Clear();
 496        if (world == null || !world.IsActive)
 197            return;
 98
 399        SwiftHashSet<Voxel> voxelRedundancyCheck = SwiftHashSetPool<Voxel>.Shared.Rent();
 3100        SwiftList<ushort> candidateGrids = SwiftListPool<ushort>.Shared.Rent();
 101
 102        try
 103        {
 3104            AddTraceLineVoxelsTo(
 3105                world,
 3106                start,
 3107                end,
 3108                padding,
 3109                includeEnd,
 3110                results,
 3111                voxelRedundancyCheck,
 3112                candidateGrids);
 113
 3114        }
 115        finally
 116        {
 3117            SwiftHashSetPool<Voxel>.Shared.Release(voxelRedundancyCheck);
 3118            SwiftListPool<ushort>.Shared.Release(candidateGrids);
 3119        }
 3120    }
 121
 122    /// <summary>
 123    /// Clears and fills caller-owned storage with voxels traced by a 3D line using caller-owned scratch collections.
 124    /// </summary>
 125    /// <param name="world">The world whose grids should be traced.</param>
 126    /// <param name="start">Starting position in world space.</param>
 127    /// <param name="end">Ending position in world space.</param>
 128    /// <param name="results">Caller-owned storage that receives traced voxels.</param>
 129    /// <param name="scratch">Reusable scratch storage for grid candidates and duplicate-voxel guards.</param>
 130    /// <param name="padding">Value applied to the start/end positions before snapping.</param>
 131    /// <param name="includeEnd">Whether to include the end voxel in the traced line.</param>
 132    public static void TraceLineInto(
 133        GridWorld world,
 134        Vector3d start,
 135        Vector3d end,
 136        SwiftList<Voxel> results,
 137        GridTraceScratch scratch,
 138        Fixed64? padding = null,
 139        bool includeEnd = true)
 140    {
 11141        ChronicleGuard.ThrowIfNull(results, nameof(results));
 10142        ChronicleGuard.ThrowIfNull(scratch, nameof(scratch));
 143
 9144        results.Clear();
 9145        if (world == null || !world.IsActive)
 2146            return;
 147
 7148        scratch.Clear();
 7149        AddTraceLineVoxelsTo(
 7150            world,
 7151            start,
 7152            end,
 7153            padding,
 7154            includeEnd,
 7155            results,
 7156            scratch.VoxelRedundancy,
 7157            scratch.CandidateGrids);
 158
 7159    }
 160
 161    /// <summary>
 162    /// Traces a 2D XZ-plane line between two points in the supplied world, snapping them to grid coordinates.
 163    /// </summary>
 164    /// <remarks>
 165    /// This method maps <see cref="Vector2d.X"/> to world X, <see cref="Vector2d.Y"/> to world Z,
 166    /// and <paramref name="layerY"/> to world Y. The default layer is world Y = 0.
 167    /// </remarks>
 168    /// <param name="world">The world whose grids should be traced.</param>
 169    /// <param name="start">Starting XZ-plane position in world space.</param>
 170    /// <param name="end">Ending XZ-plane position in world space.</param>
 171    /// <param name="padding">Value applied to the start/end positions before snapping.</param>
 172    /// <param name="includeEnd">Whether to include the end voxel in the traced line.</param>
 173    /// <param name="layerY">The world Y layer to trace. Defaults to zero.</param>
 174    /// <returns>Grouped results whose voxel lists are lent until enumeration completes or is disposed.</returns>
 175    public static IEnumerable<GridVoxelSet> TraceLine(
 176        GridWorld world,
 177        Vector2d start,
 178        Vector2d end,
 179        Fixed64? padding = null,
 180        bool includeEnd = true,
 181        Fixed64 layerY = default)
 182    {
 4183        Vector3d start3D = GridPlane2d.ToWorld(start, layerY);
 4184        Vector3d end3D = GridPlane2d.ToWorld(end, layerY);
 185
 4186        return TraceLine(world, start3D, end3D, padding, includeEnd);
 187    }
 188
 189    /// <summary>
 190    /// Clears and fills caller-owned storage with voxels traced by a 2D XZ-plane line.
 191    /// </summary>
 192    /// <param name="world">The world whose grids should be traced.</param>
 193    /// <param name="start">Starting XZ-plane position in world space.</param>
 194    /// <param name="end">Ending XZ-plane position in world space.</param>
 195    /// <param name="results">Caller-owned storage that receives traced voxels.</param>
 196    /// <param name="padding">Value applied to the start/end positions before snapping.</param>
 197    /// <param name="includeEnd">Whether to include the end voxel in the traced line.</param>
 198    /// <param name="layerY">The world Y layer to trace. Defaults to zero.</param>
 199    public static void TraceLineInto(
 200        GridWorld world,
 201        Vector2d start,
 202        Vector2d end,
 203        SwiftList<Voxel> results,
 204        Fixed64? padding = null,
 205        bool includeEnd = true,
 206        Fixed64 layerY = default)
 207    {
 1208        Vector3d start3D = GridPlane2d.ToWorld(start, layerY);
 1209        Vector3d end3D = GridPlane2d.ToWorld(end, layerY);
 210
 1211        TraceLineInto(world, start3D, end3D, results, padding, includeEnd);
 1212    }
 213
 214    /// <summary>
 215    /// Clears and fills caller-owned storage with voxels traced by a 2D XZ-plane line using caller-owned scratch collec
 216    /// </summary>
 217    /// <param name="world">The world whose grids should be traced.</param>
 218    /// <param name="start">Starting XZ-plane position in world space.</param>
 219    /// <param name="end">Ending XZ-plane position in world space.</param>
 220    /// <param name="results">Caller-owned storage that receives traced voxels.</param>
 221    /// <param name="scratch">Reusable scratch storage for grid candidates and duplicate-voxel guards.</param>
 222    /// <param name="padding">Value applied to the start/end positions before snapping.</param>
 223    /// <param name="includeEnd">Whether to include the end voxel in the traced line.</param>
 224    /// <param name="layerY">The world Y layer to trace. Defaults to zero.</param>
 225    public static void TraceLineInto(
 226        GridWorld world,
 227        Vector2d start,
 228        Vector2d end,
 229        SwiftList<Voxel> results,
 230        GridTraceScratch scratch,
 231        Fixed64? padding = null,
 232        bool includeEnd = true,
 233        Fixed64 layerY = default)
 234    {
 1235        Vector3d start3D = GridPlane2d.ToWorld(start, layerY);
 1236        Vector3d end3D = GridPlane2d.ToWorld(end, layerY);
 237
 1238        TraceLineInto(world, start3D, end3D, results, scratch, padding, includeEnd);
 1239    }
 240
 241    /// <summary>
 242    /// Retrieves all grid voxels covered by the given bounding area in the supplied world.
 243    /// </summary>
 244    /// <remarks>
 245    /// Each result lends a pooled voxel list until enumeration completes or is
 246    /// disposed. Copy contents before retaining them, or use <c>GetCoveredVoxelsInto</c>.
 247    /// </remarks>
 248    public static IEnumerable<GridVoxelSet> GetCoveredVoxels(
 249        GridWorld world,
 250        Vector3d boundsMin,
 251        Vector3d boundsMax,
 252        Fixed64? padding = null)
 253    {
 204254        if (world == null || !world.IsActive)
 2255            return System.Array.Empty<GridVoxelSet>();
 256
 202257        return GetCoveredVoxelsIterator(world, boundsMin, boundsMax, padding);
 258    }
 259
 260    /// <summary>
 261    /// Retrieves all grid voxels covered by the given XZ-plane bounding area on the supplied world Y layer.
 262    /// </summary>
 263    /// <param name="world">The world whose grids should be queried.</param>
 264    /// <param name="boundsMin">The 2D minimum corner whose X component maps to world X and Y component maps to world Z.
 265    /// <param name="boundsMax">The 2D maximum corner whose X component maps to world X and Y component maps to world Z.
 266    /// <param name="layerY">The world Y layer to cover. Defaults to zero.</param>
 267    /// <param name="padding">Value applied to the min/max bounds before snapping.</param>
 268    /// <returns>Grouped results whose voxel lists are lent until enumeration completes or is disposed.</returns>
 269    public static IEnumerable<GridVoxelSet> GetCoveredVoxels(
 270        GridWorld world,
 271        Vector2d boundsMin,
 272        Vector2d boundsMax,
 273        Fixed64 layerY = default,
 274        Fixed64? padding = null)
 275    {
 5276        (Vector3d min, Vector3d max) = GridPlane2d.ToWorldBounds(boundsMin, boundsMax, layerY);
 5277        return GetCoveredVoxels(world, min, max, padding);
 278    }
 279
 280    /// <summary>
 281    /// Retrieves all grid voxels covered by the given XZ-plane area on the supplied world Y layer.
 282    /// </summary>
 283    /// <param name="world">The world whose grids should be queried.</param>
 284    /// <param name="area">The 2D area whose X component maps to world X and Y component maps to world Z.</param>
 285    /// <param name="layerY">The world Y layer to cover. Defaults to zero.</param>
 286    /// <param name="padding">Value applied to the min/max bounds before snapping.</param>
 287    /// <returns>Grouped results whose voxel lists are lent until enumeration completes or is disposed.</returns>
 288    public static IEnumerable<GridVoxelSet> GetCoveredVoxels(
 289        GridWorld world,
 290        FixedBoundArea area,
 291        Fixed64 layerY = default,
 292        Fixed64? padding = null)
 293    {
 1294        return GetCoveredVoxels(world, area.Min, area.Max, layerY, padding);
 295    }
 296
 297    /// <summary>
 298    /// Clears and fills caller-owned storage with voxels covered by the supplied bounding area.
 299    /// </summary>
 300    /// <param name="world">The world whose grids should be queried.</param>
 301    /// <param name="boundsMin">The minimum corner of the bounding area.</param>
 302    /// <param name="boundsMax">The maximum corner of the bounding area.</param>
 303    /// <param name="results">Caller-owned storage that receives covered voxels.</param>
 304    /// <param name="padding">Value applied to the min/max bounds before normalization.</param>
 305    public static void GetCoveredVoxelsInto(
 306        GridWorld world,
 307        Vector3d boundsMin,
 308        Vector3d boundsMax,
 309        SwiftList<Voxel> results,
 310        Fixed64? padding = null)
 311    {
 11312        ChronicleGuard.ThrowIfNull(results, nameof(results));
 313
 10314        results.Clear();
 10315        if (world == null || !world.IsActive)
 1316            return;
 317
 9318        AddCoveredVoxelsTo(world, boundsMin, boundsMax, results, padding);
 9319    }
 320
 321    /// <summary>
 322    /// Clears and fills caller-owned storage with voxels covered by the supplied XZ-plane bounding area.
 323    /// </summary>
 324    /// <param name="world">The world whose grids should be queried.</param>
 325    /// <param name="boundsMin">The 2D minimum corner whose X component maps to world X and Y component maps to world Z.
 326    /// <param name="boundsMax">The 2D maximum corner whose X component maps to world X and Y component maps to world Z.
 327    /// <param name="results">Caller-owned storage that receives covered voxels.</param>
 328    /// <param name="layerY">The world Y layer to cover. Defaults to zero.</param>
 329    /// <param name="padding">Value applied to the min/max bounds before normalization.</param>
 330    public static void GetCoveredVoxelsInto(
 331        GridWorld world,
 332        Vector2d boundsMin,
 333        Vector2d boundsMax,
 334        SwiftList<Voxel> results,
 335        Fixed64 layerY = default,
 336        Fixed64? padding = null)
 337    {
 2338        (Vector3d min, Vector3d max) = GridPlane2d.ToWorldBounds(boundsMin, boundsMax, layerY);
 2339        GetCoveredVoxelsInto(world, min, max, results, padding);
 2340    }
 341
 342    /// <summary>
 343    /// Clears and fills caller-owned storage with voxels covered by the supplied XZ-plane area.
 344    /// </summary>
 345    /// <param name="world">The world whose grids should be queried.</param>
 346    /// <param name="area">The 2D area whose X component maps to world X and Y component maps to world Z.</param>
 347    /// <param name="results">Caller-owned storage that receives covered voxels.</param>
 348    /// <param name="layerY">The world Y layer to cover. Defaults to zero.</param>
 349    /// <param name="padding">Value applied to the min/max bounds before normalization.</param>
 350    public static void GetCoveredVoxelsInto(
 351        GridWorld world,
 352        FixedBoundArea area,
 353        SwiftList<Voxel> results,
 354        Fixed64 layerY = default,
 355        Fixed64? padding = null)
 356    {
 1357        GetCoveredVoxelsInto(world, area.Min, area.Max, results, layerY, padding);
 1358    }
 359
 360    /// <summary>
 361    /// Clears and fills caller-owned storage using caller-owned scratch collections.
 362    /// </summary>
 363    /// <param name="world">The world whose grids should be queried.</param>
 364    /// <param name="boundsMin">The minimum corner of the bounding area.</param>
 365    /// <param name="boundsMax">The maximum corner of the bounding area.</param>
 366    /// <param name="results">Caller-owned storage that receives covered voxels.</param>
 367    /// <param name="scratch">Reusable scratch storage for grid candidates and duplicate-voxel guards.</param>
 368    /// <param name="padding">Value applied to the min/max bounds before normalization.</param>
 369    public static void GetCoveredVoxelsInto(
 370        GridWorld world,
 371        Vector3d boundsMin,
 372        Vector3d boundsMax,
 373        SwiftList<Voxel> results,
 374        GridTraceScratch scratch,
 375        Fixed64? padding = null)
 376    {
 18377        ChronicleGuard.ThrowIfNull(results, nameof(results));
 17378        ChronicleGuard.ThrowIfNull(scratch, nameof(scratch));
 379
 16380        results.Clear();
 16381        if (world == null || !world.IsActive)
 2382            return;
 383
 14384        AddCoveredVoxelsTo(world, boundsMin, boundsMax, results, scratch, padding);
 14385    }
 386
 387    /// <summary>
 388    /// Clears and fills caller-owned storage using caller-owned scratch collections for an XZ-plane bounding area.
 389    /// </summary>
 390    /// <param name="world">The world whose grids should be queried.</param>
 391    /// <param name="boundsMin">The 2D minimum corner whose X component maps to world X and Y component maps to world Z.
 392    /// <param name="boundsMax">The 2D maximum corner whose X component maps to world X and Y component maps to world Z.
 393    /// <param name="results">Caller-owned storage that receives covered voxels.</param>
 394    /// <param name="scratch">Reusable scratch storage for grid candidates and duplicate-voxel guards.</param>
 395    /// <param name="layerY">The world Y layer to cover. Defaults to zero.</param>
 396    /// <param name="padding">Value applied to the min/max bounds before normalization.</param>
 397    public static void GetCoveredVoxelsInto(
 398        GridWorld world,
 399        Vector2d boundsMin,
 400        Vector2d boundsMax,
 401        SwiftList<Voxel> results,
 402        GridTraceScratch scratch,
 403        Fixed64 layerY = default,
 404        Fixed64? padding = null)
 405    {
 2406        (Vector3d min, Vector3d max) = GridPlane2d.ToWorldBounds(boundsMin, boundsMax, layerY);
 2407        GetCoveredVoxelsInto(world, min, max, results, scratch, padding);
 2408    }
 409
 410    /// <summary>
 411    /// Clears and fills caller-owned storage using caller-owned scratch collections for an XZ-plane area.
 412    /// </summary>
 413    /// <param name="world">The world whose grids should be queried.</param>
 414    /// <param name="area">The 2D area whose X component maps to world X and Y component maps to world Z.</param>
 415    /// <param name="results">Caller-owned storage that receives covered voxels.</param>
 416    /// <param name="scratch">Reusable scratch storage for grid candidates and duplicate-voxel guards.</param>
 417    /// <param name="layerY">The world Y layer to cover. Defaults to zero.</param>
 418    /// <param name="padding">Value applied to the min/max bounds before normalization.</param>
 419    public static void GetCoveredVoxelsInto(
 420        GridWorld world,
 421        FixedBoundArea area,
 422        SwiftList<Voxel> results,
 423        GridTraceScratch scratch,
 424        Fixed64 layerY = default,
 425        Fixed64? padding = null)
 426    {
 1427        GetCoveredVoxelsInto(world, area.Min, area.Max, results, scratch, layerY, padding);
 1428    }
 429
 430    /// <summary>
 431    /// Retrieves all scan cells within the given bounding area across relevant grids in the supplied world.
 432    /// </summary>
 433    /// <param name="world">The world whose grids should be queried.</param>
 434    /// <param name="boundsMin">The minimum corner of the bounding area.</param>
 435    /// <param name="boundsMax">The maximum corner of the bounding area.</param>
 436    /// <param name="padding">Value applied to the min/max bounds before snapping.</param>
 437    /// <returns>An enumerable of covered scan cells grouped by grid.</returns>
 438    public static IEnumerable<ScanCell> GetCoveredScanCells(
 439        GridWorld world,
 440        Vector3d boundsMin,
 441        Vector3d boundsMax,
 442        Fixed64? padding = null)
 443    {
 26444        if (world == null || !world.IsActive)
 2445            return System.Array.Empty<ScanCell>();
 446
 24447        return GetCoveredScanCellsIterator(world, boundsMin, boundsMax, padding);
 448    }
 449
 450    /// <summary>
 451    /// Retrieves all scan cells within the given XZ-plane bounding area on the supplied world Y layer.
 452    /// </summary>
 453    /// <param name="world">The world whose grids should be queried.</param>
 454    /// <param name="boundsMin">The 2D minimum corner whose X component maps to world X and Y component maps to world Z.
 455    /// <param name="boundsMax">The 2D maximum corner whose X component maps to world X and Y component maps to world Z.
 456    /// <param name="layerY">The world Y layer to cover. Defaults to zero.</param>
 457    /// <param name="padding">Value applied to the min/max bounds before snapping.</param>
 458    /// <returns>An enumerable of covered scan cells grouped by grid.</returns>
 459    public static IEnumerable<ScanCell> GetCoveredScanCells(
 460        GridWorld world,
 461        Vector2d boundsMin,
 462        Vector2d boundsMax,
 463        Fixed64 layerY = default,
 464        Fixed64? padding = null)
 465    {
 3466        (Vector3d min, Vector3d max) = GridPlane2d.ToWorldBounds(boundsMin, boundsMax, layerY);
 3467        return GetCoveredScanCells(world, min, max, padding);
 468    }
 469
 470    /// <summary>
 471    /// Retrieves all scan cells within the given XZ-plane area on the supplied world Y layer.
 472    /// </summary>
 473    /// <param name="world">The world whose grids should be queried.</param>
 474    /// <param name="area">The 2D area whose X component maps to world X and Y component maps to world Z.</param>
 475    /// <param name="layerY">The world Y layer to cover. Defaults to zero.</param>
 476    /// <param name="padding">Value applied to the min/max bounds before snapping.</param>
 477    /// <returns>An enumerable of covered scan cells grouped by grid.</returns>
 478    public static IEnumerable<ScanCell> GetCoveredScanCells(
 479        GridWorld world,
 480        FixedBoundArea area,
 481        Fixed64 layerY = default,
 482        Fixed64? padding = null)
 483    {
 1484        return GetCoveredScanCells(world, area.Min, area.Max, layerY, padding);
 485    }
 486
 487    /// <summary>
 488    /// Clears and fills caller-owned storage with scan cells covered by the supplied bounding area.
 489    /// </summary>
 490    public static void GetCoveredScanCellsInto(
 491        GridWorld world,
 492        Vector3d boundsMin,
 493        Vector3d boundsMax,
 494        SwiftList<ScanCell> results,
 495        Fixed64? padding = null)
 496    {
 12497        ChronicleGuard.ThrowIfNull(results, nameof(results));
 498
 11499        results.Clear();
 11500        if (world == null || !world.IsActive)
 2501            return;
 502
 9503        AddCoveredScanCellsTo(world, boundsMin, boundsMax, results, padding);
 9504    }
 505
 506    /// <summary>
 507    /// Clears and fills caller-owned storage with scan cells covered by the supplied XZ-plane bounding area.
 508    /// </summary>
 509    public static void GetCoveredScanCellsInto(
 510        GridWorld world,
 511        Vector2d boundsMin,
 512        Vector2d boundsMax,
 513        SwiftList<ScanCell> results,
 514        Fixed64 layerY = default,
 515        Fixed64? padding = null)
 516    {
 2517        (Vector3d min, Vector3d max) = GridPlane2d.ToWorldBounds(boundsMin, boundsMax, layerY);
 2518        GetCoveredScanCellsInto(world, min, max, results, padding);
 2519    }
 520
 521    /// <summary>
 522    /// Clears and fills caller-owned storage with scan cells covered by the supplied XZ-plane area.
 523    /// </summary>
 524    public static void GetCoveredScanCellsInto(
 525        GridWorld world,
 526        FixedBoundArea area,
 527        SwiftList<ScanCell> results,
 528        Fixed64 layerY = default,
 529        Fixed64? padding = null)
 530    {
 1531        GetCoveredScanCellsInto(world, area.Min, area.Max, results, layerY, padding);
 1532    }
 533
 534    /// <summary>
 535    /// Clears and fills caller-owned storage using caller-owned scratch collections.
 536    /// </summary>
 537    public static void GetCoveredScanCellsInto(
 538        GridWorld world,
 539        Vector3d boundsMin,
 540        Vector3d boundsMax,
 541        SwiftList<ScanCell> results,
 542        GridScanScratch scratch,
 543        Fixed64? padding = null)
 544    {
 42545        ChronicleGuard.ThrowIfNull(results, nameof(results));
 41546        ChronicleGuard.ThrowIfNull(scratch, nameof(scratch));
 547
 40548        results.Clear();
 40549        if (world == null || !world.IsActive)
 2550            return;
 551
 38552        AddCoveredScanCellsTo(world, boundsMin, boundsMax, results, scratch, padding);
 38553    }
 554
 555    /// <summary>
 556    /// Clears and fills caller-owned storage using caller-owned scratch collections for an XZ-plane bounding area.
 557    /// </summary>
 558    public static void GetCoveredScanCellsInto(
 559        GridWorld world,
 560        Vector2d boundsMin,
 561        Vector2d boundsMax,
 562        SwiftList<ScanCell> results,
 563        GridScanScratch scratch,
 564        Fixed64 layerY = default,
 565        Fixed64? padding = null)
 566    {
 2567        (Vector3d min, Vector3d max) = GridPlane2d.ToWorldBounds(boundsMin, boundsMax, layerY);
 2568        GetCoveredScanCellsInto(world, min, max, results, scratch, padding);
 2569    }
 570
 571    /// <summary>
 572    /// Clears and fills caller-owned storage using caller-owned scratch collections for an XZ-plane area.
 573    /// </summary>
 574    public static void GetCoveredScanCellsInto(
 575        GridWorld world,
 576        FixedBoundArea area,
 577        SwiftList<ScanCell> results,
 578        GridScanScratch scratch,
 579        Fixed64 layerY = default,
 580        Fixed64? padding = null)
 581    {
 1582        GetCoveredScanCellsInto(world, area.Min, area.Max, results, scratch, layerY, padding);
 1583    }
 584
 585    /// <summary>
 586    /// Appends covered scan cells without allocating an iterator for hot-path callers.
 587    /// </summary>
 588    internal static void AddCoveredScanCellsTo(
 589        GridWorld world,
 590        Vector3d boundsMin,
 591        Vector3d boundsMax,
 592        SwiftList<ScanCell> scanCells,
 593        Fixed64? padding = null)
 594    {
 28595        SwiftHashSet<ScanCell> voxelRedundancyCheck = SwiftHashSetPool<ScanCell>.Shared.Rent();
 28596        SwiftList<ushort> candidateGrids = SwiftListPool<ushort>.Shared.Rent();
 597
 598        try
 599        {
 28600            AddCoveredScanCellsCore(
 28601                world,
 28602                boundsMin,
 28603                boundsMax,
 28604                scanCells,
 28605                candidateGrids,
 28606                voxelRedundancyCheck,
 28607                padding);
 28608        }
 609        finally
 610        {
 28611            SwiftHashSetPool<ScanCell>.Shared.Release(voxelRedundancyCheck);
 28612            SwiftListPool<ushort>.Shared.Release(candidateGrids);
 28613        }
 28614    }
 615
 616    /// <summary>
 617    /// Appends covered scan cells using caller-owned scratch state for allocation-sensitive scans.
 618    /// </summary>
 619    internal static void AddCoveredScanCellsTo(
 620        GridWorld world,
 621        Vector3d boundsMin,
 622        Vector3d boundsMax,
 623        SwiftList<ScanCell> scanCells,
 624        GridScanScratch scratch,
 625        Fixed64? padding = null)
 626    {
 581627        scratch.Clear();
 581628        AddCoveredScanCellsCore(
 581629            world,
 581630            boundsMin,
 581631            boundsMax,
 581632            scanCells,
 581633            scratch.CandidateGrids,
 581634            scratch.ScanCellRedundancy,
 581635            padding);
 581636    }
 637
 638    /// <summary>
 639    /// Appends covered voxels without allocating an iterator for hot-path callers.
 640    /// </summary>
 641    internal static void AddCoveredVoxelsTo(
 642        GridWorld world,
 643        Vector3d boundsMin,
 644        Vector3d boundsMax,
 645        SwiftList<Voxel> voxels,
 646        Fixed64? padding = null)
 647    {
 9648        SwiftHashSet<Voxel> voxelRedundancyCheck = SwiftHashSetPool<Voxel>.Shared.Rent();
 9649        SwiftList<ushort> candidateGrids = SwiftListPool<ushort>.Shared.Rent();
 650
 651        try
 652        {
 9653            AddCoveredVoxelsCore(
 9654                world,
 9655                boundsMin,
 9656                boundsMax,
 9657                voxels,
 9658                candidateGrids,
 9659                voxelRedundancyCheck,
 9660                padding);
 9661        }
 662        finally
 663        {
 9664            SwiftHashSetPool<Voxel>.Shared.Release(voxelRedundancyCheck);
 9665            SwiftListPool<ushort>.Shared.Release(candidateGrids);
 9666        }
 9667    }
 668
 669    /// <summary>
 670    /// Appends covered voxels using caller-owned scratch state for allocation-sensitive coverage scans.
 671    /// </summary>
 672    internal static void AddCoveredVoxelsTo(
 673        GridWorld world,
 674        Vector3d boundsMin,
 675        Vector3d boundsMax,
 676        SwiftList<Voxel> voxels,
 677        GridTraceScratch scratch,
 678        Fixed64? padding = null)
 679    {
 14680        scratch.Clear();
 14681        AddCoveredVoxelsCore(
 14682            world,
 14683            boundsMin,
 14684            boundsMax,
 14685            voxels,
 14686            scratch.CandidateGrids,
 14687            scratch.VoxelRedundancy,
 14688            padding);
 14689    }
 690
 691    private static void AddCoveredVoxelsCore(
 692        GridWorld world,
 693        Vector3d boundsMin,
 694        Vector3d boundsMax,
 695        SwiftList<Voxel> voxels,
 696        SwiftList<ushort> candidateGrids,
 697        SwiftHashSet<Voxel> voxelRedundancyCheck,
 698        Fixed64? padding = null)
 699    {
 23700        (Vector3d queryMin, Vector3d queryMax) =
 23701            CreatePaddedOrderedBounds(boundsMin, boundsMax, padding);
 23702        (Vector3d candidateMin, Vector3d candidateMax) =
 23703            ExpandOrderedBounds(queryMin, queryMax, world.MaxTopologyCellEdge);
 704
 23705        _ = world.CollectGridCandidates(
 23706            candidateMin,
 23707            candidateMax,
 23708            candidateGrids,
 23709            GridWorld.MaxGrids);
 130710        foreach (ushort gridIndex in candidateGrids)
 711        {
 42712            AddCoveredGridVoxels(
 42713                world.ActiveGrids[gridIndex],
 42714                queryMin,
 42715                queryMax,
 42716                voxels,
 42717                voxelRedundancyCheck);
 718        }
 23719    }
 720
 721    private static void AddCoveredScanCellsCore(
 722        GridWorld world,
 723        Vector3d boundsMin,
 724        Vector3d boundsMax,
 725        SwiftList<ScanCell> scanCells,
 726        SwiftList<ushort> candidateGrids,
 727        SwiftHashSet<ScanCell> voxelRedundancyCheck,
 728        Fixed64? padding = null)
 729    {
 633730        (Vector3d queryMin, Vector3d queryMax) =
 633731            CreatePaddedOrderedBounds(boundsMin, boundsMax, padding);
 633732        (Vector3d candidateMin, Vector3d candidateMax) =
 633733            ExpandOrderedBounds(queryMin, queryMax, world.MaxTopologyCellEdge);
 633734        _ = world.CollectGridCandidates(
 633735            candidateMin,
 633736            candidateMax,
 633737            candidateGrids,
 633738            GridWorld.MaxGrids);
 2628739        foreach (ushort gridIndex in candidateGrids)
 740        {
 681741            AddCoveredScanCellsForGrid(
 681742                world.ActiveGrids[gridIndex],
 681743                queryMin,
 681744                queryMax,
 681745                scanCells,
 681746                voxelRedundancyCheck);
 747        }
 633748    }
 749
 750    private static IEnumerable<GridVoxelSet> GetCoveredVoxelsIterator(
 751        GridWorld world,
 752        Vector3d boundsMin,
 753        Vector3d boundsMax,
 754        Fixed64? padding)
 755    {
 202756        SwiftList<GridVoxelSet> gridVoxelSets = SwiftListPool<GridVoxelSet>.Shared.Rent();
 202757        SwiftHashSet<Voxel> voxelRedundancyCheck = SwiftHashSetPool<Voxel>.Shared.Rent();
 202758        SwiftList<ushort> candidateGrids = SwiftListPool<ushort>.Shared.Rent();
 759
 760        try
 761        {
 202762            AddCoveredVoxelsToMapping(
 202763                world,
 202764                boundsMin,
 202765                boundsMax,
 202766                padding,
 202767                gridVoxelSets,
 202768                voxelRedundancyCheck,
 202769                candidateGrids);
 770
 834771            foreach (GridVoxelSet gridVoxelSet in gridVoxelSets)
 215772                yield return gridVoxelSet;
 202773        }
 774        finally
 775        {
 202776            ReleaseGridVoxelSets(gridVoxelSets);
 202777            SwiftHashSetPool<Voxel>.Shared.Release(voxelRedundancyCheck);
 202778            SwiftListPool<ushort>.Shared.Release(candidateGrids);
 202779        }
 202780    }
 781
 782    private static void AddCoveredVoxelsToMapping(
 783        GridWorld world,
 784        Vector3d boundsMin,
 785        Vector3d boundsMax,
 786        Fixed64? padding,
 787        SwiftList<GridVoxelSet> gridVoxelSets,
 788        SwiftHashSet<Voxel> voxelRedundancyCheck,
 789        SwiftList<ushort> candidateGrids)
 790    {
 202791        (Vector3d queryMin, Vector3d queryMax) =
 202792            CreatePaddedOrderedBounds(boundsMin, boundsMax, padding);
 202793        (Vector3d candidateMin, Vector3d candidateMax) =
 202794            ExpandOrderedBounds(queryMin, queryMax, world.MaxTopologyCellEdge);
 795
 202796        _ = world.CollectGridCandidates(
 202797            candidateMin,
 202798            candidateMax,
 202799            candidateGrids,
 202800            GridWorld.MaxGrids);
 842801        foreach (ushort gridIndex in candidateGrids)
 802        {
 219803            AddCoveredVoxelsForGrid(
 219804                world.ActiveGrids[gridIndex],
 219805                queryMin,
 219806                queryMax,
 219807                gridVoxelSets,
 219808                voxelRedundancyCheck);
 809        }
 202810    }
 811
 812    private static IEnumerable<ScanCell> GetCoveredScanCellsIterator(
 813        GridWorld world,
 814        Vector3d boundsMin,
 815        Vector3d boundsMax,
 816        Fixed64? padding)
 817    {
 24818        SwiftList<ScanCell> scanCells = SwiftListPool<ScanCell>.Shared.Rent();
 24819        SwiftHashSet<ScanCell> voxelRedundancyCheck = SwiftHashSetPool<ScanCell>.Shared.Rent();
 24820        SwiftList<ushort> candidateGrids = SwiftListPool<ushort>.Shared.Rent();
 821
 822        try
 823        {
 24824            AddCoveredScanCellsCore(
 24825                world,
 24826                boundsMin,
 24827                boundsMax,
 24828                scanCells,
 24829                candidateGrids,
 24830                voxelRedundancyCheck,
 24831                padding);
 832
 358833            foreach (ScanCell scanCell in scanCells)
 155834                yield return scanCell;
 24835        }
 836        finally
 837        {
 24838            SwiftListPool<ScanCell>.Shared.Release(scanCells);
 24839            SwiftHashSetPool<ScanCell>.Shared.Release(voxelRedundancyCheck);
 24840            SwiftListPool<ushort>.Shared.Release(candidateGrids);
 24841        }
 24842    }
 843}

/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    {
 68131        if (currentGrid.Topology.Kind == GridTopologyKind.HexPrism)
 32        {
 5533            AddCoveredHexScanCellsForGrid(
 5534                currentGrid,
 5535                queryMin,
 5536                queryMax,
 5537                scanCells,
 5538                voxelRedundancyCheck);
 5539            return;
 40        }
 41
 62642        if (!TryGetCoveredScanCellRange(
 62643                currentGrid,
 62644                queryMin,
 62645                queryMax,
 62646                out int xMin,
 62647                out int yMin,
 62648                out int zMin,
 62649                out int xMax,
 62650                out int yMax,
 62651                out int zMax))
 52        {
 353            return;
 54        }
 55
 62356        currentGrid.AddScanCellsInRange(
 62357            xMin,
 62358            yMin,
 62359            zMin,
 62360            xMax,
 62361            yMax,
 62362            zMax,
 62363            scanCells,
 62364            voxelRedundancyCheck);
 62365    }
 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    {
 26195        if (currentGrid.Topology.Kind == GridTopologyKind.HexPrism)
 96        {
 1597            AddCoveredHexGridVoxels(
 1598                currentGrid,
 1599                queryMin,
 15100                queryMax,
 15101                voxelList);
 15102            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    {
 15128        if (!TopologyVoxelRangeUtility.TryGetCandidateRange(
 15129                currentGrid,
 15130                queryMin,
 15131                queryMax,
 15132                out VoxelIndex minIndex,
 15133                out VoxelIndex maxIndex))
 134        {
 1135            return;
 136        }
 137
 14138        Fixed64 horizontalExpansion =
 14139            currentGrid.Topology.Metrics.CellRadius;
 14140        Fixed64 coverageMinX = queryMin.X - horizontalExpansion;
 14141        Fixed64 coverageMaxX = queryMax.X + horizontalExpansion;
 14142        Fixed64 coverageMinZ = queryMin.Z - horizontalExpansion;
 14143        Fixed64 coverageMaxZ = queryMax.Z + horizontalExpansion;
 144
 116145        for (long x = minIndex.x; x <= maxIndex.x; x++)
 146        {
 176147            for (long y = minIndex.y; y <= maxIndex.y; y++)
 148            {
 436149                for (long z = minIndex.z; z <= maxIndex.z; z++)
 150                {
 174151                    if (currentGrid.TryGetVoxel(
 174152                            (int)x,
 174153                            (int)y,
 174154                            (int)z,
 174155                            out Voxel? voxel)
 174156                        && IsHexVoxelCenterInHorizontalCoverage(
 174157                            voxel!,
 174158                            coverageMinX,
 174159                            coverageMaxX,
 174160                            coverageMinZ,
 174161                            coverageMaxZ))
 162                    {
 19163                        voxelList.Add(voxel!);
 164                    }
 165                }
 166            }
 167        }
 14168    }
 169
 170    private static void AddCoveredHexScanCellsForGrid(
 171        VoxelGrid currentGrid,
 172        Vector3d queryMin,
 173        Vector3d queryMax,
 174        SwiftList<ScanCell> scanCells,
 175        SwiftHashSet<ScanCell> scanCellRedundancyCheck)
 176    {
 55177        if (!TopologyVoxelRangeUtility.TryGetCandidateRange(
 55178                currentGrid,
 55179                queryMin,
 55180                queryMax,
 55181                out VoxelIndex minIndex,
 55182                out VoxelIndex maxIndex))
 183        {
 1184            return;
 185        }
 186
 54187        currentGrid.AddScanCellsInRange(
 54188            minIndex.x / currentGrid.ScanCellSize,
 54189            minIndex.y / currentGrid.ScanCellSize,
 54190            minIndex.z / currentGrid.ScanCellSize,
 54191            maxIndex.x / currentGrid.ScanCellSize,
 54192            maxIndex.y / currentGrid.ScanCellSize,
 54193            maxIndex.z / currentGrid.ScanCellSize,
 54194            scanCells,
 54195            scanCellRedundancyCheck);
 54196    }
 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    {
 172206        Vector3d position = voxel.WorldPosition;
 172207        return position.X >= coverageMinX
 172208            && position.X <= coverageMaxX
 172209            && position.Z >= coverageMinZ
 172210            && 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.Configuration;
 13using GridForge.Grids;
 14using GridForge.Grids.Storage;
 15using GridForge.Grids.Topology;
 16using GridForge.Spatial;
 17using SwiftCollections;
 18
 19namespace GridForge.Utility;
 20
 21/// <content>Provides bounded swept navigation-body coverage.</content>
 22public static partial class GridTracer
 23{
 24    /// <summary>Writes the canonical cells required by one direct upright-body sweep.</summary>
 25    /// <remarks>
 26    /// The start and end bodies must have closed-set contact with the declared source and target
 27    /// prisms respectively; exact endpoint tangency is admitted for that identity check.
 28    /// A prism is claimed only when its planar and vertical interiors overlap the swept body at
 29    /// one shared continuous parameter. Boundary-only coincidence and tangency are excluded.
 30    /// Grid, address, output, and combined candidate-work ceilings are independent.
 31    /// </remarks>
 32    public static GridNavigationBodyTraceReport TraceNavigationBodyInto(
 33        GridWorld world,
 34        WorldVoxelIndex source,
 35        WorldVoxelIndex target,
 36        Vector3d startFoot,
 37        Vector3d endFoot,
 38        Fixed64 horizontalRadius,
 39        Fixed64 bodyHeight,
 40        SwiftList<GridNavigationBodyTraceCell> results,
 41        GridNavigationBodyTraceScratch scratch,
 42        int gridCandidateLimit,
 43        int addressCandidateLimit,
 44        int outputLimit,
 45        long candidateWorkLimit) =>
 9046        TraceNavigationBodyInto(world, source, target, startFoot, endFoot, horizontalRadius, bodyHeight,
 9047            results, scratch, gridCandidateLimit, addressCandidateLimit, outputLimit, candidateWorkLimit,
 9048            excludedGridSpawnTokens: null);
 49
 50    /// <summary>Writes upright-body coverage while excluding the supplied exact grid generations.</summary>
 51    /// <remarks>
 52    /// Supply <see cref="VoxelGrid.SpawnToken"/> values from the given world and keep the set unchanged until the trace
 53    /// An excluded generation cannot provide prism coverage or cell dependency evidence. Its broad-phase
 54    /// candidate still counts toward the grid and combined limits, with no address work charged.
 55    /// An excluded source or target invalidates the trace. An old token never excludes a replacement grid.
 56    /// The optional `excludedGridCandidates` list is cleared first and receives the configuration keys
 57    /// of excluded grids encountered during candidate traversal. An aborted trace can leave only a prefix.
 58    /// </remarks>
 59    public static GridNavigationBodyTraceReport TraceNavigationBodyInto(
 60        GridWorld world,
 61        WorldVoxelIndex source,
 62        WorldVoxelIndex target,
 63        Vector3d startFoot,
 64        Vector3d endFoot,
 65        Fixed64 horizontalRadius,
 66        Fixed64 bodyHeight,
 67        SwiftList<GridNavigationBodyTraceCell> results,
 68        GridNavigationBodyTraceScratch scratch,
 69        int gridCandidateLimit,
 70        int addressCandidateLimit,
 71        int outputLimit,
 72        long candidateWorkLimit,
 73        SwiftPackedSet<long>? excludedGridSpawnTokens,
 74        SwiftList<GridConfigurationKey>? excludedGridCandidates = null)
 75    {
 10676        ChronicleGuard.ThrowIfNull(results, nameof(results));
 10677        ChronicleGuard.ThrowIfNull(scratch, nameof(scratch));
 10678        ChronicleGuard.ThrowIfNegative(gridCandidateLimit, nameof(gridCandidateLimit));
 10579        ChronicleGuard.ThrowIfNegative(addressCandidateLimit, nameof(addressCandidateLimit));
 10480        ChronicleGuard.ThrowIfNegative(outputLimit, nameof(outputLimit));
 10381        if (candidateWorkLimit < 0L)
 182            throw new ArgumentOutOfRangeException(nameof(candidateWorkLimit));
 83
 10284        results.Clear();
 10285        scratch.Clear();
 10286        excludedGridCandidates?.Clear();
 10287        if (world == null
 10288            || !world.IsActive
 10289            || horizontalRadius < Fixed64.Zero
 10290            || bodyHeight <= Fixed64.Zero
 10291            || (excludedGridSpawnTokens != null
 10292                && (excludedGridSpawnTokens.Contains(source.GridSpawnToken)
 10293                    || excludedGridSpawnTokens.Contains(target.GridSpawnToken))))
 94        {
 795            return CreateNavigationBodyTraceReport(
 796                GridNavigationBodyTraceStatus.InvalidOrUnrepresentableGeometry,
 797                0,
 798                0,
 799                results,
 7100                default);
 101        }
 102
 95103        if (!Fixed64.TryAdd(startFoot.Y, bodyHeight, out Fixed64 startTop)
 95104            || !Fixed64.TryAdd(endFoot.Y, bodyHeight, out Fixed64 endTop)
 95105            || !TryCreateNavigationBodyBounds(
 95106                startFoot,
 95107                endFoot,
 95108                startTop,
 95109                endTop,
 95110                horizontalRadius,
 95111                out Vector3d queryMin,
 95112                out Vector3d queryMax))
 113        {
 8114            return CreateNavigationBodyTraceReport(
 8115                GridNavigationBodyTraceStatus.ArithmeticOverflow,
 8116                0,
 8117                0,
 8118                results,
 8119                default);
 120        }
 121
 122        // Closed bounds reject only disjoint prisms; exact continuous overlap remains the narrow phase.
 87123        TopologyVoxelAabb bodyBounds = new TopologyVoxelAabb(queryMin, queryMax);
 87124        world.EnterReadLock();
 125        try
 126        {
 87127            if (!world.TryGetGrid(source, out VoxelGrid? sourceGridValue)
 87128                || !world.TryGetGrid(target, out VoxelGrid? targetGridValue))
 129            {
 1130                return FailNavigationBodyTrace(
 1131                    results,
 1132                    GridNavigationBodyTraceStatus.InvalidOrUnrepresentableGeometry,
 1133                    0,
 1134                    0,
 1135                    default);
 136            }
 137
 86138            VoxelGrid sourceGrid = sourceGridValue!;
 86139            VoxelGrid targetGrid = targetGridValue!;
 86140            if (!GridCellGeometry.TryCreatePrism(
 86141                    sourceGrid.Configuration.TopologyKind,
 86142                    sourceGrid.Configuration.TopologyMetrics,
 86143                    sourceGrid.GetWorldPosition(source.VoxelIndex),
 86144                    source,
 86145                    out GridCellPrism sourcePrism)
 86146                || !GridCellGeometry.TryCreatePrism(
 86147                    targetGrid.Configuration.TopologyKind,
 86148                    targetGrid.Configuration.TopologyMetrics,
 86149                    targetGrid.GetWorldPosition(target.VoxelIndex),
 86150                    target,
 86151                    out GridCellPrism targetPrism))
 152            {
 2153                return FailNavigationBodyTrace(
 2154                    results,
 2155                    GridNavigationBodyTraceStatus.InvalidOrUnrepresentableGeometry,
 2156                    0,
 2157                    0,
 2158                    default);
 159            }
 160
 84161            if (!HasClosedNavigationBodyPrismContact(
 84162                    sourcePrism,
 84163                    startFoot,
 84164                    startTop,
 84165                    horizontalRadius)
 84166                || !HasClosedNavigationBodyPrismContact(
 84167                    targetPrism,
 84168                    endFoot,
 84169                    endTop,
 84170                    horizontalRadius))
 171            {
 5172                return FailNavigationBodyTrace(
 5173                    results,
 5174                    GridNavigationBodyTraceStatus.InvalidOrUnrepresentableGeometry,
 5175                    0,
 5176                    0,
 5177                    default);
 178            }
 179
 79180            Span<GridCellPrism> closurePrisms = stackalloc GridCellPrism[8];
 79181            int closureCount = GetNavigationClosure(
 79182                sourceGrid,
 79183                sourcePrism,
 79184                targetPrism,
 79185                closurePrisms);
 79186            if (closureCount == 0)
 187            {
 2188                return FailNavigationBodyTrace(
 2189                    results,
 2190                    GridNavigationBodyTraceStatus.InvalidOrUnrepresentableGeometry,
 2191                    0,
 2192                    0,
 2193                    default);
 194            }
 195
 77196            if (!TryExpandNavigationBodyBounds(
 77197                    queryMin,
 77198                    queryMax,
 77199                    world.MaxTopologyCellEdge,
 77200                    out Vector3d candidateMin,
 77201                    out Vector3d candidateMax))
 202            {
 7203                return FailNavigationBodyTrace(
 7204                    results,
 7205                    GridNavigationBodyTraceStatus.ArithmeticOverflow,
 7206                    0,
 7207                    0,
 7208                    default);
 209            }
 210
 70211            bool gridWorkLimitIsTighter = candidateWorkLimit < gridCandidateLimit;
 70212            int effectiveGridLimit = gridWorkLimitIsTighter
 70213                ? (int)candidateWorkLimit
 70214                : gridCandidateLimit;
 70215            if (!world.CollectGridCandidates(
 70216                    candidateMin,
 70217                    candidateMax,
 70218                    scratch.CandidateGrids,
 70219                    effectiveGridLimit))
 220            {
 5221                return FailNavigationBodyTrace(
 5222                    results,
 5223                    gridWorkLimitIsTighter
 5224                        ? GridNavigationBodyTraceStatus.CandidateWorkLimitExceeded
 5225                        : GridNavigationBodyTraceStatus.GridCandidateLimitExceeded,
 5226                    scratch.CandidateGrids.Count,
 5227                    0,
 5228                    default);
 229            }
 230
 65231            SortGridIndices(world, scratch.CandidateGrids);
 65232            long remainingWork = candidateWorkLimit - scratch.CandidateGrids.Count;
 65233            bool workLimitIsTighter = remainingWork < addressCandidateLimit;
 65234            int effectiveAddressLimit = workLimitIsTighter
 65235                ? (int)remainingWork
 65236                : addressCandidateLimit;
 65237            int addressCandidateCount = 0;
 316238            for (int gridOrdinal = 0; gridOrdinal < scratch.CandidateGrids.Count; gridOrdinal++)
 239            {
 98240                VoxelGrid grid = world.ActiveGrids[scratch.CandidateGrids[gridOrdinal]];
 98241                if (excludedGridSpawnTokens != null && excludedGridSpawnTokens.Contains(grid.SpawnToken))
 242                {
 6243                    excludedGridCandidates?.Add(grid.Configuration.ToGridKey());
 4244                    continue;
 245                }
 92246                if (!TopologyVoxelRangeUtility.TryGetPrismCandidateRange(
 92247                        grid,
 92248                        queryMin,
 92249                        queryMax,
 92250                        out VoxelIndex minimum,
 92251                        out VoxelIndex maximum))
 252                {
 253                    continue;
 254                }
 255
 590256                for (int x = minimum.x; x <= maximum.x; x++)
 257                {
 914258                    for (int y = minimum.y; y <= maximum.y; y++)
 259                    {
 1884260                        for (int z = minimum.z; z <= maximum.z; z++)
 261                        {
 693262                            if (addressCandidateCount >= effectiveAddressLimit)
 263                            {
 4264                                return FailNavigationBodyTrace(
 4265                                    results,
 4266                                    workLimitIsTighter
 4267                                        ? GridNavigationBodyTraceStatus.CandidateWorkLimitExceeded
 4268                                        : GridNavigationBodyTraceStatus.AddressLimitExceeded,
 4269                                    scratch.CandidateGrids.Count,
 4270                                    addressCandidateCount,
 4271                                    default);
 272                            }
 273
 689274                            addressCandidateCount++;
 689275                            VoxelIndex index = new(x, y, z);
 689276                            WorldVoxelIndex cell = new(
 689277                                world.SpawnToken,
 689278                                grid.GridIndex,
 689279                                grid.SpawnToken,
 689280                                index);
 689281                            if (!GridCellGeometry.TryCreatePrism(
 689282                                    grid.Configuration.TopologyKind,
 689283                                    grid.Configuration.TopologyMetrics,
 689284                                    grid.GetWorldPosition(index),
 689285                                    cell,
 689286                                    out GridCellPrism prism))
 287                            {
 1288                                return FailNavigationBodyTrace(
 1289                                    results,
 1290                                    GridNavigationBodyTraceStatus.InvalidOrUnrepresentableGeometry,
 1291                                    scratch.CandidateGrids.Count,
 1292                                    addressCandidateCount,
 1293                                    default);
 294                            }
 295
 688296                            bool hasPositiveOverlap = bodyBounds.Overlaps(prism.GetAabb(), Fixed64.Zero)
 688297                                && GridCellGeometry.HasPositiveNavigationBodyPrismOverlap(
 688298                                    prism,
 688299                                    startFoot,
 688300                                    endFoot,
 688301                                    horizontalRadius,
 688302                                    bodyHeight);
 688303                            bool isClosure = IsNavigationClosurePrism(
 688304                                prism,
 688305                                closurePrisms,
 688306                                closureCount);
 688307                            if (!hasPositiveOverlap && !isClosure)
 308                                continue;
 309
 339310                            scratch.AddressCandidates.Add(new GridNavigationBodyTraceCandidate(
 339311                                grid,
 339312                                index,
 339313                                prism,
 339314                                hasPositiveOverlap,
 339315                                isClosure));
 316                        }
 317                    }
 318                }
 319            }
 320
 60321            GridCoveredAddressRunStamp runStamp = SnapshotNavigationBodyCandidates(
 60322                world,
 60323                scratch.AddressCandidates);
 60324            scratch.AddressCandidates.SortInPlace(
 60325                default(GridNavigationBodyTraceCandidateComparer));
 60326            if (!HasNavigationBodyUnionCoverage(
 60327                    sourceGrid,
 60328                    source.VoxelIndex,
 60329                    targetGrid,
 60330                    target.VoxelIndex,
 60331                    startFoot,
 60332                    endFoot,
 60333                    horizontalRadius,
 60334                    bodyHeight,
 60335                    bodyBounds,
 60336                    scratch.AddressCandidates,
 60337                    scratch.UnionMembers))
 338            {
 2339                return FailNavigationBodyTrace(
 2340                    results,
 2341                    GridNavigationBodyTraceStatus.InvalidOrUnrepresentableGeometry,
 2342                    scratch.CandidateGrids.Count,
 2343                    addressCandidateCount,
 2344                    default);
 345            }
 58346            int alternativeEvidenceCount = CountMissingNavigationBodyAlternativeEvidence(
 58347                scratch.AddressCandidates,
 58348                sourceGrid,
 58349                source.VoxelIndex,
 58350                targetGrid,
 58351                target.VoxelIndex);
 58352            if (scratch.UnionMembers.Count > outputLimit
 58353                || alternativeEvidenceCount > outputLimit - scratch.UnionMembers.Count)
 354            {
 2355                return FailNavigationBodyTrace(
 2356                    results,
 2357                    GridNavigationBodyTraceStatus.OutputLimitExceeded,
 2358                    scratch.CandidateGrids.Count,
 2359                    addressCandidateCount,
 2360                    default);
 361            }
 362
 56363            bool hasMissingPhysicalCell = false;
 610364            for (int i = 0; i < scratch.UnionMembers.Count; i++)
 365            {
 249366                GridNavigationBodyTraceCandidate candidate =
 249367                    scratch.AddressCandidates[scratch.UnionMembers[i]];
 249368                hasMissingPhysicalCell |= !candidate.IsPhysicallyPresent;
 249369                results.Add(new GridNavigationBodyTraceCell(
 249370                    new WorldVoxelIndex(
 249371                        world.SpawnToken,
 249372                        candidate.Grid.GridIndex,
 249373                        candidate.Grid.SpawnToken,
 249374                        candidate.Index),
 249375                    candidate.Grid.Configuration.ToGridKey(),
 249376                    candidate.IsPhysicallyPresent,
 249377                    candidate.GridLastChangeSequence,
 249378                    GridNavigationBodyTraceCellRole.RequiredCoverage));
 379            }
 380
 56381            if (hasMissingPhysicalCell)
 382            {
 12383                AppendMissingNavigationBodyAlternativeEvidence(
 12384                    world,
 12385                    scratch.AddressCandidates,
 12386                    results,
 12387                    sourceGrid,
 12388                    source.VoxelIndex,
 12389                    targetGrid,
 12390                    target.VoxelIndex);
 391            }
 392
 56393            results.SortInPlace(default(GridNavigationBodyTraceCellComparer));
 56394            return CreateNavigationBodyTraceReport(
 56395                hasMissingPhysicalCell
 56396                    ? GridNavigationBodyTraceStatus.IncompletePhysicalCoverage
 56397                    : GridNavigationBodyTraceStatus.Complete,
 56398                scratch.CandidateGrids.Count,
 56399                addressCandidateCount,
 56400                results,
 56401                runStamp);
 402        }
 403        finally
 404        {
 87405            world.ExitReadLock();
 87406            scratch.Clear();
 87407        }
 87408    }
 409
 410    private static bool HasClosedNavigationBodyPrismContact(
 411        in GridCellPrism prism,
 412        Vector3d foot,
 413        Fixed64 bodyTop,
 414        Fixed64 horizontalRadius)
 415    {
 163416        if (foot.Y > prism.VerticalMax || bodyTop < prism.VerticalMin)
 1417            return false;
 418
 162419        Span<Vector2d> offsets = stackalloc Vector2d[6];
 162420        Vector2d planarOrigin = new(prism.Center.X, prism.Center.Z);
 1684421        for (int i = 0; i < prism.FootprintVertexCount; i++)
 680422            offsets[i] = prism.GetFootprintVertex(i) - planarOrigin;
 423
 162424        return FixedConvex2dRelations.TryGetCircleContact(
 162425            new Vector2d(foot.X, foot.Z),
 162426            Fixed64.Zero,
 162427            horizontalRadius,
 162428            planarOrigin,
 162429            Fixed64.Zero,
 162430            offsets[..prism.FootprintVertexCount],
 162431            out _,
 162432            out _,
 162433            out _,
 162434            out _,
 162435            out _);
 436    }
 437
 438    private static int GetNavigationClosure(
 439        VoxelGrid sourceGrid,
 440        in GridCellPrism source,
 441        in GridCellPrism target,
 442        Span<GridCellPrism> closure)
 443    {
 79444        Span<VoxelIndex> offsets = stackalloc VoxelIndex[8];
 79445        VoxelIndex targetOffset = default;
 79446        bool foundTarget = AreSameNavigationBodyPrism(source, target);
 602447        for (int slot = 0; !foundTarget && slot < sourceGrid.Topology.NeighborSlotCount; slot++)
 448        {
 223449            VoxelIndex offset = sourceGrid.Topology.GetNeighborOffset(slot);
 223450            if (!Vector3d.TryAdd(
 223451                    source.Center,
 223452                    sourceGrid.Topology.GetWorldOffset((offset.x, offset.y, offset.z)),
 223453                    out Vector3d center)
 223454                || !GridCellGeometry.TryCreatePrism(
 223455                    sourceGrid.Configuration.TopologyKind,
 223456                    sourceGrid.Configuration.TopologyMetrics,
 223457                    center,
 223458                    default,
 223459                    out GridCellPrism neighbor))
 460            {
 1461                return 0;
 462            }
 222463            if (AreSameNavigationBodyPrism(neighbor, target))
 464            {
 25465                targetOffset = offset;
 25466                foundTarget = true;
 467            }
 468        }
 78469        if (!foundTarget)
 1470            return 0;
 471
 472        int closureCount;
 77473        if (targetOffset == default)
 474        {
 52475            offsets[0] = default;
 52476            closureCount = 1;
 477        }
 25478        else if (sourceGrid.Configuration.TopologyKind == GridTopologyKind.RectangularPrism)
 479        {
 23480            RectangularDirection direction = RectangularDirectionUtility.GetDirectionFromOffset(
 23481                (targetOffset.x, targetOffset.y, targetOffset.z));
 23482            closureCount = RectangularDirectionUtility.CopyNavigationClosureOffsets(direction, offsets);
 483        }
 484        else
 485        {
 2486            closureCount = HexDirectionUtility.CopyNavigationClosureOffsets(targetOffset, offsets);
 487        }
 488
 418489        for (int i = 0; i < closureCount; i++)
 490        {
 132491            VoxelIndex offset = offsets[i];
 132492            bool usesTargetPlanarCoordinates = offset.x != 0 || offset.z != 0;
 132493            Vector3d center = sourceGrid.Configuration.TopologyKind == GridTopologyKind.RectangularPrism
 132494                ? new Vector3d(
 132495                    offset.x == 0 ? source.Center.X : target.Center.X,
 132496                    offset.y == 0 ? source.Center.Y : target.Center.Y,
 132497                    offset.z == 0 ? source.Center.Z : target.Center.Z)
 132498                : new Vector3d(
 132499                    usesTargetPlanarCoordinates ? target.Center.X : source.Center.X,
 132500                    offset.y == 0 ? source.Center.Y : target.Center.Y,
 132501                    usesTargetPlanarCoordinates ? target.Center.Z : source.Center.Z);
 502
 503            // Every coordinate comes from one of the two already validated endpoint prisms.
 132504            _ = GridCellGeometry.TryCreatePrism(
 132505                sourceGrid.Configuration.TopologyKind,
 132506                sourceGrid.Configuration.TopologyMetrics,
 132507                center,
 132508                default,
 132509                out closure[i]);
 510        }
 511
 77512        return closureCount;
 513    }
 514
 515    private static bool IsNavigationClosurePrism(
 516        in GridCellPrism prism,
 517        ReadOnlySpan<GridCellPrism> closure,
 518        int count)
 519    {
 9080520        for (int i = 0; i < count; i++)
 521        {
 2801522            if (AreSameNavigationBodyPrism(prism, closure[i]))
 433523                return true;
 524        }
 525
 1739526        return false;
 527    }
 528
 529    private static GridCoveredAddressRunStamp SnapshotNavigationBodyCandidates(
 530        GridWorld world,
 531        SwiftList<GridNavigationBodyTraceCandidate> candidates)
 532    {
 533        GridCoveredAddressRunStamp runStamp;
 261534        lock (world.ChangeSyncRoot)
 535        {
 261536            runStamp = new GridCoveredAddressRunStamp(
 261537                world.SpawnToken,
 261538                world.Version,
 261539                world.ChangeSequence);
 3932540            for (int i = 0; i < candidates.Count; i++)
 541            {
 1705542                GridNavigationBodyTraceCandidate candidate = candidates[i];
 1705543                bool isPresent = candidate.Grid.StorageKind == GridStorageKind.Dense
 1705544                    || candidate.Grid.TryGetVoxel(candidate.Index, out _);
 1705545                candidates[i] = candidate.WithPhysicalEvidence(
 1705546                    isPresent,
 1705547                    candidate.Grid.LastChangeSequence);
 548            }
 261549        }
 550
 261551        return runStamp;
 552    }
 553
 554    private static bool TryCreateNavigationBodyBounds(
 555        Vector3d startFoot,
 556        Vector3d endFoot,
 557        Fixed64 startTop,
 558        Fixed64 endTop,
 559        Fixed64 radius,
 560        out Vector3d minimum,
 561        out Vector3d maximum)
 562    {
 92563        minimum = default;
 92564        maximum = default;
 92565        return Fixed64.TrySubtract(FixedMath.Min(startFoot.X, endFoot.X), radius, out Fixed64 minX)
 92566            && Fixed64.TrySubtract(FixedMath.Min(startFoot.Z, endFoot.Z), radius, out Fixed64 minZ)
 92567            && Fixed64.TryAdd(FixedMath.Max(startFoot.X, endFoot.X), radius, out Fixed64 maxX)
 92568            && Fixed64.TryAdd(FixedMath.Max(startFoot.Z, endFoot.Z), radius, out Fixed64 maxZ)
 92569            && AssignNavigationBodyBounds(
 92570                minX,
 92571                FixedMath.Min(startFoot.Y, endFoot.Y),
 92572                minZ,
 92573                maxX,
 92574                FixedMath.Max(startTop, endTop),
 92575                maxZ,
 92576                out minimum,
 92577                out maximum);
 578    }
 579
 580    private static bool AssignNavigationBodyBounds(
 581        Fixed64 minX,
 582        Fixed64 minY,
 583        Fixed64 minZ,
 584        Fixed64 maxX,
 585        Fixed64 maxY,
 586        Fixed64 maxZ,
 587        out Vector3d minimum,
 588        out Vector3d maximum)
 589    {
 87590        minimum = new Vector3d(minX, minY, minZ);
 87591        maximum = new Vector3d(maxX, maxY, maxZ);
 87592        return true;
 593    }
 594
 595    private static bool TryExpandNavigationBodyBounds(
 596        Vector3d minimum,
 597        Vector3d maximum,
 598        Fixed64 expansion,
 599        out Vector3d expandedMinimum,
 600        out Vector3d expandedMaximum)
 601    {
 77602        if (!Fixed64.TrySubtract(minimum.X, expansion, out Fixed64 minX)
 77603            || !Fixed64.TrySubtract(minimum.Y, expansion, out Fixed64 minY)
 77604            || !Fixed64.TrySubtract(minimum.Z, expansion, out Fixed64 minZ)
 77605            || !Fixed64.TryAdd(maximum.X, expansion, out Fixed64 maxX)
 77606            || !Fixed64.TryAdd(maximum.Y, expansion, out Fixed64 maxY)
 77607            || !Fixed64.TryAdd(maximum.Z, expansion, out Fixed64 maxZ))
 608        {
 7609            expandedMinimum = default;
 7610            expandedMaximum = default;
 7611            return false;
 612        }
 613
 70614        expandedMinimum = new Vector3d(minX, minY, minZ);
 70615        expandedMaximum = new Vector3d(maxX, maxY, maxZ);
 70616        return true;
 617    }
 618
 619    private static bool HasNavigationBodyUnionCoverage(
 620        VoxelGrid sourceGrid,
 621        VoxelIndex source,
 622        VoxelGrid targetGrid,
 623        VoxelIndex target,
 624        Vector3d startFoot,
 625        Vector3d endFoot,
 626        Fixed64 horizontalRadius,
 627        Fixed64 bodyHeight,
 628        TopologyVoxelAabb bodyBounds,
 629        SwiftList<GridNavigationBodyTraceCandidate> candidates,
 630        SwiftList<int> unionMembers)
 631    {
 60632        int sourceCandidate = FindNavigationBodyCandidate(candidates, sourceGrid, source);
 60633        int targetCandidate = FindNavigationBodyCandidate(candidates, targetGrid, target);
 634        // A connected body intersects a connected set of interiors in the source topology's
 635        // exact lattice. Closing every positive-overlap neighbor therefore proves containment;
 636        // exact coincident prisms let aligned adjacent grids continue the same lattice.
 60637        AddNavigationBodyUnionMember(candidates, unionMembers, sourceCandidate);
 60638        if (targetCandidate != sourceCandidate
 60639            && AreSameNavigationBodyPrism(
 60640                candidates[sourceCandidate].Prism,
 60641                candidates[targetCandidate].Prism))
 642        {
 2643            AddNavigationBodyUnionMember(candidates, unionMembers, targetCandidate);
 644        }
 654645        for (int memberOrdinal = 0; memberOrdinal < unionMembers.Count; memberOrdinal++)
 646        {
 269647            GridCellPrism member = candidates[unionMembers[memberOrdinal]].Prism;
 14264648            for (int slot = 0; slot < sourceGrid.Topology.NeighborSlotCount; slot++)
 649            {
 6865650                VoxelIndex offset = sourceGrid.Topology.GetNeighborOffset(slot);
 651                // Candidate bounds were expanded by the world's maximum topology edge, so every
 652                // immediate neighbor of a selected member is exactly representable here.
 6865653                _ = Vector3d.TryAdd(
 6865654                    member.Center,
 6865655                    sourceGrid.Topology.GetWorldOffset((offset.x, offset.y, offset.z)),
 6865656                    out Vector3d neighborCenter);
 6865657                _ = GridCellGeometry.TryCreatePrism(
 6865658                    sourceGrid.Configuration.TopologyKind,
 6865659                    sourceGrid.Configuration.TopologyMetrics,
 6865660                    neighborCenter,
 6865661                    default,
 6865662                    out GridCellPrism neighbor);
 663
 6865664                int matchingCandidate = FindBestMatchingNavigationBodyPrism(
 6865665                    candidates,
 6865666                    neighbor,
 6865667                    sourceCandidate,
 6865668                    targetCandidate);
 6865669                bool overlapsBody = matchingCandidate >= 0
 6865670                    ? candidates[matchingCandidate].HasPositiveOverlap
 6865671                    : bodyBounds.Overlaps(neighbor.GetAabb(), Fixed64.Zero)
 6865672                        && GridCellGeometry.HasPositiveNavigationBodyPrismOverlap(
 6865673                            neighbor,
 6865674                            startFoot,
 6865675                            endFoot,
 6865676                            horizontalRadius,
 6865677                            bodyHeight);
 6865678                if (overlapsBody && matchingCandidate < 0)
 2679                    return false;
 6863680                if (matchingCandidate >= 0
 6863681                    && !candidates[matchingCandidate].IsVisited)
 682                {
 207683                    AddNavigationBodyUnionMember(candidates, unionMembers, matchingCandidate);
 684                }
 685            }
 686        }
 687
 58688        return true;
 689    }
 690
 691    private static int FindNavigationBodyCandidate(
 692        SwiftList<GridNavigationBodyTraceCandidate> candidates,
 693        VoxelGrid grid,
 694        VoxelIndex index)
 695    {
 1954696        for (int i = 0; ; i++)
 697        {
 1954698            GridNavigationBodyTraceCandidate candidate = candidates[i];
 1954699            if (candidate.Grid == grid && candidate.Index == index)
 522700                return i;
 701        }
 702    }
 703
 704    private static int FindBestMatchingNavigationBodyPrism(
 705        SwiftList<GridNavigationBodyTraceCandidate> candidates,
 706        in GridCellPrism prism,
 707        int sourceCandidate,
 708        int targetCandidate)
 709    {
 17686710        if (AreSameNavigationBodyPrism(candidates[sourceCandidate].Prism, prism))
 1358711            return sourceCandidate;
 16328712        if (AreSameNavigationBodyPrism(candidates[targetCandidate].Prism, prism))
 181713            return targetCandidate;
 714
 16147715        if (!FindNavigationBodyPrismRange(candidates, prism, out int start, out int end))
 11025716            return -1;
 717
 5122718        int best = start;
 10566719        for (int i = start + 1; i < end; i++)
 720        {
 161721            if (IsPreferredNavigationBodyCandidate(candidates[i], candidates[best]))
 17722                best = i;
 723        }
 724
 5122725        return best;
 726    }
 727
 728    private static bool IsPreferredNavigationBodyCandidate(
 729        GridNavigationBodyTraceCandidate candidate,
 730        GridNavigationBodyTraceCandidate current)
 731    {
 161732        if (candidate.IsPhysicallyPresent != current.IsPhysicallyPresent)
 27733            return candidate.IsPhysicallyPresent;
 734
 134735        return CompareGridIdentity(candidate.Grid, current.Grid) < 0;
 736    }
 737
 738    private static bool AreSameNavigationBodyPrism(
 739        in GridCellPrism first,
 37706740        in GridCellPrism second) => CompareNavigationBodyPrisms(first, second) == 0;
 741
 742    private static int CompareNavigationBodyPrisms(
 743        in GridCellPrism first,
 744        in GridCellPrism second)
 745    {
 117934746        int comparison = (int)first.TopologyKind - (int)second.TopologyKind;
 117934747        if (comparison != 0)
 42748            return comparison;
 117892749        comparison = first.Center.X.CompareTo(second.Center.X);
 117892750        if (comparison != 0)
 67697751            return comparison;
 50195752        comparison = first.Center.Y.CompareTo(second.Center.Y);
 50195753        if (comparison != 0)
 11322754            return comparison;
 38873755        comparison = first.Center.Z.CompareTo(second.Center.Z);
 38873756        if (comparison != 0)
 26012757            return comparison;
 12861758        comparison = first.VerticalMin.CompareTo(second.VerticalMin);
 12861759        if (comparison != 0)
 3760            return comparison;
 12858761        comparison = first.PlanarInradius.CompareTo(second.PlanarInradius);
 12858762        if (comparison != 0)
 3763            return comparison;
 764
 129558765        for (int i = 0; i < first.FootprintVertexCount; i++)
 766        {
 51931767            Vector2d firstVertex = first.GetFootprintVertex(i);
 51931768            Vector2d secondVertex = second.GetFootprintVertex(i);
 51931769            comparison = firstVertex.X.CompareTo(secondVertex.X);
 51931770            if (comparison != 0)
 3771                return comparison;
 51928772            comparison = firstVertex.Y.CompareTo(secondVertex.Y);
 51928773            if (comparison != 0)
 4774                return comparison;
 775        }
 776
 12848777        return 0;
 778    }
 779
 780    private static bool FindNavigationBodyPrismRange(
 781        SwiftList<GridNavigationBodyTraceCandidate> candidates,
 782        in GridCellPrism prism,
 783        out int start,
 784        out int end)
 785    {
 16147786        int low = 0;
 16147787        int high = candidates.Count;
 68999788        while (low < high)
 789        {
 52852790            int middle = low + ((high - low) >> 1);
 52852791            if (CompareNavigationBodyPrisms(candidates[middle].Prism, prism) < 0)
 21493792                low = middle + 1;
 793            else
 31359794                high = middle;
 795        }
 796
 16147797        start = low;
 16147798        if (start >= candidates.Count
 16147799            || CompareNavigationBodyPrisms(candidates[start].Prism, prism) != 0)
 800        {
 11025801            end = start;
 11025802            return false;
 803        }
 804
 5122805        low = start + 1;
 5122806        high = candidates.Count;
 16699807        while (low < high)
 808        {
 11577809            int middle = low + ((high - low) >> 1);
 11577810            if (CompareNavigationBodyPrisms(candidates[middle].Prism, prism) <= 0)
 161811                low = middle + 1;
 812            else
 11416813                high = middle;
 814        }
 815
 5122816        end = low;
 5122817        return true;
 818    }
 819
 820    private static void AddNavigationBodyUnionMember(
 821        SwiftList<GridNavigationBodyTraceCandidate> candidates,
 822        SwiftList<int> unionMembers,
 823        int candidateIndex)
 824    {
 1647825        candidates[candidateIndex] = candidates[candidateIndex].WithVisited();
 1647826        unionMembers.Add(candidateIndex);
 1647827    }
 828
 829    private static void AppendMissingNavigationBodyAlternativeEvidence(
 830        GridWorld world,
 831        SwiftList<GridNavigationBodyTraceCandidate> candidates,
 832        SwiftList<GridNavigationBodyTraceCell> results,
 833        VoxelGrid sourceGrid,
 834        VoxelIndex source,
 835        VoxelGrid targetGrid,
 836        VoxelIndex target)
 837    {
 124838        for (int start = 0; start < candidates.Count;)
 839        {
 86840            int end = GetNavigationBodyPrismGroupEnd(candidates, start);
 86841            if (!IsMissingNavigationBodyAlternativeGroup(
 86842                    candidates,
 86843                    start,
 86844                    end,
 86845                    sourceGrid,
 86846                    source,
 86847                    targetGrid,
 86848                    target))
 849            {
 69850                start = end;
 69851                continue;
 852            }
 853
 74854            for (int candidateIndex = start; candidateIndex < end; candidateIndex++)
 855            {
 20856                GridNavigationBodyTraceCandidate candidate = candidates[candidateIndex];
 20857                if (candidate.IsVisited)
 858                    continue;
 859
 3860                candidates[candidateIndex] = candidate.WithVisited();
 3861                results.Add(new GridNavigationBodyTraceCell(
 3862                    new WorldVoxelIndex(
 3863                        world.SpawnToken,
 3864                        candidate.Grid.GridIndex,
 3865                        candidate.Grid.SpawnToken,
 3866                        candidate.Index),
 3867                    candidate.Grid.Configuration.ToGridKey(),
 3868                    isPhysicallyPresent: false,
 3869                    candidate.GridLastChangeSequence,
 3870                    GridNavigationBodyTraceCellRole.PhysicalAlternativeDependency));
 871            }
 872
 17873            start = end;
 874        }
 19875    }
 876
 877    private static int CountMissingNavigationBodyAlternativeEvidence(
 878        SwiftList<GridNavigationBodyTraceCandidate> candidates,
 879        VoxelGrid sourceGrid,
 880        VoxelIndex source,
 881        VoxelGrid targetGrid,
 882        VoxelIndex target)
 883    {
 255884        int count = 0;
 2145885        for (int start = 0; start < candidates.Count;)
 886        {
 1635887            int end = GetNavigationBodyPrismGroupEnd(candidates, start);
 1635888            if (IsMissingNavigationBodyAlternativeGroup(
 1635889                    candidates,
 1635890                    start,
 1635891                    end,
 1635892                    sourceGrid,
 1635893                    source,
 1635894                    targetGrid,
 1635895                    target))
 896            {
 80897                for (int candidateIndex = start; candidateIndex < end; candidateIndex++)
 22898                    count += candidates[candidateIndex].IsVisited ? 0 : 1;
 899            }
 900
 1635901            start = end;
 902        }
 903
 255904        return count;
 905    }
 906
 907    private static int GetNavigationBodyPrismGroupEnd(
 908        SwiftList<GridNavigationBodyTraceCandidate> candidates,
 909        int start)
 910    {
 1721911        GridCellPrism prism = candidates[start].Prism;
 1721912        int end = start + 1;
 1778913        while (end < candidates.Count
 1778914            && CompareNavigationBodyPrisms(candidates[end].Prism, prism) == 0)
 915        {
 57916            end++;
 917        }
 918
 1721919        return end;
 920    }
 921
 922    private static bool IsMissingNavigationBodyAlternativeGroup(
 923        SwiftList<GridNavigationBodyTraceCandidate> candidates,
 924        int start,
 925        int end,
 926        VoxelGrid sourceGrid,
 927        VoxelIndex source,
 928        VoxelGrid targetGrid,
 929        VoxelIndex target)
 930    {
 1721931        bool hasMissingSelectedNonEndpoint = false;
 3542932        for (int candidateIndex = start; candidateIndex < end; candidateIndex++)
 933        {
 1732934            GridNavigationBodyTraceCandidate candidate = candidates[candidateIndex];
 1732935            if (candidate.IsPhysicallyPresent)
 1682936                return false;
 50937            hasMissingSelectedNonEndpoint |= candidate.IsVisited
 50938                && !IsNavigationBodyEndpoint(
 50939                    candidate,
 50940                    sourceGrid,
 50941                    source,
 50942                    targetGrid,
 50943                    target);
 944        }
 945
 39946        return hasMissingSelectedNonEndpoint;
 947    }
 948
 949    private static bool IsNavigationBodyEndpoint(
 950        GridNavigationBodyTraceCandidate candidate,
 951        VoxelGrid sourceGrid,
 952        VoxelIndex source,
 953        VoxelGrid targetGrid,
 954        VoxelIndex target) =>
 39955        (candidate.Grid == sourceGrid && candidate.Index == source)
 39956        || (candidate.Grid == targetGrid && candidate.Index == target);
 957
 958    private static GridNavigationBodyTraceReport CreateNavigationBodyTraceReport(
 959        GridNavigationBodyTraceStatus status,
 960        int gridCandidateCount,
 961        int addressCandidateCount,
 962        SwiftList<GridNavigationBodyTraceCell> results,
 963        GridCoveredAddressRunStamp runStamp) =>
 471964        new(
 471965            status,
 471966            gridCandidateCount,
 471967            addressCandidateCount,
 471968            gridCandidateCount + (long)addressCandidateCount,
 471969            results.Count,
 471970            runStamp);
 971
 972    private static GridNavigationBodyTraceReport FailNavigationBodyTrace(
 973        SwiftList<GridNavigationBodyTraceCell> results,
 974        GridNavigationBodyTraceStatus status,
 975        int gridCandidateCount,
 976        int addressCandidateCount,
 977        GridCoveredAddressRunStamp runStamp)
 978    {
 196979        results.Clear();
 196980        return CreateNavigationBodyTraceReport(
 196981            status,
 196982            gridCandidateCount,
 196983            addressCandidateCount,
 196984            results,
 196985            runStamp);
 986    }
 987
 988    private readonly struct GridNavigationBodyTraceCandidateComparer :
 989        IComparer<GridNavigationBodyTraceCandidate>
 990    {
 991        public int Compare(
 992            GridNavigationBodyTraceCandidate first,
 993            GridNavigationBodyTraceCandidate second) =>
 1673994            CompareNavigationBodyPrisms(first.Prism, second.Prism);
 995    }
 996
 997    private readonly struct GridNavigationBodyTraceCellComparer :
 998        IComparer<GridNavigationBodyTraceCell>
 999    {
 1000        public int Compare(
 1001            GridNavigationBodyTraceCell first,
 1002            GridNavigationBodyTraceCell second) =>
 30931003            CompareNavigationBodyTraceCells(first, second);
 1004    }
 1005
 1006    private static int CompareNavigationBodyTraceCells(
 1007        GridNavigationBodyTraceCell first,
 1008        GridNavigationBodyTraceCell second)
 1009    {
 30931010        int comparison = CompareConfigurationKeys(first.ConfigurationKey, second.ConfigurationKey);
 30931011        return comparison != 0
 30931012            ? comparison
 30931013            : first.Cell.VoxelIndex.CompareTo(second.Cell.VoxelIndex);
 1014    }
 1015}

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

#LineLine coverage
 1//=======================================================================
 2// GridTracer.PlanarNavigationBody.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 FixedMathSharp;
 10using GridForge.Grids;
 11using GridForge.Grids.Topology;
 12using GridForge.Spatial;
 13using SwiftCollections;
 14
 15namespace GridForge.Utility;
 16
 17public static partial class GridTracer
 18{
 19    /// <summary>Writes bounded native planar upright-capsule coverage for one immediate neighbor leg.</summary>
 20    /// <remarks>
 21    /// Eligible generations must be strictly configuration-ordered, with one selected layer per generation.
 22    /// The positive-radius capsule has an upright Forward axis of <paramref name="axisLength"/>;
 23    /// total height is axis length plus twice the radius. World Y selects layers, not gameplay height.
 24    /// Closed endpoint contact admits identity; only strict swept interior overlap claims other cells.
 25    /// Existing scratch/output capacities are hard ceilings. Candidate work counts admitted generation
 26    /// and address inspections, not every geometry operation. Per selected grid, candidate range math
 27    /// uses at most four 31-step forward-lattice bounds. With N retained candidates, union closure
 28    /// visits at most eight planar neighbors per member; sorting and lookup are O(N log N), with
 29    /// duplicate-alternative scans bounded by O(N squared). No world-registry scan or storage growth occurs.
 30    /// The world read lock precedes the committed-change lock for the whole bounded proof.
 31    /// </remarks>
 32    /// <param name="world">The explicit world owning every selected generation.</param>
 33    /// <param name="eligibleLayers">Exact generations and one selected layer each, in strict configuration order.</para
 34    /// <param name="embeddingY">World Y contained by every selected layer.</param>
 35    /// <param name="source">Pinned source identity in an eligible generation/layer.</param>
 36    /// <param name="target">Pinned target identity on the same footprint or an immediate planar neighbor.</param>
 37    /// <param name="startCenter">Capsule center at the start of the planar sweep.</param>
 38    /// <param name="endCenter">Capsule center at the end of the planar sweep.</param>
 39    /// <param name="axisLength">Nonnegative upright core segment length; zero represents a circle.</param>
 40    /// <param name="radius">Strictly positive capsule radius.</param>
 41    /// <param name="results">Pre-sized caller-owned evidence storage, cleared before writing.</param>
 42    /// <param name="scratch">Pre-sized caller-owned temporary storage, cleared on return.</param>
 43    /// <param name="gridCandidateLimit">Maximum charged generation inspections.</param>
 44    /// <param name="addressCandidateLimit">Maximum charged address inspections.</param>
 45    /// <param name="outputLimit">Maximum complete required and dependency-evidence cells.</param>
 46    /// <param name="candidateWorkLimit">Maximum combined generation and address inspections.</param>
 47    /// <returns>The completion status, exact candidate counts, and coherent evidence stamp.</returns>
 48    public static GridNavigationBodyTraceReport TracePlanarNavigationBodyInto(
 49        GridWorld world, ReadOnlySpan<GridPlanarLayer> eligibleLayers, Fixed64 embeddingY,
 50        WorldVoxelIndex source, WorldVoxelIndex target, Vector2d startCenter, Vector2d endCenter,
 51        Fixed64 axisLength, Fixed64 radius, SwiftList<GridNavigationBodyTraceCell> results,
 52        GridNavigationBodyTraceScratch scratch, int gridCandidateLimit, int addressCandidateLimit,
 53        int outputLimit, long candidateWorkLimit)
 54    {
 37555        ChronicleGuard.ThrowIfNull(results, nameof(results));
 37456        ChronicleGuard.ThrowIfNull(scratch, nameof(scratch));
 37357        ChronicleGuard.ThrowIfNegative(gridCandidateLimit, nameof(gridCandidateLimit));
 37258        ChronicleGuard.ThrowIfNegative(addressCandidateLimit, nameof(addressCandidateLimit));
 37159        ChronicleGuard.ThrowIfNegative(outputLimit, nameof(outputLimit));
 37060        ChronicleGuard.ThrowIfArgumentOutOfRange(candidateWorkLimit < 0L,
 37061            actualValue: null, paramName: nameof(candidateWorkLimit));
 36962        results.Clear();
 36963        scratch.Clear();
 36964        GridNavigationBodyTraceStatus invalid = GridNavigationBodyTraceStatus.InvalidOrUnrepresentableGeometry;
 36965        if (world == null || !world.IsActive || axisLength < Fixed64.Zero || radius <= Fixed64.Zero)
 466            return CreateNavigationBodyTraceReport(invalid, 0, 0, results, default);
 36567        if (!TryCreatePlanarBodyBounds(startCenter, endCenter, axisLength, radius, out Vector2d queryMin, out Vector2d q
 568            return CreateNavigationBodyTraceReport(GridNavigationBodyTraceStatus.ArithmeticOverflow, 0, 0, results, defa
 69
 36070        int gridCount = 0;
 36071        int addressCount = 0;
 36072        int gridCeiling = Math.Min(gridCandidateLimit, scratch.CandidateGrids.Capacity);
 36073        world.EnterReadLock();
 74        try
 75        {
 76            // Match sparse edits: world lifetime lock before the publication lock. No grid
 77            // obstacle/occupant locks or host callbacks occur inside this bounded proof.
 36078            lock (world.ChangeSyncRoot)
 79            {
 36080                VoxelGrid? sourceGrid = null;
 36081                VoxelGrid? targetGrid = null;
 118882                for (int i = 0; i < eligibleLayers.Length; i++)
 83                {
 37184                    if (gridCount >= gridCeiling || gridCount >= candidateWorkLimit)
 385                        return FailNavigationBodyTrace(results, candidateWorkLimit < gridCeiling
 386                            ? GridNavigationBodyTraceStatus.CandidateWorkLimitExceeded : GridNavigationBodyTraceStatus.G
 387                            gridCount, addressCount, default);
 36888                    gridCount++;
 36889                    GridPlanarLayer selected = eligibleLayers[i];
 36890                    GridCoveredAddressGeneration generation = selected.Generation;
 36891                    if ((i > 0 && eligibleLayers[i - 1].Generation.CompareTo(generation) >= 0)
 36892                        || !world.TryGetGrid(generation.GridIndex, out VoxelGrid? grid)
 36893                        || grid!.SpawnToken != generation.GridSpawnToken
 36894                        || grid.LastChangeSequence != generation.GridLastChangeSequence
 36895                        || grid.Configuration.ToGridKey() != generation.ConfigurationKey
 36896                        || selected.LayerIndex >= grid.Height
 36897                        || !GridCellGeometry.TryCreatePrism(grid.Configuration.TopologyKind, grid.Configuration.Topology
 36898                            grid.GetWorldPosition(new VoxelIndex(0, selected.LayerIndex, 0)), default, out GridCellPrism
 36899                        || embeddingY < layerPrism.VerticalMin || embeddingY > layerPrism.VerticalMax)
 134100                        return FailNavigationBodyTrace(results, invalid, gridCount, addressCount, default);
 101
 234102                    scratch.CandidateGrids.Add(grid.GridIndex);
 234103                    if (MatchesPlanarEndpoint(world, grid, selected.LayerIndex, source))
 216104                        sourceGrid = grid;
 234105                    if (MatchesPlanarEndpoint(world, grid, selected.LayerIndex, target))
 216106                        targetGrid = grid;
 107                }
 223108                if (sourceGrid == null || targetGrid == null
 223109                    || !TryCreatePlanarProofPrism(sourceGrid.Topology, sourceGrid.GetWorldPosition(source.VoxelIndex), o
 223110                    || !TryCreatePlanarProofPrism(targetGrid.Topology, targetGrid.GetWorldPosition(target.VoxelIndex), o
 223111                    || !HasClosedPlanarBodyContact(sourcePrism, startCenter, axisLength, radius)
 223112                    || !HasClosedPlanarBodyContact(targetPrism, endCenter, axisLength, radius))
 11113                    return FailNavigationBodyTrace(results, invalid, gridCount, addressCount, default);
 114
 212115                Span<GridCellPrism> closure = stackalloc GridCellPrism[4];
 212116                int closureCount = GetPlanarNavigationClosure(sourceGrid.Topology, sourcePrism, targetPrism, closure);
 212117                if (closureCount == 0)
 3118                    return FailNavigationBodyTrace(results, invalid, gridCount, addressCount, default);
 119
 838120                for (int i = 0; i < scratch.CandidateGrids.Count; i++)
 121                {
 218122                    VoxelGrid grid = world.ActiveGrids[scratch.CandidateGrids[i]];
 218123                    if (!TryExpandPlanarCandidateBounds(grid, queryMin, queryMax, out Vector2d candidateMin, out Vector2
 4124                        return FailNavigationBodyTrace(results, GridNavigationBodyTraceStatus.ArithmeticOverflow, gridCo
 214125                    if (!TryGetPlanarCandidateRange(grid, candidateMin, candidateMax, out VoxelIndex minimum, out VoxelI
 126                        continue;
 208127                    int layer = eligibleLayers[i].LayerIndex;
 1494128                    for (int x = minimum.x; x <= maximum.x; x++)
 129                    {
 4052130                        for (int z = minimum.z; z <= maximum.z; z++)
 131                        {
 1487132                            long remaining = candidateWorkLimit - gridCount;
 1487133                            if (addressCount >= addressCandidateLimit || addressCount >= remaining)
 2134                                return FailNavigationBodyTrace(results, remaining < addressCandidateLimit
 2135                                    ? GridNavigationBodyTraceStatus.CandidateWorkLimitExceeded : GridNavigationBodyTrace
 2136                                    gridCount, addressCount, default);
 1485137                            addressCount++;
 1485138                            VoxelIndex index = new VoxelIndex(x, layer, z);
 1485139                            if (!TryCreatePlanarProofPrism(grid.Topology, grid.GetWorldPosition(index), out GridCellPris
 1140                                return FailNavigationBodyTrace(results, invalid, gridCount, addressCount, default);
 1484141                            bool overlaps = HasStrictPlanarBodyOverlap(prism, startCenter, endCenter, axisLength, radius
 1484142                            bool isClosure = IsNavigationClosurePrism(prism, closure, closureCount);
 1484143                            if (!overlaps && !isClosure)
 144                                continue;
 1407145                            if (scratch.AddressCandidates.Count == scratch.AddressCandidates.Capacity)
 1146                                return FailNavigationBodyTrace(results, GridNavigationBodyTraceStatus.AddressLimitExceed
 1406147                            scratch.AddressCandidates.Add(new GridNavigationBodyTraceCandidate(grid, index, prism, overl
 148                        }
 149                    }
 150                }
 151
 201152                GridCoveredAddressRunStamp stamp = SnapshotNavigationBodyCandidates(world, scratch.AddressCandidates);
 201153                scratch.AddressCandidates.SortInPlace(default(GridNavigationBodyTraceCandidateComparer));
 201154                GridNavigationBodyTraceStatus unionStatus = ClosePlanarBodyUnion(sourceGrid, source.VoxelIndex, targetGr
 201155                    startCenter, endCenter, axisLength, radius, scratch);
 201156                if (unionStatus != GridNavigationBodyTraceStatus.Complete)
 4157                    return FailNavigationBodyTrace(results, unionStatus, gridCount, addressCount, default);
 197158                int alternatives = CountMissingNavigationBodyAlternativeEvidence(scratch.AddressCandidates, sourceGrid, 
 197159                int outputCeiling = Math.Min(outputLimit, results.Capacity);
 197160                if (scratch.UnionMembers.Count > outputCeiling || alternatives > outputCeiling - scratch.UnionMembers.Co
 2161                    return FailNavigationBodyTrace(results, GridNavigationBodyTraceStatus.OutputLimitExceeded, gridCount
 195162                bool missing = false;
 3096163                for (int i = 0; i < scratch.UnionMembers.Count; i++)
 164                {
 1353165                    GridNavigationBodyTraceCandidate candidate = scratch.AddressCandidates[scratch.UnionMembers[i]];
 1353166                    missing |= !candidate.IsPhysicallyPresent;
 1353167                    results.Add(new GridNavigationBodyTraceCell(new WorldVoxelIndex(world.SpawnToken, candidate.Grid.Gri
 1353168                        candidate.Grid.Configuration.ToGridKey(), candidate.IsPhysicallyPresent, candidate.GridLastChang
 169                }
 195170                if (missing)
 7171                    AppendMissingNavigationBodyAlternativeEvidence(world, scratch.AddressCandidates, results, sourceGrid
 195172                results.SortInPlace(default(GridNavigationBodyTraceCellComparer));
 195173                return CreateNavigationBodyTraceReport(missing ? GridNavigationBodyTraceStatus.IncompletePhysicalCoverag
 195174                    gridCount, addressCount, results, stamp);
 175            }
 176        }
 177        finally
 178        {
 360179            scratch.Clear();
 360180            world.ExitReadLock();
 360181        }
 360182    }
 183}

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

#LineLine coverage
 1//=======================================================================
 2// GridTracer.PlanarNavigationBody.Geometry.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 FixedMathSharp;
 10using FixedMathSharp.Geometry;
 11using GridForge.Configuration;
 12using GridForge.Grids;
 13using GridForge.Grids.Topology;
 14using GridForge.Spatial;
 15using SwiftCollections;
 16
 17namespace GridForge.Utility;
 18
 19/// <content>Owns planar-only footprint geometry and finite lattice-union closure.</content>
 20public static partial class GridTracer
 21{
 22    /// <summary>Tests whether two cell footprints are coincident or exact planar coverage neighbors.</summary>
 23    /// <remarks>Uses the source grid's quantized forward topology. Vertical layers and physical voxel presence are igno
 24    public static bool ArePlanarCoverageNeighborsOrCoincident(in NormalizedGridConfiguration sourceGrid, VoxelIndex sour
 25        in NormalizedGridConfiguration targetGrid, VoxelIndex target)
 26    {
 1027        if (!TryGetPlanarProofPrism(sourceGrid, source, out GridCellPrism from)
 1028            || !TryGetPlanarProofPrism(targetGrid, target, out GridCellPrism to))
 429            return false;
 30
 631        Span<GridCellPrism> closure = stackalloc GridCellPrism[4];
 632        return GetPlanarNavigationClosure(sourceGrid.Topology!, from, to, closure) != 0;
 33    }
 34
 35    private static bool TryGetPlanarProofPrism(in NormalizedGridConfiguration grid, VoxelIndex index, out GridCellPrism 
 36    {
 1837        index = new VoxelIndex(index.x, 0, index.z);
 1838        if (!grid.IsValidIndex(index))
 39        {
 440            prism = default;
 441            return false;
 42        }
 43
 1444        IGridTopology topology = grid.Topology!;
 1445        return TryCreatePlanarProofPrism(topology, topology.GetWorldPosition(grid.Configuration.BoundsMin, index), out p
 46    }
 47
 48    private static bool MatchesPlanarEndpoint(GridWorld world, VoxelGrid grid, int layer, WorldVoxelIndex endpoint) =>
 46849        endpoint.WorldSpawnToken == world.SpawnToken && endpoint.GridIndex == grid.GridIndex
 46850        && endpoint.GridSpawnToken == grid.SpawnToken && endpoint.VoxelIndex.y == layer
 46851        && endpoint.VoxelIndex.x >= 0 && endpoint.VoxelIndex.x < grid.Width
 46852        && endpoint.VoxelIndex.z >= 0 && endpoint.VoxelIndex.z < grid.Length;
 53
 54    private static bool TryCreatePlanarBodyBounds(Vector2d start, Vector2d end, Fixed64 axis, Fixed64 radius,
 55        out Vector2d min, out Vector2d max)
 56    {
 36557        min = default;
 36558        max = default;
 59        // Only the broad phase rounds outward; the exact relation retains an odd half-axis.
 36560        Fixed64 halfAxis = Fixed64.FromRaw((axis.m_rawValue >> 1) + (axis.m_rawValue & 1));
 36561        if (!Fixed64.TryAdd(halfAxis, radius, out Fixed64 extent)
 36562            || !Fixed64.TrySubtract(FixedMath.Min(start.X, end.X), radius, out Fixed64 minX)
 36563            || !Fixed64.TryAdd(FixedMath.Max(start.X, end.X), radius, out Fixed64 maxX)
 36564            || !Fixed64.TrySubtract(FixedMath.Min(start.Y, end.Y), extent, out Fixed64 minZ)
 36565            || !Fixed64.TryAdd(FixedMath.Max(start.Y, end.Y), extent, out Fixed64 maxZ))
 566            return false;
 36067        min = new Vector2d(minX, minZ);
 36068        max = new Vector2d(maxX, maxZ);
 36069        return true;
 70    }
 71
 72    private static bool TryExpandPlanarCandidateBounds(VoxelGrid grid, Vector2d min, Vector2d max,
 73        out Vector2d candidateMin, out Vector2d candidateMax)
 74    {
 21875        candidateMin = default;
 21876        candidateMax = default;
 21877        GridTopologyMetrics metrics = grid.Configuration.TopologyMetrics;
 21878        Fixed64 x = grid.Configuration.TopologyKind == GridTopologyKind.HexPrism ? metrics.CellRadius : metrics.CellWidt
 21879        Fixed64 z = grid.Configuration.TopologyKind == GridTopologyKind.HexPrism ? metrics.CellRadius : metrics.CellLeng
 21880        if (!Fixed64.TrySubtract(min.X, x, out Fixed64 minX) || !Fixed64.TryAdd(max.X, x, out Fixed64 maxX)
 21881            || !Fixed64.TrySubtract(min.Y, z, out Fixed64 minZ) || !Fixed64.TryAdd(max.Y, z, out Fixed64 maxZ))
 482            return false;
 21483        candidateMin = new Vector2d(minX, minZ);
 21484        candidateMax = new Vector2d(maxX, maxZ);
 21485        return true;
 86    }
 87
 88    private static bool TryCreatePlanarProofPrism(IGridTopology topology, Vector3d center, out GridCellPrism prism)
 89    {
 1308890        GridTopologyMetrics metrics = topology.Metrics;
 91        // This is an internal footprint key, not a physical prism or a rotated world.
 92        // Removing Y and thickness lets the existing exact-alternative proof compare planar geometry.
 1308893        GridTopologyMetrics planar = new GridTopologyMetrics(metrics.CellRadius, metrics.CellWidth, Fixed64.One, metrics
 1308894        return GridCellGeometry.TryCreatePrism(topology.Kind, planar,
 1308895            new Vector3d(center.X, Fixed64.Zero, center.Z), default, out prism);
 96    }
 97
 98    private static bool HasClosedPlanarBodyContact(in GridCellPrism prism, Vector2d center, Fixed64 axis, Fixed64 radius
 99    {
 428100        Span<Vector2d> offsets = stackalloc Vector2d[6];
 428101        Vector2d origin = prism.Center.ToVector2d();
 4496102        for (int i = 0; i < prism.FootprintVertexCount; i++)
 1820103            offsets[i] = prism.GetFootprintVertex(i) - origin;
 428104        return FixedConvex2dRelations.IntersectsUprightCapsule(center, axis, radius,
 428105            origin, offsets[..prism.FootprintVertexCount]);
 106    }
 107
 108    private static bool HasStrictPlanarBodyOverlap(in GridCellPrism prism, Vector2d start, Vector2d end, Fixed64 axis, F
 109    {
 6646110        Span<Vector2d> offsets = stackalloc Vector2d[6];
 6646111        Vector2d origin = prism.Center.ToVector2d();
 68016112        for (int i = 0; i < prism.FootprintVertexCount; i++)
 27362113            offsets[i] = prism.GetFootprintVertex(i) - origin;
 6646114        return FixedConvex2dRelations.IntersectsSweptUprightCapsuleStrict(start, end, axis, radius, origin, offsets[..pr
 115    }
 116
 117    private static int GetPlanarNavigationClosure(IGridTopology topology, in GridCellPrism source, in GridCellPrism targ
 118    {
 218119        closure[0] = source;
 218120        if (AreSameNavigationBodyPrism(source, target))
 157121            return 1;
 814122        for (int slot = 0; slot < topology.NeighborSlotCount; slot++)
 123        {
 403124            VoxelIndex offset = topology.GetNeighborOffset(slot);
 403125            if (offset.y != 0)
 126                continue;
 295127            if (!Vector3d.TryAdd(source.Center, topology.GetWorldOffset((offset.x, 0, offset.z)), out Vector3d center)
 295128                || !TryCreatePlanarProofPrism(topology, center, out GridCellPrism neighbor))
 1129                return 0;
 294130            if (!AreSameNavigationBodyPrism(neighbor, target))
 131                continue;
 56132            closure[1] = target;
 56133            if (topology.Kind != GridTopologyKind.RectangularPrism || offset.x == 0 || offset.z == 0)
 34134                return 2;
 135            // Each rectangular axis bound is already represented by source or target.
 136            // Their Cartesian combinations add no new arithmetic or topology dimension.
 22137            _ = TryCreatePlanarProofPrism(topology, new Vector3d(source.Center.X, Fixed64.Zero, target.Center.Z), out cl
 22138            _ = TryCreatePlanarProofPrism(topology, new Vector3d(target.Center.X, Fixed64.Zero, source.Center.Z), out cl
 22139            return 4;
 140        }
 4141        return 0;
 142    }
 143
 144    private static GridNavigationBodyTraceStatus ClosePlanarBodyUnion(VoxelGrid sourceGrid, VoxelIndex source, VoxelGrid
 145        Vector2d start, Vector2d end, Fixed64 axis, Fixed64 radius, GridNavigationBodyTraceScratch scratch)
 146    {
 201147        SwiftList<GridNavigationBodyTraceCandidate> candidates = scratch.AddressCandidates;
 148        // Closed endpoint admission places both identities inside the outward-rounded
 149        // candidate range; closure retention keeps them even when contact is tangent.
 150        // Thus the shared identity lookups visit at most candidates.Count entries.
 201151        int sourceCandidate = FindNavigationBodyCandidate(candidates, sourceGrid, source);
 201152        int targetCandidate = FindNavigationBodyCandidate(candidates, targetGrid, target);
 201153        bool pinBoth = targetCandidate != sourceCandidate
 201154            && AreSameNavigationBodyPrism(candidates[sourceCandidate].Prism, candidates[targetCandidate].Prism);
 201155        if (scratch.UnionMembers.Capacity < (pinBoth ? 2 : 1))
 1156            return GridNavigationBodyTraceStatus.AddressLimitExceeded;
 200157        AddNavigationBodyUnionMember(candidates, scratch.UnionMembers, sourceCandidate);
 200158        if (pinBoth)
 1159            AddNavigationBodyUnionMember(candidates, scratch.UnionMembers, targetCandidate);
 3132160        for (int i = 0; i < scratch.UnionMembers.Count; i++)
 161        {
 1369162            GridCellPrism member = candidates[scratch.UnionMembers[i]].Prism;
 73076163            for (int slot = 0; slot < sourceGrid.Topology.NeighborSlotCount; slot++)
 164            {
 35172165                VoxelIndex offset = sourceGrid.Topology.GetNeighborOffset(slot);
 35172166                if (offset.y != 0)
 167                    continue;
 10822168                if (!Vector3d.TryAdd(member.Center, sourceGrid.Topology.GetWorldOffset((offset.x, 0, offset.z)), out Vec
 10822169                    || !TryCreatePlanarProofPrism(sourceGrid.Topology, center, out GridCellPrism neighbor))
 1170                    return GridNavigationBodyTraceStatus.InvalidOrUnrepresentableGeometry;
 10821171                int match = FindBestMatchingNavigationBodyPrism(candidates, neighbor, sourceCandidate, targetCandidate);
 10821172                bool overlap = match >= 0 ? candidates[match].HasPositiveOverlap : HasStrictPlanarBodyOverlap(neighbor, 
 10821173                if (overlap && match < 0)
 1174                    return GridNavigationBodyTraceStatus.InvalidOrUnrepresentableGeometry;
 10820175                if (match >= 0 && !candidates[match].IsVisited && !TryAddPlanarUnionMember(scratch, match))
 1176                    return GridNavigationBodyTraceStatus.AddressLimitExceeded;
 177            }
 178        }
 179        // A distinct target is either pinned above or an admitted immediate source
 180        // neighbor, so the first closure iteration necessarily visits it.
 197181        return GridNavigationBodyTraceStatus.Complete;
 182    }
 183
 184    private static bool TryAddPlanarUnionMember(GridNavigationBodyTraceScratch scratch, int index)
 185    {
 1178186        if (scratch.UnionMembers.Count == scratch.UnionMembers.Capacity)
 1187            return false;
 1177188        AddNavigationBodyUnionMember(scratch.AddressCandidates, scratch.UnionMembers, index);
 1177189        return true;
 190    }
 191}

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

#LineLine coverage
 1//=======================================================================
 2// GridTracer.PlanarNavigationBody.Range.cs
 3//=======================================================================
 4// MIT License, Copyright (c) 2024-present David Oravsky (mrdav30)
 5// See LICENSE file in the project root for full license information.
 6//=======================================================================
 7
 8using FixedMathSharp;
 9using GridForge.Grids;
 10using GridForge.Grids.Topology;
 11using GridForge.Spatial;
 12
 13namespace GridForge.Utility;
 14
 15/// <content>Derives conservative native planar address ranges from the actual forward lattice.</content>
 16public static partial class GridTracer
 17{
 18    private static bool TryGetPlanarCandidateRange(VoxelGrid grid, Vector2d minimum, Vector2d maximum,
 19        out VoxelIndex minIndex, out VoxelIndex maxIndex)
 20    {
 21        // The ideal hex inverse is not the inverse of its quantized forward basis.
 22        // Use four monotone coordinate bounds instead: each takes at most 31
 23        // probes over an Int32 dimension, with no storage or physical-cell reads.
 24        int minX;
 25        int maxX;
 26        int minZ;
 27        int maxZ;
 21428        if (grid.Configuration.TopologyKind == GridTopologyKind.HexPrism
 21429            && grid.Configuration.TopologyMetrics.HexOrientation == HexOrientation.PointyTop)
 30        {
 1631            minZ = FindPlanarCoordinateBound(grid, column: false, fixedIndex: 0, minimum.Y, upper: false);
 1632            maxZ = FindPlanarCoordinateBound(grid, column: false, fixedIndex: 0, maximum.Y, upper: true) - 1;
 1633            if (minZ > maxZ)
 34            {
 135                minIndex = default;
 136                maxIndex = default;
 137                return false;
 38            }
 39            // X increases with both q and r; the retained row extrema conservatively bound q.
 1540            minX = FindPlanarCoordinateBound(grid, column: true, fixedIndex: maxZ, minimum.X, upper: false);
 1541            maxX = FindPlanarCoordinateBound(grid, column: true, fixedIndex: minZ, maximum.X, upper: true) - 1;
 42        }
 43        else
 44        {
 45            // Rectangular X is independent of z; flat hex X is independent of r.
 19846            minX = FindPlanarCoordinateBound(grid, column: true, fixedIndex: 0, minimum.X, upper: false);
 19847            maxX = FindPlanarCoordinateBound(grid, column: true, fixedIndex: 0, maximum.X, upper: true) - 1;
 19848            if (minX > maxX)
 49            {
 250                minIndex = default;
 251                maxIndex = default;
 252                return false;
 53            }
 54            // Rectangular Z ignores fixedIndex; flat hex Z increases with both indices.
 19655            minZ = FindPlanarCoordinateBound(grid, column: false, fixedIndex: maxX, minimum.Y, upper: false);
 19656            maxZ = FindPlanarCoordinateBound(grid, column: false, fixedIndex: minX, maximum.Y, upper: true) - 1;
 57        }
 21158        minIndex = new VoxelIndex(minX, 0, minZ);
 21159        maxIndex = new VoxelIndex(maxX, 0, maxZ);
 21160        return minX <= maxX && minZ <= maxZ;
 61    }
 62
 63    private static int FindPlanarCoordinateBound(VoxelGrid grid, bool column, int fixedIndex,
 64        Fixed64 bound, bool upper)
 65    {
 85066        int low = 0;
 85067        int high = column ? grid.Width : grid.Length;
 269568        while (low < high)
 69        {
 184570            int middle = low + ((high - low) >> 1);
 184571            VoxelIndex index = column ? new VoxelIndex(middle, 0, fixedIndex) : new VoxelIndex(fixedIndex, 0, middle);
 184572            Vector3d center = grid.GetWorldPosition(index);
 184573            Fixed64 coordinate = column ? center.X : center.Z;
 184574            if (coordinate < bound || (upper && coordinate == bound))
 89675                low = middle + 1;
 76            else
 94977                high = middle;
 78        }
 85079        return low;
 80    }
 81}

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

#LineLine coverage
 1//=======================================================================
 2// GridTracer.RectangularSlabs.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 FixedMathSharp;
 10using GridForge.Grids;
 11using GridForge.Grids.Storage;
 12using GridForge.Grids.Topology;
 13using GridForge.Spatial;
 14using SwiftCollections;
 15
 16namespace GridForge.Utility;
 17
 18public static partial class GridTracer
 19{
 20    /// <summary>Attempts a bounded trace observed after each complete rectangular X slab.</summary>
 21    /// <remarks>
 22    /// Returns false only before chargeable discovery when the original segment or expected single-layer
 23    /// rectangular generation is unsupported. Results are then empty and the observer is not invoked.
 24    /// All qualified terminal outcomes return true, including ceilings. The observer runs under the world
 25    /// read lock and must not reenter world/grid operations or mutate results or scratch. Reading world
 26    /// identity/change-stamp properties for freshness fences is allowed. Scratch is not thread-safe.
 27    /// Returning false from the observer retains emission-order intervals, not a canonical ray prefix;
 28    /// ties and coverage remain unassigned. Continuation sorts canonically and source ordinals follow every
 29    /// move. The ordinal span must fit outputLimit. Failure or exception clears results and used ordinals;
 30    /// exceptions propagate after cleanup. World stamps are captured before qualification, not refreshed by
 31    /// callbacks; concurrent obstacle changes remain possible and consumers own their final freshness fence.
 32    /// </remarks>
 33    public static bool TryTraceRectangularSlabsInto(
 34        GridWorld world, Vector3d start, Vector3d end,
 35        in GridCoveredAddressGeneration expectedGeneration,
 36        SwiftList<GridTraceInterval> results, GridTraceIntervalScratch scratch,
 37        Span<int> intervalSourceOrdinals, Func<GridTraceSlab, bool> continueTrace,
 38        int gridCandidateLimit, int addressCandidateLimit, int outputLimit,
 39        long candidateWorkLimit, out GridTraceIntervalReport report)
 40    {
 10041        ValidateTraceArguments(results, scratch, gridCandidateLimit, addressCandidateLimit, outputLimit, candidateWorkLi
 9442        ChronicleGuard.ThrowIfNull(continueTrace, nameof(continueTrace));
 9343        ChronicleGuard.ThrowIfArgument(intervalSourceOrdinals.Length < outputLimit,
 9344            nameof(intervalSourceOrdinals), "Source ordinals must fit the output limit.");
 45
 9246        report = default;
 9247        scratch.Enter();
 9148        int usedTags = 0;
 9149        bool retainOutput = false;
 50        try
 51        {
 9152            results.Clear();
 9153            if (world == null || !world.IsActive)
 254                return false;
 55
 8956            world.EnterReadLock();
 57            try
 58            {
 59                // Capture before checking the expected generation: the read lock protects grid lifetime,
 60                // but concurrent obstacle changes can still commit under ChangeSyncRoot.
 8961                long worldSpawnToken = world.SpawnToken;
 8962                ulong worldChangeSequence = world.ChangeSequence;
 8963                (Vector3d queryMin, Vector3d queryMax) = CreatePaddedOrderedBounds(start, end, padding: null);
 8964                if (!TryQualifyRectangularSlabs(world, start, end, queryMin, queryMax, expectedGeneration,
 8965                        out VoxelGrid? grid, out VoxelIndex minIndex, out VoxelIndex maxIndex, out Fixed64 deltaX))
 2366                    return false;
 67
 6668                (Vector3d candidateMin, Vector3d candidateMax) =
 6669                    ExpandOrderedBounds(queryMin, queryMax, world.MaxTopologyCellEdge);
 6670                bool gridWorkIsTighter = candidateWorkLimit < gridCandidateLimit;
 6671                int effectiveGridLimit = gridWorkIsTighter ? (int)candidateWorkLimit : gridCandidateLimit;
 6672                if (!world.CollectGridCandidates(candidateMin, candidateMax, scratch.CandidateGrids, effectiveGridLimit)
 73                {
 374                    report = FailTrace(results, gridWorkIsTighter
 375                        ? GridTraceIntervalStatus.CandidateWorkLimitExceeded : GridTraceIntervalStatus.GridCandidateLimi
 376                        scratch.CandidateGrids.Count, 0);
 377                    return true;
 78                }
 79
 80                // Snapped topology ranges can reach a grid outside the world's discovery bounds.
 81                // Match the eager tracer: no discovered grid means no admitted address or slab.
 6382                if (scratch.CandidateGrids.Count == 0)
 83                {
 184                    report = CreateTraceReport(GridTraceIntervalStatus.Complete, 0, 0, results);
 185                    retainOutput = true;
 186                    return true;
 87                }
 88
 6289                long remainingWork = candidateWorkLimit - scratch.CandidateGrids.Count;
 6290                bool addressWorkIsTighter = remainingWork < addressCandidateLimit;
 6291                int effectiveAddressLimit = addressWorkIsTighter ? (int)remainingWork : addressCandidateLimit;
 6292                int addressCount = 0;
 6293                if (!TryAdmitTraceRange(minIndex, maxIndex, effectiveAddressLimit, ref addressCount))
 94                {
 495                    report = FailTrace(results, addressWorkIsTighter
 496                        ? GridTraceIntervalStatus.CandidateWorkLimitExceeded : GridTraceIntervalStatus.AddressCandidateL
 497                        scratch.CandidateGrids.Count, addressCount);
 498                    return true;
 99                }
 100
 422101                for (int x = minIndex.x; x <= maxIndex.x; x++)
 102                {
 179103                    scratch.AddressCandidates.Clear();
 179104                    CollectRectangularSegmentSlab(grid!, start, end, deltaX, minIndex, maxIndex, x, scratch);
 179105                    if (grid!.StorageKind == GridStorageKind.Sparse)
 32106                        SnapshotSparsePresence(world, scratch.AddressCandidates);
 107
 179108                    int intervalStart = results.Count;
 179109                    GridTraceIntervalStatus status = AppendTraceIntervals(world, start, end, results, scratch,
 179110                        outputLimit, intervalSourceOrdinals, ref usedTags);
 179111                    if (status != GridTraceIntervalStatus.Complete)
 112                    {
 2113                        report = FailTrace(results, status, scratch.CandidateGrids.Count, addressCount);
 2114                        return true;
 115                    }
 116
 177117                    GridTraceSlab slab = new GridTraceSlab(x, intervalStart, results.Count - intervalStart,
 177118                        RectangularSlabSeparatesEndpoints(grid, x, start.X, end.X),
 177119                        worldSpawnToken, worldChangeSequence, expectedGeneration);
 177120                    if (!continueTrace(slab))
 121                    {
 22122                        report = new GridTraceIntervalReport(GridTraceIntervalStatus.StoppedAfterCompleteSlab,
 22123                            scratch.CandidateGrids.Count, addressCount, results.Count, 0, false, false);
 22124                        retainOutput = true;
 22125                        return true;
 126                    }
 127                }
 128
 32129                SortIntervals(results, intervalSourceOrdinals);
 32130                report = CreateTraceReport(GridTraceIntervalStatus.Complete, scratch.CandidateGrids.Count, addressCount,
 32131                retainOutput = true;
 32132                return true;
 133            }
 134            finally
 135            {
 89136                world.ExitReadLock();
 89137            }
 138        }
 139        finally
 140        {
 91141            if (!retainOutput)
 142            {
 36143                results.Clear();
 36144                intervalSourceOrdinals.Slice(0, usedTags).Clear();
 145            }
 91146            scratch.Exit();
 91147        }
 89148    }
 149
 150    private static bool TryQualifyRectangularSlabs(GridWorld world, Vector3d start, Vector3d end,
 151        Vector3d queryMin, Vector3d queryMax, in GridCoveredAddressGeneration expected,
 152        out VoxelGrid? grid, out VoxelIndex minIndex, out VoxelIndex maxIndex, out Fixed64 deltaX)
 153    {
 89154        grid = null;
 89155        minIndex = maxIndex = default;
 89156        deltaX = default;
 89157        if (world.ActiveGrids.Count != 1 || !world.ActiveGrids.IsAllocated(expected.GridIndex))
 3158            return false;
 86159        grid = world.ActiveGrids[expected.GridIndex];
 86160        if (!grid.IsActive || grid.SpawnToken != expected.GridSpawnToken
 86161            || grid.LastChangeSequence != expected.GridLastChangeSequence
 86162            || grid.Configuration.ToGridKey() != expected.ConfigurationKey
 86163            || grid.Topology.Kind != GridTopologyKind.RectangularPrism || grid.Height != 1
 86164            || !Fixed64.TrySubtract(end.X, start.X, out deltaX) || deltaX == Fixed64.Zero
 86165            || start.Z == end.Z
 86166            || !TopologyVoxelRangeUtility.TryGetPrismCandidateRange(grid, queryMin, queryMax, out minIndex, out maxIndex
 15167            return false;
 168
 71169        return IsRepresentableSlabExtreme(grid, minIndex, start, end)
 71170            && IsRepresentableSlabExtreme(grid, maxIndex, start, end);
 171    }
 172
 173    private static bool IsRepresentableSlabExtreme(VoxelGrid grid, VoxelIndex index, Vector3d start, Vector3d end)
 174    {
 137175        if (!GridCellGeometry.TryCreatePrism(grid.Topology.Kind, grid.Topology.Metrics,
 137176                grid.GetWorldPosition(index), default, out GridCellPrism prism))
 3177            return false;
 134178        Vector2d minimum = prism.GetFootprintVertex(0);
 134179        Vector2d maximum = prism.GetFootprintVertex(2);
 134180        return GridCellGeometry.TryGetPlanarSlab(start.X, end.X, minimum.X, maximum.X, out _, out _, out _)
 134181            && GridCellGeometry.TryGetPlanarSlab(start.Z, end.Z, minimum.Y, maximum.Y, out _, out _, out _);
 182    }
 183
 184    private static bool RectangularSlabSeparatesEndpoints(VoxelGrid grid, int x, Fixed64 start, Fixed64 end)
 185    {
 186        // Qualification proves actual extreme faces and positive planar differences representable.
 177187        Fixed64 center = grid.BoundsMin.X + x * grid.Topology.Metrics.CellWidth;
 177188        Fixed64 halfWidth = grid.Topology.Metrics.CellWidth * Fixed64.Half;
 177189        Fixed64 left = center - halfWidth;
 177190        Fixed64 right = center + halfWidth;
 177191        Fixed64 first = FixedMath.Min(start, end);
 177192        Fixed64 last = FixedMath.Max(start, end);
 177193        return Fixed64.TrySubtract(last, first, out Fixed64 delta)
 177194            && Fixed64.TrySubtract(left, first, out Fixed64 before)
 177195            && Fixed64.TrySubtract(last, right, out Fixed64 after)
 177196            && before > Fixed64.Zero && after > Fixed64.Zero
 177197            && Fixed64.CompareProducts(before, Fixed64.One, delta, Fixed64.MinIncrement) > 0
 177198            && Fixed64.CompareProducts(after, Fixed64.One, delta, Fixed64.MinIncrement) > 0;
 199    }
 200}

/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    /// The supplied scratch must not already be active in another trace; reentrant use throws before clearing results.
 33    /// </remarks>
 34    public static GridTraceIntervalReport TraceIntervalsInto(
 35        GridWorld world,
 36        Vector3d start,
 37        Vector3d end,
 38        SwiftList<GridTraceInterval> results,
 39        GridTraceIntervalScratch scratch,
 40        int gridCandidateLimit,
 41        int addressCandidateLimit,
 42        int outputLimit,
 43        long candidateWorkLimit)
 44    {
 19945        ValidateTraceArguments(results, scratch, gridCandidateLimit, addressCandidateLimit, outputLimit, candidateWorkLi
 19546        scratch.Enter();
 47        try
 48        {
 19449            return TraceIntervalsCore(world, start, end, results, scratch,
 19450                gridCandidateLimit, addressCandidateLimit, outputLimit, candidateWorkLimit);
 51        }
 52        finally
 53        {
 19454            scratch.Exit();
 19455        }
 19356    }
 57
 58    private static void ValidateTraceArguments(SwiftList<GridTraceInterval> results, GridTraceIntervalScratch scratch,
 59        int gridCandidateLimit, int addressCandidateLimit, int outputLimit, long candidateWorkLimit)
 60    {
 29961        ChronicleGuard.ThrowIfNull(results, nameof(results));
 29862        ChronicleGuard.ThrowIfNull(scratch, nameof(scratch));
 29763        ChronicleGuard.ThrowIfNegative(gridCandidateLimit, nameof(gridCandidateLimit));
 29564        ChronicleGuard.ThrowIfNegative(addressCandidateLimit, nameof(addressCandidateLimit));
 29365        ChronicleGuard.ThrowIfNegative(outputLimit, nameof(outputLimit));
 29166        ChronicleGuard.ThrowIfArgumentOutOfRange(candidateWorkLimit < 0L, null, nameof(candidateWorkLimit));
 28967    }
 68
 69    private static GridTraceIntervalReport TraceIntervalsCore(GridWorld world, Vector3d start, Vector3d end,
 70        SwiftList<GridTraceInterval> results, GridTraceIntervalScratch scratch,
 71        int gridCandidateLimit, int addressCandidateLimit, int outputLimit, long candidateWorkLimit)
 72    {
 19473        results.Clear();
 19474        if (world == null || !world.IsActive)
 275            return CreateTraceReport(GridTraceIntervalStatus.Complete, 0, 0, results);
 76
 19277        world.EnterReadLock();
 78        try
 79        {
 19180            (Vector3d queryMin, Vector3d queryMax) = CreatePaddedOrderedBounds(start, end, padding: null);
 19181            (Vector3d candidateMin, Vector3d candidateMax) =
 19182                ExpandOrderedBounds(queryMin, queryMax, world.MaxTopologyCellEdge);
 19183            bool candidateGridLimitIsTighter = candidateWorkLimit < gridCandidateLimit;
 19184            int effectiveGridLimit = candidateGridLimitIsTighter
 19185                ? (int)candidateWorkLimit
 19186                : gridCandidateLimit;
 19187            if (!world.CollectGridCandidates(
 19188                    candidateMin,
 19189                    candidateMax,
 19190                    scratch.CandidateGrids,
 19191                    effectiveGridLimit))
 92            {
 793                return FailTrace(
 794                    results,
 795                    candidateGridLimitIsTighter
 796                        ? GridTraceIntervalStatus.CandidateWorkLimitExceeded
 797                        : GridTraceIntervalStatus.GridCandidateLimitExceeded,
 798                    scratch.CandidateGrids.Count,
 799                    0);
 100            }
 101
 184102            SortGridIndices(world, scratch.CandidateGrids);
 103
 184104            long remainingCandidateWork = candidateWorkLimit - scratch.CandidateGrids.Count;
 184105            bool candidateAddressLimitIsTighter = remainingCandidateWork < addressCandidateLimit;
 184106            int effectiveAddressLimit = candidateAddressLimitIsTighter
 184107                ? (int)remainingCandidateWork
 184108                : addressCandidateLimit;
 184109            bool hasSparseGrid = false;
 184110            int addressCandidateCount = 0;
 790111            for (int gridCandidateIndex = 0; gridCandidateIndex < scratch.CandidateGrids.Count; gridCandidateIndex++)
 112            {
 241113                VoxelGrid grid = world.ActiveGrids[scratch.CandidateGrids[gridCandidateIndex]];
 241114                if (!grid.IsActive
 241115                    || !TryCollectSegmentCandidates(
 241116                        grid,
 241117                        queryMin,
 241118                        queryMax,
 241119                        start,
 241120                        end,
 241121                        scratch,
 241122                        effectiveAddressLimit,
 241123                        ref addressCandidateCount))
 124                {
 30125                    return FailTrace(
 30126                        results,
 30127                        candidateAddressLimitIsTighter
 30128                            ? GridTraceIntervalStatus.CandidateWorkLimitExceeded
 30129                            : GridTraceIntervalStatus.AddressCandidateLimitExceeded,
 30130                        scratch.CandidateGrids.Count,
 30131                        addressCandidateCount);
 132                }
 133
 211134                hasSparseGrid |= grid.StorageKind == GridStorageKind.Sparse;
 135            }
 136
 154137            if (hasSparseGrid)
 19138                SnapshotSparsePresence(world, scratch.AddressCandidates);
 139
 154140            int unusedTagCount = 0;
 154141            GridTraceIntervalStatus status = AppendTraceIntervals(world, start, end, results, scratch,
 154142                outputLimit, default, ref unusedTagCount);
 154143            if (status != GridTraceIntervalStatus.Complete)
 17144                return FailTrace(results, status, scratch.CandidateGrids.Count, addressCandidateCount);
 145
 137146            SortIntervals(results);
 137147            return CreateTraceReport(
 137148                GridTraceIntervalStatus.Complete,
 137149                scratch.CandidateGrids.Count,
 137150                addressCandidateCount,
 137151                results);
 152        }
 153        finally
 154        {
 191155            world.ExitReadLock();
 191156        }
 191157    }
 158
 159    private static GridTraceIntervalStatus AppendTraceIntervals(
 160        GridWorld world, Vector3d start, Vector3d end, SwiftList<GridTraceInterval> results,
 161        GridTraceIntervalScratch scratch, int outputLimit, Span<int> sourceOrdinals, ref int usedTags)
 162    {
 5682163        for (int addressIndex = 0; addressIndex < scratch.AddressCandidates.Count; addressIndex++)
 164        {
 2527165            GridTraceAddressCandidate candidate = scratch.AddressCandidates[addressIndex];
 2527166            VoxelGrid grid = candidate.Grid;
 2527167            VoxelIndex index = candidate.Index;
 2527168            WorldVoxelIndex cell = new WorldVoxelIndex(world.SpawnToken, grid.GridIndex, grid.SpawnToken, index);
 2527169            if (!GridCellGeometry.TryCreatePrism(grid.Configuration.TopologyKind, grid.Configuration.TopologyMetrics,
 2527170                    grid.GetWorldPosition(index), cell, out GridCellPrism prism))
 4171                return GridTraceIntervalStatus.UnrepresentableGeometry;
 172
 2523173            if (!TryGetPrismInterval(start, end, prism, out Fixed64 tEnter, out Fixed64 tExit))
 174                continue;
 1579175            if (results.Count >= outputLimit)
 15176                return GridTraceIntervalStatus.OutputLimitExceeded;
 177
 1564178            if (!sourceOrdinals.IsEmpty)
 325179                sourceOrdinals[usedTags++] = results.Count;
 1564180            results.Add(new GridTraceInterval(cell, grid.Configuration.ToGridKey(), candidate.IsPhysicallyPresent,
 1564181                grid.LastChangeSequence, tEnter, tExit));
 182        }
 314183        return GridTraceIntervalStatus.Complete;
 184    }
 185
 186    private static bool TryCollectSegmentCandidates(
 187        VoxelGrid grid,
 188        Vector3d queryMin,
 189        Vector3d queryMax,
 190        Vector3d start,
 191        Vector3d end,
 192        GridTraceIntervalScratch scratch,
 193        int addressCandidateLimit,
 194        ref int addressCandidateCount)
 195    {
 241196        if (!TopologyVoxelRangeUtility.TryGetPrismCandidateRange(
 241197                grid,
 241198                queryMin,
 241199                queryMax,
 241200                out VoxelIndex minIndex,
 241201                out VoxelIndex maxIndex))
 202        {
 1203            return true;
 204        }
 205
 240206        if (!TryAdmitTraceRange(minIndex, maxIndex, addressCandidateLimit, ref addressCandidateCount))
 30207            return false;
 208
 210209        if (TryCollectRectangularSegmentCandidates(grid, start, end, minIndex, maxIndex, scratch))
 60210            return true;
 211
 150212        bool isDense = grid.StorageKind == GridStorageKind.Dense;
 1164213        for (int x = minIndex.x; x <= maxIndex.x; x++)
 214        {
 1760215            for (int y = minIndex.y; y <= maxIndex.y; y++)
 216            {
 2308217                for (int z = minIndex.z; z <= maxIndex.z; z++)
 218                {
 706219                    scratch.AddressCandidates.Add(new GridTraceAddressCandidate(
 706220                        grid,
 706221                        new VoxelIndex(x, y, z),
 706222                        isDense));
 223                }
 224            }
 225        }
 226
 150227        return true;
 228    }
 229
 230    private static bool TryAdmitTraceRange(VoxelIndex minIndex, VoxelIndex maxIndex,
 231        int addressCandidateLimit, ref int addressCandidateCount)
 232    {
 233        // Admission still charges the full original range, including omitted
 234        // planar misses. Cap the intermediate product before multiplying depth.
 302235        long width = Math.Max(0L, (long)maxIndex.x - minIndex.x + 1);
 302236        long height = Math.Max(0L, (long)maxIndex.y - minIndex.y + 1);
 302237        long depth = Math.Max(0L, (long)maxIndex.z - minIndex.z + 1);
 302238        long count = Math.Min(width * height, (long)addressCandidateLimit + 1) * depth;
 302239        if (count > addressCandidateLimit - addressCandidateCount)
 240        {
 34241            addressCandidateCount = addressCandidateLimit;
 34242            return false;
 243        }
 268244        addressCandidateCount += (int)count;
 245
 268246        return true;
 247    }
 248
 249    private static bool TryCollectRectangularSegmentCandidates(
 250        VoxelGrid grid,
 251        Vector3d start,
 252        Vector3d end,
 253        VoxelIndex minIndex,
 254        VoxelIndex maxIndex,
 255        GridTraceIntervalScratch scratch)
 256    {
 210257        if (grid.Topology.Kind != GridTopologyKind.RectangularPrism
 210258            || !Fixed64.TrySubtract(end.X, start.X, out Fixed64 deltaX)
 210259            || deltaX == Fixed64.Zero
 210260            // Collinear edge projections can round an extrapolated parameter
 210261            // onto 0 or 1. Keep that existing behavior on horizontal rays.
 210262            || start.Z == end.Z)
 146263            return false;
 264
 64265        GridTopologyMetrics metrics = grid.Topology.Metrics;
 266        // Actual rectangular centers are monotone on each independent axis.
 267        // Valid extreme prisms prove every omitted prism is representable;
 268        // otherwise retain the original geometry and failure evaluation order.
 64269        if (!GridCellGeometry.TryCreatePrism(grid.Topology.Kind, metrics,
 64270                grid.GetWorldPosition(minIndex), default, out _)
 64271            || !GridCellGeometry.TryCreatePrism(grid.Topology.Kind, metrics,
 64272                grid.GetWorldPosition(maxIndex), default, out _))
 4273            return false;
 274
 634275        for (int x = minIndex.x; x <= maxIndex.x; x++)
 257276            CollectRectangularSegmentSlab(grid, start, end, deltaX, minIndex, maxIndex, x, scratch);
 60277        return true;
 278    }
 279
 280    private static void CollectRectangularSegmentSlab(VoxelGrid grid, Vector3d start, Vector3d end,
 281        Fixed64 deltaX, VoxelIndex minIndex, VoxelIndex maxIndex, int x, GridTraceIntervalScratch scratch)
 282    {
 436283        GridTopologyMetrics metrics = grid.Topology.Metrics;
 436284        Fixed64 halfWidth = metrics.CellWidth * Fixed64.Half;
 436285        Fixed64 halfLength = metrics.CellLength * Fixed64.Half;
 436286        Fixed64 segmentMinX = FixedMath.Min(start.X, end.X);
 436287        Fixed64 segmentMaxX = FixedMath.Max(start.X, end.X);
 436288        Vector3d boundsMin = grid.BoundsMin;
 436289        bool isDense = grid.StorageKind == GridStorageKind.Dense;
 290        // Keep the topology's saturating multiply-then-add, but only compute the queried axis.
 436291        Fixed64 centerX = boundsMin.X + x * metrics.CellWidth;
 436292        Fixed64 slabMin = FixedMath.Max(centerX - halfWidth, segmentMinX);
 436293        Fixed64 slabMax = FixedMath.Min(centerX + halfWidth, segmentMaxX);
 436294        if (slabMin > slabMax)
 8295            return;
 296
 297        // Clipping first makes both subtractions fit within deltaX.
 298        // Division rounds once; expand outward before full-domain Lerp.
 428299        Fixed64 first = (slabMin - start.X) / deltaX;
 428300        Fixed64 second = (slabMax - start.X) / deltaX;
 428301        Fixed64 enter = FixedMath.Max(Fixed64.Zero,
 428302            FixedMath.Min(first, second) - Fixed64.MinIncrement);
 428303        Fixed64 exit = FixedMath.Min(Fixed64.One,
 428304            FixedMath.Max(first, second) + Fixed64.MinIncrement);
 428305        Fixed64 firstZ = FixedMath.Lerp(start.Z, end.Z, enter);
 428306        Fixed64 secondZ = FixedMath.Lerp(start.Z, end.Z, exit);
 307        // Lerp also rounds once. One raw coordinate unit retains exact
 308        // contacts before expanding to the closed cell-center range.
 428309        Fixed64 minZ = FixedMath.Min(firstZ, secondZ) - Fixed64.MinIncrement - halfLength;
 428310        Fixed64 maxZ = FixedMath.Max(firstZ, secondZ) + Fixed64.MinIncrement + halfLength;
 428311        int zStart = FindRectangularZBound(boundsMin.Z, metrics.CellLength,
 428312            minIndex.z, maxIndex.z, minZ, upper: false);
 428313        int zEnd = FindRectangularZBound(boundsMin.Z, metrics.CellLength,
 428314            zStart, maxIndex.z, maxZ, upper: true);
 315        // Keep Y unchanged: independently rounded vertical intervals may
 316        // overlap a planar interval even without exact simultaneous contact.
 2376317        for (int y = minIndex.y; y <= maxIndex.y; y++)
 318        {
 5218319            for (int z = zStart; z < zEnd; z++)
 1849320                scratch.AddressCandidates.Add(new GridTraceAddressCandidate(
 1849321                    grid, new VoxelIndex(x, y, z), isDense));
 322        }
 428323    }
 324
 325    private static int FindRectangularZBound(
 326        Fixed64 origin, Fixed64 cellLength, int min, int max, Fixed64 position, bool upper)
 327    {
 328        // Search actual centers, not an inverse transform: positioning may
 329        // saturate and produce multiple addresses with the same center.
 856330        int end = max + 1;
 2824331        while (min < end)
 332        {
 1968333            int middle = min + ((end - min) >> 1);
 1968334            Fixed64 center = origin + middle * cellLength;
 1968335            if (center < position || (upper && center == position))
 709336                min = middle + 1;
 337            else
 1259338                end = middle;
 339        }
 856340        return min;
 341    }
 342
 343    private static void SnapshotSparsePresence(
 344        GridWorld world,
 345        SwiftList<GridTraceAddressCandidate> candidates)
 346    {
 51347        lock (world.ChangeSyncRoot)
 348        {
 1718349            for (int i = 0; i < candidates.Count; i++)
 350            {
 808351                GridTraceAddressCandidate candidate = candidates[i];
 808352                if (candidate.Grid.StorageKind == GridStorageKind.Sparse)
 353                {
 808354                    candidates[i] = candidate.WithPhysicalPresence(
 808355                        candidate.Grid.TryGetVoxel(candidate.Index, out _));
 356                }
 357            }
 51358        }
 51359    }
 360
 361    internal static bool TryGetPrismInterval(
 362        Vector3d start,
 363        Vector3d end,
 364        in GridCellPrism prism,
 365        out Fixed64 tEnter,
 366        out Fixed64 tExit)
 367    {
 2668368        if (!GridCellGeometry.TryGetPlanarSegmentInterval(
 2668369                prism,
 2668370                new Vector2d(start.X, start.Z),
 2668371                new Vector2d(end.X, end.Z),
 2668372                out Fixed64 planarEnter,
 2668373                out Fixed64 planarExit)
 2668374            || !TryGetVerticalInterval(start.Y, end.Y, prism.VerticalMin, prism.VerticalMax,
 2668375                out Fixed64 verticalEnter, out Fixed64 verticalExit))
 376        {
 354377            tEnter = default;
 354378            tExit = default;
 354379            return false;
 380        }
 381
 2314382        tEnter = FixedMath.Max(planarEnter, verticalEnter);
 2314383        tExit = FixedMath.Min(planarExit, verticalExit);
 2314384        return tEnter <= tExit;
 385    }
 386
 387    private static bool TryGetVerticalInterval(
 388        Fixed64 start,
 389        Fixed64 end,
 390        Fixed64 verticalMin,
 391        Fixed64 verticalMax,
 392        out Fixed64 tEnter,
 393        out Fixed64 tExit)
 394    {
 2332395        Fixed64 delta = end - start;
 2332396        if (delta == Fixed64.Zero)
 397        {
 1031398            tEnter = Fixed64.Zero;
 1031399            tExit = Fixed64.One;
 1031400            return start >= verticalMin && start <= verticalMax;
 401        }
 402
 1301403        tEnter = (verticalMin - start) / delta;
 1301404        tExit = (verticalMax - start) / delta;
 1301405        if (tEnter > tExit)
 593406            (tEnter, tExit) = (tExit, tEnter);
 407
 1301408        tEnter = FixedMath.Clamp(tEnter, Fixed64.Zero, Fixed64.One);
 1301409        tExit = FixedMath.Clamp(tExit, Fixed64.Zero, Fixed64.One);
 1301410        return FixedMath.Min(start, end) <= verticalMax
 1301411            && FixedMath.Max(start, end) >= verticalMin;
 412    }
 413
 414    private static GridTraceIntervalReport CreateTraceReport(
 415        GridTraceIntervalStatus status,
 416        int gridCandidateCount,
 417        int candidateCount,
 418        SwiftList<GridTraceInterval> results)
 419    {
 172420        int tieGroupCount = AssignTieGroups(results);
 172421        return new GridTraceIntervalReport(
 172422            status,
 172423            gridCandidateCount,
 172424            candidateCount,
 172425            results.Count,
 172426            tieGroupCount,
 172427            HasContinuousCoverage(results, requirePhysical: false),
 172428            HasContinuousCoverage(results, requirePhysical: true));
 429    }
 430
 431    private static GridTraceIntervalReport FailTrace(
 432        SwiftList<GridTraceInterval> results,
 433        GridTraceIntervalStatus status,
 434        int gridCandidateCount,
 435        int candidateCount)
 436    {
 63437        results.Clear();
 63438        return new GridTraceIntervalReport(status, gridCandidateCount, candidateCount, 0, 0, false, false);
 439    }
 440
 441    private static int AssignTieGroups(SwiftList<GridTraceInterval> results)
 442    {
 172443        int groupId = -1;
 172444        int order = 0;
 172445        Fixed64 groupEnter = default;
 172446        Fixed64 groupExit = default;
 2844447        for (int i = 0; i < results.Count; i++)
 448        {
 1250449            GridTraceInterval interval = results[i];
 1250450            bool pointPeer = i > 0
 1250451                && groupEnter == groupExit
 1250452                && interval.TEnter == groupEnter
 1250453                && interval.TExit == groupExit;
 1250454            bool overlapsInterior = i > 0
 1250455                && groupExit > groupEnter
 1250456                && interval.TExit > interval.TEnter
 1250457                && interval.TEnter < groupExit;
 1250458            if (i == 0 || (!overlapsInterior && !pointPeer))
 459            {
 849460                groupId++;
 849461                order = 0;
 849462                groupEnter = interval.TEnter;
 849463                groupExit = interval.TExit;
 464            }
 401465            else if (interval.TExit > groupExit)
 1466                groupExit = interval.TExit;
 467
 1250468            results[i] = interval.WithTie(groupId, order++);
 469        }
 470
 172471        return groupId + 1;
 472    }
 473
 474    private static bool HasContinuousCoverage(
 475        SwiftList<GridTraceInterval> results,
 476        bool requirePhysical)
 477    {
 344478        Fixed64 coveredThrough = Fixed64.Zero;
 344479        bool started = false;
 4016480        for (int i = 0; i < results.Count; i++)
 481        {
 1966482            GridTraceInterval interval = results[i];
 1966483            if (requirePhysical && !interval.IsPhysicallyPresent)
 484                continue;
 1811485            if (!started)
 486            {
 312487                if (interval.TEnter > Fixed64.Zero)
 54488                    return false;
 258489                started = true;
 490            }
 1499491            else if (interval.TEnter > coveredThrough)
 492            {
 7493                return false;
 494            }
 495
 1750496            if (interval.TExit > coveredThrough)
 1122497                coveredThrough = interval.TExit;
 1750498            if (coveredThrough >= Fixed64.One)
 241499                return true;
 500        }
 501
 42502        return started && coveredThrough >= Fixed64.One;
 503    }
 504
 505    private static void SortGridIndices(GridWorld world, SwiftList<ushort> values) =>
 249506        values.SortInPlace(new GridIndexComparer(world));
 507
 508    private static void SortIntervals(SwiftList<GridTraceInterval> values, Span<int> sourceOrdinals = default)
 509    {
 169510        GridTraceInterval[] items = values.InnerArray;
 169511        int count = values.Count;
 1466512        for (int root = (count >> 1) - 1; root >= 0; root--)
 564513            SiftIntervalsDown(items, sourceOrdinals, root, count);
 514
 2526515        for (int end = count - 1; end > 0; end--)
 516        {
 1094517            (items[0], items[end]) = (items[end], items[0]);
 1094518            if (!sourceOrdinals.IsEmpty)
 232519                (sourceOrdinals[0], sourceOrdinals[end]) = (sourceOrdinals[end], sourceOrdinals[0]);
 1094520            SiftIntervalsDown(items, sourceOrdinals, 0, end);
 521        }
 169522    }
 523
 524    private static void SiftIntervalsDown(GridTraceInterval[] items, Span<int> sourceOrdinals, int root, int count)
 525    {
 526        // Carry the root once instead of swapping the full interval at every level.
 1658527        GridTraceInterval value = items[root];
 1658528        int sourceOrdinal = sourceOrdinals.IsEmpty ? 0 : sourceOrdinals[root];
 4324529        while (root < (count >> 1))
 530        {
 2969531            int child = (root << 1) + 1;
 2969532            int right = child + 1;
 2969533            if (right < count && CompareIntervals(items[child], items[right]) < 0)
 1186534                child = right;
 2969535            if (CompareIntervals(value, items[child]) >= 0)
 536                break;
 537
 2666538            items[root] = items[child];
 2666539            if (!sourceOrdinals.IsEmpty)
 518540                sourceOrdinals[root] = sourceOrdinals[child];
 2666541            root = child;
 542        }
 1658543        items[root] = value;
 1658544        if (!sourceOrdinals.IsEmpty)
 348545            sourceOrdinals[root] = sourceOrdinal;
 1658546    }
 547
 548    private static int CompareIntervals(in GridTraceInterval first, in GridTraceInterval second)
 549    {
 5641550        int comparison = first.TEnter.CompareTo(second.TEnter);
 5641551        if (comparison != 0)
 4309552            return comparison;
 1332553        comparison = second.TExit.CompareTo(first.TExit);
 1332554        if (comparison != 0)
 608555            return comparison;
 724556        comparison = CompareConfigurationKeys(first.ConfigurationKey, second.ConfigurationKey);
 724557        if (comparison != 0)
 92558            return comparison;
 632559        return first.Cell.VoxelIndex.CompareTo(second.Cell.VoxelIndex);
 560    }
 561
 562    private static int CompareGridIdentity(VoxelGrid first, VoxelGrid second)
 563    {
 249564        return CompareConfigurationKeys(
 249565            first.Configuration.ToGridKey(),
 249566            second.Configuration.ToGridKey());
 567    }
 568
 569    private readonly struct GridIndexComparer : IComparer<ushort>
 570    {
 571        private readonly GridWorld _world;
 572
 249573        internal GridIndexComparer(GridWorld world) => _world = world;
 574
 575        public int Compare(ushort first, ushort second) =>
 115576            CompareGridIdentity(_world.ActiveGrids[first], _world.ActiveGrids[second]);
 577    }
 578
 579    private static int CompareConfigurationKeys(
 580        GridConfigurationKey first,
 581        GridConfigurationKey second)
 582    {
 4066583        int comparison = CompareVectors(first.BoundsMin, second.BoundsMin);
 4066584        if (comparison != 0)
 227585            return comparison;
 3839586        comparison = CompareVectors(first.BoundsMax, second.BoundsMax);
 3839587        if (comparison != 0)
 42588            return comparison;
 3797589        comparison = ((int)first.TopologyKind).CompareTo((int)second.TopologyKind);
 3797590        if (comparison != 0)
 73591            return comparison;
 592
 3724593        GridTopologyMetrics firstMetrics = first.TopologyMetrics;
 3724594        GridTopologyMetrics secondMetrics = second.TopologyMetrics;
 3724595        comparison = firstMetrics.CellRadius.CompareTo(secondMetrics.CellRadius);
 3724596        if (comparison != 0)
 4597            return comparison;
 3720598        comparison = firstMetrics.CellWidth.CompareTo(secondMetrics.CellWidth);
 3720599        if (comparison != 0)
 7600            return comparison;
 3713601        comparison = firstMetrics.LayerHeight.CompareTo(secondMetrics.LayerHeight);
 3713602        if (comparison != 0)
 5603            return comparison;
 3708604        comparison = firstMetrics.CellLength.CompareTo(secondMetrics.CellLength);
 3708605        return comparison != 0
 3708606            ? comparison
 3708607            : ((int)firstMetrics.HexOrientation).CompareTo((int)secondMetrics.HexOrientation);
 608    }
 609
 610    private static int CompareVectors(Vector3d first, Vector3d second)
 611    {
 7905612        int comparison = first.X.CompareTo(second.X);
 7905613        if (comparison != 0)
 237614            return comparison;
 7668615        comparison = first.Y.CompareTo(second.Y);
 7668616        return comparison != 0 ? comparison : first.Z.CompareTo(second.Z);
 617    }
 618}

/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    {
 1188184        Fixed64 fixedPadding = padding.HasValue && padding.Value > Fixed64.Zero
 1188185            ? padding.Value
 1188186            : Fixed64.Zero;
 187
 1188188        min -= fixedPadding;
 1188189        max += fixedPadding;
 190
 1188191        (min.X, max.X) = min.X > max.X ? (max.X, min.X) : (min.X, max.X);
 1188192        (min.Y, max.Y) = min.Y > max.Y ? (max.Y, min.Y) : (min.Y, max.Y);
 1188193        (min.Z, max.Z) = min.Z > max.Z ? (max.Z, min.Z) : (min.Z, max.Z);
 194
 1188195        return (min, max);
 196    }
 197
 198    private static (Vector3d min, Vector3d max) ExpandOrderedBounds(
 199        Vector3d min,
 200        Vector3d max,
 201        Fixed64 expansion)
 202    {
 1165203        if (expansion <= Fixed64.Zero)
 6204            return (min, max);
 205
 1159206        return (
 1159207            new Vector3d(min.X - expansion, min.Y - expansion, min.Z - expansion),
 1159208            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    {
 626222        xMin = 0;
 626223        yMin = 0;
 626224        zMin = 0;
 626225        xMax = 0;
 626226        yMax = 0;
 626227        zMax = 0;
 228
 626229        (Vector3d snappedMin, Vector3d snappedMax) = grid.NormalizeBounds(queryMin, queryMax);
 626230        if (!TopologyVoxelRangeUtility.TryClipBoundsToGrid(grid, snappedMin, snappedMax, out Vector3d clippedMin, out Ve
 3231            return false;
 232
 623233        (xMin, yMin, zMin) = grid.SnapToScanCell(clippedMin);
 623234        (xMax, yMax, zMax) = grid.SnapToScanCell(clippedMax);
 623235        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}

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)
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,SwiftCollections.SwiftPackedSet`1<System.Int64>,SwiftCollections.SwiftList`1<GridForge.Configuration.GridConfigurationKey>)
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,GridForge.Grids.Topology.TopologyVoxelAabb,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)
TracePlanarNavigationBodyInto(GridForge.Grids.GridWorld,System.ReadOnlySpan`1<GridForge.Grids.Topology.GridPlanarLayer>,FixedMathSharp.Fixed64,GridForge.Spatial.WorldVoxelIndex,GridForge.Spatial.WorldVoxelIndex,FixedMathSharp.Vector2d,FixedMathSharp.Vector2d,FixedMathSharp.Fixed64,FixedMathSharp.Fixed64,SwiftCollections.SwiftList`1<GridForge.Grids.GridNavigationBodyTraceCell>,GridForge.Grids.GridNavigationBodyTraceScratch,System.Int32,System.Int32,System.Int32,System.Int64)
ArePlanarCoverageNeighborsOrCoincident(GridForge.Configuration.NormalizedGridConfiguration&,GridForge.Spatial.VoxelIndex,GridForge.Configuration.NormalizedGridConfiguration&,GridForge.Spatial.VoxelIndex)
TryGetPlanarProofPrism(GridForge.Configuration.NormalizedGridConfiguration&,GridForge.Spatial.VoxelIndex,GridForge.Grids.Topology.GridCellPrism&)
MatchesPlanarEndpoint(GridForge.Grids.GridWorld,GridForge.Grids.VoxelGrid,System.Int32,GridForge.Spatial.WorldVoxelIndex)
TryCreatePlanarBodyBounds(FixedMathSharp.Vector2d,FixedMathSharp.Vector2d,FixedMathSharp.Fixed64,FixedMathSharp.Fixed64,FixedMathSharp.Vector2d&,FixedMathSharp.Vector2d&)
TryExpandPlanarCandidateBounds(GridForge.Grids.VoxelGrid,FixedMathSharp.Vector2d,FixedMathSharp.Vector2d,FixedMathSharp.Vector2d&,FixedMathSharp.Vector2d&)
TryCreatePlanarProofPrism(GridForge.Grids.Topology.IGridTopology,FixedMathSharp.Vector3d,GridForge.Grids.Topology.GridCellPrism&)
HasClosedPlanarBodyContact(GridForge.Grids.Topology.GridCellPrism&,FixedMathSharp.Vector2d,FixedMathSharp.Fixed64,FixedMathSharp.Fixed64)
HasStrictPlanarBodyOverlap(GridForge.Grids.Topology.GridCellPrism&,FixedMathSharp.Vector2d,FixedMathSharp.Vector2d,FixedMathSharp.Fixed64,FixedMathSharp.Fixed64)
GetPlanarNavigationClosure(GridForge.Grids.Topology.IGridTopology,GridForge.Grids.Topology.GridCellPrism&,GridForge.Grids.Topology.GridCellPrism&,System.Span`1<GridForge.Grids.Topology.GridCellPrism>)
ClosePlanarBodyUnion(GridForge.Grids.VoxelGrid,GridForge.Spatial.VoxelIndex,GridForge.Grids.VoxelGrid,GridForge.Spatial.VoxelIndex,FixedMathSharp.Vector2d,FixedMathSharp.Vector2d,FixedMathSharp.Fixed64,FixedMathSharp.Fixed64,GridForge.Grids.GridNavigationBodyTraceScratch)
TryAddPlanarUnionMember(GridForge.Grids.GridNavigationBodyTraceScratch,System.Int32)
TryGetPlanarCandidateRange(GridForge.Grids.VoxelGrid,FixedMathSharp.Vector2d,FixedMathSharp.Vector2d,GridForge.Spatial.VoxelIndex&,GridForge.Spatial.VoxelIndex&)
FindPlanarCoordinateBound(GridForge.Grids.VoxelGrid,System.Boolean,System.Int32,FixedMathSharp.Fixed64,System.Boolean)
TryTraceRectangularSlabsInto(GridForge.Grids.GridWorld,FixedMathSharp.Vector3d,FixedMathSharp.Vector3d,GridForge.Grids.Topology.GridCoveredAddressGeneration&,SwiftCollections.SwiftList`1<GridForge.Grids.GridTraceInterval>,GridForge.Grids.GridTraceIntervalScratch,System.Span`1<System.Int32>,System.Func`2<GridForge.Grids.GridTraceSlab,System.Boolean>,System.Int32,System.Int32,System.Int32,System.Int64,GridForge.Grids.GridTraceIntervalReport&)
TryQualifyRectangularSlabs(GridForge.Grids.GridWorld,FixedMathSharp.Vector3d,FixedMathSharp.Vector3d,FixedMathSharp.Vector3d,FixedMathSharp.Vector3d,GridForge.Grids.Topology.GridCoveredAddressGeneration&,GridForge.Grids.VoxelGrid&,GridForge.Spatial.VoxelIndex&,GridForge.Spatial.VoxelIndex&,FixedMathSharp.Fixed64&)
IsRepresentableSlabExtreme(GridForge.Grids.VoxelGrid,GridForge.Spatial.VoxelIndex,FixedMathSharp.Vector3d,FixedMathSharp.Vector3d)
RectangularSlabSeparatesEndpoints(GridForge.Grids.VoxelGrid,System.Int32,FixedMathSharp.Fixed64,FixedMathSharp.Fixed64)
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)
ValidateTraceArguments(SwiftCollections.SwiftList`1<GridForge.Grids.GridTraceInterval>,GridForge.Grids.GridTraceIntervalScratch,System.Int32,System.Int32,System.Int32,System.Int64)
TraceIntervalsCore(GridForge.Grids.GridWorld,FixedMathSharp.Vector3d,FixedMathSharp.Vector3d,SwiftCollections.SwiftList`1<GridForge.Grids.GridTraceInterval>,GridForge.Grids.GridTraceIntervalScratch,System.Int32,System.Int32,System.Int32,System.Int64)
AppendTraceIntervals(GridForge.Grids.GridWorld,FixedMathSharp.Vector3d,FixedMathSharp.Vector3d,SwiftCollections.SwiftList`1<GridForge.Grids.GridTraceInterval>,GridForge.Grids.GridTraceIntervalScratch,System.Int32,System.Span`1<System.Int32>,System.Int32&)
TryCollectSegmentCandidates(GridForge.Grids.VoxelGrid,FixedMathSharp.Vector3d,FixedMathSharp.Vector3d,FixedMathSharp.Vector3d,FixedMathSharp.Vector3d,GridForge.Grids.GridTraceIntervalScratch,System.Int32,System.Int32&)
TryAdmitTraceRange(GridForge.Spatial.VoxelIndex,GridForge.Spatial.VoxelIndex,System.Int32,System.Int32&)
TryCollectRectangularSegmentCandidates(GridForge.Grids.VoxelGrid,FixedMathSharp.Vector3d,FixedMathSharp.Vector3d,GridForge.Spatial.VoxelIndex,GridForge.Spatial.VoxelIndex,GridForge.Grids.GridTraceIntervalScratch)
CollectRectangularSegmentSlab(GridForge.Grids.VoxelGrid,FixedMathSharp.Vector3d,FixedMathSharp.Vector3d,FixedMathSharp.Fixed64,GridForge.Spatial.VoxelIndex,GridForge.Spatial.VoxelIndex,System.Int32,GridForge.Grids.GridTraceIntervalScratch)
FindRectangularZBound(FixedMathSharp.Fixed64,FixedMathSharp.Fixed64,System.Int32,System.Int32,FixedMathSharp.Fixed64,System.Boolean)
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>,System.Span`1<System.Int32>)
SiftIntervalsDown(GridForge.Grids.GridTraceInterval[],System.Span`1<System.Int32>,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>)