| | | 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 FixedMathSharp; |
| | | 9 | | |
| | | 10 | | namespace SwiftCollections.Query; |
| | | 11 | | |
| | | 12 | | /// <summary> |
| | | 13 | | /// Represents a fixed-point octree optimized for deterministic hierarchical spatial queries. |
| | | 14 | | /// </summary> |
| | | 15 | | public sealed class SwiftFixedOctree<T> : SwiftOctree<T, FixedBoundVolume> |
| | | 16 | | { |
| | | 17 | | /// <summary> |
| | | 18 | | /// Initializes a new instance of the <see cref="SwiftFixedOctree{T}"/> class. |
| | | 19 | | /// </summary> |
| | | 20 | | /// <param name="worldBounds">The immutable world bounds covered by the octree.</param> |
| | | 21 | | /// <param name="options">Backend-neutral octree options.</param> |
| | | 22 | | /// <param name="minNodeSize">The minimum child-node axis length allowed for fixed-point subdivision.</param> |
| | | 23 | | public SwiftFixedOctree(FixedBoundVolume worldBounds, SwiftOctreeOptions options, Fixed64 minNodeSize) |
| | 14 | 24 | | : base(worldBounds, options, new FixedBoundVolumeOctreePartitioner(minNodeSize)) |
| | 12 | 25 | | { } |
| | | 26 | | |
| | | 27 | | private sealed class FixedBoundVolumeOctreePartitioner : IOctreeBoundsPartitioner<FixedBoundVolume> |
| | | 28 | | { |
| | | 29 | | private readonly Fixed64 _minNodeSize; |
| | | 30 | | |
| | 14 | 31 | | public FixedBoundVolumeOctreePartitioner(Fixed64 minNodeSize) |
| | | 32 | | { |
| | 14 | 33 | | if (minNodeSize <= Fixed64.Zero) |
| | 2 | 34 | | throw new System.ArgumentOutOfRangeException(nameof(minNodeSize), minNodeSize, "Minimum node size must b |
| | | 35 | | |
| | 12 | 36 | | _minNodeSize = minNodeSize; |
| | 12 | 37 | | } |
| | | 38 | | |
| | | 39 | | public bool ContainsBounds(FixedBoundVolume outer, FixedBoundVolume inner) |
| | | 40 | | { |
| | 27 | 41 | | return inner.Min.X >= outer.Min.X && |
| | 27 | 42 | | inner.Min.Y >= outer.Min.Y && |
| | 27 | 43 | | inner.Min.Z >= outer.Min.Z && |
| | 27 | 44 | | inner.Max.X <= outer.Max.X && |
| | 27 | 45 | | inner.Max.Y <= outer.Max.Y && |
| | 27 | 46 | | inner.Max.Z <= outer.Max.Z; |
| | | 47 | | } |
| | | 48 | | |
| | | 49 | | public bool CanSubdivide(FixedBoundVolume bounds) |
| | | 50 | | { |
| | 4 | 51 | | Vector3d childSize = bounds.Size * Fixed64.Half; |
| | 4 | 52 | | return childSize.X >= _minNodeSize && |
| | 4 | 53 | | childSize.Y >= _minNodeSize && |
| | 4 | 54 | | childSize.Z >= _minNodeSize; |
| | | 55 | | } |
| | | 56 | | |
| | | 57 | | public bool TryGetContainingChildIndex(FixedBoundVolume nodeBounds, FixedBoundVolume entryBounds, out int childI |
| | | 58 | | { |
| | 15 | 59 | | Vector3d midpoint = (nodeBounds.Min + nodeBounds.Max) * Fixed64.Half; |
| | | 60 | | |
| | | 61 | | int xBit; |
| | 15 | 62 | | if (entryBounds.Min.X >= midpoint.X) |
| | 6 | 63 | | xBit = 1; |
| | 9 | 64 | | else if (entryBounds.Max.X <= midpoint.X) |
| | 8 | 65 | | xBit = 0; |
| | | 66 | | else |
| | | 67 | | { |
| | 1 | 68 | | childIndex = -1; |
| | 1 | 69 | | return false; |
| | | 70 | | } |
| | | 71 | | |
| | | 72 | | int yBit; |
| | 14 | 73 | | if (entryBounds.Min.Y >= midpoint.Y) |
| | 6 | 74 | | yBit = 1; |
| | 8 | 75 | | else if (entryBounds.Max.Y <= midpoint.Y) |
| | 7 | 76 | | yBit = 0; |
| | | 77 | | else |
| | | 78 | | { |
| | 1 | 79 | | childIndex = -1; |
| | 1 | 80 | | return false; |
| | | 81 | | } |
| | | 82 | | |
| | | 83 | | int zBit; |
| | 13 | 84 | | if (entryBounds.Min.Z >= midpoint.Z) |
| | 6 | 85 | | zBit = 1; |
| | 7 | 86 | | else if (entryBounds.Max.Z <= midpoint.Z) |
| | 6 | 87 | | zBit = 0; |
| | | 88 | | else |
| | | 89 | | { |
| | 1 | 90 | | childIndex = -1; |
| | 1 | 91 | | return false; |
| | | 92 | | } |
| | | 93 | | |
| | 12 | 94 | | childIndex = xBit | (yBit << 1) | (zBit << 2); |
| | 12 | 95 | | return true; |
| | | 96 | | } |
| | | 97 | | |
| | | 98 | | public FixedBoundVolume CreateChildBounds(FixedBoundVolume parentBounds, int childIndex) |
| | | 99 | | { |
| | 24 | 100 | | Vector3d midpoint = (parentBounds.Min + parentBounds.Max) * Fixed64.Half; |
| | 24 | 101 | | bool upperX = (childIndex & 1) != 0; |
| | 24 | 102 | | bool upperY = (childIndex & 2) != 0; |
| | 24 | 103 | | bool upperZ = (childIndex & 4) != 0; |
| | | 104 | | |
| | 24 | 105 | | return new FixedBoundVolume( |
| | 24 | 106 | | new Vector3d( |
| | 24 | 107 | | upperX ? midpoint.X : parentBounds.Min.X, |
| | 24 | 108 | | upperY ? midpoint.Y : parentBounds.Min.Y, |
| | 24 | 109 | | upperZ ? midpoint.Z : parentBounds.Min.Z), |
| | 24 | 110 | | new Vector3d( |
| | 24 | 111 | | upperX ? parentBounds.Max.X : midpoint.X, |
| | 24 | 112 | | upperY ? parentBounds.Max.Y : midpoint.Y, |
| | 24 | 113 | | upperZ ? parentBounds.Max.Z : midpoint.Z)); |
| | | 114 | | } |
| | | 115 | | } |
| | | 116 | | } |