| | | 1 | | //======================================================================= |
| | | 2 | | // SwiftFixedOctree.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 | | |
| | | 11 | | namespace SwiftCollections.Query; |
| | | 12 | | |
| | | 13 | | /// <summary> |
| | | 14 | | /// Represents a fixed-point octree optimized for deterministic hierarchical spatial queries. |
| | | 15 | | /// </summary> |
| | | 16 | | public sealed class SwiftFixedOctree<T> : SwiftOctree<T, FixedBoundVolume> |
| | | 17 | | { |
| | | 18 | | /// <summary> |
| | | 19 | | /// Initializes a new instance of the <see cref="SwiftFixedOctree{T}"/> class. |
| | | 20 | | /// </summary> |
| | | 21 | | /// <param name="worldBounds">The immutable world bounds covered by the octree.</param> |
| | | 22 | | /// <param name="options">Backend-neutral octree options.</param> |
| | | 23 | | /// <param name="minNodeSize">The minimum child-node axis length allowed for fixed-point subdivision.</param> |
| | | 24 | | public SwiftFixedOctree(FixedBoundVolume worldBounds, SwiftOctreeOptions options, Fixed64 minNodeSize) |
| | 15 | 25 | | : base(worldBounds, options, new FixedBoundVolumeOctreePartitioner(minNodeSize)) |
| | 13 | 26 | | { } |
| | | 27 | | |
| | | 28 | | private sealed class FixedBoundVolumeOctreePartitioner : IOctreeBoundsPartitioner<FixedBoundVolume> |
| | | 29 | | { |
| | | 30 | | private readonly Fixed64 _minNodeSize; |
| | | 31 | | |
| | 15 | 32 | | public FixedBoundVolumeOctreePartitioner(Fixed64 minNodeSize) |
| | | 33 | | { |
| | 15 | 34 | | if (minNodeSize <= Fixed64.Zero) |
| | 2 | 35 | | throw new System.ArgumentOutOfRangeException(nameof(minNodeSize), minNodeSize, "Minimum node size must b |
| | | 36 | | |
| | 13 | 37 | | _minNodeSize = minNodeSize; |
| | 13 | 38 | | } |
| | | 39 | | |
| | | 40 | | public bool ContainsBounds(FixedBoundVolume outer, FixedBoundVolume inner) |
| | | 41 | | { |
| | 29 | 42 | | return inner.Min.X >= outer.Min.X && |
| | 29 | 43 | | inner.Min.Y >= outer.Min.Y && |
| | 29 | 44 | | inner.Min.Z >= outer.Min.Z && |
| | 29 | 45 | | inner.Max.X <= outer.Max.X && |
| | 29 | 46 | | inner.Max.Y <= outer.Max.Y && |
| | 29 | 47 | | inner.Max.Z <= outer.Max.Z; |
| | | 48 | | } |
| | | 49 | | |
| | | 50 | | public bool CanSubdivide(FixedBoundVolume bounds) |
| | | 51 | | { |
| | 5 | 52 | | Vector3d min = bounds.Min; |
| | 5 | 53 | | Vector3d midpoint = bounds.Center; |
| | 5 | 54 | | Vector3d max = bounds.Max; |
| | 5 | 55 | | ulong requiredRawSpan = (ulong)_minNodeSize.m_rawValue; |
| | 5 | 56 | | return HasMinimumChildSpan(min.X, midpoint.X, max.X, requiredRawSpan) |
| | 5 | 57 | | & HasMinimumChildSpan(min.Y, midpoint.Y, max.Y, requiredRawSpan) |
| | 5 | 58 | | & HasMinimumChildSpan(min.Z, midpoint.Z, max.Z, requiredRawSpan); |
| | | 59 | | } |
| | | 60 | | |
| | | 61 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 62 | | private static bool HasMinimumChildSpan( |
| | | 63 | | Fixed64 min, |
| | | 64 | | Fixed64 midpoint, |
| | | 65 | | Fixed64 max, |
| | | 66 | | ulong requiredRawSpan) |
| | | 67 | | { |
| | | 68 | | // Ordered raw endpoints can span the complete signed scalar domain; |
| | | 69 | | // unsigned subtraction preserves that exact non-negative distance. |
| | 15 | 70 | | ulong lowerRawSpan = unchecked((ulong)midpoint.m_rawValue - (ulong)min.m_rawValue); |
| | 15 | 71 | | ulong upperRawSpan = unchecked((ulong)max.m_rawValue - (ulong)midpoint.m_rawValue); |
| | 15 | 72 | | return lowerRawSpan >= requiredRawSpan & upperRawSpan >= requiredRawSpan; |
| | | 73 | | } |
| | | 74 | | |
| | | 75 | | public bool TryGetContainingChildIndex(FixedBoundVolume nodeBounds, FixedBoundVolume entryBounds, out int childI |
| | | 76 | | { |
| | 17 | 77 | | Vector3d midpoint = nodeBounds.Center; |
| | | 78 | | |
| | | 79 | | int xBit; |
| | 17 | 80 | | if (entryBounds.Min.X >= midpoint.X) |
| | 7 | 81 | | xBit = 1; |
| | 10 | 82 | | else if (entryBounds.Max.X <= midpoint.X) |
| | 9 | 83 | | xBit = 0; |
| | | 84 | | else |
| | | 85 | | { |
| | 1 | 86 | | childIndex = -1; |
| | 1 | 87 | | return false; |
| | | 88 | | } |
| | | 89 | | |
| | | 90 | | int yBit; |
| | 16 | 91 | | if (entryBounds.Min.Y >= midpoint.Y) |
| | 7 | 92 | | yBit = 1; |
| | 9 | 93 | | else if (entryBounds.Max.Y <= midpoint.Y) |
| | 8 | 94 | | yBit = 0; |
| | | 95 | | else |
| | | 96 | | { |
| | 1 | 97 | | childIndex = -1; |
| | 1 | 98 | | return false; |
| | | 99 | | } |
| | | 100 | | |
| | | 101 | | int zBit; |
| | 15 | 102 | | if (entryBounds.Min.Z >= midpoint.Z) |
| | 7 | 103 | | zBit = 1; |
| | 8 | 104 | | else if (entryBounds.Max.Z <= midpoint.Z) |
| | 7 | 105 | | zBit = 0; |
| | | 106 | | else |
| | | 107 | | { |
| | 1 | 108 | | childIndex = -1; |
| | 1 | 109 | | return false; |
| | | 110 | | } |
| | | 111 | | |
| | 14 | 112 | | childIndex = xBit | (yBit << 1) | (zBit << 2); |
| | 14 | 113 | | return true; |
| | | 114 | | } |
| | | 115 | | |
| | | 116 | | public FixedBoundVolume CreateChildBounds(FixedBoundVolume parentBounds, int childIndex) |
| | | 117 | | { |
| | 32 | 118 | | Vector3d midpoint = parentBounds.Center; |
| | 32 | 119 | | bool upperX = (childIndex & 1) != 0; |
| | 32 | 120 | | bool upperY = (childIndex & 2) != 0; |
| | 32 | 121 | | bool upperZ = (childIndex & 4) != 0; |
| | | 122 | | |
| | 32 | 123 | | return new FixedBoundVolume( |
| | 32 | 124 | | new Vector3d( |
| | 32 | 125 | | upperX ? midpoint.X : parentBounds.Min.X, |
| | 32 | 126 | | upperY ? midpoint.Y : parentBounds.Min.Y, |
| | 32 | 127 | | upperZ ? midpoint.Z : parentBounds.Min.Z), |
| | 32 | 128 | | new Vector3d( |
| | 32 | 129 | | upperX ? parentBounds.Max.X : midpoint.X, |
| | 32 | 130 | | upperY ? parentBounds.Max.Y : midpoint.Y, |
| | 32 | 131 | | upperZ ? parentBounds.Max.Z : midpoint.Z)); |
| | | 132 | | } |
| | | 133 | | } |
| | | 134 | | } |