diff --git a/Assets/Scripts/Pulse.cs b/Assets/Scripts/Pulse.cs index c1927f3..01af65a 100755 --- a/Assets/Scripts/Pulse.cs +++ b/Assets/Scripts/Pulse.cs @@ -7,11 +7,28 @@ { private static Vector3[] randomSpherePoints = null; - private static KdTree.KdTree randomSphereKd = new KdTree.KdTree(3, new FloatMath()); + private static KdTree.KdTree randomSphereKd = new KdTree.KdTree(3, new SphereMath()); + private static Dictionary> separatedPoints = new Dictionary>(); + + private class SphereMath : FloatMath + { + public override float MinValue => -1; + + public override float MaxValue => 1; + + public override float DistanceSquaredBetweenPoints(float[] a, float[] b) + { + Vector3 normA = new Vector3(a[0], a[1], a[2]); + Vector3 normB = new Vector3(b[0], b[1], b[2]); + return Mathf.Atan2(Vector3.Cross(normA, normB).magnitude, Vector3.Dot(normA, normB)); + } + } private static int randomSpherePointsCount = 300; private static void GenerateRandomPoints() { + if (randomSpherePoints != null) return; + randomSpherePoints = new Vector3[randomSpherePointsCount]; for (int i = 0; i < randomSpherePointsCount; i++) { @@ -21,13 +38,101 @@ Vector3 r = UnityEngine.Random.insideUnitSphere; if (r.sqrMagnitude > 0.000001f) { - randomSpherePoints[i] = r.normalized; ok = true; + + r.Normalize(); + randomSpherePoints[i] = r; + randomSphereKd.Add(new float[] { r.x, r.y, r.z }, 0); } } } } + /* + private class KdTreePoints : IEnumerable + { + private class KdTreeEnumerator : IEnumerator + { + public Vector3 Current => new Vector3(underlying.Current.Point[0], underlying.Current.Point[1], underlying.Current.Point[2]); + object IEnumerator.Current => Current; + public void Dispose() => underlying.Dispose(); + public bool MoveNext() => underlying.MoveNext(); + public void Reset() => underlying.Reset(); + + private IEnumerator> underlying; + public KdTreeEnumerator(KdTree.KdTree tree) + { + this.underlying = tree.GetEnumerator(); + } + } + private KdTree.KdTree tree; + public KdTreePoints(KdTree.KdTree tree) + { + this.tree = tree; + } + + public IEnumerator GetEnumerator() => new KdTreeEnumerator(tree); + IEnumerator IEnumerable.GetEnumerator() => new KdTreeEnumerator(tree); + } + */ + + private const float R1_SPHERE_AREA = 4 * Mathf.PI; + + private static float ArcLengthOfArea(float area) + { + // area = 2πd^2(1−cos(l / d)), where d = 1 is the sphere radius, and l is the arclength (disk radius) + + // area = 2π(1-cos(l)) + // area = 2π-2πcos(l) + // 2π-area=2πcos(l) + // (2π-area)/2π=cos(l) + // 1-(area/2π)=cos(l) + // l = acos(1-area/2π) + + return Mathf.Acos(1 - area / (Mathf.PI * 2)); + } + + private static IEnumerable GetNumRandomPointsOnSphere(int numPoints) + { + if (separatedPoints.ContainsKey(numPoints)) return separatedPoints[numPoints]; + + GenerateRandomPoints(); + + HashSet remaining = new HashSet(randomSpherePoints); + List points = new List(); + + float areaPerPoint = R1_SPHERE_AREA / numPoints; + float arclengthPerPoint = ArcLengthOfArea(areaPerPoint); + + while (points.Count < numPoints && remaining.Count > 0) + { + int random = Random.Range(0, remaining.Count); + foreach (Vector3 r in remaining) + { + if (random == 0) + { + points.Add(r); + + remaining.Remove(r); + + foreach (KdTree.KdTreeNode close in randomSphereKd.RadialSearch(new float[] { r.x, r.y, r.z }, arclengthPerPoint)) + { + remaining.Remove(new Vector3(close.Point[0], close.Point[1], close.Point[2])); + } + + break; + } + else + { + random--; + } + } + } + + separatedPoints[numPoints] = points; + return separatedPoints[numPoints]; + } + public float Lobes = 10; public float TimeScale = 1;