< Summary

Information
Class: GridForge.Utility.GridTracer
Assembly: GridForge
File(s): /home/runner/work/GridForge/GridForge/src/GridForge/Utility/GridTracer.cs
Line coverage
88%
Covered lines: 153
Uncovered lines: 19
Coverable lines: 172
Total lines: 445
Line coverage: 88.9%
Branch coverage
85%
Covered branches: 116
Total branches: 136
Branch coverage: 85.2%
Method coverage

Feature is only available for sponsors

Upgrade to PRO version

Metrics

MethodBranch coverage Crap Score Cyclomatic complexity Line coverage
TraceLine(...)50%5466.66%
TraceLine(...)100%11100%
GetCoveredVoxels(...)50%5466.66%
GetCoveredScanCells(...)50%5466.66%
GetCoveredScanCellsInto(...)0%4260%
GetCoveredScanCellsInto(...)0%7280%
AddCoveredScanCellsTo(...)100%11100%
AddCoveredScanCellsTo(...)100%11100%
AddCoveredScanCellsCore(...)100%2626100%
TraceLineIterator()100%3838100%
GetCoveredVoxelsIterator()100%2222100%
GetCoveredScanCellsIterator()100%2424100%

File(s)

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

#LineLine coverage
 1using FixedMathSharp;
 2using GridForge.Grids;
 3using SwiftCollections;
 4using SwiftCollections.Pool;
 5using System.Collections.Generic;
 6
 7namespace GridForge.Utility;
 8
 9/// <summary>
 10/// Provides utilities for tracing lines or bounding areas in a grid, aligning them to grid voxels.
 11/// Uses fixed-point calculations to ensure deterministic and accurate grid traversal.
 12/// </summary>
 13public static class GridTracer
 14{
 15    /// <summary>
 16    /// Traces a 3D line between two points in the supplied world.
 17    /// The traced points are returned as grid voxels.
 18    /// </summary>
 19    /// <remarks>
 20    /// Uses a fractional step algorithm inspired by Bresenham’s line algorithm.
 21    /// This implementation leverages fixed-point math to maintain precision across a deterministic grid.
 22    /// </remarks>
 23    /// <param name="world">The world whose grids should be traced.</param>
 24    /// <param name="start">Starting position in world space.</param>
 25    /// <param name="end">Ending position in world space.</param>
 26    /// <param name="padding">Value applied to the start/end positions before snapping.</param>
 27    /// <param name="includeEnd">Whether to include the end voxel in the traced line.</param>
 28    /// <returns>A collection of <see cref="GridVoxelSet"/> objects representing the traced path.</returns>
 29    public static IEnumerable<GridVoxelSet> TraceLine(
 30        GridWorld world,
 31        Vector3d start,
 32        Vector3d end,
 33        Fixed64? padding = null,
 34        bool includeEnd = true)
 35    {
 1136        if (world == null || !world.IsActive)
 037            return System.Array.Empty<GridVoxelSet>();
 38
 1139        return TraceLineIterator(world, start, end, padding, includeEnd);
 40    }
 41
 42    /// <summary>
 43    /// Traces a 2D line between two points in the supplied world, snapping them to grid coordinates.
 44    /// </summary>
 45    /// <remarks>
 46    /// This method projects the 2D line onto the X-Y plane and follows the closest grid-aligned path.
 47    /// </remarks>
 48    public static IEnumerable<GridVoxelSet> TraceLine(
 49        GridWorld world,
 50        Vector2d start,
 51        Vector2d end,
 52        Fixed64? padding = null,
 53        bool includeEnd = true)
 54    {
 155        Vector3d start3D = start.ToVector3d(Fixed64.Zero);
 156        Vector3d end3D = end.ToVector3d(Fixed64.Zero);
 57
 158        return TraceLine(world, start3D, end3D, padding, includeEnd);
 59    }
 60
 61    /// <summary>
 62    /// Retrieves all grid voxels covered by the given bounding area in the supplied world.
 63    /// </summary>
 64    public static IEnumerable<GridVoxelSet> GetCoveredVoxels(
 65        GridWorld world,
 66        Vector3d boundsMin,
 67        Vector3d boundsMax,
 68        Fixed64? padding = null)
 69    {
 15270        if (world == null || !world.IsActive)
 071            return System.Array.Empty<GridVoxelSet>();
 72
 15273        return GetCoveredVoxelsIterator(world, boundsMin, boundsMax, padding);
 74    }
 75
 76    /// <summary>
 77    /// Retrieves all scan cells within the given bounding area across relevant grids in the supplied world.
 78    /// </summary>
 79    /// <param name="world">The world whose grids should be queried.</param>
 80    /// <param name="boundsMin">The minimum corner of the bounding area.</param>
 81    /// <param name="boundsMax">The maximum corner of the bounding area.</param>
 82    /// <param name="padding">Value applied to the min/max bounds before snapping.</param>
 83    /// <returns>An enumerable of covered scan cells grouped by grid.</returns>
 84    public static IEnumerable<ScanCell> GetCoveredScanCells(
 85        GridWorld world,
 86        Vector3d boundsMin,
 87        Vector3d boundsMax,
 88        Fixed64? padding = null)
 89    {
 290        if (world == null || !world.IsActive)
 091            return System.Array.Empty<ScanCell>();
 92
 293        return GetCoveredScanCellsIterator(world, boundsMin, boundsMax, padding);
 94    }
 95
 96    /// <summary>
 97    /// Clears and fills caller-owned storage with scan cells covered by the supplied bounding area.
 98    /// </summary>
 99    public static void GetCoveredScanCellsInto(
 100        GridWorld world,
 101        Vector3d boundsMin,
 102        Vector3d boundsMax,
 103        SwiftList<ScanCell> results,
 104        Fixed64? padding = null)
 105    {
 0106        if (results == null)
 0107            throw new System.ArgumentNullException(nameof(results));
 108
 0109        results.Clear();
 0110        if (world == null || !world.IsActive)
 0111            return;
 112
 0113        AddCoveredScanCellsTo(world, boundsMin, boundsMax, results, padding);
 0114    }
 115
 116    /// <summary>
 117    /// Clears and fills caller-owned storage using caller-owned scratch collections.
 118    /// </summary>
 119    public static void GetCoveredScanCellsInto(
 120        GridWorld world,
 121        Vector3d boundsMin,
 122        Vector3d boundsMax,
 123        SwiftList<ScanCell> results,
 124        GridScanScratch scratch,
 125        Fixed64? padding = null)
 126    {
 0127        if (results == null)
 0128            throw new System.ArgumentNullException(nameof(results));
 129
 0130        if (scratch == null)
 0131            throw new System.ArgumentNullException(nameof(scratch));
 132
 0133        results.Clear();
 0134        if (world == null || !world.IsActive)
 0135            return;
 136
 0137        AddCoveredScanCellsTo(world, boundsMin, boundsMax, results, scratch, padding);
 0138    }
 139
 140    /// <summary>
 141    /// Appends covered scan cells without allocating an iterator for hot-path callers.
 142    /// </summary>
 143    internal static void AddCoveredScanCellsTo(
 144        GridWorld world,
 145        Vector3d boundsMin,
 146        Vector3d boundsMax,
 147        SwiftList<ScanCell> scanCells,
 148        Fixed64? padding = null)
 149    {
 7150        SwiftHashSet<ushort> processedGrids = SwiftHashSetPool<ushort>.Shared.Rent();
 7151        SwiftHashSet<ScanCell> voxelRedundancyCheck = SwiftHashSetPool<ScanCell>.Shared.Rent();
 152
 153        try
 154        {
 7155            AddCoveredScanCellsCore(
 7156                world,
 7157                boundsMin,
 7158                boundsMax,
 7159                scanCells,
 7160                processedGrids,
 7161                voxelRedundancyCheck,
 7162                padding);
 7163        }
 164        finally
 165        {
 7166            SwiftHashSetPool<ushort>.Shared.Release(processedGrids);
 7167            SwiftHashSetPool<ScanCell>.Shared.Release(voxelRedundancyCheck);
 7168        }
 7169    }
 170
 171    /// <summary>
 172    /// Appends covered scan cells using caller-owned scratch state for allocation-sensitive scans.
 173    /// </summary>
 174    internal static void AddCoveredScanCellsTo(
 175        GridWorld world,
 176        Vector3d boundsMin,
 177        Vector3d boundsMax,
 178        SwiftList<ScanCell> scanCells,
 179        GridScanScratch scratch,
 180        Fixed64? padding = null)
 181    {
 258182        scratch.Clear();
 258183        AddCoveredScanCellsCore(
 258184            world,
 258185            boundsMin,
 258186            boundsMax,
 258187            scanCells,
 258188            scratch.ProcessedGrids,
 258189            scratch.ScanCellRedundancy,
 258190            padding);
 258191    }
 192
 193    private static void AddCoveredScanCellsCore(
 194        GridWorld world,
 195        Vector3d boundsMin,
 196        Vector3d boundsMax,
 197        SwiftList<ScanCell> scanCells,
 198        SwiftHashSet<ushort> processedGrids,
 199        SwiftHashSet<ScanCell> voxelRedundancyCheck,
 200        Fixed64? padding = null)
 201    {
 265202        (Vector3d snappedMin, Vector3d snappedMax) =
 265203            world.SnapBoundsToVoxelSize(boundsMin, boundsMax, padding);
 265204        (int cellXMin, int cellYMin, int cellZMin, int cellXMax, int cellYMax, int cellZMax) =
 265205            world.GetSpatialGridCellBounds(snappedMin, snappedMax);
 206
 1062207        for (int cellZ = cellZMin; cellZ <= cellZMax; cellZ++)
 208        {
 1064209            for (int cellY = cellYMin; cellY <= cellYMax; cellY++)
 210            {
 1068211                for (int cellX = cellXMin; cellX <= cellXMax; cellX++)
 212                {
 268213                    int cellIndex = SwiftHashTools.CombineHashCodes(cellX, cellY, cellZ);
 268214                    if (!world.SpatialGridHash.TryGetValue(cellIndex, out SwiftHashSet<ushort> gridList))
 215                        continue;
 216
 1056217                    foreach (ushort gridIndex in gridList)
 218                    {
 264219                        if (!world.ActiveGrids.IsAllocated(gridIndex) || !processedGrids.Add(gridIndex))
 220                            continue;
 221
 264222                        VoxelGrid currentGrid = world.ActiveGrids[gridIndex];
 223
 264224                        (int xMin, int yMin, int zMin) = currentGrid.SnapToScanCell(snappedMin);
 264225                        (int xMax, int yMax, int zMax) = currentGrid.SnapToScanCell(snappedMax);
 226
 1586227                        for (int x = xMin; x <= xMax; x++)
 228                        {
 2116229                            for (int y = yMin; y <= yMax; y++)
 230                            {
 3188231                                for (int z = zMin; z <= zMax; z++)
 232                                {
 1065233                                    int scanCellKey = currentGrid.GetScanCellKey(x, y, z);
 1065234                                    if (scanCellKey == -1
 1065235                                        || !currentGrid.TryGetScanCell(scanCellKey, out ScanCell? scanCell)
 1065236                                        || voxelRedundancyCheck.Add(scanCell!) != true)
 237                                    {
 238                                        continue;
 239                                    }
 240
 1065241                                    scanCells.Add(scanCell!);
 242                                }
 243                            }
 244                        }
 245                    }
 246                }
 247            }
 248        }
 265249    }
 250
 251    private static IEnumerable<GridVoxelSet> TraceLineIterator(
 252        GridWorld world,
 253        Vector3d start,
 254        Vector3d end,
 255        Fixed64? padding,
 256        bool includeEnd)
 257    {
 11258        SwiftDictionary<VoxelGrid, SwiftList<Voxel>> gridVoxelMapping = new();
 11259        SwiftHashSet<Voxel> voxelRedundancyCheck = SwiftHashSetPool<Voxel>.Shared.Rent();
 260
 11261        (Vector3d snappedMin, Vector3d snappedMax) =
 11262            world.SnapBoundsToVoxelSize(start, end, padding);
 263
 264        // Preserve the caller's trace direction while still using snapped bounds for coverage lookup.
 11265        Vector3d traceStart = new(
 11266            start.x <= end.x ? snappedMin.x : snappedMax.x,
 11267            start.y <= end.y ? snappedMin.y : snappedMax.y,
 11268            start.z <= end.z ? snappedMin.z : snappedMax.z);
 11269        Vector3d traceEnd = new(
 11270            start.x <= end.x ? snappedMax.x : snappedMin.x,
 11271            start.y <= end.y ? snappedMax.y : snappedMin.y,
 11272            start.z <= end.z ? snappedMax.z : snappedMin.z);
 273
 11274        Vector3d diff = traceEnd - traceStart;
 11275        Vector3d delta = Vector3d.Abs(diff);
 276
 11277        Fixed64 steps = FixedMath.Ceiling(FixedMath.Max(FixedMath.Max(delta.x, delta.y), delta.z));
 278
 11279        Fixed64 stepX = diff.x / (steps + Fixed64.One);
 11280        Fixed64 stepY = diff.y / (steps + Fixed64.One);
 11281        Fixed64 stepZ = diff.z / (steps + Fixed64.One);
 282
 50283        foreach (int cellIndex in world.GetSpatialGridCells(snappedMin, snappedMax))
 284        {
 14285            if (!world.SpatialGridHash.TryGetValue(cellIndex, out SwiftHashSet<ushort> gridList))
 286                continue;
 287
 54288            foreach (ushort gridIndex in gridList)
 289            {
 14290                if (!world.ActiveGrids.IsAllocated(gridIndex))
 291                    continue;
 292
 13293                VoxelGrid currentGrid = world.ActiveGrids[gridIndex];
 13294                if (gridVoxelMapping.ContainsKey(currentGrid))
 295                    continue;
 296
 11297                SwiftList<Voxel> voxelList = SwiftListPool<Voxel>.Shared.Rent();
 11298                gridVoxelMapping.Add(currentGrid, voxelList);
 299
 322300                for (Fixed64 i = Fixed64.Zero; i <= steps; i += Fixed64.One)
 301                {
 150302                    Vector3d tracePos = world.FloorToVoxelSize(
 150303                        new Vector3d(
 150304                            traceStart.x + stepX * i,
 150305                            traceStart.y + stepY * i,
 150306                            traceStart.z + stepZ * i));
 307
 150308                    if (!currentGrid.TryGetVoxel(tracePos, out Voxel? voxel) || voxelRedundancyCheck.Add(voxel!) != true
 309                        continue;
 310
 127311                    voxelList.Add(voxel!);
 312                }
 313            }
 314        }
 315
 11316        if (includeEnd
 11317            && world.TryGetGridAndVoxel(end, out VoxelGrid? endGrid, out Voxel? endVoxel)
 11318            && gridVoxelMapping.TryGetValue(endGrid!, out SwiftList<Voxel> endVoxelList)
 11319            && voxelRedundancyCheck.Add(endVoxel!))
 320        {
 6321            endVoxelList.Add(endVoxel!);
 322        }
 323
 44324        foreach (KeyValuePair<VoxelGrid, SwiftList<Voxel>> kvp in gridVoxelMapping)
 325        {
 11326            yield return new GridVoxelSet(kvp.Key, kvp.Value);
 11327            SwiftListPool<Voxel>.Shared.Release(kvp.Value);
 11328        }
 329
 11330        SwiftHashSetPool<Voxel>.Shared.Release(voxelRedundancyCheck);
 11331    }
 332
 333    private static IEnumerable<GridVoxelSet> GetCoveredVoxelsIterator(
 334        GridWorld world,
 335        Vector3d boundsMin,
 336        Vector3d boundsMax,
 337        Fixed64? padding)
 338    {
 152339        SwiftDictionary<VoxelGrid, SwiftList<Voxel>> gridVoxelMapping = new();
 152340        SwiftHashSet<Voxel> voxelRedundancyCheck = SwiftHashSetPool<Voxel>.Shared.Rent();
 341
 152342        (Vector3d snappedMin, Vector3d snappedMax) =
 152343            world.SnapBoundsToVoxelSize(boundsMin, boundsMax, padding);
 344
 624345        foreach (int cellIndex in world.GetSpatialGridCells(snappedMin, snappedMax))
 346        {
 160347            if (!world.SpatialGridHash.TryGetValue(cellIndex, out SwiftHashSet<ushort> gridList))
 348                continue;
 349
 642350            foreach (ushort gridIndex in gridList)
 351            {
 163352                if (!world.ActiveGrids.IsAllocated(gridIndex))
 353                    continue;
 354
 162355                VoxelGrid currentGrid = world.ActiveGrids[gridIndex];
 162356                if (gridVoxelMapping.ContainsKey(currentGrid))
 357                    continue;
 358
 154359                SwiftList<Voxel> voxelList = SwiftListPool<Voxel>.Shared.Rent();
 154360                gridVoxelMapping.Add(currentGrid, voxelList);
 361
 154362                Fixed64 resolution = world.VoxelSize;
 982363                for (Fixed64 x = snappedMin.x; x <= snappedMax.x; x += resolution)
 364                {
 1348365                    for (Fixed64 y = snappedMin.y; y <= snappedMax.y; y += resolution)
 366                    {
 2456367                        for (Fixed64 z = snappedMin.z; z <= snappedMax.z; z += resolution)
 368                        {
 891369                            Vector3d position = new(x, y, z);
 891370                            if (!currentGrid.TryGetVoxel(position, out Voxel? voxel) || voxelRedundancyCheck.Add(voxel!)
 371                                continue;
 372
 862373                            voxelList.Add(voxel!);
 374                        }
 375                    }
 376                }
 377            }
 378        }
 379
 612380        foreach (KeyValuePair<VoxelGrid, SwiftList<Voxel>> kvp in gridVoxelMapping)
 381        {
 154382            yield return new GridVoxelSet(kvp.Key, kvp.Value);
 154383            SwiftListPool<Voxel>.Shared.Release(kvp.Value);
 154384        }
 385
 152386        SwiftHashSetPool<Voxel>.Shared.Release(voxelRedundancyCheck);
 152387    }
 388
 389    private static IEnumerable<ScanCell> GetCoveredScanCellsIterator(
 390        GridWorld world,
 391        Vector3d boundsMin,
 392        Vector3d boundsMax,
 393        Fixed64? padding)
 394    {
 2395        SwiftList<ScanCell> scanCells = SwiftListPool<ScanCell>.Shared.Rent();
 2396        SwiftHashSet<ushort> processedGrids = SwiftHashSetPool<ushort>.Shared.Rent();
 2397        SwiftHashSet<ScanCell> voxelRedundancyCheck = SwiftHashSetPool<ScanCell>.Shared.Rent();
 398
 2399        (Vector3d snappedMin, Vector3d snappedMax) =
 2400            world.SnapBoundsToVoxelSize(boundsMin, boundsMax, padding);
 401
 14402        foreach (int cellIndex in world.GetSpatialGridCells(snappedMin, snappedMax))
 403        {
 5404            if (!world.SpatialGridHash.TryGetValue(cellIndex, out SwiftHashSet<ushort> gridList))
 405                continue;
 406
 18407            foreach (ushort gridIndex in gridList)
 408            {
 5409                if (!world.ActiveGrids.IsAllocated(gridIndex) || !processedGrids.Add(gridIndex))
 410                    continue;
 411
 2412                VoxelGrid currentGrid = world.ActiveGrids[gridIndex];
 413
 2414                (int xMin, int yMin, int zMin) = currentGrid.SnapToScanCell(snappedMin);
 2415                (int xMax, int yMax, int zMax) = currentGrid.SnapToScanCell(snappedMax);
 416
 20417                for (int x = xMin; x <= xMax; x++)
 418                {
 32419                    for (int y = yMin; y <= yMax; y++)
 420                    {
 32421                        for (int z = zMin; z <= zMax; z++)
 422                        {
 8423                            int scanCellKey = currentGrid.GetScanCellKey(x, y, z);
 8424                            if (scanCellKey == -1
 8425                                || !currentGrid.TryGetScanCell(scanCellKey, out ScanCell? scanCell)
 8426                                || voxelRedundancyCheck.Add(scanCell!) != true)
 427                            {
 428                                continue;
 429                            }
 430
 7431                            scanCells.Add(scanCell!);
 432                        }
 433                    }
 434                }
 435            }
 436        }
 437
 18438        foreach (ScanCell scanCell in scanCells)
 7439            yield return scanCell;
 440
 2441        SwiftListPool<ScanCell>.Shared.Release(scanCells);
 2442        SwiftHashSetPool<ushort>.Shared.Release(processedGrids);
 2443        SwiftHashSetPool<ScanCell>.Shared.Release(voxelRedundancyCheck);
 2444    }
 445}
Generated by: ReportGenerator 5.5.9.0
05/07/2026 - 15:39:52
GitHub | reportgenerator.io

Methods/Properties

TraceLine(GridForge.Grids.GridWorld,FixedMathSharp.Vector3d,FixedMathSharp.Vector3d,System.Nullable`1<FixedMathSharp.Fixed64>,System.Boolean)
TraceLine(GridForge.Grids.GridWorld,FixedMathSharp.Vector2d,FixedMathSharp.Vector2d,System.Nullable`1<FixedMathSharp.Fixed64>,System.Boolean)
GetCoveredVoxels(GridForge.Grids.GridWorld,FixedMathSharp.Vector3d,FixedMathSharp.Vector3d,System.Nullable`1<FixedMathSharp.Fixed64>)
GetCoveredScanCells(GridForge.Grids.GridWorld,FixedMathSharp.Vector3d,FixedMathSharp.Vector3d,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.Vector3d,FixedMathSharp.Vector3d,SwiftCollections.SwiftList`1<GridForge.Grids.ScanCell>,GridForge.Grids.GridScanScratch,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>)
AddCoveredScanCellsCore(GridForge.Grids.GridWorld,FixedMathSharp.Vector3d,FixedMathSharp.Vector3d,SwiftCollections.SwiftList`1<GridForge.Grids.ScanCell>,SwiftCollections.SwiftHashSet`1<System.UInt16>,SwiftCollections.SwiftHashSet`1<GridForge.Grids.ScanCell>,System.Nullable`1<FixedMathSharp.Fixed64>)
TraceLineIterator()
GetCoveredVoxelsIterator()
GetCoveredScanCellsIterator()