| | | 1 | | //======================================================================= |
| | | 2 | | // GjkSimplexPolicy.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 FixedMathSharp; |
| | | 9 | | using System; |
| | | 10 | | using System.Runtime.CompilerServices; |
| | | 11 | | |
| | | 12 | | namespace Gravitas.CollisionHandling; |
| | | 13 | | |
| | | 14 | | internal static class GjkSimplexPolicy |
| | | 15 | | { |
| | | 16 | | public static void AddPoint(Span<Vector3d> simplex, ref int count, Vector3d point) |
| | | 17 | | { |
| | 8972 | 18 | | for (int i = Math.Min(count, 3); i > 0; i--) |
| | 3009 | 19 | | simplex[i] = simplex[i - 1]; |
| | | 20 | | |
| | 1477 | 21 | | simplex[0] = point; |
| | 1477 | 22 | | if (count < 4) |
| | 1476 | 23 | | count++; |
| | 1477 | 24 | | } |
| | | 25 | | |
| | | 26 | | public static bool Update(Span<Vector3d> simplex, ref int count, ref Vector3d direction) |
| | | 27 | | { |
| | 1476 | 28 | | return count switch |
| | 1476 | 29 | | { |
| | 475 | 30 | | 2 => UpdateLine(simplex, ref count, ref direction), |
| | 472 | 31 | | 3 => UpdateTriangle(simplex, ref count, ref direction), |
| | 529 | 32 | | _ => UpdateTetrahedron(simplex, ref count, ref direction) |
| | 1476 | 33 | | }; |
| | | 34 | | } |
| | | 35 | | |
| | | 36 | | public static bool UpdateLine(Span<Vector3d> simplex, ref int count, ref Vector3d direction) |
| | | 37 | | { |
| | 482 | 38 | | Vector3d a = simplex[0]; |
| | 482 | 39 | | Vector3d b = simplex[1]; |
| | 482 | 40 | | Vector3d ab = b - a; |
| | 482 | 41 | | Vector3d ao = -a; |
| | | 42 | | |
| | 482 | 43 | | if (SameDirection(ab, ao)) |
| | | 44 | | { |
| | 480 | 45 | | direction = TripleCross(ab, ao, ab); |
| | 480 | 46 | | if (direction.MagnitudeSquared <= Fixed64.Epsilon) |
| | 225 | 47 | | direction = Perpendicular(ab); |
| | 480 | 48 | | return false; |
| | | 49 | | } |
| | | 50 | | |
| | 2 | 51 | | simplex[0] = a; |
| | 2 | 52 | | count = 1; |
| | 2 | 53 | | direction = ao; |
| | 2 | 54 | | return false; |
| | | 55 | | } |
| | | 56 | | |
| | | 57 | | public static bool UpdateTriangle(Span<Vector3d> simplex, ref int count, ref Vector3d direction) |
| | | 58 | | { |
| | 478 | 59 | | Vector3d a = simplex[0]; |
| | 478 | 60 | | Vector3d b = simplex[1]; |
| | 478 | 61 | | Vector3d c = simplex[2]; |
| | 478 | 62 | | Vector3d ab = b - a; |
| | 478 | 63 | | Vector3d ac = c - a; |
| | 478 | 64 | | Vector3d ao = -a; |
| | 478 | 65 | | Vector3d abc = Vector3d.Cross(ab, ac); |
| | | 66 | | |
| | 478 | 67 | | Vector3d acPerp = Vector3d.Cross(abc, ac); |
| | 478 | 68 | | if (SameDirection(acPerp, ao)) |
| | | 69 | | { |
| | 7 | 70 | | if (SameDirection(ac, ao)) |
| | | 71 | | { |
| | 6 | 72 | | simplex[1] = c; |
| | 6 | 73 | | count = 2; |
| | 6 | 74 | | direction = TripleCross(ac, ao, ac); |
| | 6 | 75 | | if (direction.MagnitudeSquared <= Fixed64.Epsilon) |
| | 1 | 76 | | direction = Perpendicular(ac); |
| | 6 | 77 | | return false; |
| | | 78 | | } |
| | | 79 | | |
| | 1 | 80 | | simplex[1] = b; |
| | 1 | 81 | | count = 2; |
| | 1 | 82 | | return UpdateLine(simplex, ref count, ref direction); |
| | | 83 | | } |
| | | 84 | | |
| | 471 | 85 | | Vector3d abPerp = Vector3d.Cross(ab, abc); |
| | 471 | 86 | | if (SameDirection(abPerp, ao)) |
| | | 87 | | { |
| | 3 | 88 | | simplex[1] = b; |
| | 3 | 89 | | count = 2; |
| | 3 | 90 | | return UpdateLine(simplex, ref count, ref direction); |
| | | 91 | | } |
| | | 92 | | |
| | 468 | 93 | | if (SameDirection(abc, ao)) |
| | | 94 | | { |
| | 12 | 95 | | direction = abc; |
| | 12 | 96 | | return false; |
| | | 97 | | } |
| | | 98 | | |
| | 456 | 99 | | simplex[1] = c; |
| | 456 | 100 | | simplex[2] = b; |
| | 456 | 101 | | direction = -abc; |
| | 456 | 102 | | return false; |
| | | 103 | | } |
| | | 104 | | |
| | | 105 | | public static bool UpdateTetrahedron(Span<Vector3d> simplex, ref int count, ref Vector3d direction) |
| | | 106 | | { |
| | 533 | 107 | | Vector3d a = simplex[0]; |
| | 533 | 108 | | Vector3d b = simplex[1]; |
| | 533 | 109 | | Vector3d c = simplex[2]; |
| | 533 | 110 | | Vector3d d = simplex[3]; |
| | 533 | 111 | | Vector3d ao = -a; |
| | | 112 | | |
| | 533 | 113 | | Vector3d abc = OrientFaceNormal(a, b, c, d); |
| | 533 | 114 | | if (SameDirection(abc, ao)) |
| | | 115 | | { |
| | 32 | 116 | | simplex[0] = a; |
| | 32 | 117 | | simplex[1] = b; |
| | 32 | 118 | | simplex[2] = c; |
| | 32 | 119 | | count = 3; |
| | 32 | 120 | | direction = abc; |
| | 32 | 121 | | return false; |
| | | 122 | | } |
| | | 123 | | |
| | 501 | 124 | | Vector3d acd = OrientFaceNormal(a, c, d, b); |
| | 501 | 125 | | if (SameDirection(acd, ao)) |
| | | 126 | | { |
| | 23 | 127 | | simplex[0] = a; |
| | 23 | 128 | | simplex[1] = c; |
| | 23 | 129 | | simplex[2] = d; |
| | 23 | 130 | | count = 3; |
| | 23 | 131 | | direction = acd; |
| | 23 | 132 | | return false; |
| | | 133 | | } |
| | | 134 | | |
| | 478 | 135 | | Vector3d adb = OrientFaceNormal(a, d, b, c); |
| | 478 | 136 | | if (SameDirection(adb, ao)) |
| | | 137 | | { |
| | 14 | 138 | | simplex[0] = a; |
| | 14 | 139 | | simplex[1] = d; |
| | 14 | 140 | | simplex[2] = b; |
| | 14 | 141 | | count = 3; |
| | 14 | 142 | | direction = adb; |
| | 14 | 143 | | return false; |
| | | 144 | | } |
| | | 145 | | |
| | 464 | 146 | | return true; |
| | | 147 | | } |
| | | 148 | | |
| | | 149 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 150 | | private static bool SameDirection(Vector3d first, Vector3d second) => |
| | 3418 | 151 | | Vector3d.Dot(first, second) > Fixed64.Zero; |
| | | 152 | | |
| | | 153 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 154 | | private static Vector3d TripleCross(Vector3d first, Vector3d second, Vector3d third) => |
| | 486 | 155 | | Vector3d.Cross(Vector3d.Cross(first, second), third); |
| | | 156 | | |
| | | 157 | | private static Vector3d OrientFaceNormal(Vector3d a, Vector3d b, Vector3d c, Vector3d opposite) |
| | | 158 | | { |
| | 1512 | 159 | | Vector3d normal = Vector3d.Cross(b - a, c - a); |
| | 1512 | 160 | | return Vector3d.Dot(normal, opposite - a) > Fixed64.Zero ? -normal : normal; |
| | | 161 | | } |
| | | 162 | | |
| | | 163 | | private static Vector3d Perpendicular(Vector3d vector) |
| | | 164 | | { |
| | 226 | 165 | | Vector3d candidate = Vector3d.Cross(vector, Vector3d.Up); |
| | 226 | 166 | | if (candidate.MagnitudeSquared > Fixed64.Epsilon) |
| | 224 | 167 | | return candidate; |
| | | 168 | | |
| | 2 | 169 | | candidate = Vector3d.Cross(vector, Vector3d.Right); |
| | 2 | 170 | | return candidate.MagnitudeSquared > Fixed64.Epsilon ? candidate : Vector3d.Forward; |
| | | 171 | | } |
| | | 172 | | } |