| | | 1 | | //======================================================================= |
| | | 2 | | // Physics3DHitSorter.cs |
| | | 3 | | //======================================================================= |
| | | 4 | | // MIT License, Copyright (c) 2026–present David Oravsky (mrdav30) |
| | | 5 | | // See LICENSE file in the project root for full license information. |
| | | 6 | | //======================================================================= |
| | | 7 | | |
| | | 8 | | using SwiftCollections; |
| | | 9 | | using System.Runtime.CompilerServices; |
| | | 10 | | |
| | | 11 | | namespace Gravitas.Queries; |
| | | 12 | | |
| | | 13 | | internal static class Physics3DHitSorter |
| | | 14 | | { |
| | | 15 | | internal static void SortByDistance(SwiftList<Physics3DHit> hits) |
| | | 16 | | { |
| | 22690 | 17 | | SortByDistance(hits, 0, hits.Count); |
| | 22690 | 18 | | } |
| | | 19 | | |
| | | 20 | | internal static void SortByDistance(SwiftList<Physics3DHit> hits, int start, int count) |
| | | 21 | | { |
| | 22690 | 22 | | if (count < 2) |
| | 21836 | 23 | | return; |
| | | 24 | | |
| | 3432 | 25 | | for (int root = (count / 2) - 1; root >= 0; root--) |
| | 862 | 26 | | SiftDown(hits, start, root, count); |
| | | 27 | | |
| | 3968 | 28 | | for (int end = count - 1; end > 0; end--) |
| | | 29 | | { |
| | 1130 | 30 | | Swap(hits, start, start + end); |
| | 1130 | 31 | | SiftDown(hits, start, 0, end); |
| | | 32 | | } |
| | 854 | 33 | | } |
| | | 34 | | |
| | | 35 | | private static void SiftDown(SwiftList<Physics3DHit> hits, int start, int root, int count) |
| | | 36 | | { |
| | 950 | 37 | | while (true) |
| | | 38 | | { |
| | 2942 | 39 | | int child = (root * 2) + 1; |
| | 2942 | 40 | | if (child >= count) |
| | 1796 | 41 | | return; |
| | | 42 | | |
| | 1146 | 43 | | int swapIndex = root; |
| | 1146 | 44 | | if (ComesBefore(hits[start + swapIndex], hits[start + child])) |
| | 925 | 45 | | swapIndex = child; |
| | | 46 | | |
| | 1146 | 47 | | int right = child + 1; |
| | 1146 | 48 | | if (right < count && ComesBefore(hits[start + swapIndex], hits[start + right])) |
| | 242 | 49 | | swapIndex = right; |
| | | 50 | | |
| | 1146 | 51 | | if (swapIndex == root) |
| | 196 | 52 | | return; |
| | | 53 | | |
| | 950 | 54 | | Swap(hits, start + root, start + swapIndex); |
| | 950 | 55 | | root = swapIndex; |
| | | 56 | | } |
| | | 57 | | } |
| | | 58 | | |
| | | 59 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 60 | | internal static bool ComesBefore(Physics3DHit left, Physics3DHit right) |
| | | 61 | | { |
| | 1650 | 62 | | int distanceCompare = left.Distance.CompareTo(right.Distance); |
| | 1650 | 63 | | if (distanceCompare != 0) |
| | 1579 | 64 | | return distanceCompare < 0; |
| | | 65 | | |
| | 71 | 66 | | return (left.Collider?.Id ?? -1) < (right.Collider?.Id ?? -1); |
| | | 67 | | } |
| | | 68 | | |
| | | 69 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 70 | | private static void Swap(SwiftList<Physics3DHit> hits, int left, int right) |
| | | 71 | | { |
| | 2080 | 72 | | Physics3DHit temp = hits[left]; |
| | 2080 | 73 | | hits[left] = hits[right]; |
| | 2080 | 74 | | hits[right] = temp; |
| | 2080 | 75 | | } |
| | | 76 | | } |