Increased speed of generating and querying splines (excluding straigh…

…t-line solver).
prime31 · Aug 5, 2015 · 3e2c923 · 3e2c923
1 parent c7e9971
commit 3e2c923
Show file tree

Hide file tree

Showing 3 changed files with 180 additions and 47 deletions.
diff --git a/Assets/Demo/scripts/GoKitSplineTest.cs b/Assets/Demo/scripts/GoKitSplineTest.cs
@@ -0,0 +1,110 @@
+/*
+
+	Spline Build and Query Tests - GoKit AbstractGoSplineSolver master vs speedysplines
+
+	Greg Harding greg@flightless.co.nz www.flightless.nz
+	Retina MacBook Pro 2012, OS X 10.9.5, Unity 5.1.2f1
+
+	Empty scene with single gameobject running this script.
+
+	Building splines;
+	master: Built 10000 splines with 0 lookups - avg 86.31397ms over 100 tests
+	speedysplines: Built 10000 splines with 0 lookups - avg 72.74738ms over 100 tests
+	~16% faster
+
+	Querying spline;
+	master: Built 1 splines with 10000 lookups - avg 46.2421ms over 100 tests
+	speedysplines: Built 1 splines with 10000 lookups - avg 5.12037ms over 100 tests
+	~89% faster
+
+	Building and querying splines;
+	master: Built 1000 splines with 1000 lookups - avg 4454.5128ms over 100 tests
+	speedysplines: Built 1000 splines with 1000 lookups - avg 514.76155ms over 100 tests
+	~88% faster
+	
+*/
+
+using UnityEngine;
+using System.Collections;
+using System.Collections.Generic;
+using System;
+using System.Diagnostics;
+
+public class GoKitSplineTest : MonoBehaviour {
+
+	// test settings
+	public float testDelay = 5f;
+	public float retestDelay = 1f;
+	protected List<double> testTimes;
+
+	public int splineCount = 100;
+	public int splineLookupCount = 100;
+
+	// spline
+	protected Vector3 startPosition = Vector3.zero;
+	protected Vector3 controlPosition1 = Vector3.one;
+	protected Vector3 controlPosition2 = Vector3.right;
+	protected Vector3 endPosition = Vector3.zero;
+
+	protected Vector3[] splineNodes;
+
+
+	protected void Start() {
+		testTimes = new List<double>(100);
+
+		splineNodes = new Vector3[] { startPosition, controlPosition1, controlPosition2, endPosition };
+
+		Invoke("BuildSplines", testDelay);
+	}
+
+	protected void BuildSplines() {
+		Stopwatch stopWatch = new Stopwatch();
+		stopWatch.Start();
+
+		BuildSplines(splineCount);
+
+		stopWatch.Stop();
+
+		TimeSpan ts = stopWatch.Elapsed;
+		testTimes.Add(ts.TotalMilliseconds);
+
+		UnityEngine.Debug.Log(string.Format("Built {0} splines with {1} lookups in {2}ms (avg {3}ms over {4} tests)", splineCount, splineLookupCount, ts.TotalMilliseconds, GetAverage(testTimes), testTimes.Count));
+
+		Invoke("BuildSplines", retestDelay);
+	}
+
+	protected void BuildSplines(int num) {
+		for (int s=0; s<num; s++) {
+			GoSpline spline = new GoSpline(splineNodes);
+			spline.buildPath();
+
+			if (splineLookupCount > 0) {
+				LookupSpline(spline);
+			}
+		}
+	}
+
+	protected void LookupSpline(GoSpline spline) {
+		float tStep = 1f / splineLookupCount;
+
+		float t = tStep;
+		for (int i=0; i<splineLookupCount; i++) {
+			spline.getPointOnPath(t);
+			t += tStep;
+		}
+	}
+
+	protected double GetAverage(List<double> values) {
+		// no data?
+		if (values.Count == 0) return 0;
+
+		// sum
+		double sum = 0;
+		for (int t=0; t<values.Count; t++) {
+			sum += values[t];
+		}
+
+		// avg
+		return sum / values.Count;
+	}
+}
diff --git a/Assets/Demo/scripts/GoKitSplineTest.cs.meta b/Assets/Demo/scripts/GoKitSplineTest.cs.meta
diff --git a/Assets/Plugins/GoKit/properties/splines/AbstractGoSplineSolver.cs b/Assets/Plugins/GoKit/properties/splines/AbstractGoSplineSolver.cs
@@ -20,26 +20,46 @@ public float pathLength
 	// how many subdivisions should we divide each segment into? higher values take longer to build and lookup but
 	// result in closer to actual constant velocity
 	protected int totalSubdivisionsPerNodeForLookupTable = 5;
-	protected Dictionary<float, float> _segmentTimeForDistance; // holds data in the form [time:distance] as a lookup table
-
-
-
+
+	// time:distance lookup table
+	protected struct Segment
+	{
+		public float time;
+		public float distance;
+
+		public Segment ( float time, float distance )
+		{
+			this.time = time;
+			this.distance = distance;
+		}
+	}
+
+	protected List<Segment> segments;
+
+
 	// the default implementation breaks the spline down into segments and approximates distance by adding up
 	// the length of each segment
 	public virtual void buildPath()
 	{
-		var totalSudivisions = _nodes.Count * totalSubdivisionsPerNodeForLookupTable;
+		// build or clear segments cache
+		var totalSubdivisions = _nodes.Count * totalSubdivisionsPerNodeForLookupTable;
+		if( segments == null )
+		{
+			segments = new List<Segment>(totalSubdivisions);
+		}
+		else
+		{
+			segments.Clear();
+			segments.Capacity = totalSubdivisions;
+		}
+
 		_pathLength = 0;
-		float timePerSlice = 1f / totalSudivisions;
-
-		// we dont care about the first node for distances because they are always t:0 and len:0
-		_segmentTimeForDistance = new Dictionary<float, float>( totalSudivisions );
-
-
+		float timePerSlice = 1f / totalSubdivisions;
 		var lastPoint = getPoint( 0 );
 
 		// skip the first node and wrap 1 extra node
-        for( var i = 1; i < totalSudivisions + 1; i++ )
+		// we dont care about the first node for distances because they are always t:0 and len:0
+        for( var i = 1; i < totalSubdivisions + 1; i++ )
         {
 			// what is the current time along the path?
             float currentTime = timePerSlice * i;
@@ -48,7 +68,8 @@ public virtual void buildPath()
             _pathLength += Vector3.Distance( currentPoint, lastPoint );
             lastPoint = currentPoint;
 
-            _segmentTimeForDistance.Add( currentTime, _pathLength );
+			// cache segment
+			segments.Add(new Segment(currentTime, _pathLength));
         }
 	}
 
@@ -65,44 +86,34 @@ public virtual void buildPath()
 	public virtual Vector3 getPointOnPath( float t )
 	{
 		// we know exactly how far along the path we want to be from the passed in t
-		var targetDistance = _pathLength * t;
-
-		// store the previous and next nodes in our lookup table
-		var previousNodeTime = 0f;
-		var previousNodeLength = 0f;
-		var nextNodeTime = 0f;
-		var nextNodeLength = 0f;
-
-		float[] keysSegmentTimeForDistance = new float[_segmentTimeForDistance.Keys.Count];
-		_segmentTimeForDistance.Keys.CopyTo ( keysSegmentTimeForDistance, 0 );
+		float targetDistance = _pathLength * t;
 
 		// loop through all the values in our lookup table and find the two nodes our targetDistance falls between
-		for( int k = 0; k < keysSegmentTimeForDistance.Length; ++k )
+		// translate the values from the lookup table estimating the arc length between our known nodes from the lookup table
+		int nextSegmentIndex;
+		for( nextSegmentIndex = 0; nextSegmentIndex < segments.Count; nextSegmentIndex++ )
 		{
-			float key = keysSegmentTimeForDistance[k];
-			float value = _segmentTimeForDistance[key];
-
-			// have we passed our targetDistance yet?
-		    if( value >= targetDistance )
-		    {
-		        nextNodeTime = key;
-		        nextNodeLength = value;
-
-		        if( previousNodeTime > 0 )
-		            previousNodeLength = _segmentTimeForDistance[previousNodeTime];
-
-		        break;
-		    }
-		    previousNodeTime = key;
+			if( segments[nextSegmentIndex].distance >= targetDistance )
+				break;
 		}
-
-		// translate the values from the lookup table estimating the arc length between our known nodes from the lookup table
-		var segmentTime = nextNodeTime - previousNodeTime;
-		var segmentLength = nextNodeLength - previousNodeLength;
-		var distanceIntoSegment = targetDistance - previousNodeLength;
-
-		t = previousNodeTime + ( distanceIntoSegment / segmentLength ) * segmentTime;
-
+
+		Segment nextSegment = segments[nextSegmentIndex];
+
+		if( nextSegmentIndex == 0 ) {
+			// t within first segment
+			t = ( targetDistance / nextSegment.distance ) * nextSegment.time;
+		}
+		else
+		{
+			// t within prev..next segment
+			Segment previousSegment = segments[nextSegmentIndex-1];
+
+			float segmentTime = nextSegment.time - previousSegment.time;
+			float segmentLength = nextSegment.distance - previousSegment.distance;
+
+			t = previousSegment.time + ( ( targetDistance - previousSegment.distance ) / segmentLength ) * segmentTime;
+		}
+
 		return getPoint( t );
 	}