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