| | | 1 | | //======================================================================= |
| | | 2 | | // HexPrismTopology.cs |
| | | 3 | | //======================================================================= |
| | | 4 | | // MIT License, Copyright (c) 2024-present David Oravsky (mrdav30) |
| | | 5 | | // See LICENSE file in the project root for full license information. |
| | | 6 | | //======================================================================= |
| | | 7 | | |
| | | 8 | | using System.Runtime.CompilerServices; |
| | | 9 | | using FixedMathSharp; |
| | | 10 | | using GridForge.Spatial; |
| | | 11 | | |
| | | 12 | | namespace GridForge.Grids.Topology; |
| | | 13 | | |
| | | 14 | | internal sealed class HexPrismTopology : IGridTopology |
| | | 15 | | { |
| | 1228 | 16 | | public GridTopologyKind Kind => GridTopologyKind.HexPrism; |
| | | 17 | | |
| | | 18 | | public GridTopologyMetrics Metrics { get; } |
| | | 19 | | |
| | 154 | 20 | | public Fixed64 OverlapTolerance => MaxCellEdge * Fixed64.Half; |
| | | 21 | | |
| | 321 | 22 | | public Fixed64 MaxCellEdge => Metrics.LargestHexEdge; |
| | | 23 | | |
| | 1770 | 24 | | public int NeighborSlotCount => HexDirectionUtility.Offsets.Length; |
| | | 25 | | |
| | 4283 | 26 | | public HexPrismTopology(GridTopologyMetrics metrics) |
| | | 27 | | { |
| | 4283 | 28 | | Metrics = GridTopologyMetrics.Normalize(GridTopologyKind.HexPrism, metrics); |
| | 4283 | 29 | | } |
| | | 30 | | |
| | | 31 | | public GridDimensions CalculateDimensions(Vector3d boundsMin, Vector3d boundsMax) |
| | | 32 | | { |
| | 4423 | 33 | | VoxelIndex maxIndex = GetMaxIndex(boundsMin, boundsMax); |
| | 4423 | 34 | | int height = ((boundsMax.Y - boundsMin.Y) / Metrics.LayerHeight).FloorToInt() + 1; |
| | 4423 | 35 | | return new GridDimensions(maxIndex.x + 1, height, maxIndex.z + 1); |
| | | 36 | | } |
| | | 37 | | |
| | | 38 | | public (Vector3d min, Vector3d max) NormalizeBounds(Vector3d min, Vector3d max, Fixed64? padding = null) |
| | | 39 | | { |
| | 4281 | 40 | | Fixed64 fixedPadding = padding.HasValue && padding.Value > Fixed64.Zero |
| | 4281 | 41 | | ? padding.Value |
| | 4281 | 42 | | : Fixed64.Zero; |
| | | 43 | | |
| | 4281 | 44 | | min -= fixedPadding; |
| | 4281 | 45 | | max += fixedPadding; |
| | | 46 | | |
| | 4281 | 47 | | Fixed64 yMin = FloorToLayerOrigin(min.Y); |
| | 4281 | 48 | | Fixed64 yMax = CeilToLayerOrigin(max.Y); |
| | 4281 | 49 | | Vector3d normalizedMin = new(min.X, yMin, min.Z); |
| | | 50 | | |
| | 4281 | 51 | | VoxelIndex maxIndex = GetMaxIndex(normalizedMin, max); |
| | 4281 | 52 | | int maxY = ((yMax - yMin) / Metrics.LayerHeight).FloorToInt(); |
| | 4281 | 53 | | Vector3d normalizedMax = normalizedMin + HexCoordinateUtility.AxialToWorldOffset(new VoxelIndex(maxIndex.x, maxY |
| | | 54 | | |
| | 4281 | 55 | | return (normalizedMin, normalizedMax); |
| | | 56 | | } |
| | | 57 | | |
| | | 58 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 59 | | public bool IsInBounds( |
| | | 60 | | Vector3d boundsMin, |
| | | 61 | | Vector3d boundsMax, |
| | | 62 | | int width, |
| | | 63 | | int height, |
| | | 64 | | int length, |
| | | 65 | | Vector3d position) => |
| | 24 | 66 | | TryGetVoxelIndex(boundsMin, boundsMax, width, height, length, position, out _); |
| | | 67 | | |
| | | 68 | | public bool TryGetVoxelIndex( |
| | | 69 | | Vector3d boundsMin, |
| | | 70 | | Vector3d boundsMax, |
| | | 71 | | int width, |
| | | 72 | | int height, |
| | | 73 | | int length, |
| | | 74 | | Vector3d position, |
| | | 75 | | out VoxelIndex result) |
| | | 76 | | { |
| | 78 | 77 | | result = default; |
| | | 78 | | |
| | 78 | 79 | | if (!IsInsideCoarseBounds(boundsMin, boundsMax, position)) |
| | 5 | 80 | | return false; |
| | | 81 | | |
| | 73 | 82 | | HexCoordinateUtility.WorldOffsetToAxial( |
| | 73 | 83 | | position.X - boundsMin.X, |
| | 73 | 84 | | position.Z - boundsMin.Z, |
| | 73 | 85 | | Metrics, |
| | 73 | 86 | | out Fixed64 q, |
| | 73 | 87 | | out Fixed64 r); |
| | | 88 | | |
| | 73 | 89 | | Fixed64 layer = (position.Y - boundsMin.Y) / Metrics.LayerHeight; |
| | 73 | 90 | | VoxelIndex rounded = HexCoordinateUtility.RoundAxial(q, layer, r); |
| | 73 | 91 | | if ((uint)rounded.x >= (uint)width |
| | 73 | 92 | | || (uint)rounded.y >= (uint)height |
| | 73 | 93 | | || (uint)rounded.z >= (uint)length) |
| | | 94 | | { |
| | 7 | 95 | | return false; |
| | | 96 | | } |
| | | 97 | | |
| | 66 | 98 | | result = rounded; |
| | 66 | 99 | | return true; |
| | | 100 | | } |
| | | 101 | | |
| | | 102 | | public VoxelIndex GetClosestVoxelIndex( |
| | | 103 | | Vector3d boundsMin, |
| | | 104 | | int width, |
| | | 105 | | int height, |
| | | 106 | | int length, |
| | | 107 | | Vector3d position) |
| | | 108 | | { |
| | 116 | 109 | | HexCoordinateUtility.WorldOffsetToAxial( |
| | 116 | 110 | | position.X - boundsMin.X, |
| | 116 | 111 | | position.Z - boundsMin.Z, |
| | 116 | 112 | | Metrics, |
| | 116 | 113 | | out Fixed64 q, |
| | 116 | 114 | | out Fixed64 r); |
| | 116 | 115 | | HexCoordinateUtility.RoundCube(q, r, out int roundedQ, out int roundedR); |
| | | 116 | | |
| | 116 | 117 | | int roundedY = ((position.Y - boundsMin.Y) / Metrics.LayerHeight).RoundToInt(); |
| | 116 | 118 | | return new VoxelIndex( |
| | 116 | 119 | | FixedMath.Clamp(roundedQ, 0, width - 1), |
| | 116 | 120 | | FixedMath.Clamp(roundedY, 0, height - 1), |
| | 116 | 121 | | FixedMath.Clamp(roundedR, 0, length - 1)); |
| | | 122 | | } |
| | | 123 | | |
| | | 124 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 125 | | public Vector3d GetWorldPosition(Vector3d boundsMin, VoxelIndex index) => |
| | 209485 | 126 | | boundsMin + HexCoordinateUtility.AxialToWorldOffset(index, Metrics); |
| | | 127 | | |
| | | 128 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 129 | | public Vector3d GetWorldOffset((int x, int y, int z) offset) => |
| | 767 | 130 | | HexCoordinateUtility.AxialToWorldOffset(new VoxelIndex(offset.x, offset.y, offset.z), Metrics); |
| | | 131 | | |
| | 1660 | 132 | | public VoxelIndex GetNeighborOffset(int slot) => HexDirectionUtility.Offsets[slot]; |
| | | 133 | | |
| | | 134 | | public bool TryGetNeighborSlotFromWorldDelta(Vector3d worldDelta, out int slot) |
| | | 135 | | { |
| | 42 | 136 | | HexCoordinateUtility.WorldOffsetToAxial( |
| | 42 | 137 | | worldDelta.X, |
| | 42 | 138 | | worldDelta.Z, |
| | 42 | 139 | | Metrics, |
| | 42 | 140 | | out Fixed64 q, |
| | 42 | 141 | | out Fixed64 r); |
| | 42 | 142 | | HexCoordinateUtility.RoundCube(q, r, out int roundedQ, out int roundedR); |
| | | 143 | | |
| | 42 | 144 | | int yDirection = worldDelta.Y.Sign(); |
| | 42 | 145 | | if (yDirection != 0) |
| | | 146 | | { |
| | 15 | 147 | | if (roundedQ == 0 && roundedR == 0) |
| | 9 | 148 | | return TryGetNeighborSlot(new VoxelIndex(0, yDirection, 0), out slot); |
| | | 149 | | |
| | 6 | 150 | | VoxelIndex planarOffset = NormalizePlanarOffset(roundedQ, roundedR); |
| | 6 | 151 | | if (planarOffset == default) |
| | | 152 | | { |
| | 1 | 153 | | slot = -1; |
| | 1 | 154 | | return false; |
| | | 155 | | } |
| | | 156 | | |
| | 5 | 157 | | return TryGetNeighborSlot(new VoxelIndex(planarOffset.x, yDirection, planarOffset.z), out slot); |
| | | 158 | | } |
| | | 159 | | |
| | 27 | 160 | | return TryGetNeighborSlot(NormalizePlanarOffset(roundedQ, roundedR), out slot); |
| | | 161 | | } |
| | | 162 | | |
| | | 163 | | public bool IsFacingBoundary(VoxelIndex voxelIndex, int slot, int width, int height, int length) |
| | | 164 | | { |
| | 4 | 165 | | VoxelIndex offset = HexDirectionUtility.Offsets[slot]; |
| | 4 | 166 | | return RectangularDirectionUtility.IsAxisFacingBoundary(voxelIndex.x, offset.x, width) |
| | 4 | 167 | | && RectangularDirectionUtility.IsAxisFacingBoundary(voxelIndex.y, offset.y, height) |
| | 4 | 168 | | && RectangularDirectionUtility.IsAxisFacingBoundary(voxelIndex.z, offset.z, length); |
| | | 169 | | } |
| | | 170 | | |
| | | 171 | | public void GetBoundaryRange( |
| | | 172 | | int slot, |
| | | 173 | | int width, |
| | | 174 | | int height, |
| | | 175 | | int length, |
| | | 176 | | out int xStart, |
| | | 177 | | out int xEnd, |
| | | 178 | | out int yStart, |
| | | 179 | | out int yEnd, |
| | | 180 | | out int zStart, |
| | | 181 | | out int zEnd) |
| | | 182 | | { |
| | 1 | 183 | | VoxelIndex offset = HexDirectionUtility.Offsets[slot]; |
| | 1 | 184 | | (xStart, xEnd) = RectangularDirectionUtility.GetBoundaryRange(offset.x, width); |
| | 1 | 185 | | (yStart, yEnd) = RectangularDirectionUtility.GetBoundaryRange(offset.y, height); |
| | 1 | 186 | | (zStart, zEnd) = RectangularDirectionUtility.GetBoundaryRange(offset.z, length); |
| | 1 | 187 | | } |
| | | 188 | | |
| | | 189 | | public Vector3d FloorToGrid( |
| | | 190 | | Vector3d boundsMin, |
| | | 191 | | Vector3d boundsMax, |
| | | 192 | | int width, |
| | | 193 | | int height, |
| | | 194 | | int length, |
| | | 195 | | Vector3d position) |
| | | 196 | | { |
| | 25 | 197 | | VoxelIndex index = ClampToGrid(boundsMin, width, height, length, position); |
| | 25 | 198 | | return GetWorldPosition(boundsMin, index); |
| | | 199 | | } |
| | | 200 | | |
| | | 201 | | public Vector3d CeilToGrid( |
| | | 202 | | Vector3d boundsMin, |
| | | 203 | | Vector3d boundsMax, |
| | | 204 | | int width, |
| | | 205 | | int height, |
| | | 206 | | int length, |
| | | 207 | | Vector3d position) |
| | | 208 | | { |
| | 7 | 209 | | VoxelIndex index = ClampToGrid(boundsMin, width, height, length, position); |
| | 7 | 210 | | return GetWorldPosition(boundsMin, index); |
| | | 211 | | } |
| | | 212 | | |
| | | 213 | | public (int x, int y, int z) SnapToScanCell(Vector3d boundsMin, Vector3d position, int scanCellSize) |
| | | 214 | | { |
| | 7 | 215 | | HexCoordinateUtility.WorldOffsetToAxial( |
| | 7 | 216 | | position.X - boundsMin.X, |
| | 7 | 217 | | position.Z - boundsMin.Z, |
| | 7 | 218 | | Metrics, |
| | 7 | 219 | | out Fixed64 q, |
| | 7 | 220 | | out Fixed64 r); |
| | | 221 | | |
| | 7 | 222 | | Fixed64 layer = (position.Y - boundsMin.Y) / Metrics.LayerHeight; |
| | 7 | 223 | | VoxelIndex index = HexCoordinateUtility.RoundAxial(q, layer, r); |
| | 7 | 224 | | return (index.x / scanCellSize, index.y / scanCellSize, index.z / scanCellSize); |
| | | 225 | | } |
| | | 226 | | |
| | | 227 | | private VoxelIndex ClampToGrid( |
| | | 228 | | Vector3d boundsMin, |
| | | 229 | | int width, |
| | | 230 | | int height, |
| | | 231 | | int length, |
| | | 232 | | Vector3d position) |
| | | 233 | | { |
| | 32 | 234 | | HexCoordinateUtility.WorldOffsetToAxial( |
| | 32 | 235 | | position.X - boundsMin.X, |
| | 32 | 236 | | position.Z - boundsMin.Z, |
| | 32 | 237 | | Metrics, |
| | 32 | 238 | | out Fixed64 q, |
| | 32 | 239 | | out Fixed64 r); |
| | | 240 | | |
| | 32 | 241 | | Fixed64 layer = (position.Y - boundsMin.Y) / Metrics.LayerHeight; |
| | 32 | 242 | | VoxelIndex rounded = HexCoordinateUtility.RoundAxial(q, layer, r); |
| | | 243 | | |
| | 32 | 244 | | return new VoxelIndex( |
| | 32 | 245 | | FixedMath.Clamp(rounded.x, 0, width - 1), |
| | 32 | 246 | | FixedMath.Clamp(rounded.y, 0, height - 1), |
| | 32 | 247 | | FixedMath.Clamp(rounded.z, 0, length - 1)); |
| | | 248 | | } |
| | | 249 | | |
| | | 250 | | private VoxelIndex GetMaxIndex(Vector3d boundsMin, Vector3d boundsMax) |
| | | 251 | | { |
| | 8704 | 252 | | HexCoordinateUtility.WorldOffsetToAxial( |
| | 8704 | 253 | | boundsMax.X - boundsMin.X, |
| | 8704 | 254 | | boundsMax.Z - boundsMin.Z, |
| | 8704 | 255 | | Metrics, |
| | 8704 | 256 | | out Fixed64 qMax, |
| | 8704 | 257 | | out Fixed64 rMax); |
| | | 258 | | |
| | | 259 | | // An odd raw width at an odd coupled index rounds its half-raw center to even. |
| | | 260 | | // Its continuous inverse can sit on either side of the integer address. |
| | | 261 | | // Preserve exact authored corners before applying outward rounding. |
| | 8704 | 262 | | HexCoordinateUtility.RoundCube(qMax, rMax, out int roundedQ, out int roundedR); |
| | 8704 | 263 | | VoxelIndex rounded = new VoxelIndex(roundedQ, 0, roundedR); |
| | 8704 | 264 | | Vector3d projected = HexCoordinateUtility.AxialToWorldOffset(rounded, Metrics); |
| | 8704 | 265 | | if (roundedQ >= 0 && roundedR >= 0 |
| | 8704 | 266 | | && projected.X == boundsMax.X - boundsMin.X |
| | 8704 | 267 | | && projected.Z == boundsMax.Z - boundsMin.Z) |
| | | 268 | | { |
| | 7691 | 269 | | return rounded; |
| | | 270 | | } |
| | | 271 | | |
| | 1013 | 272 | | int maxQ = HexCoordinateUtility.CeilToIntWithTolerance(FixedMath.Max(qMax, Fixed64.Zero)); |
| | 1013 | 273 | | int maxR = HexCoordinateUtility.CeilToIntWithTolerance(FixedMath.Max(rMax, Fixed64.Zero)); |
| | | 274 | | |
| | 1013 | 275 | | return new VoxelIndex( |
| | 1013 | 276 | | maxQ, |
| | 1013 | 277 | | 0, |
| | 1013 | 278 | | maxR); |
| | | 279 | | } |
| | | 280 | | |
| | | 281 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 282 | | private bool IsInsideCoarseBounds(Vector3d boundsMin, Vector3d boundsMax, Vector3d position) => |
| | 78 | 283 | | boundsMin.X <= position.X && position.X <= boundsMax.X |
| | 78 | 284 | | && boundsMin.Y <= position.Y && position.Y <= boundsMax.Y |
| | 78 | 285 | | && boundsMin.Z <= position.Z && position.Z <= boundsMax.Z; |
| | | 286 | | |
| | | 287 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 288 | | private Fixed64 FloorToLayerOrigin(Fixed64 coordinate) => |
| | 4281 | 289 | | (coordinate / Metrics.LayerHeight).FloorToInt() * Metrics.LayerHeight; |
| | | 290 | | |
| | | 291 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 292 | | private Fixed64 CeilToLayerOrigin(Fixed64 coordinate) => |
| | 4281 | 293 | | (coordinate / Metrics.LayerHeight).CeilToInt() * Metrics.LayerHeight; |
| | | 294 | | |
| | | 295 | | private static bool TryGetNeighborSlot(VoxelIndex neighborOffset, out int slot) |
| | | 296 | | { |
| | 726 | 297 | | for (int i = 0; i < HexDirectionUtility.Offsets.Length; i++) |
| | | 298 | | { |
| | 356 | 299 | | if (HexDirectionUtility.Offsets[i] == neighborOffset) |
| | | 300 | | { |
| | 34 | 301 | | slot = i; |
| | 34 | 302 | | return true; |
| | | 303 | | } |
| | | 304 | | } |
| | | 305 | | |
| | 7 | 306 | | slot = -1; |
| | 7 | 307 | | return false; |
| | | 308 | | } |
| | | 309 | | |
| | | 310 | | private static VoxelIndex NormalizePlanarOffset(int q, int r) |
| | | 311 | | { |
| | 33 | 312 | | if (q > 0 && r == 0) |
| | 13 | 313 | | return new VoxelIndex(1, 0, 0); |
| | 20 | 314 | | if (q > 0 && r < 0) |
| | 1 | 315 | | return new VoxelIndex(1, 0, -1); |
| | 19 | 316 | | if (q == 0 && r < 0) |
| | 1 | 317 | | return new VoxelIndex(0, 0, -1); |
| | 18 | 318 | | if (q < 0 && r == 0) |
| | 7 | 319 | | return new VoxelIndex(-1, 0, 0); |
| | 11 | 320 | | if (q < 0 && r > 0) |
| | 2 | 321 | | return new VoxelIndex(-1, 0, 1); |
| | 9 | 322 | | if (q == 0 && r > 0) |
| | 1 | 323 | | return new VoxelIndex(0, 0, 1); |
| | | 324 | | |
| | 8 | 325 | | return default; |
| | | 326 | | } |
| | | 327 | | } |