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