gistfile1.cs

using System.Collections;
using System.Collections.Generic;
using UnityEngine;

// Camera spline. Naming it "CSpline" over something like "Path" or "Spline" to avoid potential conflicts
[System.Serializable] // Allow Unity-serialization
public class CSpline {
  
	[HideInInspector] 
	public Vector3[] _points; // Serialized but unlisted
	// Unserialized:
	private Vector3[] _pathPoints; // Points along the spline polyline
	private float[] _tauCache; // distance to each point, for binary search
	
	public float resolveAngle = 0.0f; // The degree of inaccuracy for an angle
			// (Lower = slower, smoother; Higher = faster, bumpier, 0 has no pruning )
	
	private bool isDirty = true; // Is dirty? Defaults to true.
	
	// Constructors
	public CSpline() {}
	public CSpline(params Vector3[] points) { _points = points; }
	public CSpline(int _itr, params Vector3[] points) { subdivideIterations = _itr; _points = points; }
	
	int subdivideIterations = 2; // Number of iterations
	
	public Vector3[] points {// = new[] { Vector3.forward, Vector3.zero, Vector3.left };
		get { return _points; }
		set {
			_points = value;
			isDirty = true;
		}
	}
	
	public Vector3[] smoothPoints {
		get {
			if (isDirty) resolve();
			return _pathPoints;
		}
	}
	
	private float _length;
	public float length {
		get { 
			if (isDirty) resolve();
			return _length; 
		}
	}
	
	public Vector3 pointAndTangent(float t, out Vector3 tangent) {
		var at = this[t];
		
		Vector3 offset;
		
		// Use right limit
		if (t < 0.01) t = 0.01f;
		if (t >= length) {
			offset = at - this[length - 0.01f];
		} else {
			offset = this[t + 0.01f] - at;
		}
		
		tangent = offset.normalized;
		
		return at;
	}
	
	public Vector3 this[float t] {
		get {
			if (isDirty) resolve();
			
			// Get the next greater index
			int index = System.Array.BinarySearch(_tauCache,t);
			
			// If there is an exact match (probably won't happen at any nonzero point)
			if (index >= 0) return _pathPoints[index]; // Simply return the matching point
			
			index = ~index; // Negate (Binary search returns the first greater index if there is not an exact match, negated)
			if (index == 0) return _pathPoints[index]; // Clamping in the case that the t value is before all points
			
			if (index >= _pathPoints.Length) return _pathPoints[_pathPoints.Length-1];
			
			// Find the current and next point, and our position between them.
			Vector3 at = _pathPoints[index-1], next = _pathPoints[index];
			var tau = Mathf.InverseLerp(_tauCache[index-1],_tauCache[index],t);
			
			return Vector3.Lerp(at,next,tau);
		}
	}
	
	
	public void resolve() {
		if (_points.Length < 3) { // Shouldn't work with under three points
			// Log an error with the active camera as context (since this is a camera spline, after all)
			throw new System.ArgumentException("Cannot resolve a spline with fewer than three points, spline has " + points.Length + " points");
		}
		
		isDirty = false;
		
		// Using subdivide and prune method to resolve spline into polyline (Since integrating distance is unreasonable)
		Vector3[] last = _points;
		
		// Subdivide the path (recursively)
		
		int itr = 0; // current iteration
		do {
			var sub = new List<Vector3>();
			// Iterate for all points except the last one
			for(int i = 0; i < last.Length; ++i) {
				// Grab the associated points
				Vector3 
					before = last[i-2 < 0 ? i-1 < 0 ? 0 : i - 1 : i - 2],
					at = last[i-1 < 0 ? 0 : i - 1],
					next = last[i],
					then = last[i+2 < last.Length ? i + 1 : last.Length - 1];
				
				// The splitting process
				sub.AddRange( new[] {
					cuspInterp(before,at,next,then,0),
					cuspInterp(before,at,next,then,0.125f),
					cuspInterp(before,at,next,then,0.25f),
					cuspInterp(before,at,next,then,0.375f),
					cuspInterp(before,at,next,then,0.5f),
					cuspInterp(before,at,next,then,0.625f),
					cuspInterp(before,at,next,then,0.75f),
					cuspInterp(before,at,next,then,0.875f)
					});
			}
			sub.Add(last[last.Length-1]); // Add the endpoint
			
			last = sub.ToArray();
			sub.Clear();
		} while (++itr < subdivideIterations);
		
		// Prune the path
		if (resolveAngle > 0f) {
			var sub = new List<Vector3>();
			Vector3 previous = last[0], heading = last[1] - last[0];
			for(int i = 0; i < last.Length-1; ++i) {
				var nHeading = last[i] - previous;
				var angle = Vector3.Angle(heading,nHeading);
				
				if (angle < resolveAngle) continue;
				
				heading = nHeading;
				previous = last[i];
				sub.Add(last[i]);
			}
			sub.Add(last[last.Length-1]);
			
			last = sub.ToArray();
		}
		
		// Build the length cache
		_length = 0f;
		_tauCache = new float[last.Length]; _tauCache[0] = 0f;
		for (int i = 1; i < last.Length; ++i) {
			_length += Vector3.Distance(last[i],last[i-1]); 
			_tauCache[i] = _length;
		}
		
		_pathPoints = last;
	}
	
	// Quadradic cusps
	private Vector3 cusp(Vector3 A, Vector3 B, Vector3 C, float t) {
		Vector3
			AB = Vector3.Lerp(A,B,t),
			BC = Vector3.Lerp(B,C,t);
		return Vector3.Lerp(AB,BC,t);
	}
	
	// Bezier Cusp interpolation (Could be improved by caching midpoints or bulk tau evaluation)
	private Vector3 cuspInterp(Vector3 prev, Vector3 last, Vector3 next, Vector3 then, float t) {
		// Fork on if we are doing the first or second half of the segment
		
		Vector3 mid = (last + next) * 0.5f;
		if (t > 0.5f) {
			Vector3 later = (next + then) * 0.5f;
			return cusp(mid,next,later,t - 0.5f);
		}
		Vector3 prior = (prev + last) * 0.5f;
		return cusp(prior,last,mid,t + 0.5f);
	}
}